数据结构实验指导书实验一线性表的顺序存储结构一、实验学时 4学时二、背景知识:顺序表的插入、删除及应用。
三、目的要求：1．掌握顺序存储结构的特点。
2．掌握顺序存储结构的常见算法。
四、实验内容1．从键盘随机输入一组整型元素序列，建立顺序表。
（注意：不可将元素个数和元素值写死在程序中）2．实现该顺序表的遍历（也即依次打印出每个数据元素的值）。
3．在该顺序表中顺序查找某一元素,如果查找成功返回1,否则返回0。
4．实现把该表中某个数据元素删除。
5．实现在该表中插入某个数据元素。
6．实现两个线性表的归并（仿照课本上P26 算法2.7）。
7. 编写一个主函数,调试上述6个算法。
五、实现提示1.存储定义#include <iostream.h>#include <stdlib.h>#define MAXSIZE 100 //表中元素的最大个数typedef int ElemType；//元素类型typedef struct list{ElemType *elem;//静态线性表int length; //表的实际长度int listsize; //表的存储容量}SqList;//顺序表的类型名2.建立顺序表时可利用随机函数自动产生数据。
3.为每个算法功能建立相应的函数分别调试，最后在主函数中调用它们。
六、注意问题插入、删除元素时对于元素合法位置的判断。
七、测试过程1.先从键盘输入元素个数，假设为6。
2.从键盘依次输入6个元素的值（注意：最好给出输入每个元素的提示，否则除了你自己知道之外，别人只见光标在闪却不知道要干什么），假设是：10,3,8,39,48，2。
3．遍历该顺序表。
4.输入待查元素的值例如39（而不是待查元素的位置）进行查找，因为它在表中所以返回1。
假如要查找15,因为它不存在，所以返回0。
5.输入待删元素的位置将其从表中删掉。
此处需要注意判断删位置是否合法，若表中有n个元素，则合法的删除位置是[1,n]。
例如，该示例中的合法删除位置是[1,6],输入其它位置均应报错。
提示：删除完毕后再调用遍历函数打印一下结果，看删除的是否正确。
6.输入待插入元素值和待插入的位置，进行插入操作。
注意：要判断待插入位置的合法性，应是[1,n+1]。
此示例中合法插入位置是[1,7],输入其它位置均应报错。
同理，插入完毕后也要调用遍历函数，看看插入的结果是否正确。
7.要实现两个表的归并，需要先建立两个顺序表LA和LB，依照算法2.7归并后将结果放入LC表中，故而归并操作结束后也要对LC表进行遍历，以验证结果的正确。
实验二链式存储结构----单链表的有关操作一、实验学时 8学时二、背景知识：单链表的插入、删除及应用。
三、目的要求1．掌握单向链表的存储特点及其实现。
2．掌握单向链表的插入、删除算法及其应用算法的程序实现。
四、实验内容1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
2．遍历单向链表。
3．把单向链表中元素原地逆置（即不允许申请新的结点空间）。
4．在单向链表中删除所有的偶数位置的元素结点。
（注：不是删除数据域的值为偶数的结点）五、实验说明1．类型定义#include <stdlib.h>typedef int ElemType；//元素类型typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;2．为了算法实现简单，最好采用带头结点的单向链表。
六、注意问题1．重点理解链式存储的特点及指针的含义。
2．注意比较顺序存储与链式存储的各自特点。
3．注意比较带头结点、无头结点链表实现插入、删除算法时的区别。
如果时间允许，请实现在不带头结点的单链表中的上述操作。
4．单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。
七、测试过程1.从键盘输入若干个元素以构造一个带头结点的单链表，例如：23,18,3,94，39。
提示：构造单链表可以用头插法，也可用尾插法，但是头插之后的结果正好是逆序的，而尾插是正序。
2.对该单链表进行遍历，打印出每个数据元素结点的数据域的值。
注意：头结点的数据域可以不赋值，它不被打印，因为它只是为了编程统一引入的，并没有用它来装实际的数据。
3.对单链表进行原地逆置。
注意：原地逆置是指不增加额外的存储空间，故而应该只修改该链表的指针值，而不开辟新的单元就完成逆置。
提示：头插法产生的结果正好是逆序的，所以可将原链表中的数据元素结点依次摘下，用头插法插入到头结点后面，就实现了原地逆置。
4.删除链表中的偶数位置元素，即删除链表中的2号、4号、6号、8号……元素。
提示：删除i号结点，需要将i-1号结点的指针域指向i+1号结点。
所以，要完成删除偶数位置结点，一方面要记录每个结点的位序，另一方面要记录它的前一结点位置以方便删除。
5.注意测试边界数据，例如链表长度为0。
实验三栈和队列的应用一、实验学时 4学时二、背景知识：入栈、出栈，入队、出队。
三、目的要求1．掌握栈、队列的思想及其存储实现。
2．掌握栈、队列的常见算法的程序实现。
四、实验内容1．采用顺序存储实现栈的初始化、入栈、出栈、判栈空操作。
2．采用顺序存储实现循环队列的初始化、入队、出队操作。
3．综合训练:1) 利用栈实现求一个十进制数的二进制表示算法。
2) 利用栈实现表达式中括号匹配算法。
五、基本要求1.实现算法3中的某一个即可。
2.类型定义顺序栈示例#define MAX 100 //栈的最大值typedef struct{ElemType *base；int top；}SqStack；顺序队列示例#define MAX 100 //队列的最大长度typedef struct{ElemType *base；int front，rear；}SqQueue；六、注意问题重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。
七、测试过程1.先做好栈的构造、入栈、出栈、判栈空函数，以及队列的构造、入队、出队函数，并进行相应检测。
2.十进制转二进制问题参照课本P48 算法3.1来完成。
要求输入一个任意的十进制数，得到其对应的二进制数。
3.括号匹配问题也采用栈来完成，实现思路参考课本P49。
要求从键盘读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”的信息。
例如，读入（[]（）），结果“匹配”。
读入[（]），结果“此串括号匹配不合法”。
实验四二叉树的常见操作一、实验学时 8学时二、背景知识：二叉树的存储、建立、遍历及其应用。
三、目的要求1．掌握二叉树的存储实现。
2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
四、实验内容1．输入字符序列，建立二叉链表。
2．中序遍历二叉树:递归算法。
3．求二叉树的高度。
4．求二叉树的叶子个数。
5．借助队列实现二叉树的层次遍历。
6．在主函数中设计一个简单的菜单，分别调试上述算法。
五、实验说明１．类型定义 //二叉链表存储typedef char ElemType;//元素类型typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;２．元素类型可以根据实际情况选取。
六、注意问题1．注意理解递归算法的执行步骤。
2．注意字符类型数据在输入时的处理。
七、测试过程1.从键盘读入某二叉树的前序序列，以”*”或”#”或其它特殊字符代表空格，构造二叉树。
注意测试边界情况，例如空树也是二叉树。
2.在一次执行过程中，多次反复调用求树高和求叶结点数的函数，看看每次的结果是否都正确。
此处考查全局变量的应用。
实验五图的建立与遍历一、实验学时 6学时二、背景知识：图的建立、图的深度优先遍历和广度优先遍历三、目的要求1.掌握图的邻接矩阵和邻接表的两种存储结构。
2.区分有向图、无向图、有向网、无向网在存储上的不同之处。
3.理解图的深度优先遍历需要借助栈，图的广度优先遍历需要借助队列。
四、实验内容1.建立有向图、无向图、有向网、无向网的邻接矩阵存储。
2.建立有向图、无向图、有向网、无向网的邻接表存储。
3.在邻接矩阵存储结构上进行图的深度和广度优先遍历。
4.在邻接表存储结构上进行图的深度和广度优先遍历。
五、实验说明1.对于四种图的类型，选取一个做实验内容1和2中的一个。
2.依据选取的存储结构，选做实验内容3和4中的一个。
六、注意问题1.注意图的顶点集是非空有限集，边集是有限集。
2.图的存储结构和起始顶点一旦确定，它的遍历序列就是唯一的了。
3.图的遍历可从任意顶点出发，为方便起见，我们取第一个顶点作为出发点。
七、测试过程1.从键盘敲入图的顶点数和边数，判断这两个值的合法性。
2.依次读入n个顶点，构造顶点集。
3.依次读入e条边，将其添入到邻接矩阵或邻接表中。
4.参照课本P169 算法7.4和7.5完成图的深度优先遍历。
5.参照课本P170 算法7.6完成图的广度优先遍历。
实验六折半查找验证实验一、实验学时：2学时二、背景知识：折半查找算法三、目的要求1.掌握折半查找算法的基本思想；2.掌握折半查找算法的实现方法；3.掌握折半查找算法的时间性能。
4.自己确实掌握一种排序算法，理解时间性能好的那几种算法。
四、实验内容1.对给定的数组（假设长度为n）排序。
排序算法任选，但要求对于简单的排序算法，比如简单插入排序、简单选择排序、冒泡排序，要脱离课本自己单独能写出来。
对于复杂的排序算法，比如堆排序、快速排序、归并排序，要求理解算法的思想，脱离课本也能写出大致框架。
2.查找数组中与给定值k相等的元素。
五、实验说明类型定义：typedef int ElemType;typedef struct{ElemType *elem; //数组元素存储空间地址 Int length; //表长度}SSTable //静态查找表的顺序存储结构六、注意问题1.此处数据元素是int类型，所以不用求其关键字。
2.需要预先实现EQ(int,int)函数。
七、测试过程1.从键盘敲入元素序列，而不是在程序中写死。
2.排序算法任选。
3.基于排序后生成的有序表进行折半查找。