山東大學(xué)《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)02線性表

實驗二線性表一實驗任務(wù)1)線性表的順序表示和實現(xiàn)2)線性表的鏈?zhǔn)浇Y(jié)構(gòu)表示和實現(xiàn)二實驗?zāi)康?)掌握線性表的類型定義和結(jié)構(gòu)特點。2)掌握線性表的順序存儲表示、鏈?zhǔn)酱鎯Ρ硎炯捌銫語言實現(xiàn)。3)掌握順序表的各種基本操作的實現(xiàn)。4)掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的各種操作。三實驗原理1.線性表的邏輯結(jié)構(gòu)及特性所謂線性表(LineajList),就是n(nNO)個數(shù)據(jù)元素的集合{ai,a2,…,an},這些數(shù)據(jù)元素之間有邏福上的線性關(guān)系。線性表的抽象數(shù)據(jù)類型定義如下：ADTList數(shù)據(jù)對象：D={aj|ajGEIemSet,i=l,2,n>0}數(shù)據(jù)關(guān)系：Ri={<aj-i,ai>|aj-1,ajeD,i=2,…,n)基本操作：CreatList(&L)操作結(jié)果：生成一個空的線性表L。ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。ListInsert(&L,i,e)初始條件：線性表L已存在，lWiWListLength(L)+l。操作結(jié)果:在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加loListDelete(&L,i,&e)初始條件：線性表L已存在且非空，lWWListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減loGet日em(L,i,&e)初始條件：線性表L已存在，lWWListLength(L)。操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。LocateElem(L,e,compare())初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù)。操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。假設(shè)這樣的數(shù)據(jù)元素不存在，那么返回值為0。ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：假設(shè)L為空表，那么返回TRUE,否那么返回FALSE。ClearList(&L)

初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。DestroyList(&L)初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L。}ADTList.線性表的順序表示線性表的順序表示就是利用一組地址連續(xù)的內(nèi)存空間依次存儲線性表的各個數(shù)據(jù)元素，即以元素在計算機內(nèi)''物理位置相鄰〃來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。由于順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，所以通常利用C語言中動態(tài)分配的一組連續(xù)的存儲單元作為順序存儲結(jié)構(gòu)所需要的存儲空間?？赏ㄟ^定義結(jié)構(gòu)體類型來實現(xiàn)線性表的動態(tài)分配順序存儲結(jié)構(gòu)。具體數(shù)據(jù)類型描述如下：#defineMAXLEN100#defineLISTJNCREASE10〃線性表存儲空間的動態(tài)分配增量typedefstruct{ElemType*list;〃線性表的存儲空間的基地址intlength;〃線性表的當(dāng)前長度intmaxsize;〃線性表當(dāng)前分配的存儲容量}List_Sq;.^性表的鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)具有以下特點：不要求邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰;允許迅速簡單地插入或刪除結(jié)點，而不必移動大量元素；但只能順序存取而不能隨機存取線性表中任一元素。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可通過單鏈表來實現(xiàn)。此時，線性表中的每個元素對應(yīng)單鏈表中的一個結(jié)點，每個結(jié)點的數(shù)據(jù)域存儲線性表的數(shù)據(jù)元素，每個結(jié)點的指針域存儲其后繼元素所在結(jié)點的地址，可以通過每個結(jié)點的指針域訪問到其后繼結(jié)點，如圖2,1所示。頭指針第一個結(jié)點圖2.1線性鏈表例如頭指針第一個結(jié)點因此，單鏈表中每個結(jié)點都是由包含這個數(shù)據(jù)元素的信息和一個指示其直接后繼的指針組成的一個結(jié)構(gòu)體類型，具體描述如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*List_Link;每個單鏈表的反指針L是ListJJnk型的變量，指向鏈表中第一個結(jié)點。由表頭指針出發(fā)可以依次訪問到每個結(jié)點，存取相應(yīng)的數(shù)據(jù)元素值。線性表中數(shù)據(jù)元素間的線性關(guān)系都可以通過單鏈表中結(jié)點指針域的鏈接關(guān)系反映出來。當(dāng)L=NULL時，意味著所表示的線性表為''空〃表，其長度n為''零四實驗設(shè)備、儀器、工具及資料微機、VC五實驗內(nèi)容（1）實驗任務(wù)工：順序表的表示與實現(xiàn)請編制C程序，利用順序存儲方式來實現(xiàn)以下功能：1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素、查找元素、銷毀線性表、結(jié)束程序運行等菜單項。2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個線性表，并輸出該原始線性表。3）根據(jù)屏幕菜單的提示選擇，進行數(shù)據(jù)插入、刪除、查找等操作。4）最后，輸出修改之后的線性表并結(jié)束程序的運行。（2）實驗任務(wù)2：線性表的鏈?zhǔn)酱鎯Ρ硎九c實現(xiàn)請編制C程序，利用鏈?zhǔn)酱鎯Ψ绞絹韺崿F(xiàn)以下功能：1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素、查找元素、銷毀線性表、結(jié)束程序運行等菜單項。2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個單鏈表，并輸出該原始單鏈表。3）根據(jù)屏幕菜單的提示選擇，進行數(shù)據(jù)插入、刪除、查找等操作。4）最后，輸出修改之后的單鏈表并結(jié)束程序的運行。（3）實驗任務(wù)3：線性表的合并（選做）編制C程序?qū)崿F(xiàn)以下功能：1）建立兩個線性表（順序存儲表示或鏈?zhǔn)酱鎯Ρ硎荆?）對已建立的兩個線性表進行升序排序。3）合并這兩個有序表。六實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于線性表的定義、順序存儲表示和鏈?zhǔn)酱鎯Y(jié)構(gòu)。2）分析掌握教材21~23頁中的算法2-1~2-5,為完成實驗任務(wù)1做好準(zhǔn)備。3）分析掌握教材27~30頁中的算法2-9~2-13,為完成實驗任務(wù)2做好準(zhǔn)備。4）分析掌握教材25頁中的算法2-7~2-8或教材31-32頁中的算法2-15-2-16,為完成實驗任務(wù)3做好準(zhǔn)備。（2）實驗步驟1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原那么劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示那么更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。3）詳細設(shè)計。詳細設(shè)計的目的是對子程序（過程或函數(shù)）的進一步求精。用IF、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是防止陷入細節(jié)。4）編碼。在詳細設(shè)計的基礎(chǔ)上，對詳細設(shè)計的結(jié)果進一步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七實驗報告要求實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本程序所用的數(shù)據(jù)