第九章 实验内容与上机指导

数据结构第九章实验内容与上机指导第九章实验内容与上机指导9.1实验1线性表及其运算9.2实验2链表及其运算9.3实验3二叉树的存储与遍历9.4实验4图的存储与遍历9.5实验5排序9.6实验6查找第九章实验内容与上机指导实验一线性表及其运算一、实验目的1.掌握线性表的逻辑特征2.掌握线性表顺序存储结构的特点3.熟练掌握线性表的基本运算4.掌握栈和队列的特点及其运算二、实验内容1.有一个已按递增次序排好序的线性表，今输入一个数，要求按原来的排序规律将它插入到线性表中。第九章实验内容与上机指导[实验说明]设已建立了一个上界为11，元素个数为10递增排序的线性表：12，14，16，22，25，27，29，32，43，70。若将待插入数据插入到合适位置，首先将线性表的末尾元素与之比较。如果该元素小于待插入元素，则直接将插入元素放到线性表末端即可；否则从线性表头开始，找到其插入的第i个位置，将第i个元素之后的所有元素依次后移，最后将其插入第i个位置，即完成了所要求的操作。第九章实验内容与上机指导2.利用一个堆栈，将一个线性表中的元素按逆序重新存放。例如原来的顺序为12，8，6，4，2，要求改为2，4，6，8，12。[实验说明]设原始数据已存入数组a中，堆栈为stack，已清空，栈指针为top，初始top=0。首先从线性表第1个元素开始，依次将其元素压入栈中，然后将栈中元素依次弹出，重新放入数组a中。3.设数组QU[0，mo-1]中存放循环队列的元素。编写能向该循环队列插入一个结点数据和删除一个结点数据的程序。第九章实验内容与上机指导[实验说明](1)队列的特点是在队尾入队，在队首出队。在循环队列中，最初队列为空时队首指针front和队尾指针rear都指向同一位置，当有元素入队时，由于是循环的，所以rear位置前移，即：

QU.rear=(QU.rear+1)%mo

将插入元素放到rear的新位置上。(2)当有元素出队时，先将front前移一个位置，即：

QU.front=(QU.front+1)%mo

将front新位置的元素取出即可。第九章实验内容与上机指导三、实验要求按要求编写实验程序，将实验程序上机调试运行，给出输出的结果，并提交实验报告，写出调试运行程序的分析和体会。返回第九章实验内容与上机指导实验二链表及其运算一、实验目的1.掌握链表存储结构的特点2.熟练掌握单链表的基本运算3.掌握循环链表和双链表的特点和基本运算二、实验内容1.建立一个单链表，显示链表中每个结点的数据，并做删除和插入处理。[实验说明](1)建立链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。第九章实验内容与上机指导(2)

显示链表是将链表中各结点的数据依次显示。设一个指针变量p，先指向第1个结点，显示p所指的结点，然后p后一个结点再显示之，直到链表尾结点。(3)

删除链表中的结点是从p指向第1个结点开始，检查该结点的数据是否等于要删除的数据，如果相等就将该结点删除，如不相等，则将p后移一个结点，如此进行下去，直到表尾为止。(4)插入结点是将一个结点插入到已知的链表中，且保持结点的数据按原来的递增次序排列。2.建立一个双链表，从链首开始，顺序显示链表中的所有结点的数据，然后从链尾开始，反序显示链表中所有结点的数据，最后将一个新的结点插入到链表中。第九章实验内容与上机指导[实验说明](1)

设双向链表的类型定义如下:

structchn

{ structchn*prior; structchn*next; chardata[100]; }prior是指向直接前趋结点的指针，next是指向直接后继结点的指针。结点的数据域为字符串。第九章实验内容与上机指导(2)建立双链表时，用到复制字符串库函数：

strcpy(char*destin,char*source);

该函数的功能是将字符串source的内容复制到字符型数组destin中。在本程序中应用此函数是将输入到字符数组buf中的字符串复制到双链表一个结点的数据域中。(3)通过向后指针next，可以从链首向后顺序显示链表中各结点的数据；通过向前指针prior可以从链尾反序显示链表中各结点的数据。(4)修改向前、向后指针可以实现从双链表中删除和插入结点。设该双链表没有空表头结点，即其链首结点的prior域为NULL，其链尾结点的next域为NULL。第九章实验内容与上机指导3.建立如图所示的循环链表，编写一个程序将所有箭头方向取反。第九章实验内容与上机指导[实验说明](1)因为此链表为循环链表，所以建此链表时最后一个结点的指针域不能是p->next=NULL，而是指向第一个结点，即p->next=head;p=head;(2)为了将链表的所有箭头取反，需从头开始扫描单链表，将第一个结点的next域指向最后一个结点，将第二个结点的next域指向第一个结点，将第三个结点的next域指向第二个结点，…直到最后一个结点用head指向它。(3)判定最后一个结点不能用p->next=NULL，因为是循环链表，需用q指向第1个结点，以p!=q作为条件。返回第九章实验内容与上机指导实验三二叉树的存储与遍历一、实验目的1.掌握二叉树的非线性和递归性特点2.掌握二叉树的存储结构3.掌握二叉树的遍历（递归和非递归方式）操作的实现方法二、实验内容1.建立链式存储二叉树并遍历该二叉树。[实验说明](1)采用链式存储结构建立二叉树，并按先序输入二叉树的结点序列。例如建立如图所示的二叉树：第九章实验内容与上机指导第九章实验内容与上机指导建立时按先序输入的结点序列为：

abc000de0f00g00(2)二叉树的建立、先序遍历、中序遍历、后序遍历均采用递归方式实现。(3)主函数中设计一个选项菜单，可选择执行建立二叉树，先序、中序、后序遍历二叉树。2.用栈实现二叉树先序遍历的非递归程序。第九章实验内容与上机指导[实验说明](1)非递归遍历二叉树的程序中，要用栈来保存遍历经过的路径，才能访问到二叉树的每一个结点。先序遍历二叉树的顺序是“根、左、右”，所以，在对二叉树进行先序遍历时，从二叉树的根结点开始，在沿左子树向前走的过程中，将所遇结点进栈，并退栈访问之，并将其左、右子树进栈，当前进到最左端无法再走下去时，则退回，按退回的顺序进入其右子树进行遍历，如此重复直到树中的所有结点都访问完毕为止。(2)上题所示的二叉树，先序非递归方式遍历该二叉树时栈的变化如下：第九章实验内容与上机指导第九章实验内容与上机指导第九章实验内容与上机指导第九章实验内容与上机指导第九章实验内容与上机指导返回第九章实验内容与上机指导实验四图的存储与遍历一、实验目的1.掌握图的非线性结构的特点2.掌握图的邻接矩阵和邻接表的存储结构3.掌握基于图的两种常用存储结构下的深度优先搜索（DFS）和广度优先搜索操作的实现。二、实验内容1.完成无向图用邻接矩阵存储的深度优先搜索程序。第九章实验内容与上机指导[实验说明](1)用邻接矩阵表示图，除了要用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。为了反映上面图的全面信息，可以采用以下结构：#defineMAX10

typedefstruct

{ charvexs[MAX]; intedges[MAX][MAX]; intn,e;}MGraph;第九章实验内容与上机指导(2)图的深度优先搜索可以通过递归调用来实现，其调用过程可描述如下：DFS(Vi)访问Vi结点；visited[i]=true;对所有与Vi相邻接的顶点jifvisited[j]=FalsethenDFS(Vj);visited[]是一个布尔型标志数组，用以标志一个结点是否被访问过。第九章实验内容与上机指导2.完成无向图用邻接表的广度优先搜索程序。[实验说明](1)广度优先搜索是一种分层的搜索过程，当访问图中某指定起始点后，由V0出发访问与它相邻的所有顶点w1，w2…，然后再访问w1，w2…等各顶点的相邻顶点，如此做下去，直到所有的顶点均被访问过为止。当然访问过程中已被访问过的顶点则不重复访问。为此程序中设置了一个访问标志数组visited[MAX]。(2)广度优先搜索不是递归过程，过程中需借一个队列Q[MAX]，其队头指针为front，队首指针为rear。返回第九章实验内容与上机指导实验五排序一、实验目的1.掌握常用排序方法的基本思想及其实现技术2.了解各种排序方法的优缺点和适用范围二、实验内容实现冒泡、直接插入、选择排序和快速排序，并比较各种排序算法的运行速度。[实验说明](1)

采用顺序表存放待排序的记录，设关键字类型为整型。(2)

设计一个菜单，以菜单方式选择上述排序方法。(3)程序执行时，能按趟输出排序的结果。返回第九章实验内容与上机指导实验六查找一、实验目的1.掌握常用查找方法的基本思想及其实现技术2.了解各种查找方法的优缺点和适用范围二、实验内容1.在有n个元素的顺序表上进行顺序查找。[实验说明](1)

建立有n个元素的顺序表，数据元素为整型。(2)在该顺序表上查找某个数据，若查找成功输出其位置，若查找失败输出失败信息。第九章实验内容与上机指导2.在有n个元素的有序顺序表上进行二分查找。[实验说明](1)

建立有n个元素的有序顺序表，