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

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

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

3、入新元素3當(dāng)前i為5if(i<111i>L-length+1)returnERROR;/i值不合丫去if(L.length>=L.listsize)當(dāng)前存儲(chǔ)空間已滿，增加分配<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、號(hào)5對(duì)應(yīng)L.elEmgfor(p=&(L.elemL.length-1);p>=q;p)表長(zhǎng)L.length值為8,P揖向序號(hào)也對(duì)應(yīng)L®pc7*(P+D=*P；"元素后移*1=序號(hào)5對(duì)應(yīng)L.elgm叼賦值為e*+L.length;returnOK;順序表刪除算法思想：如果要?jiǎng)h除序號(hào)5元素，需要將68依次向前移動(dòng)一位移動(dòng)次數(shù)為3次，公式n-istatusListDeiete_Sq(SqList&L.inti,ElenTupete)刪除第i個(gè)元素，并用。返回其值，當(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(zhǎng)-Uem7for(+p；p<=q；+p)P先移到序號(hào)叫判斷是查公于q*(p-1)=*p；元素前移-L.length;表長(zhǎng)減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中元素逐個(gè)比較，較小的先插入

6、Lc中。注：非遞減是指遞增排序，但元素有可能相等，與之相對(duì)的有非遞增排序。移動(dòng)次數(shù)為(La.length+Lb.length)voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)/需爵線性表呼Lb的元素按值非遞減排列.歸并門(mén)和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);/存儲(chǔ)分配失敗_pa_last=La.elem+La.length-1;“paj4只指向La最后一個(gè)元素pblast=Lb.el&mLb.length-1;/pb指向Lh最后一個(gè)元素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的剩余元素這兩個(gè)岫i12語(yǔ)句只會(huì)執(zhí)行其中一個(gè)/MergeList2.鏈表（有無(wú)頭節(jié)點(diǎn)、單雙、循環(huán)）插入（前、后）、刪除（前、本身、后）的指針掛接、建立（不帶頭節(jié)點(diǎn)）算法。單鏈表每個(gè)節(jié)點(diǎn)有數(shù)據(jù)域和指針域datanextm頭ala2a3a4a5a6帶頭節(jié)點(diǎn)L-JinJZELEDJZELEELLHPTala2a3a4a5a6不帶頭節(jié)點(diǎn)L-匚一匚匚I一匚口一匚口一匚口一133PT團(tuán)一口口口口口m單循環(huán)鏈表在P(a3)節(jié)點(diǎn)前插入S節(jié)點(diǎn)(1)Q=P;先讓Q指向a3(2)P

9、=L;/P指向第一個(gè)節(jié)點(diǎn)(帶頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)，不帶頭結(jié)點(diǎn)指向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é)點(diǎn)S 在P(a3)節(jié)點(diǎn)后插入S節(jié)點(diǎn)(1)S-next=P->next;(2)P->next=S; 刪除P(a3)前一個(gè)節(jié)點(diǎn)(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é)點(diǎn)(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)后一個(gè)節(jié)點(diǎn)(1)P->next=P->next->next;讓a3指針域指向a5,從而刪除a4雙鏈表每個(gè)節(jié)點(diǎn)有前驅(qū)指針、數(shù)據(jù)域、后繼指針priordatanext雙循環(huán)鏈表頭a1a2a3a4 在P(a2)節(jié)點(diǎn)前插入S節(jié)點(diǎn)技巧：先讓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;/再把a(bǔ)1->next指向S(4)P->prior=S;/a2->prior指向S 在P(a2)節(jié)點(diǎn)后插入S節(jié)點(diǎn)注：步驟(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)前一個(gè)節(jié)點(diǎn)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的存儲(chǔ)空間 刪除P(a2)節(jié)點(diǎn)(1)P->next->prior=p->prior;(2)P->prior->next=p->next;(3)free(P); 刪除P(a2)后一個(gè)節(jié)點(diǎn)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存儲(chǔ)空間建立(不帶頭節(jié)點(diǎn))單鏈表voidCreateList_l(LinkLi.st&l,intn)/建立不帶頭結(jié)點(diǎn)鏈表LinkListp,q;for(inti=Q;i<n;*+i)p=(LinkList)malloc(sizeoF(LHode);cin»p->(lata；輸入數(shù)據(jù)速p->next=NULL;p當(dāng)前為最后一個(gè)節(jié)點(diǎn)IfCl=

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

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

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

17、it_Stack(BDStacktype&tws,intm)初始化一個(gè)大小為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;/注意此時(shí)的棧滿條件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、字符串模式匹配的簡(jiǎn)單算法；intIndex(SStringS,SStringT,intpos)/算法4.5/返回子串T在主串S中第pos個(gè)字符之后的位置。/若不存在，則函數(shù)值為0。/其中，T非空，1WposWStrLength(S)。inti=pos;intj=1;while(i<=S0&&j<=T0)if(Si=Tj)/繼續(xù)比較后繼字符+i;+j;else/指針后退重新開(kāi)始匹配i=i-j+2;/此時(shí)i為上次開(kāi)始比較位置的下一位j=1;if(j>T0)returni-T0;elsereturn0;/Index2.計(jì)算NEXTnextj:0111232技巧：第一

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

21、儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址1000+(6*7+4)*6=6276基址+(每列的元素個(gè)數(shù)*列數(shù)+當(dāng)前彳T序)*每個(gè)元素所占存儲(chǔ)單元習(xí)題5.2假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)組A9*3*5*8時(shí)，第一個(gè)元素的字節(jié)地址是100,每個(gè)整數(shù)占四個(gè)字節(jié)。問(wèn)下列元素的存儲(chǔ)地址是什么？(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ī)律)壓縮為一維的下標(biāo)計(jì)算；下三角矩陣壓

22、縮為一維數(shù)組(記憶公式)技巧：推薦把公式(2)背下來(lái)(i,j,R范圍都是從0開(kāi)始)，其他根據(jù)范圍變化公式(1)若1<=j,j<=n,0<=R<=n(n+1)/2-1當(dāng)i>=j時(shí)，k=i(i-1)/2+j-1;當(dāng)i<j時(shí)，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時(shí)，k=(i+1)i/2+j;當(dāng)j<j時(shí)，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時(shí)，k=i(i-1)/2+j;當(dāng)i<j時(shí)，k=j(j-1)/2+i;(4)若0<=j,j<=n-1,1<=R<=n(n+1)/2當(dāng)i>=j時(shí)，k=(i+1)i/2+j+1;當(dāng)i<j時(shí)，k=(j+1)j/2+i+1;3 .稀疏矩陣的三元組表示。4.稀疏矩陣應(yīng)用的算法。(略)£)5.10T的三元組裝bxLsta第六章1 .二叉樹(shù)的性質(zhì)；性質(zhì)1：在二叉秋i的第i層上至多有2個(gè)結(jié)點(diǎn)(i/)。性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k>

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

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

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

27、仁）注：原樹(shù)中B為A最左孩子，C,D為B兄弟，變成二叉樹(shù)后C成為B右子樹(shù)，D成為C右子樹(shù)。二叉樹(shù)轉(zhuǎn)化成樹(shù)5 .求哈夫曼樹(shù)和給出編碼、帶權(quán)路徑長(zhǎng)度計(jì)算。習(xí)題6.26假設(shè)用于通信的電文僅由0.07,0.19,0.02,0.06,0.32,0.21,0.10路徑長(zhǎng)度8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，并求帶權(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編碼：樹(shù)的左分支為0,右分支為1。得到哈夫曼編碼為A:1101B:01C:11111D:1110E:10F:11110G:00H:1100帶權(quán)路徑長(zhǎng)度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100=2.61注：該公式為：A路徑長(zhǎng)*A權(quán)+B路徑長(zhǎng)*B權(quán)+H路徑長(zhǎng)*H權(quán)，因?yàn)樵O(shè)的權(quán)值是原來(lái)的100倍，所以結(jié)果除以100。第七章1.鄰接矩陣、鄰接表存儲(chǔ)結(jié)

29、構(gòu)及其特征;圖7.1圖的示例(«)有向圖Gr(b)無(wú)向圖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.求最小生成樹(shù)（Prim、Kruskal）;（a）普里姆（Prim）：以點(diǎn)為基礎(chǔ)從V1開(kāi)始，找到最小邊（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)的最小邊，此時(shí)有（V4,V1）和（V3,V2）,因?yàn)椋╒4,V1）與原來(lái)的邊構(gòu)成圈，所以選擇（V3,V2）。（如果（V4,V1）不與原來(lái)的邊構(gòu)成圈，則二條邊任選一條）；尋找與V1、V3、V6V4、V2相關(guān)聯(lián)，并且不與原來(lái)邊構(gòu)成圈的最小邊，找到（V2,V5）;克魯斯卡爾（Kruskal）（避圈法）：以邊為基礎(chǔ)方法介紹：依次尋找權(quán)最小邊，避免生成一個(gè)圈，所有點(diǎn)聯(lián)通時(shí)生成最小樹(shù)。3 .拓?fù)渑判?；步驟：（1）在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之。（2）從圖

31、中刪除該頂點(diǎn)和所有以它為尾的弧。注：拓?fù)渑判虿晃ㄒ?。、Floyd)。算法求題7.11圖中從頂點(diǎn)a到其他各頂點(diǎn)間的最短路徑，寫(xiě)4 .求最短路徑過(guò)程(Dijkstra迪杰斯特拉(Dijkstra)習(xí)題7.11試?yán)肈ijkstra出執(zhí)行算法過(guò)程中各步狀態(tài)。10求解過(guò)程:終點(diǎn)bcdef£s【終點(diǎn)集)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時(shí)，找a能直接到達(dá)的點(diǎn)，有b,c,d,(a,c)權(quán)最小，(a,c)為a到c最短路徑，將c放如終點(diǎn)集S;K=2時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(guò)(a,c)能到達(dá)的點(diǎn)，(a,c,f)權(quán)最小，(a,c,f)為a到f的最短路徑，將f放入終點(diǎn)集S;K=3時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(guò)(a,c)能到達(dá)的點(diǎn)，或通過(guò)(a,c,f)能到達(dá)的點(diǎn)，(a,c,e)權(quán)最小，(a,c,e)為a到e最短路徑，將e放入終點(diǎn)集S;K=4時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(guò)(a,c)能到達(dá)的點(diǎn)，或通過(guò)(a,c,f)能到達(dá)的點(diǎn)，或通過(guò)(a,c,e)能到達(dá)的點(diǎn)，(a,c,f,d)為a

33、到d最短路徑，將d放入終點(diǎn)集S;K=5時(shí)，找a能直接到達(dá)的點(diǎn)，或通過(guò)(a,c)能到達(dá)的點(diǎn)，或通過(guò)(a,c,f)能到達(dá)的點(diǎn)，或通過(guò)(a,c,e)能到達(dá)的點(diǎn)，或通過(guò)(a,c,f,d)能到達(dá)的點(diǎn)，(a,c,f,d,g)權(quán)最小，為a到g最短路徑，將g放入終點(diǎn)集S;K=6時(shí)，只剩下(a,b),(a,b)為a到b最短路徑，將b放入終點(diǎn)集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中有向圖的各對(duì)頂點(diǎn)間的最爆路徑及其路徑長(zhǎng)度注：D(1)ij是從Vi到Vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑的長(zhǎng)度；D(k)ij是從Vi到Vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度；D(n-1)ij就是從Vi到Vj的最短路徑的長(zhǎng)度。D(-1)欄中，Vi-Vj不允許有轉(zhuǎn)折點(diǎn)。直接填鄰接矩陣。D(0)欄中，Vi-Vj只允許通過(guò)V0轉(zhuǎn)折，或者不轉(zhuǎn)折。通過(guò)V0轉(zhuǎn)折權(quán)值小于原權(quán)值，就把原權(quán)值替換掉。D(1)欄中，Vi-Vj只允許通過(guò)V0、V1轉(zhuǎn)折，或

35、者不轉(zhuǎn)折。如果轉(zhuǎn)折后權(quán)值小于原權(quán)值，替換。D(2)欄中，Vj-Vj允許通過(guò)V0、V1、V2轉(zhuǎn)折，或者不轉(zhuǎn)折，如果轉(zhuǎn)折后權(quán)值小于原權(quán)值，替換。此時(shí)p(2)中就是各點(diǎn)間的最短路徑。如果要找的值大于如果要找的值小于平均查找長(zhǎng)度等概率條件下,ASL=一呼夫mid=(low+high)/2,繼續(xù)比較；,繼續(xù)比較。第九章1 .以下所有查找成功平均查找長(zhǎng)度2 .順序查找；折半查找；順序查找：從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行比較。平均查找長(zhǎng)度等概率時(shí)，平均查找長(zhǎng)度ASL=(n+1)/2不等概率時(shí)，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時(shí)，有近似結(jié)果ASL=Og：(n+1)-13.二叉排序樹(shù)的插入二叉排序樹(shù)建立(建立)、刪除、平衡過(guò)程;(1)若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2)若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；(3)它的左、右子樹(shù)也分別為二叉排序樹(shù)。習(xí)胰9.哨已知如下所示長(zhǎng)度為12的表(Jan*Feb»Mar*Apr,May.June,July.Aug.Sep.Oct,Nov,Dec)<1)試按表中元素的順序依次插入一棵初始為空的二叉排

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

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

39、雙親變化后的(3)插入Nov時(shí)，Jan不平衡。把Jan左轉(zhuǎn)，Mar的左子樹(shù)變成Jan右子樹(shù)。4.最終平衡樹(shù)哈希表構(gòu)造、沖突解決方法；除留余數(shù)法、線性探測(cè)或鏈地址法。構(gòu)造：除留余數(shù)法：H(key)=keyMODp,p<=m沖突解決：，k(k<=m-1)線性探測(cè)法：Hi=(H(key)+曲Modmi=1,2,鏈地址法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。例題：已知一個(gè)線性表(38,25,74,63,52,48),假定采用散列函數(shù)h(key)=key%7計(jì)算散列地址，并散列存儲(chǔ)在散列表A0.6中，采用線性探測(cè)方法解決沖突。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等概率成功查找的平均查找長(zhǎng)度為:地址：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.建鏈地址法處理神突時(shí)的哈爵衰第十章1 .簡(jiǎn)單排序(直接插入、選擇、冒泡)的過(guò)程； 直接插入(略) 選擇排序基本思想：依次在序列中選出最小的記錄Rk,將它與第1個(gè)記錄R1交換。模式：for(i=0;i<10;i+)for(j=i;j<10;j+); 冒泡排序：基本思想：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。模式：for(i=0;i<n;i+)for(j=0;j<n-i-1;j+);2 .先進(jìn)排序(希爾、快速、堆、歸并、基數(shù))過(guò)程；希爾排序：基本思想：先取一個(gè)

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

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

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

45、CKD快速排序O(nloflit)tXn1)0(1。5)堆播序OCnJogn)CXulofn)0(1)歸并排序O(nlogn)。（制。）CKn)基數(shù)排序0(點(diǎn)打+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)系；操作：對(duì)數(shù)據(jù)的加工處理；數(shù)據(jù)結(jié)構(gòu)研究的問(wèn)題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲(chǔ)，如何處理。(字符字符用文字圖形圖象聲音)對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問(wèn)題：數(shù)據(jù)的邏輯結(jié)構(gòu)；邏輯

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

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

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

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

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

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