【正文】 d DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p。 /*找到表 LA的表尾 */ while (qnext!=LB) q=qnext。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。r=pb。 LCnext=NULL； r=LC。要求：利用新表 LC利用現(xiàn)有的表 LA和 LB中的元素結(jié)點(diǎn)空間，而不需要額外申請(qǐng)結(jié)點(diǎn)空間。 int ListLength(LinkList L) /*L為帶頭結(jié)點(diǎn)的 單鏈表 */ { Node *p。amp。 /*為 e申請(qǐng)一個(gè)新的結(jié)點(diǎn) */ sdata=e。 pre=L。 單鏈表查找 2022/8/26 37 按值查找算法實(shí)現(xiàn) / * 在帶頭結(jié)點(diǎn)的單鏈表 L中查找其結(jié)點(diǎn)值等于 key的結(jié)點(diǎn) ， 若找到則返回該結(jié)點(diǎn)的位置 p， 否則返回 NULL * / Node *Locate( LinkList L,ElemType key) { Node *p。 } } } 2022/8/26 34 單鏈表查找 ? 按序號(hào)查找 算法描述： 設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為 n，要查找表中第 i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針 L出發(fā)，從頭結(jié)點(diǎn)（ Lnext）開始順著鏈域掃描，用指針 p指向當(dāng)前掃描到的結(jié)點(diǎn) ,初值指向頭結(jié)點(diǎn)（ pLnext），用j做記數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)（初值為 0），當(dāng) j = i 時(shí)，指針 p所指的結(jié)點(diǎn)就是要找的第 i個(gè)結(jié)點(diǎn) 。 r=L。 snext=Lnext。 ? 帶頭結(jié)點(diǎn)的空單鏈表 ? 帶頭結(jié)點(diǎn)的單鏈表 ∧ H a1 a2 … H an ∧ 2022/8/26 28 單鏈表的存儲(chǔ)結(jié)構(gòu)描述 typedef struct Node / * 結(jié)點(diǎn)類型定義 * / { ElemType data； struct Node * next； }Node, *LinkList； /* LinkList為結(jié)構(gòu) 指針類型 */ 2022/8/26 29 單鏈表上的基本運(yùn)算 ? 線性表的基本運(yùn)算 ： 1. 建立單鏈表 2. 單鏈表查找 3. 單鏈表插入操作 4. 單鏈表刪除 ? 算法應(yīng)用示例： 1. 求單鏈表的長(zhǎng)度 2. 求兩個(gè)集合的差 2022/8/26 30 建立單鏈表 ? 頭插法建表 算法描述： 從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。 i++。amp。 /*將后面的元素依次前移 */ Llast。 } 算法演示 （ 此處連接算法演示程序 ） 。 if( (i1) || (iLlast+2) ) /*首先判斷插入位置是否合法 */ { printf(“插入位置 i值不合法 ” )； return(ERROR)。amp。 操作結(jié)果：將表 L置為空表。 線性表的邏輯結(jié)構(gòu)圖為： 2022/8/26 5 線性表的特點(diǎn) ?同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè) ai必須屬于同一數(shù)據(jù)對(duì)象。 數(shù)據(jù)元素之間是一對(duì)一的關(guān)系 ， 即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼 。 （ 3） ClearList(L) 操作前提：線性表 L已存在 。 /*i為掃描計(jì)數(shù)器 ， 初值為 0， 即從第一個(gè)元素開始比較 */ while ((i=)amp。則需要將第 9個(gè)位置到第 4個(gè)位置的元素依次后移一個(gè)位置，然后將 “ 21”插入到第 4個(gè)位置， 序號(hào) 移動(dòng)元素 插入元素 1 2 3 4 5 6 7 8 10 9 4 9 15 28 30 30 42 51 62 4 9 15 28 30 30 42 62 51 4 9 15 21 28 30 30 42 62 51 2022/8/26 16 插入運(yùn)算 int InsList(SeqList *L,int i,ElemType e) { int k。 return(OK)。k++) Lelem[k1]= Lelem[k]。 while(i=LAlastamp。 } while(i=LAlast) /*當(dāng)表 LA長(zhǎng)則將表 LA余下的元素賦給表 LC*/ { LCelem[k]= LAelem[i]。 缺點(diǎn)： ，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低； ，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配。 2022/8/26 26 單鏈表的示例圖 頭指針 H 存儲(chǔ)地址 數(shù)據(jù)域 指針域 1 D 43 7 B 13 13 C 1 19 H NULL 25 F 37 31 A 7 37 G 19 43 E 25 31 2022/8/26 27 帶頭結(jié)點(diǎn)的單鏈表示意圖 有時(shí)為了操作的方便，還可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)。 sdata=c。/*為頭結(jié)點(diǎn)分配存儲(chǔ)空間 */ Lnext=NULL。 rnext=NULL。 算法實(shí)現(xiàn) ，算法演示。 */ Node *pre,*s。 } s=(Node*)malloc(sizeof(Node))。 while(pnext!=NULLamp。 /*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間 */ } 2022/8/26 42 求單鏈表的長(zhǎng)度 算法描述： 可以采用 “ 數(shù) ” 結(jié)點(diǎn)的方法來求出單鏈表的長(zhǎng)度，用指針 p依次指向各個(gè)結(jié)點(diǎn) ,從第一個(gè)元素開始 “ 數(shù) ” ，一直 “ 數(shù) ” 到最后一個(gè)結(jié)點(diǎn)（ pnext=NULL）。 2022/8/26 43 兩個(gè)有序單鏈表的合并 ? 有兩個(gè)單鏈表 LA和 LB，其元素均為非遞減有序排列，編寫一個(gè)算法，將它們合并成一個(gè)單鏈表 LC，要求 LC也是非遞減有序排列。 LC=LA。} else {rnext=pb。 特點(diǎn) ：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由 NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。 while (pnext!=LA) p=pnext。 雙向鏈表的 結(jié)構(gòu)定義： typedef struct Dnode { ElemType data； struct DNode *prior， *next； } DNode, * DoubleList； 2022/8/26 52 雙鏈表的結(jié)構(gòu)定義 ? 雙鏈表的結(jié)點(diǎn)結(jié)構(gòu) 后繼指針域 prior data next 前驅(qū)指針域 數(shù)據(jù)域 2022/8/26 53 雙向循環(huán)鏈表示意圖 a1 a2 a3 L L 空的雙向循環(huán)鏈表 非空的雙向循環(huán)鏈表 2022/8/26 54 雙向鏈表的前插操作 ? 算法描述： 欲在雙向鏈表第 i個(gè)結(jié)點(diǎn)之前插入一個(gè)的新的結(jié)點(diǎn)，則指針的變化情況如圖所示。 return TRUE。 free(p)。 ? 基本操作： 初始化 、 分配結(jié)點(diǎn)與結(jié)點(diǎn)回收 、 前插操作 、 刪除 。kMaxsize1。 *av=k。適合存儲(chǔ)表示非零項(xiàng)少的多項(xiàng)式。 int c,e。rearnext=s 。 算法實(shí)現(xiàn) ， 算法演示 – 若 pexp qexp， 則結(jié)點(diǎn) p所指的結(jié)點(diǎn)應(yīng) 是 “ 和多項(xiàng)式 ” 中的一項(xiàng) ， 令指針 p后移； – 若 pexpqexp， 則結(jié)點(diǎn) q所指的結(jié)點(diǎn)應(yīng)是 “ 和多項(xiàng)式 ” 中的一項(xiàng) ， 將結(jié)點(diǎn) q插入在結(jié)點(diǎn) p之前 ， 且令指針 q在原來的鏈表上后移； – 若 pexp=qexp， 則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加 ， 當(dāng)和不為零時(shí)修改結(jié)點(diǎn) p的系數(shù)域 ， 釋放 q結(jié)點(diǎn)；若和為零 ， 則和多項(xiàng)式中無此項(xiàng) ， 從 A中刪去 p結(jié)點(diǎn) ， 同時(shí)釋放 p和 q結(jié)點(diǎn) 。當(dāng)表長(zhǎng)度變化時(shí)僅需適當(dāng)變化指針的聯(lián)接，適合于表中元素個(gè)數(shù)動(dòng)態(tài)變化。 2022/8/26 78 【 算法描述 】 AdjustSqlist(SeqList *L) /* {int i=0,j=Llast。若對(duì)順序表中的元素進(jìn)行逆置，可以借助于“ 交換 ” 前后相應(yīng)元素；對(duì)單鏈表中的元素進(jìn)行逆置，則不能按 “ 交換 ” 思路，因?yàn)閷?duì)于鏈表中第 i個(gè)結(jié)點(diǎn)需要順鏈查找第 ni+1(鏈表長(zhǎng)度為 n)個(gè)結(jié)點(diǎn)，逆置鏈表的時(shí)間復(fù)雜度將達(dá) O（ n2）。 Lnext=p。④若在鏈表中未找到值域?yàn)?0的結(jié)點(diǎn)，則表示該二進(jìn)制數(shù)各位均為 1，此時(shí)，申請(qǐng)一新結(jié)點(diǎn)，值域?yàn)?1，插入到頭結(jié)點(diǎn)與原鏈表的第一個(gè)結(jié)點(diǎn)之間，成為新鏈表的第一個(gè)結(jié)點(diǎn)，其后所有結(jié)點(diǎn)的值域賦為 0。 s=(Node*)malloc(sizeof(Node))。 } }/*BinAdd結(jié)束 */