数据结构实验指导Word文档下载推荐.docx

数据结构实验指导Word文档下载推荐.docx

《数据结构实验指导Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构实验指导Word文档下载推荐.docx（59页珍藏版）》请在冰点文库上搜索。

其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。

3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。

五、实验报告的书写要求

1、明确实验的目的及要求;

2、记录实验的输入数据和输出结果;

3、说明实验中出现的问题和解决过程;

4、写出实验的体会和实验过程中没能解决的问题;

六、成绩考评办法

1．期末考试占70分，闭卷。

2．平时考评占30分。

其中实验环节占20分（实验准备、上机、报告、考试等）；

平时占10分（出勤，作业，测验等）

七、参考书目

《数据结构》（Ｃ语言版）严蔚敏等清华大学出版社

《数据结构题集》（C语言版）严蔚敏等清华大学出版社

《DATASTRUCTUREWITHC++》WilliamFord,WilliamTopp

清华大学出版社（影印版）

实验一线性表的顺序存储结构

实验学时2学时

背景知识:

顺序表的插入、删除及应用。

目的要求：

1．掌握顺序存储结构的特点。

2．掌握顺序存储结构的常见算法。

实验内容

1．输入一组整型元素序列，建立顺序表。

2．实现该顺序表的遍历。

3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。

4．判断该顺序表中元素是否对称,对称返回1,否则返回0。

5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。

6．输入整型元素序列利用有序表插入算法建立一个有序表。

7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。

8．编写一个主函数,调试上述算法。

*9．综合训练：

利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）

实验说明

1.算法1至算法7可以以头文件的方式存储,主函数实现该头文件的包含即可调用

2.存储定义

#defineMAXSIZE100//表中元素的最大个数

typedefintElemType；

//元素类型

typedefstructlist{

ElemTypeelem[MAXSIZE];

//静态线性表

intlength;

//表的实际长度

}SqList;

//顺序表的类型名

3.建立顺序表时可利用随机函数自动产生数据。

注意问题

1．插入、删除时元素的移动原因、方向及先后顺序。

2．解不同的函数形参与实参的传递关系。

实验二链式存储结构

（一）

--单向链表的有关操作

实验学时２学时

背景知识：

单向链表的插入、删除及应用。

目的要求

1．掌握单向链表的存储特点及其实现。

2．掌握单向链表的插入、删除算法及其应用算法的程序实现。

1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

2．遍历单向链表。

3．把单向链表中元素逆置（不允许申请新的结点空间）。

4．在单向链表中删除所有的偶数元素结点。

5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。

7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。

8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

*9．采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。

10．在主函数中设计一个简单的菜单，分别调试上述算法。

*11．综合训练：

利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）

1．类型定义

#include<

stdio.h>

typedefstructLNode

{ElemTypedata;

structLNode*next;

}LNode,*LinkList;

2．为了算法实现简单，最好采用带头结点的单向链表。

1．重点理解链式存储的特点及指针的含义。

2．注意比较顺序存储与链式存储的各自特点。

3．注意比较带头结点、无头结点链表实现插入、删除算法时的区别。

__4．单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。

实验三链式存储结构

（二）

----双向链表的有关操作

实验学时２学时

双向链表的插入、删除及应用。

１．掌握双向链表的存储特点及其实现。

２．掌握双向链表的插入、删除算法及其应用算法的程序实现。

１．利用尾插法建立一个双向链表。

２．遍历双向链表。

３．实现双向链表中删除一个指定元素。

４．在非递减有序双向链表中实现插入元素e仍有序算法。

５．判断双向链表中元素是否对称若对称返回1否则返回0。

６．设元素为正整型,实现算法把所有奇数排列在偶数之前。

７．在主函数中设计一个简单的菜单调试上述算法。

双向链表的类型定义

typedefstructDuLNode

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

注意问题

注意比较单向、双向链表的特点。

_

实验四栈、队列的操作

入栈、出栈，入队、出队。

1．掌握栈、队列的思想及其存储实现。

2．掌握栈、队列的常见算法的程序实现。

1．采用链式存储实现栈的初始化、入栈、出栈操作。

2．采用顺序存储实现栈的初始化、入栈、出栈操作。

3．采用链式存储实现队列的初始化、入队、出队操作。

4．采用顺序存储实现循环队列的初始化、入队、出队操作。

5．在主函数中设计一个简单的菜单，分别测试上述算法。

*6．综合训练:

1）利用栈实现表达式求值算法。

2）利用栈实现迷宫求解。

1．基本要求：

实现算法1、3或算法2、4即可。

2．类型定义

顺序栈示例

#defineMAX100//栈的最大值

typedef　struct

{ElemType*base；

inttop；

}SqStack；

顺序队列示例

#defineMAX100//队列的最大长度

intfront，rear；

}SqQueue；

3．算法6的每个子功能尽可能写成函数形式。

1．重点理解栈、队列的算法思想，能够根据实际情况选择合适的存储结构。

2．注意算法6的各个函数之间值的传递情况。

3．栈、队列的算法是后续实验的基础（广义表、树、图、查找、排序等）。

实验五二叉树的常见操作

实验学时6学时

二叉树的存储、建立、遍历及其应用。

1．掌握二叉树的存储实现。

2．掌握二叉树的遍历思想。

3．掌握二叉树的常见算法的程序实现。

1．输入字符序列，建立二叉链表。

2．中序遍历二叉树:

递归算法。

3．中序遍历二叉树:

非递归算法。

（最好也能实现先序，后序非递归算法）

4．求二叉树的高度。

5．求二叉树的叶子个数。

*6．将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。

*7．建立中序线索二叉树，并实现中序遍历。

8．借助队列实现二叉树的层次遍历。

9．在主函数中设计一个简单的菜单，分别调试上述算法。

*10．综合训练：

为N个权值设计哈夫曼编码。

１．类型定义//二叉链表存储

#defineElemTypechar//元素类型

typedefstructBiTNode

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

２．元素类型可以根据实际情况选取。

1．注意理解递归算法的执行步骤。

2．注意字符类型数据在输入时的处理。

3．重点理解如何利用栈结构实现非递归算法。

实验六图的有关操作

图的存储、遍历、及其应用。

１．掌握图的存储思想及其存储实现。

２．掌握图的深度、广度优先遍历算法思想及其程序实现。

３．掌握图的常见应用算法的思想及其程序实现。

１．键盘输入数据，建立一个有向图的邻接表。

２．输出该邻接表。

*３．建立一个无向图的十字链表。

４．在有向图的邻接表的基础上计算各顶点的度，并输出。

５．以有向图的邻接表为基础实现输出它的拓扑排序序列。

*６．采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。

７．采用邻接表存储实现无向图的深度优先非递归遍历。

８．采用邻接表存储实现无向图的广度优先遍历。

*９．采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。

*10．判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。

11．在主函数中设计一个简单的菜单，分别调试上述算法。

*12．综合训练：

为计算机专业设计教学计划：

4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。

实验说明１．类型定义（邻接表存储）#defineMAX_VERTEX_NUM8//顶点最大个数typedefstructArcNode

{intadjvex;

structArcNode*nextarc;

intweight;

//边的权

}ArcNode;

//表结点#defineVertexTypeint//顶点元素类型

typedefstructVNode

{intdegree,indegree;

//顶点的度，入度VertexTypedata;

ArcNode*firstarc;

}VNode/*头结点*/,AdjList[MAX_VERTEX_NUM];

typedefstruct{AdjListvertices;

intvexnum,arcnum;

//顶点的实际数，边的实际数}ALGraph;

２．上述类型定义可以根据实际情况适当调整。

３．算法７、８分别利用栈、队列实现非递归算法。

１．注意理解各算法实现时所采用的存储结构。

２．注意区别正、逆邻接。

实验七查找的有关操作

顺序查找、树表查找、散列查找。

1．掌握折半查找算法的思想及程序实现。

2．掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。

3．掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。

1．利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。

2．随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键字元素。

*3．建立ＡＶＬ树并实现删除某一指定关键字元素。

4．已知散列函数为H（key）=key%p（p为自定的常数），冲突处理方法分别为线性探测法、外拉链法实现散列表的建立（利用插入算法实现）。

1．存储定义（散列表的外拉链法）

#definen9

typedefstructnode

{intkey;

structnode*next;

}NODE;

NODE*HashTable[9];

算法1、2、3可以参考顺序表，二叉链表的存储实现。

2．各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。

3．算法1存储在文件seqlist.h中,算法2、3存储在文件bintree.h中,算法4存储在文件hash.h中

注意问题1．注意理解折半查找的适用条件（链表能否实现折半查找？

）。

2．注意建立二叉排序树、散列表时相同元素的处理。

3．注意理解静态查找、动态查找概念。

4．比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。

实验八排序

各种排序方法

１．掌握常见的排序算法的思想及其适用条件。

２．掌握常见的排序算法的程序实现。

输入一组关键字序列分别实现下列排序:

1.实现简单选择排序、直接插入排序和冒泡排序。

2.实现希尔排序算法。

3.实现快速排序算法。

4.实现堆排序算法。

*5.快速排序的非递归算法。

*6.实现折半插入排序。

*7.采用链式存储实现简单选择排序、直接插入排序和冒泡排序。

8.在主函数中设计一个简单的菜单，分别测试上述算法。

*9．综合训练：

采用几组不同数据测试各个排序算法的性能（比较次数和移动次数）。

#defineMAXSIZE100/*参加排序元素的最大个数*/

typedefstructlist

}RedType;

typedefstruct{

RedTyper[MAXSIZE+1];

/*参加排序元素的实际个数*/

2．算法５可以借助栈实现。

1．在RedType中增加一个数据项验证各种排序算法的稳定性。

2．注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。

数据结构练习题

说明：

除题中另有说明外，本书均采用下面的存储结构及操作

二叉链表的C语言存储描述如下单向链表的存储

typedefstructBiTNodetypedefstructLNode

{chardata；

//元素信息{ElemTypedata；

structBiTNode*lchild，rchild；

}BiTNode，*BiTree；

}LNode，*LinkList；

邻接表的C语言存储描述如下基本操作如下

typedefstructArcInitStack（S）

{intadj；

//顶点序号StackEmpty（S）

structArc*next；

Push（S，e）

}ArcNode，*ARC；

//表结点Pop（S，e）

typedefstructVnode{//头结点InitQueue（Q）

chardata；

//元素信息QueueEmpty（Q）

ARC*first；

Enqueue（Q，x）

}Graph[N]；

//N为顶点的实际个数DelQueue（Q，x）

一、判断正误

1、线性表采用链式存储，则链表中结点总数一定等于元素总数。

2、栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同。

3、无论采用何种存储结构，队列的入队、出队次序一定相同。

4、由三个不同关键字构造的二叉排序树的基本形态共有五种。

5、若非空二叉树的先序、中序遍历序列相同，则必为仅有一个根的二叉树。

6、二叉链表存储的二叉树中结点总数为n，则空指针域总数必为n+1。

7、n（>

0）个权值作为叶子构造的哈夫曼树中结点总数为2n-1。

8、森林的后序遍历与它对应的二叉树的中序遍历相同。

9、折半查找的平均查找效率高于顺序查找，因此，查找某一元素时，折半查找所需与关键字的比较次数一定少于顺序查找。

10、二叉排序树的中序遍历序列按关键字递增有序。

11、有向图的邻接表的第i个链表中表结点总数为该顶点的度。

12、顺序表，链表，二叉链表，邻接表，散列表均为存储结构。

13、选取散列函数时，冲突越少越好。

14、冒泡，直接插入，归并，基数排序均为稳定排序。

15、快速排序最坏的时间复杂度为O（N*logN）。

16、不稳定排序后，相同关键字元素的相对位置一定发生改变。

17、直接插入排序适用于元素个数较少或初始序列基本有序情况。

18、对称矩阵压缩存储后不具备随机存取的特点。

19、在考虑存储结构的前提下，有向图的拓扑排序序列一定唯一。

20、折半查找要求元素必须按关键字有序，且只能采用顺序存储结构。

二、填空题

1、数据的基本单位是_____，数据结构常见的逻辑结构有_____，存储结构有____。

2、数据结构的逻辑结构可视为一个二元组Data_Structure=（D，S），其中D是_____，S是_____。

3、数据结构的抽象数据类型ADT是指一个数学模型及定义在该模型上的一组操作。

它可用三元组（D，S，P）表示，其中D是数据对象，S是_____，P是_____

4、设计一个好的算法应达到的目标是正确性、_____、_____和高效率低存储量。

算法时间效率、空间效率的度量分别称为_____、_____。

5、顺序表、链表分别通过_____、_____体现元素的前驱、后继的逻辑关系。

6、在表长为n的顺序表中插入、删除元素时，在等概率条件下平均移动元素的次数分别为_____、_____，具体移动的元素个数与_____有关。

7、已知L为头指针的带头结点的单循环链表（指针域为next），a．若R为尾指针，则满足的条件为______，b．若该表为空表，则满足的条件是______。

8、已知五个元素ABCDE的进栈次序为ABCDE，a．若C为第一个出栈元素，则下一个出栈的元素可能是_____；

b．能否得到出栈序列CDBEA______、CEDAB______？

9、若三个元素ABC的进栈次序为ABC，则借助栈一共可以得到______中出栈序列？

10、已知顺序存储的循环队列中，f，r分别为队头、队尾指针，MAX为队列中存储单元的最大个数。

若当队列中仅有一个空闲单元时视为队满，则队空、队满条件分别为_____、_____；

一般情况下，队列中元素个数可表示为_____。

11、广义表A=（（a，（b），c），（d），（e，f，g））的表长为_____，深度为_____，利用取表头、表尾运算表示原子e的表达式为_____。

12、广义表中元素既可以是单原子，也可以是_____，广义表的两个基本操作是_____和_____。

13、10个结点二叉树至多有_____个叶子，最低高度为_____。

14、83个结点的完全二叉树高度为_____，其中叶子个数为_____，一度结点个数为_____。

15、n（n>

0）个结点的完全二叉树叶子个数为_____，一度结点个数为_____。

16、高度为5的BST树结点总数至多，至少为_____，_____。

17、n个叶子的哈夫曼树最高高度为_____，结点总数为_____。

18、从本质上而言，森林的孩子兄弟链表与它转换所对应的二叉树的_____存储结构一致。

19、n个顶点的无向、有向完全图的边数分别是_____、_____，n个顶点的强连通图至少有_____条边。

20、无向网的最小生成树的构造算法是_____和_____；

n个顶点的无向网构造的最小生成树中边的条数为_____。

21、构造散列表要解决的两个问题是_____；

若将关键字序列的散列地址定位在100至110之间，则散列函数可表示为H（key）=_____。

22、从理论上讲，散列查找的算法效率为_____，但实际应用时，常常因为_____使查找速度有所降低。

23、若关键字序列为正序，则直接插入、冒泡、简单选择、归并、快速、堆排序中排序效率最高的是_____和_____，此时时间复杂度为__________。

24、希尔排序每趟的排序方法是_____，平均时间复杂度为_________；

快速排序的平均时间复杂度为_______，最坏时间复杂度为________。

25、排序时所需与关键字的比较次数仅与元素个数有关而与关键字的初始序列无关的排序方法是_____，若关键字个数为n个，则第一趟的比较次数为_____。

26、写出三种不稳定的排序方法的名称_____、_____和_____。

27、n个元素进行起泡排序时，最好情况下只需进行_____次比较和____次交换，最坏情况需进行_____次比较和_____次交换。

三、综合题

1、已知线性链表中结点的数据域、指针域依次为data、next，写出在表中删除*p结点的语句（设该结点存在后继）及*p结点前插入*s结点语句。

2、简述顺序表、链表的各自特点。

3、简述链式存储中头结点、头指针；

结点、元素的区别。

4、n阶矩阵Aij（1≤i，j≤n）或Aij（0≤i，j≤n-1）的上三角（不含对角线）为常数C，下三角无规律，设计压缩存储方案。

5、画出广义表A=（（a，（b），c），（d），（e，f））的链式存储结构。

6、画出由三个结点构造的二叉树的基本形态。

7、已知一棵度为5的树中1度，2度，．．．，5度结点的个数依次为1，2，．．．，5，则叶子个数为多少？