实验一线性表插入和删除.doc

《实验一线性表插入和删除.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一线性表的插入与删除1.实验目的掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。2.实验内容1．产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。2．编制一个程序，依次实现以下功能：(1)定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。(2)从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。(3)在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。3．以N=100及N=400分别运

2、行2的程序，并比较它们的运行时间。4．编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。3.实验步骤和要求1．事先编制好实验内容中1、2、4的程序（可参考本实验中的方法说明），并调试通过。2．运行1的程序，生成1000个0至999之间的随机整数的数据文件，并打印输出此数据文件。3．以N=100运行2的程序，并记下运行时间。4．以N=400运行2的程序，并记下运行时间。5．运行4的程序。6．整理程序清单和运行结果，写出实验报告。4.方法说明（1）随机整数的产生产生随机整数的方法有很多，下面只介绍一种方法：设m=216，初值y0=0，

3、则递推公式yi=mod(2053yi-1+13849，m)产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算xi=INT(1000yi/m)。其中mod（*）是模运算，INT（*）是取整函数。（2）线性表的插入与删除在本实验中线性表是动态增长的。插入一个新元素后，为了使线性表仍保持有序，必须要找到新元素应插入的位置。实际上这是一个插入排序的问题。10为了要将新元素插入到一个有序的线性表中，可以从原有序表的最后一个元素开始，往前逐个与新元素比较，并将大于新元素的所有元素都往后移动一个位置，直到找到新元素应插入的位置为止。显然，插入一个新元素后，表的长度也增加了1。

4、现假设用一个数组L(1:m)来存储线性表，其中m为最大容量（在本实验中为m=1000）；用一个变量n表示线性表的长度（在本实验中，其初值为n=0）。则可以得到将新元素插入到有序线性表的算法如下。输入：数组L(1:m)，有序线性表L(1:n)，需插入的新元素b。其中n

5、个元素之后，线性表的长度减小了1。其算法如下。输入：线性表L(1:n)，n为线性表的长度，删除的元素b（一定在线性表中）。输出：删除b后的线性表L(1:n)。在上述算法中，从线性表的第一个元素开始寻找要删除的元素b,实际上我们还可以从线性表的最后一个元素开始寻找b，其算法留给读者自行考虑。（3）线性链表的插入排序定义一个二列数组A(1:1000，1:2)，其中，A(i,1)(i=1,2,…,1000)依随机数产生的顺序存放1000个数据，A(i,2)(i=1,2,…,1000)为链接指针，将1000个随机数链接成有序链表。其插入排序的方法如下。依次从数据文件中读入一个数据，将它按行顺序存放

6、到数组A的第一列中，然后通过相应行的第二列将它链接到已经有序的链表中。其过程为：将读入的数据依次与链表中各元素进行比较，找到其应该插入的位置后，适当改变链指针，将其插入。其算法如下：输入：1000个随机整数。10输出：头指针为H的有序链表。10实验二二叉树1.实验目的掌握二叉树的存储结构2.实验内容1．对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。2．按层次输出所有结点。3．输出所有叶子结点。4．将所有左右子树值交换。3.实验步骤和要求1．分别编制实验内容中题2、3、4的三个子程序。2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结

7、构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3．自行设计一棵二叉树，重复步骤2。4．整理程序清单与所有结果，并写出实验报告。4.方法说明（1）二叉树的链式存储结构二叉树的每一个结点i有三个域：值域V（i），左链域L（i），右链域R（i10）。我们分别用三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。具体存储方案由读者自行考虑。（2）按层次输