1、2022年年5月月5日日1第2章 線性表本章知識要點：線性表的邏輯結構線性表的順序存儲及運算實現(xiàn)線性表的鏈式存儲及運算實現(xiàn)順序表和鏈表的比較2022年年5月月5日日22.1 線性表的邏輯結構線性表的定義線性表的基本操作2022年年5月月5日日32.1.1 線性表的定義線性表是一種線性結構。線性結構的特點是數(shù)據(jù)元素之間是一種線性關系，數(shù)據(jù)元素“一個接一個的排列”。在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構成的線性結構。線性表是具有相同數(shù)據(jù)類型的n(n=0)個數(shù)據(jù)元素的有限序列，通常記為：(a1，a2， ai-1，ai，ai+1，an)2022年年5月月5日日42.

2、1.1 線性表的定義其中n為表長， n0 時稱為空表。表中相鄰元素之間存在著順序關系。將 ai-1 稱為 ai 的直接前趨，ai+1 稱為 ai 的直接后繼。就是說：對于ai，當 i=2，.，n 時，有且僅有一個直接前趨 ai-1.，當i=1，2，.，n-1 時，有且僅有一個直接后繼 ai+1，而 a1 是表中第一個元素，它沒有前趨，an 是最后一個元素無后繼。需要說明的是：ai為序號為 i 的數(shù)據(jù)元素（i=1,2,n），通常我們將它的數(shù)據(jù)類型抽象為datatype，datatype根據(jù)具體問題而定，如在學生情況信息表中，它是用戶自定義的學生類型； 在字符串中，它是字符型； 等等。2022年年

3、5月月5日日52.1.2 線性表的基本操作線性表初始化：Init_List(L) 初始條件：表L不存在 操作結果：構造一個空的線性表 求線性表的長度：Length_List(L) 初始條件：表L存在 操作結果：返回線性表中的所含元素的個數(shù)取表元：Get_List(L,i) 初始條件：表L存在且1=i=Length_List(L) 操作結果：返回線性表L中的第個元素的值或地址按值查找：Locate_List(L,x)，是給定的一個數(shù)據(jù)元素。 初始條件：線性表L存在 操作結果：返回在L中首次出現(xiàn)的值為的那個元素的序號或地址，稱為查找成功; 否則，在L中未找到值為的數(shù)據(jù)元素，返回一特殊值表示查找失敗

4、。插入操作：Insert_List(L,i,x) 初始條件：線性表L存在，插入位置正確 (1=i=n+1,為插入前的表長)。 操作結果：在線性表L的第 i 個位置上插入一個值為 x 的新元素，這樣使原序號為 i , i+1, . , n 的數(shù)據(jù)元素的序號變?yōu)?i+1,i+2, . , n+1，插入后表長=原表長+1。刪除操作：Delete_List(L,i) 初始條件：線性表L存在，1=ilast=-1; return L; /返回順序表的存儲地址 else return 1; /申請不成功，返回錯誤代碼-12022年年5月月5日日10插入運算 線性表的插入是指在表的第i個位置上插入一個值為

5、x 的新元素：【算法2-2】 順序表的插入算法int Insert_SeqList(SeqList *L,int i,DataType x) int j; if (L-last=MAXSIZE-1) cout”表滿”endl; return -1; /表空間已滿，不能插入，返回錯誤代碼-1 if (iL-last+2) cout”位置錯”last;j=i-1;j-) L-dataj+1=L-dataj; /結點移動 L-datai-1=x;/新元素插入2022年年5月月5日日11插入算法的時間性能分析 順序表上的插入運算，時間主要消耗在了數(shù)據(jù)的移動上，在第i個位置上插入 x ，從 ai 到 a

6、n 都要向下移動一個位置，共需要移動 ni1個元素，而 i 的取值范圍為 ：1 i n+1，即有 n1個位置可以插入。設在第i個位置上作插入的概率為Pi，則平均移動數(shù)據(jù)元素的次數(shù)： 設：Pi=1/ (n+1) ，即為等概率情況，則： 這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復雜度為(n)。11)1(Eniiininp11112)1(11)1(Eniniiinninninp2022年年5月月5日日12刪除運算 線性表的刪除運算是指將表中第 i 個元素從線性表中去掉。【算法 2-3】 順序表的刪除算法int Delete_SeqList(SeqList *L,int i) i

7、nt j; if (iL-last+1) /檢查空表及刪除位置的合法性 cout”不存在第i個元素”endl; return 0; /不能刪除，返回錯誤代碼0 for (j=i;jlast;j+) L-dataj-1=L-dataj; /數(shù)據(jù)元素向前移動 L-last-; /last指向新的最后元素 return 1; /刪除成功，返回成功代碼12022年年5月月5日日13刪除算法的時間性能分析 與插入運算相同，其時間主要消耗在了移動表中元素上，刪除第i個元素時，其后面的元素 ai+1an 都要向上移動一個位置，共移動了 n-i 個元素，所以平均移動數(shù)據(jù)元素的次數(shù)：在等概率情況下，pi =1/

8、 n，則： 這說明順序表上作刪除運算時大約需要移動表中一半的元素，顯然該算法的時間復雜度為(n)。 niideinp1)(E11121)(1)(Eniniideninninp2022年年5月月5日日14按值查找 線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。【算法2-4】 順序表的按值查找算法int Location_SeqList(SeqList *L,DataType x) int i; i=0; while (ilast & L-datai!=x) /順序檢查數(shù)據(jù)元素值 i+; if (iL-last) /到最后元素，沒有找到 return -1; /查找不成功，

9、返回錯誤代碼-1 else return i; /查找成功，返回數(shù)據(jù)元素在順序表中的存儲位置 本算法的主要運算是比較。顯然比較的次數(shù)與x在表中的位置有關，也與表長有關。平均比較次數(shù)為（n+1）/2，時間性能為O(n)。2022年年5月月5日日152.2.3 順序表應用舉例 例例2.1 將順序表 (a1，a2，. ，an) 重新排列為以 a1 為界的兩部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大。 劃分的方法有多種，下面介紹的劃分算法其思路簡單，性能較差。 基本思路： 從第二個元素開始到最后一個元素，逐一向后掃描： 當前數(shù)據(jù)元素 aI 比 a1 大時，表明它已經在 a1 的后

10、面，不必改變它與 a1 之間的位置，繼續(xù)比較下一個。 當前結點若比 a1 小，說明它應該在 a1 的前面，此時將它上面的元素都依次向下移動一個位置，然后將它置入最上方。2022年年5月月5日日16總的移動次數(shù)為 ： 即最壞情況下移動數(shù)據(jù)時間性能為()。2)3(*)1()21(22nniinini【算法2-5】 順序表劃分算法void part(SeqList *L) int i,j; DataType x,y; x=L-data0; /將基準數(shù)據(jù)元素置入 x 中 for (i=1;ilast;i+) if (L-dataidatai; for (j=i-1;j=0;j-) /前面所有數(shù)據(jù)元素向

11、后移動 Ldataj+1=L-dataj; L-data0=y; /將當前元素置入最前面位置 2022年年5月月5日日17例例2.2 有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。 算法思路：依次掃描通過A和B的元素，比較當前的元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個線性表相加的長度。2022年年5月月5日日18【算法2-6】有序表的合并算法void merge(SeqList A,SeqList B,SeqList *C) in

12、t i,j,k; /i,j,k分別為順序表A、B、C當前元素指針 i=0; j=0; /i,j分別指向順序表A、B當前待處理元素 k=0; /k指向順序表C帶插入元素位置 while (i=A.last & j=B.last) /依次掃描比較順序表A、B中的數(shù)據(jù)元素 if (A.dataidatak=A.datai; k+; i+; else C-datak=B.dataj; k+;算法的時間性能是O(m+n)，其中m是A的表長，n是B的表長。2022年年5月月5日日19例例2.3 比較兩個線性表的大小。兩個線性表的比較依據(jù)下列方法：設A、B是兩個線性表，均用向量表示，表長分別為m和n

13、。 A和B分別為 A 和 B 中除去最大共同前綴后的子表。 例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，兩表最大共同前綴為 (x,y,y,z) 。則A=（x,z），B=（y,x,x,z），若A= B= 空表，則A=B；若A=空表且B空表，或兩者均不空且A首元素小于B首元素，則AB。 算法思路：首先找出A、B的最大共同前綴；然后求出A和B，之后在按比較規(guī)則進行比較，AB 函數(shù)返回1；A=B返回0；AB返回-1。2022年年5月月5日日20算法的時間性能是O( m+n )。【算法2-7】比較線性表大小算法int compare(int A,int B,int m,

14、int n) int i,j,AS,BS,ms,ns; /AS，BS作為A，B i=0; while (i=m & i=n & Ai=Bi) i+; /找最大共同前綴 ms=ns=0; for (j=i;jm;j+) ASj-i=Aj; ms+; /建立A，ms為A的長度 for (j=i;jx; while (x!=Flag) s=new LNode; s-data=x; s-next=L;2022年年5月月5日日24 在單鏈表的尾部插入結點建立單鏈表【算法2-9】建立單鏈表的算法二#define Flag /Flag為根據(jù)實際情況設定的結束數(shù)據(jù)輸入的標志數(shù)據(jù)LinkList

15、 Creat_LinkList2() LinkList L; LNode *s,*r; int x; /設數(shù)據(jù)元素的類型為int L=r=NULL; cinx; while (x!=Flag) /Flag表示輸入結束 s=new LNode; s-data=x; if (L=NULL) L=s; /第一個結點的處理 else r-next=s; /其他結點的處理2022年年5月月5日日25求表長設L是帶頭結點的單鏈表(線性表的長度不包括頭結點)。【算法2-10】帶頭結點的單鏈表求表長算法int Length_LinkList1(LinkList L)( LNode *p; int i; p=L

16、; /p指向頭結點 i=0; while (p-next) p=p-next; i+; /p指向第 i 個結點 return i;2022年年5月月5日日26 設L是不帶頭結點的單鏈表。【算法2-11】不帶頭結點的單鏈表求表長算法int Length_LinkList2(LinkList L) LNode *p; int i; p=L; i=0; /初始化表長變量為0 while (p) i+; p=p-next; /p指向第 i+1 個結點 return i;2022年年5月月5日日27查找操作按序號查找 Get_Linklist(L,i)算法思路：從鏈表的第一個元素結點起，判斷當前結點是否

17、是第i個，若是，則返回該結點的指針，否則繼續(xù)后一個，表結束為止。沒有第個結點時返回空指針。【算法2-12】按序號查找鏈表數(shù)據(jù)元素算法LNode *Get_LinkList(LinkList L,Int i)/在單鏈表L中查找第i個元素結點，找到返回其指針;否則返回空指針 LNode *p; int j; p=L-next; /p指向第1個數(shù)據(jù)元素結點 j=1; while (p!=NULL & jnext; j+; /p指向第j個數(shù)據(jù)元素結點 return p;2022年年5月月5日日28按值查找即定位 Locate_LinkList(L,x) 算法思路：從鏈表的第一個元素結點起，判斷

18、當前結點值是否等于x，若是，返回該結點的指針，否則繼續(xù)后一個，表結束為止。找不到時返回空指針。【算法2-13】按值查找鏈表數(shù)據(jù)元素算法LNode *Locate_LinkList(LinkList L,DataType x)/在單鏈表L中查找值為x的結點，找到后返回其指針，否則返回空 LNode *p; p=L-next; /p指向第1個數(shù)據(jù)元素結點 while (p!=NULL & p-data!=x) p=p-next; return p;算法2-12、算法2-13的時間復雜度均為O(n)。2022年年5月月5日日29插入操作 后插結點：設p指向單鏈表中某結點，s指向待插入的值為x

19、的新結點，將*s插入到*p的后面。操作如下： s-next=p-next;p-next=s;注意：兩個指針的操作順序不能交換。2022年年5月月5日日30 前插結點：設指向鏈表中某結點，指向待插入的值為x的新結點，將*s插入到*p的前面。與后插不同的是：首先要找到*p的前驅*q，然后再完成在*q之后插入*s，設單鏈表頭指針為L，操作如下：q=L;while (q-next!=p) q=q-next; /*找*p的直接前驅*/s-next=q-next; q-next=s;2022年年5月月5日日31 插入運算 Insert_LinkList(L,i,x)算法思路：1.找到第i-1個結點；若存在

20、繼續(xù)2，否則結束。 2.申請、填裝新結點。 3.將新結點插入，結束。【算法2-14】鏈表的插入算法int Insert_LinkList(LinkList L,int i,DataType x)/在單鏈表L的第i個位置上插入值為x的元素 LNode *p,*s; p=Get_LinkList(L,i-1); /查找第i-1個結點 if (p=NULL) cout”參數(shù)i錯”data=x; 算法2-14的時間復雜度為O(n)。2022年年5月月5日日32刪除操作設p指向單鏈表中某結點，刪除*p。要實現(xiàn)對結點*p的刪除，首先要找到*p的前驅結點*q，然后完成指針的操作即可。指針的操作由下列語句實現(xiàn)

21、： q-next=p-next; free(p);顯然找*p前驅的時間復雜性為O(n)。 若要刪除*p的后繼結點(假設存在)，則可以直接完成： s=p-next; p-next=s-next; free(s);該操作的時間復雜性為O(1) 。2022年年5月月5日日33 刪除運算：Del_LinkList(L,i)算法思路：1.找到第i-1個結點；若存在繼續(xù)2，否則結束。 2.若存在第i個結點則繼續(xù)3，否則結束。 3.刪除第i個結點，結束。【算法2-15】鏈表的刪除運算int Del_LinkList(LinkList L,int i)/刪除單鏈表L上的第i個數(shù)據(jù)結點 LinkList p,s

22、; p=Get_LinkList(L,i-1); /查找第i-1個結點 if (p=NULL) cout”第i-1個結點不存在”next=NULL)算法2-15的時間復雜度為O(n)。2022年年5月月5日日342.3.3 2.3.3 循環(huán)鏈表循環(huán)鏈表 對于單鏈表而言，最后一個結點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結點相連，就構成了單循環(huán)鏈表。 在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。 對于單循環(huán)鏈表則可以從表中任意結點開始遍歷整個鏈表；另外，有時對鏈表常做的操作是在表尾、表頭進行，此時

23、可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結點的指針R來標識，可以使得操作效率提高。2022年年5月月5日日35 例：對兩個單循環(huán)鏈表H1 、H2的連接操作，是將H2的第一個數(shù)據(jù)結點接到H1的尾結點，如用頭指針標識，則需要找到第一個鏈表的尾結點，其時間復雜性為O(n)，而鏈表若用尾指針R、R2來標識，則時間性能為O(1)。操作如下：P= Rnext; /*保存第一個表的頭結點指針*/R-next=R2-next-next; /*頭尾連接*/free(R2-next); /*釋放第二個表的頭結點*/R2-next=P; /*組成循環(huán)鏈表*/2022年年5月月5日日362.3.4 2.3

24、.4 雙向鏈表雙向鏈表 單鏈表的結點中只有一個指向其后繼結點的指針域next，找后繼的時間性能是O(1)，找前驅的時間性能是O(n)；可以付出空間的代價使得找前驅的時間性達到O(1)：每個結點再加一個指向前驅的指針域。用這種結點組成的鏈表稱為雙向鏈表。 雙向鏈表結點的定義如下：typedef struct dlnode datatype data; struct dlnode *prior,*next;DLNode,*DLinkList;2022年年5月月5日日37 和單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以帶頭結點和做成循環(huán)結構。通過某結點的指針p即可以直接得到它的后繼結點的指針p-

25、next，也可以直接得到它的前驅結點的的指針p-prior。這樣在有些操作中需要找前驅時，則勿需再用循環(huán)。 p-prior-next = p= p-next-prior2022年年5月月5日日38 在雙向鏈表中插入一個結點： 設p指向雙向鏈表中某結點，s指向待插入的值為x的新結點，將*s插入到*p的前面。操作如下： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 上面指針操作的順 序不是唯一的，但也 不是任意的，操作必須要放到操作的前面完成，否 則*p的前驅結點的指針就丟掉了。2022年年5月月5日日39在雙向鏈表中刪除指定結點：在雙

26、向鏈表中刪除指定結點： 設p指向雙向鏈表中某結點，刪除*p。操作如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 2022年年5月月5日日402.3.5 靜態(tài)鏈表 首先看一個例子：規(guī)模較大的結構數(shù)組 sdMAXSIZE 中有兩個鏈表：其中鏈表SL是一個帶頭結點的單鏈表，表示了線性表(a1, a2, a3, a4, a5)，而另一個單鏈表AV是將當前 sd 中的空結點組成的鏈表。數(shù)組sd的定義如下： #define MAXSIZE /*足夠大的數(shù)*/ typedef struct datatype data; int next; SN

27、ode; /*結點類型*/ SNode sdMAXSIZE; int SL,AV; /*兩個頭指針變量*/ 2022年年5月月5日日41 在例子中，SL是用戶的線性表，AV模擬的是系統(tǒng)存儲池中空閑結點組成的鏈表，當用戶需要結點時，例如向線性表中插入一個元素，需自己向AV申請，而不能用系統(tǒng)函數(shù)malloc來申請，相關的語句為： if(AV != -1) t=AV; AV=sdAV.next; ；所得到的結點地址(下標)存入了 t 中；不難看出當AV表非空時，摘下了第一個結點給用戶。當用戶不再需要某個結點時，需通過該結點的相對地址 t 將它還給AV，相關語句為： sdt.next=AV; AV=t

28、;交給AV表的結點鏈在了AV的頭部。2022年年5月月5日日42例 在帶頭結點的靜態(tài)鏈表SL的第i個結點之前插入一個值為x的新結點。設靜態(tài)鏈表的存儲區(qū)域sd為全局變量。【算法2-16】靜態(tài)鏈表的插入算法SNode sdMAXSIZE;int Insert_SList(int SL,DataType x,int i) int j; int p,s; p=SL; j=0; while (sdp.next!=-1 & jnext; /p指向第一個數(shù)據(jù)元素結點 H-next=NULL; /將原鏈表置為空表H while (p) q=p; p=p-next; q-next=H-next; /將當

29、前結點插到頭結點的后面 H-next=q;2022年年5月月5日日44例2 已知單鏈表L，寫一算法，刪除其重復結點。算法思路：用指針p指向第一個數(shù)據(jù)元素結點，從它的后繼結點開始到表的結束，查找與其值相同的結點并刪除之；p指向下一個結點；依此類推，p指向最后結點時算法結束。【算法2-18】刪除鏈表中重復結點算法void pur_LinkList(LinkList H) LNode *p,*q,*r; p=H-next; /p指向第一個數(shù)據(jù)元素結點 while (p) q=p; while (q-next) /從p結點的后繼結點開始找重復結點 if (q-next-data=p-data) r=q-next; /找到重復結點，用指針r指向該結點 q-next=r-next; /從鏈表中摘除r結點 delete r; /釋放r結點所占空間2022