數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)知識點兼容版

1、數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)復(fù)習(xí)要點：第一章1 .相關(guān)基本概念：數(shù)據(jù)、數(shù)據(jù)元素（基本單位）、數(shù)據(jù)項（最小單位）、算法及其特征等； 數(shù)據(jù)：所有能輸入到計算機中并被計算機程序處理的符號總稱。 數(shù)據(jù)元素：基本單位。 數(shù)據(jù)項：最小單位。 算法特征（5點）：有窮性；確定性；可行性；輸入；輸出。2 .邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（物理結(jié)構(gòu)）及其類型；邏輯結(jié)構(gòu)有四種基本類型：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。注：期中考題目數(shù)據(jù)結(jié)構(gòu)分為兩大類，即為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。其中邏輯結(jié)果又分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，存儲

2、結(jié)構(gòu)一共有四種（順序、鏈接、索引、散列）。3 .算法分析：語句頻度（執(zhí)行次數(shù)）計算、時間和空間復(fù)雜度分析。表示方法 語句頻度：直接寫次數(shù)。 時間復(fù)雜度：0（執(zhí)行次數(shù)），如：O（n）o 空間復(fù)雜度：0（所需空間）第二章1213212428304277123456781.順序表（數(shù)組）插入、刪除、有序表合并算法及其移動次數(shù)計算；序號12345678表示L.elem01234567順序表插入算法思想：如果要在序號5前插入元素e,需要將序號58向后移動一個位置。移動次數(shù)為4次，公式n-i+1StatusListInsert_Sq(SqList&L.inti,ElenTypeej在第i個元素前插

3、入新元素3當(dāng)前i為5if(i<111i>L-length+1)returnERROR;/i值不合丫去if(L.length>=L.listsize)當(dāng)前存儲空間已滿，增加分配<ElemType*newbace=(ElemType*)realloc(L.elenij(L-listsize+LISTIHCREMENT)*sizeof(ElemType);if(fnewbace)returnERROR;L.elea=neibace;L-listsize+=LISTIHCREMENT；ElemType*p;ElemType*q=&(L.elen»i-1);/序

4、號5對應(yīng)L.elEmgfor(p=&(L.elemL.length-1);p>=q;p)表長L.length值為8,P揖向序號也對應(yīng)L®pc7*(P+D=*P；"元素后移*1=序號5對應(yīng)L.elgm叼賦值為e*+L.length;returnOK;順序表刪除算法思想：如果要刪除序號5元素，需要將68依次向前移動一位移動次數(shù)為3次，公式n-istatusListDeiete_Sq(SqList&L.inti,ElenTupete)刪除第i個元素，并用。返回其值，當(dāng)前i為5<if(1<1|i>L.length)returnERROR;/i

5、值不合法ELcmType*p=&(!_.£電mi-1);"P為被刪除元素檢置-*P；被刪除元素的值賦值給eElenTt|pe*q=L.elem+L.length-1;表尾元素位置Llem叼+7,為L-Uem7for(+p；p<=q；+p)P先移到序號叫判斷是查公于q*(p-1)=*p；元素前移-L.length;表長減1returnOK;有序表合并LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)則LC=(2,3,5,6,8,8,9,11,11,15,20)算法思想(以非遞減為例)：La和Lb非遞減排列，La與Lb中元素逐個比較，較小的先插入

6、Lc中。注：非遞減是指遞增排序，但元素有可能相等，與之相對的有非遞增排序。移動次數(shù)為(La.length+Lb.length)voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)/需爵線性表呼Lb的元素按值非遞減排列.歸并門和Lb得到新的順序線性表L*Lc的元素也按值非遞減排列。Elemlype*pa,*pbf*pcf*pa_last,*pb_last;pa=La.elem;pb=Lb.elem：Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElenType*)malloc(Lc,lis

7、tsize*sizeoF(EleinT|fpe);"p嗡向if(*Lc.elem)exitCOUERFLOW);/存儲分配失敗_pa_last=La.elem+La.length-1;“paj4只指向La最后一個元素pblast=Lb.el&mLb.length-1;/pb指向Lh最后一個元素iihile(pa<-palast&&pb<=pblast)</歸并if(*pa<=*pb)*pc+=*pa+;如第PH當(dāng)前宿不于pb當(dāng)前值，pc當(dāng)前位置的值賦值為pc當(dāng)前值else*pc+=*pt)+;>_while(pa<=pa_l

8、ast)«pc+*-*p3*+;/每入La的剩余元塞while(pb<=pb_last)*pc+*=*pb+；/插入LD的剩余元素這兩個岫i12語句只會執(zhí)行其中一個/MergeList2.鏈表（有無頭節(jié)點、單雙、循環(huán)）插入（前、后）、刪除（前、本身、后）的指針掛接、建立（不帶頭節(jié)點）算法。單鏈表每個節(jié)點有數(shù)據(jù)域和指針域datanextm頭ala2a3a4a5a6帶頭節(jié)點L-JinJZELEDJZELEELLHPTala2a3a4a5a6不帶頭節(jié)點L-匚一匚匚I一匚口一匚口一匚口一133PT團一口口口口口m單循環(huán)鏈表在P(a3)節(jié)點前插入S節(jié)點(1)Q=P;先讓Q指向a3(2)P

9、=L;/P指向第一個節(jié)點(帶頭結(jié)點指向頭結(jié)點，不帶頭結(jié)點指向al)(3)while(P->next!=Q)P=P->next;/找至Ua3的前驅(qū)a2,P指向a2(4)S->next=P->next;/P->next為a3,讓S->next等于a3(5)P->next=S;/a2指針域指向節(jié)點S 在P(a3)節(jié)點后插入S節(jié)點(1)S-next=P->next;(2)P->next=S; 刪除P(a3)前一個節(jié)點(1)Q=P;(2)P=L;(3)while(P->next->next!=Q)P=P->next;/找至Ua1(4

10、)P->next=P->next->next;讓a1指針域指向a3,從而刪除a2 刪除P(a3)節(jié)點(1)Q=P;(2)P=L;(3)while(P->next!=Q)P=P->next;/找至Ua2(4)P->next=P->next->next;/讓a2指針域指向a4,從而刪除a3 刪除P(a3)后一個節(jié)點(1)P->next=P->next->next;讓a3指針域指向a5,從而刪除a4雙鏈表每個節(jié)點有前驅(qū)指針、數(shù)據(jù)域、后繼指針priordatanext雙循環(huán)鏈表頭a1a2a3a4 在P(a2)節(jié)點前插入S節(jié)點技巧：先讓S

11、->prior和S->next與鏈表建立關(guān)系注：步驟(4)必須在步驟后面(1)S->next=P;/先讓S->next指向a2(2)S->prior=P->prior;/S->prior指向a1(3)P->prior->next=S;/再把a1->next指向S(4)P->prior=S;/a2->prior指向S 在P(a2)節(jié)點后插入S節(jié)點注：步驟(4)必須在步驟(3)后面(1)S->prior=P;(2)S->next=P->next;(3)P->next->prior=S;/a3-&g

12、t;prior指向S(4)P->next=S; 刪除P(a2)前一個節(jié)點a1(1)Q=P->prior;Q指向要被刪除的a1;(2)P->prior=P->prior->prior;/P->priro指向頭(3)P->prior->next=P;/頭->next指向P(4)free(Q);/釋放a1的存儲空間 刪除P(a2)節(jié)點(1)P->next->prior=p->prior;(2)P->prior->next=p->next;(3)free(P); 刪除P(a2)后一個節(jié)點a3(1)Q=P->

13、next;(2)P->next=P->next->next;/a2->next指向a4(3)P->next->prior=P;/a4->prior=P(4)free(Q);/釋放a3存儲空間建立(不帶頭節(jié)點)單鏈表voidCreateList_l(LinkLi.st&l,intn)/建立不帶頭結(jié)點鏈表LinkListp,q;for(inti=Q;i<n;*+i)p=(LinkList)malloc(sizeoF(LHode);cin»p->(lata；輸入數(shù)據(jù)速p->next=NULL;p當(dāng)前為最后一個節(jié)點IfCl=

14、0)第一個節(jié)點continue;不執(zhí)行后面的語句<|->next=p;讓前一個節(jié)點next指針指向pq=p;"q指向p讀程序：設(shè)n為2（i取0,1）dat4i=0時，pTLTqTdata八datai=1時，LTqTpTqTpT第三章1 .棧的進出序列、棧、隊列、循環(huán)隊列的滿/空條件；由于棧的插入、刪除操作是限制在棧頂進行的，因而后進棧的元素必然是先出棧，0.所以棧是“后進先出”表。由于隊列的輸入、輸出操作分別在隊的兩端進行，因此先入隊的元素必然先輸出，故隊列又稱為“先進先出”表棧的進出序列例題：進棧序列為123,可能得到的出棧序列是什么？答：共五種123/132/213/

15、231/321進出棧情況（以132序列為例）：1進棧一1出棧，輸出1-2進棧一3進棧一3出棧一2出棧輸出32棧、隊列、循環(huán)隊列的滿/空條件?？諚l件：s.top=s.base;棧滿條件：s.top-s.base=stacksize;隊空條件：Q.front=Q.rear;隊滿條件：q->rear-q->front=MAXSIZE循環(huán)隊列空條件：Q.front=Q.rear循環(huán)隊列滿條件：為避免在隊滿是隊頭指針和隊尾指針也是重合的情況，規(guī)定隊列中還有一個空的存儲單元時為隊滿，即為Q.front=（Q.rear+1）MODmaxsize（MOD為取余運算符）。因而，這種循環(huán)隊列不適合用動

16、態(tài)數(shù)組作為存儲結(jié)構(gòu)。2.棧、隊列的存儲結(jié)構(gòu)、基本操作算法（雙向棧）；棧存儲結(jié)構(gòu) 順序棧typedefstructSElemType*base;SElemType*top;intstacksize;SqStack; 鏈式棧,dam.產(chǎn)型_匚1槿底 隊列存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)出隊列入隊列3%4.-BS3.8隊列的示意圖鏈式存儲結(jié)構(gòu)隊頭隊尾Q-itOTtQA-*T*Ta尸rrnH-hAQzrp5:"一雙向棧UIIUV棧i底棧i頂性口頂?？诘状鎯Y(jié)構(gòu)：typedefstructElemtype*base2;Elemtype*top2;BDStacktype;/雙向棧類型初始化：StatusIn

17、it_Stack(BDStacktype&tws,intm)初始化一個大小為m的雙向棧twstws.base0=(Elemtype*)malloc(sizeof(Elemtype)*m);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;returnOK;/Init_Stack入棧：Statuspush(BDStacktype&tws,inti,Elemtypex)/x入棧,i=0表示低端棧,i=1表示高端棧if(tws.top0>tws.top1)returnOVERFLOW;/注意此時的棧滿條件if

18、(i=0)*tws.top0+=x;elseif(i=1)*tws.top1卜-=x;elsereturnERROR;returnOK;/push出棧:Statuspop(BDStacktype&tws,inti,Elemtype&x)/x出棧,i=0表示低端棧,i=1表示高端棧if(i=0)if(tws.top0=tws.base0)returnOVERFLOW;x=*-tws.top0;elseif(i=1)if(tws.top1=tws.base1)returnOVERFLOW;x=*+tws.top1;elsereturnERROR;returnOK;/pop第四章1.

19、字符串模式匹配的簡單算法；intIndex(SStringS,SStringT,intpos)/算法4.5/返回子串T在主串S中第pos個字符之后的位置。/若不存在，則函數(shù)值為0。/其中，T非空，1WposWStrLength(S)。inti=pos;intj=1;while(i<=S0&&j<=T0)if(Si=Tj)/繼續(xù)比較后繼字符+i;+j;else/指針后退重新開始匹配i=i-j+2;/此時i為上次開始比較位置的下一位j=1;if(j>T0)returni-T0;elsereturn0;/Index2.計算NEXTnextj:0111232技巧：第一

20、二個肯定是0,1!如果要計算next4,找的字符串必須是以第3個字符c為結(jié)尾，第1個字符a為開頭的。以第6個為例，a前一個字母是b,以第5個字符b為結(jié)尾的ab剛好和以第1個字符為開頭的ab匹配，所以next6=2+1=3。第五章1.二維數(shù)組的地址(下標)換算;習(xí)題5.1假設(shè)有二維數(shù)組A6*8,每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置(基地址)為1000,計算：(1)數(shù)組A的體積(即存儲量)6*8*6=288字節(jié)(3)按行存儲是，元素a14的第一個字節(jié)的地址1000+(8*1+4)*6=1072基址+(每行的元素個數(shù)*行數(shù)+當(dāng)前列序)*每個元素所占存儲單元(4)按列存

21、儲時，元素a47的第一個字節(jié)的地址1000+(6*7+4)*6=6276基址+(每列的元素個數(shù)*列數(shù)+當(dāng)前彳T序)*每個元素所占存儲單元習(xí)題5.2假設(shè)按低下標優(yōu)先存儲整數(shù)組A9*3*5*8時，第一個元素的字節(jié)地址是100,每個整數(shù)占四個字節(jié)。問下列元素的存儲地址是什么？(2) a1111地址：100+(3*5*8*1+5*8*1+8*1+1)*4=776(3) a3125地址：100+(3*5*8*3+5*8*1+8*2+5)*4=1784(4) a8247地址：100+(3*5*8*8+5*8*2+8*4+7)*4=44162 .特殊矩陣(三角、其他有規(guī)律)壓縮為一維的下標計算；下三角矩陣壓

22、縮為一維數(shù)組(記憶公式)技巧：推薦把公式(2)背下來(i,j,R范圍都是從0開始)，其他根據(jù)范圍變化公式(1)若1<=j,j<=n,0<=R<=n(n+1)/2-1當(dāng)i>=j時，k=i(i-1)/2+j-1;當(dāng)i<j時，k=j(j-1)/2+i-1.(2)若0<=i,j<=n-1,0<=R<=n(n+1)/2-1/注意i,j是0到n-1,下面的公式相當(dāng)于把(1)中i變成i+1,j變成j+1當(dāng)i>=j時，k=(i+1)i/2+j;當(dāng)j<j時，k=(j+1)j/2+i.(3)若1<=j,j<=n,1<=R&l

23、t;=n(n+1)/2/注意R是1到n(n+1)/2,下面公式相當(dāng)于把(1)中k變成k-1當(dāng)i>=j時，k=i(i-1)/2+j;當(dāng)i<j時，k=j(j-1)/2+i;(4)若0<=j,j<=n-1,1<=R<=n(n+1)/2當(dāng)i>=j時，k=(i+1)i/2+j+1;當(dāng)i<j時，k=(j+1)j/2+i+1;3 .稀疏矩陣的三元組表示。4.稀疏矩陣應(yīng)用的算法。(略)£)5.10T的三元組裝bxLsta第六章1 .二叉樹的性質(zhì)；性質(zhì)1：在二叉秋i的第i層上至多有2個結(jié)點(i/)。性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(k>

24、1)o性質(zhì)3:對任何一棵二叉樹T,如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為og2n+1。性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1日中)，有：(1)如果i=1,則結(jié)點i是二叉樹的根，無雙親；如果i>1,則其雙親是j/2(2)如果2i>n,則結(jié)點i無左孩子；如果2i4,則其左孩子是2i。(3)如果2i+1>n,則結(jié)點i無右孩子;如果2i+1芻，則其右孩子是2i+1。2 .二叉樹的先序、中序、后序、層次遍歷過程；樹的先序、后序、層次遍歷過程;光不遍歷：-+ab-c<l/ef中序

25、;遍歷：a+b*c-d-e/f后序;遍歷：abcd*+ef/-整次遍歷：-+/a*efb-cd3.二叉樹遍歷過程：先（根）序遍歷：根一左子樹一右子樹中（根）序遍歷：左子樹一根一右子樹后（根）序遍歷：左子樹一右子樹一根層次遍歷：從上到下，從左往右，逐個遍歷樹的遍歷過程：先根（次序）遍歷：先訪問根結(jié)點，然后依次先根遍歷根的每棵子樹（根一子樹）后跟（次序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點（子樹一根）層次遍歷：從上到下，從左往右，逐個遍歷注：樹與二叉樹相互轉(zhuǎn)化后樹的先根遍歷相當(dāng)于二叉樹的先序遍歷樹的后根遍歷相當(dāng)于二叉樹的中序遍歷給出兩個遍歷序列，畫出樹（二叉樹、樹）習(xí)題6.23畫出和下列已

26、知序列對應(yīng)的樹T:（1）樹的先根次序訪問序列為GFKDAIEBCHJ;（2）樹的后根次序訪問序列為DIAEKFCJHBGo注：樹的后根遍歷相當(dāng)于二叉樹的中序遍歷EJ由（1）知G為根；G為根，聯(lián)系（2）知G無右子樹；觀察（1）,F為G左子樹；根據(jù)，觀察（2）知DIAEK在F左邊,在F右邊；觀察（1）,K為F左子樹；根據(jù)，觀察（2）知K無右子樹；觀察（1）,D為K左子樹；根據(jù)，觀察（2）知D無左子樹；觀察（1）,A為D右子樹；觀察（2）,IE分別為A左右子樹；的右子樹自行觀察判斷。4 .二叉樹與樹相互轉(zhuǎn)換；樹轉(zhuǎn)化成二叉樹：規(guī)則：樹的最左孩子變成二叉樹左子樹，該左孩子的兄弟變成二叉樹左子樹的右子樹向

27、仁）注：原樹中B為A最左孩子，C,D為B兄弟，變成二叉樹后C成為B右子樹，D成為C右子樹。二叉樹轉(zhuǎn)化成樹5 .求哈夫曼樹和給出編碼、帶權(quán)路徑長度計算。習(xí)題6.26假設(shè)用于通信的電文僅由0.07,0.19,0.02,0.06,0.32,0.21,0.10路徑長度8個字母組成，字母在電文中出現(xiàn)的頻率分別為。試為這8個字母設(shè)計哈夫曼編碼，并求帶權(quán)7、19、2、6、32、3、21、10。當(dāng)前未用權(quán)：7、19、2、6、32、3、21、10,選出2、3構(gòu)造出5。當(dāng)前未用權(quán)：7、19、6、32、21、10、5,選出5、6構(gòu)造出11。當(dāng)前未用權(quán)：7、19、32、21、10、11,選出7、10構(gòu)造出17。當(dāng)前未

28、用權(quán)：19、32、21、11、17,選出11、17構(gòu)造出28。當(dāng)前未用權(quán)：19、32、21、28,選出19、21構(gòu)造出40。當(dāng)前未用權(quán)：32、28、40,選出32、28構(gòu)造出60。剩下權(quán)：40、60,構(gòu)造出100編碼：樹的左分支為0,右分支為1。得到哈夫曼編碼為A:1101B:01C:11111D:1110E:10F:11110G:00H:1100帶權(quán)路徑長度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100=2.61注：該公式為：A路徑長*A權(quán)+B路徑長*B權(quán)+H路徑長*H權(quán)，因為設(shè)的權(quán)值是原來的100倍，所以結(jié)果除以100。第七章1.鄰接矩陣、鄰接表存儲結(jié)

29、構(gòu)及其特征;圖7.1圖的示例(«)有向圖Gr(b)無向圖G圖7.8圖的部接矩陣注以后向圖G1為例01(T(有'路徑用1,v1v2否則0)v3v4101v10110011v20000100v3000110ojv41000的鄰接表:的鄰接表.G】的逆鄰接表收012300110100002000131000注：以有向圖G1為例第0行值為1的是1、2,所以有V1一2一1。第1行值全為0,所以有V2。第2行值為1的是3,所以有V3-3。第3行值為1的是0,所以有V4-0。2.求最小生成樹（Prim、Kruskal）;（a）普里姆（Prim）：以點為基礎(chǔ)從V1開始，找到最小邊（V1,V3

30、）;尋找與VI、V3相關(guān)聯(lián)的最小邊，找到（V3,V6）;尋找與VI、V3、V6相關(guān)聯(lián)的最小邊，找到（V6,V4）;尋找與VI、V3、V6V4相關(guān)聯(lián)的最小邊，此時有（V4,V1）和（V3,V2）,因為（V4,V1）與原來的邊構(gòu)成圈，所以選擇（V3,V2）。（如果（V4,V1）不與原來的邊構(gòu)成圈，則二條邊任選一條）；尋找與V1、V3、V6V4、V2相關(guān)聯(lián)，并且不與原來邊構(gòu)成圈的最小邊，找到（V2,V5）;克魯斯卡爾（Kruskal）（避圈法）：以邊為基礎(chǔ)方法介紹：依次尋找權(quán)最小邊，避免生成一個圈，所有點聯(lián)通時生成最小樹。3 .拓撲排序；步驟：（1）在有向圖中選一個沒有前驅(qū)的頂點且輸出之。（2）從圖

31、中刪除該頂點和所有以它為尾的弧。注：拓撲排序不唯一。、Floyd)。算法求題7.11圖中從頂點a到其他各頂點間的最短路徑，寫4 .求最短路徑過程(Dijkstra迪杰斯特拉(Dijkstra)習(xí)題7.11試利用Dijkstra出執(zhí)行算法過程中各步狀態(tài)。10求解過程:終點bcdef£s【終點集)K=1152(atc)12K-2156b)p1210(aeQ6(a.c/)®jfK=3153)11(a丁七，f.d)10(口便通)16(a,cTfkg)加aC.f)K=415(B.b)11(siCtfid)16(fliCJig)iCtf»e)K=5*1&14(0ii&

32、#163;1(f.d1g)a-cJte.d值K=615K=1時，找a能直接到達的點，有b,c,d,(a,c)權(quán)最小，(a,c)為a到c最短路徑，將c放如終點集S;K=2時，找a能直接到達的點，或通過(a,c)能到達的點，(a,c,f)權(quán)最小，(a,c,f)為a到f的最短路徑，將f放入終點集S;K=3時，找a能直接到達的點，或通過(a,c)能到達的點，或通過(a,c,f)能到達的點，(a,c,e)權(quán)最小，(a,c,e)為a到e最短路徑，將e放入終點集S;K=4時，找a能直接到達的點，或通過(a,c)能到達的點，或通過(a,c,f)能到達的點，或通過(a,c,e)能到達的點，(a,c,f,d)為a

33、到d最短路徑，將d放入終點集S;K=5時，找a能直接到達的點，或通過(a,c)能到達的點，或通過(a,c,f)能到達的點，或通過(a,c,e)能到達的點，或通過(a,c,f,d)能到達的點，(a,c,f,d,g)權(quán)最小，為a到g最短路徑，將g放入終點集S;K=6時，只剩下(a,b),(a,b)為a到b最短路徑，將b放入終點集S。弗洛伊德(Floyd)b-041廠602,3oo0.(b)圖7,36帶權(quán)有向圖(Q有向網(wǎng)Gt(b)鄰接矩陣DDta>Dfl)012012012012004110411Q46Q461602602602502231803703703?0Pp(-1)p(l)p<S

34、3012012012Q1Z0ABACABACABABCABABC1BAECBABCBABCBCABC2CACACABCACABCACAB圖7.37圖7.36中有向圖的各對頂點間的最爆路徑及其路徑長度注：D(1)ij是從Vi到Vj的中間頂點的序號不大于1的最短路徑的長度；D(k)ij是從Vi到Vj的中間頂點的序號不大于k的最短路徑的長度；D(n-1)ij就是從Vi到Vj的最短路徑的長度。D(-1)欄中，Vi-Vj不允許有轉(zhuǎn)折點。直接填鄰接矩陣。D(0)欄中，Vi-Vj只允許通過V0轉(zhuǎn)折，或者不轉(zhuǎn)折。通過V0轉(zhuǎn)折權(quán)值小于原權(quán)值，就把原權(quán)值替換掉。D(1)欄中，Vi-Vj只允許通過V0、V1轉(zhuǎn)折，或

35、者不轉(zhuǎn)折。如果轉(zhuǎn)折后權(quán)值小于原權(quán)值，替換。D(2)欄中，Vj-Vj允許通過V0、V1、V2轉(zhuǎn)折，或者不轉(zhuǎn)折，如果轉(zhuǎn)折后權(quán)值小于原權(quán)值，替換。此時p(2)中就是各點間的最短路徑。如果要找的值大于如果要找的值小于平均查找長度等概率條件下,ASL=一呼夫mid=(low+high)/2,繼續(xù)比較；,繼續(xù)比較。第九章1 .以下所有查找成功平均查找長度2 .順序查找；折半查找；順序查找：從表中最后一個記錄開始，逐個進行比較。平均查找長度等概率時，平均查找長度ASL=(n+1)/2不等概率時，ASL=nP1+(n-1)P2+2Pn-1+Pn折半查找：指針low和high分別指示待查元素所在范圍的下界和上界

36、，Smid,則讓mid=(mid+1+high)/2Smid,則讓mid=(low+mid-1)/2當(dāng)n>50時，有近似結(jié)果ASL=Og：(n+1)-13.二叉排序樹的插入二叉排序樹建立(建立)、刪除、平衡過程;(1)若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；(2)若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；(3)它的左、右子樹也分別為二叉排序樹。習(xí)胰9.哨已知如下所示長度為12的表(Jan*Feb»Mar*Apr,May.June,July.Aug.Sep.Oct,Nov,Dec)<1)試按表中元素的順序依次插入一棵初始為空的二叉排

37、序?qū)?畫出插入完成之后的二叉排序樹并求其在等概率的情況下杳找成功的平均查找長度。<1)求得的二叉排序樹如下圖所示，在等概率情況下查找成功的平均查找長度為ASLt=-(1X1+2X注：中序遍歷二叉排序樹，得到從小到大序列根據(jù)字母的先后確定大小插入Jan;F小于J,Feb成為Jan左子樹；M大于J,Mar成為Jan右子樹；Apr小于Jan,且Apr小于Feb,Apr成為Feb左子樹；May大于Jan,且May大于Mar,May成為Mar右子樹；June大于Jan,且June小于Mar,June成為Mar左子樹。剩下的略。二叉排序樹刪除()3種情況：(1)*p為葉子節(jié)點，直接刪除。(2) *p

38、只有一個孩子*child只需將*child和*p的雙親直接連接后，即可刪去*p。(3)*p有兩個孩子用*p的直接前驅(qū)或直接后繼代替*p,然后刪除它的直接前驅(qū)或直接后繼。平衡二叉樹：樹上任何節(jié)點的左右子樹深度差都不超過1插入節(jié)點P后不平衡，找到離P最近的不平衡點，根據(jù)二叉排序樹的建立進行調(diào)整。序列:Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec(i)(1)插入Aug時，F(xiàn)eb左右子樹深度差超過1不平衡(50XE變化后的2(72)變化后(】)>)(2)插入Oct時，最近不平衡點為May)因為Sep>Oct>May,所以O(shè)ct作為

39、雙親變化后的(3)插入Nov時，Jan不平衡。把Jan左轉(zhuǎn)，Mar的左子樹變成Jan右子樹。4.最終平衡樹哈希表構(gòu)造、沖突解決方法；除留余數(shù)法、線性探測或鏈地址法。構(gòu)造：除留余數(shù)法：H(key)=keyMODp,p<=m沖突解決：，k(k<=m-1)線性探測法：Hi=(H(key)+曲Modmi=1,2,鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。例題：已知一個線性表(38,25,74,63,52,48),假定采用散列函數(shù)h(key)=key%7計算散列地址，并散列存儲在散列表A0.6中，采用線性探測方法解決沖突。38:38%7=3,查找次數(shù)為1。25:25%7=4,

40、查找次數(shù)為1。74:74%7=4,與25沖突,(4+1)%7=5,查找次數(shù)為2。63:63%7=0,查找次數(shù)為1.52:52%7=3,與38沖突,(3+1)%7=4,與25沖突，(4+1)%7=(5+1)%7=5,與74沖突，(1+3+1+1+2+4)76=26,杳找次數(shù)為4。48:48%7=6,與52沖突，(6+1)%7=0,與63沖突，(0+1)%7=1,查找次數(shù)為3等概率成功查找的平均查找長度為:地址：0123456634838257452次數(shù)：131124例9-3已知一組關(guān)鍵字為U9J4.23.01.68,20,84,27.55,11,10,79)則按哈希函數(shù)H(key)=keyMOD

41、13和鏈地址法處理沖突構(gòu)造所得的哈希表如圖9.26所示,125520A3456789101112圖9.建鏈地址法處理神突時的哈爵衰第十章1 .簡單排序(直接插入、選擇、冒泡)的過程； 直接插入(略) 選擇排序基本思想：依次在序列中選出最小的記錄Rk,將它與第1個記錄R1交換。模式：for(i=0;i<10;i+)for(j=i;j<10;j+); 冒泡排序：基本思想：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。模式：for(i=0;i<n;i+)for(j=0;j<n-i-1;j+);2 .先進排序(希爾、快速、堆、歸并、基數(shù))過程；希爾排序：基本思想：先取一個

42、小于n的整數(shù)d1作為第一個增量，所有距離為dl的倍數(shù)的記錄放在同一個組中，先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量di=1?！境跏缄P(guān)鍵字:一越排序結(jié)果:493865977613274955044913t3827-I|6549i9755I7604二趟排序結(jié)果：三趟排序結(jié)果:13274955044938659776圖10.5希爾排序示例初始關(guān)9字快速排序：基本思想：選第一個記錄為支點，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄關(guān)鍵字比支點小，另一個部分記錄的關(guān)鍵字比支點大。再可分別找兩個支點，對這兩部分記錄繼續(xù)進行快速排序。p

43、ivorkcy進行I次交換之后迸行2次交換之后進行3次交換之后進行4次交換之后273813769765麗完成一趟排序76976549初始狀態(tài)一次劃分之后分別進行快速排序有序序列493865972738131491132738結(jié)束結(jié)束1327384976132749><76976549)由6576(97)49(65結(jié)束結(jié)束49657697堆排序：n個關(guān)鍵字序列Kl,K2,，Kn稱為堆，必須所有根大于（或小于）其子樹。例題：無序序列49,38,65,97,76,13,27,49），進行堆排序思路：將次序列寫出完全二叉樹形式，然后從最有一個非終端結(jié)點開始篩選。歸并排序：析始關(guān)字一18歸并

44、之后二通舊井之后三前歸并之后圖10.132路歸并排序示例基數(shù)排序：先將個位數(shù)值與fi中的i值相等的放入相應(yīng)位置將十位數(shù)值與fi中的i值相等的放入相應(yīng)位置將百位數(shù)值與fi中的i值相等的放入相應(yīng)位置()930f£5f£6f7(WJfE»圖10.14鏈式基數(shù)排序示例C»)初始狀態(tài)1(b)第一君分配之后*(C)第一通收集之后，d)第二母分配之后.(G第二收集之后fU)第三也分配之后(G第三船收出之后的有序文杵甲甲fflf5(b)3.各種排序的特點、穩(wěn)定性、時間復(fù)雜度（包括平均、最好、最壞）排序方法平均時閶地壞情況輔助存儲簡單排序CXrt()|'OGi，)

45、CKD快速排序O(nloflit)tXn1)0(1。5)堆播序OCnJogn)CXulofn)0(1)歸并排序O(nlogn)。（制。）CKn)基數(shù)排序0(點打+rd)CXref)希爾排序O(nlogn)0(nr)排序方法穩(wěn)定性插入排序穩(wěn)定選擇排序不穩(wěn)定冒泡排序穩(wěn)定希爾排序不穩(wěn)定快速排序不穩(wěn)定堆排序不穩(wěn)定歸并排序穩(wěn)定基數(shù)排序穩(wěn)定數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合結(jié)構(gòu)：數(shù)據(jù)元素之間的關(guān)系；操作：對數(shù)據(jù)的加工處理；數(shù)據(jù)結(jié)構(gòu)研究的問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲，如何處理。(字符字符用文字圖形圖象聲音)對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：數(shù)據(jù)的邏輯結(jié)構(gòu)；邏輯

46、結(jié)構(gòu)它屬于用戶的視圖，是面向問題的數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：集合：”屬于同一個集合”；線性結(jié)構(gòu)：一對一的線性關(guān)系；樹結(jié)構(gòu)：一對多的層次關(guān)系；圖結(jié)構(gòu)：多對多的任意關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的物理存儲方式，屬于具體實現(xiàn)的視圖，是面向計算機的通常有兩種存儲結(jié)構(gòu)：1 .順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示。2 .鏈接存儲結(jié)構(gòu)：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲數(shù)據(jù)結(jié)構(gòu)的抽象層次線性結(jié)構(gòu)直接存取類數(shù)組，文件順序存取類表，棧，隊列，優(yōu)先隊列廣義索引類

47、線性索引，搜索樹非線性結(jié)構(gòu)層次結(jié)構(gòu)類樹，二叉樹，堆群結(jié)構(gòu)類集合，圖3)數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作算法分析：時間復(fù)雜度算法的概念：算法是求解問題的操作序列(或操作步驟)。時間復(fù)雜度T(n):以求解問題的基本操作(原操作)的執(zhí)行次數(shù)作為算法時間的度量for(i=1;i<=n;i+)for(j=1;j<=n;j+)x+;單條語句O(1)一條循環(huán)O(n)兩條循環(huán)0(門八2).一、線性表1線性表的邏輯結(jié)構(gòu)：在線性表中，除第一個元素和最后一個元素外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。2順序表存儲特點：1）元素存儲在一組連續(xù)的內(nèi)存單元中2）通過元素的存儲順序反映線性表中數(shù)

48、據(jù)元素之間的邏輯順序；3 順序表操作特點：1）可隨機存取順序表的元素；2）順序表的插入刪除操作要通過移動元素實現(xiàn)4 線性鏈表存儲特點：1）用任意一組的存儲單元存儲線性表中的數(shù)據(jù)元素；2）通過保存直接后繼元素的存儲位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；5 線性鏈表操作特點1）不能隨機存取元素；2）插入、刪除操作通過修改結(jié)點的指針實現(xiàn)；6順序表的插入平均要移動表的一半元素n/2、刪除操作平均要移動（n-1）/27順序表能隨機存取元素的原因是：順序表能通過L.elemi-1或L.elem+（i-1）直接定位元素的存儲地址。8線性鏈表不能隨機存取元素的原因是：需從線性鏈表的頭指針開始，順著鏈指針定位元素的

49、存儲地址9對于經(jīng)常要存取元素的應(yīng)用，線性表應(yīng)采用順序存儲結(jié)構(gòu)10對于經(jīng)常要插入刪除元素的應(yīng)用，線性表應(yīng)采用鏈式存儲結(jié)構(gòu)二、棧和隊列棧：1棧是限定僅能在表尾一端進行插入、刪除操作的線性表；后進先出2表尾稱為棧頂，表頭稱為棧底；3棧的滿空判斷4棧頂元素的位置由一個棧頂指針指示；5進棧、出棧操作要修改棧頂指針；6一個棧的輸入序列為a,b,c,則所有可能的出棧序列為：abc,acb,bac,bca,cba7棧的順序存儲結(jié)構(gòu)1 ）用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素；2 ）棧頂元素的位置由棧頂指針指示；8棧的鏈式存儲和實現(xiàn)棧的鏈式存儲與線性表的鏈式存儲類似，可用帶頭結(jié)點的線性鏈表存儲。注意

50、：棧頂指針就是帶頭結(jié)點的線性鏈表的頭指針隊列：1隊列是限定僅能在表尾一端插入，表頭一端刪除操作的線性表；先進先出2表尾稱為隊頭，表頭稱為隊尾3隊頭、隊尾元素的位置分別由隊頭指針和隊尾指針指示；4隊列的滿空判斷5入隊操作要修改隊尾指針，出隊操作要修改隊頭指針；6循環(huán)隊列一一隊列的順序存貯結(jié)構(gòu)三、數(shù)和二叉樹1樹的邏輯結(jié)構(gòu)樹：是一種一對多的結(jié)構(gòu)關(guān)系或稱為分枝結(jié)構(gòu)關(guān)系，除了根之外，每個元素只有一個直接前趨；，但每個元素可以有零個或多個直接后繼；2樹的基本術(shù)語：樹的結(jié)點孩子結(jié)點雙親結(jié)點兄弟結(jié)點結(jié)點層（根為1）樹的高度（層數(shù)）結(jié)點的度（結(jié)點子樹的個數(shù)）樹的度（樹中最大的結(jié)點度）葉子結(jié)點（度為0的結(jié)點）分枝

51、結(jié)點（度不為0的結(jié)點）森林（互不相交的樹集合）3二叉樹的定義：或為空樹，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹。4二叉樹的五種基本形態(tài)5二叉樹性質(zhì)性質(zhì)1在二叉機t的第i層上最多有2A（i-1）個結(jié)點性質(zhì)2深度為k的二叉樹最多有2Ak-1個結(jié)點，最少有k個結(jié)點性質(zhì)3設(shè)二叉樹葉子結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為log2（n+1）性質(zhì)5在完全二叉權(quán)寸中編號為i的結(jié)點，1）若有左孩子，則左孩編號為2i;2）若有右孩子，則有孩子結(jié)點編號為2i+1;3）若有雙親，則雙親結(jié)點編號為i/2;4）結(jié)點所在層次為10g2i+15）若i為奇數(shù)，且i!=1,它處于右兄弟位置，則它的左兄弟為