自考02331數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(最終修訂)培訓(xùn)資料

1、自考02331數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(最終修訂)第一章概論1 .瑞士計(jì)算機(jī)科學(xué)家沃思提出：算法+數(shù)據(jù)Z§構(gòu)=程序.算法是對數(shù)據(jù)運(yùn)算的描述,而數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu).由此可見,程序設(shè)計(jì)的實(shí)質(zhì)是針對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個(gè)好的算法,而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu).2 .數(shù)據(jù)是信息的載體.數(shù)據(jù)元素是數(shù)據(jù)的根本單位.一個(gè)數(shù)據(jù)元素可以由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成,數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位.數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合.3 .數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素之間的相互關(guān)系,即數(shù)據(jù)的組織形式.數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)

2、的運(yùn)算數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),與數(shù)據(jù)元素的存儲結(jié)構(gòu)無關(guān),是獨(dú)立于計(jì)算機(jī)的.數(shù)據(jù)的邏輯結(jié)構(gòu)分類：線性結(jié)構(gòu)和非線性結(jié)構(gòu).線性表是一個(gè)典型的線性結(jié)構(gòu).棧、隊(duì)列、串等都是線性結(jié)構(gòu).數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu).數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲方式,稱為數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn),它依賴于計(jì)算機(jī)語言.數(shù)據(jù)的運(yùn)算.最常用的檢索、插入、刪除、更新、排序等.4 .數(shù)據(jù)的四種根本存儲方法：順序存儲、鏈接存儲、索引存儲、散列存儲(1)順序存儲：通常借助程序設(shè)計(jì)語言的數(shù)組描述.(2)鏈接存儲：通常借助于程序語言的指針來描述.(3)索引存儲：索引

3、表由假設(shè)干索引項(xiàng)組成.關(guān)鍵字是能唯一標(biāo)識一個(gè)元素的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合.(4)散列存儲：該方法的根本思想是：根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲地址.5 .算法必須滿足5個(gè)準(zhǔn)那么：輸入,0個(gè)或多個(gè)數(shù)據(jù)作為輸入；輸出,產(chǎn)生一個(gè)或多個(gè)輸出；有窮性,算法執(zhí)行有限步后結(jié)束；確定性,每一條指令的含義都明確；可行性,算法是可行的.算法與程序的區(qū)別：程序必須依賴于計(jì)算機(jī)程序語言,而一個(gè)算法可用自然語言、計(jì)算機(jī)程序語言、數(shù)學(xué)語言或約定的符號語言來描述.目前常用的描述算法語言有兩類：類Pascal和類G6 .評價(jià)算法的優(yōu)劣：算法的"正確性是首先要考慮的.此外,主要考慮如下三點(diǎn)： 執(zhí)行算法所消耗的時(shí)

4、間,即時(shí)間復(fù)雜性； 執(zhí)行算法所消耗的存儲空間,主要是輔助空間,即空間復(fù)雜性； 算法應(yīng)易于理解、易于編程,易于調(diào)試等,即可讀性和可操作性.以上幾點(diǎn)最主要的是時(shí)間復(fù)雜性,時(shí)間復(fù)雜度常用漸進(jìn)時(shí)間復(fù)雜度表示.7 .算法求解問題的輸入量稱為問題的規(guī)模,用一個(gè)正整數(shù)n表示.8 .常見的時(shí)間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)和階乘階0(n!).9 .一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所消耗的存儲空間,它是問題規(guī)模n的函數(shù),它包括存儲算法本身所占的存儲空

5、間、算法的輸入輸出數(shù)據(jù)所占的存儲空間和算法在運(yùn)行過程中臨時(shí)占用的存儲空間.第二章線性表1 .數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的,而運(yùn)算的具體實(shí)現(xiàn)是在存儲結(jié)構(gòu)上進(jìn)行的.2 .只要確定了線性表存儲的起始位置,線性表中任意一個(gè)元素都可隨機(jī)存取,所以順序表是一種隨機(jī)存取結(jié)構(gòu).3 .常見的線性表的根本運(yùn)算：置空表InitList(L)構(gòu)造一個(gè)空的線性表L.(2)求表長ListLength(L)求線性表L中的結(jié)點(diǎn)個(gè)數(shù),即求表長.(3)GetNode(L,i)取線性表L中的第i個(gè)元素.(4)LocateNode(L,x)在L中查找第一個(gè)值為x的元素,并返回該元素在L中的位置.假設(shè)L中沒有元素的值為x,那么返回0

6、值.(5)InsertList(L,i,x)在線性表L的第i個(gè)元素之前插入一個(gè)值為x的新元素,表L的長度加1.(6)DeleteList(L,i)刪除線性表L的第i個(gè)元素,刪除后表L的長度減1.4 .順序存儲方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法.順序表(SequentialList):用順序存儲方法存儲的線性表稱為順序表.順序表是一種隨機(jī)存取結(jié)構(gòu),順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰.順序表中結(jié)點(diǎn)ai的存儲地址：LOC(a)=LOC(a)+(i-1)*c1<i<n,5 .順序表上實(shí)現(xiàn)的根本運(yùn)算：(1)插入：該算法的平均時(shí)間復(fù)雜度是O(

7、n),即在順序表上進(jìn)行插入運(yùn)算,平均要移動一半結(jié)點(diǎn)(n/2).在第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動次數(shù)為n-i+1(2)刪除：順序表上做刪除運(yùn)算,平均要移動表中約一半的結(jié)點(diǎn)(n-1)/2,平均時(shí)間復(fù)雜度也是O(n).刪除第i個(gè)結(jié)點(diǎn)移動次數(shù)為n-i6 .采用鏈?zhǔn)酱鎯Y(jié)構(gòu)可以防止頻繁移動大量元素.一個(gè)單鏈表可由頭指針唯一確定,因此單鏈表可以用頭指針的名字來命名.生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=(ListNode*)malloc(sizeof(ListNode);/函數(shù)malloc分配一個(gè)類型為ListNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p);釋放p所指的結(jié)

8、點(diǎn)變量空間結(jié)點(diǎn)分量的訪問方法二：p->data和p->next指針變量p和結(jié)點(diǎn)變量*p的關(guān)系：指針變量p的值一一結(jié)點(diǎn)地址,結(jié)點(diǎn)變量*p的值一一結(jié)點(diǎn)內(nèi)容7 .建立單鏈表：(1) 頭插法建表：算法：p=(ListNode*)malloc(sizeof(ListNode);生成新結(jié)點(diǎn)p->data=ch;將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中p->next=head;head=p;心|(|-t、將靖在*1理i箕單轉(zhuǎn)和行郵i頭上(2) 尾插法建表：算法：p=(ListNode*)malloc(sizeof(ListNode);生成新結(jié)點(diǎn)p->data=ch;將讀入的數(shù)據(jù)放入新結(jié)

9、點(diǎn)的數(shù)據(jù)域中if(head=NULL)head=p;/新結(jié)點(diǎn)插入空表elserear->next=p;將新結(jié)點(diǎn)插到*r之后rear=p;尾指針指向新表尾(3)尾插法建帶頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn).它具有兩個(gè)優(yōu)點(diǎn)：1 .由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致,無須進(jìn)行特殊處理；2 .無論鏈表是否為空,其頭指針都是指向頭結(jié)點(diǎn)的非空指針(空表中頭結(jié)點(diǎn)的指針域空),因此空表和非空表的處理也就統(tǒng)一了.h自id頭結(jié)點(diǎn)開始白I"IJI、|二A*4Hi-頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該局部不存儲

10、信息.中可用于存放表長等附加信息.在有的應(yīng)用R-HI型表帶頭怙點(diǎn)的隼槌去具體算法：r=head;/尾指針初值也指向頭結(jié)點(diǎn)while(ch=getchar()!='n')s=(ListNode*)malloc(sizeof(ListNode);/生成新結(jié)點(diǎn)s->data=ch;/將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中r->next=s;r=s;r->next=NULL;/終端結(jié)點(diǎn)的指針域置空,或空表的頭結(jié)點(diǎn)指針域置空以上三個(gè)算法的時(shí)間復(fù)雜度均為O(n).8 .單鏈表上的查找：(帶頭結(jié)點(diǎn))(1)按結(jié)點(diǎn)序號查找：序號為0的是頭結(jié)點(diǎn).算法：p=head;j=0;/從頭結(jié)點(diǎn)開

11、始掃描while(p->next&&j<i)/順指針向后掃描,直到p->next為NULLi=j為止p=p->next;j+;if(i=j)returnp;/找到了第i個(gè)結(jié)點(diǎn)elsereturnNULL;/當(dāng)i<0或i>0時(shí),找不到第i個(gè)結(jié)點(diǎn)時(shí)間復(fù)雜度：在等概率假設(shè)下,平均時(shí)間復(fù)雜度為：為n/2=O(n)(2)按結(jié)點(diǎn)值查找：具體算法：ListNode*p=head->next;/從開始結(jié)點(diǎn)比擬.表非空,p初始值指向開始結(jié)點(diǎn)while(p&&p->data!=key)直至Up為NULL或p->data為key為

12、止p=p->next;/掃描下一結(jié)點(diǎn)returnp;/假設(shè)p=NULL那么查找失敗,否那么p指向值為key的結(jié)點(diǎn)時(shí)間復(fù)雜度為：O(n)9 .插入運(yùn)算：插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上,即插入到a,與a之間.博密上施入,一示,良s=(ListNode*)malloc(sizeof(ListNode);s->data=x;s->next=p->next;p->next=s;算法的時(shí)間主要消耗在查找結(jié)點(diǎn)上,故時(shí)間復(fù)雜度亦為O(n).10 .刪除運(yùn)算r=p->next;使r指向被刪除的結(jié)點(diǎn)aip->next=r->next;將ai從

13、鏈上摘下free(r);釋放結(jié)點(diǎn)ai的空間給存儲池算法的時(shí)間復(fù)雜度也是O(n).p指向被刪除的前一個(gè)結(jié)點(diǎn).鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算,無須移動結(jié)點(diǎn),僅需修改指針.11 .單循環(huán)鏈表一在單鏈表中,將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可.判斷空鏈表的條件是head=head->next;12 .僅設(shè)尾指針的單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是O(1).而表的操作常常是在表的首尾位置上進(jìn)行,因此,實(shí)用中多采用尾指針表示單循環(huán)鏈表.判斷空鏈表的條件為rear=rear->next;13 .循環(huán)鏈表：循環(huán)鏈表的特點(diǎn)是無須增加存

14、儲量,僅對表的鏈接方式稍作改變,即可使得表處理更加方便靈活.假設(shè)在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn),那么只需修改指針,無須遍歷,其執(zhí)行時(shí)間是O(1).具體算法：LinkListConnect(LinkListA,LinkListB)/假設(shè)A,B為非空循環(huán)鏈表的尾指針LinkListp=A->next;/保存A表的頭結(jié)點(diǎn)位置A->next=B->next->next;/B表的開始結(jié)點(diǎn)鏈接到A表尾free(B->next);/釋放B表的頭結(jié)點(diǎn)B->next=p;/returnB;/返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒有NULL指針.涉及遍歷操作時(shí),其終止條件就不再是像

15、非循環(huán)鏈表那樣判別p或p->next是否為空,而是判別它們是否等于某一指定指針,如頭指針或尾指針等.在單鏈表中,從一結(jié)點(diǎn)出發(fā),只能訪問到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn),無法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn).而在單循環(huán)鏈表中,從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn),這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn).向其直接前趨的指針域prior.29%P1的UH原總石14 .雙向鏈表：雙(向)鏈表中有兩條方向不同的鏈,即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外,還增加一個(gè)指雙鏈表由頭指針head惟一確定的.帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便.將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來,為雙(向)循環(huán)鏈表.15 .雙向鏈表的前插和刪除本結(jié)

16、點(diǎn)操作雙鏈表的前插操作voidDInsertBefore(DListNode*p,DataTypex)/在帶頭結(jié)點(diǎn)的雙鏈表中,將值為x的新結(jié)點(diǎn)插入*p之前,設(shè)pwNULLDListNode*s=malloc(sizeof(DListNode);/s->data=x;/s->prior=p->prior;/s->next=p;/p->prior->next=s;/p->prior=s;/雙鏈表上刪除結(jié)點(diǎn)*p自身的操作取以gI算除11.+ivoidDDeleteNode(DListNode*p)/在帶頭結(jié)點(diǎn)的雙鏈表中,刪除結(jié)點(diǎn)p->prior->

17、;next=p->next;/p->next->prior=p->prior;/free(p);/*p,設(shè)*p為非終端結(jié)點(diǎn)與單鏈表上的插入和刪除操作不同的是,在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針.上述兩個(gè)算法的時(shí)間復(fù)雜度均為O(1).16 .順序表和鏈表比擬時(shí)間性能：a、線性表：經(jīng)常性的查找；b、鏈?zhǔn)酱鎯Y(jié)構(gòu)：經(jīng)常插入刪除操作；空間性能：a、對數(shù)據(jù)量大小事先能夠知道的用線性表；b、數(shù)據(jù)量變化較大的用鏈?zhǔn)酱鎯Y(jié)構(gòu).存儲密度越大,存儲空間的利用率越高.顯然,順序表的存儲密度是1,鏈表的存儲密度肯定小于1.第三章棧和隊(duì)列1 .棧稱為后進(jìn)先出(LastInFirst

18、Out)的線性表,簡稱為LIFO表.棧是運(yùn)算受限的線性表,順序棧也是用數(shù)組表示的.進(jìn)棧操作：進(jìn)棧時(shí),需要將S->top力口1,S->top=StackSize-1表示棧滿"上溢"現(xiàn)象-當(dāng)棧滿時(shí),再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象.L|3i11退棧操作：退棧時(shí),需將S->top減1,S->top<0表示空棧"下溢"現(xiàn)象-當(dāng)棧空時(shí),做退棧運(yùn)算產(chǎn)生的溢出現(xiàn)象.下溢是正?，F(xiàn)象,常用作程序限制轉(zhuǎn)移的條件.空棧時(shí)棧頂指針不能是0,只能是-1.兩個(gè)棧共享同一存儲空間：當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí),可以將兩個(gè)棧的棧底分別設(shè)在順序存儲空間的兩端,讓兩

19、個(gè)棧頂各自向中間延伸.當(dāng)一個(gè)棧中的元素較多而棧使用的空間超過共享空間的一半時(shí),只要另一個(gè)棧的元素不多,那么前者就可以占用后者的局部存儲空間.當(dāng)Top1=Top2-1時(shí),棧滿2 .為了克服順序存儲分配固定空間所產(chǎn)生的溢出和空間浪費(fèi)問題.可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲棧.鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表.棧頂指針就是鏈表的頭指針.順序隊(duì)列的根本操作鏈棧中的結(jié)點(diǎn)是動態(tài)分配的,所以可以不考慮上溢,無須定義StackFull運(yùn)算棧的一個(gè)重要應(yīng)用是實(shí)現(xiàn)遞歸,直接調(diào)用自己或間接調(diào)用自己的函數(shù).3 .隊(duì)列(Queue)是只允許在一端進(jìn)行插入,而在另一端進(jìn)行刪除的運(yùn)算受限的線性表.允許刪除的一端稱為隊(duì)頭(Fro

20、nt),允許插入的一端稱為隊(duì)尾(Rear),當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列,隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表,簡稱為FIFO表.隊(duì)列的順序存儲結(jié)構(gòu)稱為順序隊(duì)列,順序隊(duì)列實(shí)際上是一個(gè)受限的線性表.入隊(duì)時(shí)：將新元素插入rear所指的位置,然后將rear加1.出隊(duì)時(shí)：刪去front所指的元素,然后將front加1并返回被刪元素.當(dāng)頭尾指針相等時(shí),隊(duì)列為空.在非空隊(duì)列里,頭指針始終指向隊(duì)頭元素,而隊(duì)尾指針始終指向隊(duì)尾元素的下一位置.而棧頂指針指向棧頂元素.4.循環(huán)隊(duì)列：為充分利用數(shù)組空間,克服上溢,可將數(shù)組空間想象為一個(gè)環(huán)狀空間,并稱這種環(huán)狀數(shù)組表示的隊(duì)列為循環(huán)隊(duì)列.循環(huán)隊(duì)列

21、中進(jìn)行出隊(duì)、入隊(duì)操作時(shí),頭尾指針仍要加1,朝前移動.只不過當(dāng)頭尾指針指向向量上界(QueueSize-1)時(shí),其加1操作的結(jié)果是指向向量的下界0.這種循環(huán)意義下的加1操作可以描述為：方法一：if(i+1=QueueSize)i=0;/i表示front或rearelsei+;方法二-利用"模運(yùn)算"i=(i+1)%QueueSize;循環(huán)隊(duì)列中,由于入隊(duì)時(shí)尾指針向前追趕頭指針；出隊(duì)時(shí)頭指針向前追趕尾指針,造成隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等.因此,無法通過條件Q.front=Q.rear來判別隊(duì)列是"空"還是"滿".解決這個(gè)問題的方法至少有三種

22、：另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿；設(shè)置一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)(即隊(duì)列長度).少用一個(gè)元素的空間.約定入隊(duì)前,測試尾指針在循環(huán)意義下加1后是否等于頭指針,假設(shè)相等那么認(rèn)為隊(duì)列滿即尾指針Q.rear所指的單元始終為空.循環(huán)隊(duì)列操作演示人隊(duì)無第F出隊(duì)無界疝室兒隊(duì)來作電仃串.個(gè)無奈皿石斯耳隊(duì)列的凡播竹儂“鼎括向F喬規(guī)中兀,入鼠.重新7T始O出M5 .循環(huán)隊(duì)列的根本運(yùn)算：置隊(duì)空：Q->front=Q->rear=0;判隊(duì)空：returnQ->rear=Q->front;判隊(duì)滿：return(Q->rear+1)%QueueSize=Q->front;入隊(duì)Q

23、->dataQ->rear=x;/新元素插入隊(duì)尾Q->rear=(Q->rear+1)%QueueSize;出隊(duì)temp=Q->dataQ->front;Q->front=(Q->front+1)%QueueSize;/循環(huán)意義下的頭指針加1returntemp;取隊(duì)頭元素returnQ->dataQ->front;6 .隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊(duì)列.它是限制僅在表頭刪除和表尾插入的單鏈表.為了簡化處理,在隊(duì)頭結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn),并設(shè)隊(duì)頭指針指向此結(jié)點(diǎn).嵋四電-的隊(duì)-.一FttmtI八|1front|a國>宏認(rèn)阿砧>

24、作空認(rèn)列i.IAEmMl鏈隊(duì)列的根本運(yùn)算：(帶頭結(jié)點(diǎn))(1) 構(gòu)造空隊(duì)：Q->rear=Q->front;Q->rear->next=NULL;(2) 判隊(duì)空：returnQ->rear=Q->front;(3) 入隊(duì)：QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申請新結(jié)點(diǎn)p->data=x;p->next=NULL;Q->rear->next=p;/*p鏈到原隊(duì)尾結(jié)點(diǎn)后Q->rear=p;/隊(duì)尾指針指向新的尾(4) 出隊(duì)：當(dāng)隊(duì)列長度大于1時(shí),只需修改頭結(jié)點(diǎn)指針,尾指針不變

25、s=Q->front->next;Q->front->next=s->next;x=s->data;free(s);returnx;當(dāng)隊(duì)列長度等于1時(shí),不僅要修改頭結(jié)點(diǎn)指針,還要修改尾指針s=Q->front->next;Q->front->next=NULL;Q->rear=Q->front;x=s->data;free(s);returnx;(5)取隊(duì)頭元素：returnQ->front->next->data;由于有頭結(jié)點(diǎn),所以用了next和鏈棧類似,無須考慮判隊(duì)滿的運(yùn)算及上溢.在出隊(duì)算法中,

26、一般只需修改隊(duì)頭指針.但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾,故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針,且刪去此結(jié)點(diǎn)后隊(duì)列變空.7.用計(jì)算機(jī)來處理計(jì)算算術(shù)表達(dá)式問題,首先要解決的問題是如何將人們習(xí)慣書寫的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式.第四章多維數(shù)組和廣義表1 .數(shù)組的順序存儲方式：一般采用順序存儲方法表示數(shù)組.(1) 7f順序a11,a12,a1n,a21,a22,a2n,am1,am2,amn(2)歹順a11,a21,am1,a12,a22,am2,a1n,a2n,amnPascal和C語言是按行優(yōu)先順序存儲的,而Fortran語言是按列優(yōu)先順序存儲的.按行優(yōu)先順序存儲的二維數(shù)組4n地址計(jì)算公式

27、LOC(aj)=LOC(an)+(i-1)Xn+j-1Xd(注：此公式下界為1,如下界為0,那么公式變?yōu)閕xn+j)按列優(yōu)先順序存儲的二維數(shù)組Amn地址計(jì)算公式LOC(a)=LOC(an)+(j-1)xm+i-1xd(注：此公式下界為1,如下界為0,那么公式變?yōu)閖xm+i)按行優(yōu)先順序存儲的三維數(shù)組Amnp地址計(jì)算公式LOC(ajk)=LOC(a111)+(i-1)XnXp+(j-1)xp+k-1xd(注：此公式下界為1,如下界為0,那么公式變?yōu)閕xnxp+jxp+k)2 .為了節(jié)省存儲空間,可以對矩陣中有許多值相同或值為零的元素的矩陣,采用壓縮存儲.特殊矩陣是指相同值的元素或零元素在矩陣中的

28、分布有一定的規(guī)律.常見的有對稱矩陣、三角矩陣.(1)對稱矩陣在一個(gè)n階方陣A中,假設(shè)元素滿足下述性質(zhì)：aij=aji0<i,j<n-1稱為n階對稱矩陣,它的元素是關(guān)于主對角線對稱的,所以只需要存儲矩陣上三角或下三角元素即可,讓兩個(gè)對稱的元素共享一個(gè)存儲空間.矩陣元素au和數(shù)組元素sa【k】之間的關(guān)系是k=ix(i+1)/2+ji0<k<n(n+1)/2-1k=jx(j+1)/2+iivj0<k<n(n+1)/2-1對稱矩陣的地址計(jì)算公式：LOC(aj)=LOC(sa0)+Ix(I+1)/2+JXd,其中I=max(i,j),J=min(i,j)(2)三角矩陣

29、：以主對角線劃分,三角矩陣有上三角和下三角兩種.上三角矩陣是指它的下三角(不包括主角線)中的元素均為常數(shù)c或零；下三角矩陣的主對角線上方均為常數(shù)c或零.一般情況,三角矩陣的常數(shù)c均為零.三角矩陣的壓縮存儲：三角矩陣中的重復(fù)元素c可共享一個(gè)存儲空間,其余的元素正好有nX(n+1)/2個(gè),因此,三角矩陣可壓縮存儲在一維數(shù)組san(n+1)/2+1中,其中c存放在數(shù)組的最后一個(gè)元素中.上三角矩陣中aij和sak之間的對應(yīng)關(guān)系k=ix(2n-i+1)/2+j-i當(dāng)iwjk=nX(n+1)/2當(dāng)i>j下三角矩陣中aij和sak之間的對應(yīng)關(guān)系k=iX(i+1)/2+j當(dāng)iRjk=nX(n+1)/2當(dāng)

30、ivj三角矩陣的壓縮存儲結(jié)構(gòu)是隨機(jī)存取結(jié)構(gòu).3 .稀疏失I陣：設(shè)矩陣Amn中有s個(gè)非零元素,假設(shè)s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù),那么稱A為稀疏矩陣.為了節(jié)省存儲單元,可用壓縮存儲方法只存儲非零元素.由于非零元素的分布一般是沒有規(guī)律的,因此在存儲非零元素的同時(shí),還必須存儲非零元素所在的行、列位置,所以可用三元組(i,j,aij)來確定非零元素.稀疏矩陣進(jìn)行壓縮存儲通常有兩類方法：順序存儲(三元組表)和鏈?zhǔn)酱鎯?十字鏈表).稀疏矩陣的壓縮存儲會失去隨機(jī)存取功能.VIh.'H*ridtilMaxSiM1韓或矩陳兒和它的二兀插？4 .廣義表是線性表的推廣,又稱列表.廣義表是n(n>0)個(gè)元素a

31、i,a2,ai,an的有限序列.其中ai或者是原子或者是一個(gè)廣義表.廣義表通常用圓括號括起來,用逗號分隔其中的元素.為了區(qū)分原子和廣義表,書寫時(shí)用大寫字母表示廣義表,用小寫字母表示原子.假設(shè)廣義表Ls非空(n>1),那么ai是LS的表頭,其余元素組成的表(ai,a2,an)稱為Ls的表尾.廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個(gè)表展開后所含括號的層數(shù)稱為廣義表的深度.19.廣義表是一種多層次的線性結(jié)構(gòu),實(shí)際上這就是一種樹形結(jié)構(gòu).廣義表的兩個(gè)特殊的根本運(yùn)算：取表頭head(Ls)和取表尾tail(Ls).任何一個(gè)非空廣義表的表頭可以是原子,也可以是子表,而其表尾必定是子表.head=(

32、a,b)=a,tail(a,b)=(b)對非空表A和(y),也可繼續(xù)分解.注意：廣義表()和()不同.前者是長度為0的空表,對其不能做求表頭和表尾的運(yùn)算；而后者是長度為l的由空表作元素的廣義表,可以分解得到的表頭和表尾均是空表().廣義表是一種有層次的非線性結(jié)構(gòu),通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu),每個(gè)元素用一個(gè)結(jié)點(diǎn)表示,結(jié)點(diǎn)由3個(gè)域構(gòu)成,其中一個(gè)是tag標(biāo)志位,用來區(qū)分結(jié)點(diǎn)是原子還是子表,當(dāng)tag為零時(shí)結(jié)點(diǎn)是子表,第二個(gè)域?yàn)閟link,用以存放子表的地址；當(dāng)tag為1時(shí)結(jié)點(diǎn)是原子,第二個(gè)域?yàn)閐ata,用以存放元素值.第五章樹和二叉樹1.樹的表示法：最常用的是機(jī)形圖表示法；還有3種嵌套集合、凹形、廣義表.樹

33、結(jié)構(gòu)的根本術(shù)語(1)結(jié)點(diǎn)的度(Degree)樹中的一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度(Degree).一棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù).度為零的結(jié)點(diǎn)稱為葉子(Leaf)或終端結(jié)點(diǎn).度不為零的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn).除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn).根結(jié)點(diǎn)又稱為開始結(jié)點(diǎn).(2)路徑(path)假設(shè)樹中存在一個(gè)結(jié)點(diǎn)序列k1,k2,ki,使得ki是ki+1的雙親(1Wi<j),那么稱該結(jié)點(diǎn)序列是從kl到kj的一條路徑(Path).一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過的所有結(jié)點(diǎn),而一個(gè)結(jié)點(diǎn)的子孫那么是以該結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn).結(jié)點(diǎn)的層數(shù)(Level)從根起算：根的層數(shù)為1

34、,其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1.雙親在同一層的結(jié)點(diǎn)互為堂兄弟.樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度(Height)或深度(Depth).假設(shè)將樹中每個(gè)結(jié)點(diǎn)的各子樹看成是從左到右有次序的(即不能互換),那么稱該樹為有序樹(OrderedTree);否那么稱為無序樹(UnoderedTree).假設(shè)不特別指明,一般討論的樹都是有序樹.森林(Forest)是m(nr>0)棵互不相交的樹的集合.樹和森林的概念相近.刪去一棵樹的根,就得到一個(gè)森林；反之,加上一個(gè)結(jié)點(diǎn)作樹根,森林就變?yōu)橐豢脴?3.二叉樹與度數(shù)為2的有序樹不同：在有序樹中,雖然一個(gè)結(jié)點(diǎn)的孩子之間是有左右次序的,但是假設(shè)該結(jié)點(diǎn)只有一

35、個(gè)孩子,就無須區(qū)分其左右次序.而在二叉樹中,即使是一個(gè)孩子也有左右之分.二叉樹的性質(zhì)：性質(zhì)1二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為2i-1(i>1)o例如5層的二叉樹,第5層上的結(jié)點(diǎn)數(shù)目最多為24=16性質(zhì)2深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k>1).例如深度為5的二叉樹,至多有25-1=31個(gè)結(jié)點(diǎn)性質(zhì)3在任意-棵二叉樹中,假設(shè)終端結(jié)點(diǎn)的個(gè)數(shù)為n.,度為2的結(jié)點(diǎn)數(shù)為n2,那么山=山+1.例如一棵深度為4的二叉樹a,其終端結(jié)點(diǎn)數(shù)no為8,度為2的結(jié)點(diǎn)樹為7,那么8=7+1,廿廿1成立b其終端結(jié)點(diǎn)數(shù)no為6,度為2的結(jié)點(diǎn)樹為5,那么6=5+1,n°=n2+1成立IIJKtUkU1

36、1IJKLH1JKL如3輛.X構(gòu)3龍金一又料上】*兌至二£樹背葉航奔為父田滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二又樹稱為滿二叉樹.滿二叉樹的特點(diǎn)：1每一層上的結(jié)點(diǎn)數(shù)都到達(dá)最大值.即對給定的高度,它是具有最多結(jié)點(diǎn)數(shù)的二叉樹.2滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn),每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹,且樹葉都在最下一層上.完全二叉樹：假設(shè)一棵深度為k的二叉樹,其前k-1層是一棵滿二叉樹,而最下面一層上的結(jié)點(diǎn)都集中在該層最左邊的假設(shè)干位置上,那么此二叉樹稱為完全二叉樹.特點(diǎn)：1滿二叉樹是完全二叉樹,完全二叉樹不一定是滿二叉樹.2在滿二叉樹的最下一層上,從最右邊開始連續(xù)刪去假設(shè)干結(jié)點(diǎn)后得到的

37、二叉樹仍然是一棵完全二叉樹.3在完全二叉樹中,假設(shè)某個(gè)結(jié)點(diǎn)沒有左孩子,那么它一定沒有右孩子,即該結(jié)點(diǎn)必是葉結(jié)點(diǎn).性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為.?logn?+1或？10gn+1?例,具有100個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：？lg100?+1=7,26=6427=128所以？lg100?=6,?lg100+1?=74 .完全二叉樹的編號特點(diǎn)：完全二叉樹中除最下面一層外,各層都充滿了結(jié)點(diǎn).每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié)點(diǎn)個(gè)數(shù)的2倍.從一個(gè)結(jié)點(diǎn)的編號就可推得其雙親,左、右孩子等結(jié)點(diǎn)的編號.編號從0開始假設(shè)i=0,那么qi為根結(jié)點(diǎn),無雙親；否那么,qi的雙親編號為？i-1/2?.假設(shè)2i+1&l

38、t;n,那么qi的左孩子的編號是2i+1;否那么,qi無左孩子,即q必定是葉子.假設(shè)2i+2<n,那么qi的右孩子的編號是2i+2;否那么,qi無右孩子.對于完全二叉樹而言,使用順序存儲結(jié)構(gòu)既簡單又節(jié)省存儲空間.但對于一般二叉樹來說,采用順序存儲時(shí),為了使用結(jié)點(diǎn)在數(shù)組中的相對位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系,就必須增加一些虛結(jié)點(diǎn)使其成為完全二叉樹的形式.5 .鏈?zhǔn)酱鎯Y(jié)構(gòu)：二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子.用鏈接方式存儲二叉樹時(shí),每個(gè)結(jié)點(diǎn)除了存儲結(jié)點(diǎn)本身的數(shù)據(jù)外,還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild,分別指向該結(jié)點(diǎn)的左孩子和右孩子.結(jié)點(diǎn)的結(jié)構(gòu)為：叵巫二叉鏈表是一種常用的二叉樹存儲結(jié)構(gòu).

39、建立二叉鏈表方法：a、按廣義表方法,靠近左括號的結(jié)點(diǎn)是在左子樹上,而逗號右邊結(jié)點(diǎn)是在右子樹上.b、按完全二叉樹的層次順序建立結(jié)點(diǎn).具有n個(gè)結(jié)點(diǎn)的二叉鏈表中,共有2n個(gè)指針域.其中有n-1個(gè)用來指示結(jié)點(diǎn)的左、右孩子,其余的n+1個(gè)為空.二叉樹遍歷算法中的遞歸終止條件是二叉樹為空.中序遍歷的遞歸算法定義：1遍歷左子樹；2訪問根結(jié)點(diǎn)；3遍歷右子樹.先序遍歷的遞歸算法定義：1訪問根結(jié)點(diǎn)；2遍歷左子樹；3遍歷右子樹.后序遍歷得遞歸算法定義：1遍歷左子樹；2遍歷右子樹；3訪問根結(jié)點(diǎn).遞歸工作棧中包括兩項(xiàng)：一項(xiàng)為哪一項(xiàng)遞歸調(diào)用的語句編號,另一項(xiàng)那么是指向根結(jié)點(diǎn)的指針.一棵二叉樹的前序和中序遍歷序列或中序和后

40、序遍歷序列,可唯一確定一棵二叉樹.具體方法如下：首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根,然后根據(jù)中序遍歷序列確定各子樹根的左右子樹.6 .線索二叉樹：n個(gè)結(jié)點(diǎn)的二叉鏈表必定存在n+1個(gè)空指針域,可以利用這些空指針域,存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針,這種指向前驅(qū)和后繼結(jié)點(diǎn)的指針稱為"線索",這種加上線索的二叉鏈表稱為線索鏈表,相應(yīng)的二叉樹稱為線索二叉樹ThreadedBinaryTree.線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)：圖中的實(shí)線表示指針,虛線表示線索.線索二叉樹中,一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1.7 .二叉樹的線索化：把對一棵二叉線索鏈表

41、結(jié)構(gòu)中所有結(jié)點(diǎn)的空指針域根據(jù)某種遍歷次序加線索的過程稱為線索化.n個(gè)結(jié)點(diǎn)的二叉樹,線索化的算法時(shí)間復(fù)雜度和中序遍歷算法一樣,遞歸過程中對每結(jié)點(diǎn)僅做一次訪問.因此對于為O(n).8 .樹、森林到二叉樹的轉(zhuǎn)換：樹中每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子(長子)和一個(gè)右鄰的兄弟.將樹轉(zhuǎn)換成二叉樹：在所有兄弟結(jié)點(diǎn)之間加一道連線；對每個(gè)結(jié)點(diǎn),除了保存與其長子的連線外,去掉該結(jié)點(diǎn)與其它孩子的連線.由于樹根沒有兄弟,故樹轉(zhuǎn)化為二叉樹后,二叉樹的根結(jié)點(diǎn)的右子樹必為空.IlCihl第二步；對5個(gè)結(jié)點(diǎn),除了保甯.其的長了的在線外1去押談結(jié)點(diǎn).4他獨(dú)子的連續(xù)將一個(gè)森林轉(zhuǎn)換為二叉樹將森林中的每棵樹轉(zhuǎn)化成二叉樹,然后再將二叉

42、樹的根節(jié)點(diǎn)看做兄弟連在一起,形成一棵二叉樹第二步!將國二父四的根結(jié).點(diǎn)現(xiàn)為兄弟從左存右連住起.就形成了一株一支樹9.二叉樹到樹、森林的轉(zhuǎn)換：方式是：假設(shè)二叉樹中結(jié)點(diǎn)x是雙親y的左孩子,那么把x的右孩子,右孩子的右孩子,都與y用連線連起來,最后去掉所有雙親到右孩子的連線.閏月H化亨£國3J樹4依史&110.樹的存儲結(jié)構(gòu)：1 .雙親表示法：雙親鏈表表示法利用樹中每個(gè)結(jié)點(diǎn)的雙親唯一性,在存儲結(jié)點(diǎn)信息的同時(shí),為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針parent,惟一地表示任何-棵樹.1雙親鏈表表示法的實(shí)現(xiàn)分析：E和F所在結(jié)點(diǎn)的雙親域是1,它們的雙親結(jié)點(diǎn)在向量中的位置是1,即B是它們的雙親.

43、注意：根無雙親,其parent域?yàn)?1.雙親鏈表表示法中指針parent向上鏈接,適合求指定結(jié)點(diǎn)的雙親或祖先包括根；求指定結(jié)點(diǎn)的孩子或其它后代時(shí),可能要遍歷整個(gè)數(shù)組.2 .孩子鏈表法：孩子鏈表表示法是為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈表,并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中.閣反IT局科比為：義擁5中四的西予植*A注意：孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們在向量空間的序號.與雙親鏈表表示法相反,孩子鏈表表示便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算,但不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算.將雙親鏈表表示法和孩子鏈表表示法結(jié)合起來,可形成雙親孩子鏈表表示法.3 .孩子兄弟表示法：在存儲結(jié)點(diǎn)信息的同時(shí),附加兩個(gè)分別指

44、向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域,即可得樹的.孩子兄弟鏈表表示.!.注意：|'這種存儲結(jié)構(gòu)的最大優(yōu)點(diǎn)是：它和二叉樹的二叉鏈mbi山二hjurn區(qū)口耳表表示完全一樣.可利用二叉樹的算法來實(shí)現(xiàn)對樹的操|(zhì)愕人it用妙化為二文樹S中軻iWDtr把協(xié)位收11.樹的遍歷：一般都只給出兩種次序遍歷樹的方法：前序先根次序遍歷和后序后根次序遍歷.前序遍歷一棵樹等價(jià)于前序遍歷該樹對應(yīng)的二叉樹后序遍歷一棵樹等價(jià)于中序遍歷該樹對應(yīng)的二叉樹.對下面a圖中所不'的森林進(jìn)行前序遍歷和后序遍歷,那么得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE而b圖所示二叉樹的前序序列和中序

45、序列也分別為ABCDEFIGJHBDCAIFJGHE興林削河出m.X料前序遍歷森林等同于前序遍歷該森林對應(yīng)的二叉樹后序遍歷森林等同于中序遍歷該森林對應(yīng)的二叉樹12 .從根結(jié)點(diǎn)到某結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長度,樹種所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度.帶權(quán)路徑長度WPL小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹.哈夫曼樹不一定是二叉樹.哈夫曼樹又稱為最優(yōu)樹,是一類帶權(quán)路徑長度最短的樹.完全二叉樹就是這種路徑長度最短的二叉樹. 只有葉結(jié)點(diǎn)上的權(quán)值均相同時(shí),完全二叉樹一定是最優(yōu)二叉樹,否那么完全二叉樹不一定是最優(yōu)二叉樹. 最優(yōu)二叉樹中,權(quán)越大的葉子離根越近.最優(yōu)

46、二叉樹的形態(tài)不唯一,wplM小.13 .哈夫曼算法：根本思想是：(1)根據(jù)給定的n個(gè)權(quán)值w,wz,wn構(gòu)成n棵二叉樹的森林F=Ti,T2,Tn,其中每棵二叉樹Ti中都只有一個(gè)權(quán)值為w的根結(jié)點(diǎn),其左右子樹均空.(2)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹(當(dāng)這樣的樹不止兩棵樹時(shí),可以從中任選兩棵),將這兩棵樹合并成一棵新樹,為了保證新樹仍是二叉樹,需要增加一個(gè)新結(jié)點(diǎn)作為新樹的根,并將所選的兩棵樹的根分別作為新根的左右孩子(誰左,誰右無關(guān)緊要),將這兩個(gè)孩子的權(quán)值之和作為新樹根的權(quán)值.(3)對新的森林F重復(fù)(2),直到森林F中只剩下一棵樹為止.這棵樹便是哈夫曼樹.注意：初始森林中的n棵二叉樹,每棵樹

47、有一個(gè)孤立的結(jié)點(diǎn),它們既是根,又是葉子n個(gè)葉子的哈夫曼樹要經(jīng)過n-1次合并,產(chǎn)生n-1個(gè)新結(jié)點(diǎn).最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn).哈夫曼樹是嚴(yán)格的二叉樹,沒有度數(shù)為1的分支結(jié)點(diǎn).14 .哈夫曼編碼：數(shù)據(jù)壓縮過程稱為編碼,反之,解壓縮的過程稱為解碼.設(shè)計(jì)一種長短不等的編碼,那么必須保證任一字符的編碼都不是另一個(gè)字符編碼的前綴,這種編碼稱為前綴編碼.可以利用二叉樹來設(shè)計(jì)二進(jìn)制的前綴編碼,其左分支表示字符0,右分支表示字符1,那么以根結(jié)點(diǎn)到葉結(jié)點(diǎn)路徑上的分支字符組成的串作為該葉節(jié)點(diǎn)的字符編碼.因此設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼,就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹,由哈夫曼樹求得的

48、編碼就是哈夫曼編碼.譯碼過程是從樹根結(jié)點(diǎn)出發(fā),逐個(gè)讀入電文中的二進(jìn)制碼.第六章圖1.圖G由兩個(gè)集合構(gòu)成,頂點(diǎn)集合和邊集合,也可以圖G只有頂點(diǎn)而沒有邊.用尖括號表示圖的有向邊<vi,vj>,有向邊又稱為弧,起點(diǎn)稱為弧尾,終點(diǎn)稱為弧頭.無向圖的頂點(diǎn)對用圓括號表示(Vi,Vj).在無向圖中,稱Vi和Vj相鄰接,在有向圖中稱頂點(diǎn)Vi鄰接到Vj,頂點(diǎn)Vj鄰接于Vi在無向圖中,n的取值范圍是0-n(n-1)/2,將具有n(n-1)/2條邊的無向圖稱為無向完全圖.在有向圖中,n的取值范圍是0-n(n-1),將具有n(n-1)條邊的有向圖稱為有向完全圖.無向圖中,頂點(diǎn)的度定義為以該頂點(diǎn)為一個(gè)端點(diǎn)的

49、邊的數(shù)目,有向圖的度等于出度和入度之和.在無向圖中,任意兩頂點(diǎn)都有路徑,那么稱兩頂點(diǎn)連通.假設(shè)圖G中的任意兩個(gè)頂點(diǎn)都連通,稱G為連通圖.無向圖的極大連通子圖稱為連通分量,顯然,任何連通圖的連通分量只有一個(gè),即其自身,而非連通的無向圖有多個(gè)連通分量.在有向圖中,圖G中任意兩頂點(diǎn)連通,稱為強(qiáng)連通圖,極大連通子圖稱為強(qiáng)連通分量.假設(shè)在一個(gè)圖的每條邊上標(biāo)上某種數(shù)值,該數(shù)值稱為該邊的權(quán).邊上帶權(quán)的圖稱為帶權(quán)圖,帶權(quán)的連通圖稱為網(wǎng)絡(luò).2.圖的存儲結(jié)構(gòu)：鄰接矩陣和鄰接表表示法.圖的頂點(diǎn)編號從0開始.鄰接矩陣表示法：<切、)>或“1、)是邊,那么值為1,不是邊那么值為0.無向圖的鄰接矩陣是按主對角

50、線對稱的.假設(shè)G是帶權(quán)圖,只要把1換成相應(yīng)邊上的權(quán)值即可,0的位置上可以不動或?qū)⑵鋼Q成無窮大表示.無向圖的鄰接矩陣表示法可以僅存儲主對角線以下的元素,時(shí)間復(fù)雜度為O(n2)鄰接表表示法：鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu).將無向圖的鄰接表稱為邊表,將有向圖的鄰接表稱為出邊表,將鄰接表的表頭向量稱為頂點(diǎn)表.假設(shè)無向圖有n個(gè)頂點(diǎn)和e條邊,那么它的鄰接表共有n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn).建立鄰接表的時(shí)間復(fù)雜度是O(n+e).圖的鄰接表表示不是唯一的,這是由于在每個(gè)頂點(diǎn)的鄰接表中,各邊結(jié)點(diǎn)的鏈接次序可以是任意的,其具體鏈接次序與邊的輸入次序和生成算法有關(guān).3 .圖的遍歷：遍歷圖的算法是求解圖的連通性、圖的拓?fù)渑?/p>

51、序等算法的根底.圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法.深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷.按訪問頂點(diǎn)的先后次序得到的頂點(diǎn)序列稱為圖的深度優(yōu)先遍歷序列,或簡稱為DFS序歹U.共需要搜索n2個(gè)矩陣元素,時(shí)間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(n+e).G無向用帽4g5的旗度優(yōu)先搜索理歷過慳示意廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷,先被訪問的頂點(diǎn),其鄰接點(diǎn)也先被訪問,就是先進(jìn)先出.時(shí)間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(n+e),空間復(fù)雜度都是O(n).4 .生成樹是連通圖的包含圖中所有頂點(diǎn)的一個(gè)極小連通子圖,一個(gè)圖的極小連通子圖恰為一個(gè)無回路的連通

52、圖,也就是說,假設(shè)圖中任意添加一條邊,就會出現(xiàn)回路,假設(shè)去掉任意一條邊,都會使之成為非連通圖.因此,一個(gè)具有n個(gè)頂點(diǎn)的生成機(jī)有且僅有n-1條邊,但有n-1條邊的圖不一定是生成樹,同一個(gè)圖可以有不同的生成樹.生成樹定義為：假設(shè)從圖的某頂點(diǎn)出發(fā),可以系統(tǒng)的訪問到圖的所有頂點(diǎn),那么遍歷時(shí)經(jīng)過的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖,稱為該圖的生成樹.最小生成樹：圖的生成樹不唯一,把權(quán)值最小的生成樹稱為最小生成樹(MST.構(gòu)造最小生成樹的算法：普里姆Prim算法的時(shí)間復(fù)雜度為O(n2)與網(wǎng)中邊數(shù)無關(guān)適于稠密圖.克魯斯卡爾Kruskal算法的時(shí)間復(fù)雜度為O(eloge),主要取決于邊數(shù),較適合于稀疏圖.【例63】

53、利用普里姆算法,給山求圖6.171)所示的無向網(wǎng)絡(luò)的最小生成樹的過程.5 .最短路徑：Dijkstra迪杰斯特拉算法,提出了按路徑長度遞增的順序產(chǎn)生諸頂點(diǎn)的最短路徑算法.拓?fù)渑判颍鹤庸こ谭Q為活動,頂點(diǎn)代表活動,有向邊代表活動的先后關(guān)系.這樣的有向無環(huán)圖DAG稱為頂點(diǎn)活動網(wǎng),簡稱為AO颯.將有向無環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列,假設(shè)<u,v>CE(G),那么在線性序列u在v之前,這種線性序列稱為拓?fù)湫蛄?由AOM構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判?檢測的方法是：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)湫蛄?假設(shè)網(wǎng)中所有頂點(diǎn)都在他的拓?fù)湫蛄兄?那么AO颯必定不存在環(huán).AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?拓?fù)渑?/p>

54、序的描述思想：a、在有向圖中選一個(gè)沒有前趨(入度為零)的頂點(diǎn),且輸出之.b、從有向圖中刪除該頂點(diǎn)及其與該頂點(diǎn)有關(guān)的所有邊.c、重復(fù)上述步驟,直到全部頂點(diǎn)都已輸出或圖中剩余的頂點(diǎn)中沒有前趨頂點(diǎn)為止.d、輸出剩余的無前趨結(jié)點(diǎn).拓?fù)渑判驅(qū)嶋H上是對鄰接表表示的圖G進(jìn)行遍歷的過程.時(shí)間復(fù)雜度是O(n+e).圖6J2迪杰斯特拉算法求圖621的單源最短路徑示意圖第七章排序1 .如果待排序文件中存在多個(gè)關(guān)鍵字相同的記錄,經(jīng)過排序后,這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變,該排序方法是穩(wěn)定的；反之,那么是不穩(wěn)定的.排序在內(nèi)存中處理,不涉及數(shù)據(jù)的內(nèi)外存交換,稱為內(nèi)部排序,反之為外部排序.內(nèi)部排序又分為五類

55、：插入、選擇、交換、歸并和分配排序.在排序過程中需進(jìn)行兩種操作：比擬兩個(gè)關(guān)鍵字的大小、改變指向記錄的指針或移動記錄本身,而待排序記錄的存儲形式一般有三種：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)和輔助表.評價(jià)排序算法的標(biāo)準(zhǔn)：執(zhí)行算法需要的時(shí)間,以及算法所需要的附加空間.還有算法本身的復(fù)雜度.排序的時(shí)間開銷,一般情況下可用算法中關(guān)鍵字的比擬次數(shù)和記錄的移動次數(shù)來衡量.2 .插入排序：每次將一個(gè)待排序記錄按其關(guān)鍵字大小插入到前面已排好序的文件中的適當(dāng)位置.直接插入排序：每次從無序區(qū)取出第一個(gè)元素把它插入到有序區(qū)的適當(dāng)位置,使之成為新的有序區(qū),經(jīng)過n-1次插入后完成.算法中R0作用：保存Ri副本,監(jiān)視數(shù)組下標(biāo)變量j是否越

56、界.所以R0稱為哨兵.每次的比擬是從后往前比擬的.時(shí)間復(fù)雜度最好是O(n),最壞是O(n2),所以是O(n2).空間復(fù)雜度O(1),所以是就地排序.是穩(wěn)定的算法.初始情況是有序區(qū)中只有一個(gè)元素R1,無序區(qū)中R2.n.希爾排序(縮小增量排序廣算法不穩(wěn)定.記錄的總比擬次數(shù)和總移動次數(shù)都要比直接插入排序少得多,特別是當(dāng)n越大越明顯.希爾排序的時(shí)間依賴于增量序列,最后一個(gè)增量必須是1,盡量防止增量互為倍數(shù)的情況.F標(biāo)1234567891a初始關(guān)健字3b254S27652543舞7632d=52525相27殳3643麗7665d-3252536273248435®76后5d=i25252732J6434ft5g6576圖L1希爾挑序例如3 .交換排