【正文】 ear]=item 出隊(duì)： front=(front+1)%MaxSize。 隊(duì)空： rear = front。 隊(duì)滿(mǎn)： (rear+1) % maxSize=front。 0 1 2 …… front 0 1 2 rear 隊(duì)列初始化： front = rear = 0。 ?存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。 ?隊(duì)頭、隊(duì)尾指針 加 1時(shí)從 MaxSize 1直接進(jìn)到 0，可用語(yǔ)言的取模 (余數(shù) )運(yùn)算實(shí)現(xiàn)。 隊(duì)列（ QUEUE） 136 0 1 2 3 4 5 rear front J4 J5 J6 0 1 2 3 4 5 J9 J8 J7 front rear 隊(duì)列（ QUEUE） J4 J5 J6 0 1 2 3 4 5 rear front 初始狀態(tài) 解決方案： 設(shè)一個(gè)標(biāo)志 以區(qū)別隊(duì)空、隊(duì)滿(mǎn) ： 隊(duì)空： front==rear 隊(duì)滿(mǎn)： (rear+1)%M==front ?循環(huán)隊(duì)列出入隊(duì)圖示 隊(duì)空： front==rear 隊(duì)滿(mǎn)： front==rear 137 隊(duì)列（ QUEUE） ?少用一個(gè)元素空間解決方案 ?隊(duì)空 rear = front。 ?隊(duì)滿(mǎn) (rear+1) % maxSize=front。 ?入隊(duì) rear=(rear+1) % MaxSize。 elements[rear]=item； ?出隊(duì) front=(front+1)%MaxSize。 138 void en_cycque(int sq[],int front,int rear,int x){ if(((rear+1)%MAXSIZE)==front) printf(overflow)。 else { rear=(rear+1)%MAXSIZE。 sq[rear]=x。 } } 隊(duì)列（ QUEUE） ?循環(huán)隊(duì)列入隊(duì)算法 139 ?循環(huán)隊(duì)列出隊(duì) 隊(duì)列（ QUEUE） int del_cycque(int sq[],int front,int rear,int *q){ if(front==rear) return(0)。 else { front=(front+1)%MAXSIZE。 *q=sq[front]。 return(1)。 } } 140 1. 鐵路進(jìn)行列車(chē)調(diào)度時(shí) , 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái) ， 如右圖所示 。 試問(wèn)： (1) 設(shè)有編號(hào)為 1,2,3,4,5, 6的六輛列車(chē) , 順序開(kāi)入棧式結(jié)構(gòu)的站臺(tái) , 則可能的出棧序列有多少種 ? (2) 若進(jìn)站的六輛列車(chē)順序如上所述 , 那么是否能夠得到 435612, 325641, 154623和 135426的出站序列 , 如果不能 , 說(shuō)明為什么不能 。 如果能 , 說(shuō)明如何得到 (即寫(xiě)出 進(jìn)棧 或 出棧 的序列 )。 第三章 習(xí)題與上機(jī)實(shí)驗(yàn) 141 第三章 習(xí)題與上機(jī)實(shí)驗(yàn) Q[m]存放循環(huán)隊(duì)列中的元素 , 同時(shí)以 rear和 length分別指示環(huán)形隊(duì)列中的隊(duì)尾位置和隊(duì)列中所含元素的個(gè)數(shù)。試給出該循環(huán)隊(duì)列的隊(duì)空條件和隊(duì)滿(mǎn)條件 , 并寫(xiě)出相應(yīng)的插入 (enqueue)和刪除(delqueue)元素的操作。 142 第四章 數(shù) 組 ?數(shù)組的順序表示和實(shí)現(xiàn) ?矩陣的壓縮存儲(chǔ) : 特殊矩陣 稀疏矩陣 【 學(xué)習(xí)內(nèi)容 】 143 數(shù)組的定義及運(yùn)算 ?數(shù)組的性質(zhì) ?數(shù)組元素?cái)?shù)目固定 ?元素類(lèi)型相同 ?下標(biāo)有界且有序 144 一維數(shù)組 ?數(shù)組圖示 數(shù)組的定義及運(yùn)算 eg. [a1,a2,… ,] [（ a11,a12,… a1n） ,(a21,a22,… ,a2n)] 145 二 維 數(shù) 組 數(shù)組的定義及運(yùn)算 ?數(shù)組圖示 三 維 數(shù) 組 146 數(shù)組的定義及運(yùn)算 ?定義： 由 值 和 下標(biāo) 構(gòu)成的有序?qū)?，結(jié)構(gòu)中的每一個(gè)元素都與 一對(duì)下標(biāo) 有關(guān)。 ?運(yùn)算： ① 給定一組下標(biāo) ， 存取 相應(yīng) DE ② 給定一組下標(biāo)， 修改 相應(yīng) DE 147 4． 2 數(shù)組的順序表示 ?????????232221131211aaaaaaA元素?cái)?shù)目、關(guān)系固定 順序存儲(chǔ) 多維數(shù)組以一維方式存儲(chǔ)，即數(shù)組元素還是數(shù)組！ ?問(wèn)題：內(nèi)存是一維的 ， 如何以一維內(nèi)存存儲(chǔ)多維數(shù)組 148 4． 2 數(shù)組的順序表示 LOC ( i ) = LOC ( i 1 ) + l =α+ i*l ?一維數(shù)組的存儲(chǔ) 149 4． 2 數(shù)組的順序表示 ?二維數(shù)組的存儲(chǔ) ??????231322122111aaaaaa a23 a22 a21 a13 a12 a11 行優(yōu)先存儲(chǔ) a23 a13 a22 a12 a21 a11 列優(yōu)先存儲(chǔ) 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求對(duì)??????????????????????????行優(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ù)組 ? 各維元素個(gè)數(shù)為 m1, m2, m3, …, m n ? 下標(biāo)為 i1, i2, i3, …, i n 的數(shù)組元素的存儲(chǔ)地址： limialimimmmimmmiaiiiL O Cnjnjknkjnnnnnn**)(),(11 1143232121????????????????????????????? ??? ????????4． 2 數(shù)組的順序表示 152 4． 3 矩陣的壓縮存儲(chǔ) ?壓縮存儲(chǔ) 多個(gè)值相同的元素只分配一個(gè)空間，零元素不分配空間 153 一 、 特殊矩陣 ?定義： 相同元素 /零元素分布有一定規(guī)律的矩陣 。 ?????????????????? 1,1221100nnaaaa?0 0 ??????????????????????1,12,11,22322211211100100nnnnnnaaaaaaaaaaa?0 0 4． 3 矩陣的壓縮存儲(chǔ) 154 若將以上兩矩陣以一維數(shù)組 B[M]壓縮存儲(chǔ) ,a[i][j] b[k] ??????jijini。 k 三對(duì)角陣 ??????????1||。1||。232jijinji k 單對(duì)角陣 4． 3 矩陣的壓縮存儲(chǔ) 155 2. 上（下）三角矩陣 ??????????????????? 1,10,1111000nnn aaaaa?????0 ???????????????????1,122111,00100nnnaaaaaa???0 非零元素共 n(n+1)/2個(gè) ， 以數(shù)組B[n*(n+1)/2]存儲(chǔ)非零 DE 4． 3 矩陣的壓縮存儲(chǔ) 156 下三角 2. 上（下）三角矩陣 ?????????jijinnjii。2/)1(2/)1( k 上三角 ?????????????jijinnjniiin。2/)1()1(2/)1()1( k 4． 3 矩陣的壓縮存儲(chǔ) 157 3. 對(duì)稱(chēng)矩陣 aij = aji k= I(I+1)/2+J 。I = max(i,j),J=min(i,j) 4． 3 矩陣的壓縮存儲(chǔ) 好東西??！ 158 二 . 稀疏矩陣 ?Am*n 中非零元素個(gè)數(shù)遠(yuǎn)小于零元素個(gè)數(shù) 4． 3 矩陣的壓縮存儲(chǔ) 1．三元組表 組成 ：所有非零元素（行，列，值） + （行數(shù)，列數(shù)，非零元素個(gè)數(shù)） 159 ?三元組表類(lèi)型說(shuō)明： define SMAX 16 typedef int datatype； typedef struct{ int i,j。 /*行列號(hào) */ datatype v。 /*元素值 */ }node。 typedef struct{ int m,n,t。 /*行、列數(shù)，非零元素個(gè)數(shù) */ node data[SMAX]。 /*三元組表 */ }SpMatrix。 4． 3 矩陣的壓縮存儲(chǔ) rr oo w cc oo ll vv aa ll u ee 160 4． 3 矩陣的壓縮存儲(chǔ) ? 三元組表示例 ???????????100001013200M 1 3 2 2 0 2 1 1 1 1 2 0 3 1 0 5 4 3 行數(shù) 列數(shù) 元素個(gè)數(shù) 行 列 值 161 ????????????????????????????????????????????????0000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022022A6776轉(zhuǎn)置為4． 3 矩陣的壓縮存儲(chǔ) 例： 矩陣轉(zhuǎn)置： Am*n Bn*m 且 a[i][j]==b[j][i] 162 (1) 一般矩陣： for(row=0。rowm。row++) for(col=0。coln。col++) b[col][row] = a[row][col]。 時(shí)間復(fù)雜度為 O(m*n) 4． 3 矩陣的壓縮存儲(chǔ) 163 4． 3 矩陣的壓縮存儲(chǔ) (2) 三元組表 行行 (( rr oo ww )) 列列(( cc oo ll )) 值值(( vv aa ll uu ee )) 行行(( rr oo ww )) 列列(( cc oo ll )) 值值(( vv aa ll uu ee )) [0] 00 33 22 22 [0] 00 44 99 11 [1] 00 66 11 55 [1] 11 11 11 11 [2] 11 11 11 11 [2] 22 55 22 88 [3] 11 55 11 77 [3] 33 00 22 22 [4] 22 33