第9章实验内容与上机指导.ppt

数据结构 第九章 实验内容与上机指导 第九章 实验内容与上机指导 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)??设双向链表的类型定义如下: struct chn { struct chn *prior; struct chn *next; char data[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=he