北航计算机软件技术基础实验报告1——线性表的插入与删除

《北航计算机软件技术基础实验报告1——线性表的插入与删除》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

3、生随机整数的方法有很多，-卜•面只介绍一种方法：设m=2",初值yo=O,则递推公式yi=mod(2053畑+13849,m)产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算Xj=INT(1000yi/m)。其中mod(*)是模运算，INT(*)是取整函数。2•线性表的插入与删除在本实验中线性表是动态增长的。插入一个新元素后，为了使线性表仍保持有序，必须要找到新元素应插入的位置。实际上这是一个插入排序的问题。为了要将新元素插入到一个有序的线性表小，可以从原有序表的最后一个元素开始，往前逐个与新元素比较，并将大于新元素的

4、所冇元素都往后移动一个位置，直到找到新元素应插入的位置为止。显然，插入一个新元素后，表的长度也增加了1。现假设用一个数组L(l:m)来存储线性表，其屮m为最大容量(在木实验中为m=1000)；用一个变量n表示线性表的长度(在本实验中，其初值为n=0)o则可以得到将新元素插入到有序线性表的算法如下。输入：数组L(l:m),冇序线性表L(l:n),需插入的新元素b。其中nvm。输出：插入b后的有序线性表L(l:n)0IFn=mTHENOUTPUTnoverflow0ELSE{IFn=0THENL(n+1)iELSE{i〜nWHILE(i>0)and(L

5、(i)>b)DO{L(i+1)JL(i);i〜i・1}L(i+l)〜b}n〜n+1}RETURN要在原线性表中删除一个元素b(在木实验中，保证b在线性表中)，且仍保持线性表的顺序存储结构，可以从线性表的第一个元素开始，往后逐个与新元素相比较，直到发现一个元素与新元素相等。然后从当前位置的下一个元素开始,将后面所有元素都往前移动一个位置，直到线性表的最后一个位置为止。显然，删除一个元索之后，线性表的长度减小了1。其算法如下。输入：线性表L(l:n),n为线性表的长度，删除的元素b(—定在线性表中)。输出：删除b后的线性表L(l:n)oIFn=0THE

6、NOUTPUT”underflow”ELSE{i〜1WHILE(inTHENOUTPUTnnotthiselement"ELSE{IFi

7、A(i,2)(i=l,2,...,1000)为链接指针，将1000个随机数链接成有序链表。其插入排序的方法如下。依次从数据文件屮读入一个数据，将它按行顺序存放到数组A的第一列屮,然后通过相应行的笫二列将它链接到已经有序的链表中。其过程为：将读入的数据依次与链表屮各元素进行比较，找到其应该插入的位置后，适当改变链指针，将其插入。其算法如下：输入：1000个随机整数。输出：头指针为H的有序链表。H1;READx;A(l,l)〜x;A(l,2)〜0FORk=2TO1000DO{READx;A(k,l)<—xIFA(H,1)>=xTHEN{A(k,2)«-

8、H;H<-k}ELSE{i〜HWHILE(A(i,2)丰0)and(A(A(i,2),1)