数据结构操作题
实验一线性表操作
一、实验目的
1 熟悉并掌握线性表的逻辑结构、物理结构。
2 熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。
3 熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
4 熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。
二、实验要求
1 实验之前认真准备，编写好源程序。
2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3 不断积累程序的调试方法。
三、实验内容
基本题:
1 对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。
加强、提高题：
2、编写一个求解Josephus问题的函数。用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。最后分析所完成算法的时间复杂度。定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。（可以选做其中之一）
加强题：
1、采用数组作为求解过程中使用的数据结构。
提高题：
2、采用循环链表作为求解过程中使用的数据结构。运行时允许指定任意n、s、m数值，直至输入 n = 0 退出程序。
实验二栈、队列的实现、递归应用
一、实验目的
1 熟悉栈、队列这种特殊线性结构的特性
2 熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。
二、实验要求
1 实验之前认真准备，编写好源程序。
2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3 不断积累程序的调试方法。
三、实验内容
基本题（必做）：
1 分别就栈的顺序存储结构和链式存储结构实现
栈的各种基本操作。
2 、假设以带头结点的循环链表表示队列，并且
只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。加强题：
1、设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx 都是中心对称的字符串。
提高题：
1、试编写程序：
a.将中缀表达式计算转换成后缀表达式。
b.后缀表达式的计算实现4.2.2中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。
实验三树、图的实现与应用
一、实验目的
1 理解树结构的逻辑特性
2 熟练掌握二叉树的逻辑结构特性及各种存储方法
3 熟练掌握二插树的各种基本操作，尤其是三种遍历
4 熟练掌握图的存储结构
5 掌握图的邻接矩阵和邻接表表示分别进行深度和广度优先搜索遍历的算法。
6 了解图的最小生成树算法。
二、实验要求
1 实验之前认真准备，编写好源程序。
2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3 不断积累程序的调试方法。
三、实验内容
基本题
1、给定一棵用链表表示的二叉树，其根指针为root，试写出求二叉树结点数目。
2、对图的邻接矩阵和邻接表表示分别进行深度优先搜索遍历算法的实现。
加强题
1、试写出中序遍历二叉树的递归和非递归程序并调试。
2、写出中序线索二叉树的中序遍历程序并调试。
提高题
1、实现霍夫曼编、解码
（1）输入一系列字符及其出现频率并以此构造霍夫曼树进行编码并输出码表，另输入一段文字，对其进行霍夫曼编码。例：CASTCASTSATATATASA
（2）在1中已构成的霍夫曼树的基础上，输入一段01编码，要求输出其解码的原文。例：111011001110110011001001001001100
2、校园导游咨询。要求：
（1）设计一个校园的平面图，所含景点不少于8个。以图中的顶点表示校内各景点，
存放景点名称、代号、简介等信息。以边表示路径，存放路径长度等相关信息。
（2）为来访客人图中任意景点相关信息的查询。
（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路。
实验四搜索
一、实验目的
1 熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种存储结构下实现
2 熟练掌握二叉排序树的特性、建立方法以及动态搜索算法
3 熟练掌握散列表的特点及构造方法
二、实验要求
1 实验之前认真准备，编写好源程序。
2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3 不断积累程序的调试方法。
三、实验内容
基本题
1、实现基于有序顺序表的折半搜索。
2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。加强题
1、若输入 12000个不同的整数，其值介于0和19999之间，用散列法将这些数进行存储，散列函数为H(n)=n/2，请设计实现程序并调试。
提高题
1、建立二叉搜索树、实现其删除算法。要求：实现后分析其时间复杂度
实验五排序
一、实验目的
1 熟练掌握各种内排序方法，深刻理解排序算法及其执行过程
2 学会分析各种内排序算法的性能
3 了解各种排序方法的优缺点，对于实际问题能够选择一种较好的排序方案
二、实验要求
1 实验之前认真准备，编写好源程序。
2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。
3 不断积累程序的调试方法。
三、实验内容
基本题
1、希尔排序算法的实现。
2、快速排序算法的实现。
加强题（可选择其中之一）
1、堆排序算法的实现
2、给出n个学生的考试成绩表，成绩表由姓名和分数组成，试设计一个程序实现：（1）按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次。
（2）按照名次列出每个学生的姓名和成绩。
提高题
1、输入若干个国家的名称，请按照字典顺序将这些国名进行排序（所有名称全部大写或全部小写）。