第二章 數(shù)據(jù)結(jié)構(gòu)與算法

第二章數(shù)據(jù)結(jié)構(gòu)與算法2.1基本要求1.學(xué)習(xí)目的與要求數(shù)據(jù)結(jié)構(gòu)主要研究把具有一定邏輯關(guān)係的一批數(shù)據(jù)按某種存儲(chǔ)方式存放在計(jì)算機(jī)的存儲(chǔ)器中,并在這批數(shù)據(jù)上定義一系列操作.如何操作就是算法問(wèn)題,算法與數(shù)據(jù)結(jié)構(gòu)是相互聯(lián)繫的.算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的,合理的數(shù)據(jù)結(jié)構(gòu)可以使算法簡(jiǎn)單高效.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的目的,是理解和掌握各種數(shù)據(jù)結(jié)構(gòu)的定義及基本操作的實(shí)現(xiàn),理解掌握典型的算法思想,算法設(shè)計(jì)方法和計(jì)算算法的時(shí)間複雜度.2.本章重點(diǎn)⑴線性表,順序表和鏈錶,掌握線性表的概念,兩種存儲(chǔ)結(jié)構(gòu),優(yōu)缺點(diǎn)及兩種存儲(chǔ)結(jié)構(gòu)上的基本操作⑵棧與隊(duì)列,棧和隊(duì)列的概念,順序棧,鏈棧的操作,棧的應(yīng)用,循環(huán)隊(duì)列,循環(huán)鏈隊(duì)列的操作⑶串的基本運(yùn)算和模式匹配,串的基本運(yùn)算的含義,瞭解模式匹配算法和時(shí)間複雜度⑷多維數(shù)組和廣義表,多維數(shù)組及特殊矩陣的地址公式,廣義表的運(yùn)算和存儲(chǔ)⑸樹和二叉樹,樹,二叉樹的定義,術(shù)語(yǔ),二叉樹的性質(zhì),存儲(chǔ),遍歷,應(yīng)用,線索二叉樹的概念,樹與二叉樹的關(guān)係⑹圖的存儲(chǔ)及其操作,圖的定義,術(shù)語(yǔ),圖的存儲(chǔ),圖的遍歷,圖的操作(最小生成樹,拓?fù)渑判?關(guān)鍵路徑,最短路徑)⑺表和樹的查找,表和樹的概念,平均比較次數(shù),二叉排序樹和平衡二叉樹的插入,刪除,瞭解B-樹的定義⑻Hash技術(shù),哈希表構(gòu)造,解決衝突的方法及哈希表的查找⑼排序算法,直接插入排序,冒泡排序,簡(jiǎn)單選擇排序,快速排序,堆排序,歸并排序和希爾排序算法和時(shí)間發(fā)雜度,瞭解基數(shù)排序,外排序的概念和算法⑽算法設(shè)計(jì)方法,分治法,遞推法,貪心法,回溯法,動(dòng)態(tài)規(guī)劃發(fā)和分支界法2.2基本內(nèi)容2.2.1數(shù)據(jù)結(jié)構(gòu)與算法概念數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)DS=(A,R),其中A是數(shù)據(jù)元素的非空有限集合,R是定義在A上的關(guān)係的非空有限集合,結(jié)構(gòu)就元素之間的關(guān)係算法,就是解決問(wèn)題的方法和步驟算法的時(shí)間複雜度,算法語(yǔ)句中重複執(zhí)行的次數(shù)(或稱語(yǔ)句頻度),或算法中基本操作次數(shù),一般用數(shù)量級(jí)O()來(lái)描述2.2.2線性表線性表的定義,線性表是n(n>=0)個(gè)元素的有限序列,當(dāng)n=0時(shí),稱為空表,當(dāng)n>0時(shí),線性表通常表示為(a1,a2,a3,……,an),其中a1無(wú)前驅(qū),an無(wú)後繼,其餘結(jié)點(diǎn)有且只有一個(gè)前驅(qū)和一個(gè)後繼線性表的存儲(chǔ),線性表有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu),在連續(xù)的存儲(chǔ)空間中依次存儲(chǔ)線性表的各個(gè)元素,具體用一維數(shù)組來(lái)得到連續(xù)的存儲(chǔ)空間順序存儲(chǔ)的結(jié)構(gòu)特點(diǎn),存儲(chǔ)位置上直接反映了元素的邏輯關(guān)係,不需要指出前驅(qū)後繼,操作特點(diǎn),便於查找,不便於插入,刪除鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),在任意(連續(xù)或不連續(xù))的存儲(chǔ)空間中存放線性表的各元素,所以每個(gè)結(jié)點(diǎn)要帶指針指出前驅(qū)後繼,用動(dòng)態(tài)分配空間實(shí)現(xiàn).單鏈結(jié)構(gòu),結(jié)點(diǎn)的指針域中只有一根指針指向後繼,最後一個(gè)結(jié)點(diǎn)的指針值未null,每個(gè)結(jié)點(diǎn)只能找到後繼,不能找到前驅(qū),便於插入,刪除,不便於查找單循環(huán)結(jié)構(gòu),最後一個(gè)結(jié)點(diǎn)的指針指向首結(jié)點(diǎn),特點(diǎn)便於插入和刪除,尤其是在首端和尾端插入刪除更方便雙鏈結(jié)構(gòu),每個(gè)結(jié)點(diǎn)帶有指向前驅(qū)和指向後繼的兩個(gè)指針,優(yōu)點(diǎn)查找結(jié)點(diǎn)的前驅(qū)和後繼方便,缺點(diǎn)是存儲(chǔ)空間開銷比較大線性表的操作,主要有初始化,判空表,求表長(zhǎng)度,查找,插入和刪除靜態(tài)數(shù)組#DefineArSize10TypedefStruct{ElemTypeelem[ArSize];Intlength;}SqList;voidinitList(sqList*L){L->length=0;}動(dòng)態(tài)數(shù)組TypedefStruct{Elemtype*elem;Intlength,ArSize;}sqlist;voidinitlist(sqllist*L,intn){L->elem=(Elemtype*)malloc(n*Sizeof(Elemtype));L->ArSize=n;L->length=0;}查找時(shí)間複雜度O(1)插入O(n/2),刪除O((n-1)/2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)TypeDefStructNode{ElemtypeData;StructNode*next;}LNode;LNode*initLK(){Lnode*head;Head=Null;ReturnHead;}查找元素平均比較次數(shù)O((n+1)/2)查找,刪除O(1)例在非空的雙鏈錶中刪除指針P所指向的結(jié)點(diǎn).P->Front->Next=P->NextP->Next->Front=P->Front在非空的雙鏈錶中指針P所指向的結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)QQ->Next=PQ->Front=P->FrontP->Front->Next=QP-Front=Q2.2.3棧和隊(duì)列1.棧,是一種只能在表的某一端(首端)進(jìn)行操作的線性數(shù)據(jù)結(jié)構(gòu),棧的操作主要有進(jìn)棧和出棧.是先進(jìn)後出的(FILO)棧的存儲(chǔ)結(jié)構(gòu),有順序棧和鏈棧靜態(tài)數(shù)組棧#DefineSSize10TypeDefStruct{Elemtypeelem[SSize];inttop;}SqSnode;進(jìn)棧Sqsnodes;s.elem[s.top++]=e;出棧e=s.elem[--s.top]?？誷.top==0棧滿s.top=SSize動(dòng)態(tài)數(shù)組棧TypeDefStruct{Elemtype*elem,*top;intSSize;}dsnode;dsnodes;進(jìn)棧*s.top++=e;出棧e=*--s.top;空棧s.top==s.elem滿棧s.top==s.elem+s.ssize鏈棧TypeDefStructnode{Elemtypedata;Structnode*Next;}lsnode;進(jìn)棧lsnode*top,*p;p=newlsnode;p->data=e;p->Next=top;top=p;出棧p=top;e=p->data;top=top->Next;delete(p);空棧top==null例算術(shù)表達(dá)式a+b*c/(d-e)-f的逆波蘭表達(dá)式:解法一:1.置空棧2.順序掃描3.a數(shù)字優(yōu)先級(jí)為0直接出棧結(jié)果a4.+優(yōu)先級(jí)為3,入棧5.b數(shù)字直接出棧結(jié)果ab6.*優(yōu)先級(jí)為5.入棧7.c數(shù)字直接出棧結(jié)果abc8./優(yōu)先級(jí)為5,棧頂元素>=當(dāng)前元素,出棧,當(dāng)前元素入棧結(jié)果abc*9.(直接入棧10.d數(shù)字直接出棧結(jié)果abc*d11.-優(yōu)先級(jí)為3,入棧12.e直接出棧結(jié)果abc*de13.)出棧,直到)結(jié)果abc*de-14.-優(yōu)先級(jí)為3,棧頂元素>=當(dāng)前元素,出棧,當(dāng)前元素入棧結(jié)果abc*de-/+15.f直接出棧結(jié)果abc*de-/+f16.掃描完畢順序輸出棧結(jié)果abc*de-/+f-解法二:後根序遍歷二叉樹:abc*de-/+f-2.隊(duì)列,隊(duì)列是一種只能在表的尾端進(jìn)行插入操作,在首端進(jìn)行刪除操作的線性數(shù)據(jù)結(jié)構(gòu),他是先進(jìn)先出的(FIFO)線性表.隊(duì)列的存儲(chǔ)結(jié)構(gòu),有順序隊(duì)列和循環(huán)隊(duì)列循環(huán)隊(duì)列#DefineQSize10TypeDefStruct{Elemtypeelem[QSize];intfront,rear;}sqQnode;進(jìn)隊(duì)sqqnodeQ;q.rear=(q.rear+1)%QSize;q.elem[q.rear]=e;出隊(duì)q.font=(q.font+1)%Qsize;e=q.elem[q.font];空隊(duì)q.font=q.rear;隊(duì)滿q.front=(q.rear+1)%QSize;循環(huán)鏈隊(duì)列TypeDefStructnode{Elemtypedata;Structnode*next;}lqnode;進(jìn)隊(duì)lqnode*rear,*p;p=newlqnode;p->data=e;p->next=rear->next;rear->next=p;rear=p;出隊(duì)設(shè)循環(huán)隊(duì)列Q,則當(dāng)前循環(huán)隊(duì)列中元素的個(gè)數(shù)是(q.rear-q.front+qsize)%qsize2.2.4串串,字串的定義,串是有限個(gè)字符組成的序列,子串是串中任意長(zhǎng)度的連續(xù)字符構(gòu)成的序列.串的存儲(chǔ),串的運(yùn)算.模式匹配算法和kmp算法i=i–j+2;i=i–j+2;j=1;例已知主串s=’ABBABA’,子串t=’ABA’,求樸素的模式匹配算法查找子串t比較的次數(shù),答案是8,位置是42.2.5數(shù)組和廣義表數(shù)組的定義,N維數(shù)組Ab1b2b3…bn,A中的每個(gè)元素A[j1,j2…jn],1為每一維數(shù)組的下界,bi為第i維的上界數(shù)組的存儲(chǔ),順序存儲(chǔ)(以行序?yàn)橹餍?以列序?yàn)橹餍?,壓縮存儲(chǔ)(三角陣,對(duì)角陣),稀疏矩陣,三元組順序存儲(chǔ),十字鏈錶存儲(chǔ)廣義表定義,廣義表(a1,a2,…an),其中ai是原子或表,求表頭head,表尾tail,求深度表的深度為括號(hào)的重?cái)?shù).長(zhǎng)度為外括號(hào)里逗號(hào)的個(gè)數(shù).C=(A，B)=((x，(a，b))，((x，(a，b))，y))長(zhǎng)度是2,深度是4稀疏矩陣的三元組表示0060000030008000000005000070三元組((1,3,6),(2,2,3),(2,6,8),(4,1,5),(4,6,7))2.2.6樹和二叉樹1.二叉樹定義,二叉樹是由一個(gè)特定的結(jié)點(diǎn)(無(wú)前驅(qū))稱為跟結(jié)點(diǎn)和兩個(gè)互不相交的左子樹,右子樹組成,其中左子樹,右子樹本身是二叉樹術(shù)語(yǔ)結(jié)點(diǎn)的度,結(jié)點(diǎn)的後繼數(shù)葉子,度為零的結(jié)點(diǎn),也稱終端結(jié)點(diǎn),葉子外的結(jié)點(diǎn)也稱內(nèi)結(jié)點(diǎn)結(jié)點(diǎn)的層次,樹根為第一層,根的後繼為第二層,以此類推編號(hào)樹的深度,樹的最大層次數(shù),也稱樹的高度滿二叉樹,樹中每一層上的元素都達(dá)到最多的二叉樹,即i層有2i-1個(gè)元素完全二叉樹,樹中除底層h的結(jié)點(diǎn)外,其餘層上必須有2i-1個(gè)元素,並且底層的結(jié)點(diǎn)都集中在底層的左端豐滿二叉樹,樹中除底層h的結(jié)點(diǎn)外,其餘層上必須有2i-1個(gè)元素二叉樹的性質(zhì),二叉樹第i層上最多有2i-1個(gè)元素,深度為h的二叉樹最多有2h-1個(gè)結(jié)點(diǎn),設(shè)n0,n1分別為二叉樹中度為0和度為2的結(jié)點(diǎn)數(shù)目,則有n0=n2+1,n個(gè)結(jié)點(diǎn)的二叉樹其樹的深度範(fàn)圍[log2h]+1~~n二叉樹的存儲(chǔ)順序存儲(chǔ),舍用於完全二叉樹,結(jié)點(diǎn)下標(biāo)i的父結(jié)點(diǎn)為[i/2],二叉鏈錶,每個(gè)結(jié)點(diǎn)帶有指向左右孩子的兩個(gè)指針,三叉鏈錶每個(gè)結(jié)點(diǎn)帶有指向左右孩子和指向父結(jié)點(diǎn)的指針二叉樹的遍歷前序遍歷,先訪問(wèn)根結(jié)點(diǎn),然後前序訪問(wèn)左子樹,再前序遍歷又子樹中序遍歷,先中序遍歷左子樹,然後訪問(wèn)根結(jié)點(diǎn),再中跟序遍歷又子樹后序遍歷,先后序遍歷左子樹,再后序遍歷又子樹,再訪問(wèn)根結(jié)點(diǎn)線索二叉樹,當(dāng)二叉樹用二叉鏈錶存儲(chǔ)時(shí),二叉鏈錶有n個(gè)結(jié)點(diǎn),則存在n+1指針域?yàn)榭?可以利用這些空指針域存放某種遍歷次序下的前驅(qū)和後繼結(jié)點(diǎn)的指針,這種二叉樹就稱為線索二叉樹前序線索二叉樹中序線索二叉樹後序線索二叉樹霍夫曼樹(Huffman),又稱最優(yōu)二叉樹,他是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹主要用途是實(shí)現(xiàn)數(shù)據(jù)的壓縮例給出一段報(bào)文,字符集為{a,b,c,d,e,f}各字符出現(xiàn)的頻度是{45,13,12,16,9,5}若給每個(gè)字符等長(zhǎng)編碼(a,000b,001c,010d,011e,100f,101)則總長(zhǎng)度=3*100=300若按霍夫曼編碼((a,0b,101c,100d,111e,1101f,1100))則總長(zhǎng)度=45*1+(13+12+16)*3+(9+5)*4=224數(shù)據(jù)壓縮率=224/300*100%=74.7%假設(shè)用於通信的電文由字元集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}

(1)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。

霍夫曼演算法(1)由給定的n個(gè)權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴(kuò)充二叉樹的森林F={T0,T1,T2,…,Tn-1}，其中每一棵擴(kuò)充二叉樹Ti只有一個(gè)帶有權(quán)值wi的根結(jié)點(diǎn)，其左、右子樹均為空(2)重複以下步驟,直到F中僅剩下一棵樹為止①在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的擴(kuò)充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和②在F中刪去這兩棵二叉樹③把新的二叉樹加入F假設(shè)用於通信的電文由字元集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}森林F:選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F重複選取最小權(quán)值的兩棵樹,構(gòu)成二叉樹并加入F,直到F剩下一棵樹為止2.樹和森林樹是由一個(gè)特定的結(jié)點(diǎn)(無(wú)前驅(qū))稱為跟和m個(gè)互不相交的子樹組成,當(dāng)m=0時(shí)稱為空數(shù)樹的存儲(chǔ),樹的遍歷(前跟序遍歷,后跟序遍歷)樹與二叉樹的轉(zhuǎn)換,樹用孩子兄弟法表示即為二叉樹森林,是樹的集合,將每棵樹的根看成兄弟關(guān)係,用數(shù)的孩子兄弟法表示,即為二叉樹2.2.7圖1.圖的定義圖G=(V,E),其中V是頂點(diǎn)的有窮非空集合,E是V中頂點(diǎn)的序偶組成的有窮集,這些序偶稱為邊2.基本術(shù)語(yǔ)鄰接點(diǎn),若存在一條邊<Vi,Vj>,則再無(wú)向圖中稱Vi和Vj互為鄰接點(diǎn),在有向圖中稱Vj是Vi的鄰接點(diǎn)完全圖,圖G中任意兩點(diǎn)都鄰接,無(wú)向完全圖有n(n-1)/2條邊,有向完全圖有n(n-1)條邊邊n=6,頂點(diǎn)V=4,所有接點(diǎn)的度之和為12度,入度和出度,無(wú)向圖中頂點(diǎn)V依附(關(guān)聯(lián))的邊數(shù)稱為V的度,對(duì)於有向圖分為入度和出度,V的入度之指邊的箭頭指向V的入邊數(shù)目,V的出度是箭頭離開V的出邊數(shù)目,圖中所有接點(diǎn)度數(shù)之和等於圖邊數(shù)的兩倍連通和連通圖,在無(wú)向圖中,Vi到Vj有路徑,則稱Vi和Vj時(shí)連通的,若圖G中任意兩個(gè)頂點(diǎn)都是連通的則稱G是連通圖連通分量,無(wú)向圖G中的極大連通子圖稱為圖G的連通分量強(qiáng)連通圖和強(qiáng)連通分量,在有向圖中,如任意兩個(gè)頂點(diǎn)Vi和Vj都連通,即Vi和Vj存在路徑,從Vj到Vi也存在路徑,則稱為強(qiáng)連通圖,有向圖G中的極大強(qiáng)連同子圖稱為G的強(qiáng)連通分量網(wǎng),邊帶權(quán)的圖,也稱帶權(quán)圖生成樹,連通圖G有N個(gè)頂點(diǎn),取G中n個(gè)頂點(diǎn),取連接n個(gè)頂點(diǎn)的n-1條邊所得的子圖稱為G的生成樹3.圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣,設(shè)圖G=(V,E)有n個(gè)頂點(diǎn),則G的鄰接矩是一個(gè)n階方陣A[i][j]=1(有邊)0(無(wú)邊)鄰接鏈錶,把圖的每個(gè)頂點(diǎn)Vi建立一個(gè)單鏈錶,把與Vi相鄰接的頂點(diǎn)放在一個(gè)鏈錶中4.圖的遍歷深度優(yōu)先DFS,首先訪問(wèn)指定的起始頂點(diǎn)V,然後選取與V鄰接的未被訪問(wèn)的任意一個(gè)接點(diǎn)w訪問(wèn)之,再選取與w鄰接的未被訪問(wèn)的任意一接點(diǎn)訪問(wèn)之,重複進(jìn)行如上訪問(wèn),當(dāng)達(dá)到一個(gè)所有鄰接點(diǎn)都被訪問(wèn)過(guò)時(shí),則依次退回到最近被訪問(wèn)過(guò)的接點(diǎn),若他有鄰接未被訪問(wèn),從這些未被訪問(wèn)的接點(diǎn)中選取一個(gè)頂點(diǎn),重複開始訪問(wèn)過(guò)程,直到所有頂點(diǎn)都被訪問(wèn)為止結(jié)果:125436aabcdefgh結(jié)果:abdhefcg廣度優(yōu)先(BFS),首先選取指定的起始頂點(diǎn)V,然後選取與V鄰接的全部頂點(diǎn)w1,w2…wt再依次訪問(wèn)與w1,w2…wt鄰接的未被訪問(wèn)的頂點(diǎn),直到全部訪問(wèn)ababcdefgh結(jié)果:124536結(jié)果:abfcdehg5.最小生成樹,在圖中所有生成樹權(quán)最小的樹Prim算法從0開始,選取權(quán)最小的與2相連權(quán)值最小的與5相連權(quán)值最小的不能產(chǎn)生回路,所以回走,選擇與2相連的權(quán)值最小的再選擇與1相連的權(quán)值最小的接點(diǎn)Kruskal算法選取圖中權(quán)最小的選取圖中權(quán)最小的選取圖中權(quán)最小的選取圖中權(quán)最小的選取圖中權(quán)最小的Prim算法時(shí)間複雜度O(N^2)適合稠密度,Kruskal時(shí)間複雜度O(elog2e)適合稀疏圖6.拓?fù)渑判?就是對(duì)一個(gè)有向無(wú)環(huán)圖(AOV)中的各點(diǎn)排成一個(gè)具有前後次序的線性序列,方法,找到無(wú)前驅(qū)(入度為零)的頂點(diǎn)輸出并將其每個(gè)後繼頂點(diǎn)的前驅(qū)數(shù)(入度)減一,值到所有頂點(diǎn)都輸出V1,2,3,5,4,67.關(guān)鍵路徑,帶權(quán)有向圖(AOE)中從源點(diǎn)(表示工程的開始)到匯點(diǎn)(表示工程的結(jié)束)的長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑V1,3,4,68.最短路徑,Dijkstra算法Dijkstra算法1.從V1開始,與V1相連的路徑V1~V2=====3V1~V3=====2選取最短路徑V1~V3中的V3做起點(diǎn),V1~V3=====2V1~V2=====3V1~V3~V4=====6V1~V3~V6=====5選取最短路徑V1~V2=====3中的V2做起點(diǎn)V1~V3~V4=====6V1~V3~V6=====5V1~V2~V5======6V1~V2~V4======5選取最短路徑V1~V2~V4中的V4左起點(diǎn)V1~V3~V4=====6V1~V3~V6=====5V1~V2~V5======6V1~V2~V4~V6======7得到最短的路徑為{V1~V2=3V1~V3=2V1~V2~V4=5V1~V2~V5=6V1~V3~V6=5}2.2.8查找1.查找概念查找表,同一數(shù)據(jù)類型的元素構(gòu)成的集合靜態(tài)查找表,在查找操作時(shí)不對(duì)查找表的長(zhǎng)度進(jìn)行修改動(dòng)態(tài)查找表,是在查找過(guò)程中動(dòng)態(tài)生成的,即查找時(shí)若所找元素不存在則插入平均查找長(zhǎng)度ASL(AverageSearchLength)ASL=∑PiCi2.靜態(tài)查找表上的查找方法順序查找,待查找元素依次與查找表中的元素比較,ASL=O(n)二分查找,待查找元素與查找表中間的元素比較,若小,則在前半段中用同樣的方法查找,若大,則在后半段用同樣的方法查找,ASL=O(Log2N)分塊查找,當(dāng)查找表局部有序時(shí),將查找表分成如干塊,塊內(nèi)元素不一定有序,對(duì)塊建立索引,索引是按關(guān)鍵字有序的,查找方法是先順序查找塊,再順序查找塊內(nèi)元素.當(dāng)塊長(zhǎng)為n時(shí),最小的ASL=O(Sqr(n))3.動(dòng)態(tài)查找表的查找⑴二叉排序數(shù)非空二叉樹中的任意結(jié)點(diǎn)A,若K有左子樹,則左子樹中的每個(gè)結(jié)點(diǎn)的值都小於K,若K有右結(jié)點(diǎn),則右子樹中的所有結(jié)點(diǎn)的值都大於等於K的值,中序遍歷二叉樹得到升序序列插入2刪除15⑵平衡二叉樹(AVL)非空的平衡二叉樹中的任意結(jié)點(diǎn)K,K的左子樹和右子樹的深度之差絕對(duì)值不超過(guò)1設(shè)有關(guān)鍵碼序列{20,35,40,15,30,25,38}，圖7-3給出了平衡二叉樹樹的構(gòu)造過(guò)程，結(jié)點(diǎn)旁邊標(biāo)出的是該結(jié)點(diǎn)的平衡因數(shù).平衡因子等於該結(jié)點(diǎn)左子樹與右子樹之差⑶B-樹⑷哈希表及其查找哈希表,設(shè)哈希函數(shù)H(Key),結(jié)點(diǎn)的存儲(chǔ)方法為H(關(guān)鍵字)=存儲(chǔ)位置.按這種方法得到的存儲(chǔ)結(jié)構(gòu)圖稱為哈希表解決哈希衝突的方法:當(dāng)哈希函數(shù)不是一對(duì)一時(shí)則產(chǎn)生衝突開放地址法Hi=(H(key)+di)Modm其中,M為哈希表的長(zhǎng)度,Di為曾量當(dāng)Di=1,2,3…M-1時(shí),稱為線性探測(cè)再散列當(dāng)Di=1^2,-1^,2^2,-2^2….±K^2時(shí),稱為二次探測(cè)再散列鏈地址法練習(xí)1.已知關(guān)鍵字序列4,7,9,10,15,21,33,48,52,61,3,1.寫出用二分查找方法查找關(guān)鍵字52的比較次數(shù)和等概率的平均查找長(zhǎng)度構(gòu)造平衡二叉樹1.RR型2.RR型3.RL型4.RL型5.RL型6.RL型7.LL型2.2.9排序1.排序的概念排序,將無(wú)序序列調(diào)整為有序序列穩(wěn)定性,若待排序記錄有相同關(guān)鍵字,排序后相同關(guān)鍵字的相對(duì)位置發(fā)生變化,則稱該排序算法不穩(wěn)定,否則為穩(wěn)定內(nèi)部排序,指帶排序記錄全部存放在內(nèi)存中排序的排序過(guò)程外部排序,在排序過(guò)程中,需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程2.簡(jiǎn)單排序(1)直接插入排序基本思想,將無(wú)序的序列中從第二個(gè)開始的每個(gè)元素依次插入到有序序列,當(dāng)序列有n個(gè)元素時(shí),則進(jìn)行n-1次插入C語(yǔ)言描述voidinsertsort(intr[],intn){inti,j;for(i=2;i<=n;i++){if(r[i]<r[i-1]){r[0]=r[i];j=i-1;do{r[j+1]=r[j];j--;}while(r[0]<r[j]);r[j+1]=r[0];}}}VBA描述PublicSubInsertSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextFori=2To10IfArr(i)<Arr(i-1)ThenTmp=Arr(i)j=iDoTmp=Arr(j)Arr(j)=Arr(j-1)Arr(j-1)=Tmpj=j-1LoopWhileTmp<Arr(j-1)EndIfNextiFori=1To10Cells(i,2).Value=Arr(i)NextEndSub時(shí)間複雜度O(n^2)(2)冒泡排序基本思想,小的往上冒方法,從無(wú)序序列的最後元素開始往前兩兩比較,第一次冒出最小的元素,第二次在剩餘的序列中冒出第二小的,這樣共要冒出n-1個(gè)元素C語(yǔ)言描述VoidBubbleSort(intr[],intn){inti,j,tag,tmp;for(i=0;i<n-1;i--){tag=0;for(j=n-1;j=i+1;j--){if(r[j]<r[j-1]){tmp=r[j];r[j]=r[j-1];r[j-1]=tmp;tag=1;}if(tag==0)break;}}}VBA語(yǔ)言描述PublicSubBubbleSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextFori=1To10flag=0Forj=10Toi+1Step-1IfArr(j)<Arr(j-1)Thentmp=Arr(j)Arr(j)=Arr(j-1)Arr(j-1)=tmpflag=1EndIfNextjIfflag=0ThenExitForEndIfNextiFori=1To10Cells(i,2).Value=Arr(i)NextEndSub時(shí)間複雜度O(n^2)(3)簡(jiǎn)單選擇排序基本思想,第一次從無(wú)序序列中選出第一小的元素,然後從剩下的序列中選出第二小的元素,這樣共選出n-1小的數(shù)C語(yǔ)言描述VoidSelectSort(intr[],intn){inti,jk,tmp;for(i=0;i<=n-1;i++){k=i;for(j=i+1;j<n;j++){if(r[j]<r[k])k=j;}if(i!=k){tmp=r[i];r[i]=r[k];r[k]=tmp;}}}VBA語(yǔ)言描述PublicSubSelectSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextFori=1To10k=iForj=i+1To10IfArr(j)<Arr(k)Thenk=jEndIfNextjIfi<>kThentmp=Arr(i)Arr(i)=Arr(k)Arr(k)=tmpEndIfNextiFori=1To10Cells(i,2).Value=Arr(i)NextEndSub時(shí)間複雜度O(n^2),不穩(wěn)定排序算法3.先進(jìn)排序(1)希爾排序基本思想,先將整個(gè)待排序列分割成若干子序列,然後對(duì)各個(gè)子序列分別進(jìn)行直接插入排序PublicSubShellSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)Nexth=5DoWhileh>0Fori=hTo10IfArr(i)<Arr(i-1)Thentmp=Arr(i)j=iDotmp=Arr(j)Arr(j)=Arr(j-1)Arr(j-1)=tmpj=j-1LoopWhiletmp<Arr(j-1)EndIfNextih=h-2LoopFori=1To10Cells(i,2).Value=Arr(i)NextEndSub不穩(wěn)定,時(shí)間複雜度O(nlog2n)(2)快速排序基本思想,選取第一個(gè)結(jié)點(diǎn),以它的關(guān)鍵字和序列中所有其他關(guān)鍵字比較,小的放前面,大的放後面,然後分別對(duì)這兩部份重複上述過(guò)程,直到?jīng)]部份只剩一個(gè)結(jié)點(diǎn)為止PublicSubKuaisu()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)NextCallKuaisusort(Arr(),1,10)Fori=1To10Cells(i,2).Value=Arr(i)NextEndSubPublicFunctionPartition(Tarr()AsInteger,LeftAsInteger,RightAsInteger)AsIntegerPivot=Tarr(Left)low=LeftHight=RightDoWhile(low<>Hight)IfTarr(Hight)>PivotThenHight=Hight-1ElseIfTarr(low)<=PivotThenlow=low+1ElseTmp=Tarr(low)Tarr(low)=Tarr(Hight)Tarr(Hight)=TmpEndIfLoopTarr(Left)=Tarr(low)Tarr(low)=PivotPartition=lowEndFunctionPublicSubKuaisusort(Tarr()AsInteger,LeftAsInteger,RightAsInteger)IfLeft<RightThenPt=Partition(Tarr(),Left,Right)CallKuaisusort(Tarr(),Left,Pt-1)CallKuaisusort(Tarr(),Pt+1,Right)EndIfEndSub不穩(wěn)定,時(shí)間複雜度O(nlog2n)(3)堆排序堆的定義,n個(gè)元素的序列{k1,k2,…,kn}當(dāng)且僅當(dāng)所有關(guān)鍵字都滿足下列關(guān)係時(shí)稱為堆,ki<=k2iandki<=k2i+1(小跟堆),其中i<=1<=n/2基本思想,建堆VBA描述PublicSubDuiSort()DimArr(10)AsIntegerFori=1To10Arr(i)=Int(Rnd()*100)Cells(i,1).Value=Arr(i)Nextj=10DoWhilej>0Fori=(j\2)To1Step-1m=2*in=2*i+1Ifn<jThenIfArr(i)<Arr(n)Thentmp=Arr(i)Arr(i)=Arr(n)Arr(n)=tmpEndIfEndIfIfArr(i)<Arr(m)Thentmp=Arr(i)Arr(i)=Arr(m)Arr(m)=tmpEndIfNexttmp=Arr(j)Arr(j)=Arr(1)Arr(1)=tmpj=j-1LoopFori=1To10Cells(i,2).Value=Arr(i)NextEndSub不穩(wěn)定,時(shí)間複雜度O(nlog2n)(4)并歸排序基本思想,將兩個(gè)或多個(gè)有序序列合併成一個(gè)新的有序序列(5)基數(shù)排序基本思想,4.外排序2.2.10常見算法設(shè)計(jì)方法1.分治法基本思想,將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題,這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同,遞歸地解決這些子問(wèn)題,然後將各個(gè)子問(wèn)題的解合併得到原來(lái)問(wèn)題的解二分查找,快速排序就是典型的例子2.遞推法基本思想,在n=1時(shí)能方便得到解,當(dāng)?shù)玫絾?wèn)題規(guī)模為i-1的解后,由問(wèn)題的遞推性質(zhì)能從已求的規(guī)模為1,2,3…i-1的一系列解構(gòu)造出問(wèn)題為i的解F(n)=1n<=2F(n-1)+F(n-2)n>2VBA語(yǔ)言描述PublicFunctionFibonacci(AAsInteger)AsIntegerIfA<=2ThenRst=1El