数据结构实验安排.docx
《数据结构实验安排.docx》由会员分享，可在线阅读，更多相关《数据结构实验安排.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构实验安排
数据结构实验安排
实验一顺序表的插入和删除
1.实验目的：
了解顺序表的基本概念、结构的定义及在顺序表上的基本操作（插入、删除、查找以及线性表合并），通过用C语言实现以上操作，更好地了解书本上的内容。
2.实验预备知识：
⑴复习C语言中数组的用法。
⑵了解线性表和顺序表的概念，顺序表的定义方法；
✧线性表是n个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同。
✧顺序表是线性表的顺序存储表示，是用一组地址连续的存储单元依次存储线性表的数据元素。
✧在C语言中，顺序表是用数组或指针来实现的。
⑶掌握线性表在顺序存储结构上实现基本操作：
查找、插入、删除和合并的算法。
在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：
✧在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出错误提示）。
✧在实现插入的时候，首先要判断该顺序表是否为满，如为满则须重新分配空间（此时要注意：
若顺序表是用数组来实现的，它不能随机分配空间）；如不为满，则需判断要插入的位置是否合法（例如：
如果一个线性表的元素只有10个，而要在第0个元素前插入或在第11个元素后插入就为不合法）。
其次要注意是前插还是后插，两者是有区别的；最后还要注意插入时各个数据元素移动的次序是从后面依次开始移动。
✧在实现删除的时候，首先要判断该顺序表是否为空，如为空则报错，如不为空，则需判断要删除的位置是否合法（例如：
如果一个线性表的元素只有10个，而要删除第0个或第十一个元素就为不合法）。
其次还要注意删除时各个数据元素移动的次序是从前面依次开始移动。
3.实验内容：
1、顺序表的建立
2、顺序表的插入（输入插入位置i,插入元素）
3、顺序表的删除（输入删除元素位置i）
4、顺序表的打印
5、顺序表的合并算法（选做）
实验二单链表的插入和删除
1.实验目的：
了解单链表的基本概念、结构的定义及在单链表上的基本操作（插入、删除、查找以及线性表合并），通过在TurboC实现以上操作更好的了解书本上的内容并体会线性表的两种存储结构的区别。
2.实验预备知识：
⑴复习C语言中指针的用法，特别是结构体的指针的用法；
⑵了解单链表的概念，单链表的定义方法；
单链表是线性表的链式存储表示，是用一组任意的存储单元依次存储线性表的数据元素。
因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），而这部分就是用指针来完成的。
⑶掌握线性表在链式存储结构上实现基本操作：
查找、插入、删除的算法。
在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容：
✧在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出错误提示）。
✧在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，原因同实验一，其次要注意插入的时候语句的顺序不可颠倒，否则出错。
例如：
p
s
s所指向结点要插入在p所指向的结点之后，则：
正确形式：
s->next=p->next
p->next=s
错误形式：
p->next=s
s->next=p->next（因为此时p->next已经指向s了）
✧在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删除后要回收空间。
p
s
例如：
删除如上图所示s所指向的结点
p->next=p->next->next
frees
3.实验内容：
⑴单链表的插入算法
⑵单链表的删除算法
⑶双向链表的插入和删除算法（选做）
实验三栈的应用
1.实验目的：
了解栈的概念、栈的特性、在两种存储结构上如何实现栈的基本操作以及栈在程序设计中的应用。
通过在TurboC中实现顺序栈的插入和删除加深理解顺序栈的意义。
2.实验预备知识：
⑴掌握栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；
栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。
因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；
栈又称为后进先出（LastInFirstOut）的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。
⑵熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。
⑶在学习顺序栈的基本操作实现算法时，应注意：
在书上给出的结构定义是采用了一种动态管理方式（不够时，可以再分配），但在C语言中，用数组来存储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解。
3.实验内容：
⑴顺序栈的进栈、出栈算法
⑵顺序栈的应用（数制转换）
实验四队列的应用
1.实验目的：
了解队列的概念、队列的特性、在两种存储结构上如何实现队列的基本操作以及队列在程序设计中的应用。
通过在TurboC中实现队列的插入和删除加深理解链队列和循环队列的意义。
2.实验预备知识：
⑴掌握队列这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；
队列是操作受限的线性表，是只允许仅在表的一端进行插入，而在另一端进行删除操作的线性表。
在队列中，允许插入的一端称为队尾（rear），允许删除的一端称为对头（front）；
队列又称为先进先出（FirstInFirstOut）的线性表，简称FIFO结构。
因为它的修改是按先进先出的原则进行的。
⑵熟练掌握循环队列和链队列的基本操作实现算法，特别注意在循环队列中队满和队空的描述方法。
3.实验内容：
⑴链队列的进队和出队算法
⑵循环队列的进队和出队算法
实验五数组的应用
1.实验目的：
了解数组的类型定义和表示方法；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。
通过在TurboC语言的实验加强对数组的理解和对稀疏矩阵的压缩存储方法及运算的实现。
2.实验预备知识：
⑴了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算公式。
LOC（i,j）=LOC（0,0）+（b2*i+j）*L
⑵掌握对特殊矩阵进行压缩存储时的下标变换公式
对称矩阵：
i*（i-1）/2+j-1当i>=j
三角矩阵：
k=
j*（j-1）/2+i-1当i三对角矩阵：
sa[k]=2*i+j
⑶了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。
3.实验内容：
⑴三元组顺序表结构的定义
⑵矩阵的转置运算
实验六二叉树的遍历
1.实验目的：
通过该实验加深对树及二叉树的结构特性、各种存储结构的特点及区别。
2.实验预备知识：
⑴了解树的结构特点及概念、二叉树的概念及结构特点。
⑵了解树和二叉树的基本概念和术语。
⑶二叉树的三种遍历方法（先序、中序、后序遍历）
✧先序遍历：
若二叉树为空，则空操作，否则
1访问根结点；
2先序遍历左子树；
3先序遍历右子树。
✧中序遍历：
若二叉树为空，则空操作，否则
1中序遍历左子树；
2访问根结点；
3中序遍历右子树。
✧后序遍历：
若二叉树为空，则空操作，否则
1后序遍历左子树；
2后序遍历右子树；
3访问根结点。
⑷二叉树的各种存储结构及其适用范围，特别是链式存储结构。
3.实验内容：
⑴二叉树的链式存储结构定义
⑵二叉树的三种遍历算法
实验七二叉树的应用
1.实验目的：
通过该实验加深对线索二叉树的结构特性、各种存储结构的特点及区别。
2.实验预备知识：
⑴了解线索二叉树的概念及结构特点。
⑵了解线索二叉树的基本术语。
⑶线索二叉树的遍历方法（中序遍历）
⑷二叉树的各种存储结构及其适用范围，特别是链式存储结构。
3.实验内容：
⑴创建线索二叉树的链式存储结构
⑵线索二叉树的中序遍历算法
实验八图的应用
1.实验目的：
[1]掌握图的基本存储方法。
[2]掌握有关图的操作算法并用高级语言编程实现；
[3]熟练掌握图的两种搜索路径的遍历方法。
2.实验预备知识：
⑴图的定义和基本术语；
⑵图的四种存储结构（数组表示法、邻接表、十字链表和邻接多重表）；
⑶图的两种遍历策略（深度优先搜索和广度优先搜索），并应该注意图的遍历和树的遍历算法之间的区别；
⑷图的连通性、连通分量和最小生成树的概念和实现方法；
⑸拓扑排序和关键路径、两类求最短路径问题的解法。
3.实验内容：
以邻接矩阵和邻接表的方式存储连通图。
然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。
实验九查找应用
1.实验目的：
通过各种查找算法的编写加深对各种查找方法（包括静态查找表和动态查找表）的基本思想、查找过程以及查找的时间复杂度的理解。
2.实验预备知识：
⑴熟练静态查找表的概念和查找方法；
顺序表的查找方法为：
顺序查找；
有序表的查找方法为：
顺序查找、折半查找
⑵熟练掌握动态查找表的概念和查找方法；
掌握二叉排序树（二叉查找树）的查找方法；
理解平衡二叉树的维护平衡方法
3.实验内容：
⑴折半查找的算法
⑵二叉排序树的查找算法
实验十排序
1.实验目的：
通过各种排序算法的编写加深对各种排序方法（包括静态查找表和动态查找表）的基本思想、排序过程以及排序的时间复杂度的理解。
2.实验预备知识：
⑴熟练直接插入排序的基本思想和方法；
⑵熟练快速排序法的基本思想和方法；
3.实验内容：
⑴直接插入排序算法
⑵快速排序算法
实验十一综合实验
1.实验目的：
利用所学到的知识设计出合适的存储结构解决相关的实际问题。
2.实验内容：
⑴joseph环
任务：
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
设计一个程序来求出出列顺序。
要求：
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
测试数据：
m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
要求：
输入数据：
建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。
输出形式：
建立一个输出函数，将正确的输出序列
⑵赫夫曼树的建立
任务：
建立建立最优二叉树函数
要求：
可以建立函数输入二叉树，并输出其赫夫曼树
在上交资料中请写明：
存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
升级会员 