北航計算機軟件技術基礎實驗報告1——線性表的插入與刪除

1、實驗報告實驗名稱 線性表的插入與刪除 班 級 學 號 姓 名 成 績 實驗概述： 【實驗目的及要求】 1. 實驗目的掌握線性表在順序分配下的插入與刪除運算；掌握線性表的鏈式存儲結構；掌握插入排序的方法；并掌握一種產生隨機數(shù)的方法。2. 實驗內容產生1000個0至999間的隨機整數(shù)，并以產生的次序存入一個數(shù)據(jù)文件中。編制一個程序，依次實現(xiàn)以下功能：定義一個有序（非遞減）線性表，其最大容量為1000，初始時為空。從由1產生的數(shù)據(jù)文件中依次取前N個隨機整數(shù)，陸續(xù)插入到此線性表中，并要求在每次插入后保持線性表的有序性。最后將此有序線性表打印輸出。在由（2）產生的線性表中，依在1中產生的次序逐個將元素刪

2、除，直至表空為止。以N=100及N=400分別運行2的程序，并比較它們的運行時間。編寫一個程序，用插入排序依次將1中產生的1000個隨機整數(shù)鏈接成有序鏈表（不改變原隨機數(shù)在存儲空間中的順序）。3. 實驗步驟和要求事先編制好實驗內容中1、2、4的程序（可參考本實驗中的方法說明），并調試通過。運行1的程序，生成1000個0至999之間的隨機整數(shù)的數(shù)據(jù)文件，并打印輸出此數(shù)據(jù)文件。以N=100運行2的程序，并記下運行時間。以N=400運行2的程序，并記下運行時間。運行4的程序。整理程序清單和運行結果，寫出實驗報告。【實驗原理】1.隨機整數(shù)的產生產生隨機整數(shù)的方法有很多，下面只介紹一種方法：設m=216

3、，初值y0=0，則遞推公式y(tǒng)i=mod(2053 yi-1+13849，m)產生0至65535之間的隨機整數(shù)。如要產生0至999之間的隨機整數(shù)，只需做運算xi=INT(1000yi/m)。其中mod（*） 是模運算，INT（*）是取整函數(shù)。2.線性表的插入與刪除在本實驗中線性表是動態(tài)增長的。插入一個新元素后，為了使線性表仍保持有序，必須要找到新元素應插入的位置。實際上這是一個插入排序的問題。為了要將新元素插入到一個有序的線性表中，可以從原有序表的最后一個元素開始，往前逐個與新元素比較，并將大于新元素的所有元素都往后移動一個位置，直到找到新元素應插入的位置為止。顯然，插入一個新元素后，表的長度也

4、增加了1?，F(xiàn)假設用一個數(shù)組L(1:m)來存儲線性表，其中m為最大容量（在本實驗中為m=1000）；用一個變量n表示線性表的長度（在本實驗中，其初值為n=0）。則可以得到將新元素插入到有序線性表的算法如下。輸入：數(shù)組L(1:m)，有序線性表L(1:n)，需插入的新元素b。其中nm。輸出：插入b后的有序線性表L(1:n)。要在原線性表中刪除一個元素b（在本實驗中，保證b在線性表中），且仍保持線性表的順序存儲結構，可以從線性表的第一個元素開始，往后逐個與新元素相比較，直到發(fā)現(xiàn)一個元素與新元素相等。然后從當前位置的下一個元素開始，將后面所有元素都往前移動一個位置，直到線性表的最后一個位置為止。顯然，刪

5、除一個元素之后，線性表的長度減小了1。其算法如下。輸入：線性表L(1:n)，n為線性表的長度，刪除的元素b（一定在線性表中）。輸出：刪除b后的線性表L(1:n)。在上述算法中，從線性表的第一個元素開始尋找要刪除的元素b,實際上我們還可以從線性表的最后一個元素開始尋找b，其算法留給讀者自行考慮。3.線性鏈表的插入排序定義一個二列數(shù)組A(1:1000，1:2)，其中，A(i,1)(i=1,2,1000)依隨機數(shù)產生的順序存放1000個數(shù)據(jù)，A(i,2)(i=1,2,1000)為鏈接指針，將1000個隨機數(shù)鏈接成有序鏈表。其插入排序的方法如下。依次從數(shù)據(jù)文件中讀入一個數(shù)據(jù)，將它按行順序存放到數(shù)組A的

6、第一列中，然后通過相應行的第二列將它鏈接到已經有序的鏈表中。其過程為：將讀入的數(shù)據(jù)依次與鏈表中各元素進行比較，找到其應該插入的位置后，適當改變鏈指針，將其插入。其算法如下：輸入：1000個隨機整數(shù)。輸出：頭指針為H的有序鏈表?！緦嶒灜h(huán)境】（使用的軟硬件） 處理器 英特爾 Core i5-4200M 2.50GHz 雙核 內存 4 GB ( 記憶科技 DDR3L 1600MHz )操作系統(tǒng) Windows 10 專業(yè)版 64位 ( DirectX 12 )編譯環(huán)境 Dev-C+ 5.6.1編譯語言 C 實驗內容：【實驗方案設計】1. 利用遞推公式y(tǒng)i=mod(2053 yi-1+13849，m)

7、產生0至65535之間的隨機整數(shù)。如要產生0至999之間的隨機整數(shù)，只需做運算xi=INT(1000yi/m)。將數(shù)據(jù)寫入D:data.txt中2.從1中產生的文件中依次讀出數(shù)據(jù)，以數(shù)組形式創(chuàng)建一個空白線性表，以插入排序算法依次將數(shù)據(jù)茶如有序線性表中，最后打印輸出。再從文件中依次讀取數(shù)據(jù)，與線性表中元素對比，刪除該元素。刪除方法為：將線性表后一個元素的值賦給當前元素。最終達到清空線性表的目的。3.以N=100和N=400分別運行2中的程序，比較運行時間。4.以二維數(shù)組的形式創(chuàng)建一個靜態(tài)鏈表，第一維存放從文件中讀取的數(shù)據(jù)，第二維存放指向下一個元素位置的指向記號，鏈表開始的標志是指向記號指向最小元

8、素，鏈表結束的標志是指向記號置-1。用插入排序的方法將數(shù)據(jù)存入數(shù)組中并形成鏈表結構。5.整理實驗結果，寫出實驗報告【實驗過程】（實驗步驟、記錄、數(shù)據(jù)、分析）實驗一：源代碼：/*實驗1:產生1000個0至999間的隨機整數(shù)，并以產生的次序存入一個數(shù)據(jù)文件中。*/#include#include #includeint main()long m = 65536, y = 0;int x, i;/定義一個文件類型的指針FILE *fp;/用fopen函數(shù)新建一個文件，失敗則返回0 if (fp = fopen(D:data.txt, w) = NULL)fprintf(stderr, Error o

9、pening file.);exit(0);printf(The data has been output to D:data.txt!n);printf(All data is as follows!nn);/遞歸創(chuàng)造1000個0999之間的隨機數(shù) for (i = 0; i1000; i+)y = (2053 * y + 13849) % m;x = (int)(1000 * y / m);fprintf(fp, %dn, x);printf(%d:%dt, i + 1, x);/關閉文件 fclose(fp);exit(1);運行結果：實驗二、實驗三：源代碼：/*實驗2:編制一個程序，依

10、次實現(xiàn)以下功能：1.定義一個有序非遞減線性表,其最大容量為1000,初始時為空。2.從由1產生的數(shù)據(jù)文件中依次取前N個隨機整數(shù)陸續(xù)插入到此線性表中,并要求在每次插入后保持線性表的有序性。最后將此有序線性表打印輸出。3.在由2產生的線性表中，依在1中產生的次序逐個將元素刪除直至表空為止。實驗3:以N=100及N=400分別運行2的程序，并比較它們的運行時間。*/#include#include#include #define N 1000void main()/新建時鐘變量，得到程序從開始運行到某時刻經過的時鐘周期數(shù)clock_t start, finish;FILE *fp;int a1000

11、;int i, j, n, temp;double duration;/Part 1:創(chuàng)建一個有序線性表 start = clock();if (fp = fopen(D:data.txt, r) = NULL)fprintf(stderr, Error opening file.);exit(0);/判斷插入順序是否合理 else if (n = N1000)printf(Data overflow!Please try again!);exit(0);/比較插入元素與有序表中元素位置并插入 else for (n = 0; n0) & (ai - 1temp); i-)ai = ai -

12、1;ai = temp;for (i = 0; i0; n-)fscanf(fp, %d, &temp);for (i = 0; i= n)printf(This element CANNOT be found!);/若要刪除元素不是位于順序表最后一位，則將后面的元素前移一位；若位于最后一位，直接令n-即可，不必再移動else if (in - 1)for (j = i; jn; j+)aj = aj + 1;else;/打印清空后的順序表for (i = 0; i0; n-)改成了for (; n20; n-)，即刪除至剩20個數(shù)據(jù)的線性表，目的為驗證刪除一些元素后線性表仍保持有序）實驗三：

13、1.N=100t1=0.005000s t2=0.001000s2.N=400t1=0.049000s t2=0.001000s實驗四：源代碼：/*實驗4:編寫一個程序，用插入排序依次將1中產生的1000個隨機整數(shù)鏈接成有序鏈表,不改變原隨機數(shù)在存儲空間中的順序。*/#include#include#define N 1000int main()FILE *fp;int aN2;int H, i, k, x;if (fp = fopen(D:data.txt, r) = NULL)fprintf(stderr, Error opening file.);exit(0);/定義頭節(jié)點位置 H =

14、 0;fscanf(fp, %d, &x);a00 = x;/定義鏈表結束標志 a01 = -1;/逐一插入元素并與原鏈表內元素比較以確定位置 for (k = 1; kN; k+)fscanf(fp, %d, &x);ak0 = x;/在鏈表頭結點插入元素if (ak0aH0)ak1 = H;H = k;/在鏈表某一位置插入一個元素 elsei = H;while (ai1 != -1) & (aai10x)i = ai1;ak1 = ai1;ai1 = k;printf(A linked list containing %d numbers has been created!n, N);p

15、rintf(Its head pointer is %d,its value is %d.n, H, aH0);printf(The data is as follows.nn);i = H;/按大小順序打印鏈表 doprintf(%dt, ai0);i = ai1; while (ai1 != -1);exit(1);運行結果：【結論】（結果）1.實驗1中利用函數(shù)遞歸的方法得到隨機數(shù)的方法是可行的，要得到(0,a)之間的隨機數(shù)只需加xi=INT(a*yi/m)語句即可。2.實驗2中利用插入排序法可以成功將一組無序數(shù)據(jù)按從小到大順序排好并放入線性表中，利用順序查找法可以成功找到、刪除任意元素。

16、第四個結果圖說明刪除一些元素后線性表順序保持不變3. 實驗3中N=100時插入時間t1=0.005000s，清空時間t2=0.001000s；N=400時插入時間t1=0.049000s，清空時間t2=0.001000s。當表中已經有n個數(shù)時，再插入一個數(shù)時，若比較i次，則需要移動i次（1= i =n)。假設他們的概率相等，則平均需要比較 (n+1) / 2次，移動 (n+1) / 2次。即順序表中已經有n個數(shù)的時候，再進行插入排序運算的算法復雜度為O(n)。那么假設題目要求一共讀取N個數(shù)，則程序平均要執(zhí)行(N+1)*N/2，即算法的時間復雜度為O(n2)。同理，刪除這N個數(shù)的算法的時間復雜度

17、也為O(n2)。在此程序中N=400時插入時間約為N=100時的10倍，基本符合，誤差是由于運行時電腦環(huán)境及計時誤差引起的4.實驗4中用二維數(shù)組模擬靜態(tài)鏈表成功實現(xiàn)了數(shù)據(jù)的插入及排序功能【小結】在完成這份實驗報告后，感慨良多。在實驗四中，要求是用二維數(shù)組模擬靜態(tài)鏈表，數(shù)組第一維用來存放數(shù)據(jù)，第二維用來存放指向下一個數(shù)據(jù)的記號，在本實驗中是下一個數(shù)據(jù)的位置。而參考報告中則是創(chuàng)建了一個struct類型的動態(tài)鏈表，與實驗要求有所出入。因此我認真分析題目給出的示例算法，一步步思考判斷條件與循環(huán)等問題，遇到想不明白的條件時就畫一個二維數(shù)組并將具體數(shù)據(jù)放入再進行分析或上網查找相關內容。最終，親自完成四個實驗的代碼編寫、調試及注釋說明后，我掌握了很多知識點。實驗1有文件的創(chuàng)建、數(shù)據(jù)寫入、隨機數(shù)創(chuàng)