【正文】 時(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 66 [4] 33 22 66 [5] 33 55 33 99 [5。coln。rowm。 /*三元組表 */ }SpMatrix。 typedef struct{ int m,n,t。 /*行列號 */ datatype v。2/)1()1(2/)1()1( k 4． 3 矩陣的壓縮存儲(chǔ) 157 3. 對稱矩陣 aij = aji k= I(I+1)/2+J 。2/)1(2/)1( k 上三角 ?????????????jijinnjniiin。232jijinji k 單對角陣 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。 k 三對角陣 ??????????1||。 ?????????????????? 1,1221100nnaaaa?0 0 ??????????????????????1,12,11,22322211211100100nnnnnnaaaaaaaaaaa?0 0 4． 3 矩陣的壓縮存儲(chǔ) 154 若將以上兩矩陣以一維數(shù)組 B[M]壓縮存儲(chǔ) ,a[i][j] b[k] ??????jijini。 142 第四章 數(shù) 組 ?數(shù)組的順序表示和實(shí)現(xiàn) ?矩陣的壓縮存儲(chǔ) : 特殊矩陣 稀疏矩陣 【 學(xué)習(xí)內(nèi)容 】 143 數(shù)組的定義及運(yùn)算 ?數(shù)組的性質(zhì) ?數(shù)組元素?cái)?shù)目固定 ?元素類型相同 ?下標(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è)元素都與 一對下標(biāo) 有關(guā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ù)。 試問： (1) 設(shè)有編號為 1,2,3,4,5, 6的六輛列車 , 順序開入棧式結(jié)構(gòu)的站臺(tái) , 則可能的出棧序列有多少種 ? (2) 若進(jìn)站的六輛列車順序如上所述 , 那么是否能夠得到 435612, 325641, 154623和 135426的出站序列 , 如果不能 , 說明為什么不能 。 return(1)。 else { front=(front+1)%MAXSIZE。 sq[rear]=x。 138 void en_cycque(int sq[],int front,int rear,int x){ if(((rear+1)%MAXSIZE)==front) printf(overflow)。 ?入隊(duì) rear=(rear+1) % MaxSize。 隊(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ì)滿 ： 隊(duì)空： front==rear 隊(duì)滿： (rear+1)%M==front ?循環(huán)隊(duì)列出入隊(duì)圖示 隊(duì)空： front==rear 隊(duì)滿： front==rear 137 隊(duì)列（ QUEUE） ?少用一個(gè)元素空間解決方案 ?隊(duì)空 rear = front。 ?存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。 隊(duì)滿： (rear+1) % maxSize=front。 elements[rear]=item 出隊(duì)： front=(front+1)%MaxSize。 187。出隊(duì)： front=(front+1)%M。 sq[rear]=x。實(shí)現(xiàn)：利用“模”運(yùn)算 187。 rear rear front rear 1 2 3 4 5 0 J1,J2,J3出隊(duì) J1 J2 J3 front front front ? 三、循環(huán)隊(duì)列 隊(duì)列的順序表示和實(shí)現(xiàn) 133 隊(duì)列（ QUEUE） ?存在問題 設(shè)數(shù)組維數(shù)為 M，則： ?當(dāng) front=1,rear=M1時(shí) ， 再有元素入隊(duì)發(fā)生溢出 —真溢出 ?當(dāng) front 1,rear=M1時(shí) ， 再有元素入隊(duì)發(fā)生溢出 —假溢出 解決方案 : ?隊(duì)首固定 ， 每次出隊(duì)剩余元素向下移動(dòng) ——浪費(fèi)時(shí)間 ?循環(huán)隊(duì)列 134 ?循環(huán)隊(duì)列 基本思想 ： 存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理 ； 讓 sq[0]接在 sq[M1]之后，若 rear+1==M,則令 rear=0。} 132 隊(duì)列（ QUEUE） front=1 rear=1 1 2 3 4 5 0 隊(duì)空 1 2 3 4 5 0 front J1,J1,J3入隊(duì) J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入隊(duì) J4 J5 J6 front 設(shè)兩個(gè)指針 front,rear,約定： rear指示隊(duì)尾元素； front指示隊(duì)頭元素前一位置 初值 front=rear=1 空隊(duì)列條件： front==rear 入隊(duì)列： sq[++rear]=x。 free(s)。} Else Qfrontnext = snext。/*指向被刪結(jié)點(diǎn) */ if(snext == NULL){ QfrontNext = Null。 131 隊(duì)列（ QUEUE） ?鏈隊(duì)列出隊(duì)算法 if(Empty(Q)) return ERROR。 Qrearnext = p。 pdata = x。 }Qnode,*QueuePtr。e ) 127 隊(duì)列（ QUEUE） 二、鏈隊(duì)列 ?結(jié)點(diǎn)定義 typedef struct node { int data。Q,amp。Q) （ 2）進(jìn)隊(duì) EnQueue(amp。 隊(duì)中元素按 a1， a2， a3， … an的次序入隊(duì)，出隊(duì)按先進(jìn)先出的原則進(jìn)行的 ,因此 a1，a2， a3， … an的次序出隊(duì) front 和 rear的初始值地隊(duì)列初始化時(shí)均應(yīng)置為 1。 請同學(xué)們下去自己編程序試試。 （ 2） w=2 （ 1） w=3 top (3) 輸出： 2, 2 w 1 print(0)。 3 print(2)。 printf(“ /n” )。i=w。 if ( w!=0) { print(w1)。 return n*Factorial(n1)。一個(gè)過程直接地或間接地調(diào)用自己 169。 } 112 棧 （ stack） 棧的應(yīng)用 (1)“ 回溯 ” 問題求解 (2) 過程的嵌套和遞歸調(diào)用 113 1．嵌套調(diào)用 棧 （ stack） 棧的應(yīng)用 114 r 主程序 s r 子過程1 r s t 子過程2 r s t 子過程3 s r r 棧 （ stack） ?嵌套調(diào)用過程圖示 115 遞歸：函數(shù)直接或間接的調(diào)用自身的過程 169。 free(p)。 Stop = pnext。} 111 棧 （ stack） ?鏈棧的出棧算法 出棧等同于刪除第一個(gè)結(jié)點(diǎn) Status Pop(LinkList * S,datatype *e ){ If(Stop) return ERROR。 Stop = p。 pdata = e。 ?結(jié)點(diǎn)定義 ^ …... top data link 棧底 棧頂 109 棧 （ stack） ?鏈棧的特點(diǎn) ?鏈表的存儲(chǔ)結(jié)構(gòu)與鏈接存儲(chǔ)的棧完全相同，只是鏈頭指針就是棧頂指針。 struct node *link。 return OK。 Stop 。 return OK。 Stop ++。 }SqStack。新 元 素 插 入elements[top]位置 出棧： top1 an a1 a2 ……... 棧底 棧頂 ... 出棧 進(jìn)棧 棧 s=(a1,a2,……,an) 棧 （ stack） ?棧的圖示 102 棧 （ stack） 棧和線性表類似，也有兩種（順序、鏈?zhǔn)剑?shí)現(xiàn)方法 103 ?存儲(chǔ)結(jié)構(gòu)定義 define MAXSIZE 6 typedef struct{ datatype elements[MAXSIZE]。e) （ 5）獲得棧頂元素值 GetTop(s,amp。s,x) （ 4） 出棧 Pop(amp。s) （ 2 ）判斷一個(gè)棧是否為空 StackEmpty(amp。新元素插入 elements[top]位置 ?出棧 top1。當(dāng)表中沒有元素時(shí)稱為 空棧 ?特點(diǎn)： 先進(jìn)后出 （ F I L O） 或后進(jìn)先出（ LIFO） 99 例：假設(shè)棧 S=(a1， a2， a3， … an) 則 a1稱為棧底元素， an為棧頂元素。 棧（ stack） 167。 96 習(xí)題與練習(xí) 二 算： (1) 初始化 (2) 定位 (3) 插