《数据结构》实验指导手册计算机教研室1．实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解，掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。
2．实验教学的要求：学生每次实验前必须根据实验指导手册，设计出实验方案（程序和实验步骤）；在实验过程中要求独立进行程序调试和排错，必须学会使用在线帮助解决实验中遇到的问题，必须应用理论知识分析问题、解决问题。
3．实验内容：实验1：VC6的使用一、实验目的理解和掌握如何使用Visual C＋＋环境编写C/C＋＋程序。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计4学时。
三、实验内容1、熟悉VC6环境掌握如何创建控制台应用程序。
掌握一些常用快捷键，例如编译F7，运行Ctrl＋F5，调试运行F5，单步运行F10/F11，设置断点F9，格式化代码Alt＋F8。
2、掌握如何编译程序理解编译过程中的错误信息，并掌握如何排错。
3、掌握如何调试程序掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。
4、实验题：完成实验教材的实验题、、。
要求：实现该实验结果。
通过该实验题，熟悉VC6环境下的程序编写、编译、调试。
一、实验目的（1）掌握顺序表的各种基本运算的实现。
（2）能够利用基本运算进行顺序表的操作。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计2学时。
三、实验内容1、顺序表基本运算实现顺序表的各种基本运算；并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序表L（元素类型为char型）（2）依次采用尾插法插入a, b, c, d, e元素（3）输出顺序表L（4）输出顺序表L的长度（5）判断顺序表L是否为空（6）输出顺序表L的第3个元素（7）输出元素’a’的位置（8）在第4个元素位置上插入’f’元素（9）输出顺序表L（10）删除顺序表L的第3个元素（11）输出顺序表（12）释放顺序表提示：可以参考上课教材、实验教材的实验题。
2、顺序表的应用（选做）（1）设计通讯录（也可为其他应用）文件的存储格式和线性表的顺序存储结构（2）设计在通讯录（也可为其他应用）中添加、删除、查找某个节点信息程序（3）调试程序一、实验目的（1）掌握链表的概念；掌握单链表的各种基本运算的实现。
（2）能够利用基本运算进行单链表的操作。
（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计2学时。
三、实验内容实现单链表的各种基本运算；并在此基础上设计一个主程序，完成如下功能：（1）初始化单链表L（2）依次采用尾插法插入a, b, c, d, e元素（3）输出单链表L（4）输出单链表L的长度（5）判断单链表L是否为空（6）输出单链表L的第3个元素（7）输出元素’a’的位置（8）在第4个元素位置上插入’f’元素（9）输出单链表L（10）删除单链表L的第3个元素（11）输出单链表L（12）释放单链表L提示：可以参考上课教材、实验教材的实验题。
实验4：单链表综合实验一、实验目的（1）能够利用单链表的基本运算进行单链表的相关操作。
（2）掌握文件的应用（3）加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计4学时。
三、实验内容1、通讯录设计设计一个班级同学的通讯录，要求如下：通讯录中每个同学的信息包含以下内容：学号（id）、姓名（name）、电话号码（tel）。
如果需要更多其他信息，请自行添加。
程序主菜单包含以下几个功能：（1）添加记录：通过键盘输入信息，添加一条通讯录记录。
（2）删除记录：通过键盘输入学号，删除该学号的记录。
（3）输出记录：输出通讯录全部记录。
（4）按姓名查找：通过键盘输入姓名，输出该同学的所有信息。
（5）保存记录：把通讯录中所有的记录保存到文件中。
（6）清空记录：删除通讯录中的全部记录，并删除文件。
（7）退出提示：程序启动时应判断是否存在记录文件，如果存在，则读取每条记录到链表中。
用户选择并完成主菜单某功能后，除了退出程序，应该返回主菜单。
添加一条记录时，插入到链表的尾部。
查找、删除记录时，如果该记录不存在，则应该输出不存在的提示。
添加记录、删除记录时不需要写文件。
保存记录时，用覆盖写文件的方法。
（或者先删除原文件，再保存全部记录信息）各个功能模块写成函数，由主函数调用。
选做：主菜单增加一个排序功能选项，可以按照学号从小到大进行排序。
排序方法可以用冒泡排序或者插入排序。
实验5：链栈的基本操作一、实验目的1）熟悉栈的定义和栈的基本操作。
2）掌握链式存储栈的基本运算。
3）加深对栈数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计2学时。
三、实验内容必做内容：链栈的基本操作编写栈的基本操作函数1．栈类型的定义，数据域使用char型typedef char ElemType;typedef struct node{ElemType data;struct node *next;} LinkStack;2．初始化空栈：函数原型如下：void InitLinkStack（ LinkStack * & s）其中函数参数为LinkStack * & 类型，表示指向创建的空栈的指针，并且用引用方式传入。
3. 判断是否空栈：函数原型如下：int IsEmptyLinkStack（LinkStack *s ）其中函数参数为栈指针；返回值为int型，1表示是空栈，0表示不是空栈。
4. 入栈：函数原型如下：void PushLinkStack（LinkStack* &s , ElemType x）其中函数参数s为栈指针，x为入栈的数据。
5. 出栈：函数原型如下：int PopLinkStack (LinkStack* & s, ElemType &x)其中函数参数s为栈指针，x为出栈的数据的引用；返回值为int型，1表示出栈成功，0表示出栈失败。
6．取栈顶元素：(栈保持不变)函数原型如下：int GetLinkStackTop (LinkStack* s, ElemType &x)其中函数参数s为栈指针，x存放栈顶元素值；返回值为int型，1表示成功，0表示失败。
编写主函数调用上述函数实现下列操作。
1．初始化空栈。
2. 键盘输入字符，使得输入的字符依次入栈（结束符号自定，例如回车键(值为10)或'#'）每插入一个元素，必须输出当时的栈顶元素(调用GetLinkStackTop函数)。
3．判断链栈是否为空。
输出判断结果。
4．调用出栈函数，打印出栈元素的值；反复此步骤，直至栈为空。
5．判断链栈是否为空。
输出判断结果。
6．释放链栈。
选做内容（一）：判断对称字符串设计一个算法，调用栈的基本运算，判断一个字符串是否为对称字符串。
若是返回1；否则返回0。
例如：“abcba”和“abba”都是对称字符串。
实验6：队列的基本操作一、实验目的1）熟悉队列的定义和队列的基本操作。
2）掌握顺序循环队列和链式存储队列的基本运算。
3）加深对队列数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计2学时。
三、实验内容队列的基本操作队列的存储结构从顺序循环队列或者链队任选一种。
编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列q（2）判断q是否非空（3）依次进队元素a，b，c（4）出队一个元素，输出该元素（5）输出队列q的元素个数（6）依次进队列元素d，e，f（7）输出队列q的元素个数（8）输出出队序列（9）释放队列实验7：栈和队列综合实验一、实验目的（1）能够利用栈和队列的基本运算进行相关操作。
（2）进一步熟悉文件的应用（3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计4学时。
三、实验内容以下两个实验任选一个。
1、迷宫求解设计一个迷宫求解程序，要求如下：以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
能任意设定的迷宫（选作）如果有通路，列出所有通路提示：以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11010101010101010111入口位置：1 1出口位置：8 8探索过程可采用如下算法，设定当前位置的初值为入口位置；do {若当前位置可通，则｛ 将当前位置插入栈顶；若该位置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置；｝否则，｛若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， （1） 则｛删去栈顶位置；ABDCEHJ KL MNF GI有向图G的邻接矩阵:0 5 0 7 0 00 0 4 0 0 08 0 0 0 0 90 0 5 0 0 60 0 0 5 0 03 0 0 0 1 0图G的邻接矩阵转换成邻接表: 0: 1 31: 22: 0 53: 2 54: 35: 0 4从顶点0开始的DFS:0 1 2 5 4 3从顶点0开始的BFS:0 1 3 2 5 4，哈希函数为H(k)=key%p，（p取13），并采用线性探查法解决冲突。
（2）在上述哈希表中查找关键字为29的记录。
（3）在上述哈希表中删除关键字为77的记录，再将其插入。
【输出结果】输出结果例子如下：一、实验目的1）熟悉查找的基本操作。
2）掌握二叉排序树的基本运算。
3）加深对查找的理解，逐步培养解决实际问题的编程能力。
二、实验环境装有Visual C＋＋的计算机。
本次实验共计4学时。
三、实验内容1、统计字符串中字符出现的次数编写一个程序，由键盘输入一个字符串，统计该字符串中出现的字符及其次数。
然后输出结果。
要求用一个二叉树来保存处理结果，字符串中每个不同的字符用树的结点表示，结点应该包含四个域：该字符、该字符出现的次数、左子树指针、右子树指针；其中左子树的字符的ASCII码均小于该字符，右子树的字符的ASCII码均大于该字符。
提示：从字符串中依次读取字符，在二叉树中查找该字符是否存在。
如果存在，则该字符的出现次数加1；如果不存在，则按照二叉排序树的要求插入该字符结点，同时设置出现次数为1。
全部字符读完以后，调用二叉树的中序遍历，有序的输出每个字符及其出现的次数。
2、二叉排序树【基本要求】编写一个程序，实现二叉排序树的基本运算，并在此基础上完成如下功能：（1）由{4，9，0，1，8，6，3，5，2，7}创建一棵二叉排序树bt，并以括号表示法输出。