【正文】 取表尾運(yùn)算得到的結(jié)果一定是一個(gè)子表 。 GetTail(LS) = (a2, … , an)。 由于廣義表不僅集中了線性表、數(shù)組、樹和有向圖等常見 數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，而且可有效地利用存儲(chǔ)空間，因此在計(jì)算機(jī) 的許多應(yīng)用領(lǐng)域都有成功使用廣義表的實(shí)例。 當(dāng) 二維數(shù)組的每行（或每列）作為子表處理時(shí)，二維數(shù)組 即為一個(gè)廣義表。 例： D=(E, F) 其中 ： E=(a, (b, c)) F=(d, (e)) D a d b c e E F 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表 可以看成 是線性表的推廣 ， 線性表是廣義表的特例 。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 (6) 廣義表是 多層次 結(jié)構(gòu)，廣義表的元素可以是單元素，也可以 是子表，而子表的元素還可以是子表， … 。 (5) 廣義表可以是一個(gè) 遞歸 的表。 (4) 廣 義表可以為其他廣義表 共享 ；如：廣義表 B 就共享表 A。 注意： “原子”的深度為 0 。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表的性質(zhì) (1) 廣義表中的數(shù)據(jù)元素有相對(duì) 次序 ； (2) 廣義表的 長度 定義為最外層所包含元素的個(gè)數(shù)； 如： C=(a, (b, c)) 是長度為 2 的廣義表。 長度為 2，第一項(xiàng)為原子，第二項(xiàng)為它本身。 (6) F=(a, F) 長度為 2，每一項(xiàng)都是子表。 長度為 3， 每一項(xiàng)都是原子 。 長度為 2， 由原子 a 和子表 (b, c) 構(gòu)成 。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 (1) A=( ) 例： 空表，長度為 0。 記作 tail(LS) = (a2, ..., an)。 注： 表頭可以是原子，也可以是子表。 表頭 ： 若 LS 非空 (n≥1 )，則其 第一個(gè) 元素 a1 就是表頭。 單個(gè)元素 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表 通常記作： LS = (a1， a2， … ， an) 其中： LS 為表名， n 為表的長度， 每一個(gè) ai 為表的元素。國家隊(duì)、魯能隊(duì)、實(shí)德隊(duì)均作為東道主 的參賽隊(duì)參加，構(gòu)成一個(gè)小的線性表，成為原線性表的一個(gè)數(shù) 據(jù)元素。 此算法時(shí)間復(fù)雜度： O(ta+tb) ▲ 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 廣義表 （又稱 列表 Lists） 是 n≥0 個(gè)元素 a0, a1, …, an1 的有限序列，其中每一個(gè) ai 或者是 原子 ，或者是一個(gè) 子表 。 } free (p)。 同時(shí)，為了改變列表中的指針，需要先找到同一列中的前驅(qū) 結(jié)點(diǎn)，且讓 hl[paj]指向該結(jié)點(diǎn)，然后如下修改相應(yīng)指針： if chead[pj] == p chead[pj] = hl[pj] = pdown。 } p=pa。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 此時(shí)若 pae!=0，則指針不變，否則刪除 A中該結(jié)點(diǎn)，即行表 中指針變?yōu)椋? if pre == NULL rhead[pai] = paright。 pa＝ paright。 } hl[pj] = p。 } else { pdown＝ hl[pj]down。首先需從 hl[pj] 開始找到新結(jié)點(diǎn)在同一列中的前驅(qū)結(jié)點(diǎn)，并讓 hl[pj]指 向它，然后在列鏈表中插入新結(jié)點(diǎn)： if chead[pj] == NULL { chead[pj] = p。 pre = p。 else { preright＝ p。 (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)。 j=。 pre = NULL。 /*完成插入 */ } } } 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 兩個(gè)矩陣相加的算法描述： (1) 初始令 pa和 pb分別指向 A和 B的第一行的第一個(gè)非零 元素的結(jié)點(diǎn)，即 pa＝ [1]。 q=qdown) pdown=qdown。amp。 else{ /*尋找列表中的插入位置 */ for(q=Mcol_head[j]。 qright=p。qrightcolj。 qrightamp。 //生成結(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 if(Mrow_head[i]==NULL) Mrow_head[i]=p。pcol=j。e)) {if(!(p=(OLNode *) malloc(sizeof(OLNode)))) exit(OVERFLOW)。i,amp。i!=0。j,amp。 //初始化行 、 列頭指針向量 ， 各行 、 列鏈表為空的鏈表 for(scanf(amp。 If(!(Mcol_head=(OLink * )malloc((n+1)sizeof(OLink)))) exit(OVERFLOW)。Mlen=t。 //輸入 M的行數(shù) ,列數(shù)和非零元素的個(gè)數(shù) Mm=m。n,amp。 scanf(amp。 //稀疏矩陣的行數(shù) 、 列數(shù) 、 非零元個(gè)數(shù) }CrossList。 typedef struct { OLink * rhead, *chead。 // 非零元素所在行表列表的后繼鏈域 }OLNode。 // 非零元素的行和列下標(biāo) ElementType e。 在十字鏈表中，矩陣的每一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示， 該結(jié)點(diǎn)除了（ row， col， value）以外，還要有兩個(gè)域： right： 用于鏈接同一行中的下一個(gè)非零元素； down：用以鏈接同一列中的下一個(gè)非零元素。如果事先能估算出所求 乘積矩陣 Q不再是稀疏矩陣，則以二維數(shù)組表示 Q，相乘的 算法也就更簡單了。 若 M是 m行 n列的稀疏矩陣， N是 n行 p列的稀疏矩陣，則 M中 非零元的個(gè)數(shù) = d M m n， N中非零元的個(gè)數(shù) = d N n p，相乘算法的時(shí)間復(fù)雜度就是 O(m p (1+nd Md N)) ，當(dāng) d M 和 d N 及 n 1000時(shí)，相乘算法的時(shí)間復(fù)雜度就相當(dāng)于 O (m p)。 } // if } // for arow } // if return OK。 ++ccol) // 壓縮存儲(chǔ)該行非零元 if (ctemp[ccol]) { if (++ MAXSIZE) return ERROR。 } // for q } // 求得 Q中第 crow( =arow)行的非零元 for (ccol=1。 ++q) { ccol = [q].j。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 for (q=[brow]。 if (brow ) t = [brow+1]。 p[arow+1]。 else tp=+1。 // 當(dāng)前行各元素的累加器清零 [arow] = + 1。 arow=。 = 0。 = 。 row 1 2 3 4 rpos[row] 1 2 3 5 1 2 6 2 1 1 3 2 4 0 0 6 1 0 4 注意： 兩個(gè)稀疏矩陣相乘的結(jié)果 不一定 是稀疏矩陣。 } ??????????????????????????04020 21 0 0050000 10 203NM??????????????4060 10 NMQi i j j k k 不論是否為零，都要進(jìn)行一次乘法運(yùn)算。 k=n1。 j++) { Q[i][j]=0。 i++) for(j=1。 矩陣相乘的經(jīng)典算法： for(i=1。 RLSMatrix。 int rpos[MAXRC + 1]。 int mu, nu, tu。 }Triple。 數(shù)據(jù)結(jié)構(gòu) 第五章 數(shù)組和廣義表 define MAXSIZE 12500 //假設(shè)非零元個(gè)數(shù)的最大值 typedef struct { int i, j。 7 6 8 1 3 3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 col 1 2 3 4 5 6 7 num(col) 2 2 2 1 0 1 0 cpot(col) 1 3 5 7 8 8 9 若在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中增加一個(gè)行表 rpos ——快速轉(zhuǎn)置算法中的 cpot， 指示稀疏矩陣中每行的 非零元素在三元組表中的起始位置，則不 必從第一個(gè) 元素起進(jìn)行搜索查詢。若按行號(hào)存取某 一行中的非零元，則需從頭開始進(jìn)行查找。 三元組順序表的 優(yōu)點(diǎn) ：非零元在表中按行序有序存儲(chǔ)，因此 便于進(jìn)行依行順序處理的矩陣運(yùn)算 。 } // FastTransposeSMatrix 時(shí)間復(fù)雜度為 : O(nu + tu) 若 tu 與 mu?nu 同數(shù)量級(jí)，則為： O(mu?nu) 與經(jīng)典算 法相同。 ++ cpot[col]。 [q].j = [p].i。 q = cpot[col]。 p=。 ++col) cpot[col] = cpot[col 1] + num[col 1]。 for (col=2。 ++t) ++ num[[t].j]。 for (t=1。 col=。 = 。T ) { // 采用三元組順序表存儲(chǔ)表示