《數(shù)據(jù)結(jié)構(gòu)》考前沖刺大綱講義總結(jié)

《數(shù)據(jù)結(jié)構(gòu)》考前沖刺大綱講義總結(jié)緒論數(shù)據(jù)結(jié)構(gòu)的基本概念基本概念和術(shù)語.數(shù)據(jù).數(shù)據(jù)元素:可由若干數(shù)據(jù)項組成,數(shù)據(jù)項是不可分割的最小單位.數(shù)據(jù)對象:具有相同性質(zhì)的數(shù)據(jù)元素的集合.數(shù)據(jù)類型:是一個值的集合和定義在此集合上一組操作的總稱.抽象數(shù)據(jù)類型(ADT):包括數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作集.數(shù)據(jù)結(jié)構(gòu):邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算1.2數(shù)據(jù)結(jié)構(gòu)的三要素.邏輯結(jié)構(gòu)：分為線性和非線性結(jié)構(gòu).存儲結(jié)構(gòu)(物理結(jié)構(gòu))：包括順序、鏈?zhǔn)?、索引和散列存?數(shù)據(jù)的運算:運算的定義和實現(xiàn).2算法和算法評價.2.1算法的基本概念.五個重要特性:有窮、確定、可行、輸入和輸出.好的算法目標(biāo):正確性、可讀性、健壯性、高效率與低存儲量1.2.2算法效率的度量.時間復(fù)雜度：7(〃)=。(/(〃))，通常指最壞情況下時間復(fù)雜度.空間復(fù)雜度:原地工作指算法所需的輔助空間是常量第2章線性表線性表的定義及基本操作1.1線性表的定義.線性表是具有n個相同類型數(shù)據(jù)元素的有限序列,n為表長,n=0是空表2.1.2線性表的基本操作1.InitList(&L)Length(L)LocateElem(L,e)

GetElem(L,i)Listinsert(&L,i,e)ListDelete(&L,i,&e)Empty(L)DestroyList(&L)2.2線性表的順序表示2.2.1順序表的定義.元素邏輯位置與物理位置相同,線性表的順序從1開始.線性表的順序存儲類型(1)一位數(shù)組靜態(tài)分配(1)一位數(shù)組靜態(tài)分配?defineMaxSize50typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;(2)動態(tài)分配#defineInitSize100typedefstruct{ElemType*data;intMaxSize,length;}SeqList;〃定義線性表的最大長度〃順序表的元素〃順序表的當(dāng)前長度〃順序表的類型定義〃表長度的初始定義〃指示動態(tài)分配數(shù)組的蛆/麗麗O%量融前社〃動態(tài)分配數(shù)組順序表的類型定義C的初始動態(tài)分配語句C的初始動態(tài)分配語句L.data*InitSize);.順序表特點:隨機(jī)訪問，存儲密度高,插入和刪除需要移動大量元素.2.2順序表上基本操作的實現(xiàn)(1)插入:在第i個位置插入e(\<i<LJength+\),i不合法則返回false;否則,將第i個元素及其后所有元素右移一個位置;插入e,表長加1,返回true(從后往前依次后移一個)boolListinsert(SqList i,ElemTypee){〃本算法實現(xiàn)將元素e插入到順序表L中第i個位置if<i<l||i>L.length+l) //判斷i的范圍是否有效returnfalse;if(L.length>=MaxSize) 〃當(dāng)前存儲空間已滿，不能插入returnfalse;for(intj=L.length;j>-i;j-) 〃將第i個元素及之后的元素后移L.data(j]-L.data,Li-Ur : .=''L.datafi-11-e； 〃在位置i處放入e ..L.length4-+； 〃線性表長度加1returntrue;平均移動n/2個元素,則時間復(fù)雜度為0(n)

(2)刪除:刪除第i個元素，成功返回true,并將元素用e返回，否則返回false(從前往后依次前移一個)boolListDelete(SqLlst&Lrinti,int&e){〃boolListDelete(SqLlst&Lrinti,int&e){〃本算法實現(xiàn)刪除順序表L中第i個位置的元素if(i<l||i>L.length)returnfalse;e?L.data[i-l];for(intj-i;j<L.length;j++)L.data(jdata[j];L.length--;returntrue;)〃判斷i的范圍是否有效〃將被刪除的元素賦值給e〃將第i個位置之后的元素前移〃線性表長度減1平均移動(n-l)/2個元素,則時間復(fù)雜度為0(n)(3)按值查找(順序查找)：若成功返回元素位序,若失敗返回0intLocateElem(SqListL,ElemTypee){〃本算法實現(xiàn)查找順序表中值為e的元貢，如果查找成功，返回元素位序，否則返回。inti;for(i*0;i<L.length;i++)if(L.data[i]??e)returni+1; 〃下標(biāo)為1的元素值等fe,返回其位序i+1return0; 〃退出循環(huán)，說明查找失敗平均比較次數(shù)(n+D/2,時間復(fù)雜度為0(n)2.3線性表的鏈?zhǔn)奖硎?.3.1單鏈表的定義:每個鏈表結(jié)點除了存放自身信息，還存放指向其后繼結(jié)點的指針;順序存取,從表頭開始查找typedefstructLNode{ //定義單鏈表結(jié)點類型ElemTypedata; //數(shù)據(jù)域structLNode*next; 〃指針域}LNode,*LinkList;.通常用頭指針標(biāo)識一個單鏈表,如單鏈表L,頭指針為“NULL”表示一個空表;通常在單鏈表前面附加一個頭結(jié)點(不設(shè)數(shù)據(jù),指針域指向線性表第一個結(jié)點).引入頭結(jié)點優(yōu)點：(1)由于開始結(jié)點的位置被存放在頭結(jié)點指針域中，所以在鏈表第一個位置上的操作和其他位置上一樣(2)無論鏈表是否為空,其頭指針是指向頭結(jié)點的非空指針,因此空表和非空表同樣處理.3.2單鏈表上基本操作實現(xiàn).頭插法建立單鏈表:每次插入結(jié)點插到表頭之后「立口R次格所指結(jié)點,插在最前端圖2-5「立口R次格所指結(jié)點,插在最前端圖2-5頭插法建立單鏈表三LinkListCreatListl(LinkList&L)(//從表尾到表頭逆向建立單域表LinkListCreatListl(LinkList&L)(//從表尾到表頭逆向建立單域表L,每次均在頭結(jié)點之后插入元素LNode*s;intx;〃創(chuàng)建頭結(jié)點〃初始為空鏈表〃輸入結(jié)點的值//輸入9999表示結(jié)束〃創(chuàng)建新結(jié)點L->next-NULL;scanfwhile(x!-9999)(s?(LNode,)malloc(sizeof(LNode));s->data-x;s->next-L->next;L->next-s;scanf&x);)〃將新結(jié)點插入表中，L為頭指針■〃〃將新結(jié)點插入表中，L為頭指針■〃While結(jié)束每次郴所指站點插在末端■At~i.每次郴所指站點插在末端■At~il—、I日一INI圖2?尾插法建立單鏈表LinkListCreatList2(LinkList&L){〃從表頭到表尾正向建立單鏈表L,每次均在表尾插入元素intx; //設(shè)元素類型為整型L=(LinkList)malloc(sizeof(LNode));LNode*s,*r=L; 〃r為表尾指針scanf("%d",&x); 〃輸入結(jié)點的值while(x!=9999)( 〃輸入9999表示結(jié)束3=(LNode*)malloc(sizecf(LNode));s->data=x;???????；????,???,,??r->nextms;r-s; 〃r指向新的表尾結(jié)點scanf("%d",&x);}r->next=NULL; 〃尾結(jié)點指針置空returnL;).按序號查找結(jié)點值:從第一個結(jié)點出發(fā)，順next往下查找,0(n)LNode?GetElen(LinkListL,intL)(〃計數(shù)，初始為】〃頭結(jié)點指針賦給P〃著〃計數(shù)，初始為】〃頭結(jié)點指針賦給P〃著i等于0,則返回頭結(jié)點〃若i無效，JW返回NULL〃從第1個站點開始找，杳找第i個結(jié)點intj-1;LNode*p-L->next;if(i-0)returnL;returnNULL;while(pfi(j<i)(p?p->next;returnp; 〃詆回第i個結(jié)點的指針，如果1大于表長，P-NULL,直接返回P即可.按值查找元素:0(n)LNode*LocateElem(LinkListL,ElenTypee)(〃本算法查找單健麥L(帶頭站點)中數(shù)據(jù)域值等于e的結(jié)點指針,否則返回NULLLNode*p=L->next;while(p?-NULU4p->data!-e) 〃從第1個結(jié)點開始森找data域為e的結(jié)點p-p->next;returnp; 〃找到后返回該結(jié)點指計.否則返回NULL.插入結(jié)點:插入到第i個位置,先檢查插入位置合法性,然后找到第i-1個

結(jié)點,在其后插入p=GetElem(L.i-1);s->next=p->next;p->next=s;(1)時間復(fù)雜度為0(n),若在給定序號后插入時間復(fù)雜度為0(1)(2)擴(kuò)展:對某一結(jié)點進(jìn)行前插操作:仍將*s插入到*p后面,然后將p->data與s->data換位置.刪除結(jié)點操作:先檢查位置合法性,找到iT個位置,即被刪除結(jié)點的前驅(qū)結(jié)點位置p=GetElem(L,i-1);q=p->next;p->next=q->next;free(q);2.3.3雙鏈表兩個指針prior(指針前驅(qū))和next(指向后繼)typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode*DLinkList;L雙鏈表的插入p—I；I：」t：I-4-^⑨—5E手_」①2.雙鏈表的刪除圖2-10雙性表描入結(jié)點過程2.雙鏈表的刪除圖2-10雙性表描入結(jié)點過程〃將結(jié)點*S插入到結(jié)點*P之后3=? ?圖2?11雙鏈表刪除結(jié)點過程p->next-q->next; 〃圖2-10中步驟①q->next->prior=p; 〃圖2To中步驟②free(q); //釋放結(jié)點空間2.3.4循環(huán)鏈表.循環(huán)單鏈表:表中最后一個元素不是指向NULL,而是指向頭結(jié)點;判斷是否為空是頭結(jié)點是否等于頭指針;若操作經(jīng)常在表頭和表尾進(jìn)行,可設(shè)置尾指針,這樣效率為0(1).循環(huán)雙鏈表:空表時頭結(jié)點的prior和next都是L.靜態(tài)鏈表:指針是數(shù)組下標(biāo)IaIT-1b|cITd||

偉）,杰詠時應(yīng)的第任表圖2/4靜態(tài)鏈表存儲示意圖第3章棧和隊列棧1.1棧的基本概念.棧的定義：只允許在一端進(jìn)行插入和刪除操作的線性表.棧頂(允許插入和刪除的一端)、棧底、空棧，后進(jìn)先出.棧的基本操作InitStack(&S)StackEmpty(S)Push(&S,x)Pop(&S,&x)GetTop(S,&x)ClearStack(&S)3.1.2棧的順序存儲結(jié)構(gòu)

.順序棧的實現(xiàn):用一維數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)一個指針(top)指示當(dāng)前棧頂位置?defineMaxSize50 〃定義棧中元素的最大個數(shù)typedefstruct(Elemtypedata[MaxSize]; 〃存放棧中元素inttop; //棧頂指針}SqStack;(D棧頂指針S.top初始為T,棧頂元素S.data[S.top](2)進(jìn)棧:棧不滿，棧頂指針先加1,再送值到棧頂元素(3)出棧:棧非空,先取棧頂元素值,再講棧頂指針減1(4)?？?S.top==-l,棧滿S.top==MaxSize-l,棧長S.top+1lop―?W*收 001個元素(c)5個元去 (<W個元索.順序棧的基本運算(1)初始化voidInitStack(sS)(s-top=-l； 〃初始化棧項指針)(2)判?？誗tackEmpty(S)(f(s.top==-l)StackEmpty(S)(f(s.top==-l) 〃棧空returntrue;Ise 〃不空returnfalse;1e)(3)進(jìn)棧boolPush(SqStack&S,ElemTypex){if(S.top==MaxSize-l) 〃棧滿,報錯returnfalse;S.data[++S.top]=x; 〃指針先加1,再入棧returntrue;I(4)出棧boolPop(SqStack4S,ElemType&x)(if(S.top==-1) 〃?？?，報錯returnfalse;x=S.data[S.top-]; 〃先出棧，指針再減1returntrue;)(5)讀棧頂元素boolGetTop(SqStackS,EleinType&x)(：if(S.top-1) ：//?？眨瑘箦e-returnfalse;1 -x=S.data[S.top]; 記錄棧頂元素returntrue;}3.共享棧:棧滿topl-top=l3.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)所有操作都是在單鏈表表頭進(jìn)行,第一個插入的結(jié)點在尾結(jié)點,之后依次往前插入,生成表頭注:n個不同的元素入棧，有個出棧序列隊列.1隊列的定義.隊列的定義:只允許在表的一端插入在另一端刪除,入隊和出隊,先進(jìn)先出2.隊列常見的基本操作InitQueue(&Q)QueueEmpty(Q)EnQueue(&Q,x)DeQueue(&Q,&x)GetHead(Q,&x)3.2.2隊列的順序存儲結(jié)構(gòu).隊列的順序存儲：附設(shè)兩個指針from和rear分別指示隊頭元素和隊尾元素的下一個位置?defineMaxSize50 〃定義隊列中元素的最大個數(shù)typed?fstruct(ElemTypedata[MaxSize]; 〃存放隊列元素intfront,rear; 〃隊頭指針和隊尾指針}SqQueue;初始狀態(tài)(隊空)：Q.front==Q.rear==0進(jìn)隊操作(隊不滿)：先送值到隊尾,再將隊尾指針加1出隊操作(隊不空)：先取隊頭值,再講隊頭指針加1.循環(huán)隊列(1)初始時:Q.front=Q.rear=O(2)隊首指針進(jìn)1:Q.front=(Q.front+l)%MaxSize(3)隊尾指針進(jìn)1:Q.rear=(Q.rear+l)%MaxSize(4)隊列長度：(Q.rear+MaxSize-Q.front)%MaxSize隊空條件：Q.front==Q.rearQ.front Q.front(dl)d.c、f,g入隊 ?E)d.e、f入隊為了區(qū)分隊滿還是隊空:犧牲一個單元,隊頭指針在隊尾指針的下一個位置作為隊滿標(biāo)志；隊滿條件為(Q.rear+l)%MaxSize==Q.front.循環(huán)隊列的操作(1)初始化voidInitQueue(&Q)(Q.rear-Q.front-0; //初始化隊首、隊尾指針)(2)判斷空b。。]isEmpty(Q)(if(Q.rear??Q.front)returntrue; 〃隊空條件elsereturnfalse;}(3)入隊boolEnQueue(SqQueue&Q,ElemTypex){if((Q.rear+1)%MaxSize==Q.front)returnfalse;〃隊滿Q.data[Q.rear)=x;Q.rear?(Q.rear+1)%MaxSize; 〃隊尾指針加1取模returntrue;用筆(4)出隊boolDeQueue(SqQueue&Q,ElemType&x){if(Q.rear=-Q.front)returnfalse; 〃隊空，報錯x=Q.data[Q.front];Q.fronts(Q.front+1)%MaxSize; 〃隊頭指針加1取模returntrue;}3.2.3隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu).隊列的鏈?zhǔn)酱鎯?是一個同時帶有隊頭指針和隊尾指針的單鏈表,頭指針指向隊頭結(jié)點,尾指針指向隊尾結(jié)點typedefstruct{ElemTypedata;//鏈?zhǔn)疥犃薪Y(jié)點structLinkNode*next;JLmkNode;typedefstructtypedefstruct{ElemTypedata;//鏈?zhǔn)疥犃薪Y(jié)點structLinkNode*next;JLmkNode;typedefstruct{LinkNode*frontz*rear;}LinkQueue;〃鏈?zhǔn)疥犃小犃械年狀^和隊尾指針當(dāng)Q.front==Q.rear==NULL時鏈隊列為空,通常將鏈隊列設(shè)td^一個頭結(jié)點.鏈隊列的基本操作（1）初始化voidInitQueue(LinkQueue&Q){Q.front-Q.rear=(LinkNode*)malloc(sizeof(LinkNode));//建立頭結(jié)點Q.front->next?NULL; 〃初始為空)(2)判斷空voidEnQueue(LinkQueue&QZElemTypex){s=(LinkNode*)malloc(sizeoz(LinkNode));s->data=x;s->next=NULL;〃創(chuàng)建新結(jié)點，插入到鏈尾Q.rear->next=s;Q.rear=s;}⑶入隊boolIsEmpty(LinkQueueQ){' ''t'' ' " " '(4)出隊boolDeQueue(LinkQueue4Q,ElenType&x){if(Q.fronts,rear)returnfalse;〃空隊p=Q.front->next;x=p->data；Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front; //若原隊列中只有一個結(jié)點，刪除后變空free(p);.2.4雙端隊列兩端均允許進(jìn)隊和出隊的隊列:重點是受限制的雙端隊列，即進(jìn)隊只有一端出隊有兩端或相反.3棧和隊列的應(yīng)用3.3.1棧在括號匹配中的應(yīng)用3.3.2棧在表達(dá)式求值中的應(yīng)用：中綴表達(dá)式與后綴表達(dá)式相互轉(zhuǎn)換.中綴表達(dá)式A+Bx(C-D)-E/F轉(zhuǎn)化為后綴表達(dá)式為ABCD-x+EF/-.操作:如果該項是操作數(shù),則將其壓入棧中；如果該項是操作符,則連續(xù)從棧中彈出操作數(shù)Y和X,做Y<op>X操作,并將其重新壓入棧.3.3棧在遞歸中的應(yīng)用：效率并不高.3.4隊列在層次遍歷中的應(yīng)用.3.5隊列在計算機(jī)系統(tǒng)中的應(yīng)用：緩沖區(qū)隊列.4特殊矩陣的壓縮存儲.4.1數(shù)組的定義.4.2數(shù)組的存儲結(jié)構(gòu)對于多維數(shù)組,可以分為按行優(yōu)先存儲和按列優(yōu)先存儲，但都是按順序存放在一個連續(xù)的空間中.4.3矩陣的壓縮存儲壓縮存儲:為多個值相同的元素只分配一個存儲空間，對0不分配存儲空間特殊矩陣:具有許多相同元素或0元素,分布有一定規(guī)律的矩陣(對稱矩陣、上下三角矩陣、對角矩陣).對稱矩陣:n階方陣中，按主對角線對稱,只存放主對角線和下三角元素(或上三角元素,又或按行或者按列存儲)(共n(n+l)/2).三角矩陣:上或下三角矩陣,其另外一角都為同一常數(shù),存儲完對角線和下三角元素后，緊接著存儲上三角元素一次(共n(n+D/2+l).三對角矩陣:所有元素集中在三條主對角線上,其余均為0;(i,j)元素在數(shù)組中的下標(biāo)為k=2i+j-3,反之,若元素在數(shù)組中第k個位置,則i=[(k+\)/3+\]j=k-2i+3i取下限4.4稀疏矩陣元素的個數(shù)遠(yuǎn)大于非0元素的個數(shù),此時需要一個三元數(shù)組,同時存放非0元素的行、列和值第4章樹與二叉樹1樹的基本概念樹的定義:只有一個根結(jié)點,其他結(jié)點稱為根結(jié)點的子樹1.樹的根結(jié)點沒有前驅(qū)結(jié)點,除根結(jié)點外所有結(jié)點只有一個前驅(qū)結(jié)點,所有結(jié)點可以有0或多個后繼結(jié)點;n個結(jié)點的樹有n-1個邊4.1.2基本術(shù)語（1）根往下走過的路徑直到尾結(jié)點K,前面所有結(jié)點都是K的祖先結(jié)點,K是前面所有結(jié)點的子孫結(jié)點,路徑上最接近K的結(jié)點叫K的雙親結(jié)點,K是其孩子結(jié)點,有相同雙親結(jié)點的叫兄弟結(jié)點（2）樹中一個結(jié)點的子結(jié)點（直接孩子結(jié)點）個數(shù)叫稱為該結(jié)點的度，樹中結(jié)點最大的度叫樹的度（3）度大于0的叫分支結(jié)點，又叫非終端結(jié)點,度為0的叫葉子結(jié)點（終端結(jié)點）（4）結(jié)點的層次,深度是從根結(jié)點開始自頂向下逐漸累加;高度是從葉子結(jié)點自底向上累加;樹的高度（深度）是樹中結(jié)點最大的層數(shù)（5）路徑和路徑長度:路徑長度是所經(jīng)過邊的個數(shù)（6）森林:是m>=0棵互不相交樹的集合4.1.3樹的性質(zhì)（1）樹中結(jié)點數(shù)等于所有結(jié)點度數(shù)加1（2）度為m的樹中第i層上至多有加一個結(jié)點（3）高度為h的m叉樹至多有（/_1）/（加_1）個結(jié)點（4）具有n個結(jié)點的m叉樹最小高度為+注意:設(shè)樹中度為i的結(jié)點個數(shù)為M（1）總結(jié)點數(shù)：N=N0+Nl+N2+...+Nm⑵總分支數(shù)：M=lxNl+2xN2+..+mxNm（3）N=M+T4.2二叉樹的概念4.2.1二叉樹的定義及主要特性.二叉樹的定義:不存在度大于2的結(jié)點,左右順序不能顛倒(1)二叉樹與度為2的樹的區(qū)別:度為2的樹至少有3個結(jié)點,而二叉樹可以為空;二叉樹有左右子樹之分,不能顛倒.幾個特殊的二叉樹(1)滿二叉樹:所有層都含最多個結(jié)點;對于滿二叉樹，對于編號為i的結(jié)點,若有雙親,則其雙親為若有左孩子為2i,右孩子為萬+1(2)完全二叉樹:每個結(jié)點的編號都與滿二叉樹一一對應(yīng);①若云|_〃/2」則結(jié)點i為分支結(jié)點,否則為葉子結(jié)點②葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)③如果有度為1的結(jié)點,則只能有1個,且該結(jié)點只有左孩子沒有右孩子④按層序編號后,一旦出現(xiàn)某結(jié)點(編號為i)為葉子結(jié)點或只有左孩子,則編號大于i的結(jié)點均為葉子結(jié)點⑤若n為奇數(shù),則每個結(jié)點都有左孩子和右孩子；若為偶數(shù),則編號最大的只有左孩子,無右孩子(b)完全二叉樹(3)二叉排序樹:左子樹上所有結(jié)點關(guān)鍵字小于根結(jié)點,右子樹上所有關(guān)鍵字大于根結(jié)點,左子樹和右子樹又是一個二叉排序樹(4)平衡二叉樹:樹上任意結(jié)點的左子樹和右子樹深度之差不超過1.二叉樹的性質(zhì)(1)非空二叉樹葉子結(jié)點數(shù)等于度為2的結(jié)點數(shù)+1,即N0=N2+l(2)非空二叉樹第k層上至多有2*一結(jié)點(3)高度為H的二叉樹至多有2"-i個結(jié)點(4)當(dāng)i>l時,結(jié)點i的雙親編號為即當(dāng)n為偶數(shù),雙親編號為i/2,它是雙親的左孩子;i為奇數(shù),雙親編號為(iT)/2,它是雙親結(jié)點的右孩子2i〈=N,結(jié)點的左孩子編號為2i,否則無左孩子2i+K=N,結(jié)點i的右孩子編號為2i+l,否則無右孩子(7)結(jié)點i所在層次為］k)g2i」+l(8)具有N個結(jié)點的完全二叉樹高度為［logzNj+l.2.2二叉樹的存儲結(jié)構(gòu)L順序存儲結(jié)構(gòu):按編號順序存放,完全二叉樹和滿二叉樹比較合適;要從數(shù)組下標(biāo)為1開始存儲.鏈?zhǔn)酱鎯Y(jié)構(gòu)Ichilddatarchild(1)二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)表示typedefstructBiTNode(ElemTypedata; 〃數(shù)據(jù)域structBiTNode*lchildr*rchild;//左、右孩子指針JBiTNode,*BiTree;在含有n個結(jié)點的二叉鏈表中含有n+1個空鏈域.3二叉樹的遍歷與線索二叉樹4.3.1二叉樹的遍歷.先序遍歷(NLR根左右)voidPreOrder(BiTreeT){if(T!-NULL){visit(T); 〃訪問根結(jié)點PreOrder(T->lchild); 〃遞歸遍歷左子樹PreOrder(T->rchild); 〃遞歸遍歷右子樹}}.中序遍歷(LNR左根右)3嬴渭…,ZnOrder(T->lchild); 〃遞歸遍歷左子樹visit(T); 〃訪問根結(jié)點InOrder(T->rchild); 〃遞歸遍歷右子樹.后序遍歷(LRN左右根)voidPostOrder(BiTreeT)(if(T!=NULL){PostOrder(T->lchild); 〃遞歸遍歷左子樹PostOrder(T->rchild); 〃遞歸遍歷右子樹visit(T)； //訪問根結(jié)點))時間與空間復(fù)雜度都是0(n).遞歸算法與非遞歸算法的轉(zhuǎn)換(借助棧)中序遍歷:先掃描根結(jié)點的所有左結(jié)點并將它們一一進(jìn)棧,然后出棧一個結(jié)點*p(p沒有左孩子結(jié)點或者左孩子結(jié)點被訪問過)，則訪問他;然后掃描右孩子結(jié)點,將其進(jìn)棧,再掃描右孩子結(jié)點所有左結(jié)點并一一進(jìn)棧,直到?？誺oidIn0rder2(BiTreeT){InitStack(S);BiTreep=T;while(p||lisEinpty(S)){

if(p)IPush(S.p);p=p->lchild;}else{Pop(S.p);visit(p);p-p->rchild;).層次遍歷:先將二叉樹根結(jié)點入隊,然后出隊訪問該結(jié)點,若它由左子樹,將左子樹入隊,若有右子樹將右子樹入隊.然后出隊,對出隊結(jié)點進(jìn)行訪問，如此反復(fù)voidLevelOrder(BiTreeT){InnitQueue(Q);BiTreep,EnQueue(Q,T),whi1e(IisEinpty(Q)){DeQueue(Q,p);visit(p);if(p->lchildl=NULL){EnQueue(Q,p->lchi1d),}if(p->rchildl=NULL){EnQueue(Q,p->rchild),)).由遍歷序列構(gòu)造二叉樹:先序序列和中序序列可以唯一確定一棵二叉樹，先序遍歷中第一個結(jié)點必定是根結(jié)點，中序遍歷中根結(jié)點必然將序列分為兩個子序列；同理,二叉樹后序序列和中序序列也能唯一確定一個二叉樹;注意,如果知道二叉樹先序序列和后序序列，不能唯一確定一個二叉樹例如，求先序序列(,BCDEFGHI)和中序序列(BcAeDGHFI)所確定的二叉樹。首先，由先序序列可向A為二叉樹的根結(jié)點。中序序列中A之前的BC為左子樹的中序序列，EDGHFI為右子樹的中序序列。然后由先序序列可知B是左子樹的根結(jié)點，D是右子樹的根結(jié)點。依此類推，就能將剩下的結(jié)點繼續(xù)分解下去，最后得到的二叉樹如圖心8(c).3.2線索二叉樹.基本概念:利用二叉樹中大量空鏈域(N個結(jié)點中有N+1個空指針)存放直接前驅(qū)或后繼的指針;線索化時規(guī)定,若無左子樹,令I(lǐng)child指向其前驅(qū)結(jié)點,若無右子樹,rchild指向其后繼結(jié)點afoIchild域指示結(jié)點的左孩子taS|lIchild域指示結(jié)點的前驅(qū)fOrchild域指示結(jié)點的右孩子1138|1rchild域指示結(jié)點的后繼線索二叉樹存儲結(jié)構(gòu)為：typedefstructThreadNode（ElemTypedata;structThreadNode*lchildt*rchild;intItag,rtag,/左右線索標(biāo)志}ThreadNode,*ThreadTree;這叫線索鏈表,其中指向其前驅(qū)和后繼的指針叫線索,線索二叉樹.線索二叉樹的構(gòu)造:遍歷一次二叉樹,遍歷過程中,檢查當(dāng)前結(jié)點左右指針域是否為空,若為空,將他們改為指向前驅(qū)或后繼的線索（標(biāo)識tag有孩子則為0,無則為1）圖4-10中序線索二叉樹及其二叉鏈表示注:有時為方便,在二叉樹線索鏈表上添加一個頭結(jié)點,并令其Ichild域指針指向二叉樹根結(jié)點,其rchild指向中序遍歷的最后一個結(jié)點;反之,令二叉樹第一個結(jié)點的Ichild和最后一個結(jié)點的rchild指向頭結(jié)點,變成一個雙向循環(huán)鏈表注:先序序列為n個順序的樹，不同二叉樹個數(shù)為」一。；.4樹森林4.1樹的存儲結(jié)構(gòu).雙親表示法:一組連續(xù)空間存儲每個結(jié)點,每個結(jié)點增設(shè)一個偽指針,指示其雙親在數(shù)組中位置（例下圖:根結(jié)點為下標(biāo)0,尾指針為-D；適合求雙親結(jié)點，不適合求孩子結(jié)點(?)然樹圖4J3樹的雙親表示法(c)(?)然樹圖4J3樹的雙親表示法(c)雙親指針圖示.孩子表示法:將每個結(jié)點的孩子結(jié)點用單鏈表連接起來;適合查找孩子結(jié)點,不適合雙親結(jié)點IIcIIIIAIIcIIIIA||回裝子表示法 (b)核子兄第表示法圖《14樹的孩子表示法和孩子兄弟表示法.孩子兄弟表示法：以二叉鏈表作為樹的存儲結(jié)構(gòu),包括結(jié)點值、指向結(jié)點第一個孩子結(jié)點和指向結(jié)點下一個兄弟結(jié)點的指針,方便實現(xiàn)樹轉(zhuǎn)化為二叉樹,易于查找結(jié)點的孩子(上圖).4.2樹、森林和二叉樹的轉(zhuǎn)換.樹轉(zhuǎn)化為二叉樹規(guī)則:每個結(jié)點左指針指向它第一個孩子結(jié)點,右指針指向它在樹中的相鄰兄弟結(jié)點，表示為“左孩子右兄弟”，由于根沒有右兄弟，所以樹轉(zhuǎn)化為二叉樹沒有右子樹圖445圖445樹轉(zhuǎn)挨為二叉樹.森林轉(zhuǎn)化為二叉樹:先將森林中每一棵樹轉(zhuǎn)化為二叉樹,再將第一棵樹的根作為轉(zhuǎn)化為二叉樹的根,第一棵樹的左子樹作為轉(zhuǎn)化后二叉樹根的左子樹,第二棵樹作為轉(zhuǎn)化后二叉樹的右子樹，第三棵樹作為轉(zhuǎn)化后二叉樹根的右子樹的右子樹,依次類推.二叉樹轉(zhuǎn)化為森林:二叉樹根及其左子樹為第一棵樹的二叉樹形式,二叉樹根的右子樹又可以看做是一個由除第一棵樹外的森林轉(zhuǎn)化后的二叉樹,應(yīng)用同樣的方法,直到最后產(chǎn)生一棵沒有右子樹的二叉樹為止,就得到了原森林注：(D樹轉(zhuǎn)化為二叉樹:在兄弟結(jié)點間加一條線;對每一個結(jié)點，只保留它與第一個子結(jié)點的連線,與其他子結(jié)點的連線全部抹掉；以樹軸為軸心，順時針旋轉(zhuǎn)45°(2)森林轉(zhuǎn)化為二叉樹:將每棵樹根相連,將森林中每棵樹轉(zhuǎn)化為相應(yīng)的二叉樹；以第一棵樹根軸心順時針旋轉(zhuǎn)45°.4.3樹和森林的遍歷.樹的遍歷(1)先根遍歷:與相應(yīng)的二叉樹的先序遍歷相同(2)后根遍歷:與相應(yīng)的二叉樹的中序遍歷相同(3)層次遍歷:與二叉樹一樣.森林的遍歷(1)先序遍歷森林:訪問森林每一棵樹根結(jié)點;先序遍歷第一棵樹中根結(jié)點子樹森林;先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林(2)中序遍歷森林：中序遍歷森林中第一棵樹的根結(jié)點的子樹森林;訪問第一棵樹根結(jié)點；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林.5樹與二叉樹的應(yīng)用4.5.1二叉排序樹.定義:簡稱BST,也稱二叉查找樹;左子樹值全部小于根結(jié)點值,右子樹值全部大于根結(jié)點值,左右子樹本身也是二叉排序樹,所以二叉排序樹中序遍歷可以得到一個遞增序列

.二叉排序樹查找:從根結(jié)點開始，沿某一條分支逐層向下進(jìn)行比較的過程,將給定值與根結(jié)點進(jìn)行比較,若相等,則查找成功;若根結(jié)點關(guān)鍵字大于關(guān)鍵字，在根結(jié)點左子樹中查找,否則在右子樹中查找,是一個遞歸的過程.二叉排序樹的插入:若關(guān)鍵字k小于根結(jié)點關(guān)鍵字,則插入左子樹中，相反插入右子樹中；一定插入了葉結(jié)點中.二叉排序樹的構(gòu)造:按二叉排序樹性質(zhì)進(jìn)行構(gòu)造.二叉排序樹的刪除:將單個元素刪除,其他因為此刪除的鏈再重新組合,確保性質(zhì)不變(1)若刪除是葉結(jié)點，則直接刪除(2)若結(jié)點z只有一棵左子樹或右子樹,則讓z的子樹成為z父結(jié)點的子樹，替代z位置(3)若結(jié)點z有左右兩棵子樹,則令z的直接后繼(或直接前驅(qū))代替z,然后從二叉排序樹中刪除這個直接后繼(或直接前驅(qū))左、右手樹均不空，在右子桃上找中序第一個子女填撲左、右手樹均不空，在右子桃上找中序第一個子女填撲=0>轉(zhuǎn)換為刷除81(?).二叉排序樹的查找效率分析⑴對于高度為H的二又排序樹,其插入和刪除操作的運行時間都是0(n).但在最壞的情況下,構(gòu)造二叉排序樹的輸入序列是有序的,則會形成一個傾斜的單支樹,此時二叉排序樹的性能顯變壞,樹的高度也增加為元素個數(shù)N,如下圖所示：在等概率情況下，圖4-23(a)的查找成功的平均查找長度為ASL=(1+2X2+3X4+4X3)/10=2.9而圖4-23(b)的查找成功的平均查找長度為由上可知,二叉排序樹查找算法的平均查找長度,主要取決于樹的高度，即與二叉樹的形態(tài)有關(guān).如果二叉排序樹是一個只有右(左)孩子的單支樹(類似于有序的單鍵表)，其平均查找長度和單鏈表相同，為0(n).如果二義排序樹的左、右子樹的高度之差的絕對值不超過1,這樣的二叉排序樹稱為平衡二叉樹.它的平均查找長度達(dá)到(2)二叉排序樹與二分查找:從查找過程看,二叉排序樹與二分查找相似.就平均時間性能而言,二叉排序樹上的查找和二分查找差不多.但二分查找的判定樹唯一,而二叉排序樹不唯一,相同的關(guān)鍵字其插入順序不同可能生成不同的二叉排序樹,如上圖所示;就維護(hù)表的有序性而言,二叉排序樹無須移動結(jié)點，只需修改指針即可完成插入和刪除操作，平均執(zhí)行時間為0(1%〃).二分查找的對象是有序順序表,若有插入和刪除結(jié)點的操作,所花的代價是0(n).當(dāng)有序表是靜態(tài)查找表時,宜用順序表作為其存儲結(jié)構(gòu),而采用二分查找實現(xiàn)其查找操作;若有序表是動態(tài)查找表,則應(yīng)選擇二又排序樹作為其邏輯結(jié)構(gòu)5.2平衡二叉樹.定義:要保證任意結(jié)點的左、右子樹高度差的絕對值不超過1,將這樣的二叉樹稱為平衡二叉樹,簡稱平衡樹(AVL樹)

I(?)平衡二又樹2(b)不平衡的二叉樹I(?)平衡二又樹2(b)不平衡的二叉樹圖4-24平衡二叉樹和不平衡的二叉樹.平衡二叉樹的插入:每當(dāng)二叉排序樹插入(或刪除)一個結(jié)點時,查看是否導(dǎo)致不平衡，若是則找到插入路徑上離插入結(jié)點最近平衡因子絕對值大于1的結(jié)點A,以A為根的子樹進(jìn)行調(diào)整達(dá)到平衡圖4-25圖4-25最小不平衡子樹示意LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))：由于在結(jié)點A的左孩子(L)的左子樹(L)上播入了新結(jié)點,A的平衡因子由1增至2,導(dǎo)致以A為根的子樹失去平衡,需要一次向右的旋轉(zhuǎn)操作.將A的左孩子B向右上旋轉(zhuǎn)代替A成為根結(jié)點,將A結(jié)點向右卜-旋轉(zhuǎn)成為B的右子樹的根結(jié)點,而B的原右子樹則作為A結(jié)點的左子樹圖4-26LL圖4-26LL平衡旋轉(zhuǎn)RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))：由于在結(jié)點A的右孩子(R)的右子樹(R)上插入了新結(jié)點,A的平衡因子由T減至-2,導(dǎo)致以A為根的子樹失去平衡,需要一次向左的旋轉(zhuǎn)操作.將A的右孩子B向左上旋轉(zhuǎn)代替A成為根結(jié)點,將A結(jié)點向左下旋轉(zhuǎn)成為B的左子樹的根結(jié)點,而B的原左子樹則作為A結(jié)點的右子樹

(a)插入結(jié)點柒(b)插入結(jié)點導(dǎo)致不平衡⑹(a)插入結(jié)點柒(b)插入結(jié)點導(dǎo)致不平衡⑹RR旋轉(zhuǎn)(左單旋轉(zhuǎn))圖4-27RR平衡旋轉(zhuǎn)LR平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))：由于在A的左孩子(L)的右子樹(R)上插入新結(jié)點,A的平衡因子由1增至2,導(dǎo)致以A為根的子樹失去平衡,需要進(jìn)行兩次旋轉(zhuǎn)操作,先左旋轉(zhuǎn)后右旋轉(zhuǎn).先將A結(jié)點的左孩子B的右子樹的根結(jié)點C向左上旋轉(zhuǎn)提升到B結(jié)點的位置,然后把該C結(jié)點向右上旋轉(zhuǎn)提升到A結(jié)點的位Bl.BR(?)插入結(jié)點前S4-28LR平衡旋轉(zhuǎn)e)插入結(jié)點導(dǎo)致不平街Bl.BR(?)插入結(jié)點前S4-28LR平衡旋轉(zhuǎn)e)插入結(jié)點導(dǎo)致不平街RL平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))：由于在A的右孩子(R)的左子樹(L)上插入新結(jié)點,A的平衡因子由T減至-2,導(dǎo)致以A為根的子樹失去平衡,需要進(jìn)行兩次旋轉(zhuǎn)操作,先右旋轉(zhuǎn)左旋轉(zhuǎn).先將A結(jié)點的右孩子B的左子樹的根結(jié)點C向右上旋轉(zhuǎn)提升到B結(jié)點的位置,然后把該C結(jié)點向左上旋轉(zhuǎn)提升到A結(jié)點的位置圖4-29RL圖4-29RL平衡旋轉(zhuǎn)3.平衡二叉樹的查找:假設(shè)以M表示深度為h的平衡樹中含有的最少結(jié)點數(shù).顯然N0=0,Nl=l,N2=2,并且有Nh= +N—+1,所有非葉結(jié)點平衡因子均為1,則結(jié)點數(shù)最少.可以證明，含有n個結(jié)點平衡二叉樹的最大深度為log,〃,因此，平衡二叉樹的平均查找長度為O(log2〃)圖4-30結(jié)點個數(shù)n最少的平說二又■樹5.3哈夫曼樹(Huffman)樹和哈夫曼編碼.哈夫曼樹的定義:樹中結(jié)點被賦予值(權(quán))，從樹根結(jié)點到任意結(jié)點的路徑長度(經(jīng)過的邊數(shù))與該點上權(quán)值的乘積稱為該結(jié)點的帶權(quán)路徑長度.樹中所有葉結(jié)點的帶權(quán)路徑長度之和稱為該樹的帶權(quán)路徑長度,記為叱z.=￡w,x/,式中,wi/=1是第i個葉結(jié)點所帶的權(quán)值;li是該葉結(jié)點到根結(jié)點的路徑長度.在含有N個帶權(quán)葉子結(jié)點的二又樹中，其中帶權(quán)路徑長度(WPL)最小的二叉樹稱為哈夫曼樹,也稱為最優(yōu)二叉樹.例如，下圖甲的3棵二叉樹，都有4個葉子結(jié)點a、b、c、d,分別帶權(quán)7、5、2、4、它們的帶權(quán)路徑長度分別為國*31具有不同帶權(quán)長度的二叉樹<a)WPL=7x2+5x2+2x2+4?2=36(b)WPL=7x3+5x3+2x1+4*2=46(c)WPL=7x1+5x2+2*3+4x3=35其中圖4-31(c)中樹的WPL最小.可以驗證，它恰為哈夫曼樹。.哈夫曼樹的構(gòu)造：(1)將這N個結(jié)點分別作為N棵僅含一個結(jié)點的二叉樹,構(gòu)成森林F(2)構(gòu)造一個新結(jié)點,并從F中選取兩棵根結(jié)點權(quán)值最小的樹作為新結(jié)點的左、右子樹，并且將新結(jié)點的權(quán)值置為左、右子樹上根結(jié)點的權(quán)值之和(3)從F中刪除剛才選出的兩棵樹，同時將新得到的樹加入F中(4)重復(fù)步驟(2)和(3),直至F中只剩下一棵樹為止.哈夫曼樹特點：(1)每個初始結(jié)點最終都成為葉結(jié)點，并且權(quán)值越小的結(jié)點到根結(jié)點的路徑長度越大(2)構(gòu)造過程中共新建了N-1個結(jié)點(雙分支結(jié)點)，因此哈夫曼樹中結(jié)點總數(shù)為2N-1(3)每次構(gòu)造都選擇2棵樹作為新結(jié)點的孩子,因此哈夫曼樹中不存在度為1的結(jié)點圖4-32哈夫曼樹的構(gòu)造過程.哈夫曼編碼:可變長度編碼比固定長度編碼好得多,其特點是對頻率高的字符賦以短編碼,而對頻率較低的字符則賦以較長一些的編碼,從而可以使字符平均編碼長度減短,起到壓縮數(shù)據(jù)的效果.如果沒有一個編碼是另一個編碼的前綴,則稱這樣的編碼為前綴編碼.如0、101和100是前綴編碼.對前綴編碼的解碼也是很簡單的，因為沒有一個碼是其他碼的前綴.所以,可以識別出第一個編碼,將它翻譯為原碼,再對余下的編碼文件重復(fù)同樣的解碼操作.如00101100可被唯一地分析為0、0、101和100由哈夫曼樹得到哈夫曼編碼是很自然的過程,首先,將每個出現(xiàn)的字符當(dāng)做一個獨立的結(jié)點，其權(quán)值為它出現(xiàn)的頻度(或次數(shù))，構(gòu)造出對應(yīng)的哈夫曼樹.顯然,所有字符結(jié)點都出現(xiàn)在葉結(jié)點中.我們可以將字符的編碼解釋為從根至該字符的路徑上邊標(biāo)記的序列,其中邊標(biāo)記為0表示“轉(zhuǎn)向左孩子”，標(biāo)記為I表示“轉(zhuǎn)向右孩子”.下圖所示為一個由哈夫曼樹構(gòu)造哈夫曼編碼示例，矩形方塊表示字符及其出現(xiàn)的次數(shù)圖右33由哈夫曼樹構(gòu)造哈夫曼編碼這棵哈夫曼樹的WPL為WPL=1/45+3x(13+12+16)+4x(5+9尸224第5章圖1圖的基本概念1.1圖的定義：圖G是頂點集V和邊集E組成，記為G=(V,E),其中V(G)表示圖G中頂點有限非空集,E(G)表示圖G中頂點之間關(guān)系(邊)的集合，圖中頂點個數(shù)也叫圖的階,圖不可以是空,邊集可以為空.有向圖:E是有向邊(也叫弧)的有限集合,G是有向圖,有向邊記為<v,w>,頂點V到頂點W.無向圖：(v,w).簡單圖:不存在重復(fù)邊,不存在頂點到自身的邊.完全圖:無向圖中任意兩個頂點之間都存在邊稱為無向完全圖,n個頂點無向完全圖有“("-1)/2條邊;有向圖中，任意兩定點間存在方向相反的兩條邊,稱為有向完全圖,n個頂點有條邊.子圖：兩個圖，圖VI的頂點是圖V2的子集,邊也是V2的子集,則VI是V2的子圖，但也可能不是圖，即VI不一定是V2子圖.連通、連通圖和連通分量:無向圖中，頂點v到w有路徑存在，則v和w是連通的，任意兩個頂點間都存在路徑則是連通圖;無向圖中極大連通子圖稱為連通分量,若有n個頂點,并且小于n-1條邊,則必為非連通圖;邊最少(n-1條)即構(gòu)成一個樹.強(qiáng)連通圖、強(qiáng)連通分量:有向圖中，從頂點v到w和從w到v都有路徑,則稱兩頂點是強(qiáng)連通的，任意一對頂點都是強(qiáng)連通的則是強(qiáng)連通圖;邊最少即構(gòu)成有向環(huán).生成樹:連通圖生成樹是包含全部頂點的一個極小連通子圖,頂點為n個,生成樹有n~l條邊.頂點的度、入度和出度:度是以該頂點為一個端點的邊的數(shù)目；對于無向圖,頂點度是依附于該頂點邊的條數(shù),全部頂點的度之和等于邊數(shù)的兩倍;有向圖入度是以頂點v為終點的有向邊的數(shù)目，出度是以頂點v為起點的有向邊的數(shù)目，頂點度等于出度和入度之和，有向圖全部頂點的入度之和和出度之和相等且等于邊數(shù).邊的權(quán)和網(wǎng):每條邊可以標(biāo)上有意義的數(shù)值,稱為邊的權(quán)值，圖稱為帶權(quán)圖（網(wǎng)）.路徑、路徑長度和回路:一個頂點到另一頂點全部路徑過程,路過邊數(shù)稱為路徑長度,第一個頂點和最后一個頂點相同的叫回路;一個圖有n個頂點,并且有大于n-1條邊,此圖一定有環(huán).距離:從頂點v到w最短路徑若存在,則叫距離.簡單路徑:頂點不重復(fù)出現(xiàn);除第一個和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路叫簡單回路 -.有向樹:一個頂點入度為0,其余入度全為1,則稱此有向 ,圖為有向樹5.2圖的存儲及基本操作5.2.1鄰接矩陣法（順序存儲）.定義:用一個一維數(shù)組存儲頂點，一個二維數(shù)組存儲邊的信息（各頂點之間鄰接關(guān)系），n個頂點是nxn的矩陣,若則A[i][j]=l,否則等于0；對于帶權(quán)圖,則鄰接矩陣中對應(yīng)項存放著該邊對應(yīng)的權(quán)值,若頂點vi和vj不相連,則用oo來表示這兩個頂點之間不存在邊.注意①無向圖的鄰接矩陣是對稱矩陣，對規(guī)模特大的鄰接矩陣可采用壓縮存儲②鄰接矩陣表示法的空間復(fù)雜的為0（n-2）,其中n為圖的定點數(shù)|V1.圖的鄰接矩陣存儲表示法具有以下特點：①無向圖的鄰接矩陣一定是一個對稱矩陣（并且唯一），因此,在實際存儲鄰接矩陣時只需存儲上（或下）三角矩陣的元素即可②對于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非無窮元素）的個

數(shù)正好是第i個頂點的度TD(vi)③對于有向圖，鄰接矩陣的第i行(或第i歹U)非零元素(或非無窮元素)的個數(shù)正好是第i個頂點的出度OD(vi)(或入度ID(vi)),第i行和第i列和是有向圖第i結(jié)點的度④用鄰接矩陣存儲圖，很容易確定圖中任意兩個頂點時間是否有邊相連.但是,要確定圖中有多少邊,則必須按行、按列對每個元素進(jìn)行檢測,所花費的時間代價很大.這是用鄰接矩陣存儲圖的局限性⑤稠密圖適合使用鄰接矩陣的存儲表示.2.2鄰接表法1.定義:對圖G中每個頂點建立一個單鏈表,第i個單鏈表結(jié)點表示依附于頂點vi的邊(有向圖是以頂點vi為尾的弧)<?）XMG圖%7無向圖鄰接表法實例PH<?）XMG圖%7無向圖鄰接表法實例PHI

iTi2M(a)fiMWG2.鄰接表特點僧3,鋁"a(1)如果G為無向圖，則所需存數(shù)空間為O(|V|+2|E|),若為有向圖，則需O(|V+|E|)(2)鄰接表中給定一頂點，能夠很容易找到所有鄰邊,而鄰接矩陣中需要掃描一行，時間為0(n);但是若要確定兩個頂點間是否存在邊,則在鄰接矩陣?yán)锟梢粤⒓床檎?而在鄰接表需要對相應(yīng)結(jié)點的邊表里查找另一結(jié)點,效率較低(3)有向圖鄰接表中,求一個給定頂點的出度只需計算其鄰接表結(jié)點個數(shù),但要求入度,需遍歷整表,也可用逆鄰接表5.3圖的遍歷從圖中某一頂點出發(fā),按照某種方式沿著圖中邊對圖中所有頂點訪問有且僅有一次5.3.1廣度優(yōu)先搜索(BFS).定義:首先由頂點V出發(fā),訪問V中各個未被訪問的鄰接結(jié)點,然后再依次訪問鄰接結(jié)點的未被訪問過的鄰接結(jié)點;是一種分層查找方式,每向前走一步,訪問一批結(jié)點,不是遞歸；為了實現(xiàn)逐層訪問，必須借助一個輔助隊列(例題見下圖)；圖的廣度優(yōu)先搜索與二叉樹的層序遍歷完全一致.算法性能分析:需要一個輔助隊列,最壞情況下,空間復(fù)雜度為0(IV|);鄰接表時間復(fù)雜度為0(1V[+|E|),鄰接矩陣時間復(fù)雜度為0(|Vl?).廣度優(yōu)先生成樹:廣度遍歷中，得到一顆遍歷樹,稱為廣度優(yōu)先生成樹;一給定圖的鄰接矩陣存儲是唯一的,故其廣度優(yōu)先生成樹也是唯一,但鄰接表存儲不唯一,故廣度優(yōu)先生成樹不唯一5.3.2深度優(yōu)先搜索(DFS).定義:類似于樹的先序遍歷,盡量進(jìn)行深層遍歷;從一個頂點出發(fā),挨個訪問其鄰邊未被訪問過的頂點,一直訪問到不能繼續(xù)進(jìn)行的時候退回到原來的頂點,退回路中挨個查找其鄰邊未被訪問過的頂點,并訪問之,一直退回到原點.算法性能分析:需要一個遞歸工作棧,空間復(fù)雜度為0(|V|),鄰接矩陣存儲，時間復(fù)雜度為0(|V12),鄰接表存儲,時間復(fù)雜度為0(|V|+|E|).深度優(yōu)先生成樹和森林:對連通圖調(diào)用DFS生成樹,否則生成森林3.3圖的遍歷與圖的連通性.圖的遍歷算法可以判斷圖的連通性;對于無向圖,若是連通,則從一點出發(fā),僅需一次遍歷就能訪問圖中所有結(jié)點,若是非連通,則一次只能訪問連通分量;對于有向圖,若從一個結(jié)點到每個結(jié)點都有路徑,則能夠訪問到圖中所有結(jié)點,否則不能.4圖的應(yīng)用4.1最小生成樹最ST).概念:一個連通圖的生成樹是圖的極小連通子圖;對于一個帶權(quán)無向圖,生成樹不同,每棵樹的權(quán)(權(quán)值之和)也可能不同,最小生成樹是權(quán)值最小的樹.最小生成樹性質(zhì)(1)最小生成樹樹形不唯一；圖中各權(quán)值互不相等時,G的最小生成樹唯一;若無向圖連通圖邊比頂點少1,即G本身就是一棵樹,G的最小生成樹就是本身(2)雖然最小生成樹不唯一，但最小生成樹邊的權(quán)值之和唯一且最小(3)最小生成樹邊數(shù)為頂點數(shù)減1.普里姆(Prim)算法(1)概念:算法從一個頂點開始,在此頂點對應(yīng)的結(jié)點中尋找最小權(quán)值的結(jié)點連接,如此往復(fù),直至滿了為止,此時樹必有n-1條邊圖5-20Prim算法構(gòu)造最小生成樹的過程(2)時間復(fù)雜度:0(|V|2),不依賴于|E|,適用于求解稠密圖的最小生成樹.克魯斯卡爾(Kruskal)算法(1)按權(quán)值遞增序列選擇合適的邊來構(gòu)造最小生成樹,開始時,每個頂點構(gòu)成一棵獨立的樹,T此時為僅含V各結(jié)點的森林,按G的邊的權(quán)值遞增順序選擇一條邊,若這條邊加入不構(gòu)成回路,則將其加入,否則舍棄,直到含有n-1條邊;構(gòu)造時按網(wǎng)中權(quán)值由小到大的順序,不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊，選取n-1條邊

圖5-21Kniskal算法構(gòu)造最小生成樹的過程(2)時間復(fù)雜度:采用堆存放邊的集合,0(|E|log|E|),適用于邊稀疏而頂點較多的圖5.4.2最短路徑概念:對于帶權(quán)圖,路徑上權(quán)值之和最小的叫最短路徑;帶權(quán)有向圖G的最短路徑問題,一般分為兩類，一類是單源最短路徑，即求某一頂點到其他各頂點的最短路徑,通過Dijkstra算法,二是求每一對頂點間的最短路徑,用Floyd算法Dijkstra算法求單源最短路徑(1)概念:從某一頂點出發(fā),求到另一頂點的最小路徑(帶權(quán)值)，可以從一頂點出發(fā)挨個搜尋,每一趟都需要得到最短的路徑,求的是一頂點到所有其他頂點的路徑每趟得到的最短路徑為每趟得到的最短路徑為：第1趟：路徑距離為5第2趟：1-5-4,躋囹巨離為7第3趟：1-5-2,路徑距離為8第4趟：1-5—2-3,路徑距離為9圖5-22應(yīng)用Dijkstra算法圖表5-1從V)到各線點的dist值和最短路徑的求解過程頂點第1越第2盤第3趟第4越210Vl-VjS哂一打”蹩8丫「*￥5—丫23814Vi--V}-VJ13Vj-*Vs-V4-*V39Vj—VS-V2-*Vj487VLY5f455vi-叼篥合S(b5)n.5,4)n>5,4,2)(1.5,4.2,3)(2)時間復(fù)雜度:鄰接矩陣為0(IV[②)，鄰接表為0(|V12),若要找出所有結(jié)點之間最短距離,則時間復(fù)雜度為o(M13)(3)注意:若有負(fù)權(quán)值,此算法不適用Floyd算法求各頂點間最短路經(jīng)過⑴產(chǎn)生一個n階方陣/（*）國［力&從T開始到nT）表示從頂點vi到vj路徑長度,k表示繞行第k個頂點運算步驟;初始時,vi和vj之間存在邊,則以此邊權(quán)值作為最短路徑,若不存在邊則以無窮作為權(quán)值；以后逐步加入頂點k作為中間頂點,若增加中間結(jié)點得到的路徑比原路徑減少了，則以此新路徑代替原來路徑圖5-24帶權(quán)有向圖G及其鄰接矩陣表5-2Floyd算法的執(zhí)行過程（2）時間復(fù)雜度:0（|V|3）（3）注意：允許帶負(fù)權(quán)值的邊，但不允許包含帶負(fù)權(quán)值的邊組成的回路，也適用于帶權(quán)無向圖4.3拓?fù)渑判?有向無環(huán)圖:有向圖中不存在環(huán),稱為DAG圖.A0V網(wǎng):用DAG圖表示一個工程,頂點表示活動,有向邊＜v,w＞表示v必須先于w,稱為A0V網(wǎng).拓?fù)渑判蛞粋€有向無環(huán)圖頂點組成的序列滿足下列條件①每個頂點出現(xiàn)僅出現(xiàn)一次②若頂點A排在B前面,則不存在從B到A的路徑（2）對一個DAG圖進(jìn)行拓?fù)渑判颌購腄AG中選擇一個沒有前驅(qū)的頂點并輸出②從圖中刪除該頂點和所有以它為起點的有向邊③重復(fù)（1）（2）直到DAG圖為空或者圖中不存在無前驅(qū)頂點為止,而后一種情況說明有向圖必存在環(huán)圖5-25有向無環(huán)圖的拓?fù)渑判蜻^程于是，得到拓?fù)渑判蚝蟮慕Y(jié)果為｛1,2,4,3,5).(3)時間復(fù)雜度:O(|V|+|E|)(4)用拓?fù)渑判蛩惴ㄌ幚鞤AG圖時,注意：①一個頂點有多個直接后繼,拓?fù)渑判虿晃ㄒ?但若各個頂點已經(jīng)排在一個線性有序序列中，每個頂點有唯一前驅(qū)后繼關(guān)系,則結(jié)果唯一②對于一般的圖,若它的鄰接矩陣是三角矩陣,則存在拓?fù)湫蛄?.4.4關(guān)鍵路徑.AOE網(wǎng)(D概念:帶權(quán)有向圖中以頂點表示事件,有向邊表示活動,邊上權(quán)值表示完成的開銷,稱為AOE網(wǎng),邊上的權(quán)值表示活動的持續(xù)時間(2)A0E網(wǎng)性質(zhì)：(1)只有某頂點表示的事件發(fā)生后,從該頂點出發(fā)的有向邊所表示的活動才能開始(2)只有在進(jìn)入某一頂點各有向邊所代表的活動都已經(jīng)結(jié)束時,該頂點所代表的事件才能發(fā)生AOE網(wǎng)中只有一個源點(入度為0)表示工程開始，也只有一個匯點(出度為0)表示工程結(jié)束(4)只有路徑上所有活動都完成了，整個工程才結(jié)束,從源點到匯點的最大路徑長度的路徑稱為關(guān)鍵路徑,關(guān)鍵路徑上的活動叫關(guān)鍵活動(e(i)=l(i))(5)最短時間就是關(guān)鍵路徑長度,也就是關(guān)鍵路徑上各活動花費開銷之和.參量定義(1)事件Vk最早發(fā)生時間Ve(k):從V(源點)到Vk最長路徑長度(從前往后計算)(2)事件Vk最遲發(fā)生時間VI(k):指在不推遲整個工程完成前提下，保證它所指向的事件vi在Ve(i)時刻能夠快速發(fā)生時,該事件遲早必須發(fā)生的時間(從最后向前計算)(3)活動ai最早發(fā)生的時間e(i):指該活動起點所表示的事件最早發(fā)生的時間(4)活動ai最遲發(fā)生的時間l(i):指該活動終點所表示的事件最遲發(fā)生時間與該活動所需時間之差一個活動最遲開始時間l(i)與最早開始時間e(i)差額d(i)=l(i)-e(i):指活動完成時間余量,是在不增減整個完成整個工程所需時間情況下,活動ai可以拖延的時間，如果一個活動時間余量是0,該活動必須如期完成，當(dāng)Hi)=e⑴表示活動ai是關(guān)鍵活動7.求關(guān)鍵路徑步驟(1)求AOE網(wǎng)中所有事件最早發(fā)生時間ve()(2)求AOE網(wǎng)中所有事件最遲發(fā)生時間vl()(3)求AOE網(wǎng)中所有活動最早開始時間e()(4)求AOE網(wǎng)中所有活動最遲開始時間1。(5)求AOE網(wǎng)中所有活動的差額d(),找出所有d()=0的活動構(gòu)成關(guān)鍵路徑l-eI0I10 3 0]圖626求解關(guān)鍵路徑的過程注：(1)可以判斷有向圖是否有環(huán):深度優(yōu)先遍歷、拓?fù)渑判?、關(guān)鍵路徑(2)不存在拓?fù)渑判虻挠邢驁D，必存在回路(3)只有關(guān)鍵路徑上所有活動時間同時減少,才能縮短工期第6章查找6.1查找的基本概念1.基本概念

(1)分為查找成功和查找失敗(2)靜態(tài)查找表:無需動態(tài)修改查找表(順序查找、折半查找、散列查找)；動態(tài)查找表:需要動態(tài)修改和刪除的查找表(二叉排序樹查找、散列查找)(3)平均查找長度:一次查找長度是需要比較的關(guān)鍵字的次數(shù)6.2順序查找和折半查找6.2.1順序查找.概念:主要用于線性表中查找,分為無序線性表和有序線性表查找.一般線性表順序查找(1)從線性表一端開始逐個關(guān)鍵字是否滿足要求,若滿足則查找成功,若查找到末尾還未查找到則失敗,其中引入哨兵作用是不必判斷數(shù)組是否越界,因為當(dāng)i==0時,循環(huán)一定會跳出typedefstruct( 〃查找表的數(shù)據(jù)結(jié)構(gòu)ElemType*elem; 〃元素存儲空間基址，辱時按實際長度分聞，。節(jié)單元留空.若找到則返回該元素在表中的位置intTableLen;〃表的長度.若找到則返回該元素在表中的位置}SSTable;intSearch_Seq(SSTableST,ElemType〃在順序表ST中順序查找關(guān)鍵字為key的元jST.elem[O]=key; //“哨兵”for(i-ST.TableLen;ST.elem[iJ.!=key;-i)〃從后往前找returni;〃若表中不存在關(guān)鍵字為key的元素，將查找到i為0時退出for循環(huán))2)ZSL成功=(n+l)/2,ZSL不成功=n+l;當(dāng)n較大時，平均查找長度較大，效率低；優(yōu)點是對元素存儲無要求;對線性的鏈表只能順序查找.有序表的順序查找(D概念:查找失敗時可以不用再比較到表的另一端就能返回查找失敗的信息，可以用如下判定樹表示查投序列(10,2030,40^0,60,)查找25 3；屈義向 查找40|(~°°,10)[25>20|(IOqO)IU30)><??3025001(2O.3Ci)| <'@l>40=40|(30.40)I(350)「"

|(50,60)[~ |(60,°°)|(2)4st成功=(n+l)/2，“s”或功6.2.2折半查找L概念:又叫二分查找，僅適用于按關(guān)鍵字排列有序的順序表.算法intBinary_Search(SeqListL,ElemTypekey)(〃在有序表L*查找關(guān)鍵字為key的元素，若存在則返回其位置，不存在則返回7intlow?0,high-L.TableLen-1,nid;while(low<?high>{mid=(low+high)/2; 〃取中間位置if(L.elem[mid]"?key)returnmid; 〃查找成功則返回所在位置elseif(L.elemfnid)>key)high-mid-1; 〃從前半部分繼續(xù)查找elselow-mid+1; 〃從后半部分繼續(xù)查找return-1;}例題：已知11個元素有序表億10,13,16,19,29,32,33,37,41,43)，查找11和32,可以用如下二叉樹表示查找過程;樹最下面都是方形,表示查找不成功的情況;查找成功的查找長度為從根結(jié)點到目的結(jié)點的路徑上的結(jié)點數(shù),而不成功的情況為從根結(jié)點到對應(yīng)失敗結(jié)點的父結(jié)點路徑上結(jié)點數(shù);若有序序列有n個結(jié)點,判定樹有n個圓形非葉子結(jié)點和n+1個方形葉結(jié)點,是為二叉排序樹查找成功:ASL=(lxl+2x2+3x4+4x4)/ll=3,查找不成功ASL=(3x4+4x8)/12=11/3.效率:查找成功平均長度為ASL=log2(M+l)-l,元素個數(shù)為n的樹高他即查找不成功的查找長度)為〃邛Og2(〃+1)1(往上進(jìn))，時間復(fù)雜度為O(log2〃)6.2.3分塊查找.概念:將查找表分為若干個子表,塊內(nèi)可以無序,塊間有序,即第一個塊關(guān)鍵字小于第二個塊中所有記錄的關(guān)鍵字,依次類推,再建立一個索引表,索引表中每個元素含有各塊最大關(guān)鍵字和各塊的第一個元素的地址,索引表按關(guān)鍵字有序排列.查找過程:第一步在索引表確定待查記錄所在塊,可以順序可以折半，第二步快內(nèi)順序查找例如，關(guān)鍵碼窠合為（88,24,72.61,21,6,32,II,8.31.22,83,78.54）,按照關(guān)鍵碼值為24、54,78、88.分為四個塊和索引表，如圖a3所示.1E找寰白|21|6|11|8|22|32|31|幺|72|61|78|88|83|圖6-3分塊有找示意圖.查找長度:長度為n表均勻分為b塊，每塊s個記錄,ASL=^+—=-+2s+〃，若§=0，則平均查找長度取最小心+1,若對索2 22s引表采用折半查找，則4SA=「log2（〃+l）］+等6.3B樹和B+樹6.3.1B樹及其基本操作概念:又稱多路平衡查找樹,B樹中所有結(jié)點孩子結(jié)點數(shù)的最大值稱為B樹的階,用m表示,一棵m階B樹或為空樹,或有如下特征：（1）樹中每個結(jié)點至多m個子樹（至多mT個關(guān)鍵字）（2）若根結(jié)點不是終端結(jié)點，則至少有兩棵子樹（3）除根結(jié)點外所有非葉子結(jié)點至少有「加/21棵子樹（至少有「m/21T個關(guān)鍵字）（4）所有葉結(jié)點都出現(xiàn)在同一層上，并且不帶任何信息圖&53階B樹木意圖B樹的高度（磁盤存取次數(shù),不包括最后一層不帶任何信息的葉結(jié)點所在層）（1）n個關(guān)鍵字,m階B樹,高度為logm（?+1）</?<logrm/2l（（/7+1）/2）+1（2）若讓每個結(jié)點中關(guān)鍵字個數(shù)最少,第一層1個,第二層2個,除根結(jié)點外每個非終端結(jié)點至少「%/21棵子樹,依次排列,可讓容納同樣多的關(guān)鍵字的B樹達(dá)到最高B樹的查找B樹的插入（1）定位:找出插入該關(guān)鍵字最底層中某個非葉結(jié)點（B樹中插入的關(guān)鍵字一定是插入最底層非葉結(jié)點內(nèi)）（2）插入:插入后檢查被插入結(jié)點內(nèi)關(guān)鍵字個數(shù),若大于m-1個,則必須進(jìn)行分裂（3）分裂的方法:取一個新結(jié)點,將插入key后的原結(jié)點從中間位置將其中的關(guān)鍵字分為兩部分,左部分包含的關(guān)鍵字放在原結(jié)點中，右部分包含的關(guān)鍵字放到新的結(jié)點中，中間位置「加/2］的結(jié)點插入到原結(jié)點的父結(jié)點中.若此時導(dǎo)致其父結(jié)點的關(guān)鍵字個數(shù)也超過了上限,則繼續(xù)進(jìn)行這種分裂操作,直至這個過程傳到根結(jié)點為止,這樣導(dǎo)致B樹高度增1例:對于如下m=3的B樹,分裂操作如下（1）要使得刪除后的結(jié)點關(guān)鍵字個數(shù)涉及合并問題（2）當(dāng)所刪除的關(guān)鍵字k不在終端結(jié)點（最底層非葉結(jié)點）中時,有下列幾種情況：1）如果小于k的子樹中關(guān)鍵字個數(shù)＞「加/21-1,則找出k的前驅(qū)值k',并且用k'來取代k,再遞歸地刪除k'即可2）如果大于k的子樹中關(guān)鍵字個數(shù)＞「〃7/2~|T,則找出k的后繼值k',并且用k，來取代k,再遞歸地刪除k'即可3）如果前后兩個子樹中關(guān)鍵字個數(shù)均為「而/21-1,則直接將兩個子結(jié)點合并,直接刪除k即可圖&7B樹中則除非終端結(jié)點關(guān)鍵字的合并（3）當(dāng)被刪除的關(guān)鍵字在終端結(jié)點（最底層非葉子結(jié)點），有以下幾種情況1）直接刪除關(guān)鍵字:若被刪除關(guān)鍵字所在結(jié)點關(guān)鍵字個數(shù)＞「加/21-12）兄弟夠借:若被刪除關(guān)鍵字所在結(jié)點刪除前關(guān)鍵字個數(shù)=「加/2]-1,且與此結(jié)點相連的左（右）兄弟結(jié)點關(guān)鍵字個數(shù)需要調(diào)整左右兄弟結(jié)點以及雙親結(jié)點，以達(dá)到平衡3）兄弟不夠借:若被刪除關(guān)鍵字所在結(jié)點刪除前關(guān)鍵字個數(shù)=,/21-1,且與此結(jié)點相連的左（右）兄弟結(jié)點關(guān)鍵字個數(shù)=「加/211,則將關(guān)鍵字刪除后與左（右）兄弟結(jié)點及雙親結(jié)點中關(guān)鍵字進(jìn)行合并注意:在合并的過程中，雙親結(jié)點中的關(guān)鍵字個數(shù)會減少.若其雙親結(jié)點是根結(jié)點并且關(guān)鍵字個數(shù)減少至0（根結(jié)點關(guān)鍵字個數(shù)為1時，有2棵子樹），則直接將根結(jié)點刪除,合并后的新結(jié)點成為根;若雙親結(jié)點不是根結(jié)點,且關(guān)鍵字個數(shù)減少到又要與它自己的兄弟結(jié)點進(jìn)行調(diào)整或合并操作，并重復(fù)上述步驟，直至符合B樹的要求為止兄弟夠借 （b）兄弟不夠借3.2B+樹的基本概念（支持順序查找,B樹不支持）.一棵m階的B+樹需滿足下列條件：1）每個分支結(jié)點最多有m棵子樹（子結(jié)點）2）非葉根結(jié)點至少有兩棵子樹,其他每個分支結(jié)點至少有「m/21棵子樹3）結(jié)點的子樹個數(shù)與關(guān)鍵字個數(shù)相4）所有葉結(jié)點包含全部關(guān)鍵字及指向相應(yīng)記錄的指針,而且葉結(jié)點中將關(guān)鍵字按大小順序排列.并且相鄰葉結(jié)點按大小順序相互鏈接起來5）所有分支結(jié)點（可看成是索引的索引）中僅包含它的各個子結(jié)點（即下一級的索引塊）中關(guān)鍵字的最大值及指向其子結(jié)點的指針.m階的B+樹與m階的B樹的主要差異在于：1）在B+樹中，具有n個關(guān)鍵字的結(jié)點只含有n棵子樹,即每個關(guān)鍵字對應(yīng)一棵子樹;而在B樹中，具有n個關(guān)鍵字的結(jié)點含有（n+1）棵子樹2）在B+樹中，每個結(jié)點（非根內(nèi)部結(jié)點）關(guān)鍵字個數(shù)n的范圍是pn/2~|Wn/m（根結(jié)點:lWnWm）,在B樹中，每個結(jié)點（非根內(nèi)部結(jié)點）關(guān)鍵字個數(shù)n的范圍是pn/2~|-lWnWmT（根結(jié)點:1WnWmT）3）在B+樹中，葉結(jié)點包含信息,所有非葉結(jié)點僅起到索引作用，非葉結(jié)點中的每個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針,不含有該關(guān)鍵字對應(yīng)記錄的存儲地址4）在B+樹中，葉結(jié)點包含了全部關(guān)鍵字，即在非葉結(jié)點中出現(xiàn)的關(guān)鍵字也會出現(xiàn)在葉結(jié)點中；而在B樹中，葉結(jié)點包含的關(guān)鍵字和其他結(jié)點包含的關(guān)鍵字是不重復(fù)的如下圖所示為一棵4階B+樹的示例.從圖中可以看出，分支結(jié)點的某個關(guān)鍵字是其子樹中最大關(guān)鍵字的副本.通常在B+樹中有兩個頭指針:一個指向根結(jié)點,另一個指向關(guān)鍵字最小的葉結(jié)點.因此,可以對B+樹進(jìn)行兩種查找運算:一種是從最小關(guān)鍵字開始的順序查找,另一種是從根結(jié)點開始,進(jìn)行多路查找.4散列表6.4.1散列表基本概念.概念:之前的算法建立在“比較”基礎(chǔ)上，效率取決于比較次數(shù)(1)散列函數(shù):將關(guān)鍵字映射成該關(guān)鍵字對應(yīng)地址的函數(shù)，記為Hash(key)=Addr,散列函數(shù)會把兩個不同的關(guān)鍵字映射到同一地址，稱為“沖突”，發(fā)生碰撞的不同關(guān)鍵字稱為同義詞;應(yīng)盡量減少沖突，設(shè)計好的處理沖突的方法(2)散列表:建立了關(guān)鍵字和存儲地址之間直接映射關(guān)系4.2散列函數(shù)的構(gòu)造方法1)函數(shù)定義域必須包括全部需要存儲的關(guān)鍵字2)散列函數(shù)計算出的地址能夠等概率、均勻分布在整個地址空間,減少沖突3)散列函數(shù)盡量簡單,較短時間內(nèi)能計算出任意關(guān)鍵字的地址.直接定址法:散列函數(shù)為//(%ey)=axhy+b；不會產(chǎn)生沖突,適合關(guān)鍵字分布基本連續(xù)的情況,若分布不連續(xù),則空位較多,造成空間浪費.除留余數(shù)法:假定表長為m,取一個不大于m但最接近或等于m的質(zhì)數(shù)p,散列函數(shù)為〃(《曲)=Aey%p(需要選取好P).數(shù)字分析法:適合與關(guān)鍵字已知的集合.平方取中法:取關(guān)鍵字平方值中間幾位作為散列地址，適用于關(guān)鍵字每一位取值都不夠均勻或均小于散列地址所需位數(shù).折疊法:適用于關(guān)鍵字位數(shù)很多,而且關(guān)鍵字每一位數(shù)字分布大致均勻.4.3處理沖突的方法為產(chǎn)生沖突的關(guān)鍵字尋找下一個“空”的Hash地址,用Hi表示沖突后第i次探索的散列地址.開放定址法：Hi=("(左")+4)%m,m表示表長,di表示增量(1)線性探索法:di=l開始,每次遞增1,向后查找空位,直到找到一個空位或查遍全表;缺點:可能使第i個散列地址同義詞存在第i+1個，造成大量相鄰的散列地址聚集,大大降低了查找效率(2)平方探測法：4=12,t2,22,_22..,%4m/2,m=4k+3,又稱二次探測法;可以避免堆積問題,缺點是不能探測到表的全部單元，但至少可以探測到一半(3)再散列法:使用兩個散列函數(shù)進(jìn)行散列注意:不能隨便刪除表中元素，因為若刪除元素將會截斷其他具有相同散列地址的元素的查找地址,所以要想刪除一個元素,給它做一個標(biāo)記,進(jìn)行邏輯刪除，但副作用是表面上看起來散列表很滿，實際上有許多位置沒有利用.拉鏈法(1)為避免非同義詞發(fā)生沖突,可以把所有同義詞存儲在一個線性鏈表中，這個線性鏈表由散列地址唯一標(biāo)識,拉鏈法適用于經(jīng)常進(jìn)行插入和刪除的情況例如，關(guān)鍵字序列為｛19,14,23,01,68,20,84,27,55,II,10,79),散列函數(shù)H(key尸key%l3,用拉鏈法處理沖突，建立的表如B96J2所示.oT*三國工H衛(wèi)13mHiE0AmnwKBA2 按大小進(jìn)行排序s~9A.io~-<irn-42r^i--H11hiT4.4散列查找及性能分析.散列查找(1)初始化:根據(jù)散列函數(shù)計算出散列地址,addr=Hash(key)(2)檢測表中addr位置上是否有記錄,沒有記錄則失敗;若有記錄比較它與key值,若相等返回成功標(biāo)志,不然執(zhí)行下面(3)(3)用給定的處理沖突的方法計算“下一散列地址”，并把addr置為此地此轉(zhuǎn)入⑵例如，關(guān)鍵字序列｛19,14,23,01,68,20,84,27,55,11,10,79｝按散列函數(shù)H(key)=key%13和線性探測處理沖突構(gòu)造所得的散列表L如圖6-13所示。0 1 2 3 4 5 6 7 8 9 10II12 13 14 15140168275519208479231110圖6-13用線性探測法得到的散列表L給定值84的查找過程為：苜先求得散列地址H(84)=6,因L[6]不空且U6p84,則找第一次沖突處理后的地址Hi=(6+1)%16=7,而L[7]不空且L[7]W84,則找第二次沖突處理后的地址H2=(6+2)%16=8,L網(wǎng)不空且L[8]=84,查找成功，返回記錄在表中的序號8.給定值38的查找過程為：先求散列地址H(38)=12,L[12]不空且L[12]#38,則找下一地址Hi=(12+l)%16=13,由于L[13]是空記錄，故表中不存在關(guān)鍵字為38的記錄..散列查找效率:取決于散列函數(shù)、處理沖突方法和裝填因子.裝填因子：,一表中記錄數(shù)n,平均查找長度依賴于裝填因子；a越大,裝填記一散列表長度m錄越滿,沖突可能性越大,散列表查找成功與a有關(guān),與表長無關(guān)第7章排序1.1排序的定義.定義:按關(guān)鍵字遞增或遞減.算法的穩(wěn)定性:排序中兩個元素相等,排序后位置不發(fā)生變化說明算法穩(wěn)定,主要是對算法性質(zhì)的描述,不能衡量算法優(yōu)劣.內(nèi)部算法通常進(jìn)行：比較+移動,基數(shù)排序不是基于比較的7.2插入排序基本思想是每次將一個待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中，直到全部記錄插入完成,每次插入便又多一個元素排好相對順序7.2.1直接插入排序.將第i個元素插入到前面已經(jīng)排序好的i-1的元素中，步驟為：(1)查找出L(i)在L[L.i-1]中位置k(2)將L[k..i-1]中所有元素全部后移一位(3)將L(i)復(fù)制到L(k)voidInsertSort(ElemTypeA(intn)(inti,j；for(i=2;i<=n;i+^) 〃依次將M2]?插入到前面己排序序列