实验报告

实验名称

线性表的插入与删除

班 级 学 号 姓 名 成 绩

实验概述： 【实验目的及要求】 1. 实验目的 掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。 2. 实验内容 产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。 编制一个程序，依次实现以下功能： 定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。 从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。 在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。 以N=100及N=400分别运行2的程序，并比较它们的运行时间。 编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。 3. 实验步骤和要求 事先编制好实验内容中1、2、4的程序（可参考本实验中的方法说明），并调试通过。 运行1的程序，生成1000个0至999之间的随机整数的数据文件，并打印输出此数据文件。 以N=100运行2的程序，并记下运行时间。 以N=400运行2的程序，并记下运行时间。 运行4的程序。 整理程序清单和运行结果，写出实验报告。 【实验原理】 1.随机整数的产生 产生随机整数的方法有很多，下面只介绍一种方法： 设m=216，初值y0=0，则递推公式yi=mod(2053 yi-1+13849，m)产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算xi=INT(1000yi/m)。 其中mod（*） 是模运算，INT（*）是取整函数。 2.线性表的插入与删除 在本实验中线性表是动态增长的。插入一个新元素后，为了使线性表仍保持有序，必须要找到新元素应插入的位置。实际上这是一个插入排序的问题。 为了要将新元素插入到一个有序的线性表中，可以从原有序表的最后一个元素开始，往前逐个与新元素比较，并将大于新元素的所有元素都往后移动一个位置，直到找到新元素应插入的位置为止。显然，插入一个新元素后，表的长度也增加了1。现假设用一个数组L(1:m)来存储线性表，其中m为最大容量（在本实验中为m=1000）；用一个变量n表示线性表的长度（在本实验中，其初值为n=0）。则可以得到将新元素插入到有序线性表的算法如下。 输入：数组L(1:m)，有序线性表L(1:n)，需插入的新元素b。其中n0) and (L(i)>b) DO {L(i+1)? L(i);i?i -1} L( i?1)?b } n?n?1}RETURN 要在原线性表中删除一个元素b（在本实验中，保证b在线性表中），且仍保持线性表的顺序存储结构，可以从线性表的第一个元素开始，往后逐个与新元素相比较，直到发现一个元素与新元素相等。然后从当前位置的下一个元素开始，将后面所有元素都往前移动一个位置，直到线性表的最后一个位置为止。显然，删除一个元素之后，线性表的长度减小了1。其算法如下。 输入：线性表L(1:n)，n为线性表的长度，删除的元素b（一定在线性表中）。 输出：删除b后的线性表L(1:n)。 IF n=0 THEN OUTPUT %underflow\ELSE{ i?1 WHILE (i?n) and (L(i)?b) DO i?i?1 IF i?n THEN OUTPUT \ not this element\ ELSE{ IF i?n THEN FOR j?i TO n-1 DO L(j)? L(j?1) n?n?1 }}RETURN 在上述算法中，从线性表的第一个元素开始寻找要删除的元素b,实际上我们还可以从线性表的最后一个元素开始寻找b，其算法留给读者自行考虑。 3.线性链表的插入排序 定义一个二列数组A(1:1000，1:2)，其中，A(i,1)(i=1,2,…,1000)依随机数产生的顺序存放1000个数据，A(i,2)(i=1,2,…,1000)为链接指针，将1000个随机数链接成有序链表。其插入排序的方法如下。