數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概括第一章概論數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位,可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)結(jié)構(gòu)的定義:·邏輯結(jié)構(gòu):從邏輯結(jié)構(gòu)上描述數(shù)據(jù),獨(dú)立于計(jì)算機(jī)。·線性結(jié)構(gòu):一對(duì)一關(guān)系?！ぞ€性結(jié)構(gòu):多對(duì)多關(guān)系?！ご鎯?chǔ)結(jié)構(gòu):是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)?！ろ樞虼鎯?chǔ)結(jié)構(gòu):如數(shù)組。·鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):如鏈表。·索引存儲(chǔ)結(jié)構(gòu):·稠密索引:每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。·稀疏索引:每組結(jié)點(diǎn)都有索引項(xiàng)。·散列存儲(chǔ)結(jié)構(gòu):如散列表。·數(shù)據(jù)運(yùn)算?！?duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上,每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合?！こＳ玫挠?檢索、插入、刪除、更新、排序。數(shù)據(jù)類(lèi)型:是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。·結(jié)構(gòu)類(lèi)型:由用戶借助于描述機(jī)制定義,是導(dǎo)出類(lèi)型。抽象數(shù)據(jù)類(lèi)型ADT:·是抽象數(shù)據(jù)的組織和與之的操作。相當(dāng)于在概念層上描述問(wèn)題。·優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu),設(shè)計(jì)一個(gè)好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。算法是一個(gè)良定義的計(jì)算過(guò)程,以一個(gè)或多個(gè)值輸入,并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法的好壞的因素:·算法是正確的;·執(zhí)行算法的時(shí)間;·執(zhí)行算法的存儲(chǔ)空間(主要是輔助存儲(chǔ)空間);·算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度:是某個(gè)算法的時(shí)間耗費(fèi),它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。漸近時(shí)間復(fù)雜度:是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí),該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí),主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān),還與輸入實(shí)例中各元素的取值相關(guān)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為:常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、……k次方階O(n^k)、指數(shù)階O(2^n)?？臻g復(fù)雜度:是某個(gè)算法的空間耗費(fèi),它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。第二章線性表線性表是由n≥0個(gè)數(shù)據(jù)元素組成的有限序列。n=0是空表;非空表,只能有一個(gè)開(kāi)始結(jié)點(diǎn),有且只能有一個(gè)終端結(jié)點(diǎn)。線性表上定義的基本運(yùn)算:·構(gòu)造空表:Initlist(L)·求表長(zhǎng):Listlength(L)·取結(jié)點(diǎn):GetNode(L,i)·查找:LocateNode(L,x)·插入:InsertList(L,x,i)·刪除:Delete(L,i)順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算:LOCa(i)=LOCa(1)+(i-1)*d;(首地址為1)在順序表中實(shí)現(xiàn)的基本運(yùn)算:·插入:平均移動(dòng)結(jié)點(diǎn)次數(shù)為n/2;平均時(shí)間復(fù)雜度均為O(n)?！h除:平均移動(dòng)結(jié)點(diǎn)次數(shù)為(n-1)/2;平均時(shí)間復(fù)雜度均為O(n)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同,為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系,在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí),還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息(即指針或鏈)。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。一個(gè)單鏈表由頭指針的名字來(lái)命名。單鏈表運(yùn)算:·建立單鏈表·頭插法:s->next=head;head=s;生成的順序與輸入順序相反。平均時(shí)間復(fù)雜度均為O(n)?！の膊宸?head=rear=null;if(head=null)head=s;elser->next=s;r=s;平均時(shí)間復(fù)雜度均為O(n)·加頭結(jié)點(diǎn)的算法:對(duì)開(kāi)始結(jié)點(diǎn)的操作無(wú)需特殊處理,統(tǒng)一了空表和非空表?！げ檎摇ぐ葱蛱?hào):與查找位置有關(guān),平均時(shí)間復(fù)雜度均為O(n)?！ぐ粗?與輸入實(shí)例有關(guān),平均時(shí)間復(fù)雜度均為O(n)?！げ迦脒\(yùn)算:p=GetNode(L,i-1);s->next=p->next;p->next=s;平均時(shí)間復(fù)雜度均為O(n)·刪除運(yùn)算:p=GetNode(L,i-1);r=p->next;p->next=r->next;free(r);平均時(shí)間復(fù)雜度均為O(n)單循環(huán)鏈表是一種首尾相接的單鏈表,終端結(jié)點(diǎn)的指針域指向開(kāi)始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時(shí)間都是O(1),不用1遍歷整個(gè)鏈表。雙鏈表就是雙向鏈表,就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為O(1)。順序表和鏈表的比較:·基于空間:·順序表的存儲(chǔ)空間是靜態(tài)分配,存儲(chǔ)密度為1;適于線性表事先確定其大小時(shí)采用?！ゆ湵淼拇鎯?chǔ)空間是動(dòng)態(tài)分配,存儲(chǔ)密度<1;適于線性表長(zhǎng)度變化大時(shí)采用。·基于時(shí)間:·順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu),當(dāng)線性表的操作主要是查找時(shí),宜采用。·以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)?！と舨迦牒蛣h除主要發(fā)生在表的首尾兩端,則宜采用尾指針表示的單循環(huán)鏈表。第三章棧和隊(duì)列棧(Stack)是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表,稱插入、刪除這一端為棧頂,另一端稱為棧底。表中無(wú)元素時(shí)為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的,我們又稱棧為L(zhǎng)IFO表(LastInFirstOut)。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧的基本運(yùn)算有六種:·構(gòu)造空棧:InitStack(S)·判?？?StackEmpty(S)·判棧滿:StackFull(S)·進(jìn)棧:Push(S,x)·退棧:Pop(S)·取棧頂元素:StackTop(S)在順序棧中有“上溢”和“下溢”的現(xiàn)象?！ぁ吧弦纭笔菞ｍ斨羔樦赋鰲５耐饷媸浅鲥e(cuò)狀態(tài)?！ぁ跋乱纭笨梢员硎緱榭諚?因此用來(lái)作為控制轉(zhuǎn)移的條件。順序棧中的基本操作有六種:·構(gòu)造空?！づ袟？铡づ袟M·進(jìn)?！ね藯！とｍ斣劓湕t沒(méi)有上溢的限制,因此進(jìn)棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點(diǎn),只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種:·構(gòu)造空棧·判?？铡みM(jìn)棧·退?！とｍ斣仃?duì)列(Queue)是一種運(yùn)算受限的線性表,插入在表的一端進(jìn)行,而刪除在表的另一端進(jìn)行,允許刪除的一端稱為隊(duì)頭(front),允許插入的一端稱為隊(duì)尾(rear),隊(duì)列的操作原則是先進(jìn)先出的,又稱作FIFO表(FirstInFirstOut).隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有六種:·置空隊(duì):InitQueue(Q)·判隊(duì)空:QueueEmpty(Q)·判隊(duì)滿:QueueFull(Q)·入隊(duì):EnQueue(Q,x)·出隊(duì):DeQueue(Q)·取隊(duì)頭元素:QueueFront(Q)順序隊(duì)列的“假上溢”現(xiàn)象:由于頭尾指針不斷前移,超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念,是把向量空間形成一個(gè)頭尾相接的環(huán)形,這時(shí)隊(duì)列稱循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿,方法有三種:·一種是另設(shè)一個(gè)布爾變量來(lái)判斷;·第二種是少用一個(gè)元素空間,入隊(duì)時(shí)先測(cè)試((rear+1)%m=front)?滿:空;·第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列,一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入(入隊(duì))的操作,在表尾增加一個(gè)尾指針,一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢的問(wèn)題。在鏈隊(duì)列的出隊(duì)算法中,要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。第四章串串是零個(gè)或多個(gè)字符組成的有限序列。·空串:是指長(zhǎng)度為零的串,也就是串中不包含任何字符(結(jié)點(diǎn))?！た瞻状?指串中包含一個(gè)或多個(gè)空格字符的串?！ぴ谝粋€(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串,包含子串的串就稱為主串?！ぷ哟谥鞔械男蛱?hào)就是指子串在主串中首次出現(xiàn)的位置?！た沾侨我獯淖哟?任意串是自身的子串。串分為兩種:·串常量在程序中只能引用不能改變;·串變量的值可以改變。串的基本運(yùn)算有:·求串長(zhǎng)strlen(char*s)·串復(fù)制strcpy(char*to,char*from)·串聯(lián)接strcat(char*to,char*from)·串比較charcmp(char*s1,char*s2)·字符定位strchr(char*s,charc)串是特殊的線性表(結(jié)點(diǎn)是字符),所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類(lèi)似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。順序串又可按存儲(chǔ)分配的不同分為:·靜態(tài)存儲(chǔ)分配:直接用定長(zhǎng)的字符數(shù)組來(lái)定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快,但不適合插入、鏈接操作。·動(dòng)態(tài)存儲(chǔ)分配:是在定義串時(shí)不分配存儲(chǔ)空間,需要使用時(shí)按所需串的長(zhǎng)度分配存儲(chǔ)單元。串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值,串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決“存儲(chǔ)密度”低的狀況,可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符,即結(jié)點(diǎn)的大小。順序串上子串定位的運(yùn)算:又稱串的“模式匹配”或“串匹配”,是在主串中查找出子串出現(xiàn)的位置。在串匹配中,將主串稱為目標(biāo)(串),子串稱為模式(串)。這是比較容易理解的,串匹配問(wèn)題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(shí)間復(fù)雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)第五章多維數(shù)組數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有:·行優(yōu)先順序,也就是把數(shù)組逐行依次排列。PASCAL、C·列優(yōu)先順序,就是把數(shù)組逐列依次排列。FORTRAN地址的計(jì)算方法:·按行優(yōu)先順序排列的數(shù)組:LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d.·按列優(yōu)先順序排列的數(shù)組:LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d.矩陣的壓縮存儲(chǔ):為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間;對(duì)零元素不分配空間。特殊矩陣的概念:所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。稀疏矩陣的概念:一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù),則該矩陣稱為稀疏矩陣。特殊矩陣的類(lèi)型:·對(duì)稱矩陣:滿足a(ij)=a(ji)。元素總數(shù)n(n+1)/2.I=max(i,j),J=min(i,j),LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d.·三角矩陣:·上三角陣:k=i*(2n-i+1)/2+j-i,LOCa(ij)=LOC(sa[0])+k*d.·下三角陣:k=i*(i+1)/2+j,LOCa(ij)=LOC(sa[0])+k*d.·對(duì)角矩陣:k=2i+j,LOCa(ij)=LOC(sa[0])+k*d.稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起,用這些結(jié)點(diǎn)組成的一個(gè)線性表來(lái)表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置,即帶行表的三元組表。第六章樹(shù)樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合,非空時(shí)必須滿足:只有一個(gè)稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)形成m個(gè)不相交的子集,并稱根的子樹(shù)。根是開(kāi)始結(jié)點(diǎn);結(jié)點(diǎn)的子樹(shù)數(shù)稱度;度為0的結(jié)點(diǎn)稱葉子(終端結(jié)點(diǎn));度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)(非終端結(jié)點(diǎn));除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn);有序樹(shù)是子樹(shù)有左,右之分的樹(shù);無(wú)序樹(shù)是子樹(shù)沒(méi)有左,右之分的樹(shù);森林是m個(gè)互不相交的樹(shù)的集合;樹(shù)的四種不同表示方法:·樹(shù)形表示法;·嵌套集合表示法;·凹入表示法·廣義表表示法。二叉樹(shù)的定義:是n≥0個(gè)結(jié)點(diǎn)的有限集,它是空集(n=0)或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)不是樹(shù)的特殊情形,與度數(shù)為2的有序樹(shù)不同。二叉樹(shù)的4個(gè)重要性質(zhì):·二叉樹(shù)上第i層上的結(jié)點(diǎn)數(shù)目最多為2^(i-1)(i≥1)。;·深度為k的二叉樹(shù)至多有(2^k)-1個(gè)結(jié)點(diǎn)(k≥1);·在任意一棵二叉樹(shù)中,若終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0=n2+1;·具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int(log2n)+1.滿二叉樹(shù)是一棵深度為k,結(jié)點(diǎn)數(shù)為(2^k)-1的二叉樹(shù);完全二叉樹(shù)是滿二叉樹(shù)在最下層自右向左去處部分結(jié)點(diǎn);二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹(shù)的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。(存儲(chǔ)前先將其畫(huà)成完全二叉樹(shù))樹(shù)的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild,把所有BinTNode類(lèi)型的結(jié)點(diǎn),加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域,n+1個(gè)空指針。根據(jù)訪問(wèn)結(jié)點(diǎn)的次序不同可得三種遍歷:先序遍歷(前序遍歷或先根遍歷),中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。時(shí)間復(fù)雜度為O(n)。利用二叉鏈表中的n+1個(gè)空指針域來(lái)存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針,這些附加的指針就稱為“線索”,加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效,但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒(méi)有什么作用。樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換是唯一對(duì)應(yīng)的。轉(zhuǎn)換方法:·樹(shù)變二叉樹(shù):兄弟相連,保留長(zhǎng)子的連線。·二叉樹(shù)變樹(shù):結(jié)點(diǎn)的右孩子與其雙親連?！ど肿兌鏄?shù):樹(shù)變二叉樹(shù),各個(gè)樹(shù)的根相連。樹(shù)的存儲(chǔ)結(jié)構(gòu):·有雙親鏈表表示法:結(jié)點(diǎn)data|parent,對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便,但不適于求指定結(jié)點(diǎn)的孩子及后代?！ず⒆渔湵肀硎痉?為樹(shù)中每個(gè)結(jié)點(diǎn)data|next設(shè)置一個(gè)孩子鏈表firstchild,并將data|firstchild存放在一個(gè)向量中?！るp親孩子鏈表表示法:將雙親鏈表和孩子鏈表結(jié)合。·孩子兄弟鏈表表示法:結(jié)點(diǎn)結(jié)構(gòu)leftmostchild|data|rightsibing,附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。樹(shù)的前序遍歷與相對(duì)應(yīng)的二叉樹(shù)的前序遍歷一致;樹(shù)的后序遍歷與相對(duì)應(yīng)的二叉樹(shù)的中序遍歷一致。樹(shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹(shù)的帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就稱為最優(yōu)二叉樹(shù)(即哈夫曼樹(shù))。在葉子的權(quán)值相同的二叉樹(shù)中,完全二叉樹(shù)的路徑長(zhǎng)度最短。哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn),共有2n-1個(gè)結(jié)點(diǎn),沒(méi)有度為1的結(jié)點(diǎn),這類(lèi)樹(shù)又稱為嚴(yán)格二叉樹(shù)。變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短,而頻度低的字符編碼長(zhǎng),但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個(gè)碼無(wú)法在解碼時(shí)確定是哪一個(gè),所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴,這種碼稱為前綴碼(其實(shí)是非前綴碼)。哈夫曼樹(shù)的應(yīng)用最廣泛地是在編碼技術(shù)上,它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易,只要畫(huà)好了哈夫曼樹(shù),按分支情況在左路徑上寫(xiě)代碼0,右路徑上寫(xiě)代碼1,然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。第七章圖圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)(頂點(diǎn))的前趨和后繼的個(gè)數(shù)都是沒(méi)有限制的,即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。圖GraphG=(V,E),V是頂點(diǎn)的有窮非空集合,E是頂點(diǎn)偶對(duì)的有窮集。有向圖Digraph:每條邊有方向;無(wú)向圖Undigraph:每條邊沒(méi)有方向。有向完全圖:具有n*(n-1)條邊的有向圖;無(wú)向完全圖:具有n*(n-1)/2條邊的無(wú)向圖;有根圖:有一個(gè)頂點(diǎn)有路徑到達(dá)其它頂點(diǎn)的有向圖;簡(jiǎn)單路徑:是經(jīng)過(guò)頂點(diǎn)不同的路徑;簡(jiǎn)單回路是開(kāi)始和終端重的簡(jiǎn)單路徑;網(wǎng)絡(luò):是帶權(quán)的圖。圖的存儲(chǔ)結(jié)構(gòu):·鄰接矩陣表示法:用一個(gè)n階方陣來(lái)表示圖的結(jié)構(gòu)是唯一的,適合稠密圖?！o(wú)向圖:鄰接矩陣是對(duì)稱的。·有向圖:行是出度,列是入度。建立鄰接矩陣算法的時(shí)間是O(n+n^2+e),其時(shí)間復(fù)雜度為O(n^2)·鄰接表表示法:用頂點(diǎn)表和鄰接表構(gòu)成不是唯一的,適合稀疏圖。·頂點(diǎn)表結(jié)構(gòu)vertex|firstedge,指針域存放鄰接表頭指針?！む徑颖?用頭指針確定。·無(wú)向圖稱邊表;·有向圖又分出邊表和逆鄰接表;·鄰接表結(jié)點(diǎn)結(jié)構(gòu)為adjvex|next,時(shí)間復(fù)雜度為O(n+e)。,空間復(fù)雜度為O(n+e)。。圖的遍歷:·深度優(yōu)先遍歷:借助于鄰接矩陣的列。使用棧保存已訪問(wèn)結(jié)點(diǎn)?！V度優(yōu)先遍歷:借助于鄰接矩陣的行。使用隊(duì)列保存已訪問(wèn)結(jié)點(diǎn)。生成樹(shù)的定義:若從圖的某個(gè)頂點(diǎn)出發(fā),可以系統(tǒng)地訪問(wèn)到圖中所有頂點(diǎn),則遍歷時(shí)經(jīng)過(guò)的邊和圖的所有頂點(diǎn)構(gòu)成的子圖稱作該圖的生成樹(shù)。最小生成樹(shù):圖的生成樹(shù)不唯一,從不同的頂點(diǎn)出發(fā)可得到不同的生成樹(shù),把權(quán)值最小的生成樹(shù)稱為最小生成樹(shù)(MST)。構(gòu)造最小生成樹(shù)的算法:·Prim算法的時(shí)間復(fù)雜度為O(n^2)與邊數(shù)無(wú)關(guān)適于稠密圖。·Kruskal算法的時(shí)間復(fù)雜度為O(lge),主要取決于邊數(shù),較適合于稀疏圖。最短路徑的算法:·Dijkstra算法,時(shí)間復(fù)雜度為O(n^2)?！ゎ?lèi)似于prim算法。拓?fù)渑判?是將有向無(wú)環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列,若<u,v>∈E(G),則在線性序列u在v之前,這種線性序列稱為拓?fù)湫蛄小Ｍ負(fù)渑判蛞灿袃煞N方法:·無(wú)前趨的頂點(diǎn)優(yōu)先,每次輸出一個(gè)無(wú)前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊,最后得到的序列即拓?fù)湫蛄??！o(wú)后繼的結(jié)點(diǎn)優(yōu)先:每次輸出一個(gè)無(wú)后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊,最后得到的序列是逆拓?fù)湫蛄?。第八章排序記錄中可用某一?xiàng)來(lái)標(biāo)識(shí)一個(gè)記錄,則稱為關(guān)鍵字項(xiàng),該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。排序是使文件中的記錄按關(guān)鍵字遞增(或遞減)次序排列起來(lái)?！せ静僮?比較關(guān)鍵字大小;改變指向記錄的指針或移動(dòng)記錄。·存儲(chǔ)結(jié)構(gòu):順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變,則稱這種排序方法是穩(wěn)定的,否則排序算法是不穩(wěn)定的。排序過(guò)程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為“內(nèi)部排序”(內(nèi)排序),反之,若存在數(shù)據(jù)的內(nèi)外存交換,則稱之為外排序。內(nèi)部排序方法可分五類(lèi):插入排序、選擇排序、交換排序、歸并排序和分配排序。評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條:執(zhí)行時(shí)間和所需的輔助空間,另外算法的復(fù)雜程序也是要考慮的一個(gè)因素。插入排序:·直接插入排序:·逐個(gè)向前插入到合適位置。·哨兵(監(jiān)視哨)有兩個(gè)作用:·作為臨變量存放R[i]·是在查找循環(huán)中用來(lái)監(jiān)視下標(biāo)變量j是否越界?！ぶ苯硬迦肱判蚴蔷偷氐姆€(wěn)定排序。時(shí)間復(fù)雜度為O(n^2),比較次數(shù)為(n+2)(n-1)/2;移動(dòng)次數(shù)為(n+4)(n-1)/2;·希爾排序:·等間隔的數(shù)據(jù)比較并按要求順序排列,最后間隔為1.·希爾排序是就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O(n^1.25),比較次數(shù)為(n^1.25);移動(dòng)次數(shù)為(1.6n^1.25);交換排序:·冒泡排序:·自下向上確定最輕的一個(gè)。·自上向下確定最重的一個(gè)?！ぷ韵孪蛏洗_定最輕的一個(gè),后自上向下確定最重的一個(gè)?！っ芭菖判蚴蔷偷氐姆€(wěn)定排序。時(shí)間復(fù)雜度為O(n^2),比較次數(shù)為n(n-1)/2;移動(dòng)次數(shù)為3n(n-1)/2;·快速排序:·以第一個(gè)元素為參考基準(zhǔn),設(shè)定、動(dòng)兩個(gè)指針,發(fā)生交換后指針交換位置,直到指針重合。重復(fù)直到排序完成?！た焖倥判蚴欠蔷偷氐牟环€(wěn)定排序。時(shí)間復(fù)雜度為O(nlog2n),比較次數(shù)為n(n-1)/2;選擇排序:·直接選擇排序:·選擇最小的放在比較區(qū)前?！ぶ苯舆x擇排序就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O(n^2)。比較次數(shù)為n(n-1)/2;·堆排序·建堆:按層次將數(shù)據(jù)填入完全二叉樹(shù),從int(n/2)處向前逐個(gè)調(diào)整位置。·然后將樹(shù)根與最后一個(gè)葉子交換值并斷開(kāi)與樹(shù)的連接并重建堆,直到全斷開(kāi)。·堆排序是就地不穩(wěn)定的排序,時(shí)間復(fù)雜度為O(nlog2n),不適宜于記錄數(shù)較少的文件。歸并排序:·先兩個(gè)一組排序,形成(n+1)/2組,再將兩組并一組,直到剩下一組為止?！w并排序是非就地穩(wěn)定排序,時(shí)間復(fù)雜度是O(nlog2n),分配排序:·箱排序:·按關(guān)鍵字的取值范圍確定箱子數(shù),按關(guān)鍵字投入箱子,鏈接所有非空箱?！は渑判虻钠骄鶗r(shí)間復(fù)雜度是線性的O(n)?！せ鶖?shù)排序:·從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序?！せ鶖?shù)排序是非就穩(wěn)定的排序,時(shí)間復(fù)雜度是O(d*n+d*rd)。各種排序方法的比較和選擇:·待排序的記錄數(shù)目n;n較大的要用時(shí)間復(fù)雜度為O(nlog2n)的排序方法;·記錄的大小(規(guī)模);記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu),而快速排序和堆排序在鏈表上難于實(shí)現(xiàn);·關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài);·對(duì)穩(wěn)定性的要求;·語(yǔ)言工具的條件;·存儲(chǔ)結(jié)構(gòu);·時(shí)間和輔助空間復(fù)雜度。第九章查找查找的同時(shí)對(duì)表做修改操作(如插入或刪除)則相應(yīng)的表稱之為動(dòng)態(tài)查找表,否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長(zhǎng)度ASL)。線性表查找的方法:·順序查找:逐個(gè)查找,ASL=(n+1)/2;·二分查找:取中點(diǎn)int(n/2)比較,若小就比左區(qū)間,大就比右區(qū)間。用二叉判定樹(shù)表示。ASL=(∑(每層結(jié)點(diǎn)數(shù)*層數(shù)))/N.·分塊查找。要求“分塊有序”,將表分成若干塊內(nèi)部不一定有序,并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表。二叉排序樹(shù)(BST)定義是:二叉排序樹(shù)是空樹(shù)或者滿足如下性質(zhì)的二叉樹(shù):·若它的左子樹(shù)非空,則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值;·若它的右子樹(shù)非空,則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;·左、右子樹(shù)本身又是一棵二叉排序樹(shù)。二叉排序樹(shù)的插入、建立、刪除的算法平均時(shí)間性能是O(nlog2n)。二叉排序樹(shù)的刪除操作可分三種情況進(jìn)行處理:·*P是葉子,則直接刪除*P,即將*P的雙親*parent中指向*P的指針域置空即可?！?P只有一個(gè)孩子*child,此時(shí)只需將*child和*p的雙親直接連接就可刪去*p.·*p有兩個(gè)孩子,則先將*p結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到*p,刪除中序后繼結(jié)點(diǎn)。關(guān)于B-樹(shù)(多路平衡查找樹(shù))。它適合在磁盤(pán)等直接存取設(shè)備上組織動(dòng)態(tài)的查找表,是一種外查找算法。建立的方式是從下向上拱起。散列技術(shù):將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過(guò)程稱為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn):簡(jiǎn)單和均勻。常見(jiàn)的散列函數(shù)構(gòu)的造方法:·平方取中法:hash=int((x^2)%100)·除余法:表長(zhǎng)為m,hash=x%m·相乘取整法:hash=int(m*(x*A-int(x*A));A=0.618·隨機(jī)數(shù)法:hash=random(x)。處理沖突的方法:·開(kāi)放定址法:·一般形式為hi=(h(key)+di)%m1≤i≤m-1,開(kāi)放定址法要求散列表的裝填因子α≤1.·開(kāi)放定址法類(lèi)型:·線性探查法:address=(hash(x)+i)%m;·二次探查法:address=(hash(x)+i^2)%m;·雙重散列法:address=(hash(x)+i*hash(y))%m;·拉鏈法:·是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中?！だ湻ǖ膬?yōu)點(diǎn):·拉鏈法處理沖突簡(jiǎn)單,且無(wú)堆積現(xiàn)象;·鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的適于無(wú)法確定表長(zhǎng)的情況;·拉鏈法中α可以大于1,結(jié)點(diǎn)較大時(shí)其指針域可忽略,因此節(jié)省空間;·拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。·拉鏈法也有缺點(diǎn):當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí),用拉鏈法中的指針域也要占用額外空間,還是開(kāi)放定址法省空間。第十章排序10.1排序的基本概念10.2插入排序10.3選擇排序10.4交換排序本章主要知識(shí)點(diǎn):排序的基本概念和衡量排序算法優(yōu)劣的標(biāo)準(zhǔn),其中衡量標(biāo)準(zhǔn)有算法的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性直接插入排序,希爾排序直接選擇排序,堆排序冒泡排序,快速排序10.1排序的基本概念1.排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過(guò)程。2.排序的目的:便于查找。3.關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域,排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的。關(guān)鍵字分主關(guān)鍵字和次關(guān)鍵字兩種。對(duì)要排序的數(shù)據(jù)元素集合來(lái)說(shuō),如果關(guān)鍵字滿足數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的值也一定不同,這樣的關(guān)鍵字稱為主關(guān)鍵字。不滿足主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字。4.排序的種類(lèi):分為內(nèi)部排序和外部排序兩大類(lèi)。若待排序記錄都在內(nèi)存中,稱為內(nèi)部排序;若待排序記錄一部分在內(nèi)存,一部分在外存,則稱為外部排序。注:外部排序時(shí),要將數(shù)據(jù)分批調(diào)入內(nèi)存來(lái)排序,中間結(jié)果還要及時(shí)放入外存,顯然外部排序要復(fù)雜得多。5.排序算法好壞的衡量標(biāo)準(zhǔn):(1)時(shí)間復(fù)雜度——它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。(2)空間復(fù)雜度——算法中使用的內(nèi)存輔助空間的多少。(3)穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等,但排序后A、B的先后次序保持不變,則稱這種排序算法是穩(wěn)定的。10.2插入排序插入排序的基本思想是:每步將一個(gè)待排序的對(duì)象,按其關(guān)鍵字大小,插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上,直到對(duì)象全部插入為止。簡(jiǎn)言之,邊插入邊排序,保證子序列中隨時(shí)都是排好序的。常用的插入排序有:直接插入排序和希爾排序兩種。10.2.1直接插入排序1、其基本思想是:順序地把待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。例1:關(guān)鍵字序列T=(13,6,3,31,9,27,5,11),請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列。初始關(guān)鍵字序列:【13】,6,3,31,9,27,5,11第一次排序:【6,13】,3,31,9,27,5,11第二次排序:【3,6,13】,31,9,27,5,11第三次排序:【3,6,13,31】,9,27,5,11第四次排序:【3,6,9,13,31】,27,5,11第五次排序:【3,6,9,13,27,31】,5,11第六次排序:【3,5,6,9,13,27,31】,11第七次排序:【3,5,6,9,11,13,27,31】注:方括號(hào)[]中為已排序記錄的關(guān)鍵字,下劃?rùn)M線的關(guān)鍵字表示它對(duì)應(yīng)的記錄后移一個(gè)位置。2.直接插入排序算法publicstaticvoidinsertSort(int[]a){inti,j,temp;intn=a.Length;for(i=0;i<n-1;i++){temp=a[i+1];j=i;while(j>-1&&temp<a[j]){a[j+1]=a[j];j--;}a[j+1]=temp;}}初始關(guān)鍵字序列:【13】,6,3,31,9,27,5,11第一次排序:【6,13】,3,31,9,27,5,11第二次排序:【3,6,13】,31,9,27,5,113、直接插入排序算法分析(1)時(shí)間效率:當(dāng)數(shù)據(jù)有序時(shí),執(zhí)行效率最好,此時(shí)的時(shí)間復(fù)雜度為O(n);當(dāng)數(shù)據(jù)基本反序時(shí),執(zhí)行效率最差,此時(shí)的時(shí)間復(fù)雜度為O(n2)。所以當(dāng)數(shù)據(jù)越接近有序,直接插入排序算法的性能越好。(2)空間效率:僅占用1個(gè)緩沖單元——O(1)(3)算法的穩(wěn)定性:穩(wěn)定8.2.2希爾(shell)排序(又稱縮小增量排序)1、基本思想:把整個(gè)待排序的數(shù)據(jù)元素分成若干個(gè)小組,對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序;小組的個(gè)數(shù)逐次縮小,當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程結(jié)束。2、技巧:小組的構(gòu)成不是簡(jiǎn)單地“逐段分割”,而是將相隔某個(gè)增量d的記錄組成一個(gè)小組,讓增量d逐趟縮短(例如依次取5,3,1),直到d=1為止。3、優(yōu)點(diǎn):讓關(guān)鍵字值小的元素能很快前移,且序列若基本有序時(shí),再用直接插入排序處理,時(shí)間效率會(huì)高很多。例2:設(shè)待排序的序列中有12個(gè)記錄,它們的關(guān)鍵字序列T=(65,34,25,87,12,38,56,46,14,77,92,23),請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。publicstaticvoidshellSort(int[]a,int[]d,intnumOfD){inti,j,k,m,span;inttemp;intn=a.Length;for(m=0;m<numOfD;m++){//共numOfD次循環(huán)span=d[m];//取本次的增量值for(k=0;k<span;k++){//共span個(gè)小組for(i=k;i<n-span;i=i+span){temp=a[i+span];j=i;while(j>-1&&temp<a[j]){a[j+span]=a[j];j=j-span;}a[j+span]=temp;}}}}算法分析:開(kāi)始時(shí)d的值較大,子序列中的對(duì)象較少,排序速度較快;隨著排序進(jìn)展,d值逐漸變小,子序列中對(duì)象個(gè)數(shù)逐漸變多,由于前面工作的基礎(chǔ),大多數(shù)記錄已基本有序,所以排序速度仍然很快。時(shí)間效率:O(n(log2n)2)空間效率:O(1)——因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性:不穩(wěn)定練習(xí):1.欲將序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的關(guān)鍵碼按字母升序重排,則初始d為4的希爾排序一趟的結(jié)果是?答:原始序列:Q,H,C,Y,P,A,M,S,R,D,F,Xshell一趟后:P,A,C,S,Q,D,F,X,R,H,M,Y2.以關(guān)鍵字序列(256,301,751,129,937,863,742,694,076,438)為例,寫(xiě)出執(zhí)行希爾排序(取d=5,3,1)算法的各趟排序結(jié)束時(shí),關(guān)鍵字序列的狀態(tài)。解:原始序列:256,301,751,129,937,863,742,694,076,438希爾排序第一趟d=5256301694076438863742751129937第二趟d=3076301129256438694742751863937第三趟d=107612925630143869474275186393710.3選擇排序選擇排序的基本思想是:每次從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小(或最大)的數(shù)據(jù)元素放到數(shù)據(jù)元素集合的最前(或最后),數(shù)據(jù)元素集合不斷縮小,當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序結(jié)束。常用的選擇排序算法:(1)直接選擇排序(2)堆排序10.3.1直接選擇排序1、其基本思想每經(jīng)過(guò)一趟比較就找出一個(gè)最小值,與待排序列最前面的位置互換即可。(即從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置;然后從不包括第一個(gè)位置的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)集合中的第二個(gè)數(shù)據(jù)元素交換位置;如此重復(fù),直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。)2、優(yōu)缺點(diǎn)優(yōu)點(diǎn):實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn):每趟只能確定一個(gè)元素,表長(zhǎng)為n時(shí)需要n-1趟例3:關(guān)鍵字序列T=(21,25,49,25*,16,08),請(qǐng)給出直接選擇排序的具體實(shí)現(xiàn)過(guò)程。原始序列:21,25,49,25*,16,08第1趟08,25,49,25*,16,21第2趟08,16,49,25*,25,21第3趟08,16,21,25*,25,49第4趟08,16,21,25*,25,49第5趟08,16,21,25*,25,49publicstaticvoidselectSort(int[]a){inti,j,small;inttemp;intn=a.Length;for(i=0;i<n-1;i++){small=i;//設(shè)第i個(gè)數(shù)據(jù)元素最小for(j=i+1;j<n;j++)//尋找最小的數(shù)據(jù)元素if(a[j]<a[small])small=j;//記住最小元素的下標(biāo)if(small!=i){//當(dāng)最小元素的下標(biāo)不為i時(shí)交換位置temp=a[i];a[i]=a[small];a[small]=temp;}}}3、算法分析時(shí)間效率:O(n2)——雖移動(dòng)次數(shù)較少,但比較次數(shù)仍多。空間效率:O(1)——沒(méi)有附加單元(僅用到1個(gè)temp)算法的穩(wěn)定性:不穩(wěn)定4、穩(wěn)定的直接選擇排序算法例:關(guān)鍵字序列T=(21,25,49,25*,16,08),請(qǐng)給出穩(wěn)定的直接選擇排序的具體實(shí)現(xiàn)過(guò)程。原始序列:21,25,49,25*,16,08第1趟08,21,25,49,25*,16第2趟08,16,21,25,49,25*第3趟08,16,21,25,49,25*第4趟08,16,21,25,49,25*第5趟08,16,21,25,25*,49publicstaticvoidselectSort2(int[]a){inti,j,small;inttemp;intn=a.Length;for(i=0;i<n-1;i++){small=i;for(j=i+1;j<n;j++){//尋找最小的數(shù)據(jù)元素if(a[j]<a[small])small=j;//記住最小元素的下標(biāo)}if(small!=i){temp=a[small];for(j=small;j>i;j--)//把該區(qū)段尚未排序元素依次后移a[j]=a[j-1];a[i]=temp;//插入找出的最小元素}}}8.3.2堆排序1.什么是堆?2.怎樣建堆?3.怎樣堆排序?堆的定義:設(shè)有n個(gè)數(shù)據(jù)元素的序列k0,k1,…,kn-1,當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí),稱之為堆。解釋:如果讓滿足以上條件的元素序列(k0,k1,…,kn-1)順次排成一棵完全二叉樹(shù),則此樹(shù)的特點(diǎn)是:樹(shù)中所有結(jié)點(diǎn)的值均大于(或小于)其左右孩子,此樹(shù)的根結(jié)點(diǎn)(即堆頂)必最大(或最小)。例4:有序列T1=(08,25,49,46,58,67)和序列T2=(91,85,76,66,58,67,55),判斷它們是否“堆”?2.怎樣建堆?步驟:從第一個(gè)非終端結(jié)點(diǎn)開(kāi)始往前逐步調(diào)整,讓每個(gè)雙親大于(或小于)子女,直到根結(jié)點(diǎn)為止。終端結(jié)點(diǎn)(即葉子)沒(méi)有任何子女,無(wú)需單獨(dú)調(diào)整例:關(guān)鍵字序列T=(21,25,49,25*,16,08),請(qǐng)建最大堆。解:為便于理解,先將原始序列畫(huà)成完全二叉樹(shù)的形式:這樣可以很清晰地從(n-1-1)/2開(kāi)始調(diào)整。publicstaticvoidcreateHeap(int[]a,intn,inth){inti,j,flag;inttemp;i=h;j=2*i+1;//j為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的下標(biāo)temp=a[i];flag=0;while(j<n&&flag!=1){//尋找左右孩子結(jié)點(diǎn)中的較大者,j為其下標(biāo)if(j<n-1&&a[j]<a[j+1])j++;if(temp>=a[j])//a[i]>=a[j]flag=1;//標(biāo)記結(jié)束篩選條件else{//否則把a(bǔ)[j]上移a[i]=a[j];i=j;j=2*i+1;}}a[i]=temp;}利用上述createHeap(a,n,h)函數(shù),初始化創(chuàng)建最大堆的過(guò)程就是從第一個(gè)非葉子結(jié)點(diǎn)a[i]開(kāi)始,到根結(jié)點(diǎn)a[0]為止,循環(huán)調(diào)用createHeap(a,n,h)的過(guò)程。初始化創(chuàng)建最大堆算法如下:publicstaticvoidinitCreateHeap(int[]a){intn=a.Length;for(inti=(n-1-1)/2;i>=0;i--)createHeap(a,n,i);}3.怎樣進(jìn)行整個(gè)序列的堆排序?*基于初始堆進(jìn)行堆排序的算法步驟:堆的第一個(gè)對(duì)象a[0]具有最大的關(guān)鍵碼,將a[0]與a[n-1]對(duì)調(diào),把具有最大關(guān)鍵碼的對(duì)象交換到最后;再對(duì)前面的n-1個(gè)對(duì)象,使用堆的調(diào)整算法,重新建立堆(調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義)。結(jié)果具有次最大關(guān)鍵碼的對(duì)象又上浮到堆頂,即a[0]位置;再對(duì)調(diào)a[0]和a[n-2],然后對(duì)前n-2個(gè)對(duì)象重新調(diào)整,…如此反復(fù),最后得到全部排序好的對(duì)象序列。例5:對(duì)剛才建好的最大堆進(jìn)行排序:publicstaticvoidheapSort(int[]a){inttemp;intn=a.Length;initCreateHeap(a);//初始化創(chuàng)建最大堆for(inti=n-1;i>0;i--){//當(dāng)前最大堆個(gè)數(shù)每次遞減1//把堆頂a[0]元素和當(dāng)前最大堆的最后一個(gè)元素交換temp=a[0];a[0]=a[i];a[i]=temp;createHeap(a,i,0);//調(diào)整根結(jié)點(diǎn)滿足最大堆}}4、堆排序算法分析:時(shí)間效率:O(nlog2n)?？臻g效率:O(1)。穩(wěn)定性:不穩(wěn)定。練習(xí)1:以下序列是堆的是(){75,65,30,15,25,45,20,10}B.{75,65,45,10,30,25,20,15}C.{75,45,65,30,15,25,20,10}D.{75,45,65,10,25,30,20,15}練習(xí)2:有一組數(shù)據(jù){15,9,7,8,20,1,7*,4},建成的最小堆為()。A.{1,4,8,9,20,7,15,7*}B.{1,7,15,7*,4,8,20,9}C.{1,4,7,8,20,15,7*,9}D.以上都不對(duì)練習(xí)3:已知序列{503,87,512,61,908,170,897,275,653,462},寫(xiě)出采用堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)的排序過(guò)程。排序好的序列為:61,87,170,275,462,503,512,653,897,90810.4交換排序交換排序的基本思想是:利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。交換排序的主要算法有:1)冒泡排序2)快速排序10.4.1冒泡排序1、基本思路:每趟不斷將記錄兩兩比較,并按“前小后大”(或“前大后小”)規(guī)則交換。2、優(yōu)點(diǎn):每趟結(jié)束時(shí),不僅能擠出一個(gè)最大值到最后面位置,還能同時(shí)部分理順其他元素;一旦下趟沒(méi)有交換發(fā)生,還可以提前結(jié)束排序。例:關(guān)鍵字序列T=(21,25,49,25*,16,08),請(qǐng)按從小到大的順序,寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。初態(tài):21,25,49,25*,16,08第1趟21,25,25*,16,08,49第2趟21,25,16,08,25*,49第3趟21,16,08,25,25*,49第4趟16,08,21,25,25*,49第5趟08,16,21,25,25*,493、冒泡排序算法publicstaticvoidbubbleSort(int[]a){inti,j,flag=1;inttemp;intn=a.Length;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}4、冒泡排序的算法分析時(shí)間效率:O(n2)—因?yàn)橐紤]最壞情況(數(shù)據(jù)元素全部逆序),當(dāng)然最好情況是數(shù)據(jù)元素已全部排好序,此時(shí)循環(huán)n-1次,時(shí)間復(fù)雜度為O(n)空間效率:O(1)—只在交換時(shí)用到一個(gè)緩沖單元穩(wěn)定性:穩(wěn)定—25和25*在排序前后的次序未改變練習(xí):關(guān)鍵字序列T=(31,15,9,25,16,28),請(qǐng)按從小到大的順序,寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。初態(tài):31,15,9,25,16,28第1趟15,9,25,16,28,31第2趟9,15,16,25,28,31第3趟9,15,16,25,28,311、基本思想:設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素,low為數(shù)組的低端下標(biāo),high為數(shù)組的高端下標(biāo),從數(shù)組a中任取一個(gè)元素(通常取a[low])做為標(biāo)準(zhǔn)元素,以該標(biāo)準(zhǔn)元素調(diào)整數(shù)組a中其他各個(gè)元素的位置,使排在標(biāo)準(zhǔn)元素前面的元素均小于標(biāo)準(zhǔn)元素,排在標(biāo)準(zhǔn)元素后面的均大于或等于標(biāo)準(zhǔn)元素。這樣一次排序過(guò)程結(jié)束后,一方面將標(biāo)準(zhǔn)元素放在了未來(lái)排好序的數(shù)組中該標(biāo)準(zhǔn)元素應(yīng)位于的