軟件開發(fā)技術(shù)基礎(chǔ)

整理課件

數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用

整理課件什么是數(shù)據(jù)指描述客觀事物的信息符號的集合，這些信息符號能輸入到計算機(jī)中存儲起來，并能被計算機(jī)處理。整理課件整數(shù)數(shù)據(jù)整數(shù)集合的子集：……-3-2-101234……

intj;-32768至+32767unsignedintj;0至+65535longintj;-232至+232-1unsignedlongintj;范圍？整理課件Structstudent{longnum;charname[9];charsex;floatscore;}學(xué)生花名冊數(shù)據(jù)學(xué)號姓名性別成績98031001張三男8898031002李四女89.5…...整理課件棋盤數(shù)據(jù)：圍棋棋盤如何描述？整理課件棋盤數(shù)據(jù)：井字棋盤OO**OOOOOO**OOOO********OOOOOCharchess[9];或intchess[9];整理課件城市交通圖數(shù)據(jù)OOOOOOOOO咸陽西安長安縣臨潼興平禮泉渭南大荔整理課件圖像數(shù)據(jù)像素存儲（行號，列號，顏色）整理課件聲音數(shù)據(jù)時刻值，幅度值整理課件數(shù)據(jù)元素----是數(shù)據(jù)這個集合中的一個個體，是數(shù)據(jù)的基本單位。數(shù)據(jù)項----是具有獨(dú)立含義，且不可再細(xì)分的最小標(biāo)識單位。數(shù)據(jù)結(jié)構(gòu)----指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合數(shù)據(jù)的邏輯結(jié)構(gòu)----反映數(shù)據(jù)元素之間客觀存在的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)----將數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)內(nèi)存中存儲的結(jié)構(gòu)。數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的運(yùn)算----是定義在數(shù)據(jù)結(jié)構(gòu)上的操作。例如求某個數(shù)據(jù)結(jié)構(gòu)中的最大元素等。線性表、堆棧、隊列、樹、圖名詞術(shù)語整理課件什么是算法？算法----是解決問題方案的準(zhǔn)確而完整的描述算法的特性：有窮性、確定性、可行性、有輸入、有輸出時間復(fù)雜度：依據(jù)算法編制成程序后，在計算機(jī)上運(yùn)行所消耗時間空間復(fù)雜度：依據(jù)算法編制成程序后，在計算機(jī)上運(yùn)行所消耗空間用數(shù)量級來度量和分析時間復(fù)雜度和空間復(fù)雜度。#definen1000000sum=sum+1;O(1)for(I=0;I<n;I++)sum++;O(n)for(I=0;I<n;I++)for(j=0;j<n;j++)sum++;O(n2)

floata;O(1)floata[n];O(n)floata[n][n]O(n2)算法整理課件什么是線性表日常生活中常見到表格形式的一類數(shù)據(jù)列車時刻表學(xué)生成績表周名縮寫表

整理課件車次火車種類始發(fā)站終點(diǎn)站始發(fā)時間到達(dá)時間140特快西安上海20：3019：4542特快西安北京17：307：45361普快西安銅川9：4513：10………………………………列車時刻表整理課件學(xué)號姓名性別分?jǐn)?shù)99011001周敏女8699011002蘇伊詩女9299011003王蘇朋男76……………………學(xué)生成績表整理課件Sun.Mon.Tue.Wen.Thu.Fri.Sat.周名縮寫表整理課件1）表中每一行信息雖然組成的內(nèi)容不同，但都代表某個明確獨(dú)立的含義，將表中每一行信息稱之為一個數(shù)據(jù)元素；2）每個數(shù)據(jù)元素在表中的位置固定，除了第一個元素和最后一個元素外，其余元素都有唯一一個前驅(qū)元素和唯一一個后繼元素；3）表中數(shù)據(jù)元素的個數(shù)不相同，有長有短；4）大多數(shù)表中數(shù)據(jù)元素會增加或減少，是動態(tài)變化的。但也有一些表是固定不變，將這些表格形式的數(shù)據(jù)加以抽象，統(tǒng)稱為線性表。上述表格數(shù)據(jù)具有如下共同特點(diǎn)：整理課件什么是線性表試舉出日常生活中線性表的例子？指n(n≥0)個元素a1，a2，a3，…，an

的有限集合，集合中的元素除第一個與最后一個元素外，其它元素都只有一個直接前趨元素和一個直接后繼元素。整理課件對線性表有哪些處理（或操作）呢？1）統(tǒng)計線性表里總共有多少個元素。簡稱求表長，記作Length（L），2）獲取線性表中某個數(shù)據(jù)元素的信息。簡稱取元素，記作Get（L，i）3）置換或修改線性表中某個數(shù)據(jù)元素的信息。簡稱置換元素，記作Replace（L，i，x）4）在線性表中某個位置上增加一個數(shù)據(jù)元素。簡稱插入元素，記作Insert（L，i，x）5）刪除線性表中某個位置上的一個數(shù)據(jù)元素。簡稱刪除元素，記作Delete（L，i）6）查找某個數(shù)據(jù)元素是否在線性表中存在。簡稱查找元素，記作Locate（L，x）7）對線性表中的數(shù)據(jù)元素按某個數(shù)據(jù)項的值遞增（或遞減）的順序排列。簡稱排序，記作Sort(L)。整理課件線性表的順序存儲結(jié)構(gòu)----順序表類線性表的非順序存儲結(jié)構(gòu)----鏈表類線性表的兩種存儲結(jié)構(gòu)整理課件順序表類線性表的順序存貯結(jié)構(gòu)就是將線性表的每個數(shù)據(jù)元素按其邏輯次序依次存放在一組地址連續(xù)的存貯單元里整理課件constintMAXSIZE=100; //順序表最大允許長度classSeqList{public:ElemTypedata[MAXSIZE];//存儲數(shù)據(jù)的數(shù)組intlength; //順序表當(dāng)前長度SeqList(){length=0;}//構(gòu)造函數(shù)voidClearList(){length=0;}//將順序表置為空表boolIsListEmpty(){returnlength==0;}//判斷是否為空表//判斷順序表是否為滿boolIsListFull(){returnlength==MAXSIZE;}voidListDelete(inti);//在表中刪除第i個元素//在表中第i個位置插入新元素xvoidListInsert(inti,ElemTypex);intFind(ElemTypex); //在表中查找元素};整理課件由于不同的線性表，其數(shù)據(jù)元素類型不一樣例如學(xué)生花名冊中每個元素有四個數(shù)據(jù)項航班時刻表也有多個數(shù)據(jù)項。從通用性出發(fā)，表中的元素為一個模板數(shù)據(jù)類型DataType。Template<classDataType>數(shù)據(jù)元素類型說明整理課件插入前：（a1，a2，…，ai-1，ai，…，an）插入后：（a1，a2，…，ai-1，x，ai，…，an）第1步:判定表不滿方可插入；第2步:判定插入位置i的合法性；第3步:將第n至第i個元素后移一個存儲位置；第4步:將x存入到ai-1之后空間；第5步:線性表的長度加1。

插入算法整理課件整理課件voidSeqList::ListInsert(inti,ElemTypex){if(i<1||i>length+1||length==MAXSIZE)cout<<"插入位置錯誤或表滿"; else{ for(intj=length-1;j>=i-1;j--){ data[j+1]=data[j]; //元素依次向后移動 } data[i-1]=x; //向第i個位置存入新元素

length++; //表長度加1}}整理課件在等概率的條件下,插入函數(shù)的時間復(fù)雜度:N/2a1a2a3a4……an-1an

有N+1處可能插入,等概率值為1/(1+N)

插入算法評價整理課件刪除前：（a1，a2，…，ai-1，ai，ai+1，…，an）刪除后：（a1，a2，…，ai-1，ai+1，…，an）

第1步：判定表不空方可刪除；第2步：判定刪除位置i值的合法性；第3步：將第i+1至第n個元素依次向前移動一個存儲位置；第4步：將線性表的長度減1。刪除算法整理課件整理課件voidSeqList::Delete(inti){if(i<1||i>L->length) cout<<"表中沒有第"<<i<<"個元素";else{ for(intj=i;j<=length-1;j++) data[j-1]=data[j];//元素依次向前移動

length--; } }整理課件刪除函數(shù)的時間復(fù)雜度：（N-1）/2在等概率條件下插入和刪除算法詳見rjjcjg_1.cpp刪除算法評價整理課件

intSeqList::Find(ElemTypex) { for(inti=0;i<length;i++) {//查找成功，返回元素位置 if(data[i]==x)returni+1; } return0; //查找失敗，返回0 }在表中查找某個元素下面是根據(jù)數(shù)據(jù)元素本身的值進(jìn)行查詢的算法，x為需要查找的元素，查找結(jié)果返回元素的實(shí)際位置。整理課件順序表應(yīng)用舉例

一元多項式P(x)可以表示為:((a0,0),(a1,1),…,(an,n))用順序表存放

例2-1】利用順序表表示多項式，實(shí)現(xiàn)兩個一元多項式L1(x)和L2(x)相加，將結(jié)果存于多項式L3(x)中。并計算當(dāng)L1(x)=3.5+4x2+2.5x4，L2(x)=1.5x+2.6x2+1.6x3時，L3(x)的結(jié)果是什么？(a0,0)(a1,1)……(an,n)整理課件①設(shè)定兩個位置變量i和j指向順序表L1和L2的第一個元素，設(shè)定位置變量k表示L3的插入位置，插入位置從1開始。本例中i、j和k初值均為1。②比較i和j兩個位置數(shù)據(jù)元素的指數(shù)項，如果L1中第i項指數(shù)較小，則將此項數(shù)據(jù)元素復(fù)制到L3的位置k中，并將位置變量i和k后移；如果L2中第j項指數(shù)較小，則同樣是將此項復(fù)制到L3中，并將位置變量j和k后移；如果兩項指數(shù)項相等，則合并同類項后再將結(jié)果復(fù)制到L3中，并將位置變量i、j和k同時后移。③當(dāng)L1或L2中的一個順序表已經(jīng)處理完畢，則將另一個順序表的剩余部分復(fù)制到L3中。演示運(yùn)行2-1.cpp多項式相加算法可按照下列步驟實(shí)現(xiàn)整理課件順序表類的優(yōu)缺點(diǎn)1、存取元素非常快；2、不用存關(guān)系集合；3、插入刪除元素要移動一半元素；4、需要申請較大的空間，但往往只用一部分空間；5、可擴(kuò)充性差；整理課件線性表的非順序存儲結(jié)構(gòu)----單鏈表設(shè)計新的存儲結(jié)構(gòu)，改進(jìn)順序表的結(jié)構(gòu)思路：1、線性表中有多少元素就開辟多少存儲空間，不預(yù)留空間；2、元素之間不需要緊挨著存放，元素可以散落在存儲器中任何地方；3、插入和刪除都不需要移動大量元素；整理課件鏈表類線性表中每個元素的存儲結(jié)構(gòu)如下：每個數(shù)據(jù)元素存儲都由兩部分組成：存貯數(shù)據(jù)元素值的部分，簡稱數(shù)據(jù)域；存貯直接后繼元素存貯位置的部分，簡稱指針域。數(shù)據(jù)元素值后繼元素位置structLNode{ElemTypedata;LNode*next;}整理課件為了后面定義方便，一個數(shù)據(jù)元素定義如下：TypedefstructLNode{ElemTypedata;LNode*next;}Lnode;整理課件線性表的非順序存儲結(jié)構(gòu)示意圖如下：A1A2A3Anhead…指針將線性表中每一個元素有機(jī)地連接在一起，指針像鏈條一樣，所以線性表的非順序存儲結(jié)構(gòu)又稱鏈?zhǔn)浇Y(jié)構(gòu)，簡稱鏈表。整理課件A28694A3NULLA122A1A2A322388694存儲地址數(shù)據(jù)域指針域head38head鏈表存儲結(jié)構(gòu)示意圖如下：整理課件TypedefstructLnode{ElemTypedata;LNode*next;}Lnode;classLinkList{public:LNode*head; //定義頭指針LinkList() //構(gòu)造函數(shù){ head=newLNode; //建立頭結(jié)點(diǎn) head->next=NULL; //頭結(jié)點(diǎn)的指針為空} intListSize(); //求單鏈表長度LNode*GetElemPointer(intpos);//返回表中指定序號結(jié)點(diǎn)的指針voidInsertList(inti,ElemTypex);//向單鏈表第i個位置插入元素xLNode*LinkList::DeleteList(inti);//從單鏈表中刪除第i個結(jié)點(diǎn)LNode*Find(ElemTypex)；//在單鏈表中查找數(shù)據(jù)值為x的結(jié)點(diǎn)};單鏈表類的完整定義如下：整理課件指針操作假如p為指向某一結(jié)點(diǎn)的指針則該結(jié)點(diǎn)的數(shù)據(jù)域用p->data表示該結(jié)點(diǎn)的指針域用p->next表示它們都是變量，可以被賦值，也可向其他變量賦值。 例如:假定data為整型變量,則

p->data=5;p->next=NULL;將結(jié)點(diǎn)變?yōu)?

整理課件aiai-1ai-1aiai-1ai+1qqpp如果p為指向結(jié)點(diǎn)ai的指針，那么p->next就是指向ai后繼結(jié)點(diǎn)ai+1的指針；若q為另一指針變量p=q指針p指向指針q所指的結(jié)點(diǎn)p=q->next指針p指向指針q所指結(jié)點(diǎn)的后繼指針操作整理課件要確定鏈表長度需要走遍表中所有結(jié)點(diǎn)才能算出。為了保持頭指針不變，使用了指針p在鏈表中移動。求單鏈表的長度intLinkList::ListSize(){LNode*p=head->next;//p指向第一個元素所在結(jié)點(diǎn)intlen=0;while(p!=NULL) //逐個檢測p結(jié)點(diǎn)存在與否{len++; p=p->next; //指針后移} returnlen;}整理課件LNode*LinkList::GetElemPointer(intpos){ if(pos<0){returnNULL;} //該位置不存在 elseif(pos==0){returnhead;} else {LNode*p=head->next; //p為首元結(jié)點(diǎn)指針 intk=1; while(p!=NULL&&k<pos){p=p->next;k++; } if(k==pos&&p!=NULL)returnp;//返回第pos個結(jié)點(diǎn)指針elsereturnNULL; //該位置不存在 } }返回單鏈表中指定序號的結(jié)點(diǎn)的指針整理課件Lnode*newnode=newLNode;newnode->data=x;newnode->next=previous->next;previous->next=newnode;整理課件單鏈表類的插入算法從表頭開始尋找插入位置判定插入位置有錯否申請新結(jié)點(diǎn)修改鏈表指針，將新結(jié)點(diǎn)插入鏈表中整理課件voidLinkList::InsertList(inti,ElemTypex){ LNode*p=head; p=GetElemPointer(i-1); //p最終將指向第i-1個結(jié)點(diǎn) if(!p) cout<<i<<"位置無法插入元素"; else{ LNode*s=newLNode; //建立新結(jié)點(diǎn)s s->data=x; s->next=p->next; //定義結(jié)點(diǎn)s的指針域 p->next=s; //修改結(jié)點(diǎn)p的指針域 }}整理課件Ai-1AiXpsp->next=s;新結(jié)點(diǎn)鏈入表中示意圖s->next=p->next;整理課件previous->next=current->next;deletecurrent;整理課件單鏈表類的刪除算法判定空表尋找插入位置確認(rèn)插入有錯否修改鏈表指針收回結(jié)點(diǎn)空間整理課件LNode*LinkList::DeleteList(inti){if(i<1)cout<<”不存在第”<<i<<”個元素”;else{ LNode*p=head;//p指向頭結(jié)點(diǎn)(第0個結(jié)點(diǎn)) LNode*q; //q和p最終分別指向第i-1和第i個結(jié)點(diǎn) intk=0; while(p!=NULL&&k<i){ q=p; p=p->next; k++; } if(p==NULL)cout<<i<<”超出鏈表長度”; else{ q->next=p->next; //從鏈表中刪除該結(jié)點(diǎn) deletep; //釋放結(jié)點(diǎn)p }}}整理課件Ai-1Aiq->next=p->next;deletep;Ai+1qp刪除Ai結(jié)點(diǎn)示意圖XX整理課件可以按照數(shù)據(jù)元素本身的值進(jìn)行查找，也可以按照數(shù)據(jù)元素的某個屬性進(jìn)行查找。這里僅給出按照數(shù)據(jù)元素本身的值進(jìn)行查找的算法。在單鏈表中查找數(shù)據(jù)值為x的結(jié)點(diǎn)LNode*LinkList::Find(ElemTypex){LNode*p=head->next;//p指向第一個元素所在結(jié)點(diǎn)while(p!=NULL&&p->data!=x)p=p->next;returnp;}整理課件循環(huán)鏈表…h(huán)eadA1AnA2head空循環(huán)鏈表非空循環(huán)鏈表整理課件前驅(qū)指針域prior后繼指針域next數(shù)據(jù)域data雙向鏈表結(jié)點(diǎn)示意圖每個數(shù)據(jù)元素存儲結(jié)構(gòu)如下：head......ana2a1整理課件

約瑟夫環(huán)問題可以解釋為：將整數(shù)1至n圍成一個圓圈，假定從某個整數(shù)開始順時針從1數(shù)到m時，令該位置整數(shù)出列；然后再從下一數(shù)開始，順時針從1數(shù)到第m時再令其出列，如此下去，直到圓圈中無整數(shù)為止。請寫出所有數(shù)字出列的順序。

鏈表應(yīng)用舉例

演示【例2-2】2-2.cpp整理課件堆棧stack探討貨倉工作原理假設(shè)只有一個門的貨倉，先進(jìn)去的貨物后出來。若線性表比照貨倉，貨物比照數(shù)據(jù)元素。元素只能在線性表的一端插入刪除。整理課件堆棧的定義堆棧指插入和刪除元素操作只能在表的一端進(jìn)行，這種線性表稱為堆棧。堆棧又稱LIFO表或FILO表DCBA插入進(jìn)棧刪除出棧棧頂棧底整理課件創(chuàng)建一個堆棧：setnull(stack)判空棧：emptystack(stack)元素進(jìn)棧：push(stack,data)元素出棧：pop(stack)取棧頂元素：gettop(stack)堆棧的基本操作整理課件由于棧是一個特殊線性表，順序棧類與順序表基本相同。類似于線性表的順序存儲結(jié)構(gòu)，順序棧類的C++描述如下：#defineSTACKSIZE100classSeqStack{ public:ElemTypedata[STACKSIZE];//存儲元素的數(shù)組inttop;SeqStack(){top=-1;};//構(gòu)造函數(shù)BOOLstack_empty();//判棧空函數(shù)BOOLpush(ElemTypex);//元素進(jìn)棧函數(shù)BOOLpop(ElemType&result);//元素出棧函數(shù)BOOLgettop(ElemType&result);//取棧頂元素～stack();}順序棧類定義整理課件A1A2A3A4A5A6內(nèi)存儲器top5棧頂0棧底進(jìn)棧出棧進(jìn)棧的核心操作：top++;data[top]=X;出棧的核心操作：X=data[top];top--;1234整理課件順序棧類的進(jìn)棧函數(shù)第1步：判斷棧是否已滿，若棧滿則元素不能進(jìn)棧，退出函數(shù)；第2步：棧頂下標(biāo)變量top增1，即top++；第3步：在top所指向的當(dāng)前位置存入元素x。

BOOLSeqStack∷push(ElemTypex){if(top==STACKSIZE-1){cout<<"棧滿。又稱棧溢出(上溢)\n";returnFALSE;}else{top++;data[top]=x;returnTRUE;}}整理課件順序棧類的出棧函數(shù)第1步：判定棧是否為空棧，若為空則無元素可以出棧，退出函數(shù)；第2步：彈出（刪除）棧頂元素；第3步：棧頂下標(biāo)變量top減1，即top--。

BOOLSeqStack∷pop(ElemType&result){if(top==–1){cout<<"棧空.又稱棧溢出(下溢)\n";returnfalse;}else{result=data[top];top--;returntrue;}}整理課件順序棧類的取棧頂函數(shù)第1步：判定棧是否為空棧，若為空則無元素可以出棧，退出函數(shù)；第2步：彈出（刪除）棧頂元素；BOOLSeqStack∷gettop(ElemType&result){if(top==–1){cout<<"棧空.又稱棧溢出(下溢)\n";returnfalse;}else{result=data[top];returntrue;}}整理課件類似于單鏈表，鏈棧的C++描述如下：typedefstructnode{ ElemTypedata; //數(shù)據(jù)域 structnode*next; //指針域}SNode;classLinkStack{ public: SNode*top; //棧頂指針 LinkStack(){top=NULL;} //構(gòu)造函數(shù) voidPush(ElemTypex); //入棧操作 voidPop(ElemType&result); //出棧操作};

鏈棧類定義整理課件A2A3A4A5A6A1top進(jìn)棧的核心操作：newnode=newSNode;newnode→data=X;newnode→link=top;top=newnode;出棧的核心操作：cureent=top;X=top→data;top=top→link;deletecurrent;整理課件若棧不滿，則在棧頂插入元素x作為新的棧頂。voidLinkStack::Push(ElemTypex){ SNode*p=newSNode; if(p!=NULL){ p->data=x; p->next=top; top=p; }}鏈棧進(jìn)棧操作整理課件若棧不空，則刪除棧頂元素，用result返回其值。voidLinkStack::Pop(ElemType&result);{ SNode*p; if(top!=NULL){ result=top->data; p=top; top=top->next; deletep; }}鏈棧出棧操作整理課件三種不同的表示方法：

前綴表示法OPS1S2

例如6+3寫成+63

中綴表示法S1OPS2

例如6+3寫成6+3 后綴表示法S1S2OP

例如6+3寫成63+假定表達(dá)式是由加減乘除和數(shù)字構(gòu)成。最常見的表達(dá)式為下列形式：

(操作數(shù)S1)(運(yùn)算符OP)(操作數(shù)S2)算術(shù)表達(dá)式表示整理課件

同時，任何表達(dá)式都可分解為下列形式：

(子表達(dá)式E1)(運(yùn)算符OP)(子表達(dá)式E2)

它的后綴表示法應(yīng)寫成：

(E1的后綴表示)(E2的后綴表示)OP

只要不斷對子表達(dá)式進(jìn)一步分解，總能將子表達(dá)式分解為最簡單形式，因此任何四則運(yùn)算表達(dá)式都可寫成前綴式或后綴式。 例如：2*(6+3)

2(6+3)*263+*。(注意：轉(zhuǎn)化為后綴式后括號去掉)算術(shù)表達(dá)式表示整理課件用后綴式求值的算法為：首先設(shè)立一個堆棧，依此讀取后綴式中的字符若字符是數(shù)字，則進(jìn)棧并繼續(xù)讀取若字符是運(yùn)算符，則連續(xù)出棧兩次得到數(shù)字S1和S2計算表達(dá)式S1OPS2,并將結(jié)果入棧，繼續(xù)讀取后綴式。當(dāng)讀到結(jié)束符時停止讀操作這時堆棧中只應(yīng)該有一個數(shù)據(jù)，即結(jié)果數(shù)據(jù)。后綴表達(dá)式求值人們習(xí)慣于中綴式的計算，但計算機(jī)在求值的時候往往利用前綴式或后綴式。整理課件 例如后綴式263+*的計算過程為2、6、3依次入棧，讀+號則令3和6依次出棧，計算6+3后將結(jié)果9入棧，讀*號則令9和2依次出棧，計算2*9后將結(jié)果18入棧。這時18就是最終結(jié)果。 【例2-3】假定表達(dá)式是由不超過四個實(shí)數(shù)進(jìn)行四則運(yùn)算構(gòu)成的算式，要編寫一個程序來求解該算式的結(jié)果。運(yùn)行2_3.cpp舉例計算后綴表達(dá)式整理課件中綴式變成后綴式轉(zhuǎn)換規(guī)則是：設(shè)立一個棧，存放運(yùn)算符，首先棧為空編譯程序從左到右掃描中綴表達(dá)式若遇到操作數(shù)，直接輸出，并輸出一個空格作為兩個操作數(shù)的分隔符若遇到運(yùn)算符，則必須與棧頂比較，運(yùn)算符級別比棧頂級別高則進(jìn)棧，否則退出棧頂元素并輸出，然后輸出一個空格作分隔符若遇到左括號，進(jìn)棧；若遇到右括號，則一直退棧輸出，直到退到左括號止當(dāng)棧變成空時，輸出的結(jié)果即為后綴表達(dá)式。整理課件步驟棧中元素

輸出結(jié)果

說明1(

（進(jìn)棧2(1輸出13(+1+進(jìn)棧4(+12輸出25

12++退棧輸出，退棧到（止6*12+*進(jìn)棧7*(12+（進(jìn)棧8*((12+（進(jìn)棧9*((12+8輸出810*((-12+8

-進(jìn)棧將中綴表達(dá)式(1+2)*((8-2)/(7-4))變成等價的后綴表達(dá)式。

現(xiàn)在用棧來實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下：整理課件11*((-12+82輸出212*(12+82--退棧輸出，退棧到（止13*(/12+82-/進(jìn)棧14*(/(12+82-（進(jìn)棧15*(/(12+82-7輸出716*(/(-12+82-7-進(jìn)棧17*(/(-12+82-74輸出418*(/12+82-74--退棧輸出，退棧到（止19*12+82-74-//退棧輸出，退棧到（止20

12+82-74-/*

*退棧并輸出整理課件對頭隊尾隊列類似日常生活中的排隊原理LILO表FIFO表分析進(jìn)隊順序：A,B,C則出隊順序有哪些？進(jìn)隊出隊隊列也是特殊的線性表。它只允許在線性表的一個端點(diǎn)進(jìn)行插入，而在線性表的另一個端點(diǎn)進(jìn)行刪除操作ABCDEFG整理課件

setnull（QUEUE）創(chuàng)建一個空隊列QUEUE。empty_gueue（QUEUE）判定隊列是否為空。addqueue（QUEUE，x）入列操作。delqueue（QUEUE）出列操作。frontqueue(QUEUE）讀取隊列的隊頭元素。隊列的五種基本運(yùn)算整理課件類似于順序表類的定義，C++描述如下：constintQUEUESIZE=200;classSeqQueue{ public: ElemTypedata[QUEUESIZE];intfront,rear;SeqQueue(){front=rear=–1;};//創(chuàng)建空隊列BOOLqueue_empty();//判隊列空BOOLaddqueue(ElemTypex);//元素進(jìn)隊BOOLdelqueue(ElemType&element);//元素出隊BOOLfrontgueue(ElemType&element);//取隊頭～queue();}順序隊列類定義整理課件入列操作：rear++;data[rear]=X;出列操作：front++;X=data[front];分析：隊列空的條件front==rear隊列滿的條件rear==QUEUESIZE-1

分析隊列操作整理課件隊列假滿的狀態(tài)front==rear==QUEUESIZE-1或front>-1&&rear==QUEUESIZE-1

假設(shè)MAXSIZE為8rearfrontEFGH

frontrear整理課件解決假滿的兩種方法：1、整個隊列中的元素左移2、構(gòu)造循環(huán)隊列入列操作：rear=(rear+1)%QUEUESIZE;data[rear]=X;出列操作：front=(front+1)%QUEUESIZE;X=data[front];整理課件循環(huán)隊列示意圖0172635401234567整理課件

為了將隊空和對滿的條件加以區(qū)分，一般不使用front指針?biāo)傅奈恢谩?/p>

隊空條件為:front==rear 隊滿條件為:(rear+1)%QUEUESIZE==front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE

(a)循環(huán)隊列空(b)非空循環(huán)隊列(c)循環(huán)隊列滿循環(huán)隊列示意圖

整理課件//循環(huán)隊列進(jìn)隊函數(shù)boolSeqQueue::addqueue(ElemTypex){if((rear+1)%MAXSIZE==front){printf(“隊列已滿，元素不能進(jìn)隊列！\n”);returnfalse;}else{real=(real+1)%MAXSIZE; data[real]=x; returntrue;}}整理課件//循環(huán)隊列出隊函數(shù)boolSeqQueue::delqueue(ElemType&x){if(front==rear){printf(“隊列已空，無法刪除元素\n”);returnfalse;}else{ front=(front+1)%QUEUESIZE; x=data[front]; returntrue;}}整理課件鏈隊列—隊列鏈?zhǔn)酱鎯? 鏈隊列實(shí)質(zhì)上就是只能在頭部刪除元素、只能在尾部插入元素的單鏈表。 隊頭指針front就是單鏈表的頭指針，隊尾指針rear則是指向單鏈表最后一個結(jié)點(diǎn)的指針。

Qa1an∧frontrear非空鏈隊列

整理課件structQNode{//類似于單鏈表的C++描述如下： ElemTypedata; structQNode*next; };classLinkQueue{ public: QNode*front; //隊頭指針 QNode*rear; //隊尾指針 LinkQueue() {front=newQNode; //建立頭結(jié)點(diǎn) front->next=NULL; rear=front; //尾指針也指向頭結(jié)點(diǎn) } intLength(); //求隊列長度 voidEnQueue(ElemTypex);//入隊操作 voidDeQueue(ElemType&e);//出隊操作 voidGetHead(ElemType&e);//求隊頭元素};鏈隊列整理課件返回隊列的元素個數(shù)，即隊列的長度。intLinkQueue::Length(){ QNode*p=front; intlen=0; while(p!=rear){ len++; p=p->next; } returnlen;}求隊列的長度整理課件鏈隊列進(jìn)隊算法：1、申請新結(jié)點(diǎn)2、鏈入新結(jié)點(diǎn)

voidLinkQueue::EnQueue(ElemTypex){ QNode*s=newQNode;//建立新結(jié)點(diǎn)s s->data=x; s->next=NULL; rear->next=s; //在隊尾插入結(jié)點(diǎn)s rear=s; //修改隊尾指針}鏈隊列進(jìn)隊算法整理課件鏈隊列出隊算法：1、判斷隊列空否2、隊頭元素出隊3、出隊元素歸還操作系統(tǒng)voidLinkQueue::DeQueue(ElemType&e){ QNode*p; if(front==rear)cout<<"隊列已空"; else{ p=front->next; e=p->data; front->next=p->next; if(rear==p)rear=front; deletep; }}刪除最后一個元素時，需要修改尾指針，使其指向頭結(jié)點(diǎn)整理課件上機(jī)練習(xí)一：求兩個鏈表的交集解決方法:

建立兩個帶頭結(jié)點(diǎn)的單鏈表；通過插入函數(shù)插入兩個鏈表中的所有元素創(chuàng)建第三個帶頭結(jié)點(diǎn)的單鏈表從兩個表頭開始循環(huán)比較，只有相等才能插入整理課件上機(jī)練習(xí)二：求k階斐波那切數(shù)列某一項k階斐波那切數(shù)列{ai}定義如下：

解決方法:

建立一個容量為k的循環(huán)隊列，將前k個元素依次入隊。然后計算第k+1個元素，它等于隊列中全部元素之和。而后將對頭元素出隊，將第k+1個元素入隊。重復(fù)上述過程，就可求得任意指定項元素的值。

【例2-4】利用循環(huán)隊列求k階斐波那切數(shù)列某一式的值。整理課件前面所學(xué)的數(shù)據(jù)結(jié)構(gòu)都是線性關(guān)系結(jié)構(gòu)，即每個數(shù)據(jù)元素都只有唯一的前驅(qū)元素和唯一的后繼元素。但是在客觀世界中數(shù)據(jù)元素之間的關(guān)系不一定是線性關(guān)系，即不一定是唯一的前驅(qū)和唯一的后繼，稱為非線性關(guān)系結(jié)構(gòu)。例如分析任何一個企事業(yè)單位的組織機(jī)構(gòu)，會發(fā)現(xiàn)任何一個部門機(jī)構(gòu)，它只隸屬于一個部門機(jī)構(gòu)，而下轄一個以上部門機(jī)構(gòu)。假如把部門機(jī)構(gòu)看成數(shù)據(jù)元素，那么可以說任何一個數(shù)據(jù)元素有唯一的前驅(qū)元素，但有多個后繼元素。又例如日常生活中對事物的分類——水果的分類。非線性數(shù)據(jù)結(jié)構(gòu)：樹和圖整理課件西安交通大學(xué)管理學(xué)院電信學(xué)院醫(yī)學(xué)院信控系計算機(jī)系電子系組織機(jī)構(gòu)示意整理課件水果芒果蘋果梨香蕉紅富士黃元帥秦冠巴拿馬芝麻水果分類示意整理課件RAEGDCBXFZYKJIHMLNPOQVUTS*+%將上述分層結(jié)構(gòu)抽象成如下所示的結(jié)構(gòu)——倒置樹整理課件樹是包含n個數(shù)據(jù)元素的有限集合T（n≥1），并且滿足：（1）T中有一個稱為根的結(jié)點(diǎn)root；（2）T中除根以外的其余結(jié)點(diǎn)被分成m（n>m≥0）個互不相交的集合T1、T2…、Tm，且每一個集合又符合上述兩條，即它們本身又是一棵樹，這些樹稱為root的子樹。樹的遞歸定義T1T2…TNT3T4GACFDEB樹的一般形式整理課件結(jié)點(diǎn)——表示樹中的數(shù)據(jù)元素；樹枝——表示樹中的數(shù)據(jù)元素與數(shù)據(jù)元素之間的關(guān)系；葉子結(jié)點(diǎn)——表示沒有后繼的結(jié)點(diǎn)稱為葉子（或終端結(jié)點(diǎn)）；分支結(jié)點(diǎn)——表示非葉子結(jié)點(diǎn)稱為分支結(jié)點(diǎn)（或非終端結(jié)點(diǎn)）；結(jié)點(diǎn)的度——意指一個結(jié)點(diǎn)的子樹數(shù)目就稱為該結(jié)點(diǎn)的度；樹的度——意指一棵樹上所有結(jié)點(diǎn)的度的最大值就是這棵樹的度；結(jié)點(diǎn)的層次——確定根結(jié)點(diǎn)的層數(shù)為1，其它任何結(jié)點(diǎn)的層數(shù)等于它的父結(jié)點(diǎn)的層數(shù)加1；有關(guān)樹的基本術(shù)語整理課件樹的深度——意指一棵樹中，結(jié)點(diǎn)的最大層次值就是樹的深度；孩子結(jié)點(diǎn)——代表某結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)；雙親結(jié)點(diǎn)——相對于某結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，稱該結(jié)點(diǎn)為雙親結(jié)點(diǎn)；兄妹——意指同屬于一個雙親的孩子結(jié)點(diǎn)之間互稱為兄弟；堂兄妹——意指其雙親在同一層的結(jié)點(diǎn)之間互稱為兄弟；有序樹——如果一棵樹中結(jié)點(diǎn)的各子樹看成是從左至右依次有序排列且不能交換，則該樹就稱為有序樹；無序樹——如果一棵樹中結(jié)點(diǎn)的各子樹可以互換排列次序，則該樹稱為無序樹；森林——森林是n棵互不相交的樹的集合（n≥0）；整理課件建空樹記作setnull(T)，置T為空樹。求根結(jié)點(diǎn)記作root(x)，求x所在樹的根結(jié)點(diǎn)。求雙親結(jié)點(diǎn)記作parent(T，x)，在樹T中取出結(jié)點(diǎn)x的雙親。求孩子結(jié)點(diǎn)記作child(T,x,i)，在樹T中取出結(jié)點(diǎn)x的第i個孩子。插入結(jié)點(diǎn)記作ins_child(T,y,i,x)，將x作為樹T中y結(jié)點(diǎn)的第i個孩子。刪除子樹記作del_child(T,x,I)，即刪除樹T中x結(jié)點(diǎn)的第i棵子樹。遍歷樹記作TRAVERSE(T)，即從根結(jié)點(diǎn)出發(fā)，按某種次序，依次訪問樹中每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)只訪問一次的操作。樹的基本運(yùn)算整理課件二叉樹的定義二叉樹是n（n≥0）個結(jié)點(diǎn)的有限集合，且滿足以下兩條:(1)或者為空二叉樹，即n=0；(2)或者由一個根結(jié)點(diǎn)和兩棵互不相交的被稱為根的左子樹和右子樹所組成，左子樹和右子樹分別又是一棵二叉樹。問題：1、二叉樹可以定義為度不大于2的樹？2、三個結(jié)點(diǎn)的二叉樹有幾種形態(tài)？探討結(jié)構(gòu)較為簡單的一類樹，二叉樹整理課件創(chuàng)建空二叉樹記作setnull(BT)，置BT為空二叉樹。求二叉樹的根記作root(x)，求結(jié)點(diǎn)x所在二叉樹的根。求雙親結(jié)點(diǎn)記作parent(BT,x)，在二叉樹中求結(jié)點(diǎn)x的雙親。求左孩子結(jié)點(diǎn)記作lchild(BT,x),在二叉樹BT中求結(jié)點(diǎn)x的左孩子。求右孩子結(jié)點(diǎn)記作rchild(BT,x),在二叉樹BT中求結(jié)點(diǎn)x的右孩子。插入左孩子結(jié)點(diǎn)記作ins_lchild(BT,x,y),將結(jié)點(diǎn)y置為結(jié)點(diǎn)x的左孩子。插入右孩子結(jié)點(diǎn)記作ins_rchild(BT,x,y),將結(jié)點(diǎn)y置為結(jié)點(diǎn)x的右孩子。刪除左孩子記作del_lchild(BT,x),在二叉樹BT中，刪除結(jié)點(diǎn)x的左子樹。刪除左孩子記作del_rchild(BT,x),在二叉樹BT中，刪除結(jié)點(diǎn)x的右子樹。遍歷二叉樹記作TRAVERSE(BT),即從根結(jié)點(diǎn)出發(fā)，按某種次序，依次訪問二叉樹中每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)只訪問一次。二叉樹的基本操作整理課件左指針域數(shù)據(jù)域右指針域二叉樹的非順序存儲結(jié)構(gòu)根據(jù)二叉樹的特性：任何一個結(jié)點(diǎn)最多有左、右兩個子樹，這樣可以為樹中每個數(shù)據(jù)元素設(shè)計三個存儲區(qū)域（或稱變量）。一個域用來存放數(shù)據(jù)元素值，兩個域用來存放指向左右子樹根的指針。也就是說對于二叉樹中任意一個數(shù)據(jù)元素可以設(shè)計成如下存儲結(jié)構(gòu)。俗稱結(jié)點(diǎn)。整理課件二叉樹的二叉鏈表存儲結(jié)構(gòu)示意圖ABCFEGDABCDEGFVVVVVVVV整理課件structBinTreeNode//結(jié)點(diǎn)的定義{ ElemTypedata; structBinTreeNode*leftChild,*rightChild;};

classBinTree//二叉鏈表類的定義{public: BinTreeNode*root; //定義根結(jié)點(diǎn)指針 BinTree(){root=NULL;} //構(gòu)造函數(shù)，創(chuàng)建空樹 boolIsEmpty(){returnroot==NULL;}//判空二叉樹 voidIns_lchild(BinTreeNode*p,BinTreeNode*q) {p->leftChild=q;}//在葉子結(jié)點(diǎn)p下插入左子樹qvoidIns_rchild(BinTreeNode*p,BinTreeNode*q){p->rightChild=q; }//在葉子結(jié)點(diǎn)p下插入右子樹q

//刪除結(jié)點(diǎn)p的左子樹 voidDel_lchild(BinTreeNode*p){p->leftChild=NULL;}

//刪除結(jié)點(diǎn)p的右子樹voidDel_rchild(BinTreeNode*p){p->rightChild=NULL;} voidPreOrder(BinTreeNode*t); //先序遍歷 voidInOrder(BinTreeNode*t); //中序遍歷 voidPostOrder(BinTreeNode*t); //后序遍歷};整理課件注意：上述性質(zhì)都可以通過歸納方法進(jìn)行證明。二叉樹的性質(zhì)性質(zhì)一：二叉樹的第i層上至多有2i-1（i≥1）個結(jié)點(diǎn)。性質(zhì)二：深度為h的二叉樹上最多含有2h-1個結(jié)點(diǎn)。性質(zhì)三：包含n個結(jié)點(diǎn)的二叉樹必有n-1條樹枝(分枝)。性質(zhì)四：任何一棵二叉樹，若含有n0個葉子結(jié)點(diǎn)、n2個度為2的結(jié)點(diǎn)，則必存在關(guān)系式n0=n2+1。整理課件若一棵二叉樹的深度為h，且含有2h-1個結(jié)點(diǎn)，則稱該二叉樹為滿二叉樹。AABCABCDEGF深度為1深度為2深度為5滿二叉樹整理課件深度為4的滿二叉樹整理課件編號規(guī)則：

設(shè)滿二叉樹的深度是h，根結(jié)點(diǎn)的編號為1，其余結(jié)點(diǎn)的編號次序是從上層到下層，每層從左到右。推論：

1）若1≤i≤2h-1-1，則結(jié)點(diǎn)i的左子樹根的編號為2*i，結(jié)點(diǎn)i的右子樹根的編號為2*i+1；2）若1<i≤2h-1，則結(jié)點(diǎn)i的父結(jié)點(diǎn)的編號為(int)(i/2)；124589101136712131415整理課件設(shè)一個深度為h的二叉樹，每層結(jié)點(diǎn)數(shù)目如果滿足：1）第i層（1≤i≤h-1）上的結(jié)點(diǎn)個數(shù)均為2i-1；2）第h層從右邊起連續(xù)缺若干個結(jié)點(diǎn)。這樣的二叉樹稱為完全二叉樹。ABCDEGFH完全二叉樹ABCDE從滿二叉樹葉子所在的層次中，自右向左連續(xù)刪除若干葉子所得到的二叉樹被稱為完全二叉樹。整理課件首先將任何一棵二叉樹轉(zhuǎn)變?yōu)橄嗤疃鹊耐耆鏄洌赐ㄟ^編號順序，在每一層加上一些空結(jié)點(diǎn)，以便保證第i層上有2i-1個結(jié)點(diǎn)。其次將實(shí)結(jié)點(diǎn)和空結(jié)點(diǎn)依次存入一維數(shù)組中。ABCDEFGHABCDEFGH0123456789101112ABCDEFGH任何一棵二叉樹都可用一維數(shù)組來儲存的方法整理課件ABCD□E□□□□□F□□□□□□□□□□□G二叉樹的邏輯形態(tài)？ABC□D□E□□FG□□□H二叉樹的邏輯形態(tài)？ABCDEGFABCDEGFH問題整理課件二叉樹的遍歷根據(jù)一定的規(guī)律訪問二叉樹中的每一個結(jié)點(diǎn)，且每個結(jié)點(diǎn)只能訪問一次的過程。注意：定義中所提到的訪問，對于不同應(yīng)用問題有不同的操作意義。例如讀取二叉樹中的每一個結(jié)點(diǎn)的值，進(jìn)行統(tǒng)計計算。又比如修改二叉樹中的每一個結(jié)點(diǎn)的值等等。整理課件由于二叉樹中每個結(jié)點(diǎn)最多有兩棵子樹，也就是說一個結(jié)點(diǎn)可能有兩個后繼，所以，二叉樹的遍歷方法會有好幾種。可以將二叉樹看成如下圖所示的三個基本組成部分。這樣一來對二叉樹的訪問順序就有六種<根><左子樹><右子樹>DLR先根遍歷<左子樹><根><右子樹>LDR中根遍歷<左子樹><右子樹><根>LRD后根遍歷<根><右子樹><左子樹>DRL<右子樹><根><左子樹>RDL<右子根><左子樹><根>RLD整理課件先序遍歷——a.訪問根結(jié)點(diǎn)；b.先序遍歷左子樹；c.先序遍歷右子樹；中序遍歷——a.中序遍歷左子樹；b.訪問根結(jié)點(diǎn)；c.中序遍歷右子樹；后序遍歷——a.后序遍歷左子樹；b.后序遍歷右子樹；c.訪問根結(jié)點(diǎn)；二叉樹的三種遍歷方式整理課件ABCDEGFABCDEGFH討論下列兩棵二叉樹的遍歷先根遍歷結(jié)果：中根遍歷結(jié)果：后根遍歷結(jié)果：整理課件//假設(shè)二叉樹存儲以二叉鏈表結(jié)構(gòu)voidBinTree::PreOrder(BinTreeNode*t) { if(t) {Visit(t); //訪問根結(jié)點(diǎn)PreOrder(t->leftChild);//遍歷左子樹 PreOrder(t->rightChild);//遍歷右子樹 }}先序遍歷二叉樹的遞歸算法整理課件//中序遍歷算法voidBinTree::InOrder(BinTreeNode*t){if(t){ InOrder(t->leftChild); //遍歷左子樹 Visit(t); //訪問根節(jié)點(diǎn) InOrder(t->rightChild);//遍歷右子樹 }}//后序遍歷算法voidBinTree::PostOrder(BinTreeNode*t){if(t){ PostOrder(t->leftChild);//遍歷左子樹 PostOrder(t->rightChild);//遍歷右子樹 Visit(t); //訪問根節(jié)點(diǎn) }}整理課件非線性數(shù)據(jù)結(jié)構(gòu)：圖圖是中一種重要的、比樹更復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。在樹中，每個結(jié)點(diǎn)只與上層的父結(jié)點(diǎn)有聯(lián)系，并可以與其下層的多個子結(jié)點(diǎn)有聯(lián)系，而同一層的結(jié)點(diǎn)之間沒有任何橫向聯(lián)系。在圖中，結(jié)點(diǎn)之間的聯(lián)系是任意的，每個結(jié)點(diǎn)都可以與其它的結(jié)點(diǎn)相聯(lián)系。圖的應(yīng)用范圍非常廣泛，諸如電網(wǎng)絡(luò)分析、交通、管道線路、集成電路布圖、工程進(jìn)度安排圖等實(shí)際問題的處理都可以歸納為圖的問題整理課件圖的定義圖是由數(shù)據(jù)元素集合及數(shù)據(jù)元素間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。一般記作Graph＝(V,E)。其中V是數(shù)據(jù)元素的非空有限集合；E是數(shù)據(jù)元素之間關(guān)系的有限集合。整理課件邊和弧的含義若<Vi，Vj>屬于R，則<Vi,Vj>表示從頂點(diǎn)Vi出發(fā)到頂點(diǎn)Vj存在一條弧，其中：Vi稱之為弧尾，Vj稱之為弧頭。ViVj若（Vi，Vj）屬于R，則（Vi，Vj）表示頂點(diǎn)Vi和頂點(diǎn)Vj之間存在一條邊。ViVj整理課件無向圖集合表示：G1=(V,E)V={1,2,3,4,5}E={(1,2),(1,3),(2,3),(3,4),(4,5)}12354有向圖集合表示：G2=（V，E）V={1，2，3，4，5，6}E={<1，2>，<2，1>，<2，3>，<2，4>，<3，5><5，6>，<6，3>}214356圖的符號表示整理課件鄰接點(diǎn)：對于無向圖，如果邊（v，u）∈E，則v和u互為鄰接點(diǎn)，亦即u是v的鄰接點(diǎn)，v也是u的鄰接點(diǎn)；對于有向圖，如果弧<v，u>∈E，則u是v的鄰接點(diǎn)。頂點(diǎn)的度：在無向圖中，頂點(diǎn)的度就是以該頂點(diǎn)為一個端點(diǎn)的邊的條數(shù)。在有向圖中，以某頂點(diǎn)為弧頭的弧的數(shù)目，稱為此頂點(diǎn)的入度；以某頂點(diǎn)為弧尾的弧的數(shù)目，稱為此頂點(diǎn)的出度。該頂點(diǎn)的度則是此頂點(diǎn)的入度與出度之和。路徑：在圖G中，從頂點(diǎn)v至頂點(diǎn)u的一條路徑是指存在這樣的頂點(diǎn)的序列（v，v1，v2，…，vi，u），并且有<v，v1>，<v1,v2>,…，<vi，u>都屬于邊（弧）集合。長度：路徑上弧的數(shù)目稱為該路徑的長度。環(huán)（回路）：第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為回路或環(huán)有關(guān)圖的術(shù)語整理課件連通圖：在無向圖中，若每一對頂點(diǎn)之間都有路徑，此圖為連通圖強(qiáng)連通圖：在有向圖中，若每一對頂點(diǎn)u和v之間都在從v到u及從u到v的路徑，則稱此圖為強(qiáng)連通圖。網(wǎng)：如果圖G（V，E）中每條邊（弧）都賦有反映這條邊的某種特性的數(shù)據(jù)，則稱此圖是一個網(wǎng)。權(quán)：與邊（弧）相關(guān)的數(shù)據(jù)稱為該邊的權(quán)。通常我們用n表示圖中頂點(diǎn)數(shù)目，e表示圖中邊或弧的數(shù)目，并且下面的討論不涉及頂點(diǎn)到自身的邊或弧，因此,對于有n個頂點(diǎn)的有向圖來說,其弧的數(shù)目有0≤e≤n（n-1）。完全有向圖：在n個頂點(diǎn)的有向圖中，具有n（n-1）條弧的有向圖稱為完全有向圖。完全圖：在n個頂點(diǎn)的無向圖中，具有n(n-1）/2條邊的無向圖子圖：設(shè)有圖G=(V,E)和圖G′=（V′，E′)，若V′包含在V中，且E′包含在E中，則稱G′是G的子圖。有關(guān)圖的術(shù)語整理課件0132528130123410234(a)無向圖(b)有向圖 (c)網(wǎng)絡(luò)

術(shù)語提問？整理課件由于一個圖是由頂點(diǎn)集合V和頂點(diǎn)之間的關(guān)系集合E(即頂點(diǎn)偶對集合)。因此，設(shè)計一個圖的存儲結(jié)構(gòu)只要分別解決集合V和集合E的存貯結(jié)構(gòu)表示即可。顯然可以用一個一維數(shù)組表示集合V中的所有頂點(diǎn)；用一個二維數(shù)組來表示集合E。此二維數(shù)組被稱為鄰接矩陣。對于n個頂點(diǎn)的有向圖，則其鄰接矩陣中所有元素按如下公式來確定：對于n個頂點(diǎn)的無向圖，則其鄰接矩陣中所有元素按如下公式來確定：圖的存儲結(jié)構(gòu):鄰接矩陣整理課件.對于無向圖，鄰接矩陣第i行（或第i列）的元素之和則是頂點(diǎn)Vi的度；.對于有向圖，鄰接矩陣第i行的元素之和為頂點(diǎn)Vi的出度；鄰接矩陣第i列的元素之和為頂點(diǎn)Vi的入度。12354214356無向圖G1有向圖G2整理課件#defineMAX_NUM100 //最大頂點(diǎn)個數(shù)typedefstruct{VertexTypevexs[MAX_NUM];//頂點(diǎn)數(shù)組ArcTypeMatrix[MAX_NUM][MAX_NUM];//鄰接矩陣intvexnum;//圖的實(shí)際頂點(diǎn)數(shù)intarcnum;//圖的實(shí)際弧(邊)數(shù)intkind;//圖的種類標(biāo)志,1—有向圖, //2—有向網(wǎng),3—無向圖,4—無向網(wǎng)}MGraph;

其中ArcType是頂點(diǎn)關(guān)系的數(shù)據(jù)類型。VertexType是頂點(diǎn)的數(shù)據(jù)類型。MAX_NUM表示最多可存的頂點(diǎn)數(shù)。整理課件0132528130123410234(a)無向圖(b)有向圖 (c)網(wǎng)絡(luò)

0132401324012340123401230132(a)無向圖鄰接矩陣(b)有向圖鄰接矩陣(c)網(wǎng)絡(luò)鄰接矩陣

整理課件鄰接矩陣反映出圖中頂點(diǎn)之間的聯(lián)系，值得注意的是當(dāng)一個圖為稀疏圖時，其鄰接矩陣為稀疏矩陣。如果將鄰接矩陣看成是順序存儲結(jié)構(gòu)，那么，另一種結(jié)構(gòu)就是鏈?zhǔn)酱尜A結(jié)構(gòu)，把一個頂點(diǎn)的所有鄰接頂點(diǎn)都鏈接在同一個單鏈表上。

鄰接表存儲形式是一種鏈表與數(shù)組結(jié)合的存儲形式。在鄰接表中，圖中每個頂點(diǎn)數(shù)據(jù)存儲為數(shù)組，某個頂點(diǎn)的所有鄰接點(diǎn)建立一個單鏈表，n個頂點(diǎn)就建立n個單鏈表。鄰接表中由下列三個結(jié)點(diǎn)組成，如下圖所示：圖的存儲結(jié)構(gòu):鄰接表firstdatanextadjvex數(shù)組元素（頭結(jié)點(diǎn)）：無權(quán)圖中的單鏈表結(jié)點(diǎn)：網(wǎng)中的單鏈表的結(jié)點(diǎn)：infonextadjvex整理課件214356整理課件整理課件#defineMAX_NUM100 //頂點(diǎn)最大允許數(shù)量 structAdjNode //表結(jié)點(diǎn)類型定義{ intadjvex; //該鄰接點(diǎn)在數(shù)組中的位置 InfoTypeinfo; //該弧相關(guān)信息 structAdjNode*next; //指向下一鄰接點(diǎn)的指針};typedefstructVNode //頭結(jié)點(diǎn)類型定義{ VertexTypedata; //頂點(diǎn)信息 AdjNode*first; //指向鄰接表第一個結(jié)點(diǎn)}AdjList;typedefstruct{ AdjListheadArray[MAX_NUM]; //頭結(jié)點(diǎn)數(shù)組 intvexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) intkind; //圖的種類標(biāo)志}ALGraph;整理課件從這個定義不難看出，圖的遍歷與樹的遍歷的