数据结构与算法实习实验指导书

数据结构与算法课程实习

实验指导书

上海第二工业大学

计算机与信息学院软件工程系

目录

实验一 顺序表的基本操作........................................................................................................... 2 实验二 链表的基本操作............................................................................................................... 3 实验三 二叉树的基本操作........................................................................................................... 4 实验四 综合应用 .......................................................................................................................... 5 附录A 实验报告示例 ..................................................................................................................... 9 附录B 实验报告封面、评语得分表 ........................................................................................... 12 附录C 最后要提交的文档形式 ................................................................................................... 15

实验一 顺序表的基本操作

【实验目的】

1、 掌握顺序存储的概念，学会对顺序表的基本操作。

2、 加深对顺序存储数据结构的理解，逐步培养解决实际问题的能力。

【实验性质】 设计型实验

【实验内容】

1、实现顺序表显示； 2、实现顺序表插入；

3、实现顺序表查找（显示比较次数）； 4、实现顺序表删除（显示移动次数）；

5、实现顺序表排序（分别实现简单选择、快速，显示比较次数、移动次数）； 6、实现顺序表的折半查找（显示比较次数）；

7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置； 8、顺序表有序插入（显示比较次数、移动次数），

屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素； 屏幕显示比较次数和移动次数，应有溢出判断和报告； 9、要求以较高的效率实现删除顺序表中元素值在x到y(x和y自定)之间的所有元素； 10、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次； *11、编程实现顺序表的shell排序（步长为5，3，1）； *12、编程实现堆排序算法；

*13、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）。

【实验环境】 VC++ 6.0

【实验要求】

将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。

实验二 链表的基本操作

【实验目的】

1、 掌握链表的概念，学会对链表进行操作。

2、 加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。

【实验性质】 设计型实验

【实验内容】

1、实现单链表的创建； 2、实现单链表的显示；

3、实现单链表的查找（显示比较次数）； 4、实现单链表的插入；

5、实现单链表的删除（显示比较次数）；

6、对已创建的链表（数据不限）进行直接插入排序；

7、将链接存储线性表逆置，即最后一个结点变成第1个结点，原来倒数第2个结点变成第2个结点，如此等等；

8、生成有序的两个单链表A和B（链表的数据和个数自定），其首结点指针分别为a和b，要求将两个单链表合并为一个有序的单链表C，其首结点指针为c，并且合并后的单链表的数据不重复；

9、将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a和b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序；

10、请编程实现链栈的基本操作函数，并通过调用这些基本函数，实现十进制和八进制转换的功能。

【实验环境】 VC++ 6.0

【实验要求】

将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。

实验三 二叉树的基本操作

【实验目的】

1、 掌握二叉树的概念，学会对二叉链表进行操作。

2、 加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。

【实验性质】 设计型实验

【实验内容】

1、实现二叉树的创建；

2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树； 3、编写递归算法，计算二叉树中叶子结点的数目； 4、编写递归算法，计算二叉树的深度；

5、编写递归算法，将二叉树中所有结点的左、右子树相互交换； 6、使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树；

7、在以Tree为根指针的二叉排序树中查找结点；

8、从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）； 9、用非递归算法，先序遍历以Tree为根指针的二叉树；

提示：用数组 BiTNode *stack[max] 构成堆栈，利用这个堆栈实现功能。 10、用凹入表示法的表示以Tree为根指针的二叉树，例如： // 324 // 123 // 746 // 690 // 567

11、用广义表表示以Tree为根指针的二叉树，例如 // (324(123(746,690),567))

12、对以Tree为根指针的二叉树，从根结点开始，逐层从左到右输出各结点的数据。 提示：用数组 BiTNode *queue[max] 构成队列，利用这个队列实现功能

13、根据Huffman编码原理，使用数组elem中的随机数序列（以0表示结束，不包括0）作为结点的权重，生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度。 14、（1）随机生成二叉树。 （2）生成并保存先（后）序、中序输出序列。 （3）按照保存的一对输出序列恢复出二叉树。（4）生成先（后）序输出序列。

【实验环境】 VC++ 6.0

【实验要求】

将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。