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

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

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