《数据结构实验指导册》由会员分享，可在线阅读，更多相关《数据结构实验指导册（23页珍藏版）》请在金锄头文库上搜索。
1、数据结构上机实验执导手册目 录实验一 顺序表的操作实验二 单链表的操作实验三 栈的链式存储结构的表示和实现实验四 二叉树遍历算法的设计实验五 采用邻接表实现图的 DFS 和 BFS附录 部分程序源代码实验一 顺序表的操作一实验目的1.了解顺序表的逻辑结构特性。2.掌握线性表的顺序存储结构的定义及其 C 或 C+语言实现。3.掌握线性表顺序存储结构顺序表的各种基本操作。二实验仪器设备PC 机一台三实验要求1.认真阅读和掌握本实验的相关知识。2.对给出的程序认真阅读，把相关缺失程序补充完整。3.上机运行补充后的程序。4.保存程序的运行结果，结合程序分析顺序结构的特点。5.填写实验报告四实验内容及实
2、验分析1.实验内容在 VC+6.0 的运行环境下，编写 C 或 C+语言程序，利用顺序存储的方式来实现下列功能：(1)根据键盘输入数据建立一个顺序表，并且输出该顺序表。(2)根据屏幕菜单来选择数据的插入、删除以及查找操作。(3)完成插入或删除数据操作后，把操作后的线性表进行输出。(4)在完成插入、删除和查找操作后，选择菜单上的 0，退出该程序的运行，结束实验内容。2.实验分析在顺序表的第 i 个位置上要求插入一个数据元素时候，先将顺序表的第 i个位置元素后的所有数据元素按顺序后移一个位置，在插入的地方空出一个位置，然后把要插入的新数据元素插入到该位置，同时将表长加一。 在顺序表中删除表中第 i
3、 个位置的数据元素的时候，先将该位置的数据元素删除，然后将第 i 个位置后的其他剩余元素按顺序依次向前移动一个位置，同时将表长减一。 顺序表中查找一个数据元素的值，需要遍历整个顺序表，如要找道该值，则返回该值在顺序表中的位置，否则继续查找。如果遍历整个顺序表都没有找到该值，则要求函数返回-1五 实验报告1总结顺序表的优缺点及顺序表在现实中可以解决的问题。2讨论如果按照由表尾到表头的顺序输入数据，则如何建立顺序表。 3讨论自己在设计过程中遇到的问题、解决的过程以及收获体会。实验二 单链表的操作一. 实验目的1.了解单链表的逻辑结构特性。2.掌握单链表的链式存储结构的定义及其 C 或 C+语言实现
4、。3.掌握单链表链式存储结构。4.掌握单链表的各种基本操作。二. 实验仪器设备PC 机一台三. 实验要求1.认真阅读和掌握本实验的相关知识。2.对给出的程序认真阅读，把相关缺失程序补充完整。3.上机运行补充后的程序。4.保存程序的运行结果，结合程序分析链式结构的特点。5.填写实验报告四.实验内容及实验分析1.实验内容编写 C 语言程序，利用链式存储的方式来实现下列功能：(1)根据键盘输入数据建立一个单链表，并且输出该单链表。(2)根据屏幕菜单来选择数据的插入、删除以及查找操作。(3)完成插入或删除数据操作后，把操作后的线性表进行输出。(4)在完成插入、删除和查找操作后，选择菜单上的 0，退出该
5、程序的运行，结束实验内容。2.实验分析在单链表的第 i 个位置上要求插入一个数据元素时候，先生成一个存储单元 S 来存放插入数据元素 X 的值，其次修改第 i 个位置结点 P 的 next 域值，让其存入是结点 S 所在存储单元地址的值，再次修改结点 S 的 next 域的值，让 S 的next 域的值为第 i+1 结点的地址值。在单链表中删除表中第 i 个位置的数据元素的时候，先修改第 i-1 个数据元素的 next 域的地址值，使其值为第 i+1 个数据元素存储单元的地址值，最后释放第 i 个存储单元，使用函数 free()。在 单链表中查找一个数据元素的值，需要遍历整个整个单链表，如要找
6、道该值，则返回该值，否则继续查找。如果遍历整个顺序表都没有找到该值，则要求函数返回-1五 实验报告1总结链表的优缺点及链表在现实中可以解决的问题。2讨论自己在设计过程中遇到的问题、解决的过程以及收获体会。实验三 栈的链式存储结构的表示和实现一 实验目的1.了解栈的逻辑结构特性。2.掌握栈的链式存储结构的定义。3.掌握栈的链式结构的表示和实现。二 实验仪器设备PC 机一台三 实验要求1.认真阅读和掌握本实验的相关知识。2.编写程序实现栈的链式存储方式。3.编写程序实现对栈空的判断以及栈的入栈和出栈操作、取栈顶元素。4.保存程序的运行结果，结合程序分析链式结构的特点。5.填写实验报告四 实验内容及
7、实验分析1.实验内容编写 C 或 C+语言程序，利用链式存储的方式来实现下列功能：(1)初始化链栈。(2)将链栈置空。(3)完成入栈和出栈操作，完成取栈顶元素操作。(4)选择菜单上的 0，退出该程序的运行，结束实验内容。2.实验分析(1)初始化栈操作，将栈的栈顶指针置为空值，即设栈 S 和栈顶指针top，Stop=null。(2)如果所建栈里有数据元素，要将其置空，同样也是将栈顶指针的值置为空值。(3)入栈操作，向栈里插入数据元素。首先要为插入数据元素分配结点，将插入数据元素的值赋值给插入结点的数据域，其次修改栈顶指针的指向关系，即修改插入结点和栈顶指针的地址，最后修改栈顶指针。(4)出栈操作
8、，从栈里删除数据元素。首先要判断栈是否为空栈，如是空栈则操作失败。否则，进行出栈操作，修改删除结点和栈顶指针，最后释放删除结点。(5)取栈顶元素。五 实验报告1总结栈的优缺点及栈在现实中可以解决的问题。2讨论自己在设计过程中遇到的问题、解决的过程以及收获体会。实验四 二叉树遍历算法的设计一 实验目的1.掌握二叉树的结构特征，以及各种存储结构的特点。2.掌握二叉树在实践中的应用范围。3.掌握用指针类型来描述、访问和遍历二叉树的操作算法。二 实验仪器设备PC 机一台三 实验要求1.认真阅读和掌握本实验的相关知识。2.编写程序实现二叉树的链式存储方式。3.编写程序实现对二叉树的先序遍历、中序遍历和后
9、序遍历的算法实现。4.保存程序的运行结果，结合程序分析二叉树的结构特点。5.填写实验报告四 实验内容及实验分析1.实验内容编写 C 或 C+语言程序，利用链式存储的方式来实现下列功能：(1)采用二叉树性质 5 来建立二叉树。(2)完成二叉树的三种遍历算法。(3)选择菜单上的 0，退出该程序的运行，结束实验内容。2.实验分析(1)定义二叉树结点值的数据类型，将其定义为字符型数据，定义二叉树中结点的结构类型。(2)利用性质 5 建立二叉树，设置序号为 1 的结点为二叉树的根结点，序号为偶数的结点为该二叉树的左孩子，序号为奇数的结点为该二叉树的右孩子。(3)采用递归方式来遍历二叉树，也就是实现二叉树
10、的遍历是利用递归的方法来实现，即先序递归遍历、中序递归遍历、后序递归遍历。先序递归遍历算法描述： 访问二叉树的根结点。 先序遍历左子树。 先序遍历右子树。中序递归遍历算法描述： 中序遍历左子树。 访问根结点。 中序遍历右子树。后序递归遍历算法描述： 后序遍历左子树。 后序遍历右子树。 访问根结点。五 实验报告1总结二叉树的优缺点及二叉树在现实中可以解决的问题。2讨论自己在设计过程中遇到的问题、解决的过程以及收获体会。实验五 采用邻接表实现图的 DFS 和 BFS一 实验目的1.掌握图的基本存储方法。2.熟练掌握图的两种搜索路径的遍历方法。3.掌握图的有关应用。二 实验仪器设备PC 机一台三 实
11、验要求1.认真阅读和掌握本实验的相关知识。2.编写程序实现图的邻接表存储方式。3.编写程序实现对图的 DFS（递归）和 BFS（非递归）的算法实现。4.保存程序的运行结果，结合程序分析这两种遍历的结构特点。5.填写实验报告四 实验内容及实验分析1.实验内容编写 C 或 C+语言程序，实现图的下列功能：(1)利用邻接表的结构特性实现对图中各个顶点的存储。(2)利用 DFS 算法对图中各个顶点进行遍历并且输出遍历结果。(3)利用 BFS 算法对图中各个顶点进行遍历并且输出遍历结果。(4)选择菜单上的 0，退出该程序的运行，结束实验内容。2.实验分析(1)建立无向图的邻接表，并且输出该无向图的邻接表
12、。(2)输入 DFS 的出发点，按照 DFS 遍历算法遍历图中顶点。(3)输入 BFS 的出发点，由于 BFS 采用的是非递归形式，所以要通过建立队列来实现 BFS 的遍历过程。因此，在编写该算法的过程中，就要建立队列，即队列的初始化操作、判断队是否为空、入队和出队操作。五 实验报告1总结 BFS 和 DFS 的优缺点。2总结图的邻接表存储特点。2讨论自己在设计过程中遇到的问题、解决的过程以及收获体会。附录顺序表程序部分代码：#include#include#define MAXSIZE 20 数组最大界限typedef int ElemType; 数据元素类型typedef structEl
13、emType aMAXSIZE; 一维数组子域 int length; 表长度域SqList; 顺序存储的结构体类型SqList a,b,c;void creat_list(SqList *L);void out_list(SqList L);void insert_sq(SqList *L,int i,ElemType e);ElemType delete_sq(SqList *L,int i);int locat_sq(SqList L,ElemType e);主函数void main()int i,k,loc;ElemType e,x;char ch;doprintf(nnn);prin
14、tf(n 1.建立线性表);printf(n 2.插入数据元素);printf(n 3.删除数据元素);printf(n 4.查找数据元素);printf(n 0.结束程序运行);printf(n=);printf(n 请输入你的选择(1,2,3,4,0);scanf(%d,switch(k)case 1:creat_list(out_list(a);break;case 2:printf(n 请输入插入位置：);scanf(%d,printf(n 请输入要插入的数据元素值：);scanf(%d,insert_sq(out_list(a);break;case 3: printf(n 请输入删
15、除位置：);scanf(%d,x=delete_sq(out_list(a);if(x!=-1)printf(n 删除数据元素为：%dn,x);elseprintf(要删除的数据元素不存在！);break;case 4:printf(n 请输入要查找的数据元素值：);scanf(%d,loc=locat_sq(a,e);if(loc=-1)printf(n 未找到指定数据元素！);elseprintf(n 已找到，数据元素位置是%d,loc);break;while(k!=0);printf(n 按回车键，返回.n);ch=getchar();建立线性表void creat_list(SqList *L)int i;printf(请输入线性表的长度：);scanf(%d,for(i=0;ilength;i+)printf(数据元素%d=,i);scanf(%d,输出线性表void out_list(SqLis
