实用数据结构电子实验内容与上机指导.pptxVIP

实用数据结构电子实验内容与上机指导;数据结构;第九章 实验内容与上机指导;实验一 线性表及其运算;[实验说明] 设已建立了一个上界为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新位置的元素取出即可。;三、实验要求 按要求编写实验程序，将实验程序上机调试运行，给出输出的结果，并提交实验报告，写出调试运行程序的分析和体会。;实验二 链表及其运算;(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=head; (2) 为了将链表的所有箭头取反，需从头开始扫描单链表，将第一个结点的next域指向最后一个结点，将第二个结点的next域指向第一个结点，将第三个结点的next域指向第二个结点，…直到最后一个结点用head指向它。 (3) 判定最后一个结点不能用p-next=NULL，因为是循环链表，需用q指向第1个结点，以p!=q作为条件。 ;实验三 二叉树的存储与遍历;第16页/共32页;建立时按先序输入的结点序列为： abc000de0f00g00 (2) 二叉树的建立、先序遍历、中序遍历、后序遍历均采用递归方式实现。 (3) 主函数中设计一个选项菜单，可选择执行建立二叉树，先序、中序、后序遍历二叉树。 2. 用栈实现二叉树先序遍历的非递归程序。;[实验说明] (1) 非递归遍历二叉树的程序中，要用栈来保存遍