數(shù)據(jù)結(jié)構(gòu)對象的基本概念

PAGEPAGE73目錄TOC\o"1-3"\u目錄 1第一章緒論 3一、內(nèi)容提要 3二、學(xué)習(xí)重點 3三、例題解析 3第二章

線性性表 5一、內(nèi)容提要要 5二、學(xué)習(xí)重點點 5三、例題解析 5第三章棧和隊隊列 8一、內(nèi)容提要 8二、學(xué)習(xí)重點 8三、例題解析 8第四章

串 12一、內(nèi)容提要 12二、學(xué)習(xí)重點 12三、例題解析 12第五章數(shù)組和和廣義表 14一、內(nèi)容提要要 14二、學(xué)習(xí)重點 14三、例題解析 14第六章樹和和二叉樹 16一、內(nèi)容提要要 16二、學(xué)習(xí)重點 16三、例題及分析析 16第七章圖 19一、內(nèi)容提要 19二、學(xué)習(xí)重點 19三、例題解析 20第八章動態(tài)態(tài)存儲管理 22一、內(nèi)容提要 22二、學(xué)習(xí)重點 22三、例題解析 22第九章查找找 24一、

內(nèi)容提要要 24二、學(xué)習(xí)重點 24三、例題解析 25第十章

內(nèi)內(nèi)部排序 27一、內(nèi)容提要 27二、學(xué)習(xí)要點 27二、例題解析 27第十一章外外部排序 30一、內(nèi)容提要 30二、學(xué)習(xí)要點 30三、習(xí)題解析 30第十二章文件件 32一、內(nèi)容提要 32二、學(xué)習(xí)重點 32第一章緒緒論一、內(nèi)容提要1數(shù)據(jù)結(jié)構(gòu)研研究的內(nèi)容。2基本概念：：數(shù)據(jù)、數(shù)據(jù)據(jù)元素、數(shù)據(jù)據(jù)對象、數(shù)據(jù)據(jù)結(jié)構(gòu)、數(shù)據(jù)據(jù)類型、抽象象數(shù)據(jù)類型、多多形數(shù)據(jù)類型型。3算法的定義義及五個特征征。4算法描述：：類PASCCAL語言。5算法設(shè)計要要求。6算法分析。

二、學(xué)習(xí)重點1數(shù)據(jù)結(jié)構(gòu)的的“三要素”：邏輯結(jié)構(gòu)構(gòu)、物理（存存儲）結(jié)構(gòu)及及在這種結(jié)構(gòu)構(gòu)上所定義的的操作（運(yùn)算算）。2抽象數(shù)據(jù)類類型的定義、表表示和實現(xiàn)方方法。3類PASCCAL書寫規(guī)規(guī)范，過程（函函數(shù)）中值參參和變參的差差別，過程調(diào)調(diào)用規(guī)則。4用計算語句句頻度來估算算算法的時間間復(fù)雜度。

三、例題解析1寫出以下各各語句執(zhí)行次次數(shù)（左邊括括號內(nèi)數(shù)字為為語句序號）(1)FOORi::=1TOOnDO(2)FORRj::=1toonDO(3)[c[[I,j]:=0;;(4)FORRk::=1TOnnDOO(5)

c[I,jj]:=c[[I,j]++a[I,kk]*b[kk,j]][答案]：各語語句執(zhí)行次數(shù)數(shù)（頻度）分分別為n+11，n(n+11),n22,n22(n+1)),n3[分析]：最容容易發(fā)生的錯錯誤，是將第第一個語句的的執(zhí)行次數(shù)答答成n。

2編寫最優(yōu)算算法，從小到到大依次輸出出順序讀入的的三個整數(shù)PROCaasscennding;;{本算法對讀入入的三個整數(shù)數(shù)進(jìn)行排序，然然后按從小到到大輸出}{算法中核心語語句如下}rread(aa,b,c));IIFa>bbTHHEN[[t:=a;;a:=bb;b:==t];{{a,b按正正序排序}IIFb>ccTHHEN[[t:=c;;c:=bb;{c為為最大}IFaa<tTTHENb:=t{{b為中間值值}ELLSE[[b:=a;;a:=tt]{a,,b正序}WRITEELN(a::4,b:44,c:4));ENDP;{asseendingg}

[分析]：本題題正確算法有有多種，但上上面是最優(yōu)算算法：最好情情況下只經(jīng)過過兩次比較且且無數(shù)據(jù)移動動，而在最壞情況下，也只只是經(jīng)過三次次比較，七個個賦值語句就就完成了排序序。在本課程教學(xué)中中，強(qiáng)調(diào)“好”的算法,不僅僅是是結(jié)果正確,,而且是是最優(yōu)的算法法。這與PAASCAL語語言教學(xué)中的的要求有很大大不同。算法是供供人來閱讀的的，必須牢記記這一點。算算法中語句的的書寫格式采采用縮進(jìn)規(guī)則則，保留字用用大寫，其余標(biāo)識符小小寫，提高了了算法的易讀讀性。

第二章

線性性表

一、內(nèi)容提要要1．線性表是元元素間約束力力最強(qiáng)的一類類數(shù)據(jù)結(jié)構(gòu)。2．線性表的的邏輯結(jié)構(gòu)定定義，對線性性表定義的操操作。3．線性表的存存儲結(jié)構(gòu)：順順序存儲結(jié)構(gòu)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。4．線性表的操操作在兩種存存儲結(jié)構(gòu)中的的實現(xiàn)。5．一元多項式式的線性表表表示方法，及及高次（稀疏疏）多項式的的抽象數(shù)據(jù)類類型定義、表表示和加法的的實現(xiàn)。

二、學(xué)習(xí)重點點1．

線性表表的邏輯結(jié)構(gòu)構(gòu)，指線性表表的數(shù)據(jù)元素素間存在著線線性關(guān)系。在在順序存儲結(jié)結(jié)構(gòu)中，元素素存儲的先后后位置反映出出這種線性關(guān)關(guān)系，而在鏈鏈?zhǔn)酱鎯Y(jié)構(gòu)構(gòu)中，是靠指指針來反映這這種關(guān)系的。2．

順序存存儲結(jié)構(gòu)用向向量（一維數(shù)數(shù)組）表示，給給定下標(biāo)，可可以存取相應(yīng)應(yīng)元素，屬于于隨機(jī)存取的的存儲結(jié)構(gòu)。3．

盡管“只要知道某某結(jié)點的指針針就可以存取取該元素”，但因鏈表表的存取都需需要從頭指針針開始，順鏈鏈而行，故鏈鏈表不屬于隨隨機(jī)存取結(jié)構(gòu)構(gòu)。4．

鏈表是是本章學(xué)習(xí)的的重點和難點點。要理解頭頭結(jié)點，首元元結(jié)點和元素素結(jié)點的差別別。理解頭結(jié)結(jié)點是為了在在插入、刪除除等操作時，為為了算法的統(tǒng)統(tǒng)一而設(shè)立的的（若無頭結(jié)結(jié)點，則在第第一元素前插插入元素或刪刪除第一元素素時，鏈表的的頭指針總在在變化）。掌掌握通過畫出出結(jié)點圖來進(jìn)進(jìn)行鏈表的生生成、插入、刪刪除、遍歷等等操作。5．

鏈表操操作中應(yīng)注意意不要使鏈意意外“斷開”。因此，若若在某結(jié)點前前插入一個元元素，或刪除除某元素，必必須知道該元元素的前驅(qū)結(jié)結(jié)點的指針。6．

從時間間和空間復(fù)雜雜度的角度綜綜合比較線性性表在順序和和鏈?zhǔn)絻煞N存存儲結(jié)構(gòu)下的的特點。7．

靜態(tài)鏈鏈表是又一重重點和難點。應(yīng)應(yīng)和鏈表進(jìn)行行比較、理解解。例如，在在有頭結(jié)點的的鏈表情況下下，第一元素素是p:=lla^.neext，而在在靜態(tài)鏈表中中則i:=ssa[0]..next；；相對p:==p^.neext,有i:=saa[i].nnext來找找到第i個元素的后后繼。

三、例題解析

１．設(shè)線性表以以順序存儲結(jié)結(jié)構(gòu)存于a((1..n))中，試編寫寫算法將該線線性表就地逆逆置?！痉治觥肯蛄磕嬷糜杏袔追N方法，如如逆向讀入到到另一數(shù)組中中，在正向?qū)?yīng)賦值，即即：FORi:==nDOWWNTO11DOb[n-ii+1]:==a[i];;FORRi:=11TOnDOa[[i]:=bb[i];這里要求“就地地逆置”，即不能另另用一數(shù)組空空間?！舅惴ā縋RROCiinvertt(VARa:arrr;n:iintegeer);{a是存儲線線性表的一維維數(shù)組，有nn個元素，本本算法將a逆置。}FORi:==1TO((nDIIV2))DOaa[i]?aa[n-i++1];endp;【討論】將nn個元素的一一維數(shù)組逆置置，為什么循循環(huán)控制變量量用ndiiv2，而而不用n？

２．編編寫在單鏈表表上進(jìn)行排序序的算法【分分析】這里里使用插入排排序。鏈表中中插入元素要要知道待插入入元素位置的的前驅(qū)，以pre表示之之。結(jié)束的條條件是鏈表為為空?！舅闼惴ā縋ROCinserrtsortt(VARla:liinklisst);{la是是帶頭結(jié)點的的單鏈表的指指針，本算法法將鏈表中元元素正序排序序。算法的基基本思想是先先假定第一個個元素有序，然然后從第二個個元素開始，依依次插入到有有序的表中，直直到全部元素素插入完為止止}p:=lla^.neext^.nnext;{{假定鏈表非非空，即至少少有一個結(jié)點點}la^.nnext^..next::=nil;;{設(shè)有序鏈鏈表中當(dāng)前只只有一個結(jié)點點}fouund:=ffalse;;WHILEE(p<>>nil)AANDNOOTfouundDOO[s:=pp^.nexxt;{記住住下一個結(jié)點點}pree:=la;;q:=lla^.neext;ffound::=falsse;WWHILE((q<>niil)ANDDNOTfounddDOIFq^^.dataa<p^.ddataTTHEN[[pre:==q;q::=q^.nnext]ELSEEfounnd:=trrue;p^.nextt:=q;pre^.neext:=pp;{p結(jié)點點插入}p:=s;{取取下一個結(jié)點點}]ENDP;{inseertsorrt}【討論】算法中中foundd為一布爾變變量，為的是是在鏈表到尾尾前，如找到到p的插入位置，即可退退出WHILLE循環(huán)。這這里循環(huán)條件件未寫成：（p<>niil）AND((q^.daata<p^^.dataa)因為若q=niil，則再再引用q^..data是是無意義的。請請記住這種退退出循環(huán)，引引入布爾變量量的作法。3．設(shè)設(shè)兩個非遞減減有序的線性性表各有m和n個元素（m>>0,n>00）,分別存于一一維數(shù)組a和b中，且a的存儲空空間足夠大。試試編寫算法將將兩線性表合合并成一線性性表，結(jié)果仍仍是非遞減有有序，要求算算法的時間復(fù)復(fù)雜度是o((m+n)。【分析】兩個有序線線性表合并成成一個有序表表，教材中已已有討論，算算法非常簡單單。本算法要要求復(fù)雜度為為O(m+nn)，這是著著重點。題目目敘述中有“a的空間足夠夠大”，暗示出若若將m+n個元素素合并到a中，不會溢溢出。為使數(shù)數(shù)據(jù)移動次數(shù)數(shù)最少，應(yīng)先先將兩表中最最大元素置于于m+n的位置置上，然后相相應(yīng)指針減11，再比較之之，直到兩表表中有一個指指針減到0，則結(jié)束，否否則，將b中剩余元素素傳到a中相應(yīng)位置置即可?！舅惴ā縋RROCuunion((VARaa:seqllisttpp;b:seeqlistttp);{a,bb是兩個非遞遞減有序表，順順序存儲結(jié)構(gòu)構(gòu)存儲，各有有m和n個元素，本本算法將兩表表合并到a中，仍為有有序表，算法法時間復(fù)雜度度為O(m++n)}i:==m;j::=n;kk:=m+nn;{i,,j,k分別別為表a,bb和結(jié)果表的的指針}WHHILE((i>0)AND((j>0)DOIFa[i]>>b[j]THEN[a[k]]:=a[ii];i::=i-1;;k:=kk-1]ELSEE[a[kk]:=b[[j];jj:=j-11;k:==k-1];;WHIILE(jj>0)DDO[a[[k]:=bb[j];j:=j--1;k::=k-1]];{若b表中尚有元元素，則傳至至a中相應(yīng)位置置}【討論】本算法至多比較m+n次，往a中賦值m+n次。最好情況是比較n次，往a中賦值n次，該種情況是b中最小元素不小于a中最大元素。問問題：為什么么在退出第一一個WHILLE循環(huán)后，不不討論（即沒沒有）WHIILEi>>0的情況？？

第三章棧和和隊列

一、內(nèi)容提提要

1．從數(shù)據(jù)結(jié)構(gòu)構(gòu)角度講，棧棧和隊列也是是線性表，其其操作是線性性表操作的子子集，屬操作作受限的線性性表。但從數(shù)數(shù)據(jù)類型的角角度看，它們們是和線性表表大不相同的的重要抽象數(shù)數(shù)據(jù)類型。2．棧的定義及及操作。棧是是只準(zhǔn)在一端端進(jìn)行插入和和刪除操作的的線性表，該該端稱為棧的的頂端。3．棧的順序和和鏈?zhǔn)酱鎯Y(jié)結(jié)構(gòu)，及在這這兩種結(jié)構(gòu)下下實現(xiàn)棧的操操作。4．棧的應(yīng)用：：表達(dá)式求值值，遞歸過程程及消除遞歸歸。5．隊列的定義義及操作，隊隊列的刪除在在一端（尾），而而插入則在隊隊列的另一端端（頭）。因因此在兩種存存儲結(jié)構(gòu)中，都都需要隊頭和和隊尾兩個指指針。6．鏈隊列空的的條件是首尾尾指針相等，而而循環(huán)隊列滿滿的條件的判判定，則有隊隊尾加1等于隊頭和設(shè)標(biāo)記兩兩種方法。

二、學(xué)習(xí)重重點

1．棧棧和隊列操作作在兩種存儲儲結(jié)構(gòu)下的實實現(xiàn)。2．中中綴表達(dá)式轉(zhuǎn)轉(zhuǎn)成前綴、后綴表達(dá)式式并求值。3．用遞歸解決決的問題：定定義是遞歸的的，數(shù)據(jù)結(jié)構(gòu)構(gòu)是遞歸的，及及問題的解法法是遞歸的，掌握典型型問題的算法法。4．

鏈隊列列刪除時為空空的處理（令令隊尾指針指指向隊頭）。特特別是僅設(shè)尾尾指針的循環(huán)環(huán)鏈隊列的各種種操作的實現(xiàn)現(xiàn)。5．

循環(huán)隊隊列隊空定義義為隊頭指針針等于隊尾指指針，隊滿則則可用一個單單元（教材中中所示）及設(shè)標(biāo)記辦辦法（下面例例題）。這里里特別注意取取模運(yùn)算。6．

在后續(xù)續(xù)章節(jié)中要注注意棧和隊列列的應(yīng)用，如如串中心對稱稱的判定，二二叉樹遍歷的的遞歸和非遞歸歸算法，圖的的深度優(yōu)先遍遍歷等都用到到棧，而樹的的層次遍歷、圖的寬度優(yōu)優(yōu)先遍歷等則用用到隊列。

三、例題解析

1．兩棧共享一一向量空間，編編寫入棧和出出棧算法。TYYPETwoWaayStacck=RECCORD{雙棧棧共享一向量量空間}elem::ARRAYY[1..mm]OFelemttype;top:AARRAY[[0..1]]OF00..m+11;{兩兩個棧頂指針針}ENND;PRROCinisttack(VVARtwws:TwooWaySttack);;{初始始化}{初始化化雙向棧twws為空}twws.topp[0]:==0;{左端端棧指針}twws.topp[1]:==m+1;{右端端棧指針}ENDP;{inisstack}}

PROCPPUSH(VVARtwws:TwooWaySttack;ii:0..11;x:eelemtyype;VAARofww:boollean);;{若雙向向棧tws不不滿,則將xx插入到i端端,成功時oofw為trrue,失敗敗為falsse}IFF(tws..top[11]-twss.top[[0])<>>1THENN{棧棧未滿}CCASEiiOF0::tws.ttop[0]]:=twss.top[[0]+1;;tws.eelem[ttws.toop[0]]]:=x;oofw:=ttrue1::tws.ttop[1]]:=twss.top[[1]-1;;tws.eelem[ttws.toop[1]]]:=x;oofw:=ttrueEENDCELSSEofww:=fallse;(棧滿)ENDDP;{{push}}PROCPOOP(VARRtws::TwoWaayStacck;i:00..1;VVARx::elemttype;VVARunnderfllow:boooleann);{若雙向棧棧tws非空空,則將i端端退棧,?？湛諘rundeerfloww為truee}CAASEiOF0:IFtws.ttop[0]]=0{?？諁THENN[undeerfloww:=truue;retturn(uunderfflow)]]ELSEE[twss.top[[0]:=ttws.toop[0]--1;x:==tws.eelem[ttws.toop[0]++1];{彈出元素素}];1:IFtws.ttop[1]]=m+1{棧?？諁THENN[undeerfloww:=truue;retturn(uunderfflow)]]ELSEE[twss.top[[1]:=ttws.toop[1]++1;x:==tws.eelem[ttws.toop[1]--1];{彈出元素素}];ENDCENDP;{pop}【討論】上面面算法中用00和1代表兩兩端，且按操操作在哪端來來分兩種情況況進(jìn)行討論，邏邏輯清楚。也也可用一個公公式表示插入入（進(jìn)棧）和和刪除（退棧棧）指針位置置。例如，插插入時topp=top++1-2*ii,刪除時ttop=toop-1+22*i。表達(dá)達(dá)簡潔，但不不如上面清楚楚易讀。

2．將中綴表達(dá)達(dá)式轉(zhuǎn)換成后后綴表達(dá)式，并并進(jìn)行表達(dá)式式求值。PROCtrrnssuffix(VAARexpp2:strring;ss:stacck;exxp1:sttring));｛本算法將中綴綴表達(dá)式exxp1轉(zhuǎn)為后后綴表達(dá)式eexp2,使使用運(yùn)算符棧棧s｝｛算法基本思想想是依次從中中綴表達(dá)式讀讀入字符w：：若w是變變量，直接送送入結(jié)果表達(dá)達(dá)式，若w是是運(yùn)算符，則則與棧頂運(yùn)算算符比較，若若級別高，則則進(jìn)棧；若若低，則棧頂頂元素退棧，并并送入結(jié)果表表達(dá)式，再取取棧頂運(yùn)算符符比較，重復(fù)復(fù)以上步驟；；若w＝’)’,則棧元素素依次退棧，并并送入結(jié)果表表達(dá)式，直至至＇)＇退棧棧｝innitstrring(eexp2);;inittstackk(s);ppush(ss,’#’);opp:=['++','-'','*',,'/',''(','))','#''];{操操作符集合}}reead(w));WHIILENOOT((ww='#'))AND(GETTTOP(OPPTR)=''#'))DOIFFNOT(wINNop)THEN［inssert(eexp2,ww);reead(w))］;ELSEECASEEpreccede(GGETTOPP(s),ww)OF''<':[[PUSHH(S,w));reaad(w)];''=':IIFw=’’)’THENN{遇右括括號后，運(yùn)算算符退棧并送送結(jié)果表達(dá)式式，直至左括括號}[xx:=POPP(S);WWHILEx<>’(‘DO[[inserrt(expp2,x);;x:=POOP(S)]]rread(ww)];''>':[[b:=PPOP(S));inssert(eexp2,bb)];END;;ENDP;PROCsuufixevval(VAARexpp2:strring;ss:stacck;VAARsn::stackk);｛本算法對后綴綴表達(dá)式exxp2求值，使使用運(yùn)算符棧棧s和操作數(shù)數(shù)棧sn｝｛算法基本思想想是逐字符從從左到右順序序讀入后綴表表達(dá)式。若讀讀入的字符ww是數(shù)，則直直接壓入棧sn中；若若w是運(yùn)算符符，則與棧頂頂運(yùn)算符比較較，若級別高高，則進(jìn)棧；；否則，從運(yùn)運(yùn)算數(shù)棧彈出出兩個操作數(shù)數(shù)，和從運(yùn)算算符棧彈出的的一個運(yùn)算符符進(jìn)行相應(yīng)運(yùn)運(yùn)算，結(jié)果存存入操作數(shù)棧棧中。w運(yùn)算算符再與棧頂頂運(yùn)算符比較較優(yōu)先級。直直至后綴表達(dá)達(dá)式處理完畢畢。這時snn棧中只剩一一個數(shù)，即表表達(dá)式結(jié)果。｝｝innitstrring(ssn);iinitsttack(ss);opp:=['++','-'','*',,'/',''(','))','#''];{操操作符集合}}reead(w));{從左左到右順序讀讀入后綴表達(dá)達(dá)式}WHIILENOOTemppty(exxp2)DDOIFFNOT(wINNop)THEN［PUSSH(sn,,w);rread(ww)］;ELSEECASEEpreccede(GGETTOPP(s),ww)OF''<':[[PUSHH(s,w));reaad(w)];''>':[[a:=PPOP(snn);b:==POP(ssn);ttheta::=POP((s);PUSHH(sn,ooperatte(atthetab))]];END;;ENDP;{suffixevaal}3、用設(shè)標(biāo)記來來判定循環(huán)隊隊列滿，編寫寫入隊和出隊隊的算法。{本算法法用設(shè)標(biāo)記ttag的辦法法，解決循環(huán)環(huán)隊列隊滿和和隊列空的判判斷問題,ttag=0表表示隊列空，ttag=1表表示隊列不空空}TYPEEcycliicqueuue=RECCORD{設(shè)頭尾指針和標(biāo)標(biāo)志域的循環(huán)環(huán)隊列}eelem:==ARRAYY[0..mm-1]OOFeleemtypee;rrear,ffront::0..m--1ttag:0...1;｛０為空，１１為非空｝ENDD;PROCIINITQUUEDE(VVARcqq:cycllicqueeue);｛初始化化｝cq.taag:=0;;cq.teear:=ccq.froont:=00;ENDPP;PROCENNQUEUEE(VARcq:cyyclicqqueue;;x:eelemtyype);｛ccq是由頭尾尾指針和標(biāo)志志域的循環(huán)隊隊列，本算法法是入隊操作作，若隊列不不滿，｝｛則則將x插入到到隊尾｝IF(ccq.tagg=1)AAND(ccq.froont=cqq.rearr)TTHENrreturnn(falsse){隊隊滿}EELSE[ccq.reaar:=(ccq.reaar+1)MODmm;ccq.eleem(cq..rear)):=r;IIFcq..tag=00THENNcq.ttag:=11{由空空變不空標(biāo)記記}]ENNDP;PROCDEELQUEUUE(VARRcq:ccycliccqueuee);｛ccq是由頭尾尾指針和標(biāo)志志域的循環(huán)隊隊列，本算法法是出隊操作作，若隊列非非空｝｛則則將隊頭元素素出隊｝IFccq.tagg=0TTHENrreturnn(falsse){隊隊空}EELSE[ccq.froont:=((cq.frront+11)MODDm;IIFcq..frontt=cq.rrearTTHENccq.tagg:=0{隊空}}]ENNDP;CONSSTm=mmaxlenn;｛隊隊列長度｝TYPEEccycliccqueuee=RECOORD｛只設(shè)尾尾指針和隊列列長度的循環(huán)環(huán)隊列｝ellem:AARRAY[[0..m--1]OFFelemmtype;;reear:00..m-11;leength::0..mm;｛隊隊列長度｝END;;PROCIINIT_qqueue((VARqq:cycllicqueeue);｛初始化化｝q.rrear:==0;q..lengtth:=0;;ENDP;FUNCaddd_queeue(VAARq:ccycliccqueuee;x:ellemtyppe):boooleann;｛q是是由尾指針和和長度標(biāo)志的的循環(huán)隊列，本本算法是入隊隊操作，若隊隊列不滿，｝｝｛將xx插入到隊尾尾｝IFqq.lenggth=mTTHENadd_qqueue::=falsse{{隊列滿}EELSE[[q.reear:=((q.reaar+1)modmm;q.ellem[q..rear]]:=x;q.leength;;=q.leength++1;add__queuee:=truue{入隊成成功}]EENDF;FUNCddd_queeue(VAARq:ccycliccqueuee;x;eelemtyype):bbooleaan;｛qq是由尾指針針和長度標(biāo)志志的循環(huán)隊列列，本算法是是出隊操作，若若隊列不空，｝｝｛將將將隊頭元素素出列，并賦賦給x，隊長長度減１｝IFqq.lenggth=0TTHENddd_queeue:=ffalse{{隊空}EELSE[[frontt;=(q..rear--q.lenngth+11+m)mmodmx:=q..elem[[frontt]q.lenngth:==q.lenngth-11]]EENDF;

第四章

串一、內(nèi)容提要

1、

是數(shù)據(jù)據(jù)元素為字符符的線性表，串串的定義及操操作。2、

的基本本操作，編制制算法求串的的其它操作。3、

的存儲儲結(jié)構(gòu)，因串串是數(shù)據(jù)元素素為字符的線線性表，所以以存在“結(jié)點大小“的問題。靜靜態(tài)和動態(tài)（塊塊鏈結(jié)構(gòu)，堆堆結(jié)構(gòu)）存儲儲的優(yōu)缺點。4、

樸素模模式匹配算法法及改進(jìn)（KKMP）算法法。

二、學(xué)習(xí)重點

1、

串的基基本操作，編編寫串的其他他操作（如iindex,,replaace等）。2、在串的模式式匹配中，求求匹配串的nnextvaal函數(shù)值值。3、盡管樸素的的模式匹配的的時間復(fù)雜度度是O(m**n),KKMP算法是是O(m+nn),但在一一般情況下，前前者實際執(zhí)行行時間近似OO(m+n)),因此至今今仍被采用。KMP算法僅在主串與模式串存在許多“部分匹配”時才顯得比前者塊的多，其主要優(yōu)點是主串不回嗍。5、

串操作作在存儲結(jié)構(gòu)構(gòu)下的實現(xiàn)。

三、例題解析

1、利用串的如如下基本運(yùn)算算creatte(s),,assiggn(s,tt),lenngth(ss),subbstr(ss,starrt,lenn),conncat(ss1,s2)),編寫操作作replaace的算法法PROCrreplacce(VARRs:sttring;;t,v::strinng);{本本算法實現(xiàn)串串的置換操作作，用串v置換串s中所有非重重疊的t串。}i::=INDEEX(s,tt);{判判s中有無t}IFFi<>00THENN[CRREATE(tempp,‘’));{t為臨時時串變量，存存放部分結(jié)果果}m::=LENGGTH(t));n::=LENGGTH(s));WHHILEi<>0DO[ASSSIGN(tempp,CONCCAT(teemp,SUUBSTR((s,1,ii-1),vv));{用v替換t形成部分結(jié)結(jié)果}ASSSIGN(s,SUUBSTR((s,i++m,nn-i-m++1));{t串以后后形成新s串}n::=n-((i-1)--m;i::=INDEEX(s,tt);]ASSIIGN(ss,CONCCAT(teemp,s)));{將將剩余s連接臨時串串t再賦給s}]ENDP;;FUNCindexx(s1:sstringg;t:sstringg):intteger;;{本算法法求串t在串s中的第一次次出現(xiàn)。結(jié)果是：若若t在s中，則給出串串t的第一個字字符在串s中的位置，若若不存在，則則返回0}j:==1;m:==lengtth(s);;n:=llengthh(t);eq:=ttrue;WHIILE((j<=m--n+1)ANDeqDOIFeqqual(ssubstrr(s,j,,n),t))THEENeqq:=fallseELSEj:=j++1；IFj<=mm+n-1THENindeex:=jELSEindeex:=0ENDF；{iindex}}【討論】本題是用給給定的基本操操作，編寫其其它操作的算算法。這種類類型題較多，必必須嚴(yán)格按題題的要求來做做，不準(zhǔn)選擇擇具體存儲結(jié)結(jié)構(gòu)。否則，即即使全對，也也很難得分。2

設(shè)目目標(biāo)為t=’abbcaabbbabcabbaacbaacba’,,模式串p==’abcaabaa’;;(1)計算P的的NEXTVVAL函數(shù)值值；(2)不寫出算算法，只畫出出利用KMPP算法進(jìn)行模模式匹配時每每一趟的匹配配過程；【解答】（1）P的NNEXTVAAL函數(shù)值值如下；j12334567_____________________________________模式pabccabaanextvall(j)001101002(2)abccaabbabcaabaacbaacbaabccab第一趟趟匹配abcc第二趟匹配配a第第三趟匹配abccabaa第四趟匹匹配成功【討論】為寫寫NEXTVVAL方便，可可先寫出NEEXT函數(shù)值值，在由此求求NEXTVVAL.

3、字符串s滿足下式，其其中HEADD和TAILL的定義同廣廣義表類似，如如HEAD((‘XYZ’’)=’X’’,TAILL(‘XYZZ’)=’YYZ’,則S=concaat(heaad(taiil(s))),headd(taill(taill(s)))))=’dcc’求字符串s。

可供選擇的答案案是（A）abcdd(B))acbdd(C))acdbb(D))adcbb正確答案是（DD）。第五章數(shù)組和廣義義表

一、內(nèi)容提要要

1，

數(shù)組的的邏輯結(jié)構(gòu)定定義及存儲，2，

稀疏矩矩陣（含特殊殊矩陣）的存存儲及運(yùn)算。3，

廣義表表的定以及存存儲。4，

廣義表表運(yùn)算的遞歸歸算法。

二、學(xué)習(xí)重點

1，

數(shù)組（主主要是二維）在在以行序為主主的存儲中的的地址計算方方法。2，

特殊矩矩陣在壓縮存存儲時的下標(biāo)標(biāo)變換。3，

稀疏矩矩陣的三元組組表存儲結(jié)構(gòu)構(gòu)及矩陣移植植的算法。4，

稀疏矩矩陣的十字鏈鏈表存儲方法法及十字鏈表表生成算法。5，

廣義表表的HEADD和TAIL運(yùn)算。6，

給定廣廣義表畫出其其存儲結(jié)構(gòu)。7，

從廣義義表的遞歸算算法，掌握如如何編寫遞歸歸算法。

三、例題解析

1、字符串二維維數(shù)組A[00..8,11..10]]，每個元元素由6個字符組成成，每個字符符占一個存儲儲單元，則（1）存放A需要多少個字節(jié)？（2）A的第88列和第5行共占多少少字節(jié)？(3)按行序序存儲時，AA[8,5]]和按列存儲儲時哪個元素素時的地址相相同？【解答】（11）540（2）108（3）A[3,,10]

2、編寫算法，將將自然數(shù)1n2按蛇形填入入nxnn矩陣中。例如，（11—42）如右圖所所示?！痉治觥勘颈绢}要求在NN的方陣中填填人N2個數(shù)，關(guān)鍵鍵是控制下標(biāo)。設(shè)坐標(biāo)原原點在矩陣的的左上角，且且i是向下增長長，j向右增長。原點點的坐標(biāo)為（1，1）。【算法】PROCsqrmggc(VARRa:arrr;n:iintegeer);{本算法將自自然數(shù)1n2按蛇形填填入NXN矩陣中中,a是二維維數(shù)組}i:=1;jj:=1;k:=1;;WHILEE(i<==n)ANND(j<<=n)DDO[WHILEE(i<==n)ANND(j>>0)DOO[aa[i,j]]:=k;i:=i++1;j::=j-1;;k:=kk+1]IFj<<1THEENIFi<=nTHENj:=1ELSE[j:=jj+2;i::=n]ELLSE[ii:=n;j:=j++2]WHILEE(i>00)ANDD(j<==N)DOO[a[i,jj]:=k;;i:=ii-1;jj:=j+11;k:==k+1]]IFi<<1THEENIFj<=nTHENi:=1ELSE[i:=ii+2;j::=n]EELSE[[j:=n;;i:=ii+2]]ENDP;{{sqrmggc}

3、求下列廣義義表操作結(jié)果果：(1)

HEEAD(TAAIL(HEEAD((((a,b),,(c,d)))))(2)

TAAIL(HEEAD(TAAIL((((a,b),,(c,d)))))【解答】（11）b((2)((d)

4、利用廣義義表的HEAAD和TAIL操作作，寫出如上上題的表達(dá)式式，把原子bbananaa從下列廣義義表中分離出出來。（1）

L11=（applee,(peaar),(((bananna)),((((oraange))))）;（2）

L22=(appple,(ppear,((bananna),orrange)));【解答】(1))HEADD(HEADD(HEADD(TAILL(TAILL(L1))))))(2)HHEAD(HHEAD(TTAIL(HHEAD(TTAIL(LL1))))))

第六章樹和二叉樹樹

一、內(nèi)容提要要

1、樹是復(fù)雜的的非線性數(shù)據(jù)據(jù)結(jié)構(gòu)，樹，二二叉樹的遞歸歸定義，基本本概念，術(shù)語語。2、二叉樹的性性質(zhì)，存儲結(jié)結(jié)構(gòu)。3、二叉樹的遍遍歷算法（遞遞歸，非遞歸歸）。4、線索二叉樹樹5、樹的存儲結(jié)結(jié)構(gòu)，樹、森森林的遍歷及及和二叉樹的的相互轉(zhuǎn)換。6、二叉樹的應(yīng)應(yīng)用：表達(dá)式式求值、判定定問題及哈夫夫曼樹和哈夫夫曼編碼。

二、學(xué)習(xí)重點

（本章內(nèi)容是本本課程的重點點）1、二叉樹性質(zhì)質(zhì)及證明方法法，并能把這這種方法推廣廣到K叉樹。2、二叉樹遍歷歷的遞歸算法法，本書中介介紹了三種（先先、中、后序序）方法，另另三種也應(yīng)會會用。前序和和中序的非遞遞歸遍歷。遍遍歷是基礎(chǔ)，由由此導(dǎo)出許多多實用的算法法，如求二叉叉樹的高度、各各結(jié)點的層次次數(shù)、度為00、1、2的結(jié)點數(shù)，二二叉樹的相似似、全等、復(fù)復(fù)制等等的算算法。3、由二叉樹的的遍歷的前序序和中序序列列或后序和中中序序列可以以唯一構(gòu)造一一棵二叉樹，手手工模擬及編編寫算法。由由前序和后序序序列不能唯唯一確定一棵棵二叉樹。4、二叉樹線索索化的實質(zhì)是是建立結(jié)點在在相應(yīng)序列中中的前驅(qū)和后后繼之間的直直接聯(lián)系。在在何序（前、中中、后）下進(jìn)進(jìn)行何種（全全、前驅(qū)、后后繼）線索化化，并求某結(jié)結(jié)點相應(yīng)的前前驅(qū)和后繼。5、完全二叉樹樹的性質(zhì)，順順序存儲結(jié)構(gòu)構(gòu)和二叉樹鏈鏈表存儲結(jié)構(gòu)構(gòu)的相互轉(zhuǎn)換換。6、樹的雙親表表示法和孩子子兄弟表示法法間的相互轉(zhuǎn)轉(zhuǎn)換。7、樹、森林和和二叉樹間的的相互轉(zhuǎn)換（“連線”、“切線”和“旋轉(zhuǎn)”）。8、哈夫曼樹的的定義、構(gòu)造造及求哈夫曼曼編碼。

三、例題及分析析

在二叉樹中查找找其數(shù)據(jù)域為為x的結(jié)點。如如存在，返回回該結(jié)點指針針，否則返回回空指針。【分析】可采采用遞歸遍歷歷算法。【算法】PROCssearchh(bt:bbitrepptr;x:dattatypee);{bt是是bitreeptr型的的二叉樹，xx是待查找數(shù)數(shù)據(jù)值,本算法遞歸歸遍歷二叉樹樹，在遍歷中中進(jìn)行查找。算算法中p是調(diào)用本過過程的過程中中定義的變量量，初值為NNIL，查找找成功后，pp指向數(shù)據(jù)域域為x的結(jié)點。foound是初初值為fallse的變量量。從本過程程返回后，測測試founnd以確定是是否查找成功功。}IF(bbt<>NIIL)ANDNOTfounddTHHEN[IIFbt^^.dataa=xTHEEN[pp:=bt;;founnd:=trrue]]ssearchh(bt^^.lchiild,xx);ssearchh(bt^^.rchiild,xx);]]EENDP;{seerch}【討論】本算法核心語句句有三個（即即第一個THHEN后的語語句：第一個個語句是“訪問”根結(jié)點.后兩個語語句是遞歸遍遍歷（相對位位置不變）。在在這三個語句句中，由“訪問”語句所處位位置不同（前前、中、后），形形成三種遞歸歸遍歷方法：：前序、中序序和后序。Found是為為查到x就立即（不不再遍歷未遍遍歷結(jié)點）而而設(shè)立的。若若要再考慮本本算法的優(yōu)化化，則在兩個個調(diào)用語句中中可加上IIf(btt^.lchhild<>>NIL)ANDNOTfoundd和IIf(btt^.rchhild<>>NIL)ANDNOTfoundd其優(yōu)點是在左（右右）為空時不不必再調(diào)用，且且一旦找到xx就立即退出出。

２．設(shè)二叉樹采采用二叉鏈表表作為存儲結(jié)結(jié)構(gòu)，試編寫寫算法求二叉叉樹的結(jié)點數(shù)數(shù)?！痉治觥坑嬎愣鏄浣Y(jié)點數(shù)數(shù)的數(shù)學(xué)模型型如下：f(bt)=00若bt=niilf(bt)=ff(bt^..lchilld)+ff(bt^..rchilld)+11否否則【算法】FUNNCnoddes(btt:bitrreptr)):inteeger;IFbtt=nilTHEENnoddes:=00ELLSE[n1:=nnodes((bt^.llchildd)nn2:=noodes(bbt^.rcchild))nodess:=ni++n2+1]ENDFF{noddes}【討論】二叉叉樹由根、左左子樹、右子子樹三部分組組成，很多問問題（如求葉葉子、度１、度度２結(jié)點數(shù)），可可分解到三部部分求解，上上面寫出數(shù)學(xué)學(xué)遞歸模型是是有普遍意義義的。例如：：（１）.二叉叉樹相似：f(tt1,t2))=truee若t1=t22=NILf(t11,t2)==falsee若t11,t2中只只有一個為NNILf(t11,t2)==f(t1^^.lchiild,tt2^.lcchild))ANDf(t1^^.rchiild,t22^.rchhild)若t1,tt2均不為NILL(2)求二二叉樹的葉子子結(jié)點數(shù)f(bt)=00當(dāng)bt=niilf(bt)=11當(dāng)bt左右子樹樹均為空f(bt)=ff(bt^..lchilld)+f((bt^.rrchildd)否則（３）求二叉樹樹所有葉子結(jié)結(jié)點的最大枝枝長：00若bt^.llchildd=nil且bt^.rrchildd=nilmmaxl(bbt^.lcchild))+1若若bt^.rrchildd=nilmax=maxl((bt^.rrchildd+1)若bt^.llchildd=nilmmax(maaxl(btt^.rchhild+11),maaxl(btt^.rchhild)))+1否則則３．打印二叉樹樹中結(jié)點x（假定存在在）的所有祖祖先結(jié)點?！痉治觥吭谠诙鏄涞倪f遞歸遍歷等算算法中，只有有后序遍歷才才是最后訪問問根結(jié)點，因因此有可能保保留從根結(jié)點點到待查結(jié)點點的蹤跡，這這時可用棧，存存放從根結(jié)點點到x結(jié)點路徑中中的各祖先結(jié)結(jié)點?！舅惴ā縋ROCpprintaansctrr(bt:bbitrepptr;x:dattatypee);{bt是是bitreeptr型的的二叉樹，xx是待查找數(shù)數(shù)據(jù)值,本算法輸出出X結(jié)點的各祖祖先結(jié)點。SS是工作棧，存存放X的祖先結(jié)點點。查到X后，依次輸輸出S中數(shù)據(jù)即可可。}initsstack((s);pp:=bt;;pushh(s,p));WHILEENOTTemppty(s))DO[WHILEENOTemptyy(s)AAND(pp^.datta<>x))DO[ppush(ss,p);p:=p^^.lchiild]IFFp^.ddata=xxTHENNWHILLENOTT(emppty(s)))DO[p:=ppop(s));wriite(p^^.dataa)]ELSEE{需要到到右分枝去查查x結(jié)點}[q:=nnil;rrend:==true;;{rennd是為了在在右分枝不空空時就退出循循環(huán)}WHILLENOTTemptty(s)ANDrrendDDO[[p:=poop(s);;IFp^^.r=qTHENq:=p{右分枝為為空時退棧}}ELLSE[push((s,p);;p:=p^^.rchiild;rrend:==falsee]]ENDP；{priintanssctr}

第七章圖圖

一、內(nèi)容提要

1．圖的定定義，概念、術(shù)術(shù)語及基本操操作。2．

圖的存存儲結(jié)構(gòu)。3．

圖的遍遍歷。4．

圖的應(yīng)應(yīng)用（連通分分量，最小生生成樹，拓?fù)鋼渑判?，關(guān)鍵鍵路經(jīng)，最短短路經(jīng)）。

二、學(xué)習(xí)重點圖是應(yīng)用最廣廣泛的一種數(shù)數(shù)據(jù)結(jié)構(gòu)，本本章是這門課課程的重點。1

基本本概念中，連連通分量，生生成樹，鄰接接點是重點。2

圖是是復(fù)雜的數(shù)據(jù)據(jù)結(jié)構(gòu)，也有有順序和鏈?zhǔn)绞絻煞N存儲結(jié)結(jié)構(gòu)：數(shù)組表表示法（重點點是鄰接距陣陣）和鄰接表。這兩種存存儲結(jié)構(gòu)對有有向圖和無向向圖均適用。十十字鏈表是有有向圖的另一一種表示，將將有向圖的鄰鄰接表和逆鄰鄰接表合一。鄰鄰接多重表是是無向圖鄰接接表的改進(jìn)，將將邊結(jié)點的數(shù)數(shù)量減少一半半（正好等于于邊的數(shù)量）。3

圖的的遍歷是圖的的各種算法的的基礎(chǔ)，應(yīng)熟熟練掌握圖的的深度、廣度度優(yōu)先遍歷，手手工模擬圖的的遍歷中棧和和隊列指針狀狀態(tài)的變化。4

在（強(qiáng)強(qiáng)）連通圖中中，主過程一一次調(diào)用深（寬寬）度優(yōu)先遍遍歷過程（ddfs/bffs），即可可遍歷完全部部頂點，故可可以用此方法法求出連通分分量的個數(shù)，并并能畫出遍歷歷中形成的深深（寬）度優(yōu)優(yōu)先生成樹。5

連通通圖的最小生生成樹不是唯唯一的，但最最小生成樹邊邊上的權(quán)值之之和是唯一的的。應(yīng)熟練掌握握prim和krusccal算法，特特別是手工分分步模擬生成成樹的生成過過程。6

拓?fù)鋼渑判蚴窃谟杏邢驁D上對入入度（先后）為為零的頂點的的一種排序，結(jié)結(jié)果不唯一。關(guān)關(guān)鍵路經(jīng)是在在拓?fù)溆行虻牡那疤嵯虑蟪龀鰜淼?，從源源點到匯點的的最長路徑。應(yīng)應(yīng)能掌握這兩兩種算法，并并熟練手工模模擬。理解“減少關(guān)鍵活活動時間能縮縮短工期”，是指該活活動為所有關(guān)關(guān)鍵路徑所共共有，且減少少到尚未改變變關(guān)鍵路經(jīng)的的前提下才有有效。7

從單單源點到其他他頂點，以及及各個頂點間間的最短路經(jīng)經(jīng)問題，掌握握算法，并熟熟練手工模擬擬。

三、例題解析

1、用鄰接多重重表實現(xiàn)圖的的各種運(yùn)算?！痉治觥吭卩徑咏佣嘀乇碇校棵織l邊用一個個結(jié)點表示，不不象在鄰接表表中那樣用兩兩條邊來表示示。這在圖的的操作中，要要比其他的存存儲結(jié)構(gòu)要復(fù)復(fù)雜的多。PROCcrrt_graaph(vargg:adjmmulistt);｛g為教材中中已定義的aadjmullist類型型變量，本算算法建立有nn個結(jié)點e條邊的圖圖的存儲結(jié)構(gòu)構(gòu)｝FORI::=1TOnnDO【reead(gg[i].ddata;g[i]..firsttedge::=nil))】｛建立頂點向量量，各頂點所所指向的第一一條邊指針為為nil｝FORr::=1TOeeDO【read((vi,vjj);｛讀讀兩結(jié)點｝i:=loc__verteex(g,vvi);j:=lloc_veertex((g,vj))new(p);;p^..ivex::=i;p^.jvvex:=jj;p^.ilinnk:=g[[i].fiirsteddge;g[i]].firsstedegg:=p｛將邊（vi，vj）分別插插入頂點vii，vj的邊結(jié)點點鏈表中。｝｝】ENDP;{ccrt_grraph}【討論】在本算算法中，設(shè)輸輸入的邊不含含有重復(fù)邊，即即輸入（vii，vj）后，即即不應(yīng)再輸入入（vi，vj），也也不應(yīng)再輸入入（vj，vi）。否則則，本算法應(yīng)應(yīng)添加查詢功功能（即下面面searcch過程）。查查詢成功時該該邊不再加入入到圖的存儲儲結(jié)構(gòu)中。FUNCssearchh(g:addjmuliist;I,,j:1...vtxnuum):eddgeptrr;｛本算法在圖gg中查詢頂點點vi，vj間的邊結(jié)結(jié)點是否已建建立。如是，則則返回該邊結(jié)結(jié)點的指針，否否則返回niil｝p:=gg[i].ffirsteedge;foound:==falseeWHIILE((p<>NIIL)AANDNNOTffoundDOIFFp^..ivex==i{結(jié)結(jié)點中iveel，jvex域均可能為為i}THEENIFp^.jvvex=jTHEENfoound::=truueELSSEp::=p^.iilink｛順ilinnk下找｝ELSSEIFFp^.iivex=jj｛p^.jvvex=i｝｝THEENfouund:==trueELLSEpp:=p^..jlinkk｛｛順jlinnk下找｝;ENDF;{seaarch}PROCinnsert__edge(VARg:adjjmulisst;vii,vj:vvtxptrr);｛本算法在鄰鄰接多重表中中插入邊（vi，vj）｝i:=loc__verteex(g,vvi);j:=loc__verteex(g,vvj);fp:=seaarch(gg,i,j));IFfp:==nil｛｛若邊（vii，vj）在圖圖中不存在｝｝THEN【new(pp);p^.ivvex:=ii;p^^.jvexx:=j;p^.illink:==g[i]..firsttedge;;g[ii].firrstedgge:=p;;p^.jllink:==g[j]..firsttedge;;g[jj].firrstedgge:=p;;】ENDP;{inssert}

PROCinnsert__verteex(VVARg::adjmuulist;;v:vttxptr));｛本算法在鄰接接多重表中插插入頂點V。設(shè)頂點向向量足夠大，插插入一頂點也也就是加一個個向量元素，設(shè)設(shè)m是已有頂點點數(shù)，則｝gg[m+1]].dataa:=v;;g[m++1].fiirsteddge:=nnil;ENDP;{inssert_vvertexx}

PROCdeelete__edge(VARRg:addjmuliist;vvi,vj::vtxpttr);{本算法在鄰接接多重表g中刪除邊（vvi，vj）｝ i:=loc__verteex(g,vvi);j:=loc__verteex(g,vvj);fp:=seaarch(gg,i,j));IFfp<>>nilTHEN【p:=gg[i].ffirsteedge;q:=niil;{修改改i的鏈表邊結(jié)結(jié)點(vi,,vj)的前前驅(qū)的指針}}WHILEEp<>fpDOO【q::=p;IFp^^.ivexx=iTHENp::=p^.iilinkELSEp::=p^.jjlink】IFq=nnil{刪刪除的邊是頂頂點vi的第一邊邊結(jié)點}THEENIFp^.ivvex=iTHHENgg[i].ffirsteedge:==p^.illinkELLSEgg[i].ffirsteedge:==p^.jllinkELLSE{{所刪除的不不是vi的第一邊邊結(jié)點}IFq^^.ivexx=iTTHENIIFp^..ivex==iTHEENq^..ilinkk:=p^..ilinkkELSEEq^.iilink::=p^.jjlinkEELSEIIFp^..ivex==iTHHENq^^.jlinnk:=p^^.ilinnkELSSEq^^.jlinnk:=p^^.jlinnk;p:==g[j]..firsttedge;;q:=nnil;{{修改j的鏈表邊結(jié)結(jié)點(vi,,vj)的前前驅(qū)的指針}}｛從vj的邊結(jié)點點鏈表中找到到（vi，vj）邊，修修改前驅(qū)指針針，算法同上上，故略｝disspose((fp);】ENDP；{ddeletee_edgee}PROCdeelete__verteex(VVARg::adjmuulist;;v:vttxptr));{刪除頂點的算算法，該頂點點刪除后，在在其頂點向量量數(shù)據(jù)域中作作標(biāo)記，且要要刪除與該頂頂點相關(guān)的所所有邊}i:==loc_vverdexx(g,vv);p:==g[i]..firsttedge;;WWHILEp<>nnilDOO【IFFp^.iivex=IITHENNs:=pp^.iliink{{記住下一邊邊結(jié)點}ELSEs:=p^^.jlinnk;IIFi=pp^.iveexTHEENdellete_eedge((g:,v,,g[p^..jvex]].dataa)ELSEdelette_edgge(g::,v,g[[p^.ivvex].ddata)pp:=s】ENDP;{{delette_verrtex}

2、編寫對圖圖的深度優(yōu)先先非遞歸遍歷歷算法?！痉治觥渴故褂脳＃{(diào)用用過程的算法法同教材，對對被調(diào)用過程程編寫如下：：PROCCdfss(g:addjlistt;v00:vtxpptr);｛｛本算法從頂頂點v0開始。在在圖g中進(jìn)行深深度優(yōu)先遍歷歷。算法中vvisiteed是在主過過程中已賦值值falsee的輔助數(shù)組組，s是元素為邊邊（?。┙Y(jié)點點的工作棧。｝｝initstaack(s));wrrite(vv0);visitted[v00]:=trrue;p:=g[v]].firsstarc;;WHILE(p<>nnil)ANDNOTemptyy(s)DO【W(wǎng)HILEp<>nnilDDOIFFvissited[[p^.addjvex]]THEENp::=p^.nnextarrcELSSE【writte(pp^.adjjvex);;pushh(s,p));vissited[p^.aadjvexx]:=trrue;p:==g[p^..adjveex].fiistarcc;】IFNOTemptyy(s)THEN【pp:=popp(s);p:=p^.nnextarrc】

】ENDP; {{dfs}第八章動態(tài)態(tài)存儲管理

一、內(nèi)容提要

1．

動態(tài)存存儲管理指的的是在用戶需需要時給分配配內(nèi)存，而在在用戶結(jié)束使使用時，系統(tǒng)統(tǒng)要收回用戶所占空空間。2．

可利用用空間表的三三種結(jié)構(gòu)形式式：結(jié)點固定定大?。环謳讕追N規(guī)格；任任意大小。3．

可利用用空間表的兩兩種組織形式式：目錄表，鏈鏈表。4．

可利用用空間表的分分配方式：首首次擬合法，最最佳擬合法，最最差擬合法。5．

可利用用空間表的分分配和回收的的兩種基本實實現(xiàn)方法：邊邊界標(biāo)識法，伙伙伴系統(tǒng)。6．

無用單單元回收和緊緊縮存儲的概概念。

二、學(xué)習(xí)重點

1、概念：可利利用空間表及及分配方式，緊緊縮存儲，伙伙伴系統(tǒng)，等等。2、邊界表示法法的分配及回回收算法。3、伙伴系統(tǒng)的的分配及回收收算法。

三、例題解析

設(shè)有大小為5112字節(jié)的存存儲，有6個用戶申請請大小分別為為23，4