《数据结构与算法》试验指导书

本文格式为Word版，下载可任意编辑——《数据结构与算法》试验指导书试验1线性表及其操作算法实现-单链表试验

一、试验目的

1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并把握单链表的类定义以及成员函数的定义与调用。

2.把握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。

二、试验要求

1．预习C语言中结构体的定义与基本操作方法。2．对单链表的每个基本操作用单独的函数实现。3．编写完整程序完成下面的试验内容并上机运行。

三、试验内容

1．编写程序完成单链表的以下基本操作：(1)初始化单链表La。(2)在La中插入一个新结点。(3)删除La中的某一个结点。

(4)在La中查找某结点并返回其位置。(5)打印输出La中的结点元素值。

2．构造两个带有表头结点的有序单链表La、Lb，编写程序实现将La、Lb合并成一个有序单链表Lc。

合并思想是：程序需要3个指针：pa、pb、pc，其中pa，pb分别指向La表与Lb表中当前待比较插入的结点，pc指向Lc表中当前最终一个结点。依次扫描La和Lb中的元素，比较当前元素的值，将较小者链接到*pc之后，如此重复直到La或Lb终止为止，再将另一个链表余下的内容链接到pc所指的结点之后。

3．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最终一个结点变成第一个结点，原来倒数其次个结点变成其次个结点，如此等等。）

四、思考与提高

1．假使上面试验内容2中合并的表内不允许有重复的数据该如何操作？

2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？

试验2队列与栈及其操作算法实现-栈的操作试验

一、试验目的

1．熟悉并能实现栈的定义和基本操作。2．了解和把握栈在递归和非递归算法的应用。

二、试验要求

1．进行栈的基本操作时要注意栈“后进先出〞的特性。2．编写完整程序完成下面的试验内容并上机运行。

三、试验内容

1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。

2．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。

主要功能描述如下：1、从键盘上输入表达式。2、分析该表达式是否合法：

(1)是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。(2)是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。

(3)若是其它字符，则返回错误信息。

3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：voidinitstack()：初始化堆栈intMake_str()：语法检查并计算

intpush_operate(intoperate)：将操作码压入堆栈intpush_num(doublenum)：将操作数压入堆栈intprocede(intoperate)：处理操作码

intchange_opnd(intoperate)：将字符型操作码转换成优先级intpush_opnd(intoperate)：将操作码压入堆栈

intpop_opnd()：将操作码弹出堆栈

intcaculate(intcur_opnd)：简单计算+，-，*，/doublepop_num()：弹出操作数

3．已知函数t(n)=2*t(n/2)+n其中t(0)=0，n为整数。编写程序实现：(1)计算t(n)的递归算法。

(2)用链式栈实现计算t(n)的非递归算法。

四、思考与提高

1．假使一个程序中要用到两个栈，为了不发生上溢错误，就必需给每个栈预先分派一个足够大的存储空间。若每个栈都预分派过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？

2．栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？

3．在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来便利地实现？如何实现？

试验3队列与栈及其操作算法实现-队列的操作试验

一、试验目的

1．熟悉并能实现顺序循环队列的定义和基本操作。2．了解用队列解决实际应用问题。

二、试验要求

1．进行队列的基本操作时要注意队列“先进先出〞的特性。2．复习关于栈操作的基础知识。

3．编写完整程序完成下面的试验内容并上机运行。

三、试验内容

1．任意输入队列长度和队列中的元素值，构造一个顺序循环队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。

2．约瑟夫环的实现：设有n个人围坐在圆桌周边，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题蜕变而来，所以寻常称为Josephus问题。

例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6

编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。

四、思考与提高

1．链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？2．一个程序中假使要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。假使一个程序中要用到两个队列，能否实现？如何实现？

试验4树及其操作算法实现-二叉树试验

一、试验目的

1．学会实现二叉树结点结构和对二叉树的基本操作。

2．把握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

二、试验要求

1．认真阅读和把握和本试验相关的教材内容。2．编写完整程序完成下面的试验内容并上机运行。

三、试验内容

1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。

2．编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。

四、思考与提高

1．如何计算二叉链表存储的二叉树中度数为1的结点数？

2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?

试验5排序与查找算法实现-内部排序试验

一、试验目的

1．把握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。

2．对各种查找、排序技术的时间、空间繁杂性有进一步认识。

二、试验要求

1．认真阅读和把握和本试验相关的教材内容。2．编写完整程序完成下面的试验内容并上机运行。3．整理并上交试验报告。

三、试验内容

编写程序实现下述五种算法，并用以下无序序列加以验证：

49，38，65，97，76，13，27，49

1．简单插入排序2．冒泡排序3．快速排序4．归并排序5．堆排序

四、思考与提高

1．设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，采用哪一种排序方法最好？为什么？

2．如何构造一种排序方法，使五个整数至多用七次比较就可以完成排序任务？

试验5排序与查找算法实现-内部排序试验

一、试验目的

1．把握简单插入排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。

2．对各种查找、排序技术的时间、空间繁杂性有进一步认识。

二、试验要求

1．认真阅读和把握和本试验相关的教材内容。2．编写完整程序完成下面的试验内容并上机运行。3．整理并上交试验报告。

三、试验内容

编写程序实现下述五种算法，并用以下无序序列加以验证：