數據結構輔導課程內容框架數據結構基礎數據結構應用數據結構棧隊列線性表線性結構非線性結構串查找內部排序外部排序文件動態存管理儲數組廣義表樹二叉樹圖2PPT課件基本概念1.2基本概念和術語數據、數據元素、數據項、數據對象結構 *集合：松散的關系 *線性結構：一對一的關系 *樹形結構：一對多的關系 *網狀結構：多對多的關系數據結構

Data_Structure=（D，S）3PPT課件數據結構的分類1.2基本概念和術語（續）邏輯結構： 數據元素之間的邏輯關系（本來的關系）存儲結構： 數據結構在計算機中的映象。包括數據元素的表示和關系的表示兩個方面。

分類： *順序存儲結構 *鏈式存儲結構

描述方式： 用高級語言中的“數據類型”來描述4PPT課件算法1.3算法和算法分析內涵:

是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。特性: *有窮性：有窮步+有窮時間/每一步 *確定性：指令的語義無二義性 *可行性：算法能用基本操作完成 *輸入：零個或多個輸入 *輸出：一個或多個輸出5PPT課件算法設計的要求1.3算法和算法分析（續）正確性（Correctness）可讀性（Readablity）健壯性（Robustness）高時間效率與低存儲量需求6PPT課件算法時間效率的度量1.3算法和算法分析（續）算法時間效率度量的基本做法

在算法中選取一種對于所研究問題來說是基本操作的原操作，以該基本操作重復執行的次數作為算法的時間度量。 一般而言，這個基本操作是最深層循環內的語句中的原操作。算法時間復雜度

T(n)=O(f(n))稱為算法的漸近時間復雜度，簡稱時間復雜度。7PPT課件算法存儲空間的度量1.3算法和算法分析（續）算法存儲空間度量的基本做法

用程序執行中需要的輔助空間的消耗作為存儲空間度量的依據，是問題規模n的函數。而程序執行中本身需要的工作單元不能算。算法空間復雜度

S(n)=O(f(n))稱為算法的空間復雜度。8PPT課件2.線性表3.棧、隊列和串第一部分線性數據結構9PPT課件線性數據結構的特點2.1線性表的邏輯結構在數據元素的非空有限集中存在唯一的一個被稱作“第一個”的數據元素；存在唯一的一個被稱作“最后一個”的數據元素；除第一個之外，集合中的每一個數據元素均只有一個前驅；除最后一個之外，集合中每一個數據元素均只有一個后繼。10PPT課件基本概念和術語2.1線性表的邏輯結構（續）線性表：n個數據元素的有限序列（線性表中的數據元素在不同環境下具體含義可以不同，但在同一線性表中的元素性質必須相同）。表長：線性表中元素的個數n(n>=0)?？毡恚簄=0時的線性表稱為空表。位序：非空表中數據元素ai

是此表的第i個元 素，則稱i為ai

在線性表中的位序。11PPT課件線性表的抽象數據類型定義2.1線性表的邏輯結構（續）ADTList{

數據對象：D={ai|ai屬于ElemSet,i=1,2,…,n,n>=0}

數據關系：R1={<ai-1,ai>|ai-1,ai屬于D,i=2,3,…,n}

基本操作：

InitList(&L)

DestroyList(&L)

ClearList(&L)

ListLength(L)

GetElem(L,i,&e)

初始條件：L存在； 1<=i<=ListLength(L)

操作結果：用e返回L中第i個數據元素的值

} ADTListLocateElem(L,e,compare())

初始條件：L存在；compare()是判定條件

操作結果：返回第1個與e滿足關系compare()的數據元素位序，若不存在，則返回0ListInsert(&L,i,e)

初始條件：L存在；1<=i<=ListLength(L)+1

操作結果：第i個位置之前插入元素e，長度加1ListDelete(&L,i,&e)

初始條件：L存在；非空；1<=i<=ListLength(L)

操作結果：刪除第i個元素，e返回值，長度減1查找刪除插入12PPT課件順序表---線性表的順序存儲2.2線性表的順序存儲結構內涵： 線性表的順序存儲指用一組地址連續的存儲單元依次存儲線性表的數據元素。這稱為順序表。特點： *存儲單元地址連續（需要一段連續空間） *邏輯上相鄰的數據元素其物理位置也相鄰 *隨機存取 *存儲密度為大（100%）13PPT課件順序表的隨機存取2.2線性表的順序存儲結構（續）對線性表L,設每個元素占k個存儲單元，則有：遞推關系：LOC(ai+1)=LOC(ai)+k任一元素ai+1的存儲位置：

LOC(ai)=LOC(a1)+(i-1)*k(其中1<=i<=ListLength(L))a1a2…aiai+1…an…LOC(a1)LOC(ai+1)LOC(ai)LOC(an)LOC(a1)+(maxlen-1)*k空閑14PPT課件順序表上插入運算的實現2.2線性表的順序存儲結構（續）（a1，…，ai,ai+1,…,an)表長為nStatusListInsert_Sq(SqList&L,inti,ElemTypee){

第一步：判斷參數是否合法合理，否則出錯；第二步：在物理空間中找到插入位置；第三步：插入前的準備工作;第四步：插入；}//ListInsert_SqListInsert(&L,i,e)（a1，…，ai-1,e，ai,…,an)表長為n+1a1a2…ai-1ai…an…a1a2…ai-1ai…an…e插入15PPT課件順序表上刪除運算的實現2.2線性表的順序存儲結構（續）（a1，…，ai,ai+1,…,an)表長為nStatusListDelete_Sq(SqList&L,inti,ElemType

&e){

第一步：判斷參數是否合法合理，否則出錯；第二步：在物理空間中找到刪除位置；第三步：刪除；第四步：刪除后的善后工作}//ListDelete_SqListDelete(&L,i,&e)（a1，…，ai-1,ai+1,…,an)表長為n-1刪除a1a2…ai-1ai+1…an…a1a2…ai-1ai…an…ai+116PPT課件順序表優缺點分析2.3線性表的鏈式存儲結構優點： *不需要額外空間來存儲元素之間的關系 *可以隨機存取任一元素可以通過使用動態數組數據類型來描述順序表而改進這兩個缺點缺點：*插入和刪除運算需要移動大量元素*需要一段連續空間*預先分配足夠大的空間*表的容量難以擴充17PPT課件鏈表---線性表的鏈式存儲2.3線性表的鏈式存儲結構（續）內涵： 線性表的鏈式存儲指用任意的存儲單元存放線性表中的元素，每個元素與其前驅和（或）后繼之間的關系用指針來存儲。這稱為鏈表。術語： *結點 *數據域 *指針域 *頭指針 *頭結點分類： *單鏈表 *循環鏈表 *雙向鏈表 *雙向循環鏈表 *靜態鏈表18PPT課件單鏈表2.3線性表的鏈式存儲結構（續） 單鏈表中，如果每個結點中只包含一個指域，稱這種鏈表為線性鏈表或單鏈表。 單鏈表可由頭指針唯一確定。a2an^a1…LL^19PPT課件單鏈表的數據類型描述用高級語言中的指針類型描述線性表的鏈式存儲//----------用結構指針描述------------typedef

struct

LNode{

ElemType data //數據域

struct

LNode *next //指針域}Lnode,*LinkList2.3線性表的鏈式存儲結構（續）20PPT課件單鏈表上插入運算的實現2.3線性表的鏈式存儲結構（續）（a1，…，ai,ai+1,…,an)表長為nListInsert(&L,i,e)（a1，…，ai-1,e，ai,…,an)表長為n+1插入ai-1ai…L…ai-1ai…L…e^sesS=(LinkList)malloc(sizeof(LNode))ps->next=p->next;p->next=s21PPT課件單鏈表上刪除運算的實現2.3線性表的鏈式存儲結構（續）刪除q（a1，…，ai,ai+1,…,an)表長為nListDelete(&L,i,&e)（a1，…，ai-1,ai+1,…,an)表長為n-1free(q)ai-1ai…L…ai+1pp->next=p->next->nextai-1ai…L…ai+1p22PPT課件2.線性表3.棧、隊列和串教學內容---第三章23PPT課件棧、隊列和串是特殊的線性表3.1棧、隊列和串的邏輯結構棧和隊列是操作受限的線性表棧和隊列的“操作受限”指操作位置受限串的特殊性在于線性表中數據元素只能是字符串一般以子串為操作單位棧、隊列和串具有一般線性表共性的特點特殊的線性表反而應用面更寬24PPT課件棧的基本概念和術語3.1棧、隊列和串的邏輯結構（續）棧（Stack）：限定僅在表尾進行插入或刪除操作的線性表。棧頂（top）

：插入或刪除的表尾端。棧底（bottom）

：表頭端?？諚＃嚎毡?。棧的操作特點：后進先出（LastInFirstOut---LIFO）25PPT課件棧的抽象數據類型定義3.1棧、隊列和串的邏輯結構（續）ADTStack{

數據對象：D={ai|ai屬于ElemSet,i=1,2,…,n,n>=0}

數據關系：R1={<ai-1,ai>|ai-1,ai屬于D,i=2,3,…,n}//a1

為棧底，an

棧頂基本操作：

InitStack(&S)

DestroyStack(&S)

StackEmpty(S)

ClearStack(&S)

StackLength(S)

GetTop(S,&e)

初始條件：S存在,非空；

操作結果：用e返回S的棧頂元 素 Push(&S,e)

初始條件：S存在操作結果：插入元素e為新的棧頂元素，長度加 1Pop(&S,&e)

初始條件：S存在；非空操作結果：刪除S的棧頂元素，e返回值，長度 減1}ADTStack出棧（刪除）入棧（插入）26PPT課件隊列的基本概念和術語3.1棧、隊列和串的邏輯結構（續）隊列（Queue）：限定僅在表的一端進行插入，而另一端進行刪除操作的線性表。隊尾（rear）

：允許插入的一端。隊頭（front）：允許刪除的一端?？贞牐嚎毡?。隊列操作特點：先進先出（FirstInFirstOut---FIFO）27PPT課件隊列的抽象數據類型定義3.1棧、隊列和串的邏輯結構（續）ADTQueue{

數據對象：D={ai|ai屬于ElemSet,i=1,2,…,n,n>=0}

數據關系：R1={<ai-1,ai>|ai-1,ai屬于D,i=2,3,…,n}//a1

為隊頭，an

隊尾基本操作：

InitQueue(&Q)

DestroyQueue(&Q)

ClearQueue(&Q)

QueueEmpty(Q)

QueueLength(Q)

GetHead(Q,&e)

初始條件：Q存在,非空；

操作結果：用e返回Q的棧頂元 素 EnQueue(&Q,e)

初始條件：Q存在操作結果：插入元素e為新的隊尾元素，長度加 1DelQueue(&S,&e)

初始條件：Q存在；非空操作結果：刪除Q的對頭元素，e返回值，長度 減1}ADTQueue出隊（刪除）入隊（插入）28PPT課件串的基本概念和術語3.1棧、隊列和串的邏輯結構（續）串（String）：由零個或多個字符組成的有限序列。S=‘a1a2…an’串名、串值串長空串、空格串子串：串中任意連續的字符組成的子序列主串：字符在串中的位置、子串在串中的位置串相等串的操作特點：一般以子串整體為單位29PPT課件串的抽象數據類型定義3.1棧、隊列和串的邏輯結構（續）ADTSring{

數據對象：D={ai|ai屬于CharacterSet,i=1,2,…,n,n>=0}

數據關系：R1={<ai-1,ai>|ai-1,ai屬于D,i=2,3,…,n}基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

StrEmpty(S)

StrLength(S)

SubString(&Sub,S,pos,len)

初始條件：S存在,1<=pos<=StrLength(S), 0<=len<=StrLength(S)-pos+1；

操作結果： Index(S,T,pos)StrInsert(&S,pos,T)

初始條件：S存在,1<=pos<=StrLength(S)+1

操作結果：在串S的第pos個字符之前插入串TStrDelete(&S,pos,len)

初始條件：S存在,1<=pos<=StrLength(S)-len+1

操作結果：從串S中刪除第pos個字符起長度為

len

的子串}ADTString插入查找刪除30PPT課件棧的順序存儲3.2棧、隊列和串的存儲結構a1…ai…a2base//----------動態分配------------#defineSTACK_INIT_SIZE100//空間初始分配量#defineSTACKINCREMENT10 //空間分配增量typedef

struct{

sElemType *base

sElemType *top

int

stacksize//當前分配的存儲容量}SqStacktop31PPT課件StatusPush(SqStack&S,SElemTypee)

if(S.top–S.base>=S.stacksize){ S.base=(SElemTupe*)realloc(S.base,(S.stacksize

+STACKINCERMENT)*sizeof(Selemtype)); if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base+S.stacksize;

S.stacksize=+STACKINCERMENT;}*S.top++=e;returnOK;}//Push入棧a1…ai…a2basetopa1eai……a2basetop順序棧上的入棧3.2棧、隊列和串的存儲結構（續）32PPT課件StatusPop(SqStack&S,SElemType&e)

if(S.top=S.base)returnerror;e=*--S.top;returnOK;}//Pop出棧a1…ai-1…a2basetopa1aiai-1……a2basetop順序棧上的出棧3.2棧、隊列和串的存儲結構（續）33PPT課件棧的鏈式存儲---鏈棧3.2棧、隊列和串的存儲結構（續）basetoptypedef

struct{

ElemType data

struct

Lnode *next }Lnode,*StackPtran-1a1^an…typedef

struct{

StackPtr top

StackPtr base}LinkStack34PPT課件鏈棧上的入棧與出棧3.2棧、隊列和串的存儲結構（續）鏈棧上的入棧與出棧與單鏈表上元素插入刪除操作類似插入刪除位置都在棧頂處，不花費查找時間?？盏呐袛?5PPT課件隊列的順序存儲---循環隊列（一）3.2棧、隊列和串的存儲結構（續）a1…ai…a2front一般順序存儲的隊列特點：隊空條件：front=rear隊滿條件：rear=MAXSIZE隊滿條件下的隊滿為假滿（假溢出）（真滿時：rear=MAXSIZE,front=0）rear36PPT課件//----------動態分配------------#defineMAXSIZE100//最大隊列長度typedef

struct{

QElemType *base

int front //指向隊頭元素當前位置

int rear//指向隊尾元素下一個位置}SqQueue隊列的順序存儲---循環隊列（二)3.2棧、隊列和串的存儲結構（續）37PPT課件循環隊列特點：隊空條件： *front=rear（方式一） *標志域+（front=rear）（方式二）隊滿條件： *(rear+1)%MAXSIZE=front（方式一） *標志域+（front=rear）（方式二）隊滿條件下的隊滿為真滿隊列的順序存儲---循環隊列（三)3.2棧、隊列和串的存儲結構（續）38PPT課件隊列的順序存儲---循環隊列（四)3.2棧、隊列和串的存儲結構（續）StatusEnQueue(SqQueue&Q,QElemTypee)

if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueueStatusInitQueue(SqQueue&Q){

Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));if(!Q.base)exit(overflow);Q.front=Q.rear=0;returnOK;}//InitQueueStatusDeQueue(SqQueue&Q,QElemType&e){

if(Q.rear==Q.front)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}//DeQueue39PPT課件隊列的鏈式存儲---鏈隊列（一）3.2棧、隊列和串的存儲結構（續）typedef

struct{

QElemType data

struct

QNode *next }QNode,*QueuePtra2an^a1…typedef

struct{

QueuePtr rear

QueuePtr front}LinkQueueq.rear.front40PPT課件StatusEnQueue(LinkQueue&Q,QElemTypee)

p=(QueuePtr)malloc(sizeof(Qnode));if(!p)exit(overflow);p->data=e; p->next=NULL;Q.rear->next=p; Q.rear=p;returnOK;}//EnQueueStatusInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(overflow);Q.front->next=NULL;returnOK;}//InitQueueStatusDeQueue(LinkQueue&Q,QElemType&e){

if(Q.rear==Q.front)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}//DeQueue隊列的鏈式存儲---鏈隊列（二）3.2棧、隊列和串的存儲結構（續）41PPT課件串的順序存儲（一）3.2棧、隊列和串的存儲結構（續）//----------串的定長順序存儲表示------------#defineMAXSTRLEN255//最大串長度typedefunsignedcharSString[MAXSTRLEN+1] //0號單元存放串的長度串順序存儲的特點：連續存儲單元靜態分配串操作中的原操作一般為“字符序列的復制”截尾法處理串值序列的上越界42PPT課件StatusSubString(SString&Sub,SStringS,intpos,int

len){

if(pos<1||pos>S[0]||len<0||len>S[0]–pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}//SubString串的順序存儲（二）3.2棧、隊列和串的存儲結構（續）StatusConcat(SString&T,SStringS1,SStringS2){…}//Concat43PPT課件一般算法3.3串的模式匹配算法int

Index(SString

S,SStringT,intpos){//返回子串T在主串S中第pos個

i=pos; j=1; //字符之后的位置。若不存在，

while(i<=s[0]&&j<=T[0]){//函數值位0 if(S[i]==T[j]){++i; ++j;} else{i=i-j+2; j=1;}}if(j>T[0])returni–T[0];elsereturn0;}//Index算法時間復雜度：T(n)=O(n*m)邏輯函數為Index(S,T,pos)S=‘a1a2…ai…an’ T=‘t1t2…tj…tm’一般而言，m<<n算法思路：從主串S的第pos個字符起和模式的第一個字符比較之，若相等，繼續逐個比較后續字符，否則從主串的下一個字符起再重新和模式的字符比較之。44PPT課件3.3串的模式匹配算法（續）第一趟主串： ababcabcacbab //i=3

模式串：abc //j=3第二趟主串： ababcabcacbab //i=2

模式串：a /j=1第三趟主串： ababcabcacbab //i=7

模式串：abcac //j=5第四趟主串： ababcabcacbab //i=4

模式串：a //j=1第五趟主串： ababcabcacbab //i=5

模式串：

a //j=1第六趟主串： ababcabcacbab //i=11

模式串：abcac //j=6模式串T=‘abcac’45PPT課件改進算法---思路3.3串的模式匹配算法（續）KMP算法思路：從主串S的第pos個字符起和模式的第一個字符比較之，若相等，繼續逐個比較后續字符。當一趟匹配過程中出現字符比較不等時，不回朔i指針，而是利用已經得到的“部分匹配”的結果將模式串向右“滑動”盡可能遠的一段距離后，繼續進行比較。優點：在匹配過程中，主串的跟蹤指針不回朔時間效率達到T(n)=O(n+m)如何理解“部分匹配”？主串：acabaacaabcac 模式串：acaab

46PPT課件改進算法---原理3.3串的模式匹配算法（續）設主串S=‘s1s2…si…sn’,模式串T=‘t1t2…tj…tm’在匹配過程中，當主串中第i個字符與模式串中第j個字符“失配”時（si不等于tj），將模式串“向右滑動”，讓模式串中第k（k<j）個字符與si對齊繼續比較。這時有：

‘t1t2…tk-1’=‘si-k+1si-k+2…si-1’ -----(1)而由部分匹配成功的結果可知：

‘t1t2…tj-1’=‘si-j+1si-j+2…si-1’ -----(2)由(2)式可以推知：

‘tj-k+1tj-k+2…tj-1’=‘si-k+1si-k+2…si-1’ -----(3)由(1)式與(3)式可以推知：

‘t1t2…tk-1’=‘tj-k+1tj-k+2…tj-1’ -----(4)

47PPT課件令next[j]=k，表示當模式串中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置。根據其語義，定義如下：0 當j=1時//相當于主串中i指針推進一個位置Next[j]=Max{k|1<k<j且‘t1t2…tk-1’=‘tj-k+1tj-k+2…tj-1’}// 1 其他情況改進算法---Next函數定義3.3串的模式匹配算法（續）設主串S=‘s1s2…si…sn’,模式串T=‘t1t2…tj…tm’Next函數值僅取決于模式串本身的結構而與相匹配的主串無關j 12345678模式串 abaabcacnext[j] 01122312j 12345678模式串 abaabcacnext[j] 保證得到第一個“配串”48PPT課件改進算法---匹配過程3.3串的模式匹配算法（續）第一趟主串： acabaabaabcac aabc //i=2

模式串：a

b

//j=2,next[2]=1第二趟主串： acabaabaabcac aabc //i=2

模式串：a //j=1,next[1]=0第三趟主串： acabaabaabcac aabc //i=8

模式串：abaabc //j=6,next[6]=3第四趟主串：acabaabaabcac aabc //i=14

模式串：

(ab)aabcac //j=9j 12345678模式串 abaabcacnext[j] 0112231249PPT課件int

Index_KMP(SString

S,SStringT,intpos){//返回子串T在主串S中第pos個字符之后的位置。若不存在,函數值為0

i=pos; j=1; while(i<=s[0]&&j<=T[0]){ if(j==0|S[i]==T[j]){++i; ++j;} elsej=next[j];}if(j>T[0])returni–T[0];elsereturn0;}//Index_KMP算法時間復雜度：T(n)=O(n+m)改進算法---KMP算法3.3串的模式匹配算法（續）50PPT課件4.數組5.廣義表6.樹和二叉樹7.圖第二部分非線性數據結構51PPT課件4.數組5.廣義表6.樹和二叉樹7.圖教學內容---第六章52PPT課件6.1樹的邏輯結構基本概念和術語樹：樹T是n個結點的有限集。非空樹中： （1）有且只有一個特定的稱為根(Root)的結點； （2）當n>1時，其余結點可分為m(m>0)各互不相交 的有限集T1,T2,…,Tm,其中每一個集合本身又是 一棵樹，并且稱為根的子樹(SubTree)。樹的結點：一個數據元素和指向其子樹的分支。結點的度：結點擁有的子樹數。終端結點（或葉子）：度為0的結點。非終端結點（或分支結點、或內部結點）：度不為0的結點。樹的度：樹內各結點的度的最大值。（結點的）孩子：結點的子樹的根。53PPT課件6.1樹的邏輯結構（續）樹的性質及樹的表示樹的性質：遞歸性層次性樹的表示形式：樹形表示集合嵌套表示廣義表形式表示凹入表示54PPT課件datafirstchildnextsibling結點6.2樹的存儲結構（續）孩子兄弟表示法（二叉鏈表）//----------樹的二叉鏈表（孩子-兄弟）存儲表示------------typedef

struct

CSNode{

ElemType data; //樹結點數據域

struct

CSNode *firstchild,*nextsibling;}CSNode,*CSTree;55PPT課件6.3二叉樹的邏輯結構二叉樹的描述性定義及其基本形態二叉樹：二叉樹BT是n個結點的有限集。非空二叉樹中：（1）有且只有一個特定的稱為根(Root)的結點； （2）當n>1時，其余結點可分為2個互不相交的有限集BTL,BTR,BTL,BTR分別又是一棵二叉樹，BTL稱為根的左子樹；BTR稱為根的右子樹。二叉樹的基本形態：

五種：空二叉樹；僅有根結點的二叉樹；右子樹為空的二叉樹；左、右子樹均不為空的二叉樹；左子樹為空的二叉樹。56PPT課件6.3二叉樹的邏輯結構（續）二叉樹的數學性質性質1：在二叉樹的第i層上至多右2i-1個結點(i>=1);性質2：深度為k的二叉樹至多有2k–1個結點(k>=1);性質3：二叉樹T，若葉子結點數為n0,度為2的結點數為n2，則有n0=n2+1;性質1：[證明]

i=1時，顯然有2i-1=20=1；假設對于所有的j，1<=j<i，第j層上至多有2j-1個結點，則當j=i時，由假設知2i-1層上至多右2i-2,而二叉樹的每個結點的度至多為2，故在第i層上

最大結點數為i-1層上最大結點數的2倍，即2*2i-2=2i-1。

[證畢]性質3：[證明]

n=n0

+n1+n2n

=B+1B=n1+2n2所以：

n0

=n2+1

[證畢]性質4：具有n個結點的完全二叉樹的深度為：以2為底的n的對數值取下整+1； 性質5：n個結點的完全二叉樹結點按照層序編號，則對任一結點i(1<=i<=n)，有：（1）如果i=1，則結點i是二叉樹的根；如果i>1，則其雙親是結點(i/2)取下整；(2)如果2i>n,則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點2i；(3)如果如果2i+1>n,則結點i無右孩子；否則其右孩子是結點2i+1。滿二叉樹：深度為k且有2k–1個結點的二叉樹;完全二叉樹：深度為k，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。性質4：[證明]假設深度為k，由性質2以及完全二叉樹定義有：2k-1–1<n<=2k–1推出2k-1

<=n<2k

k–1<=以2為底的n的對數<k由于k是整數，所以結論成立。

[證畢]57PPT課件6.4二叉樹的存儲結構順序存儲具體做法：利用完全二叉樹的性質，元素之間的關系隱含在元素的編號中，所以采用順序存儲后，完全二叉樹中結點的存儲位置為其編號所在的位置。對于一般二叉樹，若采用順序存儲，須先增加虛結點以補成虛完全二叉樹，對此虛完全二叉樹的存儲對應該二叉樹的順序存儲。//----------二叉樹的順序存儲表示------------#defineMAX_TREE_SIZE 100typedef

TElemType

SqBiTree[MAX_TREE_SIZE]; //0號單元存放根結點SqBiTree

bt;58PPT課件ABCDIJEABDIJK6.4二叉樹的存儲結構（續）順序存儲59PPT課件6.4二叉樹的存儲結構（續）二叉鏈表存儲datalchildrchild結點//----------二叉樹的二叉鏈表存儲表示------------typedef

struct

BiTNode{

TElemType data; //數據域

struct

BiTNode *lchild,*rchild;}BiTNode,*BiTree;60PPT課件6.4二叉樹的存儲結構（續）三叉鏈表存儲datalchildrchild結點parent//----------二叉樹的三叉鏈表存儲表示------------typedef

struct

BiTNode{

TElemType data; //數據域

struct

BiTNode *lchild,*rchild，*parent;}BiTNode,*BiTree;61PPT課件6.4二叉樹的存儲結構（續）（二叉）線索鏈表存儲datalchild結點ltagrtagrchild//----------二叉樹的二叉線索鏈表存儲表示------------typedef

enum{Link,Thread}PointerTag;//Link==0;Thread==1typedef

struct

BiThrNode{

TElemType data; //數據域

struct

BiThrNode *lchild,*rchild;//左、右孩子指針

PointerTag

LTag，Rtag; //左、右標志}BiThrNode,*BiThrTree;62PPT課件EABCDFIJHGK6.4二叉樹的存儲結構（續）（二叉）線索鏈表存儲63PPT課件6.5二叉樹的遍歷及線索化遍歷二叉樹在二叉樹中查找具有某種特征的結點需要對結點進行訪問（處理、輸出等）操作二叉樹上許多復雜操作的基礎是對其遍歷遍歷(Traversing)：按照某條路徑訪問每個結點,使得每個結點均被訪問一次，而且僅被訪問一次。遍歷本質：結點之間非線性關系線性化的過程兩種思路： *只要保證每個結點都被訪問到一次； *遍歷過程中易于實現關于結點的復雜操作層次遍歷法遞歸遍歷法：先序、中序、后序64PPT課件6.5二叉樹的遍歷及線索化（續）遍歷二叉樹的方法先序遍歷(PreOrderTraverse)：DLR;

若二叉樹為空，則空操作（遞歸基礎）；否則：訪問根結點；先序遍歷左子樹；先序遍歷右子樹。中序遍歷(InOrderTraverse)：LDR;

若二叉樹為空，則空操作（遞歸基礎）；否則：中序遍歷左子樹；訪問根結點；中序遍歷右子樹。后序遍歷(PostOrderTraverse)：LRD;

若二叉樹為空，則空操作（遞歸基礎）；否則：后序遍歷左子樹；中序遍歷右子樹；訪問根結點。層次遍歷(LevelOrderTraverse)：從上到下，自左至右按照層次遍歷。65PPT課件EABCDFIJHGK層次遍歷：A,B,I,C,D,J,K,E,F,G,H先序遍歷：A,B,C,D,E,F,G,H,I,J,K中序遍歷：C,B,E,D,G,F,H,A,J,I,K后序遍歷：C,E,G,HF,D,B,J,K,I,A66PPT課件StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍歷二叉樹T的遞歸算法，對每個數據元素調用函數Visit

if(T){

if(InOrderTraverse(T->lchild,Visit)) if(Visit(T->data)){

if(InOrderTraverse(T->rchild,Visit)) returnOK; }elsereturnERROR;//當訪問失敗時，出錯}else returnOK;//一次遞歸訪問終止}InOrderTraverse

//算法時間復雜度：O(n)6.5二叉樹的遍歷及線索化（續）中序遍歷的算法StatusInOrderTraverse1(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit

InitStack(S); Push(S,T); //根指針入棧While(!StackEmpty(S)){ while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到盡頭 Pop(S,p) //空指針退棧

if(!StackEmpty(S)){ //訪問結點，向右一步

Pop(S,p); if(!Visit(p->data))returnERROR//訪問出錯

Push(S,p->rchild);}//if}//whilereturnOK;}InOrderTraverse

//算法時間復雜度：O(n)StatusInOrderTraverse2(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit

InitStack(S); p=T; While(p||!StackEmpty(S)){ if(p){Push(S,p);p=p->lchild;}//根指針入棧,遍歷左子樹 else{

//根指針退棧，訪問根結點，遍歷右子樹

Pop(S,p); if(!Visit(p->data))returnERROR//訪問出錯

p=p->rchild);}//else}//whilereturnOK;}InOrderTraverse

//算法時間復雜度：O(n)67PPT課件6.5二叉樹的遍歷及線索化（續）二叉樹遍歷的典型應用已知二叉樹的前序遍歷序列和中序遍歷序列，或者已知二叉樹的后序遍歷序列和中序遍歷序列，可以唯一確定這棵二叉樹。EABCDFIJHGKStep1:判定根，由PostOrder知根為A；Step2:判定左子樹元素集合，由InOrder知為{CBEDGFH}InOrder:CBEDGFHAJIKPostOrder:CEGHFDBJKIAStep3:判定右子樹元素集合，由InOrder知為{JIK}Step4:分別對左、右子樹元素集合按照中序和后序序列遞歸進行Step1---Step3，直到元素集合為空。68PPT課件6.5二叉樹的遍歷及線索化（續）線索二叉樹遍歷本質是結點之間非線性關系線性化的過程遍歷后的元素之間的某種線性關系一般隱藏在遍歷規則下需要多次對同一棵樹遍歷時，如何提高效率？在二叉鏈表結構中增加線索域，顯式描述遍歷后的線索關系節省線索域空間，充分利用二叉鏈表中空的n+1個指針域線索鏈表：二叉樹的存儲結構，結點結構定義見前面。線索：指向結點前驅和后繼的指針，叫做線索。線索二叉樹：加上線索的二叉樹。線索化：對二叉樹以某種次序遍歷使其變為線索二叉樹的過程。線索二叉樹上遍歷的過程，就是根據線索和遍歷規則不斷找當前結點后繼結點的過程。69PPT課件6.5二叉樹的遍歷及線索化（續）線索二叉樹上的中序遍歷InOrder:CBEDGFHAJIK設當前結點指針為p，其前驅結點為q，后繼結點指針為s,則有：求結點p的后繼：1.若p->rtag=1

則s=p->rchild;2.若p->rtag=0s為p的右子樹的中序遍歷序列的第一個結點，即右子樹最左下結點EABCDFIJHGK求結點p的前驅：1.若p->ltag=1

則q=p->lchild;2.若p->rtag=0q為p的左子樹的中序遍歷序列的第一個結點，即左子樹最右下結點70PPT課件6.6樹、森林與二叉樹的轉換森林與樹相互遞歸定義森林：m棵互不相交的樹的集合。樹：樹是一個二元組Tree=(root，F),root是根，F是m(m>0)棵樹的森林，F={T1,T2,…,Tm}其中Ti=(ri，Fi)

稱為根的第i棵子樹；當m!=0時，在樹根和其子樹森林之間存在下列關系：RF={<root，ri>|i=1,2,…,m,m>0}

71PPT課件6.6樹、森林與二叉樹的轉換（續）樹與二叉樹的轉換目的：利用二叉樹運算來簡化樹和森林上的運算；依據：樹與二叉樹具有相同的二叉鏈表存儲結構；EABCDFIABDECIF72PPT課件EABCDFIJHGKABDECIFKJGH6.6樹、森林與二叉樹的轉換（續）73PPT課件EABCDFIJHGKEABCDFHGKIJ6.6樹、森林與二叉樹的轉換（續）74PPT課件6.7二叉樹的應用哈夫曼樹(HuffmanTree)結點之間路徑長度：樹中兩個結點之間的分支構成這兩個結點的路徑，路徑上的分支數目為路徑長度。樹的路徑長度：樹根到每個結點的路徑長度之和。結點的帶權路徑長度：該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，記為：WPL=w1k1+w2k2+…+wiki

+wnkn。最優二叉樹（哈夫曼樹）：設n個權值{w1,w2,…,wn

},構造一棵有n個葉子結點的二叉樹，每個葉子結點帶權wi,則其中帶權路徑長度WPL最小的二叉樹稱為最優二叉樹（哈夫曼樹）。75PPT課件6.7二叉樹的應用（續）哈夫曼算法(HuffmanAlgorithmic)輸入：n個權值{w1,w2,…,wn

}

；輸出：一棵哈夫曼樹算法：步驟一：根據給定的n個權值{w1,w2,…,wn

}

構成n棵二叉樹的集合F={T1,T2…,Tn}，其中每棵二叉樹Ti

中只有一個帶權為wi

的根結點，其左右子樹均為空。步驟二：在F中選取兩棵根結點的權值最小的樹作為左、右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。步驟三：在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。步驟四：重復步驟二與三，直到F只含有一棵樹為止。76PPT課件給定權的集合:{15,3,14,2,6,9,16,17}6.7二叉樹的應用（續）哈夫曼算法(HuffmanAlgorithmic){15,3,14,2,6,9,16,17}{15,5,14,6,9,16,17}{15,11,14,9,16,17}{15,14,20,16,17}{29,20,16,17}{29,20,33}{49,33}{82}9496161782325141511202933WPL=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=22977PPT課件6.7二叉樹的應用（續）哈夫曼編碼(HuffmanCode)等長編碼：每個被編碼對象的碼長相等。 優點：碼長等長，易于解碼； 缺點：被編碼信息總碼長較大，尤其是當存在 許多不常用的被編碼對象時前綴編碼：任一個被編碼對象的編碼都不是另一個 被編碼對象的編碼的前綴。 優點：當存在被編碼對象使用概率不同時，被 編碼信息總碼長可以減小； 缺點：碼長不等長，不易于解碼78PPT課件6.7二叉樹的應用（續）哈夫曼編碼(HuffmanCode)---前綴編碼利用二叉樹來設計二進制的前綴編碼：被編碼對象出現在二叉樹的葉子結點。約定左分支表示字符“0”，右分支表示字符“1”，則可以從根結點到葉子結點的路徑上分支字符組成的字符串作為該葉子結點對應對象的編碼。baedcf0000011111a(00)b(010)c(0110)d(0111)e(10)f(11)這種編碼的譯碼過程從根開始。沿著某條分支走到葉子結點時，走過的二進制字符串即譯為該葉子結點對應的對象。然后循環掃描總編碼后的字符串。79PPT課件6.7二叉樹的應用（續）哈夫曼編碼與譯碼利用哈夫曼算法可以得到總碼長最短的二進制前綴編碼，即為哈夫曼編碼。設某次編碼應用中不同被編碼對象有n種，以此n種被編碼對象出現的頻率作權，構造出的哈夫曼樹即為這n種對象的編碼樹，由此可得到其二進制的前綴編碼。假定用于通訊的電文如下，現在要對其編碼，采用哈夫曼編碼。寫出編碼后的二進制串。電文：castcatssatatatasac(110)a(0)s(111)t(10)Set={c,a,s,t}W={2,7,4,5}電文編碼：11001111011001011111101001001001110518711642000111csat80PPT課件4.數組5.廣義表6.樹和二叉樹7.圖教學內容---第七章81PPT課件ADTGraph{

數據對象：V={具有相同性質的數據元素}

數據關系：R: R={VR}

VR={<v,w>|v,w屬于V且P(v,w),<v,w>是從v到w的一 條弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}

基本操作：P:

CreateGraph(&G,V,VR);DFSTraverseGraph(G,v,Visit()); …;BFSTraverseGraph(G,v,Visit())

}ADTGraph7.1圖的邏輯結構圖的抽象數據類型82PPT課件7.1圖的邏輯結構（續）基本概念和術語頂點(Vertex)、弧(Arc)、有向圖(Digraph)、邊(Edge)、無向圖(Undigraph)、完全圖(Completedgraph)、有向完全圖、稀疏圖(Sparsegraph)、權(Weight)、網(Network)、子圖(Subgraph)、鄰接點(Adjacent)、（頂點的）度(Degree)、（頂點的）入度(InDegree)、（頂點的）出度(OutDegree)、（頂點之間）路徑(Path)、（頂點之間）路徑長度、回路或環(Cycle)、簡單路徑、簡單回路（簡單環）、（頂點之間）連通、連通圖(ConnectedGraph)、連通分量(ConnectedComponent)、強連通圖、強連通分量、（連通圖的）生成樹：（有向圖的）生成森林83PPT課件 01010 10101G1.arcs=01011 10100 011007.2樹的存儲結構（續）數組表示法V3V1V2V5V4G1V1V2V4V3G2 0110 0000G2.arcs=1001 111084PPT課件7.2圖的存儲結構（續）鄰接表---圖的鏈式存儲基本思路：對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點vi的邊（對有向圖是以頂點vi為尾的?。?。每個表結點由三個域組成：鄰接點域(adjvex)指示與頂點vi鄰接的點在圖中的位置；鏈域(nextarc)指示下一條邊或弧的結點；數據域(info)存儲和邊或弧相關的信息。頭結點由兩個域組成：鏈域(firstarc)指向鏈表中第一個結點；數據域(data)存儲頂點vi信息。頭結點以順序結構形式存取，以便隨機訪問任一頂點的鏈表。Adjvexnextarcinfodatafirstarc表結點頭結點85PPT課件7.2圖的存儲結構（續）V10V21V32V43V5421^20^420^31^431^V3V1V2V5V4G1V1V2V4V3G2V10V32V21V4330^0^32^30^V10V2^1V32V4330^221^20^86PPT課件7.2圖的存儲結構（續）鄰接表---圖的鏈式存儲鄰接表的優點：邊（或弧）稀疏時，節省空間；和邊（或?。┫嚓P的信息較多時，節省空間；容易求得當前頂點的第一個鄰接點、下一個鄰接點。對有向圖，也可建立逆向鄰接表，即對每個頂點建立一個鏈接以該頂點為頭的弧的表。87PPT課件7.3圖的遍歷遍歷圖在圖中查找具有某種特征的結點需要對結點進行訪問（處理、輸出等）操作圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎圖的遍歷(TraversingGraph)：從圖的某一個頂點出發，按照某條路徑訪問每個結點,使得每個結點均被訪問一次，而且僅被訪問一次。遍歷本質：結點之間非線性關系線性化的過程遍歷思路： *深度優先：類似于樹的先根遍歷； *廣度優先：類似于樹的層次遍歷。88PPT課件7.3圖的遍歷（續）深度優先搜索遍歷思路：從圖的某個頂點v出發，訪問此頂點，然后依次從v的未被訪問的鄰接點出發深度優先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為始點，重復上述過程，直至圖中所有頂點都被訪問到為止。這是一個遞歸算法，遍歷過程中，當某個頂點的所有鄰接點都被訪問到后，需要“回朔”，即沿著調用的逆方向回退到上一層頂點，繼續考察該頂點的下一個鄰接點。Booleanvisited[MAX]; //訪問標志數組Status(*VisitFunc)(intv); //函數變量VoidDFSTraverse(GraphG,Status(*Visit)(intv)){

VisitFunc=Visit；//使用全局變量VisitFunc，使DFS不必設函數指針參數

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//標志數組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}StatusDFS(GraphG,intv){//從第v個頂點出發遞歸地深度優先遍歷圖G，對每個元素調用函數Visitvisited[v]=TRUE; VisitFunc(v);//訪問第v個頂點for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);}//算法時間復雜度與存儲結構相關鄰接矩陣存儲:T(n)=O(n2);鄰接表存儲:T(n)=O(n+e)89PPT課件7.3圖的遍歷（續）深度優先搜索V12V9V10V11V1G3V3V6V2V8V5V4V7一種DFS遍歷序列：

V1,V2,V4,V8,V5,V3,V6,V7,V9,V10,V12,V11當存儲結構和算法確定后，遍歷序列唯一。90PPT課件7.3圖的遍歷（續）廣度優先搜索遍歷思路：從圖的某個頂點v出發，訪問此頂點，然后依次訪問v的未被訪問的鄰接點，然后從這些鄰接點出發依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的