【正文】 st Lc, LinkList La, LinkList Lb ， int (*pare) (ElemType,ElemType))) { // 歸并有序表 La 和 Lb ,生成新的有序表 Lc, // 并在歸并之后銷毀 La 和 Lb, // pare 為指定的元素大小判定函數(shù) …… } // MergeList_L 例二 if ( !InitList(Lc)) return ERROR。 // 存儲(chǔ)空間分配失敗 while (!( a=MAXC b=MAXC)) { // La 或 Lb 非空 } … … LocatePos (La, 0)。 LocatePos (Lb, 0)。 // 當(dāng)前指針指向頭結(jié)點(diǎn) if ( DelAfter( La, e)) a = e。 // 取得 La 表中第一個(gè)元素 a else a = MAXC。 // MAXC為常量最大值 if ( DelFirst( Lb, e)) b = e。 // 取得 Lb 表中第一個(gè)元素 b else b = MAXC。 // a 和 b 為兩表中當(dāng)前比較元素 DestroyList(La)。 DestroyList(Lb)。 // 銷毀鏈表 La 和 Lb return OK。 if ((*pare)(a, b) =0) { // a≤b InsAfter(Lc, a)。 if ( DelAfter( La, e1) ) a = e1。 else a = MAXC。 } else { // a＞ b InsAfter(Lc, b)。 if ( DelAfter( Lb, e1) ) b = e1。 else b = MAXC。 } 1. 雙向鏈表 typedef struct DuLNode { ElemType data。 // 數(shù)據(jù)域 struct DuLNode *prior。 // 指向前驅(qū)的指針域 struct DuLNode *next。 // 指向后繼的指針域 } DuLNode, *DuLinkList。 五、其它形式的鏈表 最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表 a1 a2 … ... a n 和單鏈表的差別僅在于， 判別 鏈表中最后一個(gè)結(jié)點(diǎn)的 條件 不再是“后繼是否為空”，而是 “后繼是否為頭結(jié)點(diǎn)” 。 2. 循環(huán)鏈表 雙向循環(huán)鏈表 空表 非空表 a1 a2 … ... a n 雙向鏈表的操作特點(diǎn)： “ 查詢” 和單鏈表相同 “插入” 和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。 ai1 ai e snext = pnext。 pnext = s。 snextprior = s。 sprior = p。 p s 插入 ai1 刪除 ai ai+1 pnext = pnextnext。 pnextprior = p。 p ADT Ordered_List { 數(shù)據(jù)對(duì)象 : S = { xi|xi ? OrderedSet ， i=1,2,…,n, n ≥0 } 集合中 任意兩個(gè) 元素之間 均可以 進(jìn)行比較 數(shù)據(jù)關(guān)系 :R = {xi1, xi | xi1, xi ? S, xi1≤ xi, i=2,3,…,n } 回顧例 22的兩個(gè)算法 六、有序表類型 基本操作： … … … … LocateElem( L, e, q, int(*pare)(ElemType,ElemType) ) 初始條件 ：有序表 L已存在。 操作結(jié)果 ：若有序表 L中存在元素 e，則 q指示 L中 第一個(gè)值為 e 的元素 的位置 ，并返回函數(shù)值 TRUE；否則 q 指示 第一個(gè)大于 e 的元素的前驅(qū) 的位置 ，并返回函數(shù)值FALSE。 Compare是一個(gè)有序判定函數(shù) ( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 ) 例如 : 若 e = 45, 則 q 指向 若 e = 88, 則 q 指向 表示值為 88 的元素應(yīng)插入在該指針?biāo)附Y(jié)點(diǎn)之后。 void union(List La, List Lb) {// Lb 為線性表 InitList(La)。 // 構(gòu)造 (空的 )線性表 LA La_len=ListLength(La)。 Lb_len=ListLength(Lb)。 for (i = 1。 i = Lb_len。 i++) { GetElem(Lb, i, e)。 // 取 Lb中第 i 個(gè)數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( )) ) ListInsert(La, ++La_len, e)。 // La中不存在和 e 相同的數(shù)據(jù)元素，則插入之 } } // union 算法時(shí)間復(fù)雜度： O(n2) void purge(List La, List Lb) { // Lb為有序表 InitList(LA)。 La_len = ListLength(La)。 Lb_len =ListLength(Lb)。 // 求線性表的長(zhǎng)度 for (i = 1。 i = Lb_len。 i++) { } } // purge GetElem(Lb, i, e)。 // 取 Lb中第 i個(gè)數(shù)據(jù)元素賦給 e if (ListEmpty(La) || !equal (en, e)) { ListInsert(La, ++La_len, e)。 en = e。 } // La中不存在和 e 相同的數(shù)據(jù)元素，則插入之 算法時(shí)間復(fù)雜度： O(n) nnn xpxpxppxp ????? ...)(2210在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示 : P = (p0, p1, … ， pn) 但是對(duì)于形如 S(x) = 1 + 3x10000 – 2x20230 的多項(xiàng)式，上述表示方法是否合適？ 一元多項(xiàng)式 一般情況下的 一元稀疏多項(xiàng)式 可寫(xiě)成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中 ： pi 是指數(shù)為 ei 的項(xiàng)的非零系數(shù) ， 0≤ e1 e2 ┄ em = n 可以下列線性表表示： （（ p1, e1） , (p2, e2), ┄ , (pm,em) ） P999(x) = 7x3 2x12 8x999 例如 : 可用線性表 ( (7, 3), (2, 12), (8, 999) ) 表示 ADT Polynomial { 數(shù)據(jù)對(duì)象 ： 數(shù)據(jù)關(guān)系 ： 抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下： D＝ { ai | ai ∈ TermSet, i=1,2,...,m, m≥0 TermSet 中的 每個(gè)元素包含一個(gè) 表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) } R1＝ { ai1 ,ai |ai1 ,ai∈ D, i=2,...,n 且 ai1中的指數(shù)值 ＜ ai中的指數(shù)值 } CreatPolyn ( P, m ) DestroyPolyn ( P ) PrintPolyn ( P ) 基本操作 ： 操作結(jié)果 ： 輸入 m 項(xiàng)的系數(shù)和指數(shù)， 建立一元多項(xiàng)式 P。 初始條件 ： 一元多項(xiàng)式 P 已存在 。 操作結(jié)果 ： 銷毀一元多項(xiàng)式 P。 初始條件 ： 一元多項(xiàng)式 P 已存在 。 操作結(jié)果 ： 打印輸出一元多項(xiàng)式 P。 PolynLength( P ) AddPolyn ( Pa, Pb ) SubtractPolyn ( Pa, Pb ) … … } ADT Polynomial 初始條件 ： 一元多項(xiàng)式 P 已存在 。 操作結(jié)果 ： 返回一元多項(xiàng)式 P 中的項(xiàng)數(shù) 。 初始條件 ： 一元多項(xiàng)式 Pa 和 Pb 已存在 。 操作結(jié)果 ： 完成多項(xiàng)式相加運(yùn)算，即： Pa = Pa＋ Pb，并銷毀一元多項(xiàng)式 Pb。 一元多項(xiàng)式的實(shí)現(xiàn)： typedef struct { // 項(xiàng) 的表示 float coef。 // 系數(shù) int expn。 // 指數(shù) } term, ElemType。 typedef OrderedLinkList polynomial。 // 用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式 結(jié)點(diǎn)的數(shù)據(jù)元素類型定義為 : Status CreatPolyn ( polynomail P, int m ) { // 輸入 m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表 P } // CreatPolyn InitList (P)。 = 。 = 1。 SetCurElem (h, e)。 // 設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素 for ( i=1。 i=m。 ++i ) { // 依次輸入 m 個(gè)非零項(xiàng) } return OK。 scanf (, )。 if (!LocateElem ( P, e, (*cmp)()) ) if ( !InsAfter ( P, e ) ) return ERROR。 注意 : 。 Status AddPolyn ( polynomial Pc, polynomial Pa, polynomial Pb) { // 利用兩個(gè)多項(xiàng)式的結(jié)點(diǎn)構(gòu)成“和多項(xiàng)式” Pc = Pa＋Pb … … if (DelAfter(Pa, e1)) a= else a=MAXE。 if (DelAfter(Pb, e2)) b= else b=MAXE。 while (!(a=MAXE b=MAXE)) { … … } … … } // AddPolyn switch (*cmp(e1, e2)) { case 1: { // 多項(xiàng)式 PA中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 … … break 。 } case 0: { // 兩者的指數(shù)值相等 = + 。 if ( != ) InsAfter(Pc, e1)。 … … break 。 } case 1: { //多項(xiàng)式 PB中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 … … break 。 } } 本章小結(jié) 存在著線性關(guān)系 ， 在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 用前者表示的線性表簡(jiǎn)稱為順序表 ，用后者表示的線性表簡(jiǎn)稱為鏈表 。 ，以及線性表的各種基本操作的實(shí)現(xiàn)。 表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。 演講完畢，謝謝觀看！