【文章內容簡介】 rintf(“第 i1個元素不存在 ， 參數(shù) i有錯 \n”)。 else {S=(LinkList *)malloc(sizeof(LinkList))。 Sdata=x。 Snext=Pnext。 Pnext=S。} }/*insertLinkList*/ ? 該算法的時間復雜度為 O(n)。 ?設 P為指向單鏈表中某結點的指針 ， 刪除 P所指結點即 *P的操作示意圖如下圖 。 ?由示意圖可見 ， 要刪除 *P先要找到 *P的前趨結點 *q， 然后完成指針的變化操作即可 。 ?顯然要找到 *P的前趨得有 O(n)的時間開銷 。 在找到 *q的前提下 ， 刪除 *P的操作可由下列語句實現(xiàn)： qnext=Pnext。 free (P)。 刪除（續(xù)） ?若要刪除 P所指結點的后繼結點 （ 假設存在 ） ， 時間開銷為 O(1),直接完成刪除即可： S=Pnext。 Pnext=Snext。 free S。 ? 要刪除單鏈表 L中的第 i個結點 ， 關鍵是先找出第 i1個結點 （ 即前趨結點 ） ， 然后完成刪除并釋放被刪結點空間的工作 。 刪除單鏈表 L中的第 i個結點算法 LinkList *deleteLinkList(L,i) LinkList *L。 int i。 {LinkList *P,*S。 P=getLinkList(L,i1)。/*查找第 i1個結點 */ if(P==NULL) Printf(“第 i1個元素不存在 ， 參數(shù) i 有錯 \n”)。 else {S=Pnext。 Pnext=Snext。 free (S)。} }*deleteLinkList*/ ? 該算法的時間復雜度為 O(n)。 舉例 ——將單鏈表 H逆置 ?所謂 逆置 是指結點間的關系相反 ， 即前趨變后繼而后繼變前趨 。 如圖 (a)的單鏈表逆置后成為圖 (b)的單鏈表 。 ?算法思路 ：依次從原鏈表中取出每個結點 ， 每次都把它作為第一個結點插入到新鏈表中去 。 為此要借用兩個指針變量 P和q， P用來指向原鏈表中的當前第一個結點 ， q用來指向從原表取出的每一個結點并利用它插入到新鏈表中去 ， 當 P為空時完成逆置 。 將單鏈表 H逆置的算法描述 void reverse(H) LinkList *H。 {LinkList *P,*q。 P=Hnext。 Hnext=NULL。 while(P!=NULL) {q=P。 P=Pnext。 qnext=Hnext。 Hnext=q。} }*reverse*/ ?該算法沒有開辟新的存儲空間 ， 對鏈表順序掃描一遍就完成了逆置 ， 時間開銷為 O(n)。 鏈表 線性表的鏈式存儲結構 ——鏈表 單鏈表上的基本運算 循環(huán)鏈表和雙向鏈表 線性表應用舉例 —— 一元多項式相加問題 循環(huán)鏈表 ?循環(huán)鏈表 （ Circular Linked List） 是鏈式存儲結構的另一種形式 ， 其特點是表中最后一個結點的指針域指向頭結點 ， 使整個鏈表構成一個環(huán) ， 可以從表中任一結點出發(fā)訪問遍所有結點 （ 即遍歷 ） 。 ?單循環(huán)鏈表的空表和非空表兩種狀態(tài)如下圖所示： ?單循環(huán)鏈表上的基本運算與單鏈表基本一致 ， 差別僅在于對最后一個結點的循環(huán)處理上；單鏈表是判斷指針是否為空 （ NULL） ， 而單循環(huán)鏈表是判斷指針是否指向頭結點 。 求循環(huán)鏈表的表長算法描述 int Lengthcircularlist(L) LinkList *L。 {LinkList *P。 int j=0。 P=L。 While(Pnext!=L) /*與求單鏈表表長差別僅在于把 NULL換為頭指針 L*/ {P=Pnext。 j++。} return j。 }/*Lengthcircularlist*/ 循環(huán)鏈表（續(xù)） ?有時對鏈表常做的操作是在表尾和表頭進行 。 ?為了找尾結點必須從頭結點開始掃描全部結點 ， 時間開銷為 O(n)；而找頭結點僅 O(1)時間 。 ?改進的方法是不設頭指針而設尾指針 。 這樣找到頭結點和尾結點都只需要 O(1)的時間 ， 頭結點為(*(*r).next).next而尾結點為 r， 對于在鏈表的頭尾操作的應用十分方便 。 ?帶尾指針的循環(huán)鏈表 如下圖所示： 雙向鏈表 ?在單循環(huán)鏈表中 ， 雖然可以從任一已知結點出發(fā)找到其前趨結點 ， 但需耗時 O(n)， 原因在于每個結點只有一個指向后繼的指針域 。 ?如果希望能夠快速確定任一結點的前趨 ， 就必須付出空間代價 ， 即增加一個指針域存儲其前趨信息 ， 這樣每個結點就有兩個方向不同的鏈 ， 稱之為 雙向鏈表 （ double linked list） 。 ?如果讓每條鏈都構成一個環(huán) ， 則稱為 雙向循環(huán)鏈表（ double circular linked list） 。 ?雙向鏈表的使用往往做成雙循環(huán)鏈表 ， 和單循環(huán)鏈表類似 ， 也是由頭指針標識 ， 也可以增加頭結點方便運算 。 雙向鏈表的結點定義和類型 typedef struct dupnode {elemtype data。 struct dupnode *prior,*next。 }dulinklist。 dulinklist *H。 ?雙向鏈表是一種對稱結構 ， 每個結點都既有指向其前趨的指針 ， 也有指向其后繼的指針；每個結點的地址既放在其后繼結點的前趨域中 ， 也放在其前趨結點的后繼域中 。 即有 Pnextprior=P=Ppriornext 雙向鏈表示意圖 雙向鏈表插入運算 ?與單鏈表相比雙向鏈表的運算要方便得多 。 然而由于要涉及多指針域的運算 ， 對于某些運算要注意運算的先后順序 。 在 *P之前插入 *S的步驟為： ① Ppriornext=s。 ② Sprior=Pprior。 ③ Snext=P。 ④ Pprior=S。 ?盡管上面的指針操作順序不是惟一的 ， 但是也不能任意次序 ， 必須保證操作 ② 在操作 ④ 之前完成 ， 否則 *P的前趨域的信息就丟掉了 ， 導致不能正確地插入 *S。 雙向鏈表插入運算的示意圖 ① ② ③ ④ 雙向鏈表的刪除運算 ?刪除 P所指結點 （ 即 *P） 的操作步驟為： ① Ppriornext=Pnext。 ② Pnextprior=Pprior。 ③ free (P)。 ?在雙向鏈表中刪除一個結點的運算如下圖所示： ① ② 鏈表 線性表的鏈式存儲結構 ——鏈表 單鏈表上的基本運算 循環(huán)鏈表和雙向鏈表 線性表應用舉例 —— 一元多項式相加問題 一元多項式 ?一個一元多項式可以表示為 P(x)=a0+a1x+a2x2+… +anxn ?其中： a0,a1,a2,… ,an這 n+1個系數(shù)惟一確定了多項式 ， 而每一項的指數(shù)隱含在系數(shù) ai的序號中 ， 所以一元多項式可以由線性表 （ a0,a1,… ,an） 來表示 。 ?設 A=(a0,a1,… ,an )， B=(b0,b1,… ,bm)， 則多項式加法就是求 A+B=C。 ?其中： C=(a0+b0,a1+b1,… ,am+bm,am+1,… ,an) 或 C=（ a0+b0,a1+b1,… ， an+bn,bn+1,… ,bm） 。 一元多項式在計算機中的表示 ?如何在計算機中表示描述多項式的線性表呢 ？ 我們首先考慮用順序表 （ 即順序存儲結構 ） 。 ?如果只存儲系數(shù)讓指數(shù)隱含在系數(shù)序號中 ， 則會浪費存儲空間 ， 如 T(x)=3+5x200+7x1000的線性表長度為 1001， 而其中僅有三個非零元素 ， 故應當避免 。 ?解決的辦法是對每一非零項用 （ 系數(shù) ， 指數(shù) ） 二元組 ， T(x)只需存儲 （ 3， 0） ， （ 5， 200） 和 （ 7， 1000） 三個有序對 ，顯然對高階稀疏多項式這種方法較好 。 ?順序存儲便于訪問 ， 但插入刪除需大量移動元素 ， 所以對只需求多項式的值無需修改系數(shù)和指數(shù)值的情況下 ， 采用順序表結構較好 。 一元多項式的數(shù)據(jù)類型定義 ?如果是多項式的運算問題如相加和相乘等 ， 考慮到會產生新的項和系數(shù)為零項減少這兩種情況 ， 宜考慮采用鏈式存儲結構即單鏈表實現(xiàn) 。 ?其數(shù)據(jù)類型可如下定義： typedef struct linknode {float coef。 int exp。 struct linknode *next。 }polynomial。 多項式的鏈式存儲表示示例 ?假設使用頭結點 ， 前述的 T(X)= 3+5x200+7x1000可表示為如下圖所示的結構： 多項式相加算法的思路 ?不產生新結點而利用原有結點空間 ， 設兩個指針變量 p和 q分別指向 A和 B兩個多項式單鏈表的第一個結點 ， 依次比較兩指針所指結點的指數(shù)項 。 ?若指數(shù)相等系數(shù)相加 ， 和不為零修改 *p的系數(shù)項并刪除 *q， 和為零刪除 *p和 *q； ?若指數(shù)不等 ， pexpqexp時 *p為和多項式中的一項 ， pexpqexp時把 *q插在 *p之前 （ *q為和多項式中的一項 ） ； ?所有操作之后要相應移動指針 。 直到其中一個鏈空 ，把另一個鏈剩下的結點插在 *p之后 。 多項式相加算法的描述 void polyadd(A,B) polynomial *A,*B。 {polynomial *p,*q,*s,*r。 float x。 p=Anext。 q=Bnext。 s=A。 while((p!=NULL)amp。amp。(q!=NULL)) if((pexp)(qexp)) {r=qnext。 qnext=p。 /*把 p接在 q所指結點后 */ snext=q。 /*把 q接入結果鏈 */ s=q。 q=r。} else if(pexpqexp) {s=p。 p=pnext。 } 多項式相加算法的描述（續(xù)） else {x=pcoef+qcoef。 if(x!=0) {pcoef=x。 s=p。 } else {snext=pnext。 free(p)。} p=snext。 r=q。 q=qnext。 free(r)。} if(q!=NULL) snext=q。 /*把 q鏈剩余結點鏈入結果鏈 */ free(B)。 }/* polyadd*/ ?該算法的比較次數(shù)與 A、 B兩個多項式的長度 m和 n有關 ， 算法的時間復雜度為 O(m+n)。 第 3章 簡單數(shù)據(jù)結構 順序表 鏈表 棧 隊列 廣義表 棧 棧的概念及運算 順序棧及運算實現(xiàn) 鏈棧及運算實現(xiàn) 棧的應用舉例 ——遞歸的實現(xiàn) 棧的概念 ?棧 （ stack） 是操作受限的線性表 ， 限定對元素的插入和刪除運算只能在表的一端進行 。 ?通常把進行插入和刪除操作的這一端稱作 棧頂（ top） ， 另一端稱作 棧底 （ bottom） ； ?把棧的插入元素操作稱作 進棧 、 入棧 或 壓入 ； ?棧的刪除元素操作稱作 退棧 、 出棧 或 彈出 ； ?當棧中沒有元素時稱作 空棧 。 棧的概念（續(xù)） ?由棧的定義可知 ， 每一次 入棧 的元素都在原棧頂元素之上成為新的棧頂元素 ， 每一次 出棧 的元素總是當前棧頂元素使次棧頂元素成為新的棧頂元素 ， 即最后進棧的元素總是最先出棧 。 所以棧也稱作 后