11021199实验一 线性表的插入与删除实验报告

《11021199实验一 线性表的插入与删除实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、印输出。(3)在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。3．以N=100及N=400分别运行2的程序，并比较它们的运行时间。4．编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。3.实验步骤和要求1．事先编制好实验内容中1、2、4的程序（可参考本实验中的方法说明），并调试通过。2．运行1的程序，生成1000个0至999之间的随机整数的数据文件，并打印输出此数据文件。3．以N=100运行2的程序，并记下运行时间。4．以N

3、=400运行2的程序，并记下运行时间。5．运行4的程序。6．整理程序清单和运行结果，写出实验报告。4.方法说明（1）随机整数的产生产生随机整数的方法有很多，下面只介绍一种方法：16设m=2，初值y0=0，则递推公式yi=mod(2053yi-1+13849，m)产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算xi=INT(1000yi/m)。其中mod（*）是模运算，INT（*）是取整函数。（2）线性表的插入与删除在本实验中线性表是动态增长的。插入一个新元素后，为了使线性表仍保持

4、有序，必须要找到新元素应插入的位置。实际上这是一个插入排序的问题。为了要将新元素插入到一个有序的线性表中，可以从原有序表的最后一个元素开始，往前逐个与新元素比较，并将大于新元素的所有元素都往后移动一个位置，直到找到新元素应插入的位置为止。显然，插入一个新元素后，表的长度也增加了1。现假设用一个数组L(1:m)来存储线性表，其中m为最大容量（在本实验中为m=1000）；用一个变量n表示线性表的长度（在本实验中，其初值为n=0）。则可以得到将新元素插入到有序线性表的算法如下。输入：数组L(1:m)，有序线性表L(

5、1:n)，需插入的新元素b。其中n

6、: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个随机数链接成有序链表。其插入排序的方法如下。依次从数据文件中读入一个数据，将它按行顺序存放到数组A的第一列中，然后通过相应行的第二列将它链接到已经有序的链表中

7、。其过程为：将读入的数据依次与链表中各元素进行比较，找到其应该插入的位置后，适当改变链指针，将其插入。其算法如下：输入：1000个随机整数。输出：头指针为H的有序链表。五、程序代码：#include#include#includeusingnamespacestd;ifstreamfin("data.txt");ofstreamfout("data.txt");//yi=mod(2053yi-1+13849，m)//xi=INT(1000yi/m)//建立链

8、表结构structLnode{intd;Lnode*next;};//伪随机数产生类，有方法nextRand()产生随机数classLRandom{private:intseed,nnum,innum;public:voidinitRand(){seed=65536;nnum=0;}intnextRand(){nnum=(2053*nnum+13849)%seed;innum=int(1000*nn