C版
实验一 线性表的顺序存储实验
一、实验目的
1. 掌握用Visual C++6.0上机调试顺序表的基本方法。
2. 掌握顺序表的基本操作，插入、删除、查找等算法的实现。
二、实验内容
问题描述：实现线性表的基本操作：构造空的线性表、建立线性表、求表长、获取第
ｉ个元素、插入、删除、输出线性表等。
基本要求：在顺序存储结构下实现。并在主程序中完成输出开始建立的线性表，输出
获取的元素，输出表长，输出在插入和删除操作后的线性表的工作。
测试数据：给定线性表23、33、21、45、67，获取第３个元素的值，在第３个元素
之前插入38，删除第５个元素。
实现提示：１．完成顺序表的类定义；２．编写主程序；３．调试运行程序；４．记
录并分析程序中出现的错误以及解决办法和实验结果。
实验二 单链表实验
一、实验目的
1. 掌握用Visual C++6.0上机调试单链表的基本方法
2. 掌握单链表的基本操作，插入、删除、查找、求表等算法的实现
二、实验内容
问题描述：实现线性表的基本操作：构造空的线性表、建立线性表、求表长、获取
第ｉ个元素、插入、删除、输出线性表等。
基本要求：在链式存储结构下实现。并在主程序中完成输出开始建立的线性表，输
出获取的元素，输出表长，输出在插入和删除操作后的线性表的工作。
测试数据：给定线性表23、33、21、45、67，获取第３个元素的值，在第３个元
素之前插入38，删除第５个元素。
实现提示：１．完成单链表的类定义；２．编写主程序；３．调试运行程序；４．记
录并分析程序中出现的错误以及解决办法和实验结果。
实验三 栈及其应用实验
一、实验目的
掌握栈的基本操作算法实现及栈的应用方法。
二、实验内容
问题描述：编写程序，实现检查一个表达式（或文本文件）中的花括号、方括号和
圆括号是否配对，并输出检测结果。
实验四 稀疏矩阵及其运算实验
一、实验目的
掌握稀疏矩阵的压缩存储表示及其运算。 二、实验内容
设计存储结构实现稀疏矩阵的压缩存储； 设计算法实现稀疏矩阵的快速转置； 分析算法的时间复杂度。
实验五 树实验
一、实验目的
1. 掌握二叉树的链式存储结构的定义及实现方法。 2. 掌握二叉树的先序、中序和后序遍历方法。 3. 掌握二叉树的结点个数和树的深度的计算方法。
二、实验内容
1. 建立一棵含有n个结点的二叉树，采用二叉链表存储。
2. 分别用前序、中序和后序遍历该二叉树，输出访问到的结点。 3. 计算该二叉树的结点个数和二叉树的深度，输出计算结果。
实验六 图实验
一、实验目的
1. 掌握图的含义。 2. 掌握图的存储结构。
3. 理解并掌握图中求最短路径的算法。 二、实验内容
医院选址问题。 1. 问题描述：
n个村庄之间的交通图可以用有向网来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n各村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？ 2. 基本要求：(1) 建立模型，设计存储结构。 (2) 设计算法完成问题求解。 (3) 分析算法的时间复杂度。
测试图：
2 1 a b 2 c 4 3 e 1 d 5
实验七 查找实验
一、实验目的
1. 掌握二叉排序树的定义、特性和建立方法。 2. 掌握基于二叉排序树的查找技术。
二、实验内容
问题描述：给定一组无序序列，建立一颗二叉排序树，在该树上实现查找操作；分
析二叉排序树的查找性能。
实验八 排序实验
一、实验目的
1. 掌握各类排序算法。
2. 了解各类排序算法的时间性能。
二、实验内容
1. 设计并实现各类排序算法；
2. 产生正序和逆序的初始排列分别调用各类排序算法，并比较时间性能。 3. 产生随机的初始排列分别调用各类排序算法，并比较时间性能。
实验报告书写格式要求
一、实验目的 1. ******** 2. ******** 二、实验内容 1. ********
2. ******** 三、设计与编码
1. 本实验用到的理论知识概述（要求简明扼要） 2. 算法设计与编码
1.1 对本实验内容设计其存储结构及运算（函数声明）。
1.2 将算法转化为C程序，书写主要函数的实现部分，设计并书写主函数完成实验项
目。
四、运行与测试
1. 在调试程序的过程中遇到什么问题，是如何解决的？ 2. 设计了哪些测试数据？测试结果是什么？
