【正文】 LL） { if （ pexp qexp） { … /*將 p結(jié)點加入到和多項式中 */} else if ( pexp= =qexp） { … /*若指數(shù)相等 ， 則相應(yīng)的系數(shù)相加 。 若系數(shù)為 0則刪除 p， q節(jié)點 */} else{ … /*將 q結(jié)點加入到和多項式中 */} } … ../*將多項式 polya或 polyb中剩余的結(jié)點加入到和多項式中 */ } 2022/8/26 72 順序表和鏈表的比較 ? 1．基于空間的考慮 ? 2．基于時間的考慮 ? 3．基于語言的考慮 2022/8/26 73 線性表鏈?zhǔn)酱鎯Ψ绞降谋容^ 操作名稱 鏈表名稱 找表頭結(jié)點 找表尾結(jié)點 找 P結(jié)點前驅(qū)結(jié)點 帶頭結(jié)點單鏈表 L Lnext 時間耗費 O(1) 一重循環(huán) 時間耗費 O(n) 順 P結(jié)點的 next域無法找到 P結(jié)點的前驅(qū) 帶頭結(jié)點循環(huán)單鏈表（頭指針） L Lnext 時間耗費 O(1) 一重循環(huán) 時間耗費 O(n) 順 P結(jié)點的 next域可以找到 P結(jié)點的前驅(qū) 時間耗費 O(n) 帶尾指針的循環(huán)單鏈表 R Rnext O(1) R 時間耗費 O(1) 順 P結(jié)點的 next域可以找到 P結(jié)點的前驅(qū) 時間耗費 O(n) 帶頭結(jié)點雙向循環(huán)鏈表 L Lnext O(1) Lprior 時間耗費 O(1) Pprior 時間耗費 O(1) 2022/8/26 74 總結(jié)與提高 ? 主要知識點 ? 線性表的特征 ：線性表中每個數(shù)據(jù)元素有且僅有一個直接前驅(qū)和一個直接后繼，第一個結(jié)點無前驅(qū)，最后一個結(jié)點無后繼。 ? 線性表存儲方式 ： – 線性表順序存儲（順序表）：采用靜態(tài)分配方式，借助于 C語言的數(shù)組類型，申請一組連續(xù)的地址空間，依次存放表中元素，其邏輯次序隱含在存儲順序之中。 2022/8/26 75 總結(jié)與提高 – 線性表鏈?zhǔn)酱鎯Γㄦ湵恚翰捎脛討B(tài)分配方式，借助于 C語言的指針類型，動態(tài)申請與動態(tài)釋放地址空間，故鏈表中的各結(jié)點的物理存儲可以是不連續(xù)的。當(dāng)表長度變化時僅需適當(dāng)變化指針的聯(lián)接，適合于表中元素個數(shù)動態(tài)變化。 ? 單鏈表的操作特點 ： – ⑴順鏈操作技術(shù) – ⑵指針保留技術(shù) ? 鏈表處理中的相關(guān)技術(shù) 2022/8/26 76 典型題例 ? 例 1： 已知順序表 L中的數(shù)據(jù)元素類型為 int。設(shè)計算法將其調(diào)整為左右兩部分，左邊的元素（即排在前面的）均為奇數(shù)，右邊所有元素（即排在后面的）均為偶數(shù)，并要求算法的時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O（ 1）。 2022/8/26 77 例 1【 問題分析 】 ? 初見此題，可能會想到額外申請 1個順序表空間，之后依次從順序表 L中選擇奇數(shù)放入新表前部分，選擇偶數(shù)放在新表的后半部分。但是題目要求空間復(fù)雜度為 O(1),很顯然上述方法是不可行的。既然要求空間復(fù)雜度為O(1)，說明只能借助 1個輔助空間。分析題目要求，其實我們只需要將位于表左半部分的偶數(shù)與位于表右半部分的奇數(shù)通過一個輔助變量進(jìn)行交換即可，為此我們可以設(shè)置兩個位置指示器 i和 j,i初值為 0， j初值為 Llast,當(dāng)Lelem[i]為偶數(shù)， Lelem[j]為奇數(shù)時，則將 Lelem[i] 與 Lelem[j]交換；否則， Lelem[i]為奇數(shù) ,i++, Lelem[j]為偶數(shù)， j++。這樣既可以保證算法的時間復(fù)雜度為 O(n),亦可保證空間復(fù)雜度為 O（ 1）。 2022/8/26 78 【 算法描述 】 AdjustSqlist(SeqList *L) /* {int i=0,j=Llast。 while(ij) { while(Lelem[i]%2!=0) i++。 /*從表的左半部分開始檢測，若為奇數(shù)，則 i加 1,直到找到偶數(shù)為止*/ while(Lelem[j]%2= =0) j； /* 從表的右半部分開始檢測，若為偶數(shù)，則 j減 1,直到找到奇數(shù)為止 */ if(ij) {t= Lelem[i]。 Lelem[i]= Lelem[j]。 Lelem[j]=t。}/*交換 */ } }/*end of AdjustSqlist*/ 2022/8/26 79 ? 例 2：算法實現(xiàn)帶頭結(jié)點單鏈表的就地逆置問題。 ? 【 問題分析 】 逆置就是使得表中內(nèi)容由原來的（ a1,a2,… ， ai1， ai， ai+1， … ， an）變?yōu)椋?an,an1,… ， ai+1， ai， ai1， … ， a1）。就地逆置就是不需要額外申請結(jié)點空間，只需要利用原有的表中的節(jié)點空間。若對順序表中的元素進(jìn)行逆置，可以借助于“ 交換 ” 前后相應(yīng)元素；對單鏈表中的元素進(jìn)行逆置，則不能按 “ 交換 ” 思路，因為對于鏈表中第 i個結(jié)點需要順鏈查找第 ni+1(鏈表長度為 n)個結(jié)點，逆置鏈表的時間復(fù)雜度將達(dá) O（ n2）。 2022/8/26 80 ? 算法思路： 逆置后的單鏈表初始為空，表中的結(jié)點不是新生成的，而是從原鏈表中依次 “ 刪除 ” ，再逐個頭插入到逆置表中（類同算法 ）。設(shè)逆置鏈表的初態(tài)為空表， “ 刪除 ” 已知鏈表中的第一個結(jié)點，然后將它 “ 插入 ” 到逆置鏈表的 “ 表頭 ” ，即使它成為逆置鏈表中 “ 新 ” 的第一個結(jié)點，如此循環(huán)，直至原鏈表為空表止。 ? 根據(jù)單鏈表的特點，通過頭指針 L我們可以順著每個結(jié)點的 next域，依次訪問到 a1,a2,a3… an1,an； 2）我們可以借鑒前面講到過的頭插入法建鏈表的方法，因為頭插入法建鏈表又稱為逆序建表法 3）唯一不同的是，我們不需要重新申請結(jié)點空間，而只需要從原有單鏈表上依次 “ 摘下 ” 結(jié)點，之后插入到單鏈表頭結(jié)點和表中第一個結(jié)點之間即可。如圖所示 2022/8/26 81 … a1 … an ∧ a2 ai (a)初始狀態(tài) L p為原鏈表當(dāng)前處理結(jié)點 斷開 Lnext, 使逆置表初始為空表 (b)將單鏈表 L初始為空表 … a1 … an ∧ a2 ai ∧ L p q q指向原鏈表當(dāng)前處理結(jié)點的下一個 p ① ai a2 a1 ∧ L … … an ∧ a3 q (c)將 p指向的結(jié)點插入到逆置表 L的表頭 ② 2022/8/26 82 例 2【 算法描述 】 void ReverseList(LinkList L) /*逆置帶頭結(jié)點的單鏈表 L */ { p=Lnext。 /* P為原鏈表的當(dāng)前處理結(jié)點 */ Lnext=NULL。 /*逆置單鏈表初始為空表 */ while(p!=NULL) /*當(dāng)原鏈表未處理完 */ { q=pnext。 /*q指針保留原鏈表當(dāng)前處理結(jié)點的下一個結(jié)點 */ pnext=Lnext。 Lnext=p。 /*將當(dāng)前處理結(jié)點 p插入到逆置表 L的表頭 */ p=q。 /*p指向下一個待插入的結(jié)點 */ } /*end of while*/ }/*end of ReverstList*/ 【 思考 】 已知一個帶頭結(jié)點的單鏈表 L，設(shè)計算法實現(xiàn)：以表中第一個元素作為標(biāo)準(zhǔn)，將單鏈表中所有值小于第一個元素的結(jié)點均放在第一個元素結(jié)點之前，所有值大于第一個元素的結(jié)點均放在第一個元素結(jié)點之后。（提示：此題可以利用頭插法） 2022/8/26 83 ? 例 建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個結(jié)點的 data域存放一個二進(jìn)制位。并在此鏈表上實現(xiàn)對二進(jìn)制數(shù)加 1的運算 。 ? 【 問題分析 】 – ① 建鏈表 ：帶二進(jìn)制數(shù)可用帶頭結(jié)點的單鏈表存儲，第一個結(jié)點存儲二進(jìn)制數(shù)的最高位，依次存儲，最后一個結(jié)點存儲二進(jìn)制數(shù)的最低位。 – ②二進(jìn)制加法規(guī)則 ：實現(xiàn)二進(jìn)制數(shù)加 1運算，方向從低位往高位找到第一個值為 0的位，從該位開始，對后面所有低位進(jìn)行求反運算。③鏈表實現(xiàn)二進(jìn)制加 1時，從高位往低位與運算方向正好相反，從第一個結(jié)點開始找，找出最后一個值域為 0的結(jié)點，把該結(jié)點值域賦為 1，其后所有結(jié)點的值域賦為 0。④若在鏈表中未找到值域為 0的結(jié)點，則表示該二進(jìn)制數(shù)各位均為 1，此時，申請一新結(jié)點，值域為 1，插入到頭結(jié)點與原鏈表的第一個結(jié)點之間，成為新鏈表的第一個結(jié)點，其后所有結(jié)點的值域賦為 0。 2022/8/26 84 【 算法描述 】 void BinAdd(LinkList l) /*用帶頭結(jié)點的單鏈表 L存儲二進(jìn)制數(shù)，實現(xiàn)加 1運算 */ { Node *q,*r,*temp,*s。 q=lnext。 r=l。 while(q!=NULL) /*查找最后一個值域為 0的結(jié)點 */ {if(qdata == 0) r = q。 q = qnext。 } 2022/8/26 85 if (r != l) rdata = 1。 /*將最后一個值域為 0的結(jié)點的值域賦為 1*/ else /*未找到值域為 0的結(jié)點 */ { temp = rnext。 s=(Node*)malloc(sizeof(Node))。 /*申請新結(jié)點 */ sdata=1。 /*值域賦為 1*/ snext=temp。 rnext = s。 /*插入到頭結(jié)點之后 */ r = s。 } r = rnext。 while(r!=NULL) /*將后面的所有結(jié)點的值域賦為 0*/ {rdata = 0。 r = rnext。 } }/*BinAdd結(jié)束 */