數(shù)據(jù)結(jié)構(gòu)教案

1、第1章 緒論1.2 基本概念和術(shù)語(yǔ)一、 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)1 數(shù)據(jù)：凡能被計(jì)算機(jī)存儲(chǔ)、加工的對(duì)象，通稱為數(shù)據(jù)。2 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，通常具有完整、確定的實(shí)際意義。3 數(shù)據(jù)項(xiàng)：是數(shù)據(jù)不可分割的最小單位。注意：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)是數(shù)據(jù)組織的三個(gè)層次。如：（80，90，100，110，120）、表格二、 數(shù)據(jù)的邏輯結(jié)構(gòu)1 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的“鄰接”關(guān)系2 四種邏輯結(jié)構(gòu)線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對(duì)一”的關(guān)系樹(shù)形結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對(duì)多”的關(guān)系圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在“多對(duì)多”的關(guān)系集合：數(shù)據(jù)元素之間沒(méi)有鄰接關(guān)系三、 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1 存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的存

2、放方式2 兩種存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)：將數(shù)據(jù)元素依次存放到一組連續(xù)的存儲(chǔ)單元中。鏈?zhǔn)酱鎯?chǔ)：將數(shù)據(jù)元素存放到非連續(xù)的存儲(chǔ)單元中，并利用指針將各個(gè)存儲(chǔ)單元鏈接起來(lái)。四、 數(shù)據(jù)的基本操作 加工型操作：改變數(shù)據(jù)元素的個(gè)數(shù)或數(shù)據(jù)元素的內(nèi)容 引用型操作：數(shù)據(jù)元素的個(gè)數(shù)或數(shù)據(jù)元素的內(nèi)容均未改變五、 數(shù)據(jù)結(jié)構(gòu)1含義：包括三方面的內(nèi)容：邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的鄰接”關(guān)系存儲(chǔ)結(jié)構(gòu)：反映數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的存放方式數(shù)據(jù)的操作2. 數(shù)據(jù)按結(jié)構(gòu)分，可分為4類，每一類對(duì)應(yīng)著一種邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)線性表線性結(jié)構(gòu)樹(shù)樹(shù)型結(jié)構(gòu)圖圖狀結(jié)構(gòu)查找表集合1.3 算法描述1 算法：解決問(wèn)題的方法和步驟。2 算法的描述方法 框圖 非形式語(yǔ)言

3、：如中文 類C語(yǔ)言程序 C語(yǔ)言程序1.4 算法分析1 對(duì)同一問(wèn)題，可以設(shè)計(jì)多種不同的算法，但必有一種算法的時(shí)間效率最高。2 估算一個(gè)算法的運(yùn)行時(shí)間 確定問(wèn)題的輸入規(guī)模n。 根據(jù)問(wèn)題的特點(diǎn)，選擇一種操作作為“標(biāo)準(zhǔn)操作”。（通常以條件判斷或賦值語(yǔ)句為標(biāo)準(zhǔn)操作） 確定在給定輸入下共執(zhí)行多少次標(biāo)準(zhǔn)操作，從而算出運(yùn)行時(shí)間T。3 算法的時(shí)間復(fù)雜度對(duì)算法的運(yùn)行時(shí)間T(n)，忽略所有的常數(shù)、低次項(xiàng)，忽略最高項(xiàng)的系數(shù)，稱為算法的時(shí)間復(fù)雜度，以O(shè)表示。運(yùn)行時(shí)間時(shí)間復(fù)雜度T(n)=c常數(shù)階O(1)T(n)=cn線性階O(n)T(n)=cn2平方階O(n2)指數(shù)階O()對(duì)數(shù)階O()1.5 指針和結(jié)構(gòu)一、什么是指針1存

4、儲(chǔ)單元的地址每一個(gè)存儲(chǔ)單元由一個(gè)或多個(gè)字節(jié)組成，存儲(chǔ)單元中第一個(gè)字節(jié)的編號(hào)稱為存儲(chǔ)單元的地址。2什么叫指針？指針總是指向某個(gè)變量。指針的值是所指向變量的地址，指針的類型是所指向變量的類型。二、指針變量1指針變量的定義類型 *指針變量名;例：int *p;解釋：定義一個(gè)指針p，它只能指向int型變量。2兩個(gè)運(yùn)算符&：取地址運(yùn)算符，例&i*：指針運(yùn)算符，例*p例：int *p,i=3; p=&i; printf(%d, %d n,i,*p);說(shuō)明： &和*互為逆運(yùn)算，即：&*p=p，*&i=i 定義指針變量時(shí)，指針變量名前面的“*”不是指針運(yùn)算符。 指針可以與整數(shù)進(jìn)行加、減運(yùn)算。指針n=指針的原值

5、sizeof(指針的類型)n 同類型的兩個(gè)指針可以相互賦值。三、指針與數(shù)組1數(shù)組名代表該數(shù)組的首地址，例a= =&a02設(shè)int a6，則ai ，*(a+i)是等價(jià)的&ai ，a+i是等價(jià)的3表示數(shù)組元素的方法 下標(biāo)法：例ai 指針?lè)ǎ豪?(a+i)4設(shè)指針p指向數(shù)組a的某一個(gè)元素，則p+：使p指向數(shù)組的下一個(gè)元素；四、結(jié)構(gòu)1定義結(jié)構(gòu)類型 struct 結(jié)構(gòu)名 成員定義列表例：struct person int no; char name6;2定義結(jié)構(gòu)變量struct person x;1 引用結(jié)構(gòu)變量的成員結(jié)構(gòu)變量名成員名2 結(jié)構(gòu)變量的初始化3 結(jié)構(gòu)指針例：已知struct person x

6、,*p; p=&x;則表示x 的no成員有三種形式：x.no，p-no，(*p).no 第2章 線性表21 線性表的定義1線性表的表示形式： L=（a1，a2，a3，an）2線性表的基本操作 每種操作都采用一個(gè)函數(shù)來(lái)完成，這些函數(shù)是自定義函數(shù)，使用之前必須先定義。22 線性表的順序存儲(chǔ)結(jié)構(gòu)一、順序表的類型定義順序表實(shí)際是一個(gè)結(jié)構(gòu)變量，包括兩個(gè)域：datas：存放線性表的元素，last：存放線性表的長(zhǎng)度。typedef struct 類型 datasmaxsize; int last; sequenlist;sequenlist L;二、為線性表L=（a，b，c，d，）創(chuàng)建一個(gè)順序表，要求L的第

7、1個(gè)元素存入數(shù)組的1號(hào)元素中。typedef struct char datas20; int last; sequenlist;void main() sequenlist L; char ch; int i=1; ch=getchar(); while(ch!=n) L.datasi=ch; i+; ch=getchar(); L.last=i-1;for(i=1;inext=null3單鏈表的建立（尾插入法）例：為L(zhǎng)=（a，b，c，d，）創(chuàng)建單鏈表。#include malloc.h#include stdio.htypedef struct node char data; struct

8、 node *next; linklist;void main() char ch; /定義三根指針，head指向頭結(jié)點(diǎn)，t指向新產(chǎn)生的結(jié)點(diǎn)，last指向最后的結(jié)點(diǎn) 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單鏈表的插入需設(shè)置兩支指針：p、t。p：

9、指向待插入結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)t：指向新產(chǎn)生的結(jié)點(diǎn)5單鏈表的刪除需設(shè)置兩支指針：p、t。p：指向待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)t：指向待刪除結(jié)點(diǎn)三、其它鏈表 單鏈表單向循環(huán)鏈表（循環(huán)鏈表）雙向循環(huán)鏈表（雙向鏈表）1 循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域不是NULL，而是指向頭結(jié)點(diǎn)。2 雙鏈表每個(gè)結(jié)點(diǎn)包含三個(gè)域：一個(gè)數(shù)據(jù)域和兩個(gè)指針域。雙鏈表的特點(diǎn)是找結(jié)點(diǎn)的前趨和后繼都很容易。第4章 棧和隊(duì)列41 棧一、棧的定義1基本概念棧頂、棧底、進(jìn)棧、出棧、空棧2棧的表示形式S=（a1，a2，a3，an）按a1，a2，a3，an 順序進(jìn)棧，但按an，a3，a2，a1順序出棧。a1稱為棧底元素，an稱為棧頂元素。棧又稱后進(jìn)先出線

10、性表（LIFO）表。二、棧的順序存儲(chǔ)結(jié)構(gòu)1順序棧的類型定義順序棧實(shí)際上是一個(gè)結(jié)構(gòu)變量，包括兩個(gè)域：data：存放棧中元素，top：存放棧頂元素所在單元的編號(hào)。typedef struct 類型 datamaxsize; int top; seqstack;seqstack s;?？諚l件：s.top= 0；棧滿條件：s.top=maxsize-12為S=（a，b，c，d，）創(chuàng)建一個(gè)順序棧，要求S的第1個(gè)元素存入數(shù)組的1號(hào)元素中。typedef struct char data20; int top; seqstack;void main() seqstack s; char ch; int i=

11、1; ch=getchar(); while(ch!=n) s.datai=ch; i+; ch=getchar(); s.top=i-1;for(i=1;idata=ch;t-next=top;top=t; ch=getchar(); printf(出棧順序?yàn)?n);while(top-next!=NULL) printf(%-4c,top-data); top=top-next;printf(n);42 隊(duì)列一、隊(duì)列的定義1基本概念隊(duì)頭、隊(duì)尾、空隊(duì)2隊(duì)列的表示形式：Q=（a1，a2，a3，an）按a1，a2，a3，an 順序進(jìn)隊(duì)，仍按a1，a2，a3，an 順序出隊(duì)。隊(duì)列又稱先進(jìn)先出線性表

12、（FIFO表）二、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1順序隊(duì)的類型定義順序隊(duì)實(shí)際上是一個(gè)結(jié)構(gòu)變量，包括三個(gè)域：data：存放隊(duì)列的元素；front：存放隊(duì)頭元素所在單元的前一個(gè)單元的編號(hào)；rear：存放隊(duì)尾元素所在單元的編號(hào)。typedef struct 類型 datamaxsize; int front, rear; seqqueue;seqqueue q;2順序隊(duì)的建立例：為Q=（a，b，c，d，）創(chuàng)建一個(gè)順序隊(duì)。typedef struct char data20; int front, rear; seqqueue;void main() seqqueue q; char ch; int i=0; c

13、h=getchar(); while(ch!=n) q.datai=ch; i+; ch=getchar(); q.front= -1; q.rear=i-1; /輸出隊(duì)列元素for(i=0;inext=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(); /輸出隊(duì)列中的元素 p=lq.front-next; while(p!=NULL) printf(%-4c,p-da

14、ta); p=p-next; printf(n);3鏈隊(duì)的隊(duì)空條件lq.front=lq.rear4 各式鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比較表有無(wú)頭結(jié)點(diǎn)用何指針標(biāo)識(shí)創(chuàng)建辦法鏈表有頭指針head尾插入法鏈棧無(wú)棧頂指針top頭插入法鏈隊(duì)有由包含front和rear的結(jié)構(gòu)變量lq標(biāo)識(shí)。尾插入法第6章 樹(shù)和二叉樹(shù)61 樹(shù)的定義和基本操作一、樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼線性結(jié)構(gòu)：每個(gè)結(jié)點(diǎn)只有一個(gè)直接后繼二、樹(shù)的定義樹(shù)是n（n0）個(gè)結(jié)點(diǎn)的有限集合，任意一棵非空樹(shù)滿足： 有且只有一個(gè)根結(jié)點(diǎn)； 其余結(jié)點(diǎn)被分成若干個(gè)互不相交的集合，每個(gè)集合又是一棵樹(shù)。三、樹(shù)的特點(diǎn) 除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)直接前

15、趨； 除最底層的結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼； 若某棵樹(shù)有多個(gè)結(jié)點(diǎn)，則每個(gè)結(jié)點(diǎn)可以看作根結(jié)點(diǎn)，要么是整棵樹(shù)的根結(jié)點(diǎn)，要么是某棵子樹(shù)的根結(jié)點(diǎn)。四、基本術(shù)語(yǔ) 結(jié)點(diǎn)的度、樹(shù)的度 葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)；度大于0的結(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ù)、樹(shù)的高度結(jié)點(diǎn)的層數(shù)：從樹(shù)根開(kāi)始算起，根的層數(shù)為1；樹(shù)的高度：樹(shù)中所有結(jié)點(diǎn)層數(shù)的最大值。62 二叉樹(shù)一、二叉樹(shù)的定義：參考P73二、二叉樹(shù)的性質(zhì)（1）二叉樹(shù)的第i層上最多有個(gè)結(jié)點(diǎn)。（2）深度為k的二叉樹(shù)最多有個(gè)結(jié)點(diǎn)。（3）滿二叉樹(shù)：除最底層的結(jié)點(diǎn)外，其余結(jié)點(diǎn)

16、的度均為2的二叉樹(shù)。（4）完全二叉樹(shù)：如果對(duì)一棵滿二叉樹(shù)的最底層從最右邊開(kāi)始，連續(xù)刪去若干個(gè)結(jié)點(diǎn)，就得到完全二叉樹(shù)。（5）對(duì)一棵完全二叉樹(shù)的結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)編號(hào)為i的結(jié)點(diǎn)，其左孩子的編號(hào)為2i，右孩子的編號(hào)為2i+1，雙親結(jié)點(diǎn)的編號(hào)為三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1順序存儲(chǔ)結(jié)構(gòu)：先將二叉樹(shù)的結(jié)點(diǎn)依次編號(hào)，再將結(jié)點(diǎn)存入一維數(shù)組中，數(shù)組元素的序號(hào)對(duì)應(yīng)結(jié)點(diǎn)的編號(hào)。對(duì)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)原則是： 根結(jié)點(diǎn)的編號(hào)為1。 對(duì)于編號(hào)為i的結(jié)點(diǎn)，其左孩子的編號(hào)為2i，右孩子的編號(hào)為2i+1。 滿二叉樹(shù)、完全二叉樹(shù)一般采用順序存儲(chǔ)結(jié)構(gòu)，一般二叉樹(shù)則采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)： 二叉鏈表：每個(gè)結(jié)點(diǎn)包括三個(gè)域：數(shù)

17、據(jù)域data，左指針域lchild，右指針域rchild 對(duì)二叉樹(shù)的訪問(wèn)只能從根指針root開(kāi)始，二叉樹(shù)為空的條件：root=NULL。四、二叉樹(shù)的遍歷1什么叫二叉樹(shù)的遍歷？按照一定規(guī)律訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次且僅被訪問(wèn)一次。2二叉樹(shù)由三部分組成：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)3三種遍歷次序 先根遍歷：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù) 中根遍歷：左子樹(shù)、根結(jié)點(diǎn)、右子樹(shù) 后根遍歷：左子樹(shù)、右子樹(shù)、根結(jié)點(diǎn)63 樹(shù)和森林一、對(duì)樹(shù)中各結(jié)點(diǎn)編號(hào)從根結(jié)點(diǎn)開(kāi)始，按層依次編號(hào)，且根結(jié)點(diǎn)的編號(hào)為0。二、樹(shù)的存儲(chǔ)結(jié)構(gòu) 雙親鏈表 孩子鏈表 孩子兄弟鏈表1雙親鏈表（1）每個(gè)結(jié)點(diǎn)包含兩個(gè)域名：數(shù)據(jù)域：存放該結(jié)點(diǎn)的數(shù)

18、據(jù)元素指針域：存放該結(jié)點(diǎn)之雙親的編號(hào)（2）將所有結(jié)點(diǎn)組織成一維數(shù)組，并以各結(jié)點(diǎn)的編號(hào)作為數(shù)組元素的序號(hào)。2孩子鏈表（1）為每個(gè)結(jié)點(diǎn)建立一個(gè)“孩子鏈表”。（2）結(jié)點(diǎn)x的孩子鏈表是一個(gè)帶頭結(jié)點(diǎn)的單鏈表，用于存儲(chǔ)該結(jié)點(diǎn)的所有孩子的編號(hào)。（3）將所有頭結(jié)點(diǎn)組織成一維數(shù)組。3孩子兄弟鏈表（1）每個(gè)結(jié)點(diǎn)含有三個(gè)域：數(shù)據(jù)域：存放該結(jié)點(diǎn)的數(shù)據(jù)元素孩子域：用于指向該結(jié)點(diǎn)的第一個(gè)孩子兄弟域：用于指向該結(jié)點(diǎn)的第一個(gè)兄弟（2）二叉樹(shù)的二叉鏈表與樹(shù)的孩子兄弟鏈表在組織結(jié)構(gòu)完全相同。二叉鏈表孩子兄弟鏈表數(shù)據(jù)域數(shù)據(jù)域左指針域孩子域右指針域兄弟域三、樹(shù)與二叉樹(shù)的轉(zhuǎn)換1樹(shù)轉(zhuǎn)換為二叉樹(shù) 將樹(shù)轉(zhuǎn)換為二叉樹(shù)，只要將樹(shù)中各結(jié)點(diǎn)的第一個(gè)

19、孩子看作左孩子，第一個(gè)兄弟看作右孩子即可。 任一棵樹(shù)對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)必空。2森林轉(zhuǎn)換為二叉樹(shù) 將每棵樹(shù)先轉(zhuǎn)換為二叉樹(shù)B1，B2，Bn 以B1為基準(zhǔn)，將B2作為B1根結(jié)點(diǎn)的右子樹(shù)，將B3作為B2根結(jié)點(diǎn)的右子樹(shù)，3二叉樹(shù)轉(zhuǎn)換為森林 將二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)撤去，得到多棵二叉樹(shù)B1，B2，Bn 將二叉樹(shù)分別轉(zhuǎn)換為樹(shù)T1，T2，Tn。四、樹(shù)的遍歷 先根遍歷：根結(jié)點(diǎn)、各棵子樹(shù) 后根遍歷：各棵子樹(shù)、根結(jié)點(diǎn) 層次遍歷64哈夫曼樹(shù)和判定樹(shù)一、基本術(shù)語(yǔ)1葉子結(jié)點(diǎn)的路徑長(zhǎng)度：從根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的分支數(shù)。2樹(shù)的路徑長(zhǎng)度：樹(shù)中各葉子結(jié)點(diǎn)的路徑長(zhǎng)度之和。3葉子結(jié)點(diǎn)的權(quán)：各葉子結(jié)點(diǎn)出現(xiàn)的概率。4帶權(quán)路徑長(zhǎng)度（

20、WPL）各個(gè)葉子結(jié)點(diǎn)的權(quán)wi與相應(yīng)的路徑長(zhǎng)度li乘積之和，稱為樹(shù)的帶權(quán)路徑長(zhǎng)度。二、哈夫曼樹(shù)1什么叫哈夫曼樹(shù)？帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)，稱為哈夫曼樹(shù)。特點(diǎn)： 一般地說(shuō)，權(quán)值越大的葉子結(jié)點(diǎn)離根越近。 哈夫曼樹(shù)的時(shí)間性能最好，是最優(yōu)的二叉樹(shù)。 哈夫曼樹(shù)中各結(jié)點(diǎn)的度只能是0或2。 具有n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。2如何構(gòu)造一棵哈夫曼樹(shù)？（參考P88）3哈夫曼編碼 對(duì)一棵哈夫曼樹(shù)約定：指向左孩子的分支表示為0，指向右孩子的分支表示為1。取從根到葉子結(jié)點(diǎn)一路上的“0”或“1”組成的序列，稱為葉子結(jié)點(diǎn)的前綴編碼。三、分類和判定樹(shù)1用于描述分類問(wèn)題的二叉樹(shù)稱為判定樹(shù)。判定樹(shù)的每個(gè)分支結(jié)點(diǎn)對(duì)應(yīng)

21、一種判斷，每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)一種分類結(jié)果。2一個(gè)分類問(wèn)題對(duì)應(yīng)著若干棵判定樹(shù)，其中必有一棵判定樹(shù)的WPL最小，WPL又稱平均比較次數(shù)。3一棵判定樹(shù)對(duì)應(yīng)著一種算法，哈夫曼樹(shù)對(duì)應(yīng)的算法的時(shí)間性能最好。4如何對(duì)一個(gè)分類問(wèn)題寫(xiě)最優(yōu)的算法？ 對(duì)分類結(jié)果畫(huà)哈夫曼樹(shù)； 根據(jù)哈夫曼樹(shù)寫(xiě)算法；第7章 圖71 圖的定義和術(shù)語(yǔ)一、圖的定義圖G由頂點(diǎn)集V和邊集E組成，記為G=（V，E）。 最簡(jiǎn)單的圖只有一個(gè)頂點(diǎn)； 每條邊由其連接的兩個(gè)頂點(diǎn)表示：例：無(wú)向邊（v1 ，v2）；有向邊，二、術(shù)語(yǔ)1鄰接點(diǎn) 若頂點(diǎn)vi，vj存在一條邊，則vi，vj互為鄰接點(diǎn)。在有向邊中，稱vi為起點(diǎn)，vj為終點(diǎn)。2頂點(diǎn)的入邊，出邊 若存在一條有向邊

22、，則稱它為vi的出邊，vj的入邊。3頂點(diǎn)的入度，出度 頂點(diǎn)的度：與頂點(diǎn)v相關(guān)聯(lián)的邊數(shù)，記為D（v）； 頂點(diǎn)的入度，出度：在有向圖中，頂點(diǎn)v的入邊的數(shù)目，稱為入度，記為ID（v）； 頂點(diǎn)v的出邊的數(shù)目，稱為出度，記為OD（v）； D（v）= ID（v）+ OD（v）4無(wú)向完全圖，有向完全圖無(wú)向完全圖：任意兩個(gè)頂點(diǎn)之間都存在一條邊的無(wú)向圖；有向完全圖：任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條邊的有向圖；5 子圖設(shè)有兩個(gè)圖G=（V，E）和G=（V，E），若V是V的子集，E是E的子集，則G是G的子圖。6 連通圖和連通分量連通：在無(wú)向圖中，若兩個(gè)頂點(diǎn)有路徑，則稱兩頂點(diǎn)是連通的；連通圖：任意兩個(gè)頂點(diǎn)都連通的無(wú)

23、向圖；連通分量：無(wú)向圖中的極大連通子圖。7 強(qiáng)連通圖和強(qiáng)連通分量強(qiáng)連通：在有向圖中，若vi到vj，vj到vi都有路徑，則稱vi，vj是強(qiáng)連通的；強(qiáng)連通圖：任意兩個(gè)頂點(diǎn)都強(qiáng)連通的有向圖；強(qiáng)連通分量：有向圖中的極大連通子圖。8帶權(quán)圖：又稱網(wǎng) 帶權(quán)有向圖（有向網(wǎng)） 帶權(quán)無(wú)向圖（無(wú)向網(wǎng)）72 圖的存儲(chǔ)結(jié)構(gòu)一、鄰接矩陣1鄰接矩陣的構(gòu)建 將各個(gè)頂點(diǎn)排成一行和一列，形成矩陣。 若行、列頂點(diǎn)之間存在一條邊，則對(duì)應(yīng)元素記1，否則，對(duì)應(yīng)元素記0。2鄰接矩陣的特點(diǎn)無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣一般不對(duì)稱。3用鄰接矩陣表示加權(quán)圖只要把1元素?fù)Q成相應(yīng)邊的權(quán)值，0元素?fù)Q成即可。4 鄰接矩陣的用途便于查找每個(gè)頂

24、點(diǎn)的度、入度、出度。無(wú)向圖：每個(gè)頂點(diǎn)的度等于該頂點(diǎn)相應(yīng)的行或列中1元素的個(gè)數(shù)。有向圖：每個(gè)頂點(diǎn)的出度等于該頂點(diǎn)相應(yīng)行中1元素的個(gè)數(shù)，入度等于相應(yīng)列中1元素的個(gè)數(shù)。二、鄰接鏈表樹(shù)的孩子鏈表、圖的鄰接鏈表組織結(jié)構(gòu)相同。1鄰接鏈表的構(gòu)建 為每個(gè)頂點(diǎn)建立一個(gè)鄰接鏈表，一個(gè)圖有幾個(gè)頂點(diǎn)，就有幾個(gè)鄰接鏈表。 頂點(diǎn)x的鄰接鏈表是一個(gè)帶頭結(jié)點(diǎn)的單鏈表，用于存儲(chǔ)與x相鄰接的頂點(diǎn)序號(hào)。 將所有頭結(jié)點(diǎn)組織成一維數(shù)組。2鄰接鏈表的用途便于求頂點(diǎn)的度、出度。無(wú)向圖：每個(gè)頂點(diǎn)的度等于它的鄰接鏈表中表結(jié)點(diǎn)的個(gè)數(shù)。有向圖：每個(gè)頂點(diǎn)的出度等于它的鄰接鏈表中表結(jié)點(diǎn)的個(gè)數(shù)。3如何求頂點(diǎn)的入度？構(gòu)造一個(gè)逆鄰接鏈表，即頂點(diǎn)x的逆鄰接鏈

25、表存儲(chǔ)的是與x的入邊相關(guān)聯(lián)的頂點(diǎn)序號(hào)。注：一個(gè)圖的鄰接矩陣是唯一的，但鄰接表一般不唯一。73 圖的遍歷1樹(shù)的遍歷 先根遍歷：根結(jié)點(diǎn)、各棵子樹(shù) 后根遍歷：各棵子樹(shù)、根結(jié)點(diǎn) 層次遍歷2圖的遍歷：適應(yīng)于無(wú)向圖，也適應(yīng)于有向圖。 深度優(yōu)先搜索遍歷：類似樹(shù)的先根遍歷。 廣度優(yōu)先搜索遍歷：類似樹(shù)的層次遍歷3深度優(yōu)先搜索遍歷：首先訪問(wèn)出發(fā)點(diǎn)Vi，然后任選一個(gè)Vi的未訪問(wèn)過(guò)的鄰接點(diǎn)Vj，以Vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索。深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列不唯一。74 圖的應(yīng)用一、最小生成樹(shù)1什么叫生成樹(shù)？從n個(gè)頂點(diǎn)的連通圖G中，取它的全部頂點(diǎn)和n-1條邊構(gòu)成子圖G，如果這些邊剛好將G的全部

26、頂點(diǎn)連通但又不形成回路，則稱子圖G是G的一棵生成樹(shù)。注意： 一個(gè)連通圖可以有多棵生成樹(shù)。 生成樹(shù)是邊數(shù)極少的連通子圖。 連通分量：指極大連通子圖。 根據(jù)圖的寬度優(yōu)先遍歷或深度優(yōu)先遍歷可構(gòu)造生成樹(shù)。2最小生成樹(shù) 生成樹(shù)的權(quán)：各條邊權(quán)值之和權(quán)值最小的生成樹(shù)，稱為最小生成樹(shù)。 帶權(quán)無(wú)向圖才可構(gòu)造最小生成樹(shù)。求造價(jià)最低的通訊網(wǎng)問(wèn)題，實(shí)際是求最小生成樹(shù)問(wèn)題。3構(gòu)造最小生成樹(shù)的算法：Prim（普里姆）算法二、拓?fù)渑判?拓?fù)湫蛄性谟邢驁D中，若不存在回路，則所有頂點(diǎn)可排成一個(gè)線性序列，以便列出各頂點(diǎn)的前后關(guān)系，稱此序列為拓?fù)湫蛄小?拓?fù)渑判颍簩?shí)現(xiàn)有向圖的一個(gè)拓?fù)湫蛄械倪^(guò)程。任何一個(gè)有向無(wú)環(huán)圖，其全部頂點(diǎn)可以排

27、成一個(gè)拓?fù)湫蛄?，且其拓?fù)湫蛄胁晃ㄒ?。若圖中入度為0的頂點(diǎn)和出度為0的頂點(diǎn)都是唯一的，則其拓?fù)湫蛄惺俏ㄒ坏摹?構(gòu)成有向圖拓?fù)湫蛄械倪^(guò)程 從圖中選擇一個(gè)入度為0的頂點(diǎn)，輸出該頂點(diǎn)。 從圖中刪除該頂點(diǎn)及其相關(guān)聯(lián)的所有邊。 重復(fù)執(zhí)行1，2，直到找不到入度為0的頂點(diǎn)。三、最短路徑1最短路徑問(wèn)題 帶權(quán)有向圖才存在最短路徑問(wèn)題。 圖的路徑長(zhǎng)度：一條路徑上各條邊的權(quán)值之和。2求一個(gè)源點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑：Dijkstra 迪杰斯特拉）算法從源點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑中，先求最短的一條，再求次短的一條，以此順序，最后求最長(zhǎng)的一條。3Dijkstra算法描述 假設(shè)S為頂點(diǎn)集合，初值為源點(diǎn)v0。 首先從v0

28、出發(fā)的所有邊中找出權(quán)值最小的邊的終點(diǎn)加入到S中。 下一條最短路徑是終點(diǎn)不在S中，中間只經(jīng)過(guò)S中的頂點(diǎn)且路徑長(zhǎng)度最短，找到后將終點(diǎn)加入到S中。 反復(fù)執(zhí)行（3），直到所有頂點(diǎn)都加入到S中。例：根據(jù)P115圖7.17，求頂點(diǎn)V1到其余各頂點(diǎn)的最短路徑。終點(diǎn)V2V3V4V5集合S第1次1030100V1，V2第2次106030100V1，V2，V4第3次10503090V1，V2，V4，V3第4次10503060V1，V2，V4，V3，V5V1到各頂點(diǎn)的最短路徑是：V1V2：（V1，V2）V1V4：（V1，V4）V1V3：（V1，V4，V3）V1V5：（V1，V4，V3，V5）第8章 查找81 基本概

29、念一、各種數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)特點(diǎn)線性表線性結(jié)構(gòu)數(shù)據(jù)元素之間存在著一對(duì)一的邏輯關(guān)系。樹(shù)樹(shù)型結(jié)構(gòu)數(shù)據(jù)元素之間存在著一對(duì)多的邏輯關(guān)系。圖圖狀結(jié)構(gòu)數(shù)據(jù)元素之間存在著多對(duì)多的邏輯關(guān)系。查找表集合數(shù)據(jù)元素之間不存在任何關(guān)系。二、查找表1定義：查找表是一種以集合為邏輯結(jié)構(gòu)，以查找為核心運(yùn)算的數(shù)據(jù)結(jié)構(gòu)。例：一個(gè)平面表格，當(dāng)各條記錄可以任意排列時(shí)，就成為查找表。2關(guān)鍵字：由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，可標(biāo)識(shí)若干條記錄；主鍵：由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，能唯一標(biāo)識(shí)一條記錄。3查找：在查找表中尋找關(guān)鍵字值等于給定值的記錄，若找到，則返回記錄號(hào)；否則，則查找失敗。4靜態(tài)查找表和動(dòng)態(tài)查找表靜態(tài)查找表：只做建表、查找操作；

30、動(dòng)態(tài)查找表：做建表、查找、插入、刪除操作。82 靜態(tài)查找表 靜態(tài)查找表的存儲(chǔ)結(jié)構(gòu)：順序表、有序表、索引順序表一、 順序表上的查找1 順序表的類型定義typedef struct int key; 類型 data; . ELEMENT;typedef struct ELEMENT rmaxsize; int len; SSTABLE;2 在順序表上實(shí)現(xiàn)查找運(yùn)算，采用“順序查找法”對(duì)順序表從后往前依次查找關(guān)鍵字值等于給定值k的記錄，若找到，則返回記錄的序號(hào)。3 查找長(zhǎng)度：記錄的鍵值與給定值的比較次數(shù)，稱為查找長(zhǎng)度。它用來(lái)衡量查找算法的時(shí)間性能。 查找成功的平均查找長(zhǎng)度ASL= （n為記錄條數(shù)） 查找不成功的平均查找長(zhǎng)度為：n二、 有序表上的查找1 查找表中各元素之間無(wú)任何邏輯關(guān)系