數(shù)據(jù)結構知識點全面總結-精華版

..緒論內容提要：◆數(shù)據(jù)結構研究的內容。針對非數(shù)值計算的程序設計問題,研究計算機的操作對象以及它們之間的關系和操作。數(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ù)結構——是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合,表示為：Data_Structure=〔D,R數(shù)據(jù)類型——是一個值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型——由用戶定義的一個數(shù)學模型與定義在該模型上的一組操作,它由基本的數(shù)據(jù)類型構成?！羲惴ǖ亩x及五個特征。算法——是對特定問題求解步驟的一種描述,它是指令的有限序列,是一系列輸入轉換為輸出的計算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性◆算法設計要求。①正確性、②可讀性、③健壯性、④效率與低存儲量需求◆算法分析。時間復雜度、空間復雜度、穩(wěn)定性學習重點：◆數(shù)據(jù)結構的"三要素"：邏輯結構、物理〔存儲結構及在這種結構上所定義的操作〔運算?！粲糜嬎阏Z句頻度來估算算法的時間復雜度。線性表內容提要：◆線性表的邏輯結構定義,對線性表定義的操作。線性表的定義：用數(shù)據(jù)元素的有限序列表示◆線性表的存儲結構：順序存儲結構和鏈式存儲結構。順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結構。鏈式存儲結構:其結點在存儲器中的位置是隨意的,即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。通過指針來實現(xiàn)！◆線性表的操作在兩種存儲結構中的實現(xiàn)。數(shù)據(jù)結構的基本運算：修改、插入、刪除、查找、排序修改——通過數(shù)組的下標便可訪問某個特定元素并修改之。核心語句:V[i]=x;順序表修改操作的時間效率是O<1>2>插入——在線性表的第i個位置前插入一個元素實現(xiàn)步驟：①將第n至第i位的元素向后移動一個位置；②將要插入的元素寫到第i個位置；③表長加1。注意：事先應判斷:插入位置i是否合法?表是否已滿?應當符合條件：1≤i≤n+1或i=[1,n+1]核心語句：for<j=n;j>=i;j-->a[j+1]=a[j];a[i]=x;n++;插入時的平均移動次數(shù)為：n<n+1>/2÷〔n+1＝n/2≈O<n>3>刪除——刪除線性表的第i個位置上的元素實現(xiàn)步驟：①將第i+1至第n位的元素向前移動一個位置；②表長減1。注意：事先需要判斷,刪除位置i是否合法?應當符合條件：1≤i≤n或i=[1,n]核心語句：for<j=i+1;j<=n;j++>a[j-1]=a[j];n--;順序表刪除一元素的時間效率為:T〔n>=<n-1>/2≈O<n>順序表插入、刪除算法的平均空間復雜度為O<1>單鏈表：〔1用單鏈表結構來存放26個英文字母組成的線性表〔a,b,c,…,z,請寫出C語言程序。#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;node*p,*q,*head;//一般需要3個指針變量intn;//數(shù)據(jù)元素的個數(shù)intm=sizeof<node>;/*結構類型定義好之后,每個node類型的長度就固定了,m求一次即可*/voidbuild<>//字母鏈表的生成。要一個個慢慢鏈入{inti;head=<node*>malloc<m>;//m=sizeof<node>前面已求出p=head;for<i=1;i<26;i++>//因尾結點要特殊處理,故i≠26{p->data=i+‘a’-1;//第一個結點值為字符ap->next=<node*>malloc<m>;//為后繼結點"挖坑"！p=p->next；}//讓指針變量P指向后一個結點p->data=i+‘a’-1;//最后一個元素要單獨處理p->next=NULL;//單鏈表尾結點的指針域要置空！}}voiddisplay<>//字母鏈表的輸出{p=head;while<p>//當指針不空時循環(huán)〔僅限于無頭結點的情況{ printf<"%c",p->data>; p=p->next;//讓指針不斷"順藤摸瓜"}}單鏈表的修改<或讀取

思路：要修改第i個數(shù)據(jù)元素,必須從頭指針起一直找到該結點的指針p,然后才能：p>data=new_value讀取第i個數(shù)據(jù)元素的核心語句是：Linklist*find<Linklist*head,inti>{intj=1;Linklist*p;P=head->next;While<<p!=NULL>&&<j<i>>{p=p->next;j++;}returnp;}單鏈表的插入鏈表插入的核心語句：Step1：s->next=p->next;Step2：p->next=s；單鏈表的刪除刪除動作的核心語句〔要借助輔助指針變量q：q=p->next;//首先保存b的指針,靠它才能找到c；p->next=q->next;//將a、c兩結點相連,淘汰b結點；free<q>；//徹底釋放b結點空間雙向鏈表的插入操作：設p已指向第i元素,請在第i元素前插入元素x：①ai-1的后繼從ai<指針是p>變?yōu)閤〔指針是s>:s->next=p;p->prior->next=s;②ai的前驅從ai-1<指針是p->prior>變?yōu)閤<指針是s>;s->prior=p->prior;p->prior=s;雙向鏈表的刪除操作：設p指向第i個元素,刪除第i個元素后繼方向：ai-1的后繼由ai<指針p>變?yōu)閍i+1<指針p->next>;p->prior->next=p->next;前驅方向：ai+1的前驅由ai<指針p>變?yōu)閍i-1<指針p->prior>; p->next->prior=p->prior;◆數(shù)組的邏輯結構定義及存儲數(shù)組：由一組名字相同、下標不同的變量構成N維數(shù)組的特點：n個下標,每個元素受到n個關系約束一個n維數(shù)組可以看成是由若干個n－1維數(shù)組組成的線性表。存儲：事先約定按某種次序將數(shù)組元素排成一列序列,然后將這個線性序列存入存儲器中。在二維數(shù)組中,我們既可以規(guī)定按行存儲,也可以規(guī)定按列存儲。設一般的二維數(shù)組是A[c1..d1,c2..d2],則行優(yōu)先存儲時的地址公式為：

二維數(shù)組列優(yōu)先存儲的通式為：◆稀疏矩陣〔含特殊矩陣的存儲及運算。稀疏矩陣：矩陣中非零元素的個數(shù)較少〔一般小于5%學習重點：◆線性表的邏輯結構,指線性表的數(shù)據(jù)元素間存在著線性關系。在順序存儲結構中,元素存儲的先后位置反映出這種線性關系,而在鏈式存儲結構中,是靠指針來反映這種關系的?！繇樞虼鎯Y構用一維數(shù)組表示,給定下標,可以存取相應元素,屬于隨機存取的存儲結構?！翩湵聿僮髦袘⒁獠灰规溡馔?斷開"。因此,若在某結點前插入一個元素,或刪除某元素,必須知道該元素的前驅結點的指針?！粽莆胀ㄟ^畫出結點圖來進行鏈表〔單鏈表、循環(huán)鏈表等的生成、插入、刪除、遍歷等操作?！魯?shù)組〔主要是二維在以行序/列序為主的存儲中的地址計算方法?！粝∈杈仃嚨娜M表存儲結構?！粝∈杈仃嚨氖宙湵泶鎯Ψ椒?。補充重點：1.每個存儲結點都包含兩部分：數(shù)據(jù)域和指針域<鏈域>2.在單鏈表中,除了首元結點外,任一結點的存儲位置由其直接前驅結點的鏈域的值指示。3.在鏈表中設置頭結點有什么好處？頭結點即在鏈表的首元結點之前附設的一個結點,該結點的數(shù)據(jù)域可以為空,也可存放表長度等附加信息,其作用是為了對鏈表進行操作時,可以對空表、非空表的情況以及對首元結點進行統(tǒng)一處理,編程更方便。如何表示空表？〔1無頭結點時,當頭指針的值為空時表示空表；〔2有頭結點時,當頭結點的指針域為空時表示空表。5.鏈表的數(shù)據(jù)元素有兩個域,不再是簡單數(shù)據(jù)類型,編程時該如何表示？因每個結點至少有兩個分量,且數(shù)據(jù)類型通常不一致,所以要采用結構數(shù)據(jù)類型。6.sizeof<x>——計算變量x的長度〔字節(jié)數(shù)；malloc<m>—開辟m字節(jié)長度的地址空間,并返回這段空間的首地址；free<p>——釋放指針p所指變量的存儲空間,即徹底刪除一個變量。鏈表的運算效率分析：〔1查找因線性鏈表只能順序存取,即在查找時要從頭指針找起,查找的時間復雜度為O<n>。〔2插入和刪除因線性鏈表不需要移動元素,只要修改指針,一般情況下時間復雜度為O<1>。但是,如果要在單鏈表中進行前插或刪除操作,因為要從頭查找前驅結點,所耗時間復雜度將是O<n>。例：在n個結點的單鏈表中要刪除已知結點*P,需找到它的前驅結點的地址,其時間復雜度為O〔n8.順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲時,邏輯上相鄰的數(shù)據(jù)元素,其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大,存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈式存儲時,相鄰數(shù)據(jù)元素可隨意存放,但所占存儲空間分兩部分,一部分存放結點值,另一部分存放表示結點間關系的指針。鏈式存儲的優(yōu)點是插入或刪除元素時很方便,使用靈活。缺點是存儲密度小,存儲空間利用率低?！繇樞虮磉m宜于做查找這樣的靜態(tài)操作；◆鏈表宜于做插入、刪除這樣的動態(tài)操作?！羧艟€性表的長度變化不大,且其主要操作是查找,則采用順序表；◆若線性表的長度變化較大,且其主要操作是插入、刪除操作,則采用鏈表。9.判斷："數(shù)組的處理比其它復雜的結構要簡單",對嗎？答：對的。因為——①數(shù)組中各元素具有統(tǒng)一的類型；②數(shù)組元素的下標一般具有固定的上界和下界,即數(shù)組一旦被定義,它的維數(shù)和維界就不再改變。③數(shù)組的基本操作比較簡單,除了結構的初始化和銷毀之外,只有存取元素和修改元素值的操作。三元素組表中的每個結點對應于稀疏矩陣的一個非零元素,它包含有三個數(shù)據(jù)項,分別表示該元素的行下標、列下標和元素值。寫出右圖所示稀疏矩陣的壓縮存儲形式。解：介紹3種存儲形式。法1：用線性表表示：〔<1,2,12>,<1,3,9>,<3,1,-3>,<3,5,14>,<4,3,24>,<5,2,18>,<6,1,15>,<6,4,-7>法2：用十字鏈表表示用途：方便稀疏矩陣的加減運算方法：每個非0元素占用5個域法3：用三元組矩陣表示：稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能代碼：1.用數(shù)組V來存放26個英文字母組成的線性表〔a,b,c,…,z,寫出在順序結構上生成和顯示該表的C語言程序。charV[30];voidbuild<>//字母線性表的生成,即建表操作{inti;V[0]='a';for<i=1;i<=n-1;i++>V[i]=V[i-1]+1;}voiddisplay<>//字母線性表的顯示,即讀表操作{inti;for<i=0;i<=n-1;i++>printf<"%c",v[i]>;printf<"\n">;}voidmain<void>//主函數(shù),字母線性表的生成和輸出{n=26;//n是表長,是數(shù)據(jù)元素的個數(shù),而不是V的實際下標build<>;display<>;}棧和隊列內容提要：◆從數(shù)據(jù)結構角度來講,棧和隊列也是線性表,其操作是線性表操作的子集,屬操作受限的線性表。但從數(shù)據(jù)類型的角度看,它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。◆棧的定義及操作。棧是只準在一端進行插入和刪除操作的線性表,該端稱為棧的頂端。插入元素到棧頂?shù)牟僮?稱為入棧。從棧頂刪除最后一個元素的操作,稱為出棧。對于向上生成的堆棧:入?？谠E：堆棧指針top"先壓后加":S[top++]=an+1出?？谠E：堆棧指針top"先減后彈":e=S[--top]◆棧的順序和鏈式存儲結構,及在這兩種結構下實現(xiàn)棧的操作。順序棧入棧函數(shù)PUSH〔statusPush<ElemTypee>{if<top>M>{上溢}elses[top++]=e;}順序棧出棧函數(shù)POP<>statusPop<>{if<top=L>{下溢}else{e=s[--top];return<e>;}}◆隊列的定義及操作,隊列的刪除在一端〔隊尾,而插入則在隊列的另一端〔隊頭。因此在兩種存儲結構中,都需要隊頭和隊尾兩個指針。隊列：只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表。鏈隊列結點類型定義：typedefStructQNode{QElemTypedata;//元素StructQNode*next;//指向下一結點的指針}Qnode,*QueuePtr;鏈隊列類型定義：typedefstruct{QueuePtrfront;//隊首指針QueuePtrrear;//隊尾指針}LinkQueue;鏈隊示意圖：①空鏈隊的特征：front=rear②鏈隊會滿嗎？一般不會,因為刪除時有free動作。除非內存不足?、廴腙牎参膊坎迦耄簉ear->next=S;rear=S;出隊〔頭部刪除：front->next=p->next;順序隊順序隊類型定義：#defineQUEUE-MAXSIZE100//最大隊列長度typedefstruct{QElemType*base;//隊列的基址intfront;//隊首指針intrear;//隊尾指針}SqQueue建隊核心語句：q.base=<QElemType*>malloc<sizeof<QElemType*QUEUE_MAXSIZE;//分配空間順序隊示意圖：循環(huán)隊列：隊空條件:front=rear<初始化時：front=rear>隊滿條件：front=<rear+1>%N<N=maxsize>隊列長度〔即數(shù)據(jù)元素個數(shù)：L=〔N＋rear－front%N初始化一個空隊列StatusInitQueue<SqQueue&q>//初始化空循環(huán)隊列q{q.base=<QElemType*>malloc<sizeof<QElemType*QUEUE_MAXSIZE>;//分配空間if<!q.base>exit<OVERFLOW>;//內存分配失敗,退出程序q.front=q.rear=0;//置空隊列returnOK;}//InitQueue;入隊操作StatusEnQueue<SqQueue&q,QElemTypee>{//向循環(huán)隊列q的隊尾加入一個元素eif<<q.rear+1>%QUEUE_MAXSIZE==q.front>returnERROR;//隊滿則上溢,無法再入隊q.rear=<q.rear+1>%QUEUE_MAXSIZE;q.base[q.rear]=e;//新元素e入隊returnOK;}//EnQueue;出隊操作StatusDeQueue<SqQueue&q,QElemType&e>{//若隊列不空,刪除循環(huán)隊列q的隊頭元素,//由e返回其值,并返回OKif<q.front==q.rear>returnERROR;//隊列空q.front=<q.front+1>%QUEUE_MAXSIZE;e=q.base[q.front];returnOK;}//DeQueue◆鏈隊列空的條件是首尾指針相等,而循環(huán)隊列滿的條件的判定,則有隊尾加1等于隊頭和設標記兩種方法。補充重點：為什么要設計堆棧？它有什么獨特用途？①調用函數(shù)或子程序非它莫屬；②遞歸運算的有力工具；③用于保護現(xiàn)場和恢復現(xiàn)場；④簡化了程序設計的問題。 2.為什么要設計隊列？它有什么獨特用途？①離散事件的模擬〔模擬事件發(fā)生的先后順序,例如CPU芯片中的指令譯碼隊列；②操作系統(tǒng)中的作業(yè)調度〔一個CPU執(zhí)行多個作業(yè)；③簡化程序設計。什么叫"假溢出"？如何解決？答：在順序隊中,當尾指針已經到了數(shù)組的上界,不能再有入隊操作,但其實數(shù)組中還有空位置,這就叫"假溢出"。解決假溢出的途徑———采用循環(huán)隊列。4.在一個循環(huán)隊列中,若約定隊首指針指向隊首元素的前一個位置。那么,從循環(huán)隊列中刪除一個元素時,其操作是先移動隊首位置,后取出元素。5.線性表、棧、隊的異同點：相同點：邏輯結構相同,都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表,即受限的線性表〔只是對插入、刪除運算加以限制。不同點：①運算規(guī)則不同：線性表為隨機存?。欢鴹Ｊ侵辉试S在一端進行插入和刪除運算,因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算,因而是先進先出表FIFO。②用途不同,線性表比較通用；堆棧用于函數(shù)調用、遞歸和簡化設計等；隊列用于離散事件模擬、OS作業(yè)調度和簡化設計等。第四章串內容提要：◆串是數(shù)據(jù)元素為字符的線性表,串的定義及操作。串即字符串,是由零個或多個字符組成的有限序列,是數(shù)據(jù)元素為單個字符的特殊線性表。串比較：intstrcmp<char*s1,char*s2>;求串長：intstrlen<char*s>;串連接：charstrcat<char*to,char*from>子串T定位：charstrchr<char*s,char*c>;◆串的存儲結構,因串是數(shù)據(jù)元素為字符的線性表,所以存在"結點大小"的問題。模式匹配算法。串有三種機內表示方法：模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置〔定位定位問題稱為串的模式匹配,典型函數(shù)為Index<S,T,pos>BF算法的實現(xiàn)—即編寫Index<S,T,pos>函數(shù)BF算法設計思想：將主串S的第pos個字符和模式T的第1個字符比較,若相等,繼續(xù)逐個比較后續(xù)字符；若不等,從主串S的下一字符〔pos+1起,重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號,即匹配成功。否則,匹配失敗,返回值0。IntIndex_BP<SStringS,SStringT,intpos>{//返回子串T在主串S中第pos個字符之后的位置。若不存在,則函數(shù)值為0.//其中,T非空,1≤pos≤StrLength<S>i=pos;j=1;while<i<=S[0]&&j<=T[0]>//如果i,j二指針在正常長度范圍,{if<S[i]==T[j]>{++i,++j;}//則繼續(xù)比較后續(xù)字符else{i=i-j+2;j=1;}//若不相等,指針后退重新開始匹配}if<j>T[0]>returni-T[0];//T子串指針j正常到尾,說明匹配成功,elsereturn0;//否則屬于i>S[0]情況,i先到尾就不正常}//Index_BP補充重點：1.空串和空白串有無區(qū)別？答：有區(qū)別?？沾?lt;NullString>是指長度為零的串；而空白串<BlankString>,是指包含一個或多個空白字符‘’<空格鍵>的字符串."空串是任意串的子串；任意串S都是S本身的子串,除S本身外,S的其他子串稱為S的真子串。"樹和二叉樹內容提要：◆樹是復雜的非線性數(shù)據(jù)結構,樹,二叉樹的遞歸定義,基本概念,術語。樹：由一個或多個<n≥0>結點組成的有限集合T,有且僅有一個結點稱為根〔root,當n>1時,其余的結點分為m<m≥0>個互不相交的有限集合T1,T2,…,Tm。每個集合本身又是棵樹,被稱作這個根的子樹。二叉樹：是n〔n≥0個結點的有限集合,由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。術語：P88◆二叉樹的性質,存儲結構。性質1:在二叉樹的第i層上至多有2i-1個結點〔i>0。性質2:深度為k的二叉樹至多有2k-1個結點〔k>0。性質3:對于任何一棵二叉樹,若2度的結點數(shù)有n2個,則葉子數(shù)〔n0必定為n2＋1性質4:具有n個結點的完全二叉樹的深度必為性質5:對完全二叉樹,若從上至下、從左至右編號,則編號為i的結點,其左孩子編號必為2i,其右孩子編號為2i＋1；其雙親的編號必為i/2〔i＝1時為根,除外。二叉樹的存儲結構：一、順序存儲結構按二叉樹的結點"自上而下、從左至右"編號,用一組連續(xù)的存儲單元存儲。若是完全/滿二叉樹則可以做到唯一復原。不是完全二叉樹：一律轉為完全二叉樹！方法很簡單,將各層空缺處統(tǒng)統(tǒng)補上"虛結點",其內容為空。缺點：①浪費空間；②插入、刪除不便二、鏈式存儲結構

用二叉鏈表即可方便表示。一般從根結點開始存儲。

優(yōu)點：①不浪費空間；②插入、刪除方便◆二叉樹的遍歷。指按照某種次序訪問二叉樹的所有結點,并且每個結點僅訪問一次,得到一個線性序列。遍歷規(guī)則———二叉樹由根、左子樹、右子樹構成,定義為D、L、R若限定先左后右,則有三種實現(xiàn)方案：DLRLDRLRD先序遍歷中序遍歷后序遍歷◆樹的存儲結構,樹、森林的遍歷及和二叉樹的相互轉換?；仡?：二叉樹怎樣還原為樹？要點：逆操作,把所有右孩子變?yōu)樾值?！討?：森林如何轉為二叉樹？法一：①各森林先各自轉為二叉樹；②依次連到前一個二叉樹的右子樹上。法二：森林直接變兄弟,再轉為二叉樹討論2：二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯?其余右子樹變?yōu)樾值軜浜蜕值拇鎯Ψ绞剑簶溆腥N常用存儲方式：①雙親表示法②孩子表示法③孩子—兄弟表示法問：樹→二叉樹的"連線—抹線—旋轉"如何由計算機自動實現(xiàn)？答：用"左孩子右兄弟"表示法來存儲即可。存儲的過程就是樹轉換為二叉樹的過程！樹、森林的遍歷：①先根遍歷：訪問根結點；依次先根遍歷根結點的每棵子樹。②后根遍歷：依次后根遍歷根結點的每棵子樹；訪問根結點。討論：樹若采用"先轉換,后遍歷"方式,結果是否一樣？1.樹的先根遍歷與二叉樹的先序遍歷相同；2.樹的后根遍歷相當于二叉樹的中序遍歷；3.樹沒有中序遍歷,因為子樹無左右之分。①先序遍歷若森林為空,返回；訪問森林中第一棵樹的根結點；先根遍歷第一棵樹的根結點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構成的森林。②中序遍歷若森林為空,返回；中根遍歷森林中第一棵樹的根結點的子樹森林；訪問第一棵樹的根結點；中根遍歷除去第一棵樹之后剩余的樹構成的森林?！舳鏄涞膽茫汗蚵鼧浜凸蚵幋a。Huffman樹：最優(yōu)二叉樹〔帶權路徑長度最短的樹Huffman編碼：不等長編碼。樹的帶權路徑長度：〔樹中所有葉子結點的帶權路徑長度之和構造Huffman樹的基本思想：權值大的結點用短路徑,權值小的結點用長路徑。構造Huffman樹的步驟〔即Huffman算法：<1>由給定的n個權值{w1,w2,…,wn}構成n棵二叉樹的集合F={T1,T2,…,Tn}〔即森林,其中每棵二叉樹Ti中只有一個帶權為wi的根結點,其左右子樹均空。<2>在F中選取兩棵根結點權值最小的樹做為左右子樹構造一棵新的二叉樹,且讓新二叉樹根結點的權值等于其左右子樹的根結點權值之和。<3>在F中刪去這兩棵樹,同時將新得到的二叉樹加入F中。<4>重復<2>和<3>,直到F只含一棵樹為止。這棵樹便是Huffman樹。具體操作步驟：學習重點：〔本章內容是本課程的重點◆二叉樹性質及證明方法,并能把這種方法推廣到K叉樹。◆二叉樹遍歷,遍歷是基礎,由此導出許多實用的算法,如求二叉樹的高度、各結點的層次數(shù)、度為0、1、2的結點數(shù)?！粲啥鏄浔闅v的前序和中序序列或后序和中序序列可以唯一構造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。◆完全二叉樹的性質。◆樹、森林和二叉樹間的相互轉換。◆哈夫曼樹的定義、構造及求哈夫曼編碼。補充：1.滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹,而完全二叉樹雖然前k-1層是滿的,但最底層卻允許在右邊缺少連續(xù)若干個結點。滿二叉樹是完全二叉樹的一個特例。Huffman樹有什么用？最小冗余編碼、信息高效傳輸圖內容提要：◆圖的定義,概念、術語及基本操作。圖：記為G＝<V,E>其中：V是G的頂點集合,是有窮非空集；E是G的邊集合,是有窮集。術語：見課件◆圖的存儲結構。1.鄰接矩陣<數(shù)組>表示法①建立一個頂點表和一個鄰接矩陣②設圖A=<V,E>有n個頂點,則圖的鄰接矩陣是一個二維數(shù)組A.Edge[n][n]。注：在有向圖的鄰接矩陣中,第i行含義：以結點vi為尾的弧<即出度邊；第i列含義：以結點vi為頭的弧<即入度邊。鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作,如：求某頂點的度、判斷頂點之間是否有邊〔弧、找頂點的鄰接點等等。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊<弧>;空間效率為O<n2>。鄰接表<鏈式>表示法①對每個頂點vi建立一個單鏈表,把與vi有關聯(lián)的邊的信息〔即度或出度邊鏈接起來,表中每個結點都設為3個域:②每個單鏈表還應當附設一個頭結點〔設為2個域,存vi信息；③每個單鏈表的頭結點另外用順序存儲結構存儲。鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點：判斷兩頂點間是否有邊或弧,需搜索兩結點對應的單鏈表,沒有鄰接矩陣方便?！魣D的遍歷。遍歷定義：從已給的連通圖中某一頂點出發(fā),沿著一些邊,訪遍圖中所有的頂點,且使每個頂點僅被訪問一次,就叫做圖的遍歷,它是圖的基本運算。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索深度優(yōu)先搜索〔遍歷步驟：①訪問起始點v;②若v的第1個鄰接點沒訪問過,深度遍歷此鄰接點；③若當前鄰接點已訪問過,再找v的第2個鄰接點重新遍歷。基本思想：——仿樹的先序遍歷過程。廣度優(yōu)先搜索〔遍歷步驟：①在訪問了起始點v之后,依次訪問v的鄰接點；②然后再依次〔順序訪問這些點〔下一層中未被訪問過的鄰接點；③直到所有頂點都被訪問過為止?！魣D的應用〔最小生成樹,最短路經最小生成樹〔MST的性質如下：若U集是V的一個非空子集,若<u0,v0>是一條最小權值的邊,其中u0U,v0V-U；則：<u0,v0>必在最小生成樹上。求MST最常用的是以下兩種：Kruskal〔克魯斯卡爾算法、Prim〔普里姆算法Kruskal算法特點：將邊歸并,適于求稀疏網的最小生成樹。Prime算法特點:將頂點歸并,與邊數(shù)無關,適于稠密網。在帶權有向圖中A點〔源點到達B點〔終點的多條路徑中,尋找一條各邊權值之和最小的路徑,即最短路徑。兩種常見的最短路徑問題：一、單源最短路徑—用Dijkstra〔迪杰斯特拉算法二、所有頂點間的最短路徑—用Floyd〔弗洛伊德算法一、單源最短路徑<Dijkstra算法>一頂點到其余各頂點〔v0→j目的：設一有向圖G=〔V,E,已知各邊的權值,以某指定點v0為源點,求從v0到圖的其余各點的最短路徑。限定各邊上的權值大于或等于0。所有頂點之間的最短路徑可以通過調用n次Dijkstra算法來完成,還有更簡單的一個算法：Floyd算法〔自學。學習重點：圖是應用最廣泛的一種數(shù)據(jù)結構,本章也是這門課程的重點?！艋靖拍钪?連通分量,生成樹,鄰接點是重點。①連通圖：在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極XX通子圖叫做連通分量。②生成樹：是一個極小連通子圖,它含有圖中全部n個頂點,但只有n-1條邊。③鄰接點：若<u,v>是E<G>中的一條邊,則稱u與v互為鄰接頂點?！魣D是復雜的數(shù)據(jù)結構,也有順序和鏈式兩種存儲結構：數(shù)組表示法〔重點是鄰接距陣和鄰接表。這兩種存儲結構對有向圖和無向圖均適用◆圖的遍歷是圖的各種算法的基礎,應熟練掌握圖的深度、廣度優(yōu)先遍歷?！暨B通圖的最小生成樹不是唯一的,但最小生成樹邊上的權值之和是唯一的。應熟練掌握prim和kruscal算法,特別是手工分步模擬生成樹的生成過程。◆從單源點到其他頂點,以及各個頂點間的最短路徑問題,掌握熟練手工模擬。補充：問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1,此時是何形狀？答：是樹！而且是一棵有向樹！2.討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行,鏈表中結點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：對于任一確定的無向圖,鄰接矩陣是唯一的〔行列號與頂點編號一致,但鄰接表不唯一〔鏈接次序與頂點編號無關。3.用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲若對連通圖進行遍歷,得到的是生成樹若對非連通圖進行遍歷,得到的是生成森林。查找內容提要：◆查找表是稱為集合的數(shù)據(jù)結構。是元素間約束力最差的數(shù)據(jù)結構：元素間的關系是元素僅共在同一個集合中?！餐活愋偷臄?shù)據(jù)元素構成的集合◆查找表的操作：查找,插入,刪除。◆靜態(tài)查找表：順序表,有序表等。針對靜態(tài)查找表的查找算法主要有:順序查找、折半查找、分塊查找一、順序查找〔線性查找技巧：把待查關鍵字key存入表頭或表尾〔俗稱"哨兵",這樣可以加快執(zhí)行速度。intSearch_Seq<SSTableST,KeyTypekey>{ST.elem[0].key=key;for<i=ST.length;ST.elem[i].key!=key;--i>;returni;}//Search_Seq//ASL＝〔1＋n/2,時間效率為O<n>,這是查找成功的情況:順序查找的特點：優(yōu)點：算法簡單,且對順序結構或鏈表結構均適用。缺點：ASL太大,時間效率太低。二、折半查找〔二分或對分查找若關鍵字不在表中,怎樣得知并及時停止查找？典型標志是：當查找范圍的上界≤下界時停止查找。ASL的含義是"平均每個數(shù)據(jù)的查找時間",而前式是n個數(shù)據(jù)查找時間的總和,所以：三、分塊查找〔索引順序查找思路：先讓數(shù)據(jù)分塊有序,即分成若干子表,要求每個子表中的數(shù)據(jù)元素值都比后一塊中的數(shù)值小〔但子表內部未必有序。然后將各子表中的最大關鍵字構成一個索引表,表中還要包含每個子表的起始地址〔即頭指針。特點：塊間有序,塊內無序。查找：塊間折半,塊內線性查找步驟分兩步進行：①對索引表使用折半查找法〔因為索引表是有序表；②確定了待查關鍵字所在的子表后,在子表內采用順序查找法〔因為各子表內部是無序表；查找效率ASL分析：◆動態(tài)查找表：二叉排序樹,平衡二叉樹。特點：表結構在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關鍵字等于key的記錄,則查找成功返回；否則插入關鍵字等于key的記錄。①二叉排序樹的定義----或是一棵空樹；或者是具有如下性質的非空二叉樹：〔1左子樹的所有結點均小于根的值；〔2右子樹的所有結點均大于根的值；〔3它的左右子樹也分別為二叉排序樹。②二叉排序樹的插入與刪除思路：查找不成功,生成一個新結點s,插入到二叉排序樹中；查找成功則返回。SearchBST<K,&t>{//K為待查關鍵字,t為根結點指針p=t;//p為查找過程中進行掃描的指針while〔p!=NULL{case{K=p->data:{查找成功,return}

K<p->data:{q=p；p=p->L_child}//繼續(xù)向左搜索K>p->data:{q=p；p=p->R_child}//繼續(xù)向右搜索}

}//查找不成功則插入到二叉排序樹中s=<BiTree>malloc<sizeof<BiTNode>>;s->data=K;s->L_child=NULL;s->R_child=NULL;

//查找不成功,生成一個新結點s,插入到二叉排序樹葉子處case{

t=NULL：t=s;//若t為空,則插入的結點s作為根結點K<q->data:q->L_child=s;//若K比葉子小,掛左邊K>q->data:q->R_child=s;//若K比葉子大,掛右邊}

returnOK}③二叉排序樹的刪除操作如何實現(xiàn)？如何刪除一個結點？假設：*p表示被刪結點的指針；PL和PR分別表示*P的左、右孩子指針；*f表示*p的雙親結點指針；并假定*p是*f的左孩子；則可能有三種情況：*p有兩棵子樹時,如何進行刪除操作？設刪除前的中序遍歷序列為：….PLspPRf//顯然p的直接前驅是s,s是*p左子樹最右下方的結點希望刪除p后,其它元素的相對位置不變。有兩種解決方法：法1：令*p的左子樹為*f的左子樹,*p的右子樹接為*s的右子樹；//即fL=PL;SR=PR;法2：直接令*s代替*p//*s為*p左子樹最右下方的結點二叉排序樹的④平衡二叉樹的定義：又稱AVL樹,即它或者是一顆空樹,或者是它的左子樹和右子樹都是平衡二叉樹,且左子樹與右子樹的深度之差的絕對值不超過1。平衡因子：——該結點的左子樹的深度減去它的右子樹的深度。平衡二叉樹的特點：任一結點的平衡因子只能?。?1、0或1。如果在一棵AVL樹中插入一個新結點,就有可能造成失衡,此時必須重新調整樹的結構,使之恢復平衡。我們稱調整平衡過程為平衡旋轉。平衡旋轉可以歸納為四類：學習重點：◆查找表是稱為集合的數(shù)據(jù)結構。因元素間關系非常松散,其操作需借助其它數(shù)據(jù)結構來實現(xiàn)。本章列舉了三種方法〔靜態(tài)查找表,動態(tài)查找表實現(xiàn)查找表的運算?！繇樞虮硪蛟O置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長度不超過樹的深度?！舨檎业腁SL◆二叉排序樹的形態(tài)取決于元素的輸入順序。按中序遍歷可得到結點的有序序列,應熟練掌握其建立、查找,插入和刪除算法。◆平衡二叉樹的概念,應熟練掌握手工繪制平衡二叉樹。補充：1.查找的過程是怎樣的？給定一個值K,在含有n個記錄的文件中進行搜索,尋找一個關鍵字值等于K的記錄,如找到則輸出該記錄,否則輸出查找不成功的信息。2.對查找表常用的操作有哪些？查詢某個"特定的"數(shù)據(jù)元素是否在表中；查詢某個"特定的"數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。3.哪些查找方法？查找方法取決于表中數(shù)據(jù)的排列方式;4.如何評估查找方法的優(yōu)劣？用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度ASL。ASL=∑Pi.Ci5.使用折半查找算法時,要求被查文件：采用順序存貯結構、記錄按關鍵字遞增有序6.將線性表構造成二叉排序樹的優(yōu)點：①查找過程與順序結構有序表中的折半查找相似,查找效率高；②中序遍歷此二叉樹,將會得到一個關鍵字的有序序列〔即實現(xiàn)了排序運算；③如果查找不成功,能夠方便地將被查元素插入到二叉樹的葉子結點上,而且插入或刪除時只需修改指針而不需移動元素。內部排序內容提要：◆排序的定義,排序可以看作是線性表的一種操作排序:將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來?！襞判虻姆诸?穩(wěn)定排序與不穩(wěn)定排序的定義。穩(wěn)定性——若兩個記錄A和B的關鍵字值相等,但排序后A、B的先后次序保持不變,則稱這種排序算法是穩(wěn)定的?！舨迦肱判颉仓苯硬迦?、折半插入,索引表插入、希爾插入排序。插入排序的基本思想是：每步將一個待排序的對象,按其關鍵碼大小,插入到前面已經排好序的一組對象的適當位置上,直到對象全部插入為止。簡言之,邊插入邊排序,保證子序列中隨時都是排好序的。1>直接插入排序在已形成的有序表中線性查找,并在適當位置插入,把原來位置上的元素向后順移。時間效率：因為在最壞情況下,所有元素的比較次數(shù)總和為〔0＋1＋…＋n-1>→O<n2>。其他情況下也要考慮移動元素的次數(shù)。故時間復雜度為O<n2>空間效率：僅占用1個緩沖單元——O〔1算法的穩(wěn)定性：因為25*排序后仍然在25的后面——穩(wěn)定直接插入排序算法的實現(xiàn)：voidInsertSort<SqList&L>{//對順序表L作直接插入排序for<i=2;i<=L.length;i++>//假定第一個記錄有序{L.r[0]=L.r[i];j=i-1;//先將待插入的元素放入"哨兵"位置while〔L[0].key<L[j].key>{L.r[j+1]=L.r[j];j--;}//只要子表元素比哨兵大就不斷后移L.r[j+1]=L.r[0];//直到子表元素小于哨兵,將哨兵值送入//當前要插入的位置〔包括插入到表首}}折半插入排序既然子表有序且為順序存儲結構,則插入時采用折半查找定可加速。優(yōu)點：比較次數(shù)大大減少,全部元素比較次數(shù)僅為O<nlog2n>。時間效率：雖然比較次數(shù)大大減少,可惜移動次數(shù)并未減少,所以排序效率仍為O<n2>。空間效率：仍為O〔1穩(wěn)定性：穩(wěn)定若記錄是鏈表結構,用直接插入排序行否？答：行,而且無需移動元素,時間效率更高！但請注意：單鏈表結構無法實現(xiàn)"折半查找"表插入排序基本思想：在順序存儲結構中,給每個記錄增開一個指針分量,在排序過程中將指針內容逐個修改為已經整理〔排序過的后繼記錄地址。優(yōu)點：在排序過程中不移動元素,只修改指針。此方法具有鏈表排序和地址排序的特點表插入排序算法分析：①無需移動記錄,只需修改指針值。但由于比較次數(shù)沒有減少,故時間效率仍為O<n2>。②空間效率肯定低,因為增開了指針分量〔但在運算過程中沒有用到更多的輔助單元。③穩(wěn)定性：25和25*排序前后次序未變,穩(wěn)定。注：此算法得到的只是一個