数据结构实验指导书

2020-03-03 12:41:42 来源：范文大全收藏下载本文

实验一

线性表、栈和队列的基本操作............................................................1 实验二

二叉树的基本操作................................................................................3 实验三

内部排序的基本操作............................................................................5 附录：《数据结构与算法》实验报告格式..........................................................6

1 实验一

线性表、栈和队列的基本操作

【实验目的】

1.掌握线性表（顺序表和链表）的顺序和链式存储结构的定义及C语言的实现。

2.掌握线性表（顺序表和链表）的建立、插入、删除、查找等基本操作。 3.深入了解栈和队列的基本特性。

4.熟练掌握栈和队列的基本操作在两种存储结构上的实现。 5.熟练掌握循环队列的基本操作。

【实验内容】

1.报数问题：编号为1，2，···，n的n个人围坐在一圆桌旁，每人持有一个正整数的编号。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，则退席的人的编号依次为6，1，7，5，3，2，4。

2.设计一个顺序栈的基本操作的程序，包括初始化顺序栈、判断栈空、求顺序栈中的元素个数、取顺序栈栈顶元素、入栈、出栈，并测试十进制转换成16进制的运算。

3.设计一个循环队列的基本操作的程序，包括实现下列6种基本运算：初始化、入队、出队、遍历、求队列的长度，并测试用队列实现杨辉三角的输出显示。

【实验安排】

由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。建议课时安排如下：

课外 2学时，课内2学时

【实验提示】

1.报数问题的存储结构可以采用以下两种方式：

(1)以顺序表为存储结构：可以用简单的数组

int p[n];

(2) 以循环链表为存储结构：用不带表头结点的循环单链表表示围成圆圈的n个人；建立此循环单链表；某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的修改变化。

typedef struct LNode{ int data;

- 1

实验二

二叉树的基本操作

【实验目的】

1.掌握二叉树的链式存储结构及实现方法。 2.掌握二叉树的遍历方法。

3.掌握二叉树中插入结点、删除结点的方法。

4.掌握二叉树的结点个数、叶子结点个数和树的深度的计算方法。 5.掌握建立哈夫曼树的方法，实现哈夫曼编码。

【实验内容】

1.要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求： (1) 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。 (2) 分别利用前序遍历、中序遍历、后序遍历所建二叉树。 (3) 统计以上二叉树中叶子结点的个数和结点总数。 2.熟练掌握哈夫曼树的构建，并实现哈夫曼编码。

【实验安排】

建议课时安排如下：

课外 4学时，课内2学时

【实验提示】

1.采用C语言的定义树的存储结构： //二叉树的链式存储表示 typedef char DataType; //应由用户定义DataType的实际类型 typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指针 } BinTNode;

//结点类型

typedef BinTNode *BinTree;

2.可以考虑采用递归的方法先创建根结点，然后分别创建左右子树。在创建二叉树的过程中，要注意结点数是根据输入的字符确定的。如：

void CreateBinTree(BinTree &T) {

- 34 实验三

内部排序的基本操作

【实验目的】

1.掌握排序的有关概念和特点。

2.熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。。

3.关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。

4.了解各种排序方法的优缺点和适用范围。

【实验内容】

1.从键盘输入上述8个整数，存放在数组quick[8]中，并输出值。 2.输出各种排序算法每一趟排序的结果，观察关键字次序的变化。

3.如果上述8个整数按照升序输入，即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。 4.如果上述8个整数按照降序输入，即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。 5.测试各排序算法的执行时间，比较执行效率。

6.随机产生3万个数，对其进行排序，观察其结果。

【实验安排】

建议课时安排如下：

课外 2学时，课内2学时【实验提示】

1.采用C语言的定义记录类型的存储结构： typedef int InfoType; #define n 10

typedef int KeyType; typedef struct {

//假设的文件长度，即待排序的记录数目 //假设的关键字类型 //记录类型

//关键字项

//其它数据项，类型InfoType依赖于具体应用而 KeyType key;

InfoType otherinfo; 定义

} RecType; typedef RecType SeqList[n+1]; 作哨兵

2.注意哨兵的作用。