數(shù)據(jù)結構教案

緒論基本概念和術語數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項數(shù)據(jù)：凡能被計算機存儲、加工的對象，通稱為數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，普通含有完整、擬定的實際意義。數(shù)據(jù)項：是數(shù)據(jù)不可分割的最小單位。注意：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項是數(shù)據(jù)組織的三個層次。如：（80，90，100，110，120）、表格數(shù)據(jù)的邏輯構造邏輯構造：數(shù)據(jù)元素之間的“鄰接”關系四種邏輯構造線性構造：數(shù)據(jù)元素之間存在“一對一”的關系樹形構造：數(shù)據(jù)元素之間存在“一對多”的關系圖狀構造：數(shù)據(jù)元素之間存在“多對多”的關系集合：數(shù)據(jù)元素之間沒有鄰接關系數(shù)據(jù)的存儲構造存儲構造：數(shù)據(jù)元素在計算機內的寄存方式兩種存儲構造次序存儲：將數(shù)據(jù)元素依次寄存到一組持續(xù)的存儲單元中。鏈式存儲：將數(shù)據(jù)元素寄存到非持續(xù)的存儲單元中，并運用指針將各個存儲單元鏈接起來。數(shù)據(jù)的基本操作加工型操作：變化數(shù)據(jù)元素的個數(shù)或數(shù)據(jù)元素的內容引用型操作：數(shù)據(jù)元素的個數(shù)或數(shù)據(jù)元素的內容均未變化數(shù)據(jù)構造1．含義：涉及三方面的內容：邏輯構造：反映數(shù)據(jù)元素之間的鄰接”關系存儲構造：反映數(shù)據(jù)元素在計算機內的寄存方式數(shù)據(jù)的操作2.數(shù)據(jù)按構造分，可分為4類，每一類對應著一種邏輯構造數(shù)據(jù)邏輯構造線性表線性構造樹樹型構造圖圖狀構造查找表集合1.3算法描述算法：解決問題的辦法和環(huán)節(jié)。算法的描述辦法框圖非形式語言：如中文類C語言程序C語言程序1.4算法分析對同一問題，能夠設計多個不同的算法，但必有一種算法的時間效率最高。估算一種算法的運行時間=1\*GB3①擬定問題的輸入規(guī)模n。=2\*GB3②根據(jù)問題的特點，選擇一種操作作為“原則操作”。（普通以條件判斷或賦值語句為原則操作）=3\*GB3③擬定在給定輸入下共執(zhí)行多少次原則操作，從而算出運行時間T。算法的時間復雜度對算法的運行時間T(n)，無視全部的常數(shù)、低次項，無視最高項的系數(shù)，稱為算法的時間復雜度，以O表達。運行時間時間復雜度T(n)=c常數(shù)階O(1)T(n)=cn線性階O(n)T(n)=cn2平方階O(n2)指數(shù)階O()對數(shù)階O()指針和構造一、什么是指針1．存儲單元的地址每一種存儲單元由一種或多個字節(jié)構成，存儲單元中第一種字節(jié)的編號稱為存儲單元的地址。2．什么叫指針？指針總是指向某個變量。指針的值是所指向變量的地址，指針的類型是所指向變量的類型。二、指針變量1．指針變量的定義類型*指針變量名;例：int*p;解釋：定義一種指針p，它只能指向int型變量。2．兩個運算符&：取地址運算符，例&i*：指針運算符，例*p例：int*p,i=3;p=&i;printf("%d,%d\n",i,*p);闡明：①&和*互為逆運算，即：&*p=p，*&i=i②定義指針變量時，指針變量名前面的“*”不是指針運算符。=3\*GB3③指針能夠與整數(shù)進行加、減運算。指針±n=指針的原值±sizeof(指針的類型)×n=4\*GB3④同類型的兩個指針能夠互相賦值。三、指針與數(shù)組1．數(shù)組名代表該數(shù)組的首地址，例a==&a[0]2．設inta[6]，則a[i]，*(a+i)是等價的&a[i]，a+i是等價的3．表達數(shù)組元素的辦法下標法：例a[i]指針法：例*(a+i)4．設指針p指向數(shù)組a的某一種元素，則p++：使p指向數(shù)組的下一種元素；四、構造1．定義構造類型struct構造名{組員定義列表}例：structperson{intno;charname[6];};2．定義構造變量structpersonx;引用構造變量的組員構造變量名．組員名構造變量的初始化構造指針例：已知structpersonx,*p;p=&x;則表達x的no組員有三種形式：x.no，p->no，(*p).no線性表2．1線性表的定義1．線性表的表達形式：

L=（a1，a2，a3，…，an）2．線性表的基本操作每種操作都采用一種函數(shù)來完畢，這些函數(shù)是自定義函數(shù)，使用之前必須先定義。2．2線性表的次序存儲構造一、次序表的類型定義次序表實際是一種構造變量，涉及兩個域：datas：寄存線性表的元素，last：寄存線性表的長度。typedefstruct{類型datas[maxsize];intlast;}sequenlist;sequenlistL;二、為線性表L=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種次序表，規(guī)定L的第1個元素存入數(shù)組的1號元素中。typedefstruct{chardatas[20];intlast;}sequenlist;voidmain(){sequenlistL;charch;inti=1;ch=getchar();while(ch!='\n'){L.datas[i]=ch;i++; ch=getchar();}L.last=i-1;for(i=1;i<=L.last;i++) printf("%4c",L.datas[i]);printf("\n");}三、基本操作在次序表上的實現(xiàn)1．insert(a,x,i)：將元素x插入到次序表a的第i號元素之前2．delete(a,i)：刪除次序表a的第i號元素第3章鏈式存儲構造3．1線性表的鏈式存儲構造一、次序表的優(yōu)缺點優(yōu)點：空間運用率高，能夠隨機讀取表中任一元素。缺點：插入、刪除操作要移動大量的數(shù)據(jù)，時間性能差。二、單鏈表1．單鏈表的構成每個單鏈表由多個結點構成，每個結點包含兩個域：數(shù)據(jù)域data：寄存線性表的元素指針域next：寄存下一種結點的地址2．單鏈表的類型定義typedefstructnode{類型data;structnode*next;}linklist;linklist*head;闡明：不帶頭結點的單鏈表為空的條件：head==null帶頭結點的單鏈表為空的條件：head->next==null3．單鏈表的建立（尾插入法）例：為L=（'a'，'b'，'c'，'d'，……）創(chuàng)立單鏈表。#include"malloc.h"#include"stdio.h"typedefstructnode{chardata;structnode*next;}linklist;voidmain(){charch;//定義三根指針，head指向頭結點，t指向新產(chǎn)生的結點，last指向最后的結點linklist*head,*t,*last;t=malloc(sizeof(linklist));t->next=NULL;head=t;last=t;ch=getchar();while(ch!='\n'){t=malloc(sizeof(linklist));t->data=ch; t->next=NULL; last->next=t; last=t; ch=getchar();}}4．單鏈表的插入需設立兩支指針：p、t。p：指向待插入結點的前一種結點t：指向新產(chǎn)生的結點5．單鏈表的刪除需設立兩支指針：p、t。p：指向待刪除結點的前一種結點t：指向待刪除結點三、其它鏈表單鏈表單向循環(huán)鏈表（循環(huán)鏈表）雙向循環(huán)鏈表（雙向鏈表）循環(huán)鏈表最后一種結點的指針域不是NULL，而是指向頭結點。雙鏈表每個結點包含三個域：一種數(shù)據(jù)域和兩個指針域。雙鏈表的特點是找結點的前趨和后繼都很容易。第4章棧和隊列4．1棧一、棧的定義1．基本概念棧頂、棧底、進棧、出棧、空棧2．棧的表達形式S=（a1，a2，a3，…，an）按a1，a2，a3，…，an次序進棧，但按an，…，a3，a2，a1次序出棧。a1稱為棧底元素，an稱為棧頂元素。棧又稱后進先出線性表（LIFO）表。二、棧的次序存儲構造1．次序棧的類型定義次序棧事實上是一種構造變量，涉及兩個域：data：寄存棧中元素，top：寄存棧頂元素所在單元的編號。typedefstruct{類型data[maxsize];inttop;}seqstack;seqstacks;?？諚l件：s.top=0；棧滿條件：s.top=maxsize-12．為S=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種次序棧，規(guī)定S的第1個元素存入數(shù)組的1號元素中。typedefstruct{chardata[20];inttop;}seqstack;voidmain(){seqstacks;charch;inti=1;ch=getchar();while(ch!='\n'){s.data[i]=ch;i++; ch=getchar();}s.top=i-1;for(i=1;i<=S.top;i++) printf("%-4c",s.data[i]);printf("\n");}三、棧的鏈式存儲構造1．鏈棧的類型定義typedefstructnode{類型data;structnode*next;}linkstack;linkstack*top;注意：=1\*GB3①鏈?？偸且詶ｍ斨羔榯op開頭，top用于標記整個鏈棧。=2\*GB3②鏈棧只會出現(xiàn)?？諣顩r，?？諚l件為:top==NULL。2．鏈棧的建立（頭插入法）例：為S=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種鏈棧。#include"malloc.h"#include"stdio.h"typedefstructnode{chardata;structnode*next;}linkstack;voidmain(){linkstack*top,*t;charch;top=NULL;ch=getchar();while(ch!='\n'){t=malloc(sizeof(linkstack));t->data=ch; t->next=top; top=t;ch=getchar();}printf("出棧次序為:\n");while(top->next!=NULL){printf("%-4c",top->data);top=top->next;}printf("\n");}4．2隊列一、隊列的定義1．基本概念隊頭、隊尾、空隊2．隊列的表達形式：Q=（a1，a2，a3，…，an）按a1，a2，a3，…，an次序進隊，仍按a1，a2，a3，…，an次序出隊。隊列又稱先進先出線性表（FIFO表）二、隊列的次序存儲構造1．次序隊的類型定義次序隊事實上是一種構造變量，涉及三個域：data：寄存隊列的元素；front：寄存隊頭元素所在單元的前一種單元的編號；rear：寄存隊尾元素所在單元的編號。typedefstruct{類型data[maxsize];intfront,rear;}seqqueue;seqqueueq;2．次序隊的建立例：為Q=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種次序隊。typedefstruct{chardata[20];intfront,rear;}seqqueue;voidmain(){seqqueueq;charch;inti=0;ch=getchar();while(ch!='\n'){q.data[i]=ch;i++; ch=getchar();}q.front=-1;q.rear=i-1;//輸出隊列元素for(i=0;i<=q.rear;i++) printf("%-4c",q.data[i]);printf("\n");}次序隊的隊空、隊滿=1\*GB3①隊空條件：q.front=q.rear=2\*GB3②隊滿條件：q.rear=maxsize-1隊真滿：q.front＝-1;q.rear＝maxsize-1隊假滿：q.front≠-1;q.rear＝maxsize-14．次序隊的插入、刪除操作=1\*GB3①插入新元素：rear后移而front不變q.rear=q.rear+1;q.data[q.rear]=x;=2\*GB3②刪除元素：front后移而rear不變q.front=q.front+1;三、循環(huán)隊1．為充足運用存儲空間，克服“假滿”，能夠把數(shù)組看作首尾相接的圓環(huán)，形成“循環(huán)隊”。2．循環(huán)隊的性質=1\*GB3①存儲單元的編號從0開始，按順時針方向，編號逐步增大，最后一種存儲單元的編號為maxsize-1。=2\*GB3②在循環(huán)隊中，當q.rear=maxsize-1時，只要數(shù)組有兩個以上的存儲單元為空，就能夠把新元素插入到空單元中。=3\*GB3③當隊列中元素的個數(shù)為maxsize-1時，就認為隊滿。3．循環(huán)隊的插入、刪除操作=1\*GB3①插入新元素：rear順時針移動而front不變q.rear=(q.rear+1)%maxsize;q.data[q.rear]=x;=2\*GB3②刪除元素：front順時針移動而rear不變q.front=(q.front+1)%maxsize;4．循環(huán)隊的隊空、隊滿隊空條件：q.front=q.rear隊滿條件：(q.rear+1)%maxsize=q.front四、隊列的鏈式存儲構造1．鏈隊的類型定義=1\*GB3①鏈隊是一種含有隊頭指針front和隊尾指針rear的單鏈表；②front指向隊頭結點的前一種結點，rear指向隊尾結點；=3\*GB3③鏈隊由包含front和rear的構造變量lq標記。typedefstructnode_st{類型data;structnode_st*next;}node;typedefstruct{node*front;node*rear;}linkqueue; linkqueuelq;2．鏈隊的建立（尾插入法）例：為Q=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種鏈隊。#include"malloc.h"#include"stdio.h"typedefstructnode_st{chardata;structnode_st*next;}node;typedefstruct{node*front;node*rear;}linkqueue; voidmain(){charch;linkqueuelq;node*p;p=malloc(sizeof(node));p->next=NULL;lq.front=p;lq.rear=p;ch=getchar();while(ch!='\n'){p=malloc(sizeof(node));p->data=ch; p->next=NULL; lq.rear->next=p; lq.rear=p; ch=getchar();}//輸出隊列中的元素p=lq.front->next;while(p!=NULL){printf("%-4c",p->data);p=p->next;}printf("\n");}3．鏈隊的隊空條件lq.front=lq.rear各式鏈式存儲構造比較表有無頭結點用何指針標記創(chuàng)立方法鏈表有頭指針head尾插入法鏈棧無棧頂指針top頭插入法鏈隊有由包含front和rear的構造變量lq標記。尾插入法第6章樹和二叉樹6．1樹的定義和基本操作一、樹型構造和線性構造樹型構造：每個結點能夠有多個直接后繼線性構造：每個結點只有一種直接后繼二、樹的定義樹是n（n≥0）個結點的有限集合，任意一棵非空樹滿足：=1\*GB3①有且只有一種根結點；=2\*GB3②其它結點被分成若干個互不相交的集合，每個集合又是一棵樹。三、樹的特點=1\*GB3①除根結點外，每個結點有且只有一種直接前趨；=2\*GB3②除最底層的結點外，每個結點能夠有多個直接后繼；=3\*GB3③若某棵樹有多個結點，則每個結點能夠看作根結點，要么是整棵樹的根結點，要么是某棵子樹的根結點。四、基本術語=1\*GB3①結點的度、樹的度=2\*GB3②葉子結點、分支結點度為0的結點稱為葉子結點；度不不大于0的結點稱為分支結點。=3\*GB3③孩子結點、雙親結點、兄弟結點含有同一雙親的結點互為兄弟=4\*GB3④結點的子孫、結點的祖先=5\*GB3⑤結點的層數(shù)、樹的高度結點的層數(shù)：從樹根開始算起，根的層數(shù)為1；樹的高度：樹中全部結點層數(shù)的最大值。6．2二叉樹一、二叉樹的定義：參考P73二、二叉樹的性質（1）二叉樹的第i層上最多有個結點。（2）深度為k的二叉樹最多有個結點。（3）滿二叉樹：除最底層的結點外，其它結點的度均為2的二叉樹。（4）完全二叉樹：如果對一棵滿二叉樹的最底層從最右邊開始，持續(xù)刪去若干個結點，就得到完全二叉樹。（5）對一棵完全二叉樹的結點進行編號，則對編號為i的結點，其左孩子的編號為2i，右孩子的編號為2i+1，雙親結點的編號為三、二叉樹的存儲構造1．次序存儲構造：◆先將二叉樹的結點依次編號，再將結點存入一維數(shù)組中，數(shù)組元素的序號對應結點的編號。◆對二叉樹的結點進行編號，編號原則是：=1\*GB3①根結點的編號為1。=2\*GB3②對于編號為i的結點，其左孩子的編號為2i，右孩子的編號為2i+1。滿二叉樹、完全二叉樹普通采用次序存儲構造，普通二叉樹則采用鏈式存儲構造。2．鏈式存儲構造：=1\*GB3①二叉鏈表：每個結點涉及三個域：數(shù)據(jù)域data，左指針域lchild，右指針域rchild=2\*GB3②對二叉樹的訪問只能從根指針root開始，二叉樹為空的條件：root=NULL。四、二叉樹的遍歷1．什么叫二叉樹的遍歷？按照一定規(guī)律訪問二叉樹的全部結點，使得每個結點均被訪問一次且僅被訪問一次。2．二叉樹由三部分構成：根結點、左子樹、右子樹3．三種遍歷次序=1\*GB3①先根遍歷：根結點、左子樹、右子樹=2\*GB3②中根遍歷：左子樹、根結點、右子樹=3\*GB3③后根遍歷：左子樹、右子樹、根結點6．3樹和森林一、對樹中各結點編號從根結點開始，按層依次編號，且根結點的編號為0。二、樹的存儲構造雙親鏈表孩子鏈表孩子兄弟鏈表1．雙親鏈表（1）每個結點包含兩個域名：數(shù)據(jù)域：寄存該結點的數(shù)據(jù)元素指針域：寄存該結點之雙親的編號（2）將全部結點組織成一維數(shù)組，并以各結點的編號作為數(shù)組元素的序號。2．孩子鏈表（1）為每個結點建立一種“孩子鏈表”。（2）結點x的孩子鏈表是一種帶頭結點的單鏈表，用于存儲該結點的全部孩子的編號。（3）將全部頭結點組織成一維數(shù)組。3．孩子兄弟鏈表（1）每個結點含有三個域：數(shù)據(jù)域：寄存該結點的數(shù)據(jù)元素孩子域：用于指向該結點的第一種孩子兄弟域：用于指向該結點的第一種兄弟（2）二叉樹的二叉鏈表與樹的孩子兄弟鏈表在組織構造完全相似。二叉鏈表孩子兄弟鏈表數(shù)據(jù)域數(shù)據(jù)域左指針域孩子域右指針域兄弟域三、樹與二叉樹的轉換1．樹轉換為二叉樹=1\*GB3①將樹轉換為二叉樹，只要將樹中各結點的第一種孩子看作左孩子，第一種兄弟看作右孩子即可。=2\*GB3②任一棵樹對應的二叉樹的右子樹必空。2．森林轉換為二叉樹=1\*GB3①將每棵樹先轉換為二叉樹B1，B2，…，Bn=2\*GB3②以B1為基準，將B2作為B1根結點的右子樹，將B3作為B2根結點的右子樹，…3．二叉樹轉換為森林=1\*GB3①將二叉樹根結點的右子樹撤去，得到多棵二叉樹B1，B2，…，Bn=2\*GB3②將二叉樹分別轉換為樹T1，T2，…，Tn。四、樹的遍歷先根遍歷：根結點、各棵子樹后根遍歷：各棵子樹、根結點層次遍歷6．4哈夫曼樹和鑒定樹一、基本術語1．葉子結點的途徑長度：從根結點到某個葉子結點所通過的分支數(shù)。2．樹的途徑長度：樹中各葉子結點的途徑長度之和。3．葉子結點的權：各葉子結點出現(xiàn)的概率。4．帶權途徑長度（WPL）各個葉子結點的權wi與對應的途徑長度li乘積之和，稱為樹的帶權途徑長度。二、哈夫曼樹1．什么叫哈夫曼樹？帶權途徑長度WPL最小的二叉樹，稱為哈夫曼樹。特點：=1\*GB3①普通地說，權值越大的葉子結點離根越近。=2\*GB3②哈夫曼樹的時間性能最佳，是最優(yōu)的二叉樹。=3\*GB3③哈夫曼樹中各結點的度只能是0或2。=4\*GB3④含有n個結點的哈夫曼樹共有2n-1個結點。2．如何構造一棵哈夫曼樹？（參考P88）3．哈夫曼編碼對一棵哈夫曼樹商定：指向左孩子的分支表達為0，指向右孩子的分支表達為1。取從根到葉子結點一路上的“0”或“1”構成的序列，稱為葉子結點的三、分類和鑒定樹1．用于描述分類問題的二叉樹稱為鑒定樹。鑒定樹的每個分支結點對應一種判斷，每個葉子結點對應一種分類成果。2．一種分類問題對應著若干棵鑒定樹，其中必有一棵鑒定樹的WPL最小，WPL又稱平均比較次數(shù)。3．一棵鑒定樹對應著一種算法，哈夫曼樹對應的算法的時間性能最佳。4．如何對一種分類問題寫最優(yōu)的算法？①對分類成果畫哈夫曼樹；②根據(jù)哈夫曼樹寫算法；第7章圖7．1圖的定義和術語一、圖的定義圖G由頂點集V和邊集E構成，記為G=（V，E）。=1\*GB3①最簡樸的圖只有一種頂點；=2\*GB3②每條邊由其連接的兩個頂點表達：例：無向邊（v1，v2）；有向邊<v1，v2>，<v2，v1>二、術語1．鄰接點若頂點vi，vj存在一條邊，則vi，vj互為鄰接點。在有向邊<vi，vj>中，稱vi為起點，vj為終點。2．頂點的入邊，出邊若存在一條有向邊<vi，vj>，則稱它為vi的出邊，vj的入邊。3．頂點的入度，出度=1\*GB3①頂點的度：與頂點v有關聯(lián)的邊數(shù)，記為D（v）；=2\*GB3②頂點的入度，出度：在有向圖中，頂點v的入邊的數(shù)目，稱為入度，記為ID（v）；頂點v的出邊的數(shù)目，稱為出度，記為OD（v）；D（v）=ID（v）+OD（v）4．無向完全圖，有向完全圖無向完全圖：任意兩個頂點之間都存在一條邊的無向圖；有向完全圖：任意兩個頂點之間都存在方向相反的兩條邊的有向圖；子圖設有兩個圖G=（V，E）和G′=（V′，E′），若V′是V的子集，E′是E的子集，則G′是G的子圖。連通圖和連通分量連通：在無向圖中，若兩個頂點有途徑，則稱兩頂點是連通的；連通圖：任意兩個頂點都連通的無向圖；連通分量：無向圖中的極大連通子圖。強連通圖和強連通分量強連通：在有向圖中，若vi到vj，vj到vi都有途徑，則稱vi，vj是強連通的；強連通圖：任意兩個頂點都強連通的有向圖；強連通分量：有向圖中的極大連通子圖。8．帶權圖：又稱網(wǎng)帶權有向圖（有向網(wǎng)）帶權無向圖（無向網(wǎng)）7．2圖的存儲構造一、鄰接矩陣1．鄰接矩陣的構建=1\*GB3①將各個頂點排成一行和一列，形成矩陣。=2\*GB3②若行、列頂點之間存在一條邊，則對應元素記1，否則，對應元素記0。2．鄰接矩陣的特點無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣普通不對稱。3．用鄰接矩陣表達加權圖只要把1元素換成對應邊的權值，0元素換成∞即可。鄰接矩陣的用途便于查找每個頂點的度、入度、出度。無向圖：每個頂點的度等于該頂點對應的行或列中1元素的個數(shù)。有向圖：每個頂點的出度等于該頂點對應行中1元素的個數(shù)，入度等于對應列中1元素的個數(shù)。二、鄰接鏈表樹的孩子鏈表、圖的鄰接鏈表組織構造相似。1．鄰接鏈表的構建=1\*GB3①為每個頂點建立一種鄰接鏈表，一種圖有幾個頂點，就有幾個鄰接鏈表。=2\*GB3②頂點x的鄰接鏈表是一種帶頭結點的單鏈表，用于存儲與x相鄰接的頂點序號。=3\*GB3③將全部頭結點組織成一維數(shù)組。2．鄰接鏈表的用途便于求頂點的度、出度。無向圖：每個頂點的度等于它的鄰接鏈表中表結點的個數(shù)。有向圖：每個頂點的出度等于它的鄰接鏈表中表結點的個數(shù)。3．如何求頂點的入度？構造一種逆鄰接鏈表，即頂點x的逆鄰接鏈表存儲的是與x的入邊有關聯(lián)的頂點序號。注：一種圖的鄰接矩陣是唯一的，但鄰接表普通不唯一。7．3圖的遍歷1．樹的遍歷先根遍歷：根結點、各棵子樹后根遍歷：各棵子樹、根結點層次遍歷2．圖的遍歷：適應于無向圖，也適應于有向圖。深度優(yōu)先搜索遍歷：類似樹的先根遍歷。廣度優(yōu)先搜索遍歷：類似樹的層次遍歷3．深度優(yōu)先搜索遍歷：首先訪問出發(fā)點Vi，然后任選一種Vi的未訪問過的鄰接點Vj，以Vj為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索。深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷得到的頂點序列不唯一。7．4圖的應用一、最小生成樹1．什么叫生成樹？從n個頂點的連通圖G中，取它的全部頂點和n-1條邊構成子圖G′，如果這些邊剛好將G′的全部頂點連通但又不形成回路，則稱子圖G′是G的一棵生成樹。注意：=1\*GB3①一種連通圖能夠有多棵生成樹。=2\*GB3②生成樹是邊數(shù)極少的連通子圖。=3\*GB3③連通分量：指極大連通子圖。=4\*GB3④根據(jù)圖的寬度優(yōu)先遍歷或深度優(yōu)先遍歷可構造生成樹。2．最小生成樹①生成樹的權：各條邊權值之和權值最小的生成樹，稱為最小生成樹。=2\*GB3②帶權無向圖才可構造最小生成樹。求造價最低的通訊網(wǎng)問題，實際是求最小生成樹問題。3．構造最小生成樹的算法：Prim（普里姆）算法二、拓撲排序1．拓撲序列在有向圖中，若不存在回路，則全部頂點可排成一種線性序列，方便列出各頂點的前后關系，稱此序列為拓撲序列。2．拓撲排序：實現(xiàn)有向圖的一種拓撲序列的過程。任何一種有向無環(huán)圖，其全部頂點能夠排成一種拓撲序列，且其拓撲序列不唯一。若圖中入度為0的頂點和出度為0的頂點都是唯一的，則其拓撲序列是唯一的。3．構成有向圖拓撲序列的過程=1\*GB3①從圖中選擇一種入度為0的頂點，輸出該頂點。=2\*GB3②從圖中刪除該頂點及其有關聯(lián)的全部邊。=3\*GB3③重復執(zhí)行1，2，直到找不到入度為0的頂點。三、最短途徑1．最短途徑問題=1\*GB3①帶權有向圖才存在最短途徑問題。=2\*GB3②圖的途徑長度：一條途徑上各條邊的權值之和。2．求一種源點到其它各個頂點的最短途徑：Dijkstra迪杰斯特拉）算法從源點到其它各個頂點的最短途徑中，先求最短的一條，再求次短的一條，以此次序，最后求最長的一條。3．Dijkstra算法描述=1\*GB3①假設S為頂點集合，初值為源點v0。=2\*GB3②首先從v0出發(fā)的全部邊中找出權值最小的邊的終點加入到S中。=3\*GB3③下一條最短途徑是終點不在S中，中間只通過S中的頂點且途徑長度最短，找到后將終點加入到S中。=4\*GB3④重復執(zhí)行（3），直到全部頂點都加入到S中。例：根據(jù)P115圖7.17，求頂點V1到其它各頂點的最短途徑。終點V2V3V4V5集合S第1次10∞30100{V1，V2}第2次106030100{V1，V2，V4}第3次10503090{V1，V2，V4，V3}第4次10503060{V1，V2，V4，V3，V5}V1到各頂點的最短途徑是：V1→V2：（V1，V2）V1→V4：（V1，V4）V1→V3：（V1，V4，V3）V1→V5：（V1，V4，V3，V5）第8章查找8．1基本概念一、多個數(shù)據(jù)的邏輯構造數(shù)據(jù)邏輯構造特點線性表線性構造數(shù)據(jù)元素之間存在著一對一的邏輯關系。樹樹型構造數(shù)據(jù)元素之間存在著一對多的邏輯關系。圖圖狀構造數(shù)據(jù)元素之間存在著多對多的邏輯關系。查找表集合數(shù)據(jù)元素之間不存在任何關系。二、查找表1．定義：查找表是一種以集合為邏輯構造，以查找為核心運算的數(shù)據(jù)構造。例：一種平面表格，當各條統(tǒng)計能夠任意排列時，就成為查找表。2．核心字：由一種或多個數(shù)據(jù)項構成，可標記若干條統(tǒng)計；主鍵：由一種或多個數(shù)據(jù)項構成，能唯一標記一條統(tǒng)計。3．查找：在查找表中尋找核心字值等于給定值的統(tǒng)計，若找到，則返回統(tǒng)計號；否則，則查找失敗。4．靜態(tài)查找表和動態(tài)查找表靜態(tài)查找表：只做建表、查找操作；動態(tài)查找表：做建表、查找、插入、刪除操作。8．2靜態(tài)查找表◆靜態(tài)查找表的存儲構造：次序表、有序表、索引次序表次序表上的查找次序表的類型定義typedefstruct{intkey;類型data;...}