【正文】 List。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 建立稀疏矩陣的十字鏈表算法： CreateCrossList (CrossList * M) {//采用十字鏈表存儲(chǔ)結(jié)構(gòu) ， 創(chuàng)建稀疏矩陣 M if(M!=NULL) free(M)。 scanf(amp。m,amp。n,amp。t)。 //輸入 M的行數(shù) ,列數(shù)和非零元素的個(gè)數(shù) Mm=m。Mn=n。Mlen=t。 If(!(Mrow_head=(Olink*)malloc((m+1)sizeof(OLink)))) exit(OVERFLOW)。 If(!(Mcol_head=(OLink * )malloc((n+1)sizeof(OLink)))) exit(OVERFLOW)。 Mrow_head[ ]=Mcol_head[ ]=NULL。 //初始化行 、 列頭指針向量 ， 各行 、 列鏈表為空的鏈表 for(scanf(amp。i,amp。j,amp。e)。i!=0。 scanf(amp。i,amp。j,amp。e)) {if(!(p=(OLNode *) malloc(sizeof(OLNode)))) exit(OVERFLOW)。 prow=i。pcol=j。pvalue=e。 //生成結(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 if(Mrow_head[i]==NULL) Mrow_head[i]=p。 else{ /*尋找行表中的插入位置 */ for(q=Mrow_head[i]。 qrightamp。amp。qrightcolj。 q=qright) pright=qright。 qright=p。 /*完成插入 */ } if(Mcol_head[j]==NULL) Mcol_head[j]=p。 else{ /*尋找列表中的插入位置 */ for(q=Mcol_head[j]。 qdownamp。amp。qdownrowi。 q=qdown) pdown=qdown。 qdown=p。 /*完成插入 */ } } } 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 兩個(gè)矩陣相加的算法描述： (1) 初始令 pa和 pb分別指向 A和 B的第一行的第一個(gè)非零 元素的結(jié)點(diǎn)，即 pa＝ [1]。 pb＝ [1]。 pre = NULL。 且令 hl初始化 for (j=1。 j=。 ++j) hl[j] ＝ [j]。 (2) 重復(fù)本步驟，依次處理本行結(jié)點(diǎn)，直到 B的本行中 無非零元素的結(jié)點(diǎn)，即 pb==NULL為止： ① 若 pa==NULL或 paj〉 pbj（即 A的這一行中非零 元素已處理完），則需在 A中插入一個(gè) pb所指 結(jié)點(diǎn)的復(fù)制結(jié)點(diǎn)。假設(shè)新結(jié)點(diǎn)的地址為 p，則 A的行表 中的指針作如下變化： if pre == NULL rhead[pi]=p。 else { preright＝ p。 } pright＝ pa。 pre = p。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 A的列鏈表中的指針也要作相應(yīng)的改變。首先需從 hl[pj] 開始找到新結(jié)點(diǎn)在同一列中的前驅(qū)結(jié)點(diǎn)，并讓 hl[pj]指 向它，然后在列鏈表中插入新結(jié)點(diǎn)： if chead[pj] == NULL { chead[pj] = p。 pdown = NULL。 } else { pdown＝ hl[pj]down。 hl[pj]down＝ p。 } hl[pj] = p。 ② 若 paj〈 pbj且 paj!=0，則令 pa指向本行下一個(gè) 非零元結(jié)點(diǎn)，即 pre＝ pa。 pa＝ paright。 ③ 若 paj == pbj，則將 B中當(dāng)前結(jié)點(diǎn)的值加到 A中當(dāng) 前結(jié)點(diǎn)上，即 pae＋＝ pbe。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 此時(shí)若 pae!=0，則指針不變，否則刪除 A中該結(jié)點(diǎn)，即行表 中指針變?yōu)椋? if pre == NULL rhead[pai] = paright。 else { preright＝ paright。 } p=pa。 pa=paright。 同時(shí)，為了改變列表中的指針，需要先找到同一列中的前驅(qū) 結(jié)點(diǎn)，且讓 hl[paj]指向該結(jié)點(diǎn)，然后如下修改相應(yīng)指針： if chead[pj] == p chead[pj] = hl[pj] = pdown。 else { hl[pj]down＝ pdown。 } free (p)。 (3) 若本行不是最后一行，則令 pa和 pb指向下一行的第一個(gè) 非零元結(jié)點(diǎn)，轉(zhuǎn) (2)；否則結(jié)束。 此算法時(shí)間復(fù)雜度： O(ta+tb) ▲ 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表 （又稱 列表 Lists） 是 n≥0 個(gè)元素 a0, a1, …, an1 的有限序列，其中每一個(gè) ai 或者是 原子 ，或者是一個(gè) 子表 。 廣義表的定義 例： 中國(guó)舉辦的國(guó)際足球邀請(qǐng)賽，參賽隊(duì)名單可表示如下： （ 阿根廷，巴西，德國(guó)，法國(guó)， （ ） ，西班牙， 意大利，英國(guó)， （ 國(guó)家隊(duì)，魯能，實(shí)德 ）） 在這個(gè)表中，韓國(guó)隊(duì)?wèi)?yīng)排在法國(guó)隊(duì)后面，但由于其水平低 未敢參加，成為空表。國(guó)家隊(duì)、魯能隊(duì)、實(shí)德隊(duì)均作為東道主 的參賽隊(duì)參加，構(gòu)成一個(gè)小的線性表，成為原線性表的一個(gè)數(shù) 據(jù)元素。這種 拓寬了的線性表就是廣義表 。 單個(gè)元素 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表 通常記作： LS = (a1， a2， … ， an) 其中： LS 為表名， n 為表的長(zhǎng)度， 每一個(gè) ai 為表的元素。 習(xí)慣上，一般用 大寫字母 表示 廣義表 ， 小寫字母 表示 原子 。 表頭 ： 若 LS 非空 (n≥1 )，則其 第一個(gè) 元素 a1 就是表頭。 記作 head(LS) = a1。 注： 表頭可以是原子，也可以是子表。 表尾 ： 除表頭之外的 其它元素 組成的 表 。 記作 tail(LS) = (a2, ..., an)。 注： 表尾不是最后一個(gè)元素，而是一個(gè)子表。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 (1) A=( ) 例： 空表，長(zhǎng)度為 0。 (2) B=(( )) (3) C=(a, (b, c)) 長(zhǎng)度為 1， 表頭 、 表尾均為 ( )。 長(zhǎng)度為 2， 由原子 a 和子表 (b, c) 構(gòu)成 。 (4) D=(x, y, z) 表頭為 a ；表尾為 ((b, c))。 長(zhǎng)度為 3， 每一項(xiàng)都是原子 。 (5) E=(C, D) 表頭為 x ；表尾為 (y, z)。 (6) F=(a, F) 長(zhǎng)度為 2，每一項(xiàng)都是子表。 表頭為 C ；表尾為 (D)。 長(zhǎng)度為 2，第一項(xiàng)為原子，第二項(xiàng)為它本身。 F=(a, (a, (a, …))) 表頭為 a ；表尾為 (F)。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表的性質(zhì) (1) 廣義表中的數(shù)據(jù)元素有相對(duì) 次序 ； (2) 廣義表的 長(zhǎng)度 定義為最外層所包含元素的個(gè)數(shù)； 如： C=(a, (b, c)) 是長(zhǎng)度為 2 的廣義表。 (3) 廣義表的 深度 定義為該廣義表 展開后 所含 括號(hào)的重?cái)?shù) ； A = (b, c) 的深度為 1， B = (A, d) 的深度為 2， C = (f, B, h) 的 深度為 3。 注意： “原子”的深度為 0 。 ―空表”的深度為 1 。 (4) 廣 義表可以為其他廣義表 共享 ；如：廣義表 B 就共享表 A。 在 B 中不必列出 A 的值，而是通過名稱來引用。 (5) 廣義表可以是一個(gè) 遞歸 的表。如： F=(a, F)=(a, (a, (a, …))) 注意： 遞歸表的深度是無窮值，長(zhǎng)度是有限值 。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 (6) 廣義表是 多層次 結(jié)構(gòu)，廣義表的元素可以是單元素，也可以 是子表，而子表的元素還可以是子表， … 。 可以用圖形象地表示。 例： D=(E, F) 其中 ： E=(a, (b, c)) F=(d, (e)) D a d b c e E F 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表 可以看成 是線性表的推廣 ， 線性表是廣義表的特例 。 廣義表的結(jié)構(gòu)相當(dāng)靈活，在某種前提下，它可以兼容線性 表、數(shù)組、樹和有向圖等各種常用的數(shù)據(jù)結(jié)構(gòu)。 當(dāng) 二維數(shù)組的每行（或每列）作為子表處理時(shí)，二維數(shù)組 即為一個(gè)廣義表。 另外，樹和有向圖也可以用廣義表來表示。 由于廣義表不僅集中了線性表、數(shù)組、樹和有向圖等常見 數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可有效地利用存儲(chǔ)空間，因此在計(jì)算機(jī) 的許多應(yīng)用領(lǐng)域都有成功使用廣義表的實(shí)例。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 取表頭運(yùn)算 GetHead 和取表尾運(yùn)算 GetTail 若廣義表 LS=(a1, a2, … , an)， 則 GetHead(LS) = a1 。 GetTail(LS) = (a2, … , an)。 注意： 取表頭運(yùn)算得到的結(jié)果可以是原子 ， 也可以是一個(gè)子表 。 取表尾運(yùn)算得到的結(jié)果一定是一個(gè)子表 。 例 : D = ( E, F ) = ((a, (b, c))， F ) GetHead( D ) = E GetTail( D ) = ( F ) GetHead( E ) = a GetTail( E ) = ((b, c)) GetHead(((b, c))) = (b, c) GetTail(((b, c))) = ( ) GetHead((b, c)) = b GetTail((b, c)) = (c) GetHead((c)) = c GetTail((c)) = ( ) 廣義表基本運(yùn)算 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表的存儲(chǔ)結(jié)構(gòu) 由于廣義表是遞歸定義的，