北航計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告1——線性表的插入與刪除_第1頁(yè)
北航計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告1——線性表的插入與刪除_第2頁(yè)
北航計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告1——線性表的插入與刪除_第3頁(yè)
北航計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告1——線性表的插入與刪除_第4頁(yè)
北航計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告1——線性表的插入與刪除_第5頁(yè)
已閱讀5頁(yè),還剩11頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 線性表的插入與刪除 班 級(jí) 學(xué) 號(hào) 姓 名 成 績(jī) 實(shí)驗(yàn)概述: 【實(shí)驗(yàn)?zāi)康募耙蟆?1. 實(shí)驗(yàn)?zāi)康恼莆站€性表在順序分配下的插入與刪除運(yùn)算;掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu);掌握插入排序的方法;并掌握一種產(chǎn)生隨機(jī)數(shù)的方法。2. 實(shí)驗(yàn)內(nèi)容產(chǎn)生1000個(gè)0至999間的隨機(jī)整數(shù),并以產(chǎn)生的次序存入一個(gè)數(shù)據(jù)文件中。編制一個(gè)程序,依次實(shí)現(xiàn)以下功能:定義一個(gè)有序(非遞減)線性表,其最大容量為1000,初始時(shí)為空。從由1產(chǎn)生的數(shù)據(jù)文件中依次取前N個(gè)隨機(jī)整數(shù),陸續(xù)插入到此線性表中,并要求在每次插入后保持線性表的有序性。最后將此有序線性表打印輸出。在由(2)產(chǎn)生的線性表中,依在1中產(chǎn)生的次序逐個(gè)將元素刪

2、除,直至表空為止。以N=100及N=400分別運(yùn)行2的程序,并比較它們的運(yùn)行時(shí)間。編寫一個(gè)程序,用插入排序依次將1中產(chǎn)生的1000個(gè)隨機(jī)整數(shù)鏈接成有序鏈表(不改變?cè)S機(jī)數(shù)在存儲(chǔ)空間中的順序)。3. 實(shí)驗(yàn)步驟和要求事先編制好實(shí)驗(yàn)內(nèi)容中1、2、4的程序(可參考本實(shí)驗(yàn)中的方法說(shuō)明),并調(diào)試通過(guò)。運(yùn)行1的程序,生成1000個(gè)0至999之間的隨機(jī)整數(shù)的數(shù)據(jù)文件,并打印輸出此數(shù)據(jù)文件。以N=100運(yùn)行2的程序,并記下運(yùn)行時(shí)間。以N=400運(yùn)行2的程序,并記下運(yùn)行時(shí)間。運(yùn)行4的程序。整理程序清單和運(yùn)行結(jié)果,寫出實(shí)驗(yàn)報(bào)告?!緦?shí)驗(yàn)原理】1.隨機(jī)整數(shù)的產(chǎn)生產(chǎn)生隨機(jī)整數(shù)的方法有很多,下面只介紹一種方法:設(shè)m=216

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

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

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

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

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

8、素,鏈表結(jié)束的標(biāo)志是指向記號(hào)置-1。用插入排序的方法將數(shù)據(jù)存入數(shù)組中并形成鏈表結(jié)構(gòu)。5.整理實(shí)驗(yàn)結(jié)果,寫出實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)過(guò)程】(實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析)實(shí)驗(yàn)一:源代碼:/*實(shí)驗(yàn)1:產(chǎn)生1000個(gè)0至999間的隨機(jī)整數(shù),并以產(chǎn)生的次序存入一個(gè)數(shù)據(jù)文件中。*/#include#include #includeint main()long m = 65536, y = 0;int x, i;/定義一個(gè)文件類型的指針FILE *fp;/用fopen函數(shù)新建一個(gè)文件,失敗則返回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個(gè)0999之間的隨機(jī)數(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);/關(guān)閉文件 fclose(fp);exit(1);運(yùn)行結(jié)果:實(shí)驗(yàn)二、實(shí)驗(yàn)三:源代碼:/*實(shí)驗(yàn)2:編制一個(gè)程序,依

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

11、;int i, j, n, temp;double duration;/Part 1:創(chuàng)建一個(gè)有序線性表 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!);/若要?jiǎng)h除元素不是位于順序表最后一位,則將后面的元素前移一位;若位于最后一位,直接令n-即可,不必再移動(dòng)else if (in - 1)for (j = i; jn; j+)aj = aj + 1;else;/打印清空后的順序表for (i = 0; i0; n-)改成了for (; n20; n-),即刪除至剩20個(gè)數(shù)據(jù)的線性表,目的為驗(yàn)證刪除一些元素后線性表仍保持有序)實(shí)驗(yàn)三:

13、1.N=100t1=0.005000s t2=0.001000s2.N=400t1=0.049000s t2=0.001000s實(shí)驗(yàn)四:源代碼:/*實(shí)驗(yàn)4:編寫一個(gè)程序,用插入排序依次將1中產(chǎn)生的1000個(gè)隨機(jī)整數(shù)鏈接成有序鏈表,不改變?cè)S機(jī)數(shù)在存儲(chǔ)空間中的順序。*/#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é)點(diǎn)位置 H =

14、 0;fscanf(fp, %d, &x);a00 = x;/定義鏈表結(jié)束標(biāo)志 a01 = -1;/逐一插入元素并與原鏈表內(nèi)元素比較以確定位置 for (k = 1; kN; k+)fscanf(fp, %d, &x);ak0 = x;/在鏈表頭結(jié)點(diǎn)插入元素if (ak0aH0)ak1 = H;H = k;/在鏈表某一位置插入一個(gè)元素 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);運(yùn)行結(jié)果:【結(jié)論】(結(jié)果)1.實(shí)驗(yàn)1中利用函數(shù)遞歸的方法得到隨機(jī)數(shù)的方法是可行的,要得到(0,a)之間的隨機(jī)數(shù)只需加xi=INT(a*yi/m)語(yǔ)句即可。2.實(shí)驗(yàn)2中利用插入排序法可以成功將一組無(wú)序數(shù)據(jù)按從小到大順序排好并放入線性表中,利用順序查找法可以成功找到、刪除任意元素。

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論