【正文】 h … 2022年 1月 4日星期二 第 98頁 r 空表 設(shè)置尾指針的循環(huán)鏈表 設(shè)置尾指針的循環(huán)鏈表，在對兩個單循環(huán)鏈表進(jìn)行連接使可以提高效率。 r2 b1 bn r1 a1 an r1next=r2nextnext。 r2next=p。 r … p p=r1next。 2022年 1月 4日星期二 第 99頁 單鏈表具有單向性的缺點，找前驅(qū)不方便！ ? 結(jié)點定義 typedef struct dupnode { elemtype data。 struct dupnode *prior,*next。 }duplinklist。 prior data next L 空雙向循環(huán)鏈表： 非空雙向循環(huán)鏈表： L A B b c a p ppriornext= p= pnextproir。 雙向鏈表（ double linked list） 2022年 1月 4日星期二 第 100頁 雙向鏈表的操作特點： “ 查詢” 和單鏈表相同。 “ 插入” 和“刪除”時需要同時修改兩個方向上的指針。 2022年 1月 4日星期二 第 101頁 void ins_dlinklist(duplinklist * p,int x) {duplinklist *s。 s=(duplinklist *)malloc(sizeof(duplinklist ))。 sdata=x。 sprior=pprior。 ppriornext=s。 snext=p。 pprior=s。 } –算法描述 – 算法評價： T(n)=O(1) x S b a P ? 插入 ppriornext=s。 sprior=pprior。 snext=p。 pprior=s。 2022年 1月 4日星期二 第 103頁 b c a P void del_dlinklist(duplinklist *p) { ppriornext=pnext。 pnextprior=pprior。 free(p)。 } ? 刪除 – 算法描述 – 算法評價： T(n)=O(1) ppriornext=pnext。 pnextprior=pprior。 2022年 1月 4日星期二 第 105頁 用上述定義的單鏈表實現(xiàn)線性表的操作時， 存在的 問題 ： 改進(jìn)鏈表的設(shè)置 ? 1．單鏈表的表長是一個隱含的值； 1．增加“表長”、“表尾指針” 和 “當(dāng)前位置的 指針” 三個數(shù)據(jù)域； 2．在單鏈表的最后一個元素之后插入元素時， 需遍歷整個鏈表； 3．在鏈表中，元素的“位序”概念淡化，結(jié)點的 “位置”概念加強。 2．將基本操作中的 “位序 i ”改變?yōu)?“指針 p ”。 2022年 1月 4日星期二 第 106頁 一個帶頭結(jié)點的線性鏈表類型 typedef struct node { // 結(jié)點類型 ElemType data。 struct node *next。 } Link。 typedef struct { // 鏈表類型 Link * head, *tail。 // 分別指向頭結(jié)點和 //最后一個結(jié)點的指針 int len。 // 指示鏈表長度 Link* current。 // 指向當(dāng)前被訪問的結(jié)點 //的指針，初始位置指向頭結(jié)點 } LinkList。 2022年 1月 4日星期二 第 107頁 2022年 1月 4日星期二 第 108頁 nnn xpxpxppxp ????? .. .)(2210在計算機中，可以用一個線性表來表示 : P = (p0, p1, … ， pn) 一元多項式 但是對于形如 S(x) = 1 + 3x10000 – 2x20220 的多項式，上述表示方法是否合適？ 2022年 1月 4日星期二 第 109頁 一般情況下的 一元稀疏多項式 可寫成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中 ： pi 是指數(shù)為 ei 的項的非零系數(shù) ， 0≤ e1 e2 ┄ em = n 可以下列線性表表示： （（ p1, e1） , (p2, e2), ┄ , (pm,em) ） 2022年 1月 4日星期二 第 110頁 P999(x) = 7x3 2x12 8x999 例如 : 可用線性表 ( (7, 3), (2, 12), (8, 999) ) 表示 2022年 1月 4日星期二 第 111頁 一元多項式相加 ? 采用非零系數(shù)單鏈表 ? 一元多項式 A(x)和 B(x)。和為 C(x)，不另外申請空間 ? P,q分別指向 A(x)和 B(x)中待相加的結(jié)點 ? 分情況進(jìn)行討論： ? expqexp ,則 p為結(jié)點 C(x)的一項，移動 p ? 2. pexpqexp,則 q結(jié)點插入到 p結(jié)點之前，移動 q ? 3. pexp=qexp,則，系數(shù)相加，釋放 q結(jié)點 2022年 1月 4日星期二 一元多項式的數(shù)據(jù)類型定義 ?如果是多項式的運算問題如相加和相乘等 ， 考慮到會產(chǎn)生新的項和系數(shù)為零項減少這兩種情況 ， 宜考慮采用鏈?zhǔn)酱鎯Y(jié)構(gòu)即單鏈表實現(xiàn) 。 ?其數(shù)據(jù)類型可如下定義： typedef struct linknode {float coef。 int exp。 struct linknode *next。 }polynomial。 2022年 1月 4日星期二 多項式的鏈?zhǔn)酱鎯Ρ硎臼纠? ?假設(shè)使用頭結(jié)點 ， 前述的 T(X)= 3+5x200+7x1000可表示為如下圖所示的結(jié)構(gòu)： 2022年 1月 4日星期二 多項式相加算法的思路 ?不產(chǎn)生新結(jié)點而利用原有結(jié)點空間 ， 設(shè)兩個指針變量 p和 q分別指向 A和 B兩個多項式單鏈表的第一個結(jié)點 ， 依次比較兩指針?biāo)附Y(jié)點的指數(shù)項 。 ?若指數(shù)相等系數(shù)相加 ， 和不為零修改 *p的系數(shù)項并刪除 *q， 和為零刪除 *p和 *q； ?若指數(shù)不等 ， pexpqexp時 *p為和多項式中的一項 ， pexpqexp時把 *q插在 *p之前 （ *q為和多項式中的一項 ） ； ?所有操作之后要相應(yīng)移動指針 。 直到其中一個鏈空 ，把另一個鏈?zhǔn)Ｏ碌慕Y(jié)點插在 *p之后 。 2022年 1月 4日星期二 多項式相加算法的描述 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所指結(jié)點后 */ snext=q。 /*把 q接入結(jié)果鏈 */ s=q。 q=r。} else if(pexpqexp) {s=p。 p=pnext。 } 2022年 1月 4日星期二 多項式相加算法的描述（續(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鏈?zhǔn)Ｓ嘟Y(jié)點鏈入結(jié)果鏈 */ free(B)。 }/* polyadd*/ ?該算法的比較次數(shù)與 A、 B兩個多項式的長度 m和 n有關(guān) ， 算法的時間復(fù)雜度為 O(m+n)。 2022年 1月 4日星期二 第 117頁 在這一章我們向大家介紹了線性表的抽象數(shù)據(jù)類型的定義以及它的兩種存儲結(jié)構(gòu)的實現(xiàn) 。 線性表是 n(n≥0) 個數(shù)據(jù)元素的序列 ， 通常寫成 (a1 ,a2 , … an, ) 因此線性表中除了第一個和最后一個元素之外都只有一個前驅(qū)和一個后繼 。 線性表中每個元素都有自己確定的位置 ， 即 位序 ， 因此線性表也可以看成是由 n 個 (i,) 構(gòu)成的集合 。 n=0時的線性表稱為 空表 ， 它是線性表的一種特殊狀態(tài) ， 因此在寫線性表的操作算法時一定要考慮你的算法對空表的情況是否也正確 。 順序表 是線性表的順序存儲結(jié)構(gòu)的一種別稱 。 它的特點是以 存儲位置相鄰 表示兩個元素之間的前驅(qū)后繼關(guān)系 。 因此 ， 順序表的優(yōu)點是可以 隨機存取 表中任意一個元素 ， 其缺點是每作一次插入或刪除操作時 ， 平均來說必須移動表中一半元素 。 常應(yīng)用于主要是為 查詢而很少作插入和刪除操作 ， 表長變化不大的線性表 。 【 本章小結(jié) 】 2022年 1月 4日星期二 第 118頁 鏈表 是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的別稱 。 它的特點是以 指針 指示后繼元素 ， 因此線性表的元素可以存儲在存儲器中任意一組存儲單元中 。 它的 優(yōu)點是便于進(jìn)行插入和刪除操作 ， 但 不能進(jìn)行隨機存取 ， 每個元素的存儲位置都存放在其前驅(qū)元素的指針域中 ， 為取得表中任意一個數(shù)據(jù)元素都必須從第一個數(shù)據(jù)元素起查詢 。 由于它是一種動態(tài)分配的結(jié)構(gòu) ， 結(jié)點的存儲空間可以隨用隨取 ， 并在刪除結(jié)點時隨時釋放 ， 以便 系統(tǒng)資源更有效地被利用 。 這對編制大型軟件非常重要 ， 作為一個程序員在編制程序時必須養(yǎng)成這種習(xí)慣 。 由于線性表是一種應(yīng)用很廣的數(shù)據(jù)結(jié)構(gòu)，鏈表的操作又很靈活，因此在 C++等面向?qū)ο蟮某绦蛟O(shè)計語言中都已為程序員提供了鏈表類，讀者在使用時應(yīng)該首先充分了解它的操作接口。在自己實現(xiàn)鏈表類時，正如課程中所述，應(yīng)該為鏈表結(jié)構(gòu)設(shè)置合適的數(shù)據(jù)成員和恰當(dāng)?shù)牟僮鹘涌?，以便使每個基本操作的時間復(fù)雜度在盡可能低的級別上。 2022年 1月 4日星期二 第 119頁