第2章線性表算法總結.ppt

1、線性表算法總結,例一：簡述線性表的兩種存儲結構的主要優(yōu)缺點及各自適用的場合。,【解答】 順序存儲可以按位置直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作是將引起元素移動，降低了效率；鏈式存儲元素存儲采用動態(tài)分配，利用率高，但需增設表示結點之間有序關系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結點的插入、刪除操作十分簡單。 順序存儲適用于線性表中元素數(shù)量基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素的情況；而鏈式存儲適用于頻繁進行元素的動態(tài) 插入或刪除操作的場合。,【分析】 線性表的兩種主要存儲結構各有其優(yōu)點和缺點，不能簡單地說哪個好哪個差，要根據(jù)實際問題和其適用的場

2、合使用。,1.順序存儲結構,例二：刪除有序表中相同的數(shù)據(jù)元素,void Delete_Equale(SqList La) i=0;j=1； while (jLa.length) if (La.elemi!=La.elemj) i=i+1; La.elemi=La.elemj; j=j+1; La.length=i+ ,分析:順序表中每刪除一個數(shù)據(jù)元素,被刪元素后的元素都要依次向前移動一個位置, 浪費大量的時間. 可以每做一次刪除,只做標記,最后一次將剩余元素移動到位 試做此算法懶惰刪除 另給出一巧妙算法,2.鏈式存儲結構,例二：刪除有序表中相同的數(shù)據(jù)元素,void Delete_Equale(

3、LinkList L) pre=L-next;p=pre-next； while (p!=NULL) if (pre-data!=p-data) pre=p;p=p-next; else u=p; p=p-next; pre-next=p; free(u); ,1.順序存儲結構,例三：線性表的就地逆置,void reverse(SqList LA)/使用兩個控制變量 ElemType t; for(i=0,j=LA.length-1;ij;i+,j-) t=LA.elemi; LA.elemi= LA.elemj; LA.elemj=t; ,void reverse(SqList ,a1,a2

4、,a3,L,p,a1,a2,a3,思路一：,1）標志后繼結點； 2）修改指針（將*p插入在頭結點之后）； 3）重置結點*p（p重新指向原表中后繼）；,2.鏈式存儲結構,（1）帶頭結點單鏈表,void inverse(LinkList L) / 逆置帶頭結點的單鏈表 L p=L-next; L-next=NULL; while ( p) succ=p-next; / succ指向*p的后繼 p-next=L-next; L-next=p; / *p插入在頭結點之后 p = succ; ,void inverse(LinkList L) p=L-next; pre=NULL; while ( p)

5、 succ=p-next; / succ指向*p的后繼 p-next=pre; pre=p; p = succ; L-next=pre; ,思考：不帶頭結點單鏈表逆置？帶頭結點單循環(huán)鏈表逆置,思路二:直接修改結點的指針域,指向原來鏈表上其直接前驅結點,1）void inverse(LinkList L) /思路直接逆置 / 逆置不帶頭結點的單鏈表 L p= NULL; /p記錄剛逆置的結點 q=L;/q記錄將要逆置的結點 while ( q!=NULL) L=L-next; q-next=p; p = q; q = L; L=p; ,（2）不帶頭結點單鏈表,2) p=L-next;L-next

6、=NULL; while ( p!=NULL) r=p-next; p-next=L; L=p; p=r; /思路同上，細節(jié)不同,3)先加頭結點，逆置后再刪除,void inverse(LinkList L) / 逆置帶頭結點的單循環(huán)鏈表L p=L-next; L-next=L; while (p!=L) r=p-next; p-next=L-next; L-next=p; p=r; ,（3）帶頭結點單循環(huán)鏈表,void inverse(LinkList ,（4）不帶頭結點單循環(huán)鏈表,分析：應先找到第i-1個結點，記下第i個結點，然后從第i+1個結點開始直至第m個結點，依次插入到第i-1個結點

7、之后，最后將暫存的第i個結點的指針指向原第m個結點（即倒置后第i-1個結點的后繼）。,（5）已知L為鏈表的頭結點地址，表中共有m個結點(m3)，從表中第i個結點起到第m個結點構成一個循環(huán)部分鏈表，設計將這部分循環(huán)鏈表中所有結點順序完全倒置的算法。,void ParrernInvert(LinkList /原第i個結點指向原第m個結點 ,分析：本題也是模式匹配問題，應先找出鏈表L2在鏈表L1中的出現(xiàn)位置，然后再將L1中的L2倒置。設L2在L1中出現(xiàn)時第一個字母結點的前驅的指針為p，最后一個字母結點在L1中為q所指結點的前驅，則在保存p后繼結點指針s的情況下，執(zhí)行p-next=q，之后再將s到q結

8、點的前驅依次插入到p結點之后。,（6）L1與L2分別為兩單鏈表頭結點地址指針，且兩表中數(shù)據(jù)結點的數(shù)據(jù)域均為一個字母。設計把L1中與L2中數(shù)據(jù)相同的連續(xù)結點順序完全逆置的算法。,void ParrernInvert(LinkList else printf(“L2并不存在于L1中”)； ,思考： 1）L2在L1中出現(xiàn)多次時？ 2）統(tǒng)計L2在L1中出現(xiàn)的次數(shù),有序順序表的合并 教材p26 另 void union(SqList LA, SqList LB, SqList LC) i=0; j=0; k=0; while(iLA.length ,1.順序存儲結構,例四：線性表的合并,1.順序存儲結構

9、,例四：線性表的合并,順序結構線性表LA與LB的結點關鍵字為整數(shù)。 LA與LB的元素按非遞減有序，線性表空間足夠大。試給出一高效算法，將LB種元素合并到LA中，使新的LA的元素仍保持非遞減有序。高效是指最大限度地避免移動元素。,分析：順序存儲結構的線性表的插入、刪除，其時間復雜度為O(n)，平均移動近一半的元素。兩表合并時，若從第一個元素開始，一定會造成元素后移，這不符合題目要求。題中敘述“線性表空間足夠大”暗示出另外的合并方式，即應從線性表的最后一個元素開始比較，較大者放到最終位置上。,void union(SqList LA,SqList LB) m=LA.length; n=LB.len

10、gth; k=m+n; i=m-1; j=n-1; while(i=0 ,2.鏈式存儲結構（1）,例四：線性表的合并,void MergeList_L(LinkList /MergeList_L,利用歸并思想,該算法去掉if/else即可表示題集2.23交叉合并兩線性表; 該題結合逆置思想即可表示2.24(合并為一個非遞增有序鏈表),2.鏈式存儲結構（2）,例四：線性表的合并,void MergeList_L(LinkList /MergeList_L,2.鏈式存儲結構（3）,例四：線性表的合并,已知L1、L2分別為兩單鏈表的頭結點指針，m、n分別為L1、L2表中數(shù)據(jù)結點個數(shù)。要求設計一算法，

11、用最快速度將兩表合并成一個帶頭結點的單鏈表。,LinkList Union(LinkList L1,LinkList L2) if (mnext=NULL) p=p-next; p-next=L2-next; L2-next=L1-next; free(L2);return(L1); elseif(n=0) return(L1); else p=L2; while(p-next!=NULL) p=p-next; p-next=L1-next; L1-next=L2-next; free(L1); return(L2); ,題目要求“用最快速度將兩表合并”，因此應找結點個數(shù)少的鏈表查找其尾結點,

12、2.鏈式存儲結構（4）,例四：線性表的合并,編寫算法實現(xiàn)連接線性表la和lb（lb在后）的算法，要求其時間復雜度為O(1)，占用輔助空間盡量小。描述所用結構。,應使用只設尾指針的單循環(huán)鏈表 LinkList Union(LinkList la,LinkList lb) /不帶頭結點 q=la-next; la-next=lb-next; lb-next=q; return(lb); ,LinkList Union(LinkList la,LinkList lb) /帶頭結點 q=lb-next; lb-next=la-next; la-next=q-next; free(q); return(

13、lb); ,2.鏈式存儲結構（5）,例四：線性表的合并,設有兩個鏈表，ha為單鏈表，hb為單循環(huán)鏈表。編寫算法，將兩個鏈表合并成一個單鏈表，要求算法所需時間與鏈表長度無關。,應使用只設尾指針的單循環(huán)鏈表 LinkList Union(LinkList ha,LinkList hb) /不帶頭結點 q=hb-next; hb-next=ha; ha=q; return(ha); ,LinkList Union(LinkList ha,LinkList hb) /帶頭結點 q=hb-next; hb-next=ha-next; ha-next=q-next; free(q); return(hb)

14、; ,順序存儲的線性表A，其數(shù)據(jù)元素為整型，試編寫算法，將A拆成B和C兩個表，使A中元素值大于等于0的元素放入B，小于0的元素放入C，要求：1）表B和C另外設置存儲空間； 2）表B和C不另外設置存儲空間； 山東大學 2001 九 1(12分),例五：線性表的拆分,1）void rearray(int A ,int ,1.順序存儲結構,int rearray(SqList A) i=0; j=A.length-1; t=a0; while(i=0) j-; if (ij) A.elemi= A.elemj;i+; while (ij A.elemi0 ? return (i+1) : retur

15、n i ,2）表B和C不另外設置存儲空間； 分析:實現(xiàn)算法可以重排具有n個元的順序表,使得所有值為負數(shù)的元素移動到正數(shù)元素的前面.采用快速排序的思想來實現(xiàn),只是提出暫存的第一個元素(樞軸)并不作為比較標準,比較標準是 0,1）編寫函數(shù)將一整數(shù)序列(順序表)中的所有負數(shù)移到所有正數(shù)之前，要求時間復雜度為O(n)?！緰|北大學 1998 南航2001】 2）設有一元素為整數(shù)的線性表L=a1,a2,an 存放在一維數(shù)組AN中，設計一算法，以表中an為參考元素，將該表分為左右兩部分，左部分小于等于an ，右部分大于an， an在分界線上?！颈本├砉ご髮W 1999年 八（6分】 3）已知線性表a1,a2,

16、an按順序存儲，且每個元素都是不相等的整數(shù)，設計把所有奇數(shù)移到所有偶數(shù)前邊的算法（時間最少，空間最?。?【東北大學 1997 】,類似描述：,設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B，C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A的元素類型為整型，要求B，C表利用A表的結點）。 【北京理工大學 2000】,例五：線性表的拆分,分析：題目中鏈表帶頭結點,分解后的兩個鏈表不要求數(shù)值有序, 要求利用原表空間,采用方法: 將新結點插到頭結點之后.,2.鏈式存儲結構（1）,void DisCreat(LinkList A) B=A; C=(LN

17、ode *) malloc(sizeof(LNode); C-next=NULL; p=A-next; /p為工作指針 B-next=NULL; while (p!=NULL) succ=p-next; /暫存p的后繼 if (p-datanext=B-next;B-next=p; else if (p-data0) p-next=C-next;C-next=p; elseu=p;p=p-next;free(u); p=succ; ,例五：線性表的拆分,已知L為不帶頭結點的單鏈表中的一個結點的指針，每個結點數(shù)據(jù)域存放一個字符，該字符可能是英文字母或數(shù)字或其它字符，編寫算法構造三個以帶頭結點的單

18、循環(huán)鏈表表示的線性表，使每個表中只含同一類字符（要求用最小的空間和最少的時間）,例五：線性表的拆分,分析：將一個表拆成三個帶頭結點的表，應先構造三個表頭結點，然后從原鏈表第一個結點開始一個個結點進行判斷和鏈接，注意不要因結點插入新鏈表而使原鏈表斷鏈。,2.鏈式存儲結構（2）,void onetothree(LinkList ,例五：線性表的拆分,else if (r-data=o ,例五：線性表的拆分,設計一算法，將不帶頭結點的單鏈表L中的結點分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由P、Q指向，每個鏈中的數(shù)據(jù)按由小到大排列，算法中不得申請新的結點空間。,例五：線性表的拆分,分析：將一個表拆成兩個表，

19、兩個表都要有序，不能申請空間，這就要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。,2.鏈式存儲結構（3）,void split(LinkList /鏈入結點 ,例五：線性表的拆分,else if (Q=NULL) Q=s;Q-next=NULL;/第一個奇數(shù)結點 elsepre=Q; if (pre-datas-data) /比第一個小，修改頭指針 s-next=pre;Q=s; else while(pre-next!=NULL)/查找插入位置 if (pre-next-datadata) pre=pre-next; s-next=pre-next; pre-next=s;/鏈入結點

20、 s=r; ,例五：線性表的拆分,將一個帶頭結點的單鏈表A分解為兩個帶頭結點的單鏈表A和B，使得A表中含有原表中序號為奇數(shù)的元素，而B表中含有原表中序號為偶數(shù)的元素，且保持其相對位置不變。,例五：線性表的拆分,分析：因為要將序號是奇數(shù)的元素和序號是偶數(shù)的元素分開，因此要有計數(shù)器用來區(qū)分序號的奇偶數(shù)；由于分解后兩表中元素結點的相對位置不變，故采用在鏈表尾插入比較方便，這使用一指向表尾的指針即可方便實現(xiàn)。,2.鏈式存儲結構（4）,void Discreat(LinkList ,例五：線性表的拆分,例六：集合的并、交、差運算,分析：本題實質上是兩個鏈表的合并操作，與前面講過的并運算不同的是遞增有序，即不允許有相同元素，因此兩表合并時，如有相等的元素，則應刪除一個。,1.并 已知遞增有序的兩個單鏈表A、B分別存儲了一個集合。設計算法實現(xiàn)兩個集合的并運算,例六：集合的并、交、差運算,LinkList Union(Lin