特殊線性結(jié)構(gòu)[1頁]課件

1、1第三章 特殊線性表河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院丁海軍3.1 棧3.2 隊列3.3 特殊矩陣3.4 稀疏矩陣3.5 廣義表233.1 棧（stack）3.1.1 棧的定義和特點3.1.2 棧的表示和實現(xiàn)3.1.3 棧應(yīng)用43.1.1 棧的定義和特點定義：限定僅在表尾進行插入或刪除操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧特點：先進后出（FILO）或后進先出（LIFO）ana1a2.棧底棧頂.出棧進棧棧s=(a1,a2,an)push(e)pop()clear()gettop()isempty()棧的基本操作53.1.2 棧的表示和實現(xiàn)順序棧：用一維數(shù)組實現(xiàn)top=-1123450棧空棧頂

2、指針top,指向?qū)嶋H棧頂后的空位置，初值為-1top123450進棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,棧空，此時出棧，則下溢（underflow)top=M-1,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誴ublic class Stack protected int num,top;protected Object data;public Stack(int num)this.num=num; top=-1;data=new Objectnum; public boolean i

3、sEmpty() return top=-1; public boolean isFull() return top=num-1; public void push(T e) public T pop() public T top() public int length() return top+1; public int maxSize() return num; /取得棧的實際容量public Object toArray() public E toArray(E a) 6public void push(T e) if(topnum-1)top+;datatop=e;else throw

4、 new Exception(棧已滿！);public T pop() throws Exceptionif(!isEmpty()return (T)datatop-;else throw new Exception(棧已空!);public T top() throws Exceptionif(!isEmpty()return (T)datatop;else throw new Exception(棧已空!);7public Object toArray() Object a=new Objecttop+1; for (int i=0; i=top; i+) ai = datai; retu

5、rn a; public E toArray(E a) if (a.length = top) a = (E)java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), top+1); int i = 0; Object result = a; for (i=0; i top+1) atop+1 = null; return a; 893.1.2 棧的表示和實現(xiàn)鏈棧：用鏈表實現(xiàn)棧功能棧頂 .topdata棧底結(jié)點定義入棧算法出棧算法 .棧底toptopxtop .棧底topq繼承方式實現(xiàn)鏈棧public class

6、 LinkStack extends LinkList public LinkStack() super();public void push(T x)addFront(x);public T pop()return removeFront();public T top()return get(0);10聚合方式實現(xiàn)鏈棧public class LinkStack private LinkList list;public LinkStack() list=new LinkList();public void push(T x)list.addFront(x);public T pop()ret

7、urn list.removeFront();public T top()return list.get(0);11123.1.3 棧的應(yīng)用數(shù)制轉(zhuǎn)換回文游戲括號匹配檢驗表達式求值13例 把十進制數(shù)1348轉(zhuǎn)換成八進制數(shù)（原理： N = (N div d)d + N mod d ）top405 N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 22toptoptoptop(1348)10=(2504)8數(shù)字轉(zhuǎn)換14順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較 若不等，非回文 若

8、直到棧空都相等，回文字符串：“madam im adam”回文游戲15表達式 := (操作數(shù)) + (運算符) + (操作數(shù))操作數(shù) := 簡單變量 | 表達式簡單變量 : = 標(biāo)識符 | 無符號整數(shù)表達式的三種標(biāo)識方法：設(shè) Exp = S1 + OP + S2則稱 OP + S1 + S2 為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法 表達式求值（限于二元運算符的表達式定義）16例如: Exp = a b + (c d / e) f前綴式: + a b c / d e f中綴式: a b + c d / e f后綴式: a b c d e /

9、f + 三種表達式小結(jié)操作數(shù)之間的相對次序不變運算符的相對次序不同;中綴式丟失了括弧信息， 致使運算的次序不確定;17前綴式的運算規(guī)則為:Exp = a b + (c d / e) f前綴式: + a b c / d e f連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式;后綴式的運算規(guī)則為:Exp = a b + (c d / e) f后綴式: a b c d e / f + 運算符在式中出現(xiàn)的順序恰為表達式的運算順序; 每個運算符和在它之前且緊靠它的兩個操作數(shù)構(gòu)成一個最小 表達式。18如何從后綴式求值？例： a b c d e / f +abd/ec-d/e(c-d/e

10、)f運算規(guī)則連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式;先找運算符再找操作數(shù)19double evaluation( char suffix ) / 本函數(shù)返回由后綴式suffix表示的表達式的運算結(jié)果 ch = *suffix+; SeqStack S=new SeqStack(20); / 設(shè)置空棧S while ( ch != # ) if (!OpMember(ch) /函數(shù)OpMember() 用于判斷ch是否是操作符 S.push(ch ); / 非運算符入操作數(shù)棧 else b=S.Pop(b); a=S.pop(a); / 退出棧頂兩個操作數(shù) S.pu

11、sh(Operate(a, ch, b); / 作相應(yīng)運算，并將運算結(jié)果入棧 ch= *suffix+; / 繼續(xù)取下一字符 result=S.pop(S,result); return result; / evalution20 每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先數(shù)高的運算符領(lǐng)先于優(yōu)先數(shù)低的運算符。分析 “原表達式” 和 “后綴式”中的運算符:原表達式: a + b c d / e f 后綴式: a b c + d e / f 如何從原表達式求得后綴式？21從常規(guī)表達式求得后綴式的步驟為操作符設(shè)一個棧S；設(shè)常規(guī)表達式的結(jié)束符為“#”，予設(shè)棧S的棧底為“#”；Ch

12、=getchar(),表示從常規(guī)表達式取得的當(dāng)前字符若ch操作數(shù)，則直接發(fā)送給后綴式。若ch是操作符，將其與棧頂操作符比較：如果ch的優(yōu)先級高于棧頂運算符優(yōu)先級，ch進棧；如果ch的優(yōu)先級低于棧頂運算符優(yōu)先級，棧頂操作符出棧，并送往后綴式；如果 ch的優(yōu)先級等于棧頂運算符優(yōu)先級，視情況作不同的處理22操作符優(yōu)先級關(guān)系表23/比較操作符ch1與ch2的優(yōu)先級char express:comp(char ch1,char ch2)int i,j;char *opr= , , , , s, s= ;i=getindex(ch1);j=getindex(ch2);return oprij;24253.

13、1.4 棧與遞歸263.2 隊列3.2.1 隊列的定義及特點3.2.2 隊列的鏈?zhǔn)酱鎯︽滉犃?.2.3 隊列的順序存儲循環(huán)隊列3.2.4 隊列的應(yīng)用273.2.1 隊列的定義及特點定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表隊尾(rear)允許插入的一端隊頭(front)允許刪除的一端隊列特點：先進先出(FIFO)a1 a2 a3.an 入隊出隊frontrear隊列Q=(a1,a2,an)雙端隊列a1 a2 a3.an 端1端2入隊出隊入隊出隊抽象數(shù)據(jù)類型Queue實例數(shù)據(jù)：存儲數(shù)據(jù)元素的線性表，隊頭指針、隊尾指針操作：isEmpty( )：如果堆棧為空則返回true

14、，否則返回falseisFull( )：如果堆棧滿，則返回true，否則返回falsefront ( )：返回隊頭元素，但不刪除隊頭add (x)：向隊列中添加元素xremove ( )：從隊頭刪除元素，并將它返回 28293.4.2 隊列的鏈存儲鏈隊列頭結(jié)點 .front隊頭隊尾rear設(shè)隊首、隊尾指針front和rear,front指向頭結(jié)點，rear指向隊尾30frontrearx入隊xfrontreary入隊xyfrontrearx出隊xyfrontrear空隊frontreary出隊3.4.2 隊列的鏈存儲鏈隊列繼承方式實現(xiàn)鏈?zhǔn)疥犃衟ublic class LinkQue exten

15、ds LinkList public LinkQue() super();public T front () /取隊首元素return get(0);/*下面三個操作，在鏈表中已經(jīng)實現(xiàn)，直接繼承即可，不用重復(fù)實現(xiàn)public void add (T x); /元素進隊public T remove ()； /元素出隊 public boolean isEmpty() /判斷隊列是否空 */31聚合方式實現(xiàn)鏈?zhǔn)疥犃衟ublic class LinkQue private LinkList list;public LinkQue() list=new LinkList(); public T fr

16、ont ()return list.get(0);public void add (T x)list.add(x);public T remove ()return list.remove(0);public boolean isEmpty()return list.isEmpty(0);32333.4.3 隊列的順序存儲結(jié)構(gòu)簡單順序隊列：用一維數(shù)組實現(xiàn)sqMfront=0rear=0123450隊空123450frontJ1,J1,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設(shè)兩個指針front,rear,約定：rear指示隊尾元素的下一位置；f

17、ront指示隊頭元素初值front=rear=0空隊列條件：front=rear入隊列：sq+rear=x;出隊列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfront34存在問題設(shè)數(shù)組維數(shù)為M，則：當(dāng)front=0,rear=M-1時，再有元素入隊發(fā)生溢出真溢出當(dāng)front0,rear=M-1時，再有元素入隊發(fā)生溢出假溢出解決方案隊首固定，每次出隊時，剩余元素向隊頭移動浪費時間循環(huán)隊列35循環(huán)隊列基本思想：把隊列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0實現(xiàn)：利用“?！边\算入隊：

18、rear=(rear+1)%M; sqrear=x;出隊： front=(front+1)%M; x=sqfront;隊滿、隊空判定條件0M-11frontrear.36012345rearfrontJ5J6J7012345rearfrontJ4J9J8rearJ4J5J6501234front初始狀態(tài)J4,J5,J6出隊J7,J8,J9入隊隊空：front=rear隊滿：front=rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊空、隊滿2.少用一個元素空間： 隊空：front=rear 隊滿：(rear+1)%M=front012345frontJ5J6J7J4J8rear隊空隊滿public

19、 class SeqQue private int front,rear,maxSize;Object data;public SeqQueue(int maxQueueSize)maxSize=maxQueueSize+1; front=rear=0; data=new ObjectmaxSize;public boolean isEmpty()return (front=rear);public boolean isFull()return (rear+1)%maxSize=front;public void add (T e) throws Exceptionif(isFull() th

20、row new Exception(隊列已滿);datarear=e; rear=(rear+1)%maxSize;public T remove() throws Exception T temp;if(isEmpty() throw new Exception(隊列已空！); temp=(T)datafront; front=(front+1)%maxSize;return temp;37383.3.4 隊列應(yīng)用劃分子集問題(等價類)問題描述：已知集合A=a1,a2,an，及集合上的關(guān)系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai與aj間存在沖突關(guān)系。要求將A

21、劃分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均無沖突關(guān)系，同時要求子集個數(shù)盡可能少39例 A=1,2,3,4,5,6,7,8,9 R= (1,2), (2,5), (2,6), (2,8), (2,9), (3,6), (3,7), (4,5), (4,9), (5,6), (5,7), (5,9), (6,7) 可行的子集劃分為： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10

22、1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=沖突關(guān)系矩陣 rij=1, i,j有沖突 rij=0, i,j無沖突40算法思想：利用循環(huán)篩選。從第一個元素開始，凡與第一個元素?zé)o沖突的元素劃歸一組；再將剩下的元素重新找出互不沖突的劃歸第二組；直到所有元素進組所用數(shù)據(jù)結(jié)構(gòu)沖突關(guān)系矩陣R=rijrij=1, i,j有沖突rij=0, i,j無沖突循環(huán)隊列Qn數(shù)組resultn存放每個元素分組號41算法過程初始狀態(tài)：A中元素放于Q中，result和newr數(shù)組清零，組號group=1第一個元素出隊，將r矩陣中第一

23、行與newr中對應(yīng)元素相加，這樣，凡與第一個元素有沖突的元素在newr中對應(yīng)位置處均為非0，下一個元素出隊。若其在newr中對應(yīng)位置為非0，有沖突，重新插入Q隊尾，參加下一次分組若其在newr中對應(yīng)位置為0, 無沖突，可劃歸本組；再將r矩陣中該元素對應(yīng)行newr中對應(yīng)元素相加如此反復(fù)，直到9個元素依次出隊，由newr中為“0”的單元對應(yīng)的元素構(gòu)成第1組,將組號group值“1”寫入result對應(yīng)單元中令group=2,newr清零，對Q中元素重復(fù)上述操作，直到Q中front=rear,即隊空，運算結(jié)束420 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0

24、1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 Q0 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 newr0 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 result430 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1

25、 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 Q 1 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 newr1 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,

26、5,6,7,8,91出隊,分組440 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=3 4 5 6 7 8 9 21 2 3 4 5 6 7 8 9 Q1 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (

27、5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,92出隊，末分組2與1有沖突 1 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 newr450 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=4 5 6 7 8 9 21 2 3 4 5 6 7 8 9 Q0

28、 1 0 0 0 1 1 0 01 2 3 4 5 6 7 8 9 newr1 0 1 0 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,93出隊，分組460 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0

29、00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=5 6 7 8 9 21 2 3 4 5 6 7 8 9 Q0 1 0 0 1 1 1 0 11 2 3 4 5 6 7 8 9 newr1 0 1 1 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,94出隊，分組470 1 0 0 0 0 0 0

30、00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 7 8 9 251 2 3 4 5 6 7 8 9 Q1 0 1 1 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3

31、) A=1,2,3,4,5,6,7,8,95出隊，末分組0 1 0 0 1 1 1 0 11 2 3 4 5 6 7 8 9 newr480 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=7 8 9 25 61 2 3 4 5 6 7 8 9 Q1 0 1 1 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,

32、8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,96出隊，末分組0 1 0 0 1 1 1 0 11 2 3 4 5 6 7 8 9 newr490 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1

33、1 0 1 1R=8 9 25 6 71 2 3 4 5 6 7 8 9 Q1 0 1 1 0 0 0 0 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,97出隊，末分組0 1 0 0 1 1 1 0 11 2 3 4 5 6 7 8 9 newr500 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1

34、0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 25 6 71 2 3 4 5 6 7 8 9 Q1 0 1 1 0 0 0 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,98出隊，分組0 1 0 0 1 1 1 0 11 2

35、 3 4 5 6 7 8 9 newr510 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=25 6 7 91 2 3 4 5 6 7 8 9 Q0 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 newr1 0 1 1 0 0 0 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4),

36、(2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,99出隊，末分組第一輪結(jié)束，（1,3,4,8)分為第一組現(xiàn)在開始第二輪，2先單獨分為一組520 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=5 6 7

37、 91 2 3 4 5 6 7 8 9 Q1 0 0 0 1 1 0 1 11 2 3 4 5 6 7 8 9 newr1 2 1 1 0 0 0 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,92出隊，分組530 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1

38、 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 7 9 51 2 3 4 5 6 7 8 9 Q1 2 1 1 0 0 0 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,95出隊，末分組1 0 0 0 1 1 0 1 11 2 3 4 5 6 7 8 9 new

39、r540 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=7 9 5 61 2 3 4 5 6 7 8 9 Q1 2 1 1 0 0 0 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7

40、,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,96出隊，末分組1 0 0 0 1 1 0 1 11 2 3 4 5 6 7 8 9 newr550 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 5 61 2 3 4 5 6 7 8 9 Q1 2 1 1 0 0 2 1 01 2 3 4 5 6 7 8 9 r

41、esultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,97出隊，分組1 0 0 0 1 1 0 1 11 2 3 4 5 6 7 8 9 newr560 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 0

42、1 0 0 0 1 1 0 1 1R=5 6 91 2 3 4 5 6 7 8 9 Q0 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 0 0 2 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,99出隊，末分組第二輪結(jié)束，（2,7)分為第二組現(xiàn)在開始第三輪，5先單獨分為一組570 1 0 0 0 0 0 0 00 1 0 1

43、 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 91 2 3 4 5 6 7 8 9 Q0 1 0 1 0 1 1 0 11 2 3 4 5 6 7 8 9 newr1 2 1 1 3 0 2 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (

44、7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,95出隊，分組580 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=9 61 2 3 4 5 6 7 8 9 Q0 1 0 1 1 0 0 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 3 0 2 1 01 2 3 4 5 6 7

45、8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,96出隊，末分組590 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=6 91 2 3 4 5 6

46、 7 8 9 Q0 0 0 0 0 0 0 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 3 0 2 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,99出隊，末分組第三輪結(jié)束，（5)分為第三組現(xiàn)在開始第四輪，6先單獨分為一組600 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1

47、0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=91 2 3 4 5 6 7 8 9 Q0 1 1 0 1 0 1 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 3 4 2 1 01 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6

48、,7,8,96出隊，分組610 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=1 2 3 4 5 6 7 8 9 Q0 1 0 1 1 0 0 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 3 4 2 1 41 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (

49、2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,99出隊，分組621 2 3 4 5 6 7 8 9 Q0 1 0 1 1 0 0 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 3 4 2 1 41 2 3 4 5 6 7 8 9 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) A=1,2,3,4,5,6,7,8,9可

50、行的子集劃分為： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 隊列已空，結(jié)束63void division ( int R , int n, int result ) / 已知 Rnn 是編號為 0 至 n-1 的 n 個元素的關(guān)系矩陣，子集劃分的結(jié)果 / 記入result 數(shù)組，resultk 的值是編號為 k 的元素所屬組號 pre = n; group = 0; InitQueue_Sq ( Q, n ); / 設(shè)置最大容量為 n 的空隊列 for ( e =1; e =n; e+ ) EnQueue_Sq ( Q, e ); while ( !QueueEmpt

51、y ( Q ) ) DeQueue_Sq ( Q, i ); if ( i =pre ) group +; / 增加一個新的組 for ( j = 1; j =n; j + ) newrj = 0; if ( newri = 0 ) resulti = group; / 編號為i 的元素入group 組 for ( j = 1; j =n; j + ) newrj += Rij; / 添加和 i沖突的信息 else EnQueue ( Q, i ); / 編號為i 的元素不能入當(dāng)前組 pre = i; / while/ division64思考題一個農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南

52、岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫能撐船。因為狼吃羊，羊吃白菜，所以農(nóng)夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。請問農(nóng)夫該采取什么方案才能將所有的東西運過河呢？65求解這個問題的最簡單的方法是一步一步進行試探，每一步都搜索所有可能的選擇，對前一步合適的選擇再考慮下一步的各種方案。要模擬農(nóng)夫過河問題，首先需要對問題中每個角色的位置進行描述。一個很方便的辦法是用四位二進制數(shù)順序分別表示農(nóng)夫、狼、白菜和羊的位置。用0表示農(nóng)夫或者某東西在河的南岸，1表示在河的北岸。例如整數(shù)5(其二進制表示為0101) 表示農(nóng)夫和白菜在河的

53、南岸，而狼和羊在北岸。還應(yīng)該分析問題中所有角色的各種可能位置構(gòu)成的狀態(tài)，哪些是安全的哪些是不安全的。根據(jù)原題可知，單獨留下白菜和羊，或單獨留下狼和羊在某一岸的狀態(tài)是不安全的?，F(xiàn)在問題變成：從初始狀態(tài)二進制0000(全部在河的南岸) 出發(fā)，尋找一種全部由安全狀態(tài)構(gòu)成的狀態(tài)序列，它以二進制1111(全部到達河的北岸) 為最終目標(biāo)，并且在序列中的每一個狀態(tài)都可以從前一狀態(tài)通過農(nóng)夫（可以帶一樣?xùn)|西）劃船過河的動作到達。為避免不必要的瞎費功夫，要求在序列中不應(yīng)該出現(xiàn)重復(fù)的狀態(tài)663.3 特殊矩陣定義矩陣的特點矩陣結(jié)構(gòu)固定矩陣元素同構(gòu)矩陣運算（兩個最重要的運算）給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)

54、，修改數(shù)據(jù)元素的值1 矩陣的定義和特點67矩陣的存儲方式以行序為主序以列序為主序重點：對于矩陣A=aijm*n 不同存儲方式下，元素aij的存儲位置計算2 矩陣的順序表示和實現(xiàn)683 特殊矩陣的存儲表示對稱矩陣a11 a12 a13 . a1n . a22 a23 . ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：（左下角）（右上角）69三角矩陣a11 a21 a22 a31 a32 an1 ann .k=1 2 3 4 5 n(n-1)/2+1 n(n+1)/2 按行序為主序：70對角矩陣Loc(aij)=Loc(a11)+2(i-1)+(j-1)*

55、L a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：或713.4 稀疏矩陣定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩陣維數(shù)（6,7）唯一確定壓縮存儲原則：只存矩陣的行列維數(shù)和每個非零元的行列下標(biāo)及其值723.4.1 三元組稀疏矩陣的每個非零元素有三個要素：行號，列號，元素值。將這三個要素稱為矩陣元素三元組：矩陣元素三元組=（i,j,val

56、ue）這里，i是行號，j是列號，value是矩陣元素值。下面給出用java類描述的三元組。73743.4.2 矩陣抽象數(shù)據(jù)類型矩陣操作在科學(xué)和工程中有著廣泛的應(yīng)用，矩陣的加、減、乘 、求逆運算，求矩陣、的特征值與特征向量，奇異值分解等運算在科學(xué)個工程計算中起著重要重要。因為本課程只主要關(guān)心的是稀疏矩陣的元素存取操作，讀矩陣的各種運算，親讀者根據(jù)需要添加。753.4.3 稀疏矩陣的三元組順序表表示順序表表示稀疏矩陣就是將矩陣的所有非零元素的三元組存放在一個順序表中。例如圖3 14(a)所示的稀疏矩陣M67，用三元組順序表表示如圖3 14(b)所示。三元組順序表表示的特點:三元組順序表表示有一個基

57、本要求:在三元組順序表中的三元組先按行號排序,行號相同時,在按列號排序，這符合按行優(yōu)先順序存放。在訪問數(shù)組元素時，可用二分查找方法，查找一個元素時間為O(log_2t_(u )。若行下標(biāo)、列下標(biāo)與值均占用一個存儲單元，非零元素個數(shù)為t_u,那么這種存儲方式需要3t_u個存儲單元。767778798081828384 M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0 T = 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0

58、0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 稀疏矩陣轉(zhuǎn)置運算稀疏矩陣轉(zhuǎn)置運算問題描述：已知一個稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表85問題分析：一般矩陣轉(zhuǎn)置算法void transpose1(int M , int T ) /普通矩陣轉(zhuǎn)置 for(col=0;coln; col+) for(row=? ; rowm; row+) Tcolrow=Mrowcol;特點：行、列下標(biāo)交換T（n）=O(m*n)86i j e123456783 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14M.data

59、i j e012345672 1 124 6 -71 3 -33 4 241 6 153 1 96 3 142 5 18T.data矩陣M的三元組順序表轉(zhuǎn)置矩陣T的三元組順序表規(guī)律?87解決思路：只要做到將矩陣行、列維數(shù)互換將每個三元組中的i和j相互調(diào)換重排三元組次序，使M中元素以T的行(M的列)為主序方法一：以T為基準(zhǔn)，“按需點菜”方法二：以M為基準(zhǔn)，“按位就坐？88方法一：以T為基準(zhǔn)，“按需點菜”算法：對M.data從頭至尾掃描：第一次掃描時，將M.data中列號為1的三元組賦值到T.data中第二次掃描時，將M.data中列號為2的三元組賦值到T.data中依此類推，直至將M.data所

60、有三元組賦值到T.data中89i j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7i j v3 1 -32 5 181 3 -36 1 151 6 151 2 122 1 125 2 181 3 93 1 94 3 243 4 246 4 -74 6 -73 6 146 3 14M.dataT.data對M六次掃描完成轉(zhuǎn)置運算第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素90/轉(zhuǎn)置運算算法void transpose