數(shù)據(jù)結(jié)構(gòu)--線性表

1、2021-7-21 2021-7-22 a1a3a4ana2 2021-7-23 2021-7-24 2021-7-25 2021-7-26 a1 ai-1 ai an 空閑空閑 d Loc(ai) 0 i-2 i-1 n-1 MaxSize-1 Loc(a1) Loc(ai)=Loc(a1) + (i - -1)d 隨機(jī)存取隨機(jī)存?。涸谠贠(1)時間內(nèi)存取數(shù)據(jù)元素時間內(nèi)存取數(shù)據(jù)元素 2021-7-27 2021-7-28 2021-7-29 2021-7-210 2021-7-211 o順序存儲出現(xiàn)的問題：線性表的順序存儲結(jié) 構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個元素在物 理位置上也相鄰，因此可以快

2、速地存取表中 各元素。然而，在做插入或刪除元素的操作 時，會引起大量的數(shù)據(jù)元素移動；對于長度 變化較大的線性表，要一次性地分配足夠的 存儲空間，但這些空間常常又得不到充分的 利用；線性表的容量難以擴(kuò)充。 2021-7-212 o鏈?zhǔn)酱鎯Y(jié)構(gòu)的提出：為解決順序表所遇到 的困難，提出線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)，它不要 求邏輯上相鄰的元素在物理位置上也相鄰。 o鏈?zhǔn)酱鎯Y(jié)構(gòu)：是指用一組任意的存儲單元 （可以連續(xù)，也可以不連續(xù)）存儲線性表中 的數(shù)據(jù)元素。用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表 稱為鏈表。根據(jù)鏈表結(jié)點(diǎn)的不同結(jié)構(gòu)，鏈表 分為單鏈表、循環(huán)鏈表和雙鏈表。 2021-7-213 data next 單鏈表的結(jié)點(diǎn)結(jié)構(gòu)

3、：單鏈表的結(jié)點(diǎn)結(jié)構(gòu)： 數(shù)據(jù)域數(shù)據(jù)域指針域指針域 typedef struct LNode /*單鏈表的存儲結(jié)構(gòu)單鏈表的存儲結(jié)構(gòu)*/ DataType data; /*數(shù)據(jù)域數(shù)據(jù)域*/ struct LNode * next; /*指針域指針域*/ LNode,* LinkList; 2021-7-214 上圖所示為線性表（Sun，Mon，Tue，Wed，Thu， Fri，Sat）的線性鏈?zhǔn)酱鎯Y(jié)構(gòu)。這種鏈表有一個頭 指針（H），如果線性表非空，H指向鏈表中第一個結(jié) 點(diǎn)，否則它為空指針（即不指向任何結(jié)點(diǎn)的指針，通 常用NULL或表示）。由于最后一個結(jié)點(diǎn)設(shè)有直接后 繼，所以它的指針域為空。 202

4、1-7-215 2021-7-216 2021-7-217 o按序號查找 o算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為L,要查 找表中第i個結(jié)點(diǎn),則需從單鏈表的頭指針L出發(fā),從 頭結(jié)點(diǎn)開始,順著鏈域掃描。用指針p指向當(dāng)前掃描 到的結(jié)點(diǎn),初值指向第一個結(jié)點(diǎn)(p=L-next)。用j 做計數(shù)器,累計當(dāng)前掃描過的結(jié)點(diǎn)數(shù)（初值為1）, 當(dāng)j=i時,指針p所指的結(jié)點(diǎn)就是要找的第i個結(jié)點(diǎn)。 2021-7-218 o按值查找 o算法描述：按值查找是指在單鏈表中查找是否有結(jié) 點(diǎn)值等于e的結(jié)點(diǎn)，若有，則返回首次找到的其值 為e的結(jié)點(diǎn)的地址，否則返回NULL。查找過程從單 鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個將結(jié)

5、 點(diǎn)的值和給定值e比較。 2021-7-219 o結(jié)點(diǎn)插入到鏈表的第一個結(jié)點(diǎn)前 o算法描述：逆位序輸入n個元素的值，建立帶頭結(jié) 點(diǎn)的單鏈表。該方法從一個空表開始，逐個讀入數(shù) 據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù) 域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上。 2021-7-220 o結(jié)點(diǎn)插入到兩個結(jié)點(diǎn)之間 o算法描述：正位序輸入n個元素的值，建立含有幾 個元素的帶頭結(jié)點(diǎn)的單鏈表。頭插法建立鏈表的算 法雖然簡單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的 順序相反。若希望二者次序一致，可采用尾插法建 表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上， 為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈 表的尾結(jié)點(diǎn)

6、。 2021-7-221 o結(jié)點(diǎn)插入到鏈表的最后一個結(jié)點(diǎn)后 o算法描述：在線性表兩個數(shù)據(jù)元素值分別為a和b的 結(jié)點(diǎn)間插入值為x的結(jié)點(diǎn)，已知p指向a。 2021-7-222 o單鏈表的刪除操作 o算法描述：單鏈表中刪除b，設(shè)p指向a。 2021-7-223 2021-7-224 循環(huán)單鏈表與單鏈表的結(jié)點(diǎn)類型完全相同，循環(huán) 單鏈表的運(yùn)算和單鏈表基本一樣，差別僅在于： 當(dāng)需要從頭到尾掃描整個鏈表時，是否到表尾的 條件不同。在單鏈表L中判斷某結(jié)點(diǎn)鏈域值是否 為“空”，在循環(huán)鏈表中則判斷某結(jié)點(diǎn)P的鏈域 值是否等于頭指針。 struct CNode /*循環(huán)鏈表的存儲結(jié)構(gòu)*/ int data; struct CNode* next; C