《數(shù)據(jù)結構》復習資料

《數(shù)據(jù)結構》課程期末復習資料第一章：緒論一、基礎知識概念和術語(黑體字部分)。另外，注意：1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。2、數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。3、數(shù)據(jù)結構及其形式定義。 四種基本結構：①集合②線性結構③樹形結構④圖（網）狀結構4、數(shù)據(jù)結構的 邏輯結構（抽象的，與實現(xiàn)無關） 物理結構（存儲結構）順序映像（順序存儲結構）位置“相鄰” 非順序映像（鏈式存儲結構）指針表示關系5、數(shù)據(jù)類型抽象數(shù)據(jù)類型（ADT）ADT=（數(shù)據(jù)對象，數(shù)據(jù)關系，基本操作）ADT細分為原子類型，固定聚合，可變聚合類型。6、算法的概念7、算法的五個特征①有窮性②確定性③可行性④輸入（0個或多個）⑤輸出（1個或多個）8、算法設計的要求：①正確性②可讀性③健壯性④效率與低存儲量 其中正確性的四個層次（通常要求達到C層）。9、算法的時間復雜度常見有：O(1)，O(n)，O(n2)，O(log2n)分析算法的時間復雜度時，log2n常簡單記作logn。，O(nlog2分析算法的時間復雜度時，log2n常簡單記作logn。語句頻度，用歸納法計算。10、算法的空間復雜度二、算法起泡排序。另一種形式voidBubbleSortXE"BubbleSort"(DataTypea[],intn){for(i=0;i<n-1;i++)for(j=0;j<n-i-1;j++)if(a[j]>a[j+1])a[j]<—>a[j+1];}或voidBubbleSortXE"BubbleSort"(DataTypea[],intn){for(i=1;i<n;i++)for(j=0;j<n-i;j++)if(a[j]>a[j+1])a[j]<—>a[j+1];}或voidBubbleSortXE"BubbleSort"(DataTypea[],intn){for(i=0;i<n-1;i++){change=fasle;for(j=0;j<n-i-1;j++)if(a[j]>a[j+1]){a[j]<—>a[j+1];change=true;}if(!change)break;}}說明：a)考試中要求寫算法時，可用類C，也可用C程序。b)盡量書寫算法說明，言簡意賅。c)技巧：用“邊界值驗證法”檢查下標越界錯誤。如上第一個：第二個循環(huán)條件若寫作j<n-i，則當i=0時a[j+1]會越界。d)時間復雜度為O(n2)，第3個在最好情況下（待排記錄有序），時間復雜度為O(n)。第二章、線性表一、基礎知識和算法1、線性表及其特點線性表是n個數(shù)據(jù)元素的有限序列。線性結構的特點：①“第一個”②“最后一個”③前驅④后繼。這里太簡煉了，只是為了便于記憶。2、順序表—線性表的順序存儲結構（1）特點：a)邏輯上相鄰的元素在物理位置上相鄰。b)隨機訪問。（2）類型定義簡而言之，“數(shù)組+長度”不準確的說法，只為便于理解和記憶，不要在正式場合引用。凡此情形，都加引號以示提醒。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。凡此情形，都加引號以示提醒。constintMAXSIZE=線性表最大長度;typedefstruct{ DataTypeelem[MAXSIZE]; intlength;}SqList;注：a)SqList為類型名，可換用其他寫法。b)DataType是數(shù)據(jù)元素的類型，根據(jù)需要確定。c)MAXSIZE根據(jù)需要確定。如 constintMAXSIZE=64;d)課本上的SqList類型可在需要時增加存儲空間，在上面這種定義下不可以e)課本上的SqList類型定義中l(wèi)istsize表示已經分配的空間大?。ㄈ菁{數(shù)據(jù)元素的個數(shù)）。當插入元素而遇到L.length==L.listsize時，用realloc(L.elem,L.listsize+增量)重新分配內存，而realloc()函數(shù)在必要的時候自動復制原來的元素到新分配的空間中。（3）基本形態(tài)順序表空0101MAXSIZE-1...L.elem[]L.elem[]L.elem[]L.length==0L.length==MAXSIZE0<L.length<MAXSIZE不允許刪除操作順序表滿條件L.length==MAXSIZE不允許插入操作不空也不滿可以插入，刪除（4）基本算法——遍歷順序訪問所有元素for(i=0;i<L.length;i++)visit(L.elem[i]);5查找元素xfor(i=0;i<L.length;i++)if(L.elem[i]==x)break;if(i<L.length)找到;else未找到;插入算法ListInsert(&L,i,x)前提：表不滿合理的插入范圍：1≤i≤L.length+1注：位序i在C/C++中對應于下標i-1。步驟第i至最后所有元素后移一個元素在第i個位置插入元素x表長增1算法bool這里返回true表示正確插入，返回false表示插入失敗。以下常用來區(qū)分操作是否正確執(zhí)行。ListInsertXE"ListInsert"(SqList&L,inti,DataTypex)這里返回true表示正確插入，返回false表示插入失敗。以下常用來區(qū)分操作是否正確執(zhí)行。{if(L.length==MAXSIZE||i<1||i>L.length+1)returnfalse;//失敗//元素后移for(j=L.length-1;j>=i-1;j--) //這里j為下標，從L.length-1到i-1L.elem[j+1]=L.elem[j]; //若作為位序，有如何修改？//插入xL.elem[i-1]=x;//表長增1L.length++;returntrue;//插入成功}刪除算法ListDelete(&L,i,&x)前提：表非空合理的刪除范圍：1≤i≤L.length步驟取出第i個元素第i個元素之后的元素向前移動一個位置表長減1算法boolListDeleteXE"ListDelete"(SqList&L,inti,DataType&x){if(L.length==0||i<1||i>L.length)returnfalse;//失敗x=L.elem[i-1];for(j=i;j<L.length;j++)L.elem[j-1]=L.elem[j];L.length--;returntrue;//刪除成功}算法分析表STYLEREF1\s2.SEQ表\*ARABIC\s11順序表插入和刪除算法的分析插入刪除基本操作平均移動次數(shù)移動元素移動元素時間復雜度O(n)O(n)尾端操作插入第n+1個元素，不移動刪除第n個元素，不移動插入、刪除需移動大量元素O(n)；但在尾端插入、刪除效率高O(1)。其他算法InitList(&L),ClearList(&L)L.length=0;ListEmpty(L)returnL.length==0;ListLength(L)returnL.length;GetElem(L,i,&e)e=L.elem[i-1];單鏈表——線性表的鏈式存儲結構之一概念線性鏈表，單鏈表，結點；數(shù)據(jù)域，指針域；頭指針，頭結點。特點用指針表示數(shù)據(jù)之間的邏輯關系（邏輯相鄰的元素物理位置不一定相鄰）。類型定義簡而言之，“數(shù)據(jù)+指針”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。datanexttypedefstructdatanextDataTypedata;structLNode*next;}LNode,*LinkList;基本形態(tài)帶頭結點的單鏈表的基本形態(tài)有：單鏈表空/\a/\an/\CBA(b)(a)Ea1LL...單鏈表不空條件：L->next!=0基本算法（遍歷）順序訪問所有元素借助指針，“順藤摸瓜”(沿著鏈表訪問結點)。p=L->next; //注意起始位置的考慮while(p!=NULL){ //判表尾，另外(p!=0)或(p)均可visit(p->data); //訪問:可以換成各種操作p=p->next; //指針沿著鏈表向后移動}例：打印單鏈表中的數(shù)據(jù)。voidPrintLinkListXE"PrintLinkList"(LinkListL){p=L->next;while(p!=NULL){print(p->data); //訪問：打印數(shù)據(jù)域p=p->next;}}查找元素x//在單鏈表L中查找元素x//若找到，返回指向該結點的指針；否則返回空指針LinkListFindXE"Find"(LinkListL,DataTypex){p=L->next;while(p!=NULL){if(p->data==x)returnp;//找到xp=p->next;}returnNULL;//未找到}//在單鏈表L中查找元素x//若找到，返回該元素的位序；否則返回0intFindXE"Find"(LinkListL,DataTypex){p=L->next;j=1;while(p!=NULL){if(p->data==x)returnj;//找到xp=p->next;j++; //計數(shù)器隨指針改變}return0;//未找到}前一個算法的另一種寫法：p=L->next;while(p&&p->data!=x)p=p->next;if(p&&p->data==x)returnp;elsereturn0;或者p=L->next;while(p&&p->data!=x)p=p->next;returnp;//為什么查找第i個元素LinkListGetXE"Get"(LinkListL,inti){p=L->next;j=1;while(p&&j<i){p=p->next;j++;}if(p&&j==i)returnp;elsereturn0;}查找第i-1個元素p=L;j=0;while(p&&j<i-1){p=p->next;j++;}if(p&&j==i-1)returnp;elsereturn0;插入算法ListInsert(&L,i,x)技巧：畫圖輔助分析。思路：先查找第i-1個元素若找到，在其后插入新結點bool這里返回true表示正確插入，返回false表示插入失敗。ListInsertXE"ListInsert"(LinkList&L,inti,DataTypex)這里返回true表示正確插入，返回false表示插入失敗。{//查找第i-1個元素pp=L;j=0;while(p&&j<i-1){p=p->next;j++;}//若找到，在p后插入xai-1·-插入前ai-1·-插入前執(zhí)行①之后執(zhí)行②之后·-pxsai-1·-·-px·-sai-1·-·-px·-s①②①s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next; //①p->next=s; //②returntrue;//插入成功}elsereturnfalse;//插入失敗}注意：a)要讓p指向第i-1個而不是第i個元素（否則，不容易找到前驅以便插入）。b)能夠插入的條件：p&&j==i-1。即使第i個元素不存在，只要存在第i-1個元素，仍然可以插入第i個元素。c)新建結點時需要動態(tài)分配內存。s=(LinkList)malloc(sizeof(LNode));若檢查是否分配成功，可用if(s==NULL)exit(1);//分配失敗則終止程序d)完成插入的步驟：①②。技巧：先修改新結點的指針域。刪除算法ListDelete(&L,i,&x)思路：先查找第i-1個元素若找到且其后存在第i個元素，則用x返回數(shù)據(jù)，并刪除之ai-1·-刪除前ai·-p·-saai-1·-刪除前ai·-p·-sai-1·-執(zhí)行①之后ai·-p·-①sai-1·-執(zhí)行②之后ai·-p·-①②{//查找第i-1個元素pp=L;j=0;while(p&&j<i-1){p=p->next;j++;}//若存在第i個元素，則用x返回數(shù)據(jù)，并刪除之if(p&&j==i-1&&p->next){//可以刪除s=p->next; //①p->next=s->next; //②x=s->data;free(s);returntrue;}elsereturnfalse;}注意：a)要求p找到第i-1個而非第i個元素。為什么？b)能夠進行刪除的條件：p&&j==i-1&&p->next。條件中的p->next就是要保證第i個元素存在，否則無法刪除。若寫成p->next&&j==i-1也不妥，因為此時(循環(huán)結束時)可能有p==NULL，所以必須先確定p不空。技巧：將條件中的“大前提”放在前面。該條件也不可以寫成p->next&&p&&j==i-1，因為先有p!=0才有p->next，上式顛倒了這一關系。c)釋放結點的方法。free(s);d)完成刪除的步驟：①②。建立鏈表的兩種方法思路：建立空表（頭結點）；依次插入數(shù)據(jù)結點（每次插入表尾得(a1,a2,…,an)，每次插入表頭得(an,…,a2,a1)）。順序建表voidCreateLinkListXE"CreateLinkList"(LinkList&L,intn){//建立空表L=(LinkList)malloc(sizeof(LNode));L->next=NULL; //空表p=L; //用p指向表尾//插入元素for(i=0;i<n;i++){scanf(x);s=(LinkList)malloc(sizeof(LNode));s->data=x;//插入表尾s->next=p->next;p->next=s;p=s; //新的表尾}}逆序建表voidCreateLinkListXE"CreateLinkList"(LinkList&L,intn){//建立空表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//空表//插入元素for(i=0;i<n;i++){scanf(x);s=(LinkList)malloc(sizeof(LNode));s->data=x;//插入表頭s->next=L->next;L->next=s;}}循環(huán)鏈表特點最后一個結點的指針指向頭結點。ananCBA(b)(a)Ea1L...L同單鏈表。基本形態(tài)空表：L->next==L。非空表。與單鏈表的聯(lián)系判斷表尾的方法不同：單鏈表用p==NULL；循環(huán)鏈表用p==L。其余操作相同。雙向循環(huán)鏈表特點一個結點包含指向后繼(next)和指向前驅(prior)兩個指針，兩個方向又分別構成循環(huán)鏈表。datapriordatapriornexttypedefstructDuLNode{DataTypedata;structDuLNode*prior,*next;//兩個指針}DuLNode,*DuLinkList;基本形態(tài)空表：用后向指針判斷L->next==L，或者用前向指針判斷L->prior==L。非空表。aa1a2anLL......與單鏈表和循環(huán)鏈表的聯(lián)系最大不同：前驅容易求得，可以向前遍歷。判斷表尾的方法與循環(huán)鏈表相同：p==L。插入和刪除時需要修改兩個方向的指針。插入和刪除需要修改兩個方向的指針。例如：(見下表)表STYLEREF1\s2.SEQ表\*ARABIC\s12雙向循環(huán)鏈表的插入和刪除p之后插入sp之前插入s刪除p之后繼s刪除ps->next=p->next;p->next=s;s->prior=p;s->next->prior=s;s->prior=p->prior;p->prior=s;s->next=p;s->prior->next=s;s=p->next;p->next=s->next;p->next->prior=p;p->prior->next=p->next;p->next->prior=p->prior;順序表與單鏈表的比較表STYLEREF1\s2.SEQ表\*ARABIC\s13順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關系用指針表示關系隨機訪問，取元素O(1)順序訪問，取元素O(n)插入、刪除需要移動元素O(n)插入、刪除不用移動元素O(n)(用于查找位置)總結：需要反復插入、刪除，宜采用鏈表；反復提取，很少插入、刪除，宜采用順序表。第三章、棧和隊列棧棧，棧頂，棧底，空棧，后進先出(LIFO)，入棧(Push)，出棧(Pop)。順序棧：棧的順序存儲結構；鏈棧：棧的鏈式存儲結構。鏈棧存儲結構a1a1/\anS...an-1類型定義同單鏈表?；拘螒B(tài)a1a1/\anS...an-1S/\條件:S==NULL棧非空棧滿（一般不出現(xiàn)）基本算法入棧Push(&s,x)boolPushXE"Push"(LinkList&s,DataTypex){//新建結點p=(LinkList)malloc(sizeof(LNode));if(!p)returnfalse;//失敗p->data=x;//插入棧頂p->next=s;s=p;returntrue;}出棧Pop(&s,&x)前提：棧非空。boolPopXE"Pop"(LinkList&s,DataType&x){if(s==NULL)returnfalse;//?？?/刪除棧頂元素p=s;s=s->next;x=p->data;free(p);returntrue;}棧頂元素前提：棧非空。boolTopXE"Top"(LinkList&s,DataType&x){if(s==NULL)returnfalse;//?？誼=s->data;returntrue;}順序棧存儲結構類似于順序表，插入和刪除操作固定于表尾。類型定義簡單說，“數(shù)組+長度”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。constintMAXSIZE=棧的最大容量；typedefstruct{DataTypeelem[MAXSIZE];inttop;}SqStack;基本形態(tài)?？諚l件s.top==0;棧滿條件s.top==MAXSIZE棧不空、不滿基本算法入棧Push(&s,x)前提：棧不滿boolPushXE"Push"(SqStack&s,DataTypex){if(s.top==MAXSIZE)returnfalse;//棧滿s.elem[top]=x; //或者s.elem[top++]=x;top++; //代替這兩行returntrue;}出棧Pop(&s,&x)前提：棧非空boolPopXE"Pop"(SqStack&s,DataType&x){if(s.top==0)returnfalse;top--; //可用x=s.elem[--top];x=s.elem[top]; //代替這兩行returntrue;}棧頂元素前提：棧非空s.elem[top-1]即是。隊列隊列，隊頭，隊尾，空隊列，先進先出(FIFO)。鏈隊列：隊列的鏈式存儲結構。循環(huán)隊列：隊列的順序存儲結構之一。鏈隊列存儲結構/\·-a1/\·-a1·-a2·-an/\...Q.frontQ.rearQ.frontQ.rear不準確的說法，只為便于理解和記憶，不要在正式場合引用。類型定義typedefstruct{LinkListfront;LinkListrear;}LinkQueue;基本形態(tài)隊列空：Q.front==Q.rear。非空隊列?；舅惴ㄈ腙犃胁迦腙犖?，注意保持Q.rear指向隊尾。出隊列刪除隊頭元素，特別注意：如果隊列中只有一個元素，則隊頭也同時是隊尾，刪除隊頭元素后也需要修改隊尾指針。循環(huán)隊列存儲結構簡單說，“數(shù)組+頭、尾位置”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。類型定義constintMAXSIZE=隊列最大容量;typedefstruct{DataTypeelem[MAXSIZE];intfront,rear; //隊頭、隊尾位置}SqQueue;基本形態(tài)通常少用一個元素區(qū)分隊列空和隊列滿，也可以加一標志。約定front指向隊頭元素的位置，rear指向隊尾的下一個位置，隊列內容為[front,rear)。隊列空條件：Q.front==Q.rear。不能出隊列。隊列滿條件：(Q.rear+1)%MAXSIZE==Q.front（少用一個元素時）。不能入隊列。隊列不空也不滿frontfrontreara1rearfronta3a2a4a1rearfronta3a2frontreartag:0frontreara3a4a1a2frontreartag:1a3a4a5a1a2加一標志區(qū)分隊列空和隊列滿的情況可以用滿所有空間。隊列空和隊列滿時都有Q.front==Q.rear，再用標志區(qū)分。隊列空：Q.front==Q.rearandQ.tag==0；隊列滿：Q.front==Q.rearandQ.tag==1?；舅惴ㄈ腙犃星疤幔宏犃胁粷M。boolEnQueueXE"EnQueue"(SqQueue&Q,DataTypex){if((Q.rear+1)%MAXSIZE==Q.front)returnfalse;//隊列滿//入隊列Q.elem[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;returntrue;}出隊列前提：隊列非空。boolDeQueueXE"DeQueue"(SqQueue&Q,DataType&x){if(Q.front==Q.rear)returnfalse;//隊列空//出隊列x=Q.elem[Q.front];Q.front=(Q.front+1)%MAXSIZE;returntrue;}隊列中元素個數(shù)結論：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。intQueueLengthXE"QueueLength"(SqQueueQ){return(Q.rear-Q.front+MAXSIZE)%MAXSIZE;}用標志區(qū)分隊列空和滿用標志區(qū)分隊列空和滿時，隊列初始化、入隊列、出隊列和隊列長度的算法如下：voidInitQueueXE"InitQueue"(SqQueue&Q){Q.front=Q.rear=0;Q.tag=0;}boolEnQueueXE"EnQueue"(SqQueue&Q,DataTypex){if(Q.front==Q.rearandQ.tag==1)returnfalse;Q.elem[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.tag==0)Q.tag=1; //隊列非空returntrue;}boolDeQueueXE"DeQueue"(SqQueue&Q,DataType&x){if(Q.front==Q.rearandQ.tag==0)returnfalse;x=Q.elem[Q.front];Q.front=(Q.front+1)%MAXSIZE;if(Q.front==Q.rear)Q.tag=0; //隊列空returntrue;}intQueueLengthXE"QueueLength"(SqQueueQ){if(Q.front==Q.rearandQ.tag==1)returnMAXSIZE; //隊列滿elsereturn(Q.rear-Q.front+MAXSIZE)%MAXSIZE; //隊列不滿(包含隊列空的情況)}棧和隊列比較都是線形結構，棧的操作LIFO（后進先出），隊列操作FIFO（先進先出）。簡化的棧和隊列結構在算法中使用棧和隊列時可以采用簡化的形式。表STYLEREF1\s3.SEQ表\*ARABIC\s11簡化的棧和隊列結構簡化棧簡化隊列結構“s[]+top”結構“q[]+front+rear”初始化top=0;初始化front=rear=0;入棧s[top++]=x;入隊列q[rear]=x;rear=(rear+1)%MAXSIZE;出棧x=s[--top];出隊列x=q[front];front=(front+1)%MAXSIZE;棧頂s[top-1]隊列頭q[front]?？誸op==0隊列空front==rear說明：只要棧(隊列)的容量足夠大，算法中可以省去檢查棧(隊列)滿的情況。棧和隊列的應用表達式求值括號匹配例：檢查表達式中的括號是否正確匹配。如{()[]}正確，([)]}則錯誤。分析：每個左括號都“期待”對應的右括號，匹配成功則可以消去。思路：遇到左括號則入棧，遇到右括號則與棧頂括號相比較，如果匹配則消去，否則匹配失敗。當然，如果棧中沒有括號可以匹配，或者最后棧中還有未匹配的左括號，也都是匹配錯誤。//檢查輸入的表達式中括號是否匹配boolMatchBracketsXE"MatchBrackets"(){constintMAXSIZE=1024; //棧的最大容量chars[MAXSIZE]; //簡化的棧結構inttop; //棧頂//棧初始化top=0;//檢查括號是否匹配ch=getchar();while(ch!=EOF){switch(ch){case‘(‘,‘[’,‘{’:s[top++]=ch; //所有左括號入棧break;case‘)’:if(top==0ors[--top]!=’(’)returnfalse; //?？栈蛴依ㄌ柵c棧頂左括號失配case‘]’:if(top==0ors[--top]!=’[’)returnfalse;case‘}’:if(top==0ors[--top]!=’{’)returnfalse;}ch=getchar(); //取下一個字符}if(top==0)returntrue; //正好匹配elsereturnfalse; //棧中尚有未匹配的左括號}遞歸程序的非遞歸化將遞歸程序轉化為非遞歸程序時常使用棧來實現(xiàn)。作業(yè)排隊如操作系統(tǒng)中的作業(yè)調度中的作業(yè)排隊，打印機的打印作業(yè)也排成隊列。按層次遍歷二叉樹voidLevelOrderXE"LevelOrder"(BinTreebt,VisitFuncvisit){constintMAXSIZE=1024; //隊列容量(足夠大即可)BinTreeq[MAXSIZE]; //簡化的隊列結構intfront,rear; //隊頭、隊尾if(!bt)return;//初始化隊列，根結點入隊列front=rear=0;q[rear]=bt;rear=(rear+1)%MAXSIZE;//隊列不空，則取出隊頭訪問并將其左右孩子入隊列while(front!=rear){p=q[front];front=(front+1)%MAXSIZE;if(p){visit(p->data); //訪問結點q[rear]=p->lchild;rear=(rear+1)%MAXSIZE;q[rear]=p->rchild;rear=(rear+1)%MAXSIZE;}}}第四章串基礎知識和算法概念串，空串，空格串，串的長度；子串，子串在主串中的位置，主串；串相等。串的基本操作表STYLEREF1\s4.SEQ表\*ARABIC\s11串的基本操作Assign(s,t),Create(s,cs)Assign(s,t)將變量t賦值給s，Create(s,cs)根據(jù)字串創(chuàng)建變量s。Equal(s,t),Length(s)判斷串相等，求串長度。如Length(“”)=0。Concat(s,t)串連接。如Concat(“ab”,”cd”)=”abcd”。Substr(s,pos,len)取子串，pos為開始位置，len為子串長度。Index(s,t)求子串t在主串s中的位置。如Index(“abc”,”ab”)=1，Index(“abc”,”bc”)=3。Replace(s,t,v)把串s中的字串t替換成v。如Replace(“aaa”,”aa”,”a”)=”aa”。Delete(s,pos,len)刪除串s的一部分。注：完成習題集4.1~4.6。串的存儲結構表STYLEREF1\s4.SEQ表\*ARABIC\s12串的存儲結構定長順序串最大長度固定，超過最大長度則作截斷處理堆分配存儲表示串的長度幾乎沒有限制塊鏈存儲表示塊內存儲空間連續(xù)，塊間不連續(xù)樹和二叉樹基礎知識和算法樹及有關概念樹，根，子樹；結點，結點的度，葉子（終端結點），分支結點（非終端結點），內部結點，樹的度；孩子，雙親，兄弟，祖先，子孫，堂兄弟；層次（根所在層為第1層），深度，高度；有序樹，無序樹，二叉樹是有序樹；森林。二叉樹二叉樹（二叉樹與度為2的樹不同，二叉樹的度可能是0，1，2）；左孩子，右孩子。二叉樹的五種基本形態(tài)。二叉樹的性質二叉樹的第i層本書中約定根結點在第1層，也有約定根在第0層的，則計算公式會有所不同。上至多有2i-1本書中約定根結點在第1層，也有約定根在第0層的，則計算公式會有所不同。深度為k的二叉樹至多有2k-1個結點。滿二叉樹：深度為k，有2k-1個結點。完全二叉樹：給滿二叉樹的結點編號，從上至下，從左至右，n個結點的完全二叉樹中結點在對應滿二叉樹中的編號正好是從1到n。葉子結點n0，度為2的結點為n2，則n0=n2+1。考慮結點個數(shù)：n=n0+n1+n2考慮分支個數(shù)：n-1=2n2+n1可得n0=n2+1例：1)二叉樹有n個葉子，沒有度為1的結點，共有個結點。2)完全二叉樹的第3層有2個葉子，則共有個結點。分析：1)度為2的結點有n-1個，所以共2n-1個結點。2)注意考慮到符合條件的二叉樹的深度可能是3或4，所以有5、10或11個結點。n個結點的完全二叉樹深度為。n個結點的完全二叉樹，結點按層次編號有：i的雙親是，如果i=1時為根（無雙親）；i的左孩子是2i，如果2i>n，則無左孩子；i的右孩子是2i+1，如果2i+1>n則無右孩子。二叉樹的存儲結構順序存儲結構用數(shù)組、編號i的結點存放在[i-1]處。適合于存儲完全二叉樹。鏈式存儲結構二叉鏈表：typedefstructBTNode{DataTypedata;structBTNode*lchild,*rchild;}BTNode,*BinTree;三叉鏈表：typedefstructBTNode{DataTypedata;structBTNode*lchild,*rchild,*parent;}BTNode,*BinTree;datadataparentlchildrchilddatarchildlchild例：用二叉鏈表存儲n個結點的二叉樹(n>0)，共有(_a_)個空指針域；采用三叉鏈表存儲，共有(_b_)個空指針域。答案：(a)n+1(b)n+2。提示：只有根結點沒有雙親。二叉樹的五種基本形態(tài)①①②③④⑤①空樹：bt==NULL②左右子樹均空：bt->lchild==NULLandbt->rchild==NULL③右子樹為空：bt->rchild==NULL④左子樹為空：bt->lchild==NULL⑤左右子樹均非空。前兩種常作為遞歸結束條件，后三者常需要遞歸。遍歷二叉樹常見有四種遍歷方式-+-+/a*b-cdef按層次遍歷：“從上至下，從左至右”，利用隊列。先序遍歷：DLR；中序遍歷：LDR；后序遍歷LRD。例：寫出a+b*(c-d)-e/f的前綴、中綴和后綴表達式。畫出二叉樹，分別進行前序、中序、后序遍歷即可得到。前綴表達式：-+a*b-cd/ef中綴表達式：a+b*c-d-e/f后綴表達式：abcd-*+ef/-先序遍歷算法voidPreorderXE"Preorder"(BinTreebt){if(bt){visit(bt->data);Preorder(bt->lchild);Preorder(bt->rchild);}}中序遍歷算法voidInorderXE"Inorder"(BinTreebt){if(bt){Inorder(bt->lchild);visit(bt->data);Inorder(bt->rchild);}}后序遍歷voidPostorderXE"Postorder"(BinTreebt){if(bt){Postorder(bt->lchild);Postorder(bt->rchild);visit(bt->data);}}按層次遍歷思路：利用一個隊列，首先將根（頭指針）入隊列，以后若隊列不空則取隊頭元素p，如果p不空，則訪問之，然后將其左右子樹入隊列，如此循環(huán)直到隊列為空。voidLevelOrderXE"LevelOrder"(BinTreebt){//隊列初始化為空InitQueue(Q);//根入隊列EnQueue(Q,bt);//隊列不空則繼續(xù)遍歷while(!QueueEmpty(Q)){DeQueue(Q,p);if(p!=NULL){visit(p->data);//左、右子樹入隊列EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);}}}若隊列表示為“數(shù)組q[]+頭尾front,rear”有：voidLevelOrderXE"LevelOrder"(BinTreebt){constintMAXSIZE=1024;BinTreeq[MAXSIZE];intfront,rear;//隊列初始化為空front=rear=0;//根入隊列q[rear]=bt;rear=(rear+1)%MAXSIZE;//隊列不空則循環(huán)while(front!=rear){p=q[front];front=(front+1)%MAXSIZE;if(p){visit(p->data);//左、右子樹入隊列q[rear]=p->lchild;rear=(rear+1)%MAXSIZE;q[rear]=p->rchild;rear=(rear+1)%MAXSIZE;}}}非遞歸遍歷二叉樹一般借助棧實現(xiàn)。設想一指針沿二叉樹中序順序移動，每當向上層移動時就要出棧。(a)中序非遞歸遍歷指針p從根開始，首先沿著左子樹向下移動，同時入棧保存；當?shù)竭_空子樹后需要退棧訪問結點，然后移動到右子樹上去。voidInOrderXE"InOrder"(BinTreebt,VisitFuncvisit){InitStack(S);p=bt;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);visit(p); //中序訪問結點的位置p=p->rchild;}}}(b)先序非遞歸遍歷按照中序遍歷的順序，將訪問結點的位置放在第一次指向該結點時。voidPreorderXE"Preorder"(BinTreebt,VisitFuncvisit){InitStack(S);p=bt;while(p||!StackEmpty(S)){if(p){visit(p); //先序訪問結點的位置Push(S,p);p=p->lchild;}else{Pop(S,p);p=p->rchild;}}}或者，由于訪問過的結點便可以棄之不用，只要能訪問其左右子樹即可，寫出如下算法。voidPreorderXE"Preorder"(BinTreebt,VisitFuncvisit){InitStack(S);Push(S,bt);while(!StackEmpty(S)){Pop(S,p);if(p){visit(p);Push(S,p->rchild); //先進棧，后訪問，所以Push(S,p->lchild); //這里先讓右子樹進棧}}}(c)后序非遞歸遍歷后序遍歷時，分別從左子樹和右子樹共兩次返回根結點，只有從右子樹返回時才訪問根結點，所以增加一個棧標記到達結點的次序。voidPostOrderXE"PostOrder"(BinTreebt,VisitFuncvisit){InitStack(S),InitStack(tag);p=bt;while(p||!StackEmpty(S)){if(p){Push(S,p),Push(tag,1); //第一次入棧p=p->lchild;}else{Pop(S,p),Pop(tag,f);if(f==1){//從左子樹返回，二次入棧，然后p轉右子樹Push(S,p),Push(tag,2);p=p->rchild;}else{//從右子樹返回(二次出棧)，訪問根結點，p轉上層visit(p);p=NULL; //必須的，使下一步繼續(xù)退棧}}}}注：后序非遞歸遍歷的過程中，棧中保留的是當前結點的所有祖先。這是和先序及中序遍歷不同的。在某些和祖先有關的算法中，此算法很有價值。三叉鏈表的遍歷算法下面以中序遍歷為例。//中序遍歷三叉鏈表存儲的二叉樹voidInorderXE"Inorder"(BinTreebt,VisitFuncvisit){if(bt==NULL)return; //空樹，以下考慮非空樹//找到遍歷的起點p=bt; //Note:p!=nullherewhile(p->lchild)p=p->lchild;//開始遍歷while(p){//訪問結點visit(p);//p轉下一個結點if(p->rchild){ //右子樹不空，下一個在右子樹p=p->rchild;while(p->lchild)p=p->lchild; //轉右子樹的最左下結點}else{ //右子樹為空，下一個在上層f=p->parent;while(p==f->rchild){ //若p是右子樹則一直上溯p=f;f=f->parent;}}}}遍歷二叉樹的應用寫出遍歷序列（前、中、后序）ABABCDEGHF(a)已知前序和中序序列，唯一確定二叉樹。例：前序：ABDEGCFH，中序：DBGEAFHC，畫出二叉樹。分析：前序序列的第一個是根，這是解題的突破口。步驟：①前序序列的第一個是根②在中序序列中標出根，分成左右子樹③在前序序列中標出左右子樹(根據(jù)結點個數(shù)即可)④分別對左右子樹的前序和中序序列重復以上步驟直至完成。(b)已知后序和中序序列，唯一確定二叉樹。例：后序：DGEBHFCA，中序：DBGEAFHC，畫出二叉樹。分析：后序序列的最后一個是根，這是解題的突破口。步驟：①后序序列的最后一個是根②在中序序列中標出根，分成左右子樹③在后序序列中標出左右子樹(根據(jù)結點個數(shù)即可)④分別對左右子樹的后序和中序序列重復以上步驟直至完成。(c)已知前序和后序序列，不存在度為1的結點時能唯一確定二叉樹。例：前序：ABDEC，后序：DEBCA，畫出二叉樹。又前序AB，后序BA則不能唯一確定二叉樹。注：對于不存在度為1的結點的二叉樹，首先確定根結點，然后總可以將其余結點序列劃分成左右子樹，以此類推即可確定二叉樹。說明：畫出二叉樹后可以進行遍歷以便驗證。編寫算法思路：按五種形態(tài)(①--⑤)分析，適度簡化。例：求二叉樹結點的個數(shù)。分析：①0;②1;③L+1;④1+R;⑤1+L+R。簡化：②1+L=0+R=0③1+L+R=0④1+L=0+R⑤1+L+R可合并成⑤一種情況。intNodeCount(BinTreebt){if(bt==0)return0;elsereturn1+NodeCount(bt->lchild)+NodeCount(bt->rchild);}例：求二叉樹葉子結點的個數(shù)。分析：①0;②1;③L;④R;⑤L+R。簡化：③④⑤可合并成⑤。intLeafCount(BinTreebt){if(bt==0)return0;elseif(bt->lchild==0andbt->rchild==0)return1;elsereturnLeafCount(bt->lchild)+LeafCount(bt->rchild);}例：求二叉樹的深度。分析：①0;②1;③1+L;④1+R;⑤1+max(L,R)。簡化：②③④⑤可合并成⑤。intDepth(BinTreebt){if(bt==0)return0;elsereturn1+max(Depth(bt->lchild),Depth(bt->rchild));}線索二叉樹線索n個結點的二叉鏈表中有n+1個空指針，可以利用其指向前驅或后繼結點，叫線索，同時需附加一個標志，區(qū)分是子樹還是線索。 lchildlchildltagdatartagrchild0/10/1lchild 有左子樹，則指向左子樹，標志ltag==0； 沒有左子樹，可作為前驅線索，標志ltag==1。rchild 有右子樹，則指向右子樹，標志rtag==0； 沒有右子樹，可作為后繼線索，標志rtag==1。線索化二叉樹利用空指針作為線索指向前驅或后繼。左邊空指針可以作為前驅線索，右邊空指針可以作為后繼線索，可以全線索化或部分線索化。表STYLEREF1\s6.SEQ表\*ARABIC\s11線索化二叉樹的類型前驅、后繼線索前驅線索后繼線索中序線索化中序全線索中序前驅線索中序后繼線索前序線索化前序全線索前序前驅線索前序后繼線索后序線索化后序全線索后序前驅線索后序后繼線索畫出線索二叉樹思路：先寫出遍歷序列，再畫線索。步驟： 標出必要的空指針（前驅左指針；后繼右指針，要點：“不要多標，也不要少標”）。 寫出對應的遍歷序列（前序，中序或后序）。ABCABCDEGHFABCDEGHF例：畫出圖中二叉樹的后序后繼線索。步驟：先標出所有空的右指針(DGCH)；寫出后序遍歷結果：DGEBHFCA；標出后繼線索：DG,GE,CA,HF。如圖。遍歷線索二叉樹反復利用孩子和線索進行遍歷，可以避免遞歸。樹和森林樹的存儲結構雙親表示法，孩子表示法，孩子兄弟表示法。特點：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也可以增加指向雙親的指針來解決。樹與二叉樹的轉換表STYLEREF1\s6.SEQ表\*ARABIC\s12樹和二叉樹的對應關系樹對應的二叉樹根根第一個孩子左孩子下一個兄弟右孩子特點：由樹轉化成的二叉樹，根結點沒有右孩子例：樹轉換成二叉樹。 AABICDFHGJKEABICDFHGJKE森林與二叉樹的轉換森林中第1棵樹的根作為對應的二叉樹的根；其他的樹看作第1棵樹的兄弟；森林中的樹轉換成對應的二叉樹。則森林轉換成對應的二叉樹。例：將森林轉換成對應的二叉樹。參見課本P138。樹的遍歷樹的結構：①根，②根的子樹。先根遍歷：①②。例：ABCDEFGHIJK。后根遍歷：②①。例：CEDFBHGJKIA。遍歷森林森林的結構：①第一棵樹的根，②第一棵樹的根的子樹森林，③其余樹(除第一棵外)組成的森林。先序遍歷：①②③。例：ABCDEFGHIJ。中序遍歷：②①③。例：BDCEAGFIJH。注：先序遍歷森林，相當于依次先根遍歷每一棵樹；中根遍歷森林相當于后根遍歷每一棵樹。AABICDFHGJKEAHBCEGFIJD①①②②③樹的結構劃分森林的結構劃分遍歷樹、森林與遍歷二叉樹的關系表STYLEREF1\s6.SEQ表\*ARABIC\s13遍歷樹、森林和二叉樹的關系樹森林二叉樹先根遍歷先序遍歷先序遍歷后根遍歷中序遍歷中序遍歷赫夫曼樹及其應用最優(yōu)二叉樹(赫夫曼樹，哈夫曼樹)樹的帶權路徑長度：所有葉子結點的帶權路徑長度之和。 路徑長度lk按分支數(shù)目計算。帶權路徑長度最小的二叉樹稱為最優(yōu)二叉樹，或赫夫曼樹(哈夫曼樹)。構造赫夫曼樹算法：簡單說，“每次取兩個最小的樹組成二叉樹”不準確的說法，只為便于理解和記憶，不要在正式場合引用。不準確的說法，只為便于理解和記憶，不要在正式場合引用。赫夫曼編碼(前綴碼)向左分支為0，向右分支為1，從根到葉子的路徑構成葉子的前綴編碼。例：字符及其權值如下：A(6),B(7),C(1),D(5),E(2),F(8)，構造哈夫曼樹和哈夫曼編碼，計算帶權路徑長度。A6A6B7C1D5E2F8A6B7C1D5E2F83A6A6B7C1D5E2F88A6B7C1D5E2F8813A6A6B7C1D5E2F81316A6B7C1D5E2F8AABCDEF0010001111哈夫曼編碼：A:00B:01C:1110D:110E:1111F:10WPL=(6+7+8)*2+5*3+(1+2)*4=69哈夫曼樹或采用課本上的算法計算，如下。表STYLEREF1\s6.SEQ表\*ARABIC\s14赫夫曼算法weightparentlchildrchildweightparentlchildrchild1A60001A69002B70002B79003C10003C17004D50004D58005E20005E27006F80006F810007000073835800008810479000091311121000001016116811000011290910結果同上。說明：同樣的一組權值可能構造出不同的哈夫曼樹，結果不一定唯一，但帶權路徑長度都是最小的。技巧：要使前一種方法構造出的赫夫曼樹和課本上算法產生的一樣，只要把每次合并產生的二叉樹放在樹的集合的末尾，并且總是用兩個最小樹的前者作為左子樹后者作為右子樹。圖基礎知識和算法圖的有關概念圖，頂點，弧，弧頭，弧尾；有向圖（頂點集+弧集），0≤e≤n(n-1)，無向圖（頂點集+邊集），0≤e≤n(n-1)/2；稀疏圖（e<nlogn），稠密圖；完全圖e=n(n-1)/2，有向完全圖e=n(n-1)；網，有向網，無向網。子圖，鄰接點，頂點的度，入度，出度；路徑，路徑長度（經過邊或弧的數(shù)目），簡單路徑，回路（環(huán)），簡單回路（簡單環(huán)）；連通圖，連通分量，強連通分量。例：有6個頂點組成的無向圖構成連通圖，最少需要(_a_)條邊；當邊的數(shù)目大于(_b_)時，該圖必定連通。分析：a.5。最少有n-1條邊就可以構成連通圖。b.10?？紤]將n個頂點分成兩組，一組有n-1個頂點，另一組只有1個頂點。首先在第一組中添加邊，直到n-1個頂點構成全連通子圖，共(n-1)(n-2)/2條邊，此后若再在圖中任意添加一條邊將必定連通兩組頂點，從而構成連通圖。思考：對有向圖有何結論。圖的存儲結構圖的存儲結構常見圖的存儲結構有：鄰接矩陣，鄰接表，逆鄰接表，十字鏈表，鄰接多重表。鄰接多重表只適用于存儲無向圖，其他存儲結構可以存儲無向圖和有向圖。AABCDE例：畫出圖的鄰接矩陣、鄰接表、逆鄰接表和十字鏈表。鄰接矩陣簡言之，“數(shù)組(頂點)+二維數(shù)組(弧)+個數(shù)”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。constintMAX_VERTEX=最大頂點個數(shù);typedefstructGraph{//圖VertexType vexs[MAX_VERTEX]; //頂點向量ArcType arcs[MAX_VERTEX][MAX_VERTEX]; //鄰接矩陣int vexnum,arcnum; //頂點和弧的個數(shù)}Graph;圖：有邊(弧)為1；否則為0。網：有邊(弧)為權值；否則為∞。存儲空間個數(shù)為n2，與邊的數(shù)目無關。無向圖的鄰接矩陣是對稱的。 00110000110000101000010010ABCDE鄰接表簡言之，“數(shù)組(弧尾頂點)+鏈表(鄰接點)+個數(shù)”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。typedefstructArcNode{//弧結點int adjvex; //鄰接點structArcNode*nextarc; //下一個鄰接點}ArcNode;typedefstructVexNode{//頂點結點VertexType data; //頂點信息ArcNode*firstarc; //第一個鄰接點}VexNode;constintMAX_VERTEX=最大頂點個數(shù);typedefstructGraph{//圖VexNode vexs[MAX_VERTEX]; //頂點向量int vexnum,arcnum; //頂點和弧的個數(shù)}Graph;邊(弧)多則需要存儲空間多。 AABCDE12/\0123423/\3/\0/\03/\逆鄰接表簡言之，“數(shù)組(弧頭頂點)+鏈表(逆鄰結點)+個數(shù)”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。類型定義類似鄰接表。 AABCDE/\34/\012340/\0121/\4/\十字鏈表簡言之，“數(shù)組(頂點)+弧結點(含頭和尾)+個數(shù)”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。邊可以看作兩條弧。不準確的說法，只為便于理解和記憶，不要在正式場合引用。typedefstructArcNode{//弧結點int vtail,vhead; //弧尾和弧頭頂點編號structArcNode*nexttail,*nexthead; //指向同弧尾和同弧頭的弧結點}ArcNode;typedefstructVexNode{//頂點結點VertexType data; //頂點信息ArcNode *firstin,*firstout; //指向第一條入弧和第一條出弧}VexNode;constintMAX_VERTEX=最大頂點個數(shù);typedefstructGraph{//圖VexNode vexs[MAX_VERTEX]; //頂點向量int vexnum,arcnum; //頂點和弧的個數(shù)}Graph;弧結點中包含兩個指針分別指向同一弧頭的下一個弧和同一個弧尾的下一個弧。頂點結點則指向第一個同弧頭和弧尾的弧。十字鏈表相當于鄰接表和逆鄰接表的結合。 AABCDE/\01234/\30/\40/\01/\02/\12/\13/\23/\/\43技巧：把弧結點按行排整齊，然后畫鏈表。同弧尾的弧組成鏈表，同弧頭的弧組成鏈表。鄰接多重表簡言之，“數(shù)組(頂點)+邊結點”不準確的說法，只為便于理解和記憶，不要在正式場合引用。。不準確的說法，只為便于理解和記憶，不要在正式場合引用。typedefstructEdgeNode{//邊結點int vexi,vexj; //邊的兩個頂點structEdgeNode*nexti,*nextj; //兩個頂點所依附的下一條邊}EdgeNode;typedefstructVexNode{//頂點結點VertexType data; //頂點信息EdgeNode *firstedge; //指向第一條邊}VexNode;constintMAX_VERTEX=最大頂點個數(shù);typedefstructGraph{//圖VexNode vexs[MAX_VERTEX]; //頂點向量int vexnum,edgenum; //頂點和邊的個數(shù)}Graph;只適合存儲無向圖，不能存儲有向圖。 AABCDABCD01230102/\0312/\23/\/\13技巧：把邊結點按列排整齊，然后畫鏈表。相同頂點組成鏈表，這里沒有起點和終點的區(qū)別。圖的遍歷深度優(yōu)先搜索遍歷方法從圖中某個頂點出發(fā)，訪問此頂點，然后依次從其未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖；若圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復上述過程，直到圖中所有頂點都被訪問為止。分析方法方法：畫一棵“深度優(yōu)先搜索樹”。例：下圖從A出發(fā)深度優(yōu)先搜索的結果是：ABEDC。分析：畫“深度優(yōu)先搜索樹”。從A出發(fā)，訪問A(畫圈作標記)，A的鄰接點有B和C(作為A的孩子)，B未訪問，訪問B(畫圈)，B的鄰接點有E(作B的孩子)，...，以此類推，畫出搜索樹。深度優(yōu)先搜索的過程就是沿著該搜索樹先根遍歷的過程。技巧：頂點的鄰接點是無所謂次序的，所以同一個圖的深度優(yōu)先遍歷序列可能不同，但在遍歷時(除非鄰接點的次序有明確規(guī)定)一般按照編號順序安排鄰接點的次序。 AABCDEABCEADBBD算法課本上的算法稍加改動：voidDFSTraverseXE"DFSTraverse"(GraphG){visited[0..G.vexnum-1]=false; //初始化訪問標志為未訪問(false)for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v); //從未被訪問的頂點開始DFS}voidDFSXE"DFS"(GraphG,intv){visit(v);visited[v]=true; //訪問頂點v并作標記for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w); //分別從每個未訪問的鄰接點開始DFS}其中的FirstAdjVex(G,v)表示圖G中頂點v的第一個鄰接點，NextAdjVex(G,v,w)表示圖G中頂點v的鄰接點w之后v的下一個鄰接點。深度優(yōu)先搜索算法有廣泛的應用，以上算法是這些應用的基礎。廣度優(yōu)先搜索遍歷方法從圖中某頂點出發(fā)，訪問此頂點之后依次訪問其各個未被訪問的鄰接點，然后從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”要先于“后被訪問的頂點的鄰接點”被訪問，直至所有已被訪問的頂點的鄰接點都被訪問。若圖中尚有頂點未被訪問，則另選圖中未被訪問的頂點作為起始點，重復以上過程，直到圖中所有頂點都被訪問為止。廣度優(yōu)先搜索從某頂點出發(fā)，要依次訪問路徑長度為1，2，…的頂點。分析方法方法：畫一棵“廣度優(yōu)先搜索樹”。例：下圖從A出發(fā)廣度優(yōu)先遍歷的結果是：ABCED。分析：畫“廣度優(yōu)先搜索樹”。與深度優(yōu)先搜索樹類似，A為根，其鄰接點為其孩子，訪問一個頂點，則擴展出其孩子。不過廣度優(yōu)先搜索的訪問次序是對該樹按層遍歷的結果。 AABCDEABCEADBDB算法利用隊列(類似按層遍歷二叉樹)。voidBFSTraverseXE"BFSTraverse"(GraphG){visited[0..G.vexnum-1]=false; //初始化訪問標志為未訪問(false)InitQueue(Q);for(v=0;v<G.vexnum;v++)