1、實驗二 線性表一 實驗任務(wù)1）線性表的順序表示和實現(xiàn)2）線性表的鏈式結(jié)構(gòu)表示和實現(xiàn)二 實驗?zāi)康?）掌握線性表的類型定義和結(jié)構(gòu)特點。2）掌握線性表的順序存儲表示、鏈式存儲表示及其C語言實現(xiàn)。3）掌握順序表的各種基本操作的實現(xiàn)。4）掌握線性表在鏈式存儲結(jié)構(gòu)上的各種操作。三 實驗原理 1線性表的邏輯結(jié)構(gòu)及特性所謂線性表（Linear_List），就是n（n0）個數(shù)據(jù)元素的集合 a1, a2, , an ，這些數(shù)據(jù)元素之間有邏輯上的線性關(guān)系。線性表的抽象數(shù)據(jù)類型定義如下：ADT List 數(shù)據(jù)對象：D=ai| aiElemSet, i=1,2, ,n, n0數(shù)據(jù)關(guān)系：R1= | ai1, aiD, i

2、 =2, n基本操作：CreatList(&L) 操作結(jié)果：生成一個空的線性表L。ListLength(L) 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。ListInsert(&L, i, e) 初始條件：線性表L已存在，1iListLength(L)+1。 操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。ListDelete(&L, i, &e)初始條件：線性表L已存在且非空，1iListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。GetElem(L, i, &e) 初始條件：線性表L已存在，1iListLength(L)

3、。操作結(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ù)據(jù)元素不存在，則返回值為0。ListEmpty(L) 初始條件：線性表L已存在。 操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE。ClearList(&L) 初始條件：線性表L已存在。 操作結(jié)果：將L重置為空表。DestroyList(&L) 初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表L。 ADT List2線性表的順序表示線性表

4、的順序表示就是利用一組地址連續(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ù)類型描述如下：#define MAXLEN 100#define LIST_INCREASE 10 /線性表存儲空間的動態(tài)分配增量typedef structElemType *list; /線性表的存儲空間的基地址int length; /線性表的當前長度int ma

5、xsize; /線性表當前分配的存儲容量List_Sq;3線性表的鏈式結(jié)構(gòu)鏈式存儲結(jié)構(gòu)具有以下特點：不要求邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰；允許迅速簡單地插入或刪除結(jié)點，而不必移動大量元素；但只能順序存取而不能隨機存取線性表中任一元素。線性表的鏈式存儲結(jié)構(gòu)可通過單鏈表來實現(xiàn)。此時，線性表中的每個元素對應(yīng)單鏈表中的一個結(jié)點，每個結(jié)點的數(shù)據(jù)域存儲線性表的數(shù)據(jù)元素，每個結(jié)點的指針域存儲其后繼元素所在結(jié)點的地址，可以通過每個結(jié)點的指針域訪問到其后繼結(jié)點，如圖2.1所示。 圖2.1 線性鏈表示例因此，單鏈表中每個結(jié)點都是由包含這個數(shù)據(jù)元素的信息和一個指示其直接后繼的指針組成的一個結(jié)構(gòu)體類型，具體描述如

6、下：typedef struct LNodeElemType data;struct LNode * next; LNode, * List_Link;每個單鏈表的頭指針L是List_Link型的變量，指向鏈表中第一個結(jié)點。由表頭指針出發(fā)可以依次訪問到每個結(jié)點，存取相應(yīng)的數(shù)據(jù)元素值。線性表中數(shù)據(jù)元素間的線性關(guān)系都可以通過單鏈表中結(jié)點指針域的鏈接關(guān)系反映出來。當L=NULL時，意味著所表示的線性表為“空”表，其長度n為“零”。四 實驗設(shè)備、儀器、工具及資料 微機、VC五 實驗內(nèi)容（1）實驗任務(wù)1：順序表的表示與實現(xiàn)請編制C程序，利用順序存儲方式來實現(xiàn)下列功能：1）建立主程序菜單，使之具有建立線性

7、表、插入元素、刪除元素、查找元素、銷毀線性表、結(jié)束程序運行等菜單項。2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個線性表，并輸出該原始線性表。3）根據(jù)屏幕菜單的提示選擇，進行數(shù)據(jù)插入、刪除、查找等操作。4）最后，輸出修改之后的線性表并結(jié)束程序的運行。（2）實驗任務(wù)2：線性表的鏈式存儲表示與實現(xiàn)請編制C程序，利用鏈式存儲方式來實現(xiàn)下列功能：1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素、查找元素、銷毀線性表、結(jié)束程序運行等菜單項。2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個單鏈表，并輸出該原始單鏈表。3）根據(jù)屏幕菜單的提示選擇，進行數(shù)據(jù)插入、刪除、查找等操作。4）最后，輸出修改之后的單鏈表并結(jié)束程序的運行。（3）實驗

8、任務(wù)3：線性表的合并（選做）編制C程序?qū)崿F(xiàn)下列功能：1）建立兩個線性表（順序存儲表示或鏈式存儲表示）。2）對已建立的兩個線性表進行升序排序。3）合并這兩個有序表。六 實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于線性表的定義、順序存儲表示和鏈式存儲結(jié)構(gòu)。2）分析掌握教材2123頁中的算法2-12-5，為完成實驗任務(wù)1做好準備。3）分析掌握教材2730頁中的算法2-92-13，為完成實驗任務(wù)2做好準備。4）分析掌握教材25頁中的算法2-72-8或教材3132頁中的算法2-152-16，為完成實驗任務(wù)3做好準備。（2）實驗步驟1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件是什么

9、。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ù)類