【正文】 去，這時，需要在修改指針前保留該結點的后繼結點的地址，即設置一個臨時指針。 典型題解析 算法設計題第二類：基于單鏈表構造的算法設計 有兩種建立單鏈表的算法：頭插法和尾插法。 頭插法 建立單鏈表，由于每次都是將待插結點插在頭結點之后，使得單鏈表中元素的順序和讀入的順序正好相反； 尾插法 建立單鏈表，由于每次都是將待插結點插在終端結點之后，使得單鏈表中元素的順序和讀入的順序正好相同。有時可以利用這個特點完成具有順序相同或相反的操作。 (1) 頭插法建立單鏈表 分析： 頭插法是每次將新申請的結點插在頭結點的后面，只需修改頭結點的指針域和新結點的指針域，因此不用設置工作指針。 頭插法建立單鏈表算法 : LinkedList LinkedListCreat1( ) {//用頭插法建立帶頭結點的單鏈表 LinkedList L。 L=(LNode *)malloc(sizeof(LNode))。 Lnext=NULL。 //初始化一個空鏈表， L為頭指針 scanf(amp。x)。 //x是和鏈表元素具有相同類型的變量 while (x!=flag) //flag為結束輸入的標志 { p=(LNode *)malloc(sizeof(LNode))。 //生成新的結點 pdata=x。 //輸入元素值 pnext=Lnext。 Lnext=p。 /插入到表頭 scanf(amp。x)。 //讀入下一個元素的值 } return L。 } 三個關鍵語句 注意該算法輸入數據的順序和線性表中的數據順序是相反的 教材 .算法 (2) 尾插法建立單鏈表 分析： 尾插法就是每次將新申請的結點插在終端結點的后面，需要設置一個指向尾結點的指針 r，初始時單鏈表為空。 67 r L 23 67 r L 10 23 67 r L 45 10 23 67 r L 36 ∧ 45 10 23 67 r L ∧ L 建立單鏈表－－尾插法 : 尾插法建立單鏈表算法 : LinkedList LinkedListCreat3( ) {//用尾插法建立帶頭結點的單鏈表 LinkedList L。 L=(LNode*)malloc(sizeof(LNode))。//申請頭結點 Lnext=NULL。 r=L。 //初始化，尾指針指向頭結點 scanf(amp。x)。 while (x!=flag) //設置結束標志 { p=(LNode*)malloc(sizeof(LNode)。 //生成新結點 pdata=x。 //插入元素值 rnext=p。 //在尾部插入新結點 r=p。 //r 指向新的尾結點 scanf(amp。x)。 }//while rnext=NULL。 //最后結點的指針域放空指針 return L。 }// LinkedListCreat3 教材 .算法 注意與教材對最后一個結點的不同處理方法 (3). 設計算法實現(xiàn)將單鏈表就地逆置。 分析： 就地逆置的含義是不允許另外申請空間。單鏈表逆置即是將每個結點的指針由指向該結點的后繼改為指向該結點的前驅。 實際上就是從鏈表中摘下一個結點，用 頭插法 插入到鏈表中。 將帶頭結點的單鏈表 就地 逆置 LinkedList Invert(LinkedList head) { ∥ 就地逆置單鏈表 p=headnext。 ∥ p為工作指針，指向第一個元素 headnext=NULL； ∥ 保留第一個元素的指針后，將頭結點的指針域置空 while(p!=NULL) ∥ 將原鏈表的元素按頭插法插入 { r=pnext； ∥ 暫存 p的后繼 pnext=headnext?！?逆置（ 頭插法插入 ） headnext=p； ∥ 頭結點的指針域指向新插入的結點 p=r； ∥ 恢復待處理結點 }//while return（ head）； }∥ Invert 算法中對單鏈表中每個結點只處理一次，其時間復雜度為 O(n)。 教材 . 算法 (4). 復制一個單鏈表。 分析： 本題是建立單鏈表的一個拷貝，所以要依次處理已知單鏈表中的每個結點，對每個結點復制一個新結點并插入到新的單鏈表中。因為是原表的一個副本，要保持原有的順序，所以用 尾插法 。 算法略。 典型題解析 算法設計題第三類：有序單鏈表的算法設計 由于有序鏈表中的數據元素有序排列，因此有序單鏈表的操作要充分利用元素的有序性。有序鏈表的算法通常具有較好的時間性能。 (1) 在一個有序單鏈表（假設從小到大排列）中插入一個元素值為 x的結點，使得插入后單鏈表仍然有序。 分析： 先建立一個待插入結點，然后依次與單鏈表中各結點的數據域比較大小，找到該結點的插入位置，最后插入該結點。 尋找某結點的插入位置有兩種方法： 尋找某結點的插入位置方法 1 ? 設一個工作指針 ? 設置工作指針 p，將待插元素與結點 p的后繼結點的數據域比較，這樣，在找到插入位置后，待插結點正好插在結點 p之后。 有序單鏈表的插入 算法（設一個工作指針） void Insert(LinkedList L, ElemType x ) {//有序單鏈表的插入 s=(LNode *)malloc(sizeof(LNode))。 sdata=x。 //建立數據域為 x的新結點 p=L。 while(pnext amp。amp。 pnextdatax) //尋找插入位置 p=pnext。 snext=pnext。 //新結點插在結點 p之后 pnext=s。 } //Insert 尋找某結點的插入位置方法 2 ? 設兩個工作指針 ? 設置工作指針 pre和 p， pre指向 p的前驅結點，p指向待比較的結點，找到插入位置后，待插結點插在 pre和 p之間。 有序單鏈表的插入 算法（設兩個工作指針） void Insert2(LinkedList L, ElemType x ) {//有序單鏈表的插入 s=(LNode *)malloc(sizeof(LNode))。 sdata=x。 //建立數據域為 x的新結點 pre=L。 p=Lnext。//工作指針 pre和 p初始化 while(p amp。amp。 pdatax) { pre=p。 p=pnext。 //兩個工作指針分別后移 }//while snext=p。 prenext=s。 //新結點插在結點 pre和 p之間 } //Insert2 (2) 在一個 非遞減 有序的線性表中，有數值相同的元素存在。若存儲方式為單鏈表，設計算法去掉數值相同的元素，使表中不再有重復的元素。分析算法的時間復雜度。 分析： 注意到在有序鏈表中值相同的元素一定在連續(xù)的位置，可以從頭到尾掃描一遍單鏈表，若當前結點的元素值與后繼結點的元素值不相等，則指針后移；否則刪除該后繼結點。若單鏈表不是有序的，則需要兩層嵌套循環(huán)。 LinkedList DelSame(LinkedList la) { /*la是非遞減有序的單鏈表，刪除數值相同的元素 */ pre=lanext； ∥ pre是 p所指向的前驅結點的指針 p=prenext； ∥ p是工作指針，設鏈表中至少有一個結點 while（ p!=NULL） if（ pdata==predata） ∥ 處理相同元素值的結點 {u=p； p=pnext； prenext=p； free（ u）； } ∥ 釋放相同元素值的結點 else {pre=p； p=pnext； } ∥ 處理前驅，后繼元素值不同 //prenext=p；應該去掉 }∥ DelSame 算法中對單鏈表中每個結點只處理一次，其時間復雜度為 O(n)。 教材 . 算法 教材錯誤 在鏈表中，刪除數值相同的元素，要知道被刪除元素結點的前驅結點 算法說明 ? 算法中假設鏈表至少有一個結點，即初始時 pre不為空，否則 pnext無意義。 ? 算法中最后一條語句 prenext=p是必須的，因為鏈表最后可能有數據域值相同的結點，這些結點均被刪除，指針后移使 p=NULL而退出 while循環(huán)，所以應有 prenext=p使鏈表有尾。若鏈表尾部沒數據域相同的結點， pre和 p為前驅和后繼， prenext=p也是對的。 void DelSame(LinkedList la) { /*la是非遞減有序的單鏈表，刪除數值相同的元素 */ p=lanext； ∥ 工作指針初始化，刪除與結點 p的值相等的元素 while（ pnext!=NULL） { q=pnext； if (pdata==qdata) { ∥ 相鄰元素比較 pnext=qnext； free (q)； //結點 q的值與結點 p的值相同，刪除結點 q } //if else p=pnext； }//while }∥ DelSame 算法中對單鏈表中每個結點只處理一次，其時間復雜度為 O(n)。 方法 2：該算法中，刪除數值相同的元素，沒有找被刪除元素結點的前驅結點 (3) 已知單鏈表中各結點的元素值為整型且遞增有序，設計算法刪除鏈表中大于 mink且小于 maxk的所有元素，并釋放被刪結點的存儲空間。 分析： 由于單鏈表是有序的，所以大于 mink且小于maxk的所有元素位于單鏈表中連續(xù)的位置，為此，可以查找第一個大于 mink的結點，然后依次刪除小于 maxk的結點。注意刪除結點需要記住被刪結點的前驅結點，因此，設工作指針 p指向第一個大于mink的前驅結點，然后工作指針 p不動，再設工作指針 q指向小于 maxk的結點，注意元素值等于 mink和 maxk的結點不能刪除。 a1 amink amaxk … . … . first p q q 刪除大于 mink且小于 maxk的結點 void DeleteBetween(LinkedList first, int mink, int maxk) { p=first； while（ pnext amp。amp。 pnext data =mink） pnext ； //p指向第一個大于 mink的前驅結點 if (pnext!=NULL) { q=pnext； ∥ 工作指針 p不動，設置另一個工作指針 q while(qdatamaxk) //依次刪除結點 p之后小于 maxk的元素 { u=qnext。 //為避免鏈表斷開暫存后繼結點的地址 pnext=qnext 。 free q。 q=u。 //工作指針 q后移 } //while }//if }∥ DeleteBetween 有序鏈表的連續(xù)刪除算法 典型題解析 算法設計題第四類：多個單鏈表的算法設計 難度較大的算法設計是在多個鏈表上進行處理。這類算法的設計技巧是分別考慮每個單鏈表，一般在每個單鏈表上都要設置工作指針，然后以一個單鏈表為主要鏈表，完成其他處理。 (1) 有兩個整數序列 A=(a1,a2,…… ,am)和B=(b1,b2,…… ,bn)已經存入兩個單鏈表中，設計算法判斷序列 B是否是序列 A的