數(shù)據(jù)結(jié)構(gòu)筆記

1、目錄 TOC o 1-3 h z u HYPERLINK l _Toc326075288 第一章 概 論 PAGEREF _Toc326075288 h 1 HYPERLINK l _Toc326075289 第 二 章 線(xiàn) 性 表 PAGEREF _Toc326075289 h 2 HYPERLINK l _Toc326075290 第 三 章 棧 和 隊(duì) 列 PAGEREF _Toc326075290 h 8 HYPERLINK l _Toc326075291 第 四 章 串 PAGEREF _Toc326075291 h 17 HYPERLINK l _Toc326075292 第 五

2、章 多 維 數(shù) 組 和 廣 義 表 PAGEREF _Toc326075292 h 21 HYPERLINK l _Toc326075293 第 六 章 樹(shù) PAGEREF _Toc326075293 h 23 HYPERLINK l _Toc326075294 第 七 章 圖 PAGEREF _Toc326075294 h 27 HYPERLINK l _Toc326075295 第 八 章 排 序 PAGEREF _Toc326075295 h 31 HYPERLINK l _Toc326075296 第 九 章 查 找 PAGEREF _Toc326075296 h 35 HYPERLI

3、NK l _Toc326075297 第 十 章 文 件 PAGEREF _Toc326075297 h 40第一章 概 論1.數(shù)據(jù)：信息的載體,能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。3.數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。它包括：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)存儲(chǔ)無(wú)關(guān)，獨(dú)立于計(jì)算機(jī)；2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，依賴(lài)于計(jì)算機(jī)語(yǔ)言。3）數(shù)據(jù)的運(yùn)算，定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的運(yùn)算：檢索/插入/刪除/更新/排序。4.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是

4、從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。5.數(shù)據(jù)類(lèi)型：一個(gè)值的集合及在值上定義的一組操作的總稱(chēng)。分為：原子類(lèi)型和結(jié)構(gòu)類(lèi)型。6.抽象數(shù)據(jù)類(lèi)型：抽象數(shù)據(jù)的組織和與之相關(guān)的操作。優(yōu)點(diǎn)：將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。7. 抽象數(shù)據(jù)類(lèi)型ADT：是在概念層上描述問(wèn)題；類(lèi)：是在實(shí)現(xiàn)層上描述問(wèn)題；在應(yīng)用層上操作對(duì)象（類(lèi)的實(shí)例）解決問(wèn)題。8.數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱(chēng)為數(shù)據(jù)結(jié)構(gòu)，有：（1）線(xiàn)性結(jié)構(gòu)，若結(jié)構(gòu)是非空集則僅有一個(gè)開(kāi)始和終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和后繼。（2）非線(xiàn)性結(jié)構(gòu)，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和后繼。9.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有：1）順序存儲(chǔ)，把邏輯相鄰的

5、結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元內(nèi)。2）鏈接存儲(chǔ)，結(jié)點(diǎn)間的邏輯關(guān)系由附加指針字段表示。3）索引存儲(chǔ)，存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加索引表，有稠密索引和稀疏索引。4）散列存儲(chǔ)，按結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出存儲(chǔ)地址。 10.評(píng)價(jià)算法的好壞是：算法是正確的；執(zhí)行算法所耗的時(shí)間；執(zhí)行算法的存儲(chǔ)空間（輔助存儲(chǔ)空間）；易于理解、編碼、調(diào)試。 11.算法的時(shí)間復(fù)雜度T(n)：是該算法的時(shí)間耗費(fèi)，是求解問(wèn)題規(guī)模n的函數(shù)。記為O(n)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線(xiàn)性階O(n)、線(xiàn)性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(

6、2n)。13.算法的空間復(fù)雜度S(n)：是該算法的空間耗費(fèi)，是求解問(wèn)題規(guī)模n的函數(shù)。12.算法衡量：是用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量的，它們合稱(chēng)算法的復(fù)雜度。13. 算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。第 二 章 線(xiàn) 性 表1.線(xiàn)性表：是由n(n0)個(gè)數(shù)據(jù)元素組成的有限序列。2.線(xiàn)性表的基本運(yùn)算有：1）InitList(L),構(gòu)造空表，即表的初始化；2）ListLength(L),求表的結(jié)點(diǎn)個(gè)數(shù)，即表長(zhǎng)；3）GetNode(L,i),取表中第i個(gè)結(jié)點(diǎn)，要求1iListLength(L)；4）LocateNode(L,x)查找L中值為x的結(jié)點(diǎn)并返回結(jié)點(diǎn)在L中的位置

7、，有多個(gè)x則返回首個(gè)，沒(méi)有則返回特殊值表示查找失敗。5）InsertList(L,x,i)在表的第i個(gè)位置插入值為x的新結(jié)點(diǎn)，要求1iListLength(L)+1；6）DeleteList(L,i)刪除表的第i個(gè)位置的結(jié)點(diǎn)，要求1iListLength(L)；3.順序表：把線(xiàn)性表的結(jié)點(diǎn)按邏輯次序存放在一組地址連續(xù)的存儲(chǔ)單元里。4.順序表結(jié)點(diǎn)的存儲(chǔ)地址計(jì)算公式：Loc(ai)=Loc(a1)+(i-1)*C；1in 5.順序表上的基本運(yùn)算（1）插入void insertlist(seqlist *L,datatype x,int i)int j;if(iL-length+1) error(“p

8、osition error”);if(L-length=listsize) error(“overflow”);for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj; 結(jié)點(diǎn)后移L-datai-1=x;L-length+;在順序表上插入要移動(dòng)表的n/2結(jié)點(diǎn)，算法的平均時(shí)間復(fù)雜度為O(n)。（2）刪除void delete (seqlist *L,int i)int j;if(iL-length) error(“position error”);for(j=i;jlength-1;j+) L-dataj-1=L-dataj; 結(jié)點(diǎn)前移 L-length-;在順序

9、表上刪除要移動(dòng)表的（n+1）/2結(jié)點(diǎn)，算法的平均時(shí)間復(fù)雜度為O(n)。 6.單鏈表：只有一個(gè)鏈域的鏈表稱(chēng)單鏈表。在結(jié)點(diǎn)中存儲(chǔ)結(jié)點(diǎn)值和結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址，data next data是數(shù)據(jù)域，next是指針域。 （1）建立單鏈表。時(shí)間復(fù)雜度為O(n)。加頭結(jié)點(diǎn)的優(yōu)點(diǎn)：1）鏈表第一個(gè)位置的操作無(wú)需特殊處理；2）將空表和非空表的處理統(tǒng)一。（2）查找運(yùn)算。時(shí)間復(fù)雜度為O(n)。 1） 按序號(hào)查找。Listnode * getnode(linklist head,int i)int j;listnode *p;p=head;j=0;while(p-next&jnext; 指針下移 j+;if(i=j)

10、 return p;else return NULL;2） 按值查找。Listnode * locatenode(linklist head ,datatype key)listnode *p=head-next;while(p&p-data!=key) p=p-next;return p;（3）插入運(yùn)算。時(shí)間復(fù)雜度為O(n)。Void insertlist(linklist head ,datatype x, int i)listnode *p;p=getnode(head,i-1);if(p=NULL); error(“position error”);s=(listnode *)mall

11、oc(sizeof(listnode);s-data=x;s-next=p-next;p-next=s; （4） 刪除運(yùn)算。時(shí)間復(fù)雜度為O(n)。Void deletelist(linklist head ,int i)listnode *p ,*r;p=getnode(head ,i-1);if(p=NULL|p-next=NULL) error(“position error”);r=p-next;p-next=r-next;free(r);7.循環(huán)鏈表：是一種首尾相連的鏈表。特點(diǎn)是無(wú)需增加存儲(chǔ)量，僅對(duì)表的鏈接方式修改使表的處理靈活方便。8.空循環(huán)鏈表僅由一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。9.很多

12、時(shí)候表的操作是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯的不夠方便，改用尾指針rear來(lái)表示單循環(huán)鏈表。用頭指針表示的單循環(huán)鏈表查找開(kāi)始結(jié)點(diǎn)的時(shí)間是O(1),查找尾結(jié)點(diǎn)的時(shí)間是O(n)；用尾指針表示的單循環(huán)鏈表查找開(kāi)始結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)間都是O(1)。10.在結(jié)點(diǎn)中增加一個(gè)指針域，prior|data|next。形成的鏈表中有兩條不同方向的鏈稱(chēng)為雙鏈表。1) 雙鏈表的前插操作。時(shí)間復(fù)雜度為O(1)。Void dinsertbefore(dlistnode *p ,datatype x)dlistnode *s=malloc(sizeof(dlistnode);s-data=x;s-pr

13、ior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2) 雙鏈表的刪除操作。時(shí)間復(fù)雜度為O(1)。Void ddeletenode(dlistnode *p)p-prior-next=p-next;p-next-prior=p-prior;free(p);11.順序表和鏈表的比較1） 基于空間的考慮：順序表的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。順序表的存儲(chǔ)密度比鏈表大。因此，在線(xiàn)性表長(zhǎng)度變化不大，易于事先確定時(shí)，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。2） 基于時(shí)間的考慮：順序表是隨機(jī)存取結(jié)構(gòu)，若線(xiàn)性表的操作主要是查找，很少有插入、刪除操作時(shí)，宜用順序表

14、結(jié)構(gòu)。對(duì)頻繁進(jìn)行插入、刪除操作的線(xiàn)性表宜采用鏈表。若操作主要發(fā)生在表的首尾時(shí)采用尾指針表示的單循環(huán)鏈表。12.存儲(chǔ)密度=（結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量）/（整個(gè)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量）存儲(chǔ)密度：順序表=1，鏈表top=-1;2)判棧空。int stackempty(seqstack *s)return s-top=-1;3)判棧滿(mǎn)。int stackfull(seqstack *s)return s-top=stacksize-1;4)進(jìn)棧。Void push(seqstack *s,datatype x)if(stackfull(s) error(“stack overflow”);s-data

15、+s-top=x;5)退棧。Datatype pop(seqstack *s)if(stackempty(s) error(“stack underflow”);return S-datas-top-;6)取棧頂元素。Dtatatype stacktop(seqstack *s)if(stackempty(s) error(“stack underflow”);return S-datas-top;6.鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)鏈棧。棧頂指針是鏈表的頭指針。7.鏈棧上的基本運(yùn)算：1） 建棧。Void initstack(linkstack *s)s-top=NULL;2)判?？铡nt stac

16、kempty (linkstack *s)return s-top=NULL;3) 進(jìn)棧。Void push(linkstack *s,datatype x)stacknode *p=(stacknode *)malloc(sizeof(stacknode);p-data=x;p-next=s-top;s-top=p;4) 退棧。Datatype pop(linksatck *s)datatype x;stacknode *p=s-top;if(stackempty(s) error(“stack underflow”);x=p-data;s-top=p-next;free(p);return

17、 x;5) 取棧頂元素。Datatype stacktop(linkstack *s)if(stackempty(s) error(“stack is empty”);return s-top-data;8.隊(duì)列是一種運(yùn)算受限的線(xiàn)性表，允許刪除的一端稱(chēng)隊(duì)首，允許插入的一端稱(chēng)隊(duì)尾。隊(duì)列又稱(chēng)為先進(jìn)先出線(xiàn)性表，F(xiàn)IFO表。9.隊(duì)列的基本運(yùn)算：1） initqueue(q),置空隊(duì)；2） queueempty(q),判隊(duì)空；3） queuefull(q),判隊(duì)滿(mǎn)；4） enqueue(q,x),入隊(duì)；5） dequeue(q),出隊(duì)；6） queuefront(q),返回隊(duì)頭元素。10.順序隊(duì)列：隊(duì)列

18、的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)順序隊(duì)列。設(shè)置front和rear指針表示隊(duì)頭和隊(duì)尾元素在向量空間的位置。11.順序隊(duì)列中存在“假上溢”現(xiàn)象，由于入隊(duì)和出隊(duì)操作使頭尾指針只增不減導(dǎo)致被刪元素的空間無(wú)法利用，隊(duì)尾指針超過(guò)向量空間的上界而不能入隊(duì)。12.為克服“假上溢”現(xiàn)象，將向量空間想象為首尾相連的循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱(chēng)循環(huán)隊(duì)列。i=(i+1)%queuesize13.循環(huán)隊(duì)列的邊界條件處理：由于無(wú)法用front=rear來(lái)判斷隊(duì)列的“空”和“滿(mǎn)”。解決的方法有：1） 另設(shè)一個(gè)布爾變量以區(qū)別隊(duì)列的空和滿(mǎn)；2） 少用一個(gè)元素，在入隊(duì)前測(cè)試rear在循環(huán)意義下加1是否等于front；3） 使用一個(gè)記數(shù)器記錄元

19、素總數(shù)。14.循環(huán)隊(duì)列的基本運(yùn)算：1) 置隊(duì)空。Void initqueue(cirqueue *q)q-front=q-rear=0;q-count=0;2) 判隊(duì)空。Int queueempty(cirqueue *q)return q-count=0;3) 判隊(duì)滿(mǎn)。Int queuefull(cirqueue *q)return q-count=queuesize;4) 入隊(duì)。Void enqueue(cirqueue *q ,datatype x)if(queuefull(q) error(“queue overfolw”);q-count+;q-dataq-rear=x;q-rear

20、=(q-rear+1)%queuesize;5) 出隊(duì)。Datatype dequeue(cirqueue *q)datatype temp;if(queueempty(q) error(“queue underflow”);temp=q-dataq-front;q-count-;q-front=(q-front+1)%queuesize;return temp;6) 取隊(duì)頭元素。Datatype queuefront(cirqueue *q)if(queueempty(q) error(“queue is empty”);return q-dataq-front;15.鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)

21、結(jié)構(gòu)稱(chēng)鏈隊(duì)列，鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一確定。16.鏈隊(duì)列的基本運(yùn)算：1) 建空隊(duì)。Void initqueue(linkqueue *q)q-front=q-rear=NULL;2) 判隊(duì)空。Int queueempty(linkqueue *q)return q-front=NULL&q-rear=NULL;3) 入隊(duì)。Void enqueue(linkqueue *q,datatype x)queuenode *p=(queuenode *)malloc(sizeof(queuenode);p-data=x;p-next=NULL;if(queueempty(q) q-front

22、=q-rear=p;else q-rear-next=p; q-rear=p; 4) 出隊(duì)。Datatype dequeue(linkqueue *q)datatype x;queuenode *p;if(queueempty(q) error(“queue is underflow”);p=q-front;x=p-data;q-front=p-next;if(q-rear=p) q-rear=NULL;free(p);return x;5) 取隊(duì)頭元素。Datatype queuefront(linkqueue *q)if(queueempty(q) error(“queue is empt

23、y”);return q-front-data;第 四 章 串1.串：是由零個(gè)或多個(gè)字符組成的有限序列；包含字符的個(gè)數(shù)稱(chēng)串的長(zhǎng)度；2.空串：長(zhǎng)度為零的串稱(chēng)空串； 空白串：由一個(gè)或多個(gè)空格組成的串稱(chēng)空白串；子串：串中任意個(gè)連續(xù)字符組成的子序列稱(chēng)該串的子串； 主串：包含子串的串稱(chēng)主串；子串的首字符在主串中首次出現(xiàn)的位置定義為子串在主串中的位置；3.空串是任意串的子串； 任意串是自身的子串；串常量在程序中只能引用但不能改變其值； 串變量取值可以改變；4.串的基本運(yùn)算1） int strlen(char *s);求串長(zhǎng)。2） char *strcpy(char * to,char * from);串復(fù)

24、制。3） char *strcat(char * to,char * from);串聯(lián)接。4） int strcmp(char *s1,char *s2);串比較。5） char *strchr(char *s,char c);字符定位。5.串的存儲(chǔ)結(jié)構(gòu)：（1）串的順序存儲(chǔ)：串的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)順序串。按存儲(chǔ)分配不同分為：1） 靜態(tài)存儲(chǔ)分配的順序串：直接用定長(zhǎng)的字符數(shù)組定義，以“0”表示串值終結(jié)。#define maxstrsize 256typedef char seqstringmaxstrsize;seqstring s;不設(shè)終結(jié)符，用串長(zhǎng)表示。Typedef structChar chm

25、axstrsize;Int length;seqstring;以上方式的缺點(diǎn)是：串值空間大小是靜態(tài)的，難以適應(yīng)插入、鏈接等操作。2） 動(dòng)態(tài)存儲(chǔ)分配的順序串：簡(jiǎn)單定義：typedef char * string;復(fù)雜定義：typedef struct char *ch; int length; hstring;（2）串的鏈?zhǔn)酱鎯?chǔ)：串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)鏈串。鏈串由頭指針唯一確定。類(lèi)型定義：typedef struct nodechar data;struct node *next;linkstrnode;typedef linkstrnode *linkstring;linkstring s;將結(jié)點(diǎn)

26、數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小。結(jié)點(diǎn)大小不為1的鏈串類(lèi)型定義：#define nodesize 80typedef struct nodechar datanodesize;struct node * next;linkstrnode;6.串運(yùn)算的實(shí)現(xiàn)（1）順序串上的子串定位運(yùn)算。1）子串定位運(yùn)算又稱(chēng)串的模式匹配或串匹配。主串稱(chēng)目標(biāo)串；子串稱(chēng)模式串。2）樸素的串匹配算法。時(shí)間復(fù)雜度為O(n2)。比較的字符總次數(shù)為（n-m+1）m。Int naivestrmatch(seqstring t,seqstring p)int i,j,k;int m=p.length;int n=t.lengt

27、h;for(i=0;i=n-m;i+) j=0;k=i; while(jdata=p-data)t=t-next; p=p-next; else shift=shift-next; t=shift; p=P; if(p=NULL) return shift;else return NULL;第 五 章 多 維 數(shù) 組 和 廣 義 表1.多維數(shù)組：一般用順序存儲(chǔ)的方式表示數(shù)組。2.常用方式有：1）行優(yōu)先順序，將數(shù)組元素按行向量排列；2）列優(yōu)先順序，將數(shù)組元素按列向量排列。3.計(jì)算地址的函數(shù)：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d4.矩陣的壓縮存儲(chǔ)

28、：為多個(gè)非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配存儲(chǔ)空間。（1） 對(duì)稱(chēng)矩陣：在一個(gè)n階的方陣A中，元素滿(mǎn)足Aij=Aji 0=i,j(k-1)/2以行優(yōu)先順序存放的Aij與SAk的關(guān)系：k=2i+j;5.稀疏矩陣：當(dāng)矩陣A中有非零元素S個(gè)，且S遠(yuǎn)小于元素總數(shù)時(shí)，稱(chēng)為稀疏矩陣。對(duì)其壓縮的方法有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。（1）三元組表：將表示稀疏矩陣的非零元素的三元組（行號(hào)、列號(hào)、值）按行或列優(yōu)先的順序排列得到的一個(gè)結(jié)點(diǎn)均是三元組的線(xiàn)性表，將該表的線(xiàn)性存儲(chǔ)結(jié)構(gòu)稱(chēng)為三元組表。其類(lèi)型定義：#define maxsize 10000typedef int datatype;typedef structint

29、i,j;datatype v;trituplenode;typedef structtrituplenode datamaxsize;int m,n,t;tritupletable;（2）帶行表的三元組表：在按行優(yōu)先存儲(chǔ)的三元組表中加入一個(gè)行表記錄每行的非零元素在三元組表中的起始位置。類(lèi)型定義：#define maxrow 100typedef structtritulpenode datamaxsize;int rowtabmaxrow;int m, n, t;rtritulpetable;6.廣義表：是線(xiàn)性表的推廣，廣義表是n個(gè)元素的有限序列，元素可以是原子或一個(gè)廣義表，記為L(zhǎng)S。7.若元

30、素是廣義表稱(chēng)它為L(zhǎng)S的子表。若廣義表非空，則第一個(gè)元素稱(chēng)表頭，其余元素稱(chēng)表尾。8.表的深度是指表展開(kāi)后所含括號(hào)的層數(shù)。9.把與樹(shù)對(duì)應(yīng)的廣義表稱(chēng)為純表，它限制了表中成分的共享和遞歸；10.允許結(jié)點(diǎn)共享的表稱(chēng)為再入表；11.允許遞歸的表稱(chēng)為遞歸表；12.相互關(guān)系：線(xiàn)性表純表再入表遞歸表；13.廣義表的特殊運(yùn)算：1）取表頭head(LS)；2）取表尾tail(LS);第 六 章 樹(shù)1.樹(shù)：是n個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱(chēng)空樹(shù)，否則滿(mǎn)足：1）有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；2）其余結(jié)點(diǎn)可分為m個(gè)互不相交的子集，每個(gè)子集本身是一棵樹(shù)，并稱(chēng)為根的子樹(shù)。2.樹(shù)的表示方法：1）樹(shù)形表示法；2）嵌套集合表示法；

31、3）凹入表表示法；4）廣義表表示法；3.一個(gè)結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為該結(jié)點(diǎn)的度；一棵樹(shù)的度是指樹(shù)中結(jié)點(diǎn)最大的度數(shù)。4.度為零的結(jié)點(diǎn)稱(chēng)葉子或終端結(jié)點(diǎn)；度不為零的結(jié)點(diǎn)稱(chēng)分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)5.根結(jié)點(diǎn)稱(chēng)開(kāi)始結(jié)點(diǎn)，根結(jié)點(diǎn)外的分支結(jié)點(diǎn)稱(chēng)內(nèi)部結(jié)點(diǎn)；6.樹(shù)中某結(jié)點(diǎn)的子樹(shù)根稱(chēng)該結(jié)點(diǎn)的孩子；該結(jié)點(diǎn)稱(chēng)為孩子的雙親；7.樹(shù)中存在一個(gè)結(jié)點(diǎn)序列K1，K2，Kn，使Ki為Ki+1的雙親，則稱(chēng)該結(jié)點(diǎn)序列為K1到Kn的路徑或道路；8.樹(shù)中結(jié)點(diǎn)K到Ks間存在一條路徑，則稱(chēng)K是Ks的祖先，Ks是K的子孫；9.結(jié)點(diǎn)的層數(shù)從根算起，若根的層數(shù)為1，則其余結(jié)點(diǎn)層數(shù)是其雙親結(jié)點(diǎn)層數(shù)加1；雙親在同一層的結(jié)點(diǎn)互為堂兄弟；樹(shù)中結(jié)點(diǎn)最大層數(shù)稱(chēng)為樹(shù)的

32、高度或深度；10.樹(shù)中每個(gè)結(jié)點(diǎn)的各個(gè)子樹(shù)從左到右有次序的稱(chēng)有序樹(shù)，否則稱(chēng)無(wú)序樹(shù)；11.森林是m棵互不相交的樹(shù)的集合。 12.二叉樹(shù)：是n個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭占?，或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱(chēng)為該根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。13.二叉樹(shù)不是樹(shù)的特殊情況，這是兩種不同的數(shù)據(jù)結(jié)構(gòu)；它與無(wú)序樹(shù)和度為2的有序樹(shù)不同。14.二叉樹(shù)的性質(zhì)：1） 二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)最多為2(i-1)；2） 深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)；3） 在任意二叉樹(shù)中，葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；15.滿(mǎn)二叉樹(shù)是一棵深度為k的且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)；16.完全二叉樹(shù)是至多在最下兩

33、層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下層的結(jié)點(diǎn)集中在該層最左的位置的二叉樹(shù)；17.具有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2N取整加1；18.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)：把一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，從樹(shù)根起自上而下、從左到右對(duì)所有結(jié)點(diǎn)編號(hào)，然后依次存儲(chǔ)在一個(gè)向量b0n中，b1n存放結(jié)點(diǎn)，b0存放結(jié)點(diǎn)總數(shù)。各個(gè)結(jié)點(diǎn)編號(hào)間的關(guān)系：1） i=1是根結(jié)點(diǎn)；i1則雙親結(jié)點(diǎn)是i/2取整；2） 左孩子是2i, 右孩子是2i+1；（要小于n）3） i（n/2取整）的結(jié)點(diǎn)是葉子；4） 奇數(shù)沒(méi)有右兄弟，左兄弟是i-1；5） 偶數(shù)沒(méi)有左兄弟，右兄弟是i+1；（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)的結(jié)構(gòu)為：lchild|data

34、|rchild ；相應(yīng)的類(lèi)型說(shuō)明：typedef char data;typedef struct nodedatatype data;structnode *lchild , *rchild;bintnode;typedef bintnode * bintree;19.在二叉樹(shù)中所有類(lèi)型為bintnode的結(jié)點(diǎn)和一個(gè)指向開(kāi)始結(jié)點(diǎn)的bintree類(lèi)型的頭指針構(gòu)成二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)二叉鏈表。20.二叉鏈表由根指針唯一確定。在n個(gè)結(jié)點(diǎn)的二叉鏈表中有2n個(gè)指針域，其中n+1個(gè)為空。21.二叉樹(shù)的遍歷方式有：前序遍歷、中序遍歷、后序遍歷。時(shí)間復(fù)雜度為O(n)。22.線(xiàn)索二叉樹(shù)：利用二叉鏈表中的n+

35、1個(gè)空指針域存放指向某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這種指針?lè)Q線(xiàn)索。加線(xiàn)索的二叉鏈表稱(chēng)線(xiàn)索鏈表。相應(yīng)二叉樹(shù)稱(chēng)線(xiàn)索二叉樹(shù)。23.線(xiàn)索鏈表結(jié)點(diǎn)結(jié)構(gòu)：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指針；ltag=1,lchild是指向前趨的線(xiàn)索；rtag=0,rchild是指向右孩子的指針；rtag=1,rchild是指向后繼的線(xiàn)索；24.查找*p在指定次序下的前趨和后繼結(jié)點(diǎn)。算法的時(shí)間復(fù)雜度為O(h)。線(xiàn)索對(duì)查找前序前趨和后序后繼幫助不大。25.遍歷線(xiàn)索二叉樹(shù)。時(shí)間復(fù)雜度為O(n)。26.樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換（1）樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換1

36、）樹(shù)與二叉樹(shù)的轉(zhuǎn)換：1所有兄弟間連線(xiàn)；2保留與長(zhǎng)子的連線(xiàn)，去除其它連線(xiàn)。該二叉樹(shù)的根結(jié)點(diǎn)的右子樹(shù)必為空。2）森林與二叉樹(shù)的轉(zhuǎn)換：1將所有樹(shù)轉(zhuǎn)換成二叉樹(shù)；2將所有樹(shù)根連線(xiàn)。（2）二叉樹(shù)與樹(shù)、森林的轉(zhuǎn)換。是以上的逆過(guò)程。27.樹(shù)的存儲(chǔ)結(jié)構(gòu)（1）雙親鏈表表示法：為每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)parent指針，就可唯一表示任何一棵樹(shù)。Data|parent（2）孩子鏈表表示法：為每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)firstchild指針，指向孩子鏈表頭指針，鏈表中存放孩子結(jié)點(diǎn)序號(hào)。Data|firstchild。（3雙親孩子鏈表表示法：將以上方法結(jié)合。Data|parent|firstchild（4）孩子兄弟鏈表表示法：附加兩個(gè)指

37、向左孩子和右兄弟的指針。Leftmostchild|data|rightsibling28.樹(shù)和森林的遍歷：前序遍歷一棵樹(shù)等價(jià)于前序遍歷對(duì)應(yīng)二叉樹(shù)；后序遍歷等價(jià)于中序遍歷對(duì)應(yīng)二叉樹(shù)。29.最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）：樹(shù)的路徑長(zhǎng)度是從樹(shù)根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。將樹(shù)中的結(jié)點(diǎn)賦予實(shí)數(shù)稱(chēng)為結(jié)點(diǎn)的權(quán)。30.結(jié)點(diǎn)的帶權(quán)路徑是該結(jié)點(diǎn)的路徑長(zhǎng)度與權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度又稱(chēng)樹(shù)的代價(jià)，是所有葉子的帶權(quán)路徑長(zhǎng)度之和。31.帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱(chēng)最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）。32.具有2n-1個(gè)結(jié)點(diǎn)其中有n個(gè)葉子，并且沒(méi)有度為1的分支結(jié)點(diǎn)的樹(shù)稱(chēng)為嚴(yán)格二叉樹(shù)。33.哈夫曼編碼 34.對(duì)字符集編碼時(shí)，要求字符集中任一字

38、符的編碼都不是其它字符的編碼前綴，這種編碼稱(chēng)前綴碼。35.字符出現(xiàn)頻度與碼長(zhǎng)乘積之和稱(chēng)文件總長(zhǎng)；字符出現(xiàn)概率與碼長(zhǎng)乘積之和稱(chēng)平均碼長(zhǎng)；36.使文件總長(zhǎng)或平均碼長(zhǎng)最小的前綴碼稱(chēng)最優(yōu)前綴碼37.利用哈夫曼樹(shù)求最優(yōu)前綴碼，左為0，右為1。編碼平均碼長(zhǎng)最?。粵](méi)有葉子是其它葉子的祖先，不可能出現(xiàn)重復(fù)前綴。第 七 章 圖1.圖：圖G是由頂點(diǎn)集V和邊集E組成，頂點(diǎn)集是有窮非空集，邊集是有窮集；2.G中每條邊都有方向稱(chēng)有向圖；有向邊稱(chēng)?。贿叺氖键c(diǎn)稱(chēng)弧尾；邊的終點(diǎn)稱(chēng)弧頭；G中每條邊都沒(méi)有方向的稱(chēng)無(wú)向圖。3.頂點(diǎn)n與邊數(shù)e的關(guān)系：無(wú)向圖的邊數(shù)e介于0n(n-1)/2之間，有n(n-1)/2條邊的稱(chēng)無(wú)向完全圖；有向

39、圖的邊數(shù)e介于0n(n-1)之間，有n(n-1)條邊的稱(chēng)有向完全圖；4.無(wú)向圖中頂點(diǎn)的度是關(guān)聯(lián)與頂點(diǎn)的邊數(shù)；有向圖中頂點(diǎn)的度是入度與出度的和。所有圖均滿(mǎn)足：所有頂點(diǎn)的度數(shù)和的一半為邊數(shù)。5.圖G（V，E），如V是V的子集，E是E的子集，且E中關(guān)聯(lián)的頂點(diǎn)均在V中，則G(V,E)是G的子圖。6.在有向圖中，從頂點(diǎn)出發(fā)都有路徑到達(dá)其它頂點(diǎn)的圖稱(chēng)有根圖；7.在無(wú)向圖中，任意兩個(gè)頂點(diǎn)都有路徑連通稱(chēng)連通圖；極大連通子圖稱(chēng)連通分量；8.在有向圖中，任意順序兩個(gè)頂點(diǎn)都有路徑連通稱(chēng)強(qiáng)連通圖；極大連通子圖稱(chēng)強(qiáng)連通分量；9.將圖中每條邊賦上權(quán)，則稱(chēng)帶權(quán)圖為網(wǎng)絡(luò)。10.圖的存儲(chǔ)結(jié)構(gòu)：（1）鄰接矩陣表示法：鄰接矩陣是表

40、示頂點(diǎn)間相鄰關(guān)系的矩陣。n個(gè)頂點(diǎn)就是n階方陣。無(wú)向圖是對(duì)稱(chēng)矩陣；有向圖行是出度，列是入度。（2）鄰接表表示法：對(duì)圖中所有頂點(diǎn)，把與該頂點(diǎn)相鄰接的頂點(diǎn)組成一個(gè)單鏈表，稱(chēng)為鄰接表，adjvex|next,如要保存頂點(diǎn)信息加入data；對(duì)所有頂點(diǎn)設(shè)立頭結(jié)點(diǎn)，vertex|firstedge,并順序存儲(chǔ)在一個(gè)向量中；vertex保存頂點(diǎn)信息，firstedge保存鄰接表頭指針。11.鄰接矩陣表示法與鄰接表表示法的比較：1） 鄰接矩陣是唯一的，鄰接表不唯一；2） 存儲(chǔ)稀疏圖用鄰接表，存儲(chǔ)稠密圖用鄰接矩陣；3） 求無(wú)向圖頂點(diǎn)的度都容易，求有向圖頂點(diǎn)的度鄰接矩陣較方便；4） 判斷是否是圖中的邊，鄰接矩陣容易

41、，鄰接表最壞時(shí)間為O(n)；5） 求邊數(shù)e，鄰接矩陣耗時(shí)為O(n2)，與e無(wú)關(guān)，鄰接表的耗時(shí)為O(e+n)；12.圖的遍歷：（1）圖的深度優(yōu)先遍歷：類(lèi)似與樹(shù)的前序遍歷。按訪(fǎng)問(wèn)頂點(diǎn)次序得到的序列稱(chēng)DFS序列。對(duì)鄰接表表示的圖深度遍歷稱(chēng)DFS，時(shí)間復(fù)雜度為O(n+e); 對(duì)鄰接矩陣表示的圖深度遍歷稱(chēng)DFSM，時(shí)間復(fù)雜度為O(n2);（2）圖的廣度優(yōu)先遍歷：類(lèi)似與樹(shù)的層次遍歷。按訪(fǎng)問(wèn)頂點(diǎn)次序得到的序列稱(chēng)BFS序列。對(duì)鄰接表表示的圖廣度遍歷稱(chēng)BFS，時(shí)間復(fù)雜度為O(n+e); 對(duì)鄰接矩陣表示的圖廣度遍歷稱(chēng)BFSM，時(shí)間復(fù)雜度為O(n2);13. 將沒(méi)有回路的連通圖定義為樹(shù)稱(chēng)自由樹(shù)。14.生成樹(shù)：連通圖

42、G的一個(gè)子圖若是一棵包含G中所有頂點(diǎn)的樹(shù)，該子圖稱(chēng)生成樹(shù)。有DFS生成樹(shù)和BFS生成樹(shù)，BFS生成樹(shù)的高度最小。非連通圖生成的是森林。15.最小生成樹(shù)：將權(quán)最小的生成樹(shù)稱(chēng)最小生成樹(shù)。（是無(wú)向圖的算法）（1）普里姆算法：1） 確定頂點(diǎn)S、初始化候選邊集T0n-2；formvex|tovex|lenght2） 選權(quán)值最小的Ti與第1條記錄交換；3） 從T1中將tovex取出替換以下記錄的fromvex計(jì)算權(quán)；若權(quán)小則替換，否則不變；4） 選權(quán)值最小的Ti與第2條記錄交換；5） 從T2中將tovex取出替換以下記錄的fromvex計(jì)算權(quán)；若權(quán)小則替換，否則不變；6） 重復(fù)n-1次。初始化時(shí)間是O(n

43、),選輕邊的循環(huán)執(zhí)行n-1-k次，調(diào)整輕邊的循環(huán)執(zhí)行n-2-k；算法的時(shí)間復(fù)雜度為O(n2)，適合于稠密圖。（2）克魯斯卡爾算法：1） 初始化確定頂點(diǎn)集和空邊集；對(duì)原邊集按權(quán)值遞增順序排序；2） 取第1條邊，判斷邊的2個(gè)頂點(diǎn)是不同的樹(shù)，加入空邊集，否則刪除；3） 重復(fù)e次。對(duì)邊的排序時(shí)間是O(elog2e)；初始化時(shí)間為O(n)；執(zhí)行時(shí)間是O(log2e)；算法的時(shí)間復(fù)雜度為O(elog2e)，適合于稀疏圖。16. 路徑的開(kāi)始頂點(diǎn)稱(chēng)源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)稱(chēng)終點(diǎn)；17.單源最短路徑問(wèn)題：已知有向帶權(quán)圖，求從某個(gè)源點(diǎn)出發(fā)到其余各個(gè)頂點(diǎn)的最短路徑；18.單目標(biāo)最短路徑問(wèn)題：將圖中每條邊反向，轉(zhuǎn)換為

44、單源最短路徑問(wèn)題；19.單頂點(diǎn)對(duì)間最短路徑問(wèn)題：以分別對(duì)不同頂點(diǎn)轉(zhuǎn)換為單源最短路徑問(wèn)題；20.所有頂點(diǎn)對(duì)間最短路徑問(wèn)題：分別對(duì)圖中不同頂點(diǎn)對(duì)轉(zhuǎn)換為單源最短路徑問(wèn)題；21.迪杰斯特拉算法：1） 初始化頂點(diǎn)集Si,路徑權(quán)集Di,前趨集Pi；2） 設(shè)置Ss為真，Ds為0；3） 選取Di最小的頂點(diǎn)加入頂點(diǎn)集；4） 計(jì)算非頂點(diǎn)集中頂點(diǎn)的路徑權(quán)集；5） 重復(fù)3）n-1次。算法的時(shí)間復(fù)雜度為O(n2)。22.拓?fù)渑判颍簩?duì)一個(gè)有向無(wú)環(huán)圖進(jìn)行拓?fù)渑判颍菍D中所有頂點(diǎn)排成一個(gè)線(xiàn)性序列，滿(mǎn)足弧尾在弧頭之前。這樣的線(xiàn)性序列稱(chēng)拓?fù)湫蛄?。?）無(wú)前趨的頂點(diǎn)優(yōu)先：總是選擇入度為0的結(jié)點(diǎn)輸出并刪除該頂點(diǎn)的所有邊。設(shè)置各個(gè)頂

45、點(diǎn)入度時(shí)間是O(n+e)，設(shè)置棧或隊(duì)列的時(shí)間是O(n)，算法時(shí)間復(fù)雜度為O(n+e)。（2）無(wú)后繼的頂點(diǎn)優(yōu)先：總是選擇出度為0的結(jié)點(diǎn)輸出并刪除該頂點(diǎn)的所有邊。設(shè)置各個(gè)頂點(diǎn)出度時(shí)間是O(n+e)，設(shè)置?；蜿?duì)列的時(shí)間是O(n)，算法時(shí)間復(fù)雜度為O(n+e)。求得的是逆拓?fù)湫蛄小５?八 章 排 序1.文件：由一組記錄組成，記錄有若干數(shù)據(jù)項(xiàng)組成，唯一標(biāo)識(shí)記錄的數(shù)據(jù)項(xiàng)稱(chēng)關(guān)鍵字； 2.排序是將文件按關(guān)鍵字的遞增（減）順序排列；3.排序文件中有相同的關(guān)鍵字時(shí)，若排序后相對(duì)次序保持不變的稱(chēng)穩(wěn)定排序，否則稱(chēng)不穩(wěn)定排序；4.在排序過(guò)程中，文件放在內(nèi)存中處理不涉及數(shù)據(jù)的內(nèi)、外存交換的稱(chēng)內(nèi)排序，反之稱(chēng)外排序；5.排序

46、算法的基本操作：1）比較關(guān)鍵字的大??；2）改變指向記錄的指針或移動(dòng)記錄本身。6.評(píng)價(jià)排序方法的標(biāo)準(zhǔn)：1）執(zhí)行時(shí)間；2）所需輔助空間，輔助空間為O(1)稱(chēng)就地排序；另要注意算法的復(fù)雜程度。7.若關(guān)鍵字類(lèi)型沒(méi)有比較運(yùn)算符，可事先定義宏或函數(shù)表示比較運(yùn)算。8.插入排序（1）直接插入排序算法中引入監(jiān)視哨R0的作用是：1）保存Ri的副本；2）簡(jiǎn)化邊界條件，防止循環(huán)下標(biāo)越界。關(guān)鍵字比較次數(shù)最大為(n+2)(n-1)/2；記錄移動(dòng)次數(shù)最大為(n+4)(n-1)/2；算法的最好時(shí)間是O(n)；最壞時(shí)間是O(n2)；平均時(shí)間是O(n2)；是一種就地的穩(wěn)定的排序；（2）希爾排序?qū)崿F(xiàn)過(guò)程：是將直接插入排序的間隔變?yōu)?/p>

47、d。d的取值要注意：1）最后一次必為1；2）避免d值互為倍數(shù)；關(guān)鍵字比較次數(shù)最大為n1.25；記錄移動(dòng)次數(shù)最大為1.6n1.25；算法的平均時(shí)間是O(n1.25)；是一種就地的不穩(wěn)定的排序；9.交換排序（1）冒泡排序?qū)崿F(xiàn)過(guò)程：從下到上相鄰兩個(gè)比較，按小在上原則掃描一次，確定最小值，重復(fù)n-1次。關(guān)鍵字比較次數(shù)最小為n-1、最大為n(n-1)/2；記錄移動(dòng)次數(shù)最小為0，最大為3n(n-1)/2；算法的最好時(shí)間是O(n)；最壞時(shí)間是O(n2)；平均時(shí)間是O(n2)；是一種就地的穩(wěn)定的排序；（2）快速排序?qū)崿F(xiàn)過(guò)程：將第一個(gè)值作為基準(zhǔn)，設(shè)置i,j指針交替從兩頭與基準(zhǔn)比較，有交換后,交換j，i。i=j時(shí)

48、確定基準(zhǔn)，并以其為界限將序列分為兩段。重復(fù)以上步驟。關(guān)鍵字比較次數(shù)最好為nlog2n+nC(1)、最壞為n(n-1)/2；算法的最好時(shí)間是O(nlog2n)；最壞時(shí)間是O(n2)；平均時(shí)間是O(nlog2n)；輔助空間為O(log2n)；是一種不穩(wěn)定排序；10.選擇排序（1）直接選擇排序?qū)崿F(xiàn)過(guò)程：選擇序列中最小的插入第一位，在剩余的序列中重復(fù)上一步，共重復(fù)n-1次。關(guān)鍵字比較次數(shù)為n(n-1)/2；記錄移動(dòng)次數(shù)最小為0，最大為3(n-1)；算法的最好時(shí)間是O(n2)；最壞時(shí)間是O(n2)；平均時(shí)間是O(n2)；是一種就地的不穩(wěn)定的排序；（2）堆排序?qū)崿F(xiàn)過(guò)程：把序列按層次填入完全二叉樹(shù)，調(diào)整位置

49、使雙親大于或小于孩子，建立初始大根或小根堆，調(diào)整樹(shù)根與最后一個(gè)葉子的位置，排除該葉子重新調(diào)整位置。算法的最好時(shí)間是O(nlog2n)；最壞時(shí)間是O(nlog2n)；平均時(shí)間是O(nlog2n)；是一種就地的不穩(wěn)定排序；11.歸并排序?qū)崿F(xiàn)過(guò)程：將初始序列分為2個(gè)一組，最后單數(shù)輪空，對(duì)每一組排序后作為一個(gè)單元，對(duì)2個(gè)單元排序，直到結(jié)束。算法的最好時(shí)間是O(nlog2n)；最壞時(shí)間是O(nlog2n)；平均時(shí)間是O(nlog2n)；輔助空間為O(n)；是一種穩(wěn)定排序；12.分配排序（1）箱排序?qū)崿F(xiàn)過(guò)程：按關(guān)鍵字的取值范圍確定箱子的個(gè)數(shù)，將序列按關(guān)鍵字放入箱中，輸出非空箱的關(guān)鍵字。在桶內(nèi)分配和收集，及

50、對(duì)各桶進(jìn)行插入排序的時(shí)間為O(n),算法的期望時(shí)間是O(n),最壞時(shí)間是O(n2)。（2）基數(shù)排序?qū)崿F(xiàn)過(guò)程：按基數(shù)設(shè)置箱子，對(duì)關(guān)鍵字從低位到高位依次進(jìn)行箱排序。算法的最好時(shí)間是O(d*n+d*rd)；最壞時(shí)間是O(d*n+d*rd)；平均時(shí)間是O(d*n+d*rd)；輔助空間O(n+rd)；是一種穩(wěn)定排序；13.各種內(nèi)部排序方法的比較和選擇：（1）按平均時(shí)間復(fù)雜度分為：1) 平方階排序：直接插入、直接選擇、冒泡排序；2) 線(xiàn)性對(duì)數(shù)階：快速排序、堆排序、歸并排序；3) 指數(shù)階：希爾排序；4) 線(xiàn)性階：箱排序、基數(shù)排序。（2）選擇合適排序方法的因素：1)待排序的記錄數(shù)；2)記錄的大小；3)關(guān)鍵字的

51、結(jié)構(gòu)和初始狀態(tài)；4)對(duì)穩(wěn)定性的要求；5)語(yǔ)言工具的條件；6)存儲(chǔ)結(jié)構(gòu)； 7)時(shí)間和輔助空間復(fù)雜度。（3）結(jié)論：1) 若規(guī)模較小可采用直接插入或直接選擇排序；2) 若文件初始狀態(tài)基本有序可采用直接插入、冒泡或隨機(jī)快速排序；3) 若規(guī)模較大可采用快速排序、堆排序或歸并排序；4) 任何借助于比較的排序，至少需要O(nlog2n)的時(shí)間，箱排序和基數(shù)排序只適用于有明顯結(jié)構(gòu)特征的關(guān)鍵字；5) 有的語(yǔ)言沒(méi)有提供指針及遞歸，使歸并、快速、基數(shù)排序算法復(fù)雜；6) 記錄規(guī)模較大時(shí)為避免大量移動(dòng)記錄可用鏈表作為存儲(chǔ)結(jié)構(gòu)，如插入、歸并、基數(shù)排序，但快速、堆排序在鏈表上難以實(shí)現(xiàn)，可提取關(guān)鍵字建立索引表，然后對(duì)索引表排

52、序。第 九 章 查 找1.查找的同時(shí)對(duì)表做修改操作(如插入或刪除)則相應(yīng)的表稱(chēng)之為動(dòng)態(tài)查找表，否則稱(chēng)之為靜態(tài)查找表。2.衡量一個(gè)查找算法次序優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長(zhǎng)度ASL).3.線(xiàn)性表上進(jìn)行查找的方法主要有三種：順序查找、二分查找和分塊查找。（1）順序查找的算法基本思想：是從表的一端開(kāi)始順序掃描線(xiàn)性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值K比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與k相等則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。1）順序查找方法可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。2）在順序存儲(chǔ)結(jié)構(gòu)的順序查找算法中所設(shè)的哨兵是為了簡(jiǎn)化循環(huán)的

53、邊界條件而引入的附加結(jié)點(diǎn)(元素)，其作用是使for循環(huán)中省去判定防止下標(biāo)越界的條件從而節(jié)省了比較的時(shí)間。3）在等概率情況下，查找成功時(shí)其平均查找長(zhǎng)度約為表長(zhǎng)的一半(n+1)/2.查找失敗的話(huà)其平均查找長(zhǎng)度為n+1.（2）二分查找(又稱(chēng)折半查找)，它的算法思想：是對(duì)一有序表中的元素，從初始的查找區(qū)間開(kāi)始，每經(jīng)過(guò)一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則，當(dāng)前查找區(qū)間的縮小一半，按k值大小在某半個(gè)區(qū)間內(nèi)重復(fù)相同的步驟進(jìn)行查找，直到查找成功或失敗為止。1）二分查找在等概率的情況下查找成功的平均查找長(zhǎng)度ASL為lg(n+1)-1,在查找失敗時(shí)所需比較的關(guān)鍵字個(gè)數(shù)不超過(guò)

54、判定樹(shù)的深度，最壞情況下查找成功的比較次數(shù)也不超過(guò)判定樹(shù)的深度lg(n+1)(不小于lg(n+1)的最小整數(shù))2）二分查找只適用于順序存儲(chǔ)結(jié)構(gòu)而不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)。因?yàn)殒湵頍o(wú)法進(jìn)行隨機(jī)訪(fǎng)問(wèn)，如果要訪(fǎng)問(wèn)鏈表的中間結(jié)點(diǎn)，就必須先從頭結(jié)點(diǎn)開(kāi)始進(jìn)行依次訪(fǎng)問(wèn)，這就要浪費(fèi)很多時(shí)間，還不如進(jìn)行順序查找，而且，用鏈存儲(chǔ)結(jié)構(gòu)將無(wú)法判定二分的過(guò)程是否結(jié)束，因此無(wú)法用鏈表實(shí)現(xiàn)二分查找。（3）分塊查找(又稱(chēng)索引順序查找)的基本思想：是將原表分成若干塊，各塊內(nèi)部不一定有序，但表中的塊是分塊有序的，并抽取各塊中的最大關(guān)鍵字及其起始位置建立索引表。因?yàn)樗饕硎怯行虻模謮K查找就是先用二分查找或順序查找確定待查結(jié)點(diǎn)在哪一

55、塊，然后在已確定的塊中進(jìn)行順序查找(不能用二分查找，因?yàn)閴K內(nèi)是無(wú)序的)。分塊查找實(shí)際上是兩次查找過(guò)程，它的算法效率介與順序查找和二分查找之間。4.以上三種查找方法的比較如下表：查找算法 存儲(chǔ)結(jié)構(gòu) 優(yōu)點(diǎn) 缺點(diǎn) 適用于 順序查找 順序結(jié)構(gòu)鏈表結(jié)構(gòu) 算法簡(jiǎn)單且對(duì)表的結(jié)構(gòu)無(wú)任何要求 查找效率低 n較小的表的查找和查找較少但改動(dòng)較多的表(用鏈表作存儲(chǔ)結(jié)構(gòu)) 二分查找 順序結(jié)構(gòu) 查找效率高 關(guān)鍵字要有序且只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn) 特別適用于一經(jīng)建立就很少改動(dòng)又經(jīng)常需要查找的線(xiàn)性表 分塊查找 順序結(jié)構(gòu)鏈表 在表中插入或刪除記錄時(shí)就只要在該記錄所屬塊內(nèi)操作，因?yàn)閴K內(nèi)記錄的存放是隨意的，所以插入和刪除比較容易 要

56、增加一個(gè)輔助數(shù)組的存儲(chǔ)空間，并要進(jìn)行將初始表分塊排序運(yùn)算 適用于有分塊特點(diǎn)的記錄，如一個(gè)學(xué)校的學(xué)生登記表可按系號(hào)或班號(hào)分塊。 5.樹(shù)的查找：以樹(shù)做為表的組織形式有一個(gè)好處，就是可以實(shí)現(xiàn)對(duì)動(dòng)態(tài)查找表進(jìn)行高效率的查找。這里講到了二叉排序樹(shù)和B-樹(shù)，以及在這些樹(shù)表上進(jìn)行查找和修改操作的方法。6.二叉排序樹(shù)(BST)又稱(chēng)二叉查找樹(shù)，其定義是：二叉排序樹(shù)要或者是空樹(shù)或者滿(mǎn)足如下性質(zhì)的二叉樹(shù)：1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；3)左、右子樹(shù)本身又是一棵二叉排序樹(shù)。（1）二叉排序樹(shù)實(shí)際上是滿(mǎn)足BST性質(zhì)的二叉樹(shù)。 （2

57、）二叉排序樹(shù)的插入、建立的算法平均時(shí)間性能是O(nlgn),但其執(zhí)行時(shí)間約為堆排序的2至3倍。二叉排序樹(shù)的刪除操作可分三種情況進(jìn)行處理：1)*P是葉子，則直接刪除*P，即將*P的雙親*parent 中指向*P的指針域置空即可。2)*P只有一個(gè)孩子*child,此時(shí)只需將*child和*p的雙親直接連接就可刪去*p.3)*p有兩個(gè)孩子,則將操作轉(zhuǎn)換成刪除*p結(jié)點(diǎn)的中序后繼，在刪去它之前把這個(gè)結(jié)點(diǎn)的數(shù)據(jù)復(fù)制到原來(lái)要?jiǎng)h的結(jié)點(diǎn)位置上就完成了刪除。（3）二叉排序樹(shù)上的查找和二分查找類(lèi)似，它的關(guān)鍵字比較次數(shù)不超過(guò)樹(shù)的深度。在最好的情況下，二叉排序樹(shù)在生成的過(guò)程中比較勻稱(chēng)，此時(shí)的叉排序樹(shù)是平衡的二叉樹(shù)(也就

58、是樹(shù)中任一結(jié)點(diǎn)的左右子樹(shù)的高度大致相同)，它的高度約為1.44lgn，完全平衡的二叉樹(shù)高度約為lgn.在最壞的情況下，輸入的實(shí)例產(chǎn)生的二叉排序樹(shù)的高度將達(dá)到O(n),這種情況應(yīng)當(dāng)避免。7.關(guān)于B-樹(shù)(多路平衡查找樹(shù))。它適合在磁盤(pán)等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。B樹(shù)的階是指B-樹(shù)的度數(shù)，B-樹(shù)的結(jié)點(diǎn)具有k個(gè)孩子時(shí)，該結(jié)點(diǎn)必有k-1(k=2)個(gè)關(guān)鍵字。實(shí)際上B-樹(shù)是二叉排序樹(shù)的推廣，它就是一棵m叉樹(shù)，且滿(mǎn)足四個(gè)性質(zhì)，這些性質(zhì)與二叉排序樹(shù)有相似之處，請(qǐng)仔細(xì)理解之。8.上面的幾種查找方法均是建立在比較關(guān)鍵字的基礎(chǔ)上，因此它們的平均和最壞情況下所需的比較次數(shù)的下界是lgn+O(1)

59、.9.散列技術(shù)：可以無(wú)需任何比較就找到待查關(guān)鍵字，其查找的期望時(shí)間為O(1).散列表的概念：就是將所有可能出現(xiàn)的關(guān)鍵字的集合U(全集)映射到一個(gè)表T0.m-1的下標(biāo)集上，這個(gè)表就是散列表。10.而關(guān)鍵字與這個(gè)表地址之間以什么樣的關(guān)系發(fā)生聯(lián)系呢，這就要通過(guò)一個(gè)函數(shù)來(lái)建立，這個(gè)函數(shù)是以U中的關(guān)鍵字為自變量，以相應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址為函數(shù)值，它就稱(chēng)為散列函數(shù)。將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過(guò)程稱(chēng)為散列。11.根據(jù)某種散列函數(shù)，一個(gè)關(guān)鍵字的散列函數(shù)值是唯一的，但是有可能兩個(gè)或多個(gè)不同關(guān)鍵字的函數(shù)值是相同的，這時(shí)就會(huì)把幾個(gè)結(jié)點(diǎn)存儲(chǔ)到同一個(gè)表位置上，這時(shí)就造成沖突(或碰撞)現(xiàn)象，這兩個(gè)關(guān)鍵字稱(chēng)為該散

60、列函數(shù)的同義詞。要完全(不是安全)避免沖突需滿(mǎn)足兩個(gè)條件，一是關(guān)鍵字集合U不大于散列表長(zhǎng)m，另一個(gè)是選擇合適的散列函數(shù),如果用h(ki)=0)這樣的函數(shù)的話(huà)，看看有什么結(jié)果。 12.通常情況下U總是大大于m的，因此不可能完全避免沖突。沖突的頻繁程度還與表的填滿(mǎn)程度相關(guān)。裝填因子表示表中填入的結(jié)點(diǎn)數(shù)與表長(zhǎng)的比值，通常取1，因?yàn)樵酱螅碓綕M(mǎn)，沖突的機(jī)會(huì)也越大。13.散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻?？纯磆(ki)=0這樣的函數(shù)，簡(jiǎn)單是簡(jiǎn)單，但絕不均勻。14.下面是常見(jiàn)的幾種散列函數(shù)構(gòu)的造方法：（1）平方取中法 （2）除余法：它是用表長(zhǎng)m來(lái)除關(guān)鍵字，取余數(shù)作為散列地址。若選除數(shù)m是關(guān)鍵字的基數(shù)的