山東大學《數(shù)據(jù)結構》實驗指導02線性表

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

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