【正文】 col++) b[col][row] = a[row][col]。row++) for(col=0。 4． 3 矩陣的壓縮存儲 rr oo w cc oo ll vv aa ll u ee 160 4． 3 矩陣的壓縮存儲 ? 三元組表示例 ???????????100001013200M 1 3 2 2 0 2 1 1 1 1 2 0 3 1 0 5 4 3 行數(shù) 列數(shù) 元素個數(shù) 行 列 值 161 ????????????????????????????????????????????????0000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022022A6776轉(zhuǎn)置為4． 3 矩陣的壓縮存儲 例： 矩陣轉(zhuǎn)置： Am*n Bn*m 且 a[i][j]==b[j][i] 162 (1) 一般矩陣： for(row=0。 /*行、列數(shù)，非零元素個數(shù) */ node data[SMAX]。 /*元素值 */ }node。I = max(i,j),J=min(i,j) 4． 3 矩陣的壓縮存儲 好東西??！ 158 二 . 稀疏矩陣 ?Am*n 中非零元素個數(shù)遠小于零元素個數(shù) 4． 3 矩陣的壓縮存儲 1．三元組表 組成 ：所有非零元素（行，列，值） + （行數(shù)，列數(shù)，非零元素個數(shù)） 159 ?三元組表類型說明： define SMAX 16 typedef int datatype； typedef struct{ int i,j。1||。 ?運算： ① 給定一組下標 ， 存取 相應(yīng) DE ② 給定一組下標， 修改 相應(yīng) DE 147 4． 2 數(shù)組的順序表示 ?????????232221131211aaaaaaA元素數(shù)目、關(guān)系固定 順序存儲 多維數(shù)組以一維方式存儲，即數(shù)組元素還是數(shù)組！ ?問題：內(nèi)存是一維的 ， 如何以一維內(nèi)存存儲多維數(shù)組 148 4． 2 數(shù)組的順序表示 LOC ( i ) = LOC ( i 1 ) + l =α+ i*l ?一維數(shù)組的存儲 149 4． 2 數(shù)組的順序表示 ?二維數(shù)組的存儲 ??????231322122111aaaaaa a23 a22 a21 a13 a12 a11 行優(yōu)先存儲 a23 a13 a22 a12 a21 a11 列優(yōu)先存儲 150 5． 2 數(shù)組的順序表示 )(]][[]2][[]1][[]0][[]][2[]2][2[]1][2[]0][2[]][1[]2][1[]1][1[]0][1[]][0[]2][0[]1][0[]0][0[a i jL o cMNANANANAMAAAAMAAAAMAAAA求對??????????????????????????行優(yōu)先 LOC ( i, j ) = a + ( (i – 0) * m + (j 0)) * l ?列優(yōu)先 LOC ( i, j ) = a + ( (j 0) * n + (i – 0) ) * l 例： 151 ? n維數(shù)組 ? 各維元素個數(shù)為 m1, m2, m3, …, m n ? 下標為 i1, i2, i3, …, i n 的數(shù)組元素的存儲地址： limialimimmmimmmiaiiiL O Cnjnjknkjnnnnnn**)(),(11 1143232121????????????????????????????? ??? ????????4． 2 數(shù)組的順序表示 152 4． 3 矩陣的壓縮存儲 ?壓縮存儲 多個值相同的元素只分配一個空間，零元素不分配空間 153 一 、 特殊矩陣 ?定義： 相同元素 /零元素分布有一定規(guī)律的矩陣 。試給出該循環(huán)隊列的隊空條件和隊滿條件 , 并寫出相應(yīng)的插入 (enqueue)和刪除(delqueue)元素的操作。 如果能 , 說明如何得到 (即寫出 進棧 或 出棧 的序列 )。 } } 140 1. 鐵路進行列車調(diào)度時 , 常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺 ， 如右圖所示 。 *q=sq[front]。 } } 隊列（ QUEUE） ?循環(huán)隊列入隊算法 139 ?循環(huán)隊列出隊 隊列（ QUEUE） int del_cycque(int sq[],int front,int rear,int *q){ if(front==rear) return(0)。 else { rear=(rear+1)%MAXSIZE。 elements[rear]=item； ?出隊 front=(front+1)%MaxSize。 ?隊滿 (rear+1) % maxSize=front。 ?隊頭、隊尾指針 加 1時從 MaxSize 1直接進到 0，可用語言的取模 (余數(shù) )運算實現(xiàn)。 0 1 2 …… front 0 1 2 rear 隊列初始化： front = rear = 0。 隊空： rear = front。隊滿、隊空判定條件 0 M1 1 front rear 135 …… rear front maxSize1 入隊 : rear=(rear+1) % MaxSize。 x=sq[front]。 187。入隊： rear=(rear+1)%M。 隊列（ QUEUE） 187。 出隊列： x=sq[++front]。 return OK。 *e = sdata。 Qrear = Qfront。 else{ s = Qfrontnext。 Qrear = p。 pnext = NULL。 128 front rear x入隊 ^ x front rear y入隊 x ^ y front rear 空隊 ^ 隊列（ QUEUE） ?鏈隊列圖示 129 入隊不用考慮隊滿 ,但出隊要考慮隊空 隊空條件為 front == rear front rear y出隊 ^ front rear x出隊 x ^ y 隊列（ QUEUE） ?鏈隊列圖示 130 隊列（ QUEUE） ?鏈隊列入隊算法 p = (QueuePtr)malloc(sizeof(Qnode))。 struct node *next。e) （ 4） 判斷一個隊列是否為空 QueueEmpty(Q) （ 5）獲得隊頭元素值 GetHead(Q,amp。Q,e) （ 3） 出隊 DeQueue(amp。 124 入隊 時將 rear+1, 新元素插入 elements[rear]位置 . 出隊 時，將加 front+1, 刪去元素 隊列（ QUEUE） a1 a2 a3…………………… .an 入隊 出隊 front rear 隊列 Q=(a1,a2,……,an) ?隊列定義 125 a1 a2 a3…………………… .an 端 1 端 2 入隊 出隊 入隊 出隊 隊列（ QUEUE） ?雙端隊列 126 隊列（ QUEUE） ?隊列的主要操作 （ 1）建立一個空隊列 InitQueue(amp。 122 隊列（ QUEUE） 一、隊列定義 ?隊列是限定只能在表的一端進插入，在表的另一端進行刪除的線性表 ?隊尾 (rear)——允許插入的一端 ?隊頭 (front)——允許刪除的一端 ?隊列特點： 先進先出 (FIFO) 123 隊列（ QUEUE） ?隊列定義 假設(shè)隊列 S=(a1， a2， a3， … an)， 則 a1稱為 隊首元素 ， an為 隊尾元素 。 （ 3） w=1 （ 2） w=2 （ 1） w=3 top (4)輸出： 1 w 0 （ 4） w=0 （ 3） w=1 （ 2） w=2 （ 1） w=3 top w (2) 2 (1) 3 輸出：(3) 1 (2) 2 (1) 3 3 (1 ) 3 返回 (3) 1 (2) 2 (1) 3 top (4) 0 結(jié)束 ?上例圖示分析 121 括號的匹配檢驗 棧 （ stack） ?假設(shè)表達式中有多種擴號，可以用棧來進行擴號匹配檢驗，具體做法為： 非括號字符跳過不理；碰上左擴號，入棧；碰上右擴號，出棧，并且檢查出棧元素是否與當前右擴號相匹配，若匹配繼續(xù)檢查，否則匹配失敗。 （ 1） w=3 top (2) 輸出： 3, 3, 3 w 2 print(1)。 } } 棧 （ stack） 運行結(jié)果： 1， 2， 2， 3， 3， 3， ? 例 遞歸的執(zhí)行情況分析 120 棧 （ stack） 主程序 (1) print(w) w=3。++i) printf(―%3d,‖,w)。 for(i=1。 } 118 例 ：遞歸的執(zhí)行情況分析 棧 （ stack） 119 void print(Int w) { int i。利用前面運算來求得答案的過程 ?實現(xiàn)： 建立遞歸工作棧 ?優(yōu)點： 遞歸函數(shù)結(jié)構(gòu)清晰 ， 程序易讀 ， 正確性易證明 ?缺點： 速度慢 ， 空間大效率低 棧 （ stack） 2．遞歸調(diào)用 116 棧 （ stack） void p (參數(shù)表 ) { if （遞歸結(jié)束條件） 可直接求解步驟； 基本項 else p（較小的參數(shù)）； 歸納項 } ?遞歸算法的一般形式 117 棧 （ stack） 例：求 n! = 1， n=0 n*(n1)！ n0 int Factorial(int n){ if (n==0) return 1。一個對象部分地包含它自己 ， 或是用它自己給自己定義 169。 return OK。 *e = pdata。/*下溢 */ p = Stop。 return OK。 pnext = Stop。 初始時為NULL ? 鏈式棧無棧滿問題，空間可擴充 ? 插入與刪除僅在棧頂處執(zhí)行 ? 鏈式棧的棧頂在鏈頭 ? 適合于多棧操作 110 棧 （ stack） ?鏈棧的進棧算法 進棧等同于不帶頭結(jié)點單鏈表的頭插法 Status Push(LinkList * S,datatype e ){ p = (LinkList *)malloc(sizeof(Linklist))。 }LinkList。 } 108 二、鏈棧 （單鏈表） 棧 （ stack） typedef struct node { int data。 *e