![特殊線性結(jié)構(gòu)[1頁]課件_第1頁](http://file4.renrendoc.com/view/5614e0cae45442a4dc28276d15206ed1/5614e0cae45442a4dc28276d15206ed11.gif)
![特殊線性結(jié)構(gòu)[1頁]課件_第2頁](http://file4.renrendoc.com/view/5614e0cae45442a4dc28276d15206ed1/5614e0cae45442a4dc28276d15206ed12.gif)
![特殊線性結(jié)構(gòu)[1頁]課件_第3頁](http://file4.renrendoc.com/view/5614e0cae45442a4dc28276d15206ed1/5614e0cae45442a4dc28276d15206ed13.gif)
![特殊線性結(jié)構(gòu)[1頁]課件_第4頁](http://file4.renrendoc.com/view/5614e0cae45442a4dc28276d15206ed1/5614e0cae45442a4dc28276d15206ed14.gif)
![特殊線性結(jié)構(gòu)[1頁]課件_第5頁](http://file4.renrendoc.com/view/5614e0cae45442a4dc28276d15206ed1/5614e0cae45442a4dc28276d15206ed15.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、1第三章 特殊線性表河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院丁海軍3.1 棧3.2 隊(duì)列3.3 特殊矩陣3.4 稀疏矩陣3.5 廣義表233.1 棧(stack)3.1.1 棧的定義和特點(diǎn)3.1.2 棧的表示和實(shí)現(xiàn)3.1.3 棧應(yīng)用43.1.1 棧的定義和特點(diǎn)定義:限定僅在表尾進(jìn)行插入或刪除操作的線性表,表尾棧頂,表頭棧底,不含元素的空表稱空棧特點(diǎn):先進(jìn)后出(FILO)或后進(jìn)先出(LIFO)ana1a2.棧底棧頂.出棧進(jìn)棧棧s=(a1,a2,an)push(e)pop()clear()gettop()isempty()棧的基本操作53.1.2 棧的表示和實(shí)現(xiàn)順序棧:用一維數(shù)組實(shí)現(xiàn)top=-1123450??諚m?/p>
2、指針top,指向?qū)嶋H棧頂后的空位置,初值為-1top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=-1,???,此時(shí)出棧,則下溢(underflow)top=M-1,棧滿,此時(shí)入棧,則上溢(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; /取得棧的實(shí)際容量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 棧的表示和實(shí)現(xiàn)鏈棧:用鏈表實(shí)現(xiàn)棧功能棧頂 .topdata棧底結(jié)點(diǎn)定義入棧算法出棧算法 .棧底toptopxtop .棧底topq繼承方式實(shí)現(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聚合方式實(shí)現(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)換回文游戲括號(hào)匹配檢驗(yàn)表達(dá)式求值13例 把十進(jìn)制數(shù)1348轉(zhuǎn)換成八進(jì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表達(dá)式 := (操作數(shù)) + (運(yùn)算符) + (操作數(shù))操作數(shù) := 簡單變量 | 表達(dá)式簡單變量 : = 標(biāo)識(shí)符 | 無符號(hào)整數(shù)表達(dá)式的三種標(biāo)識(shí)方法:設(shè) Exp = S1 + OP + S2則稱 OP + S1 + S2 為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法 表達(dá)式求值(限于二元運(yùn)算符的表達(dá)式定義)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 + 三種表達(dá)式小結(jié)操作數(shù)之間的相對(duì)次序不變運(yùn)算符的相對(duì)次序不同;中綴式丟失了括弧信息, 致使運(yùn)算的次序不確定;17前綴式的運(yùn)算規(guī)則為:Exp = a b + (c d / e) f前綴式: + a b c / d e f連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;后綴式的運(yùn)算規(guī)則為:Exp = a b + (c d / e) f后綴式: a b c d e / f + 運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序; 每個(gè)運(yùn)算符和在它之前且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小 表達(dá)式。18如何從后綴式求值?例: a b c d e / f +abd/ec-d/e(c-d/e
10、)f運(yùn)算規(guī)則連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;先找運(yùn)算符再找操作數(shù)19double evaluation( char suffix ) / 本函數(shù)返回由后綴式suffix表示的表達(dá)式的運(yùn)算結(jié)果 ch = *suffix+; SeqStack S=new SeqStack(20); / 設(shè)置空棧S while ( ch != # ) if (!OpMember(ch) /函數(shù)OpMember() 用于判斷ch是否是操作符 S.push(ch ); / 非運(yùn)算符入操作數(shù)棧 else b=S.Pop(b); a=S.pop(a); / 退出棧頂兩個(gè)操作數(shù) S.pu
11、sh(Operate(a, ch, b); / 作相應(yīng)運(yùn)算,并將運(yùn)算結(jié)果入棧 ch= *suffix+; / 繼續(xù)取下一字符 result=S.pop(S,result); return result; / evalution20 每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定,在后綴式中,優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析 “原表達(dá)式” 和 “后綴式”中的運(yùn)算符:原表達(dá)式: a + b c d / e f 后綴式: a b c + d e / f 如何從原表達(dá)式求得后綴式?21從常規(guī)表達(dá)式求得后綴式的步驟為操作符設(shè)一個(gè)棧S;設(shè)常規(guī)表達(dá)式的結(jié)束符為“#”,予設(shè)棧S的棧底為“#”;Ch
12、=getchar(),表示從常規(guī)表達(dá)式取得的當(dāng)前字符若ch操作數(shù),則直接發(fā)送給后綴式。若ch是操作符,將其與棧頂操作符比較:如果ch的優(yōu)先級(jí)高于棧頂運(yùn)算符優(yōu)先級(jí),ch進(jìn)棧;如果ch的優(yōu)先級(jí)低于棧頂運(yùn)算符優(yōu)先級(jí),棧頂操作符出棧,并送往后綴式;如果 ch的優(yōu)先級(jí)等于棧頂運(yùn)算符優(yōu)先級(jí),視情況作不同的處理22操作符優(yōu)先級(jí)關(guān)系表23/比較操作符ch1與ch2的優(yōu)先級(jí)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 隊(duì)列3.2.1 隊(duì)列的定義及特點(diǎn)3.2.2 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)鏈隊(duì)列3.2.3 隊(duì)列的順序存儲(chǔ)循環(huán)隊(duì)列3.2.4 隊(duì)列的應(yīng)用273.2.1 隊(duì)列的定義及特點(diǎn)定義:隊(duì)列是限定只能在表的一端進(jìn)行插入,在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)允許插入的一端隊(duì)頭(front)允許刪除的一端隊(duì)列特點(diǎn):先進(jìn)先出(FIFO)a1 a2 a3.an 入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,an)雙端隊(duì)列a1 a2 a3.an 端1端2入隊(duì)出隊(duì)入隊(duì)出隊(duì)抽象數(shù)據(jù)類型Queue實(shí)例數(shù)據(jù):存儲(chǔ)數(shù)據(jù)元素的線性表,隊(duì)頭指針、隊(duì)尾指針操作:isEmpty( ):如果堆棧為空則返回true
14、,否則返回falseisFull( ):如果堆棧滿,則返回true,否則返回falsefront ( ):返回隊(duì)頭元素,但不刪除隊(duì)頭add (x):向隊(duì)列中添加元素xremove ( ):從隊(duì)頭刪除元素,并將它返回 28293.4.2 隊(duì)列的鏈存儲(chǔ)鏈隊(duì)列頭結(jié)點(diǎn) .front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn),rear指向隊(duì)尾30frontrearx入隊(duì)xfrontreary入隊(duì)xyfrontrearx出隊(duì)xyfrontrear空隊(duì)frontreary出隊(duì)3.4.2 隊(duì)列的鏈存儲(chǔ)鏈隊(duì)列繼承方式實(shí)現(xiàn)鏈?zhǔn)疥?duì)列public class LinkQue exten
15、ds LinkList public LinkQue() super();public T front () /取隊(duì)首元素return get(0);/*下面三個(gè)操作,在鏈表中已經(jīng)實(shí)現(xiàn),直接繼承即可,不用重復(fù)實(shí)現(xiàn)public void add (T x); /元素進(jìn)隊(duì)public T remove (); /元素出隊(duì) public boolean isEmpty() /判斷隊(duì)列是否空 */31聚合方式實(shí)現(xiàn)鏈?zhǔn)疥?duì)列public 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 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)簡單順序隊(duì)列:用一維數(shù)組實(shí)現(xiàn)sqMfront=0rear=0123450隊(duì)空123450frontJ1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個(gè)指針front,rear,約定:rear指示隊(duì)尾元素的下一位置;f
17、ront指示隊(duì)頭元素初值front=rear=0空隊(duì)列條件:front=rear入隊(duì)列:sq+rear=x;出隊(duì)列:x=sqfront+;rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront34存在問題設(shè)數(shù)組維數(shù)為M,則:當(dāng)front=0,rear=M-1時(shí),再有元素入隊(duì)發(fā)生溢出真溢出當(dāng)front0,rear=M-1時(shí),再有元素入隊(duì)發(fā)生溢出假溢出解決方案隊(duì)首固定,每次出隊(duì)時(shí),剩余元素向隊(duì)頭移動(dòng)浪費(fèi)時(shí)間循環(huán)隊(duì)列35循環(huán)隊(duì)列基本思想:把隊(duì)列設(shè)想成環(huán)形,讓sq0接在sqM-1之后,若rear+1=M,則令rear=0實(shí)現(xiàn):利用“?!边\(yùn)算入隊(duì):
18、rear=(rear+1)%M; sqrear=x;出隊(duì): front=(front+1)%M; x=sqfront;隊(duì)滿、隊(duì)空判定條件0M-11frontrear.36012345rearfrontJ5J6J7012345rearfrontJ4J9J8rearJ4J5J6501234front初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空:front=rear隊(duì)滿:front=rear解決方案:1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間: 隊(duì)空:front=rear 隊(duì)滿:(rear+1)%M=front012345frontJ5J6J7J4J8rear隊(duì)空隊(duì)滿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(隊(duì)列已滿);datarear=e; rear=(rear+1)%maxSize;public T remove() throws Exception T temp;if(isEmpty() throw new Exception(隊(duì)列已空!); temp=(T)datafront; front=(front+1)%maxSize;return temp;37383.3.4 隊(duì)列應(yīng)用劃分子集問題(等價(jià)類)問題描述:已知集合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í)要求子集個(gè)數(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)篩選。從第一個(gè)元素開始,凡與第一個(gè)元素?zé)o沖突的元素劃歸一組;再將剩下的元素重新找出互不沖突的劃歸第二組;直到所有元素進(jìn)組所用數(shù)據(jù)結(jié)構(gòu)沖突關(guān)系矩陣R=rijrij=1, i,j有沖突rij=0, i,j無沖突循環(huán)隊(duì)列Qn數(shù)組resultn存放每個(gè)元素分組號(hào)41算法過程初始狀態(tài):A中元素放于Q中,result和newr數(shù)組清零,組號(hào)group=1第一個(gè)元素出隊(duì),將r矩陣中第一
23、行與newr中對(duì)應(yīng)元素相加,這樣,凡與第一個(gè)元素有沖突的元素在newr中對(duì)應(yīng)位置處均為非0,下一個(gè)元素出隊(duì)。若其在newr中對(duì)應(yīng)位置為非0,有沖突,重新插入Q隊(duì)尾,參加下一次分組若其在newr中對(duì)應(yīng)位置為0, 無沖突,可劃歸本組;再將r矩陣中該元素對(duì)應(yīng)行newr中對(duì)應(yīng)元素相加如此反復(fù),直到9個(gè)元素依次出隊(duì),由newr中為“0”的單元對(duì)應(yīng)的元素構(gòu)成第1組,將組號(hào)group值“1”寫入result對(duì)應(yīng)單元中令group=2,newr清零,對(duì)Q中元素重復(fù)上述操作,直到Q中front=rear,即隊(duì)空,運(yùn)算結(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出隊(duì),分組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出隊(duì),末分組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出隊(duì),分組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出隊(duì),分組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出隊(duì),末分組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出隊(duì),末分組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出隊(duì),末分組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出隊(duì),分組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出隊(duì),末分組第一輪結(jié)束,(1,3,4,8)分為第一組現(xiàn)在開始第二輪,2先單獨(dú)分為一組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出隊(duì),分組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出隊(duì),末分組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出隊(duì),末分組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出隊(duì),分組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出隊(duì),末分組第二輪結(jié)束,(2,7)分為第二組現(xiàn)在開始第三輪,5先單獨(dú)分為一組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出隊(duì),分組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出隊(duì),末分組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出隊(duì),末分組第三輪結(jié)束,(5)分為第三組現(xiàn)在開始第四輪,6先單獨(dú)分為一組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出隊(duì),分組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出隊(duì),分組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 隊(duì)列已空,結(jié)束63void division ( int R , int n, int result ) / 已知 Rnn 是編號(hào)為 0 至 n-1 的 n 個(gè)元素的關(guān)系矩陣,子集劃分的結(jié)果 / 記入result 數(shù)組,resultk 的值是編號(hào)為 k 的元素所屬組號(hào) pre = n; group = 0; InitQueue_Sq ( Q, n ); / 設(shè)置最大容量為 n 的空隊(duì)列 for ( e =1; e =n; e+ ) EnQueue_Sq ( Q, e ); while ( !QueueEmpt
51、y ( Q ) ) DeQueue_Sq ( Q, i ); if ( i =pre ) group +; / 增加一個(gè)新的組 for ( j = 1; j =n; j + ) newrj = 0; if ( newri = 0 ) resulti = group; / 編號(hào)為i 的元素入group 組 for ( j = 1; j =n; j + ) newrj += Rij; / 添加和 i沖突的信息 else EnQueue ( Q, i ); / 編號(hào)為i 的元素不能入當(dāng)前組 pre = i; / while/ division64思考題一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜,身處河的南
52、岸。他要把這些東西全部運(yùn)到北岸。他面前只有一條小船,船只能容下他和一件物品,另外只有農(nóng)夫能撐船。因?yàn)槔浅匝?,羊吃白菜,所以農(nóng)夫不能留下羊和白菜自己離開,也不能留下狼和羊自己離開,而狼不吃白菜。請(qǐng)問農(nóng)夫該采取什么方案才能將所有的東西運(yùn)過河呢?65求解這個(gè)問題的最簡單的方法是一步一步進(jìn)行試探,每一步都搜索所有可能的選擇,對(duì)前一步合適的選擇再考慮下一步的各種方案。要模擬農(nóng)夫過河問題,首先需要對(duì)問題中每個(gè)角色的位置進(jìn)行描述。一個(gè)很方便的辦法是用四位二進(jìn)制數(shù)順序分別表示農(nóng)夫、狼、白菜和羊的位置。用0表示農(nóng)夫或者某東西在河的南岸,1表示在河的北岸。例如整數(shù)5(其二進(jìn)制表示為0101) 表示農(nóng)夫和白菜在河的
53、南岸,而狼和羊在北岸。還應(yīng)該分析問題中所有角色的各種可能位置構(gòu)成的狀態(tài),哪些是安全的哪些是不安全的。根據(jù)原題可知,單獨(dú)留下白菜和羊,或單獨(dú)留下狼和羊在某一岸的狀態(tài)是不安全的?,F(xiàn)在問題變成:從初始狀態(tài)二進(jìn)制0000(全部在河的南岸) 出發(fā),尋找一種全部由安全狀態(tài)構(gòu)成的狀態(tài)序列,它以二進(jìn)制1111(全部到達(dá)河的北岸) 為最終目標(biāo),并且在序列中的每一個(gè)狀態(tài)都可以從前一狀態(tài)通過農(nóng)夫(可以帶一樣?xùn)|西)劃船過河的動(dòng)作到達(dá)。為避免不必要的瞎費(fèi)功夫,要求在序列中不應(yīng)該出現(xiàn)重復(fù)的狀態(tài)663.3 特殊矩陣定義矩陣的特點(diǎn)矩陣結(jié)構(gòu)固定矩陣元素同構(gòu)矩陣運(yùn)算(兩個(gè)最重要的運(yùn)算)給定一組下標(biāo),存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)
54、,修改數(shù)據(jù)元素的值1 矩陣的定義和特點(diǎn)67矩陣的存儲(chǔ)方式以行序?yàn)橹餍蛞粤行驗(yàn)橹餍蛑攸c(diǎn):對(duì)于矩陣A=aijm*n 不同存儲(chǔ)方式下,元素aij的存儲(chǔ)位置計(jì)算2 矩陣的順序表示和實(shí)現(xiàn)683 特殊矩陣的存儲(chǔ)表示對(duì)稱矩陣a11 a12 a13 . a1n . a22 a23 . ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍海ㄗ笙陆牵ㄓ疑辖牵?9三角矩陣a11 a21 a22 a31 a32 an1 ann .k=1 2 3 4 5 n(n-1)/2+1 n(n+1)/2 按行序?yàn)橹餍颍?0對(duì)角矩陣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 按行序?yàn)橹餍颍夯?13.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)唯一確定壓縮存儲(chǔ)原則:只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值723.4.1 三元組稀疏矩陣的每個(gè)非零元素有三個(gè)要素:行號(hào),列號(hào),元素值。將這三個(gè)要素稱為矩陣元素三元組:矩陣元素三元組=(i,j,val
56、ue)這里,i是行號(hào),j是列號(hào),value是矩陣元素值。下面給出用java類描述的三元組。73743.4.2 矩陣抽象數(shù)據(jù)類型矩陣操作在科學(xué)和工程中有著廣泛的應(yīng)用,矩陣的加、減、乘 、求逆運(yùn)算,求矩陣、的特征值與特征向量,奇異值分解等運(yùn)算在科學(xué)個(gè)工程計(jì)算中起著重要重要。因?yàn)楸菊n程只主要關(guān)心的是稀疏矩陣的元素存取操作,讀矩陣的各種運(yùn)算,親讀者根據(jù)需要添加。753.4.3 稀疏矩陣的三元組順序表表示順序表表示稀疏矩陣就是將矩陣的所有非零元素的三元組存放在一個(gè)順序表中。例如圖3 14(a)所示的稀疏矩陣M67,用三元組順序表表示如圖3 14(b)所示。三元組順序表表示的特點(diǎn):三元組順序表表示有一個(gè)基
57、本要求:在三元組順序表中的三元組先按行號(hào)排序,行號(hào)相同時(shí),在按列號(hào)排序,這符合按行優(yōu)先順序存放。在訪問數(shù)組元素時(shí),可用二分查找方法,查找一個(gè)元素時(shí)間為O(log_2t_(u )。若行下標(biāo)、列下標(biāo)與值均占用一個(gè)存儲(chǔ)單元,非零元素個(gè)數(shù)為t_u,那么這種存儲(chǔ)方式需要3t_u個(gè)存儲(chǔ)單元。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)置運(yùn)算稀疏矩陣轉(zhuǎn)置運(yùn)算問題描述:已知一個(gè)稀疏矩陣的三元組表,求該矩陣轉(zhuǎn)置矩陣的三元組表85問題分析:一般矩陣轉(zhuǎn)置算法void transpose1(int M , int T ) /普通矩陣轉(zhuǎn)置 for(col=0;coln; col+) for(row=? ; rowm; row+) Tcolrow=Mrowcol;特點(diǎn):行、列下標(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ù)互換將每個(gè)三元組中的i和j相互調(diào)換重排三元組次序,使M中元素以T的行(M的列)為主序方法一:以T為基準(zhǔn),“按需點(diǎn)菜”方法二:以M為基準(zhǔn),“按位就坐?88方法一:以T為基準(zhǔn),“按需點(diǎn)菜”算法:對(duì)M.data從頭至尾掃描:第一次掃描時(shí),將M.data中列號(hào)為1的三元組賦值到T.data中第二次掃描時(shí),將M.data中列號(hào)為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對(duì)M六次掃描完成轉(zhuǎn)置運(yùn)算第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素90/轉(zhuǎn)置運(yùn)算算法void transpose
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年銅壓延加工材合作協(xié)議書
- 保密不競爭和知識(shí)產(chǎn)權(quán)歸屬協(xié)議
- 2025年文山貨運(yùn)從業(yè)資格證考試模擬考試題庫下載
- 2025年銅仁道路貨運(yùn)從業(yè)資格證模擬考試官方題下載
- 產(chǎn)品升級(jí)迭代進(jìn)度統(tǒng)計(jì)表
- 個(gè)人金融智能財(cái)富管理與服務(wù)系統(tǒng)開發(fā)
- 互聯(lián)網(wǎng)行業(yè)大數(shù)據(jù)分析與挖掘技術(shù)應(yīng)用方案
- 2025年保險(xiǎn)職業(yè)學(xué)院單招職業(yè)適應(yīng)性測試題庫學(xué)生專用
- 工程建設(shè)項(xiàng)目廉潔協(xié)議書
- 2025年包頭鐵道職業(yè)技術(shù)學(xué)院單招職業(yè)技能考試題庫及答案一套
- 《配電自動(dòng)化運(yùn)維人員培訓(xùn)考核規(guī)范(征求意見意見稿)》
- (中職組)植物病蟲害防治知識(shí)競賽考試題庫(含答案)
- 肌肉注射新版本
- 大班語言活動(dòng)-海豹到哪里去了
- 小班社會(huì)《認(rèn)識(shí)家用電器》課件
- 高考概率大題必練20題(理科)-含答案
- 涼水井煤礦礦山地質(zhì)環(huán)境與土地復(fù)墾方案
- 果實(shí)酚類和揮發(fā)性物質(zhì)含量特征及其與果實(shí)品質(zhì)關(guān)系的研究
- 2023年東華高級(jí)中學(xué)中考自招數(shù)學(xué)復(fù)習(xí)題及答案解析
- 結(jié)果比過程重要辯論賽
- JTG C10-2007 公路勘測規(guī)范
評(píng)論
0/150
提交評(píng)論