1、3.1 棧的類型定義棧的類型定義3.2 利用棧實現表達式求值利用棧實現表達式求值3.4 隊列隊列3.3 棧與遞歸棧與遞歸3.5 數組數組3.6 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲棧和隊列是限定插入和刪除只能插入和刪除只能在表的“端點端點”進行的線性表。 線性表線性表 棧棧 隊列隊列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊列是兩種常用的數據類型棧和隊列是兩種常用的數據類型1234棧和隊列是限定插入和刪除只能插入和刪除只能在表的“端

2、點端點”進行的線性表。 3.1.1 棧的定義棧的定義 堆棧是一種只允許在堆棧是一種只允許在表的一端進表的一端進行插入和刪除運算行插入和刪除運算的線性表；的線性表； 允許進行運算的一端稱為允許進行運算的一端稱為棧頂棧頂，另一端則稱為另一端則稱為棧底棧底； 當表中沒有元素時，稱為當表中沒有元素時，稱為空棧空棧； 堆棧的插入運算簡稱為堆棧的插入運算簡稱為入棧或進入棧或進棧棧，刪除運算簡稱為，刪除運算簡稱為出棧或退棧出棧或退棧。出棧出棧進棧進棧棧的示意圖棧的示意圖棧頂棧頂棧底棧底a an na a2 2a a1 1 堆棧的特點堆棧的特點出棧出棧進棧進棧棧的特點棧的特點后進先出后進先出第一個進棧的元素在

3、棧底第一個進棧的元素在棧底最后一個進棧的元素在棧頂最后一個進棧的元素在棧頂第一個出棧的元素為棧頂元素第一個出棧的元素為棧頂元素最后一個出棧的元素為棧底元最后一個出棧的元素為棧底元素素棧的示意圖棧的示意圖棧頂棧頂棧底棧底a an na a2 2a a1 1a1a2a3a4a5a6insert xiDelete xjinsertdelete棧的實例棧的實例實例：裝網球的紙筒、子彈夾實例：裝網球的紙筒、子彈夾 ，羊肉串，貨棧，羊肉串，貨棧3.1 棧的抽象數據類型定義棧的抽象數據類型定義 ADT Stack 數據對象數據對象： D ai | ai ElemSet, i=1,2,.,n, n0 數據關系

4、數據關系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT StackInitStack(Stack & S)DestroyStack(Stack &S)ClearStack(const Stack &S)StackEmpty(const Stack &S)StackLength(const Stack& S)GetTop(const Stack &S, &e)Push(Stack &S, e)Pop(Stack &S, &e)StackTrave

5、rs(const Stack &S, visit()棧類型的實現棧類型的實現順序棧順序棧鏈鏈 棧棧順序棧的實現順序棧的實現 和順序表類似，對順序棧的存儲也是利和順序表類似，對順序棧的存儲也是利用一組連續的存儲單元依次存放自棧底用一組連續的存儲單元依次存放自棧底到棧頂的元素，同時附設指針到棧頂的元素，同時附設指針toptop指示棧指示棧頂元素在順序棧中的位置頂元素在順序棧中的位置。由于棧在使用過程中所需最大空間的大小很難由于棧在使用過程中所需最大空間的大小很難估計，因此，在初始化設空棧時不應限定棧的估計，因此，在初始化設空棧時不應限定棧的最大容量。一般，先分配一個基本容量，然后最大容量。

6、一般，先分配一個基本容量，然后在應用過程中，當棧的空間不夠使用時再逐段在應用過程中，當棧的空間不夠使用時再逐段擴大。擴大。棧的數組表示棧的數組表示 順序棧順序棧0 1 2 3 4 5 6 7 8 9 maxSize-1top()elem#define initSize 100 /棧空間初始大小棧空間初始大小#define increament 20 /棧空間擴充增量棧空間擴充增量typedef struct /順序棧定義順序棧定義 SElemType *elem; /棧數組棧數組 int top, maxSize; /棧頂指針及棧大小棧頂指針及棧大小 SeqStack; top空棧toptop

7、toptoptopa 進棧b 進棧aababcdee 進棧abcdef 進棧溢出abdee 退棧c 順序棧的示意圖順序棧的示意圖topc 退棧b 退棧abaa 退棧空棧topabdd 退棧ctopabctoptop棧頂指針指示實際棧頂位置即最后加入新元素的位置void InitStack (SeqStack& S) /初始化初始化 S.elem = new SElemTypeInitSize; if (S.elem = NULL) printf(“存儲分配失敗存儲分配失敗!n”); exit(1); S.top = -1; S.maxSize = InitSize; bool Stac

8、kEmpty(const SeqStack& S) /判斷棧是否空？空則返回判斷棧是否空？空則返回1，否則返回，否則返回0 return S.top = -1; bool Pop(SeqStack& S, SElemType& x) /若棧空返回若棧空返回0, 否則棧頂元素退出到否則棧頂元素退出到x并返回并返回1 if (StackEmpty(S) return 0; x = S.elemS.top; S.top-; return 1;bool getTop(SeqStack& S, SElemType& x) /若棧空返回若棧空返回0, 否則棧頂元素讀

9、到否則棧頂元素讀到x并返回并返回1 if (StackEmpty(S) return 0; x = S.elemS.top; return 1;bool StackFull(const SeqStack& S) /判斷棧是否滿？滿則返回判斷棧是否滿？滿則返回1，否則返回，否則返回0 return S.top = S.maxSize-1; void Push(SeqStack& S, SElemType x) /若棧滿返回若棧滿返回0, 否則否則新元素新元素 x 進棧并返回進棧并返回1 if (StackFull(S) OverFlow(S); /棧滿溢出處理棧滿溢出處理 S.t

10、op+; S.elemS.top = x; /加入新元素加入新元素void OverFlow(SeqStack& S) /棧滿處理 int newSize = S.maxSize+StackIncrement; SElemType *newS = new SElemTypenewSize; if (newS = NULL) printf(“數組創建失敗數組創建失敗!n”); exit(1); S.elem = newS; /新數組作為棧數組新數組作為棧數組 S.maxSize = newSize; /新數組大小新數組大小SElemType *src = S.elem, *obj = n

11、ewS; for (int i = 0; i data = x; /結點賦值 p-link = S; S = p; /鏈入棧頂bool Pop ( LinkStack& S, ElemType& x ) /退棧 if ( StackEmpty(S) ) return 0; StackNode * p = S; S = p-link; x = p-data; /摘下原棧頂 delete p; return 1; /釋放原棧頂結點 bool getTop(LinkStack& S, ElemType& x) if ( StackEmpty(S) ) return 0

12、; x = S-data; return 1; 3.3 棧的應用舉例棧的應用舉例例一、例一、 數制轉換數制轉換例二、例二、 括號匹配的檢驗括號匹配的檢驗例三、表達式求值例三、表達式求值例四、例四、 用棧實現遞歸用棧實現遞歸 例一、例一、 數制轉換數制轉換將十進制數轉換為其他進制數將十進制數轉換為其他進制數的基本方法是輾轉相除法。的基本方法是輾轉相除法。 void conversion () / conversionSeqStack S; InitStack(S); scanf(“%d”,n);while (n) Push(S, n % 8); n= n/8; (159)10=(237)8whi

13、le (!StackEmpty(S) Pop(S,e); printf ( %d, e );3 7 余 7余 3余 2Top=-1top7top73top732運算次序和輸出次序相反運算次序和輸出次序相反例二、例二、 括號匹配的檢驗括號匹配的檢驗每個右括號將與每個右括號將與最近遇到最近遇到的未匹配的未匹配的左括號相匹配，可能出現的的左括號相匹配，可能出現的不匹不匹配配的情況的情況: :(1) 到來的右括弧不是最“期待”的;例如：下列括號序列：例如：下列括號序列： （ ） 1 2 3 4 1 2 3 4例如：下列括號序列：例如：下列括號序列： ( ( ) ) 1 2 3

14、 4 5 6 1 2 3 4 5 6 (2) 到來的右括弧是“不速之客”;(3) 直到結束，也沒有到來所“期待”的右括弧;例如：下列括號序列：例如：下列括號序列： ( ) ( ) 1 2 3 4 5 1 2 3 4 5 算法的設計思想：算法的設計思想：1）凡出現左括弧左括弧，則進棧進棧；2）凡出現右括弧右括弧，首先檢查棧是否空 若棧空棧空，則表明該“右括弧右括弧”多余多余 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出棧” 否則表明不匹配不匹配3）表達式表達式檢驗結束時結束時， 若棧空棧空，則表明表達式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余從左到右掃描一個

15、字符串：status matching(char *exp) int state=1int state=1，i=0; i=0; LinkStack s; /LinkStack s; /用鏈式棧存儲左括號用鏈式棧存儲左括號while (istrlen(exp) & state) switch (expi) case : case : case ( : /左括號進棧左括號進棧 case”)”: if (StackEmpty(S)&state) return 0; /匹配成功匹配成功else return -1; /else return -1; /匹配失敗匹配失敗 push(s,e

16、xpi); i+; break; if(! StackEmpty(s)&GetTop(s)=( ) pop(S,e); i+; else state = 0; break; 1 1）問題的提出）問題的提出從鍵盤一次性輸入一串算術表達式，給出計算結果。從鍵盤一次性輸入一串算術表達式，給出計算結果。2+32+3* *(5-4)=5(5-4)=5 例三例三 算術表達式求值算術表達式求值2 2）表達式的構成）表達式的構成 操作數操作數+ +運算符運算符+ +界符界符常數常數+ +、- -、* *、/ /( )( )、# #表達式中相鄰兩個操作符的計算次序為： 優先級高的先計算； 優先級相同的自

17、左向右計算；a) 當使用括號時從最內層括號開始計算。 表達式的三種表示方法：表達式的三種表示方法：設設 Exp = S1 + OP + S2則稱則稱 OP + S1 + S2 為前綴表示法前綴表示法 S1 + OP + S2 為中綴表示法中綴表示法 S1 + S2 + OP 為后綴表示法后綴表示法 例如:中綴式：a b + (c d / e) f后綴式: a b c d e / f + 結論結論:1）操作數之間的相對次序不變）操作數之間的相對次序不變;2）運算符的相對次序不同）運算符的相對次序不同;3）中綴式要保持正確的運算次序必須加括弧; 4)后綴式的運算規則后綴式的運算規則為: 運算符在式

18、中出現的順序恰為運算符在式中出現的順序恰為 表達式的運算順序表達式的運算順序; 每個運算符和在它之前出現每個運算符和在它之前出現 且且 緊靠它的兩個操作數構成一個最小緊靠它的兩個操作數構成一個最小 表達式表達式;例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f算術表達式求值算法的設計思路：算術表達式求值算法的設計思路： 步驟步驟1： 將用戶所輸入的帶有括號將用戶所輸入的帶有括號的中綴表達式變為后綴表達式。的中綴表達式變為后綴表達式。步驟步驟2： 對后綴表達式求值。對后綴表達式求值。l如何從原表達式求得后綴式？如何從原表達式求得后綴式？每個運算符的運算次序要由

19、它之后的一個運算符它之后的一個運算符來定，在后綴式中,優先數高的運算符領先于優先數低的運算符。分析 “原表達式” 和 “后綴式”中的運算符: :原表達式: : a + b c d / e f 后綴式: a b c + d e / f 使用棧可將表達式的中綴表示轉換成它的前綴表示和后綴表示。為了實現這種轉換，需要考慮各操作符的優先級。算符優先關系表算符優先關系表 表達式中任何相鄰運算符表達式中任何相鄰運算符 1 1、 2 2 的優先關系有：的優先關系有： 1 1 2 2： 1 1的優先級的優先級 高于高于 2 2+ 2 1 - -* */( () )#+ - - * * / ( ( ) ) #

20、= 注注：1 1、2 2是相鄰算符，是相鄰算符，1 1在左，在左，2 2在右在右從原表達式求得后綴式的步驟為：從原表達式求得后綴式的步驟為：1) 設立暫存運算符的棧棧;2) 設表達式的結束符為“#”, 予設運算符棧的棧底為“#”3) 若當前字符是操作數， 則直接發送給后綴式;4) 若當前掃描位置的當前掃描位置的運算符的優先優先數高數高于棧頂運算符，則進棧;5) 否則，退出棧頂運算符發送給后綴式; 6) “(” 對它之前后的運算符起隔離作用，“)”可視為自相應左括弧開始的表達式的結束符。convert_postfix1void transform(char suffix , char exp )

21、 InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree P P指向當前掃描位置指向當前掃描位置switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c

22、); Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch棧頂元素的優先級高于當棧頂元素的優先級高于當前掃描字符的優先級前掃描字符的優先級如何從后綴式求值？如何從后綴式求值？先找運算符，先找運算符， 再找操作數再找操作數1) 設立暫存后綴表達式的操作數操作數的棧棧2) 掃描后綴表達式，當遇到操作數操作數時，將其存入棧中.3)當遇到操作符操作符時，從棧中彈出兩個棧頂元素，執

23、行算數運算后將結果壓入棧中.如何利用棧計算后綴表達式的值？如何利用棧計算后綴表達式的值？stack_calculate_postfix多個函數嵌套調用的規則是:此時的內存管理實行“棧式管理棧式管理”后調用先返回后調用先返回 ！void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數據區函數a的數據區函數b的數據區例五、利用棧實現遞歸例五、利用棧實現遞歸求解階乘函數的遞歸算法求解階乘函數的遞歸算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n *

24、Factorial (n-1);時時當當時時當當 1 ,)!1( 0 , 1!nnnnn分析遞歸函數的執行過程1. void print(int w)2. 3. if ( w=0)4. return; 5. else6. print(w-1);7. for(int i=1;i=w;+i)8. coutw“, “endl;9. 10 1，2，2，3，3，3，1. void main()2. int w=3;3. print(w);4. return;5. 運行結果？Main program4. return;print(w) w=3; 3print(2);Line=4, w=3topw2prin

25、t(1);Line=7, w=2Line=4, w=3 topw1print(0);Line=7,w=1Line=7,w=2Line=4,w=3topw0Line=7,w=1Line=7,w=2Line=4,w=3topw(3) output：2, 2Line=7, w=2Line=4, w=3top(4) output：1Line=7,w=1Line=7,w=2Line=4,w=3top(2) output：3, 3, 3 Line=4, w=3topreturnLine=7,w=1Line=7,w=2Line=4,w=3topLine=7,w=0end(1) return1. void p

26、rint(int w)2. 3. if ( w=0)4. return; 5. else6. print(w-1); for(int i=1;i=w;+i) coutw“, “CC-BB-AB-CA-C(1,A,B, C)A-B(1,C,A,B)(1,B,C,A)(1,C,A,C)(2,A,C,B)A-C(2,B,A,C)自頂向下，逐層分解遞歸算法的設計方法void recfunc ( int A , int n ) if(n=0) return; else cout An data = x ) printf printf (“%dn”, f -data ); ; else else Prin

27、t ( f - link, x ); ; f f f f 遞歸找含x值的結點x遞歸過程改為非遞歸過程 遞歸過程簡潔、易編、易懂。然而，遞歸過程效率低，重復計算多。 例如，定義一個計算斐波那契數列的遞歸函數Fib(n)如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, 求解斐波那契數列的遞歸算法為：1n2),Fib(n1)Fib(n0,1nn,Fib(n)long Fib(long n) if ( n = 1 ) return n; else return Fib(n-1) + Fib(n-2); 重復計算多Fib(1)Fib(0)

28、Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)Fib(5)Fib(5)計算計算1 1次次, Fib(4), Fib(4)計算計算1 1次次, Fib(3), Fib(3)計算計算2 2次次, Fib(2), Fib(2)計計算算3 3次次, Fib(1) , Fib(1) 計算計算5 5次次, Fib(0) , Fib(0) 計算計算3 3次。次。 改為非遞歸過程的目的是改為非遞歸過程的目的是提高效率提高效率。 單向遞歸單向遞歸和和尾遞歸尾遞歸可直接用可直接用迭代迭代實現其非實現其非遞

29、歸過程，其他情形必須借助遞歸過程，其他情形必須借助棧棧實現非遞實現非遞歸過程。歸過程。 單向遞歸單向遞歸是指遞歸過程執行時雖然可能有是指遞歸過程執行時雖然可能有多個分支，但可以保存前面計算的結果以多個分支，但可以保存前面計算的結果以供后面的語句使用。供后面的語句使用。 尾遞歸尾遞歸指程序中只有一個遞歸語句，且在指程序中只有一個遞歸語句，且在程序最后，這時遞歸棧保存的內容無需再程序最后，這時遞歸棧保存的內容無需再利用。利用。用迭代法實現斐波那契數列的計算：用迭代法實現斐波那契數列的計算：long FibIter ( long n ) if ( n = 1 ) return n; long a =

30、 0, b = 1, c; for ( int i = 2; i = 0 ) printf ( “%d”, An ); n-; recfunc( A, n ); void sterfunc( int A , int n ) /非遞歸函數 while ( n = 0 ) printf ( “ %s ”, An ); n-; 尾遞歸： ADT Queue 數據對象：數據對象： Dai | aiElemSet, i=1,2,.,n, n0 數據關系：數據關系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊列頭隊列頭， an 端為隊列尾隊列尾基本操作：基本操作：3.4 隊列的

31、隊列的ADT ADT Queue隊列的基本操作：隊列的基本操作： InitQueue(Queue&Q)DestroyQueue(Queue&Q)QueueEmpty(Queue &Q)QueueLength(Queue &Q)GetHead(QueueQ, DataType&e)ClearQueue(Queue&Q)DeQueue(Queue&Q, DataType&e )EnQueue(Queue&Q, DataType&e)QueueTravers(Queue &Q, visit()隊列類型的實現隊列類

32、型的實現鏈隊列鏈隊列鏈式映象循環隊列循環隊列順序映象#define MAXSIZE 100 /最大隊列長度typedef struct QElemType elemmaxSize; / 靜態分配存儲空間int front; / 頭指針，若隊列不空， / 指向隊列頭元素int rear; / 尾指針，若隊列不空，指向 / 隊列尾元素 的下一個位置下一個位置 SqQueue;循環隊列循環隊列順序映象仍有空余，但新仍有空余，但新元素無法插入元素無法插入設想數組的存儲空間是個設想數組的存儲空間是個 環環 ，認定，認定“55的的下一個位置是下一個位置是00。Front 指向隊列的第一個元素，rear指向

33、隊尾的下一個可插入位置實現：利用實現：利用“模模”運算運算入隊：入隊：Q.elemrear=e; Q.rear=(Q.rear+1)%MAXSIZE; 出隊：出隊：e=Q.basefront; Q.front=(Q.front+1)% MAXSIZE; 隊滿、隊空判定條件隊滿、隊空判定條件?012345rearfrontJ7J5J6012345frontJ4J9J8rearJ5J6J4012345rearfrontJ4,J5,J6出隊出隊J7,J8,J9入隊入隊隊空：隊空：front=rear解決方案：解決方案：1.另外設一個標志以區別隊空、隊滿另外設一個標志以區別隊空、隊滿2.少用一個元素空

34、間：少用一個元素空間： 隊空：隊空：Q.front=Q.rear 隊滿：隊滿：(Q.rear+1)%M=Q.front隊滿：隊滿：front=rear 進行插入運算，必須先測試隊滿與否。進行插入運算，必須先測試隊滿與否。若隊滿，若隊滿，則調用相關算法處理有關溢出問題；否則，將則調用相關算法處理有關溢出問題；否則，將隊尾指針加隊尾指針加1，然后將新元素插入到當前隊尾指，然后將新元素插入到當前隊尾指針所指的位置。針所指的位置。 刪除隊頭元素，必須先測試隊列是否為空。刪除隊頭元素，必須先測試隊列是否為空。若若隊空，則調用相關算法處理有關信息；否則，隊空，則調用相關算法處理有關信息；否則，刪除隊頭元素

35、刪除隊頭元素(隊頭指針加隊頭指針加1)，如果需要，可以，如果需要，可以把被刪除元素保存起來。把被刪除元素保存起來。Status EnQueue (SqQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 if (Q.rear+1) % MAXSIZE = Q.front) return ERROR; /隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXSIZE; return OK; Status DeQueue (SqQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素

36、， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXSIZE; return OK; typedef struct node / 結點類型結點類型 QElemType data; struct Node *link; LinkNode, QueuePtr鏈隊列鏈隊列鏈式映象typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指

37、針 LinkQueue;a1anQ.frontQ.frontQ.rear空隊列空隊列Q.rear Status InitQueue (LinkQueue &Q) / 構造一個空隊列Q Q.front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = new QNode; if (!p) exit (OVERFLOW);

38、 /存儲分配失敗 p-data = e; p-link = NULL; Q.rear-link = p; Q.rear = p; return OK;a1anQ.frontQ.rearep Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front -link=null) return ERROR; p = Q.front-link; e = p-data; Q.front-link= p-link; /隊頭修改 delete (p);

39、return OK;隊列應用示例隊列應用示例利用隊列打印二項式展開式利用隊列打印二項式展開式(a+b) n的系數，即計算的系數，即計算 n 行行楊輝三角的值楊輝三角的值第 1 行 1 1 第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二項式系數值（楊輝三角）設第 i-1行的值：(a0=0) a1.ai (ai+1=0)則第 i 行的值：bj = aj-1+aj, j=1,2,i+100000000解題方法引入引入“循環隊列循環隊列”，則可以在第，則可以在第k k行元素行元素依次出隊列打印時把下一行的元素預先放依次出隊列打印時把下一行的元素預先放入隊列，當第入隊

40、列，當第k k行元素全部出隊列時，下行元素全部出隊列時，下一行元素已經到了隊頭。一行元素已經到了隊頭。第5行的界符第4行的界符假設隊列中已存有第假設隊列中已存有第 k k 行的計算結果，為了行的計算結果，為了計算方便，在每行前添加一個計算方便，在每行前添加一個“0”0”作為作為行界行界值值。在計算第。在計算第 k+1 k+1 行之前，行之前，頭指針指向第頭指針指向第 k k 行的行的“0”0”。尾指針指向第。尾指針指向第k+1k+1行的行的“0 0”的下的下一個位置一個位置計算楊輝三角的基本操作計算楊輝三角的基本操作do DeQueue(Q, s); / / s 為第為第 k k 行行 “ “

41、左上方左上方”的值的值GetHead(Q, e); / / e 為第為第 k k 行行 “ “右上方右上方”的值的值coute；/ / 輸出輸出 e 的值的值 EnQueue(Q, s+e);/ / 第第 k+1 行的值入隊列行的值入隊列 while (e!=0); EnQueue(Q,0); /0作為第作為第k+2行的行界符行的行界符多維數組是一種非線性結構。其特點是每一個數據元素可以有多個直接前驅和多個直接后繼。mnmmnnnmaaaaaaaaaA.212222111211 數組特點數組特點 數組結構固定 數據元素同構 數組運算數組運算 給定一組下標，存取相應的數據元素 給定一組下標，修改

42、數據元素的值( )( )( )( )( )( )( )( )( )多維數組的存儲和表示多維數組的存儲和表示數組的類型特點數組的類型特點:1) 只有引用型操作，沒有加工型操作;2) 數組是多維的結構，而存儲空間是 一個一維的結構。3）多維數組實際上是用一維數組來存儲的，只要能計算出多維數組中數組元素在相應一維數組中的位置，就可以據此直接存取相應數據元素。 按行序為主序存放按行序為主序存放01n-1m-1*n-1n am-1,n-1 . am-1,1 am-1,0 . a1,n-1 . a1,1 a1,0 a0,n-1 . a0,1 a0,0 a0,0 a0,1 . a0,n-1 a1,0 a1,

43、1 . a1,n-1 am-1,0 am-1,1 . am-1n -1 .Loc(aij)=Loc(a0,0)+i*n+j*l L 按列序為主序存放按列序為主序存放01m-1m-1*n-1m am-1,n-1 . a1,n-1 a0,n-1 . am-1,1 . a1,1 a0,1 am-1,0 . a1,0 a0,0 a0,0 a0,1 . a0,n-1 a1,0 a1,1 . a1,n-1 am-1,0 am-1,1 . am-1n -1 .Loc(aij)=Loc(a0,0)+j*m+i*LL1) 非零元的分布有一定規律非零元的分布有一定規律 非零元在矩陣中的分布有一定規則 例如: 三角

44、矩陣 對角矩陣2) 隨機稀疏矩陣隨機稀疏矩陣 非零元在矩陣中隨機出現有兩類特殊矩陣有兩類特殊矩陣：特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲對稱矩陣的壓縮存儲 設有一個設有一個 n n n n 的矩陣的矩陣 A A。如果在。如果在在矩陣中，在矩陣中，a aij ij = a= aji ji，則此矩陣是對稱矩陣，則此矩陣是對稱矩陣。若只保存對稱矩陣的對角線和對角線以上若只保存對稱矩陣的對角線和對角線以上 ( (下下) ) 的元素，則稱此為對稱矩陣的壓縮存儲。的元素，則稱此為對稱矩陣的壓縮存儲。11nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaa

45、aA11nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaaa 若只存對角線及對角線以上的元素，稱為上三若只存對角線及對角線以上的元素，稱為上三角矩陣；若只存對角線或對角線以下的元素，角矩陣；若只存對角線或對角線以下的元素，稱之為下三角矩陣。稱之為下三角矩陣。下三角矩陣上上三三角角矩矩陣陣 把它們按行存放于一個一維數組把它們按行存放于一個一維數組 B B 中，稱中，稱之為對稱矩陣之為對稱矩陣 A A 的壓縮存儲方式。的壓縮存儲方式。 數組數組 B B 共有共有 n+(n-1)+n+(n-1)+1 = +1 = n n* *(n+1)/2 (

46、n+1)/2 個個元素。元素。11nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaaa11nn12n11n10n12n22212011n12111010n020100aaaaaaaaaaaaaaaa下下三三角角矩矩陣陣B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1 若若 ijij, , 數組元素數組元素AijAij在數組在數組B B中的存放位置為中的存放位置為 1 + 2 + + i + j = (i + 1)* i / 2 + j前前i

47、-1行行元素總數元素總數第第i行第行第j個個元素前元素個數元素前元素個數反過來，反過來，若已知某矩陣元素位于數組若已知某矩陣元素位于數組 B B 的第的第 k k 個個位置，可尋找滿足位置，可尋找滿足 i (i + 1) / 2i (i + 1) / 2 k k (i + 1) (i + 1)* *(i + 2) / 2(i + 2) / 2的的 i i, , i i即為即為該元素的行號。該元素的行號。 j = k - i j = k - i * * (i + 1) / 2 (i + 1) / 2此即為該元素的列號。此即為該元素的列號。 例，當例，當 k = 8k = 8, , 3 3* *4

48、 / 2 = 4 / 2 = 6 6 k k 4 4* *5 / 2 =5 / 2 =1010，取，取 i = 3i = 3。則則 j = 8 - 3j = 8 - 3* *4 / 2 = 24 / 2 = 2。若若 i ij j，數組元素，數組元素 Aij Aij 在矩陣的上三角部分在矩陣的上三角部分, , 在在數組數組 B B 中沒有存放，可以找它的對稱元素中沒有存放，可以找它的對稱元素Aji = j Aji = j * *( j +1 ) / 2 + i( j +1 ) / 2 + i 第i行首元素的位置第i+1行首元素的i i位置若若 ijij，數組元素，數組元素AijAij在數組在數

49、組B B中的存放位置為中的存放位置為n + (n-1) + (n-2) + + (n-i+1) + j-i33323130232221201312111003020100aaaaaaaaaaaaaaaa上上三三角角矩矩陣陣B a00 a01 a02 a03 a11 a12 a13 a22 a23 a33 0 1 2 3 4 5 6 7 8 9n = 4前前i-1行行元素總數元素總數 若若 ijij，數組元素，數組元素AijAij在數組在數組B B中的存放中的存放位置為位置為 n + (n-1) + (n-2) + n + (n-1) + (n-2) + + (n-i+1) + j-i = +

50、(n-i+1) + j-i = = (2 = (2* *n-i+1) n-i+1) * * i / 2 + j-i = i / 2 + j-i = = (2(2* *n-i-1) n-i-1) * * i / 2 + j i / 2 + j 若若i ij j，數組元素，數組元素AijAij在矩陣的下三角部在矩陣的下三角部分，在數組分，在數組 B B 中沒有存放。因此，找它的中沒有存放。因此，找它的對稱元素對稱元素AjiAji。AjiAji在數組在數組 B B 的第的第 (2(2* *n-j-1) n-j-1) * * j / 2 + i j / 2 + i 的位置中找到。的位置中找到。三對角矩

51、陣的壓縮存儲三對角矩陣的壓縮存儲11nn21nn12nn22nn32nn2322211211100100aa0000aaa00000aaa0000aaa0000aaAB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10第一行第二行第n行第三行只有主對角線及其上 下最臨近的兩條對角線上的元素不為0。總共有3n-2個非零元素。 將三對角矩陣A中三條對角線上的元素按行存放在一維數組 B 中，且a00存放于B0。 在三條對角線上的元素aij 滿足 0 i n-1, i-1 j i+1 在一維數組 B 中 Aij

52、 在第 i 行，它前面有 3*i-1 個非零元素, 在本行中第 j 列前面有 j-（i-1）個元素，所以元素 Aij 在 B 中位置為： k =3i-1+j-(i-1)= 2i + j定義：非零元較零元少，且分布沒有定義：非零元較零元少，且分布沒有一定規律的矩陣一定規律的矩陣. 2) 2) 隨機稀疏矩陣隨機稀疏矩陣nmt假設假設 m m 行行 n n 列列的矩陣含的矩陣含t t個非零元素個非零元素，則稱則稱為為稀疏因子稀疏因子通常認為通常認為 0.05 0.05 的矩陣為稀疏矩陣的矩陣為稀疏矩陣 以常規方法，即以一維數組表示以常規方法，即以一維數組表示高階的稀疏矩陣時產生的問題高階的稀疏矩陣時

53、產生的問題:1) 零值元素占了很大空間零值元素占了很大空間;2) 計算中進行了很多和零值的運算，計算中進行了很多和零值的運算， 遇除法，還需判別除數是否為零遇除法，還需判別除數是否為零;1) 盡可能少存或不存零值元素盡可能少存或不存零值元素;解決問題的原則解決問題的原則:2) 盡可能減少沒有實際意義的運算盡可能減少沒有實際意義的運算;3) 操作方便操作方便; 即即: 能盡可能快地找到能盡可能快地找到 與下標值與下標值 (i, j) 對應的元素對應的元素; 能盡可能快地找到能盡可能快地找到 同一行或同一列的非零值元同一行或同一列的非零值元;隨機稀疏矩陣的壓縮存儲方法隨機稀疏矩陣的壓縮存儲方法:一

54、、三元組順序表一、三元組順序表二、行邏輯聯接的順序表二、行邏輯聯接的順序表三、三、 十字鏈表十字鏈表三元組順序表：只存矩陣的行列維數和三元組順序表：只存矩陣的行列維數和每個非零元的行列下標及其值每個非零元的行列下標及其值7600070015000001800000240001400003000000000009120MMM由由( (1 1, ,2 2,12), (,12), (1 1, ,3 3,9), (,9), (3 3, ,1 1,-3), (,-3), (3 3, ,6 6,14), (,14), (4 4, ,3 3,24), ,24), ( (5 5, ,2 2,18), (,18

55、), (6 6, ,1 1,15), (,15), (6 6, ,4 4,-7) ,-7) , ,矩陣維數（矩陣維數（6,76,7）和非零元個數和非零元個數唯一確定唯一確定 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行下標和列下標 ElemType e; / 該非零元的值 Triple; / 三元組類型三元組類型一、一、三元組順序表三元組順序表矩陣的順序存儲結構矩陣的順序存儲結構typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; /矩陣的行數，列數和非零元個數矩陣的行數，列

56、數和非零元個數 TSMatrix; / 稀疏矩陣類型稀疏矩陣類型1 2 121 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j e0 1 2 3 4 5 6 7行列下標行列下標非零元值非零元值7600070015000001800000240001400003000000000009120M以行序為主序：mu=6Nu=7Tu =8如何求轉置矩陣？如何求轉置矩陣？028003600070500140005280000007143600如果用常規的二維數組表示，則算法為： 其時間復雜度為其時間復雜度為: O(munu) for (col=1;

57、 col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;用“三元組”表示如何實現？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 281. 將矩陣的行列值相互交將矩陣的行列值相互交換換2. 2. 將每個元組中的將每個元組中的i i和和j j的值相互調換的值相互調換3. 3. 重排三元組之間的次序重排三元組之間的次序7600070015000001800000240001400003000000000009120M670000000001400000000700000

58、0024009018000121500300N6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v 0 1 2 3 4 5 6 7 8mai j v7 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 0 1 2 3 4 5 6 7 8mb?可用0號單元存儲矩陣的行列數和非零元個數方法一：按方法一：按MM的的列序列序轉置轉置即按即按mbmb中三元組次序依次在中三元組次序依次在mama中找到相中找到相應的三元組進行轉置。應的三元組進行轉置。為找到為找

59、到MM中每一列所有非零元素，需對其中每一列所有非零元素，需對其三元組表三元組表mama從第一行起掃描一遍。從第一行起掃描一遍。6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 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 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=2Status TransposeMatrix(TSMatrix M, T

60、SMatrix &T) /采用三元組表存儲表示，求稀疏矩陣采用三元組表存儲表示，求稀疏矩陣MM的轉置矩陣的轉置矩陣T TT.mu=M.mu; T.nu=M.nu; T.tu=M.tu;if(T.tu) q=1;for(col=1;col=M.nu;col+) for(p=1;p=M.tu; +p) if(M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return Success; /TransposeMatrix算法分析：算法分析：T(n)=O(MT(n)=O(M的列數的列數n n 非零元個數非零元個數t) t)。若若 t t 與與m m n n同數量級，則同數量級，則T(n)=O(mT(n)=O(m* *n n2 2) )方法二：快速轉置方法二：快速轉置即按即按mama中三元組次序轉置，轉置結果放入中三元組次序轉置，轉置結果放入mbmb中恰當位置中恰當位置此法關鍵是要預先確定此法關鍵是要預先確定矩陣矩陣mama中每一列第