第二章線性表及其應用
【實驗目的】
1. 熟練掌握線性表的基本操作在順序儲存和鏈式儲存上的實現；
2. 以線性表的各種操作（建立、插入、刪除、遍歷等）的實現為重點；
3. 掌握線性表的動態分配順序儲存結構的定義和基本操作的實現；
4. 通過本章實驗幫助學生加深對c語言的使用（特別是函式的引數呼叫、指標型別的應用和鍊錶的建立等各種基本操作）。
第一節知識準備
一、線性表的邏輯結構
線性表是由一組具有相同特性的資料元素組成的有限序列。至於每個資料元素，它可以是乙個數，乙個符號，也可以是一頁書，甚至更複雜的資訊。
例如：26個英文本母構成乙個線性表（a，b，c，…，y，z）
一串數字構成另乙個線性表（45，45，32，65，123）
每個資料元素可以由若干資料項組成，常把此資料元素稱為記錄。能唯一標識乙個記錄的資料項的值稱為關鍵字。如：
乙個學校的學生情況表如表2-1所示，表中每個學生的情況為乙個記錄，它由學號、姓名、性別、年齡、年級等五個資料項組成。
學號姓名性別年齡年級
96001 張平女 21 大二
96002 王極男 20 大一
96003 膨磊男 23 大三
96004 嚴正英女 19 大一
96005 李強男 20 大二
綜上所述，線性表有如下特性：
1． 除第乙個和最後乙個元素以外，每個元素有且僅有乙個直接前趨和乙個直接後繼；第乙個結點只有直接後繼，最後乙個結點只有直接前趨。
2． 線性表中的每個資料元素，其資料型別是一致的。
3． 資料元素之間的相對位置是線性的，結構中的資料元素之間存在乙個對乙個的關係。
二、線性表的順序表示和實現
計算機的記憶體是由有限多個儲存單元組成的，每個儲存單元都有對應的整數字址，各儲存單元的位址是連續編號的。對於乙個線性表，如果用一組連續的儲存單元依次存放它的各個資料元素，這就是線性表的順序分配。也就是說，**性表的順序分配結構中，邏輯結構上相鄰的資料元素，其物理位置也是相鄰的。
若乙個資料元素只占用乙個儲存單元，則這種分配方式如圖2-1所示。從圖可知，線性表的第i個資料元素的儲存位址loc（ai）=loc（a1）+（i-1）
如果乙個資料元素佔據k個儲存單元，則有loc（ai）=loc（a1）+（i-1）×k
其中，loc（a1）是線性表的第乙個資料元素的儲存位址。
三、 線性表的鏈式表示和實現
1.單鏈表
線性鍊錶即線性表的鏈式儲存結構是用一組任意的儲存單元（它們可以是連續的，也可以是不連續的）來儲存線性表的各個資料元素。為了表示每個元素與其直接後繼元素之間的邏輯關係，對每個元素來說，除了需要儲存元素本身的資訊之外，還需要儲存乙個指示其直接後繼的資訊（即直接後繼的儲存位置），這兩部分資訊組成了乙個資料元素的儲存結構，稱之為乙個結點（node），當然每乙個結點占用的儲存單元應該是連續的。這樣，每個結點包括兩個域，儲存資料元素本身資訊的域稱之為資料域（data），儲存直接後繼結點儲存位置的域稱之為指標域（next），該域內資訊為一指標，它指出線性表某一資料元素邏輯上直接後繼元素的儲存位置。
由於線性表的最後乙個資料元素沒有後繼，故相應結點的指標域內容為空null（也可以用符號∧表示）。如圖2-2所示為乙個不帶頭結點的單鏈表。
在實際應用中，有時也使用帶頭結點的單鏈表，雖然浪費了乙個結點，但是卻換來了其它操作的便利，例如在插入刪除操作中，不用判斷是否對第乙個結點進行。我們稱這個結點為「哨兵」，其作用往往是不用判斷出界；在以後的學習中，還會經常遇上「哨兵」。
2.迴圈鍊錶
迴圈鍊錶是線性表的一種特殊的鏈式儲存結構，它的特點是線性鍊錶的最後乙個結點（即表尾結點）的指標域存放鍊錶中第乙個結點的位址，則整個鍊錶形成了乙個環。如圖2-4所示。
3.雙向迴圈鍊錶
雙向迴圈鍊錶是對迴圈鍊錶的改進，當我們需要經常查詢某一節點的前驅時，可以增加乙個指向前驅的指標域，構成雙向迴圈鍊錶。
【實驗題】
1. 實現線性表在順序儲存上的實現的基本操作，其中以線性表的各種操作（建立、插入、刪除、遍歷等）的實現為重點，盡量完成教材19頁12個基本操作。
2. 掌握線性表的動態分配順序儲存結構的定義和基本操作的實現；
3. 將1小題中用鏈式儲存的方式實現其基本操作。
以下為補充閱讀材料：
第二節狐狸逮兔子實驗
【問題描述】
圍繞著山頂有10個圓形排列的洞，狐狸要吃兔子，兔子說：「可以，但必須找到我，我就藏身於這十個洞中，你先到１號洞找，第二次隔１個洞（即3號洞）找，第三次隔２個洞（即6號洞）找，以後如此類推，次數不限。」但狐狸從早到晚進進出出了1000次，仍沒有找到兔子。
問兔子究竟藏在哪個洞裡？
這實際上是乙個反覆查詢線性表的過程，用以前學過的程式設計的知識也很容易實現，這裡希望讀者能體會資料結構的思想。
【資料描述】
定義乙個順序表，用具有10個元素順序表來表示這10個洞。每個元素分別表示圍著山頂的乙個洞，下標為洞的編號。
#definelist_init_size10//線性表儲存空間的初始分配量
typedefstructsqlist;
【演算法描述】
statusinitlist_sq(sqlist&l)//initlist_sq
statusrabbit(sqlist&l)
sqlist;
statusinitlist_sq(sqlist*l)/*initlist_sq*/
statusrabbit(sqlist*l)/*第二次隔１個洞找，第三次隔２個洞找，以後如此類推,經過一千次*/
printf("\n兔子可能藏在如下的洞中：");
for(i=0;i if((*l).elem[i]==1) printf("\n此洞是第%d號洞",i+1);/*輸出未進過的洞號*/ returnok; }voidmain() 【測試資料】 最後的輸出結果為：2479 【說明】 本演算法思路比較簡單，採用了順序表表示圍著山頂的10個洞，首先對所有洞設定標誌為1，然後通過1000次迴圈，對每次所進之洞修改標誌為0，最後輸出標誌為1的洞。 【實驗題】 1． 同上面的狐狸逮兔子問題，如果山上有5個洞或20個洞，狐狸從早到晚進進出出了500次或10000次，仍沒有找到兔子。問兔子究竟可能藏在哪個洞裡？ 2． 同上面的問題，將表示洞的線性表採用單鏈表實現，並比較其差異。 資訊23 2120502060 古碧野一 實驗題目 建立乙個線性表，實現線性表的建立，插入，刪除和遍歷 二.實驗目的和要求 實驗目的 熟練掌握線性表的基本操作在順序儲存結構上的實現。實驗要求 用c語言編寫源程式，並除錯通過，測試正確。三.主要儀器裝置 windows xp操作平台，visual c ... 一 實驗目的 1 了解二叉樹的定義及基本運算。2 掌握二叉樹的描述方法 特點 性質及儲存結構。3 掌握二叉樹的基本操作演算法。4 自主設計二叉樹建立 遍歷等操作的整個程式。二 實驗內容 根據建立任意給定的二叉樹，並對此二叉樹進行前序 中序 後序 層次四種遍歷。基本要求 1 具有二叉樹的建立功能 2 ... 一 實驗題目編寫乙個程式實現雙鏈隊的各種基本運算，並在此基礎上設計乙個主程式完成如下功能 1 初始化鏈隊q 2 判斷鏈隊q是否為空 3 依次進隊元素a,b,c 4 出隊乙個元素，輸出該元素 5 輸出鏈隊q的元素個數 6 依次進鏈隊元素d,e,f 7 輸出鏈隊q的元素個數 8 輸出出隊序列 9 釋放鏈...資料結構實驗
資料結構實驗
資料結構實驗