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

《數(shù)據(jù)結(jié)構(gòu)》考前沖刺大綱講義總結(jié)緒論數(shù)據(jù)結(jié)構(gòu)的基本概念基本概念和術(shù)語.數(shù)據(jù).數(shù)據(jù)元素:可由若干數(shù)據(jù)項(xiàng)組成,數(shù)據(jù)項(xiàng)是不可分割的最小單位.數(shù)據(jù)對象:具有相同性質(zhì)的數(shù)據(jù)元素的集合.數(shù)據(jù)類型:是一個(gè)值的集合和定義在此集合上一組操作的總稱.抽象數(shù)據(jù)類型(ADT):包括數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作集.數(shù)據(jù)結(jié)構(gòu):邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算1.2數(shù)據(jù)結(jié)構(gòu)的三要素.邏輯結(jié)構(gòu)：分為線性和非線性結(jié)構(gòu).存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：包括順序、鏈?zhǔn)?、索引和散列存?chǔ).數(shù)據(jù)的運(yùn)算:運(yùn)算的定義和實(shí)現(xiàn).2算法和算法評價(jià).2.1算法的基本概念.五個(gè)重要特性:有窮、確定、可行、輸入和輸出.好的算法目標(biāo):正確性、可讀性、健壯性、高效率與低存儲(chǔ)量1.2.2算法效率的度量.時(shí)間復(fù)雜度：7(〃)=。(/(〃))，通常指最壞情況下時(shí)間復(fù)雜度.空間復(fù)雜度:原地工作指算法所需的輔助空間是常量第2章線性表線性表的定義及基本操作1.1線性表的定義.線性表是具有n個(gè)相同類型數(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開始.線性表的順序存儲(chǔ)類型(1)一位數(shù)組靜態(tài)分配(1)一位數(shù)組靜態(tài)分配?defineMaxSize50typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;(2)動(dòng)態(tài)分配#defineInitSize100typedefstruct{ElemType*data;intMaxSize,length;}SeqList;〃定義線性表的最大長度〃順序表的元素〃順序表的當(dāng)前長度〃順序表的類型定義〃表長度的初始定義〃指示動(dòng)態(tài)分配數(shù)組的蛆/麗麗O%量融前社〃動(dòng)態(tài)分配數(shù)組順序表的類型定義C的初始動(dòng)態(tài)分配語句C的初始動(dòng)態(tài)分配語句L.data*InitSize);.順序表特點(diǎn):隨機(jī)訪問，存儲(chǔ)密度高,插入和刪除需要移動(dòng)大量元素.2.2順序表上基本操作的實(shí)現(xiàn)(1)插入:在第i個(gè)位置插入e(\<i<LJength+\),i不合法則返回false;否則,將第i個(gè)元素及其后所有元素右移一個(gè)位置;插入e,表長加1,返回true(從后往前依次后移一個(gè))boolListinsert(SqList i,ElemTypee){〃本算法實(shí)現(xiàn)將元素e插入到順序表L中第i個(gè)位置if<i<l||i>L.length+l) //判斷i的范圍是否有效returnfalse;if(L.length>=MaxSize) 〃當(dāng)前存儲(chǔ)空間已滿，不能插入returnfalse;for(intj=L.length;j>-i;j-) 〃將第i個(gè)元素及之后的元素后移L.data(j]-L.data,Li-Ur : .=''L.datafi-11-e； 〃在位置i處放入e ..L.length4-+； 〃線性表長度加1returntrue;平均移動(dòng)n/2個(gè)元素,則時(shí)間復(fù)雜度為0(n)

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

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

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

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

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

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

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

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

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

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

(1)分為查找成功和查找失敗(2)靜態(tài)查找表:無需動(dòng)態(tài)修改查找表(順序查找、折半查找、散列查找)；動(dòng)態(tài)查找表:需要?jiǎng)討B(tài)修改和刪除的查找表(二叉排序樹查找、散列查找)(3)平均查找長度:一次查找長度是需要比較的關(guān)鍵字的次數(shù)6.2順序查找和折半查找6.2.1順序查找.概念:主要用于線性表中查找,分為無序線性表和有序線性表查找.一般線性表順序查找(1)從線性表一端開始逐個(gè)關(guān)鍵字是否滿足要求,若滿足則查找成功,若查找到末尾還未查找到則失敗,其中引入哨兵作用是不必判斷數(shù)組是否越界,因?yàn)楫?dāng)i==0時(shí),循環(huán)一定會(huì)跳出typedefstruct( 〃查找表的數(shù)據(jù)結(jié)構(gòu)ElemType*elem; 〃元素存儲(chǔ)空間基址，辱時(shí)按實(shí)際長度分聞，。節(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時(shí)退出for循環(huán))2)ZSL成功=(n+l)/2,ZSL不成功=n+l;當(dāng)n較大時(shí)，平均查找長度較大，效率低；優(yōu)點(diǎn)是對元素存儲(chǔ)無要求;對線性的鏈表只能順序查找.有序表的順序查找(D概念:查找失敗時(shí)可以不用再比較到表的另一端就能返回查找失敗的信息，可以用如下判定樹表示查投序列(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個(gè)元素有序表億10,13,16,19,29,32,33,37,41,43)，查找11和32,可以用如下二叉樹表示查找過程;樹最下面都是方形,表示查找不成功的情況;查找成功的查找長度為從根結(jié)點(diǎn)到目的結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)數(shù),而不成功的情況為從根結(jié)點(diǎn)到對應(yīng)失敗結(jié)點(diǎn)的父結(jié)點(diǎn)路徑上結(jié)點(diǎn)數(shù);若有序序列有n個(gè)結(jié)點(diǎn),判定樹有n個(gè)圓形非葉子結(jié)點(diǎn)和n+1個(gè)方形葉結(jié)點(diǎn),是為二叉排序樹查找成功:ASL=(lxl+2x2+3x4+4x4)/ll=3,查找不成功ASL=(3x4+4x8)/12=11/3.效率:查找成功平均長度為ASL=log2(M+l)-l,元素個(gè)數(shù)為n的樹高他即查找不成功的查找長度)為〃邛Og2(〃+1)1(往上進(jìn))，時(shí)間復(fù)雜度為O(log2〃)6.2.3分塊查找.概念:將查找表分為若干個(gè)子表,塊內(nèi)可以無序,塊間有序,即第一個(gè)塊關(guān)鍵字小于第二個(gè)塊中所有記錄的關(guān)鍵字,依次類推,再建立一個(gè)索引表,索引表中每個(gè)元素含有各塊最大關(guān)鍵字和各塊的第一個(gè)元素的地址,索引表按關(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.分為四個(gè)塊和索引表，如圖a3所示.1E找寰白|21|6|11|8|22|32|31|幺|72|61|78|88|83|圖6-3分塊有找示意圖.查找長度:長度為n表均勻分為b塊，每塊s個(gè)記錄,ASL=^+—=-+2s+〃，若§=0，則平均查找長度取最小心+1,若對索2 22s引表采用折半查找，則4SA=「log2（〃+l）］+等6.3B樹和B+樹6.3.1B樹及其基本操作概念:又稱多路平衡查找樹,B樹中所有結(jié)點(diǎn)孩子結(jié)點(diǎn)數(shù)的最大值稱為B樹的階,用m表示,一棵m階B樹或?yàn)榭諛?或有如下特征：（1）樹中每個(gè)結(jié)點(diǎn)至多m個(gè)子樹（至多mT個(gè)關(guān)鍵字）（2）若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則至少有兩棵子樹（3）除根結(jié)點(diǎn)外所有非葉子結(jié)點(diǎn)至少有「加/21棵子樹（至少有「m/21T個(gè)關(guān)鍵字）（4）所有葉結(jié)點(diǎn)都出現(xiàn)在同一層上，并且不帶任何信息圖&53階B樹木意圖B樹的高度（磁盤存取次數(shù),不包括最后一層不帶任何信息的葉結(jié)點(diǎn)所在層）（1）n個(gè)關(guān)鍵字,m階B樹,高度為logm（?+1）</?<logrm/2l（（/7+1）/2）+1（2）若讓每個(gè)結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)最少,第一層1個(gè),第二層2個(gè),除根結(jié)點(diǎn)外每個(gè)非終端結(jié)點(diǎn)至少「%/21棵子樹,依次排列,可讓容納同樣多的關(guān)鍵字的B樹達(dá)到最高B樹的查找B樹的插入（1）定位:找出插入該關(guān)鍵字最底層中某個(gè)非葉結(jié)點(diǎn)（B樹中插入的關(guān)鍵字一定是插入最底層非葉結(jié)點(diǎn)內(nèi)）（2）插入:插入后檢查被插入結(jié)點(diǎn)內(nèi)關(guān)鍵字個(gè)數(shù),若大于m-1個(gè),則必須進(jìn)行分裂（3）分裂的方法:取一個(gè)新結(jié)點(diǎn),將插入key后的原結(jié)點(diǎn)從中間位置將其中的關(guān)鍵字分為兩部分,左部分包含的關(guān)鍵字放在原結(jié)點(diǎn)中，右部分包含的關(guān)鍵字放到新的結(jié)點(diǎn)中，中間位置「加/2］的結(jié)點(diǎn)插入到原結(jié)點(diǎn)的父結(jié)點(diǎn)中.若此時(shí)導(dǎo)致其父結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過了上限,則繼續(xù)進(jìn)行這種分裂操作,直至這個(gè)過程傳到根結(jié)點(diǎn)為止,這樣導(dǎo)致B樹高度增1例:對于如下m=3的B樹,分裂操作如下（1）要使得刪除后的結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)涉及合并問題（2）當(dāng)所刪除的關(guān)鍵字k不在終端結(jié)點(diǎn)（最底層非葉結(jié)點(diǎn)）中時(shí),有下列幾種情況：1）如果小于k的子樹中關(guān)鍵字個(gè)數(shù)＞「加/21-1,則找出k的前驅(qū)值k',并且用k'來取代k,再遞歸地刪除k'即可2）如果大于k的子樹中關(guān)鍵字個(gè)數(shù)＞「〃7/2~|T,則找出k的后繼值k',并且用k，來取代k,再遞歸地刪除k'即可3）如果前后兩個(gè)子樹中關(guān)鍵字個(gè)數(shù)均為「而/21-1,則直接將兩個(gè)子結(jié)點(diǎn)合并,直接刪除k即可圖&7B樹中則除非終端結(jié)點(diǎn)關(guān)鍵字的合并（3）當(dāng)被刪除的關(guān)鍵字在終端結(jié)點(diǎn)（最底層非葉子結(jié)點(diǎn)），有以下幾種情況1）直接刪除關(guān)鍵字:若被刪除關(guān)鍵字所在結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)＞「加/21-12）兄弟夠借:若被刪除關(guān)鍵字所在結(jié)點(diǎn)刪除前關(guān)鍵字個(gè)數(shù)=「加/2]-1,且與此結(jié)點(diǎn)相連的左（右）兄弟結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)需要調(diào)整左右兄弟結(jié)點(diǎn)以及雙親結(jié)點(diǎn)，以達(dá)到平衡3）兄弟不夠借:若被刪除關(guān)鍵字所在結(jié)點(diǎn)刪除前關(guān)鍵字個(gè)數(shù)=,/21-1,且與此結(jié)點(diǎn)相連的左（右）兄弟結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)=「加/211,則將關(guān)鍵字刪除后與左（右）兄弟結(jié)點(diǎn)及雙親結(jié)點(diǎn)中關(guān)鍵字進(jìn)行合并注意:在合并的過程中，雙親結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)會(huì)減少.若其雙親結(jié)點(diǎn)是根結(jié)點(diǎn)并且關(guān)鍵字個(gè)數(shù)減少至0（根結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)為1時(shí)，有2棵子樹），則直接將根結(jié)點(diǎn)刪除,合并后的新結(jié)點(diǎn)成為根;若雙親結(jié)點(diǎn)不是根結(jié)點(diǎn),且關(guān)鍵字個(gè)數(shù)減少到又要與它自己的兄弟結(jié)點(diǎn)進(jìn)行調(diào)整或合并操作，并重復(fù)上述步驟，直至符合B樹的要求為止兄弟夠借 （b）兄弟不夠借3.2B+樹的基本概念（支持順序查找,B樹不支持）.一棵m階的B+樹需滿足下列條件：1）每個(gè)分支結(jié)點(diǎn)最多有m棵子樹（子結(jié)點(diǎn)）2）非葉根結(jié)點(diǎn)至少有兩棵子樹,其他每個(gè)分支結(jié)點(diǎn)至少有「m/21棵子樹3）結(jié)點(diǎn)的子樹個(gè)數(shù)與關(guān)鍵字個(gè)數(shù)相4）所有葉結(jié)點(diǎn)包含全部關(guān)鍵字及指向相應(yīng)記錄的指針,而且葉結(jié)點(diǎn)中將關(guān)鍵字按大小順序排列.并且相鄰葉結(jié)點(diǎn)按大小順序相互鏈接起來5）所有分支結(jié)點(diǎn)（可看成是索引的索引）中僅包含它的各個(gè)子結(jié)點(diǎn)（即下一級的索引塊）中關(guān)鍵字的最大值及指向其子結(jié)點(diǎn)的指針.m階的B+樹與m階的B樹的主要差異在于：1）在B+樹中，具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)只含有n棵子樹,即每個(gè)關(guān)鍵字對應(yīng)一棵子樹;而在B樹中，具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)含有（n+1）棵子樹2）在B+樹中，每個(gè)結(jié)點(diǎn)（非根內(nèi)部結(jié)點(diǎn)）關(guān)鍵字個(gè)數(shù)n的范圍是pn/2~|Wn/m（根結(jié)點(diǎn):lWnWm）,在B樹中，每個(gè)結(jié)點(diǎn)（非根內(nèi)部結(jié)點(diǎn)）關(guān)鍵字個(gè)數(shù)n的范圍是pn/2~|-lWnWmT（根結(jié)點(diǎn):1WnWmT）3）在B+樹中，葉結(jié)點(diǎn)包含信息,所有非葉結(jié)點(diǎn)僅起到索引作用，非葉結(jié)點(diǎn)中的每個(gè)索引項(xiàng)只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針,不含有該關(guān)鍵字對應(yīng)記錄的存儲(chǔ)地址4）在B+樹中，葉結(jié)點(diǎn)包含了全部關(guān)鍵字，即在非葉結(jié)點(diǎn)中出現(xiàn)的關(guān)鍵字也會(huì)出現(xiàn)在葉結(jié)點(diǎn)中；而在B樹中，葉結(jié)點(diǎn)包含的關(guān)鍵字和其他結(jié)點(diǎn)包含的關(guān)鍵字是不重復(fù)的如下圖所示為一棵4階B+樹的示例.從圖中可以看出，分支結(jié)點(diǎn)的某個(gè)關(guān)鍵字是其子樹中最大關(guān)鍵字的副本.通常在B+樹中有兩個(gè)頭指針:一個(gè)指向根結(jié)點(diǎn),另一個(gè)指向關(guān)鍵字最小的葉結(jié)點(diǎn).因此,可以對B+樹進(jìn)行兩種查找運(yùn)算:一種是從最小關(guān)鍵字開始的順序查找,另一種是從根結(jié)點(diǎn)開始,進(jìn)行多路查找.4散列表6.4.1散列表基本概念.概念:之前的算法建立在“比較”基礎(chǔ)上，效率取決于比較次數(shù)(1)散列函數(shù):將關(guān)鍵字映射成該關(guān)鍵字對應(yīng)地址的函數(shù)，記為Hash(key)=Addr,散列函數(shù)會(huì)把兩個(gè)不同的關(guān)鍵字映射到同一地址，稱為“沖突”，發(fā)生碰撞的不同關(guān)鍵字稱為同義詞;應(yīng)盡量減少?zèng)_突，設(shè)計(jì)好的處理沖突的方法(2)散列表:建立了關(guān)鍵字和存儲(chǔ)地址之間直接映射關(guān)系4.2散列函數(shù)的構(gòu)造方法1)函數(shù)定義域必須包括全部需要存儲(chǔ)的關(guān)鍵字2)散列函數(shù)計(jì)算出的地址能夠等概率、均勻分布在整個(gè)地址空間,減少?zèng)_突3)散列函數(shù)盡量簡單,較短時(shí)間內(nèi)能計(jì)算出任意關(guān)鍵字的地址.直接定址法:散列函數(shù)為//(%ey)=axhy+b；不會(huì)產(chǎn)生沖突,適合關(guān)鍵字分布基本連續(xù)的情況,若分布不連續(xù),則空位較多,造成空間浪費(fèi).除留余數(shù)法:假定表長為m,取一個(gè)不大于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)鍵字尋找下一個(gè)“空”的Hash地址,用Hi表示沖突后第i次探索的散列地址.開放定址法：Hi=("(左")+4)%m,m表示表長,di表示增量(1)線性探索法:di=l開始,每次遞增1,向后查找空位,直到找到一個(gè)空位或查遍全表;缺點(diǎn):可能使第i個(gè)散列地址同義詞存在第i+1個(gè)，造成大量相鄰的散列地址聚集,大大降低了查找效率(2)平方探測法：4=12,t2,22,_22..,%4m/2,m=4k+3,又稱二次探測法;可以避免堆積問題,缺點(diǎn)是不能探測到表的全部單元，但至少可以探測到一半(3)再散列法:使用兩個(gè)散列函數(shù)進(jìn)行散列注意:不能隨便刪除表中元素，因?yàn)槿魟h除元素將會(huì)截?cái)嗥渌哂邢嗤⒘械刂返脑氐牟檎业刂?所以要想刪除一個(gè)元素,給它做一個(gè)標(biāo)記,進(jìn)行邏輯刪除，但副作用是表面上看起來散列表很滿，實(shí)際上有許多位置沒有利用.拉鏈法(1)為避免非同義詞發(fā)生沖突,可以把所有同義詞存儲(chǔ)在一個(gè)線性鏈表中，這個(gè)線性鏈表由散列地址唯一標(biāo)識(shí),拉鏈法適用于經(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ù)計(jì)算出散列地址,addr=Hash(key)(2)檢測表中addr位置上是否有記錄,沒有記錄則失敗;若有記錄比較它與key值,若相等返回成功標(biāo)志,不然執(zhí)行下面(3)(3)用給定的處理沖突的方法計(jì)算“下一散列地址”，并把a(bǔ)ddr置為此地此轉(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,查找成功，返回記錄在表中的序號(hào)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)定性:排序中兩個(gè)元素相等,排序后位置不發(fā)生變化說明算法穩(wěn)定,主要是對算法性質(zhì)的描述,不能衡量算法優(yōu)劣.內(nèi)部算法通常進(jìn)行：比較+移動(dòng),基數(shù)排序不是基于比較的7.2插入排序基本思想是每次將一個(gè)待排序的記錄,按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中，直到全部記錄插入完成,每次插入便又多一個(gè)元素排好相對順序7.2.1直接插入排序.將第i個(gè)元素插入到前面已經(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]?插入到前面己排序序列