自考02142《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》串講筆記.docx

1、第一張 概論1.1 引言 兩項(xiàng)基本任務(wù)： 數(shù)據(jù)表示， 數(shù)據(jù)處理 軟件系統(tǒng)生存期：軟件計(jì)劃，需求分析，軟件設(shè)計(jì)，軟件編碼，軟件測試，軟件維護(hù) 由一種邏輯結(jié)構(gòu)和一組基本運(yùn)算構(gòu)成的整體是實(shí)際問題的一種數(shù)學(xué)模型，這種數(shù)學(xué)模型的建立，選擇和實(shí)現(xiàn)是數(shù)據(jù)結(jié)構(gòu)的核心問題。機(jī)外表示-邏輯結(jié)構(gòu)-存儲結(jié)構(gòu)處理要求-基本運(yùn)算和運(yùn)算-算法1.2 數(shù)據(jù)，邏輯結(jié)構(gòu)和運(yùn)算 數(shù)據(jù)：凡是能夠被計(jì)算機(jī)存儲，加工的對象通稱為數(shù)據(jù) 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體加以考慮和處理。 又稱元素，頂點(diǎn)，結(jié)點(diǎn)，記錄。 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素，但通常不具有完整確定的實(shí)際意義，或不被當(dāng)做一個(gè)整體對待。 又稱字段或域，是數(shù)據(jù)不可

2、分割的最小標(biāo)示單位。1.2.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 邏輯關(guān)系：是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式，又稱“鄰接關(guān)系” 邏輯結(jié)構(gòu):數(shù)據(jù)元素之間邏輯關(guān)系的整體稱為邏輯結(jié)構(gòu)。即數(shù)據(jù)的組織形式。 四種基本邏輯結(jié)構(gòu)： 1 集合：任何兩個(gè)結(jié)點(diǎn)間沒有邏輯關(guān)系，組織形式松散 2 線性結(jié)構(gòu)：結(jié)點(diǎn)按邏輯關(guān)系依次排列成一條“鎖鏈” 3 樹形結(jié)構(gòu)：具有分支，層次特性，形態(tài)像自然界中的樹 4. 圖狀結(jié)構(gòu)：各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接。 注意點(diǎn):1. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式，內(nèi)容無關(guān)。2. 邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置無關(guān)3. 邏輯結(jié)構(gòu)與所含結(jié)點(diǎn)個(gè)數(shù)無關(guān)。運(yùn)算：運(yùn)算是指在任何邏輯結(jié)構(gòu)上施加的操作，即對邏輯結(jié)

3、構(gòu)的加工。加工型運(yùn)算：改變了原邏輯結(jié)構(gòu)的“值”，如結(jié)點(diǎn)個(gè)數(shù)，結(jié)點(diǎn)內(nèi)容等。引用型運(yùn)算:不改變原邏輯結(jié)構(gòu)個(gè)數(shù)和值，只從中提取某些信息作為運(yùn)算的結(jié)果。 引用：查找，讀取 加工：插入，刪除，更新同一邏輯結(jié)構(gòu)S上的兩個(gè)運(yùn)算A和B, A的實(shí)現(xiàn)需要或可以利用B，而B的實(shí)現(xiàn)不需要利用A，則稱A可以歸約為B。 假如X是S上的一些運(yùn)算的集合，Y是X的一個(gè)子集，使得X中每一運(yùn)算都可以規(guī)約為Y中的一個(gè)或多個(gè)運(yùn)算，而Y中任何運(yùn)算不可規(guī)約為別的運(yùn)算，則稱Y中運(yùn)算（相對于X）為基本運(yùn)算。 將邏輯結(jié)構(gòu)S和在S上的基本運(yùn)算集X的整體（S,X）稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和處理方式。1.3 存儲實(shí)現(xiàn)和運(yùn)算實(shí)現(xiàn) 由于邏

4、輯結(jié)構(gòu)是設(shè)計(jì)人員根據(jù)解題需要選定的數(shù)據(jù)組織形式，因此存儲實(shí)現(xiàn)建立的機(jī)內(nèi)表示應(yīng)遵循選定的邏輯結(jié)構(gòu)。另一方面，由于邏輯結(jié)構(gòu)不包括結(jié)點(diǎn)內(nèi)容即數(shù)據(jù)元素本身的表示，因此存儲實(shí)現(xiàn)的另一主要內(nèi)容是建立數(shù)據(jù)元素的機(jī)內(nèi)表示。按上述思路建立的數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 存儲結(jié)構(gòu)包括三部分：1 存儲結(jié)點(diǎn)，每個(gè)存儲結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素。2 數(shù)據(jù)元素之間關(guān)聯(lián)方式的表示，也就是邏輯結(jié)構(gòu)的機(jī)內(nèi)表示。3 附加設(shè)施，如方便運(yùn)算實(shí)現(xiàn)而設(shè)置的“啞結(jié)點(diǎn)”等。 四種基本存儲方式：1 順序存儲方式：每個(gè)存儲結(jié)點(diǎn)只含一個(gè)數(shù)據(jù)元素。所有存儲結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲區(qū)里。用存儲結(jié)點(diǎn)間的位置關(guān)系表述數(shù)據(jù)元素之間的邏輯關(guān)系。2 鏈?zhǔn)酱?/p>

5、儲方式：每個(gè)存儲結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針。每個(gè)指針指向一個(gè)與本結(jié)點(diǎn)有邏輯關(guān)系的結(jié)點(diǎn)，即用附加的指針表示邏輯關(guān)系。3 索引存儲方式：每個(gè)存儲結(jié)點(diǎn)只含一個(gè)數(shù)據(jù)元素，所有存儲結(jié)點(diǎn)連續(xù)存放。此外增設(shè)一個(gè)索引表，索引指示各存儲結(jié)點(diǎn)的存儲位置或位置區(qū)間端點(diǎn)。4 散列存儲方式：每個(gè)結(jié)點(diǎn)含一個(gè)數(shù)據(jù)元素，各個(gè)結(jié)點(diǎn)均勻分布在存儲區(qū)里，用散列函數(shù)指示各結(jié)點(diǎn)的存儲位置或位置區(qū)間端點(diǎn)。1.3.2 運(yùn)算實(shí)現(xiàn) 運(yùn)算只描述處理功能，不包括處理步驟和方法；運(yùn)算實(shí)現(xiàn)的核心是處理步驟的規(guī)定，即算法設(shè)計(jì)。 算法：算法規(guī)定了求解給定問題所需的所有處理步驟及其執(zhí)行順序，使得給定類型的任何問題能在有限時(shí)間內(nèi)被機(jī)械的求解。

6、算法分類： 1：運(yùn)行終止的程序可執(zhí)行部分：又稱為程序 2: 偽語言算法：不可以直接在計(jì)算機(jī)上運(yùn)行，但容易編寫和閱讀。 3：非形式算法：用自然語言，同時(shí)可能還使用了程序設(shè)計(jì)語言或偽語言描述的算法。1.4 算法分析 算法質(zhì)量評價(jià)指標(biāo)：1 正確性：能夠正確實(shí)現(xiàn)處理要求2 易讀性：易于閱讀和理解，便于調(diào)試，修改和擴(kuò)充3 健壯性：當(dāng)環(huán)境發(fā)生變化，算法能夠適當(dāng)做出反應(yīng)或處理，不會產(chǎn)生不需要的運(yùn)行結(jié)果4 高效率：達(dá)到所需要的時(shí)空性能。如何確定一個(gè)算法的時(shí)空性能，稱為算法分析一個(gè)算法的時(shí)空性能是指該算法的時(shí)間性能和空間性能，前者是算法包含的計(jì)算量，后者是算法需要的存儲量。算法在給定輸入下的計(jì)算量：1 根據(jù)該問

7、題的特點(diǎn)選擇一種或幾種操作作為“標(biāo)準(zhǔn)操作”。2 確定每個(gè)算法在給定輸入下共執(zhí)行了多少次標(biāo)準(zhǔn)操作，并將此次數(shù)規(guī)定為該算法在給定輸入下的計(jì)算量。若無特殊說明，將默認(rèn)以賦值語句作為標(biāo)準(zhǔn)操作。最壞情況時(shí)間復(fù)雜性：算法在所有輸入下的計(jì)算量的最大值作為算法的計(jì)算量平均時(shí)間復(fù)雜性：算法在所有輸入下的計(jì)算量的加權(quán)平均值作為算法的計(jì)算量。算法的輸入規(guī)模（問題規(guī)模）是指作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)。 常見時(shí)間復(fù)雜性量級：1 常數(shù)階：O（1） 即算法的時(shí)間復(fù)雜性與輸入規(guī)模N無關(guān)或N恒為常數(shù)。2 對數(shù)階：Olog2 N 3 線性階：O(N) 4 平方階：O（N2）5 指數(shù)階：O（2

8、N次方）通常認(rèn)為指數(shù)階量級的算法實(shí)際是不可計(jì)算的，而量級低于平方階的算法是高效率的第二章 線性表2.1 線性表的基本概念 線性結(jié)構(gòu)：線性結(jié)構(gòu)是N（N大于等于0）個(gè)結(jié)點(diǎn)的有窮序列。 A I 稱為Ai+1的直接前趨，A i+1稱為Ai 的直接后繼。為滿足運(yùn)算的封閉性，通常允許一種邏輯結(jié)構(gòu)出現(xiàn)不含任何結(jié)點(diǎn)的情況。不含任何結(jié)點(diǎn)的線性結(jié)構(gòu)記為（）或 線性結(jié)構(gòu)的基本特征：若至少含有一個(gè)結(jié)點(diǎn)，則除起始節(jié)點(diǎn)沒有直接前趨外，其他結(jié)點(diǎn)有且只有一個(gè)直接前趨，除終端結(jié)點(diǎn)沒有直接后繼外，其他結(jié)點(diǎn)有且只有一個(gè)直接后繼。2.1.2 線性表線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。所含結(jié)點(diǎn)個(gè)數(shù)稱為線性表的長度（表長）。表長為0的是空表。線

9、性表的基本運(yùn)算：1 初始化 initiate （L）： 加工型運(yùn)算，其作用是建立一個(gè)空表L= 。2 求表長 length （L）：引用型運(yùn)算，其結(jié)果是線性表L的長度。3 讀表元 get （L，i）：引用型運(yùn)算。若1小于等于i小于等于length（L），其結(jié)果是L的第i個(gè)結(jié)點(diǎn)，否則為一特殊值。4 定位（按值查找）locate（L，X）：引用型運(yùn)算。若L中存在一個(gè)或多個(gè)值與X相等，結(jié)果為這些結(jié)點(diǎn)的序號最小值，否則，運(yùn)算結(jié)果為0。5 插入 insert (L,X，i)：加工型運(yùn)算。在L的第i個(gè)位置上增加一個(gè)值為X的新結(jié)點(diǎn)，參數(shù)i的合法取值范圍是1-L+1。6 刪除 delete （L，i）：加工型運(yùn)

10、算。撤銷L的第i個(gè)結(jié)點(diǎn)ai, i的合法取值范圍是1-N。2.2 線性表的順序?qū)崿F(xiàn)2.2.1 順序表 順序表是線性表的順序存儲結(jié)構(gòu)，即按順序存儲方式構(gòu)造的存儲結(jié)構(gòu)。 順序表基本思想：順序表的一個(gè)存儲結(jié)點(diǎn)存儲線性表的一個(gè)結(jié)點(diǎn)的內(nèi)容，即數(shù)據(jù)元素（不含其他信息），所有存儲結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列。 順序表的特點(diǎn)：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰。 順序表的類C語言描述：p17 Const maxsize=順序表的容量 Typedef struct datatype date maxsize Int last; sqlist;Sqlist L;L表示線性表的長度，last-

11、1 是終端結(jié)點(diǎn)在順序表中的位置。常數(shù)maxsize為順序表的容量。表長L.last , 終端結(jié)點(diǎn) L.dataL.last-12.2.2 基本運(yùn)算在順序表上的實(shí)現(xiàn) 1 插入Void inset_sqlist (sqlist L,datatype x, int i) if (L.last = maxsize) error(表滿); /*溢出*/If (iL.last+1) error (非法位置);For (j=L.last ; j=I; j-) L.dataj = L.data j-1; /*依次后移*/ L.datai-1 = x; /*置入*/ L.last =L.last+1 /*修改表

12、長*/ 2. 刪除Void delete_sqlist ( sqlist L, int I ) /*刪除順序表L中第i個(gè)位置上的結(jié)點(diǎn)*/ If ( ( iL.last) error (非法位置);For ( j= i+1; j= L.last; j+) L.data j-2 = L.data j-1 ; /*依次前移，注意第一個(gè)L.dataj-2存放ai*/ L.last=L.last-1 /*修改表長*/3 定位Int locate_sqlist (sqlist L , datatype X) /*在順序表中從前往后查找第一個(gè)值等于X的結(jié)點(diǎn)。若找到則回傳該結(jié)點(diǎn)序號，否則回傳0*/ I=1 ;

13、While ( ( i= L.last) & (L.datai-1!=x) ) /*注意：ai在L.datai-1中*/ i+; /*從前往后查找*/if (i next = NULL; return(t); 此算法說明的問題：1 語句 t = malloc(size); 有雙重作用：1 由malloc自動(dòng)生成一個(gè)類型為node的新結(jié)點(diǎn)。2指針型變量t得到一個(gè)值即指針，該指針指向上述新結(jié)點(diǎn)。2 要生成新結(jié)點(diǎn)必須通過調(diào)用malloc才能實(shí)現(xiàn)。3 語句t - next=NULL的作用是將頭結(jié)點(diǎn)*t的鏈域置為NULL。4 為了建立一個(gè)空表，可定義一個(gè)lklist類型的變量head,并通過調(diào)用head

14、 =initiate_lklist( )使head成為指向一個(gè)空表的頭指針。2 求表長 Int length_lklist(lklist head) /*求表head的長度，P是pointer類型的變量*/ p=head; J=0; While (p -next!=NULL) p=p-next; J+; Return (j ); 3 按序號查找 Pointer find_lklist ( lklist head ,int I ) /*在單鏈表head中查找第i個(gè)結(jié)點(diǎn)。若找到則回傳指向該結(jié)點(diǎn)的指針，否則回傳null*/ p= head; j=0; While ( p-next !=NULL)&(

15、 jnext; j+; If (i=j) return (p); Else return(NULL); 4 定位 Int locate_lklist ( lklist head, datatype x) p=head ; j= 0;While ( (p-next!=NULL)&(p-data!=x) p= p-next; j+; If p-data =x return(j); Else return (0); 5刪除 Void delete_lklist ( lklist head, int i) p= find_lklist (head,i-1); /*調(diào)用按序號查找算法*/If (p!=N

16、ULL)&(p-next!=NULL)q=p-next;p-next = q-next;free (q); else error(不存在第i個(gè)結(jié)點(diǎn)) free是庫函數(shù)，結(jié)果是釋放q所指結(jié)點(diǎn)占用的內(nèi)存空間，同時(shí)q的值變成無定義。6 插入 Void insert_lklist( lklist head,datatyped x ,int i) P=find_lklist (head, i-1);If ( p=NULL)Error (不存在第i個(gè)位置) Else s= malloc (size); s-data= x; s-next=p-next; p-next =s; 2.5 其他鏈表 循環(huán)鏈表尾結(jié)

17、點(diǎn)的鏈域值不是NULL,而是指向頭結(jié)點(diǎn)的指針。優(yōu)點(diǎn)是從任一結(jié)點(diǎn)出發(fā)都能通過后移操作而掃描整個(gè)循環(huán)鏈表。但為找到尾結(jié)點(diǎn)，必須從頭指針出發(fā)掃描表中所有結(jié)點(diǎn)。改進(jìn)的方法是不設(shè)頭指針而改設(shè)尾指針。這樣，頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的位置為：rear-next-next 和rear.雙鏈表：在每個(gè)結(jié)點(diǎn)中增加一個(gè)指針域，所含指針指向前趨結(jié)點(diǎn)。 雙鏈表的摘除*P的操作：p-prior-next=p-next; p-next-prior=p-prior; 鏈入操作：P后面鏈入*q: q-prior=p; q-next=p-next; p-next-prior=q; p-next =q; 2.6順序?qū)崿F(xiàn)與鏈接實(shí)現(xiàn)的比較 空間

18、性能的比較：存儲結(jié)點(diǎn)中數(shù)據(jù)域占用的存儲量與整個(gè)存儲結(jié)點(diǎn)占用存儲量之比稱為存儲密度。順序表=1，鏈表top=0; Return(1); 2. 進(jìn)棧 Int push(sqstackTp *sq, datatype x) if (s-top = sqstack_maxsize-1) error(“棧滿”);return 0;Elsesq-top+; Sq-datasq-top=x; Return(1); 3 退棧Int pop(sqstackTp *sq,datatype *x) if (sq-top=0) error(“下溢”);return(0);Else *x=sq-datasq-top;S

19、q-top-;Return(1); 4 判?？?Int emptystack(stackTp *sq)if sq-top=0 Return(1);Else return(0); 5 取棧頂元素Int gettop( sqstackTp *sq, datatype *x)if(sq-top=0) return(0);Else*x =sq-datasq-top;Return(1); 3.1.3棧的鏈接實(shí)現(xiàn) 鏈棧由棧頂指針ls唯一確定。棧中其他結(jié)點(diǎn)通過他們的next域鏈接起來。棧底結(jié)點(diǎn)的next域?yàn)镹ULL。因?yàn)殒湕１旧頉]有容量限制，所以不會出現(xiàn)棧滿情況。 31.5 棧的簡單應(yīng)用和遞歸棧與函數(shù)調(diào)用:

20、 函數(shù)調(diào)用時(shí)，先保存的位置后返回，后保存的位置先返回。所以每遇到一個(gè)函數(shù)調(diào)用便立刻將相應(yīng)的返回位置進(jìn)棧，調(diào)用結(jié)束時(shí)，棧頂元素正好是此函數(shù)的返回位置。遞歸與棧： 滿足遞歸的條件：1 被定義項(xiàng)在定義中的應(yīng)用具有更小的尺度。2 被定義項(xiàng)在最小尺度上的定義不是遞歸的。3.2 隊(duì)列 隊(duì)列也可以看成一種受限的線性表，插入限定在表的某一端進(jìn)行（隊(duì)尾），刪除限定在另一端進(jìn)行（隊(duì)頭） 隊(duì)列又稱先進(jìn)先出線性表。 隊(duì)列的基本運(yùn)算：1 隊(duì)列初始化initQueue(Q) 加工型運(yùn)算，設(shè)置一個(gè)空隊(duì)列Q2 入隊(duì)列enQueue(Q,X)加工型運(yùn)算，將X插入到隊(duì)列Q的隊(duì)尾。若原隊(duì)列為空，則X為原隊(duì)尾結(jié)點(diǎn)的后繼，同時(shí)是新隊(duì)列

21、的隊(duì)尾結(jié)點(diǎn)。3 出隊(duì) outQueue(Q,X)加工型運(yùn)算，若隊(duì)列Q不空，則將隊(duì)頭元素賦給X,并刪除隊(duì)頭結(jié)點(diǎn)，其后繼成為新的隊(duì)頭結(jié)點(diǎn)。4 判隊(duì)列空 emptyQueue(Q) 引用型運(yùn)算，若隊(duì)列Q為空，則返回1，否則為05 讀隊(duì)頭gethead(Q,x)引用型運(yùn)算，Q不空時(shí)由參數(shù)X返回隊(duì)頭結(jié)點(diǎn)的值，否則給一特殊標(biāo)志。隊(duì)列的順序?qū)崿F(xiàn)： 隊(duì)列的順序?qū)崿F(xiàn)由一個(gè)一維數(shù)組及兩個(gè)分別指示隊(duì)頭和隊(duì)尾的變量組成，稱為隊(duì)頭指針和隊(duì)尾指針。約定隊(duì)尾指針指示隊(duì)尾元素在一維數(shù)組中的當(dāng)前位置，隊(duì)頭指針指示隊(duì)頭元素在一維數(shù)組中的當(dāng)前位置的前一個(gè)位置。 如果按sq.rear=sq.rear+1; sq.datasq.rea

22、r=x和sq.front=sq.front+1分別進(jìn)行入隊(duì)和出隊(duì)操作，則會造成“假溢出?！毖h(huán)隊(duì)列的入隊(duì)操作：sq.rear=(sq.rear+1)%maxsize; sq.datasq.rear=x 出隊(duì)操作：sq.front=(sq.front+1)%maxsize;判斷循環(huán)隊(duì)列隊(duì)滿的條件：(sq.rear+1)%maxsize)=sq.front 隊(duì)空的條件：sq.rear=sq.front3.3 數(shù)組二維數(shù)組可以看成是一個(gè)被推廣的線性表，這種線性表的每一個(gè)數(shù)據(jù)元素本身也是一個(gè)線性表。數(shù)組只有兩種基本運(yùn)算：1 讀：給定一組下標(biāo)，讀取相應(yīng)的數(shù)據(jù)元素2 寫：給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素?cái)?shù)

23、組元素的存儲位置是下標(biāo)的線性函數(shù)，計(jì)算存儲位置所需的時(shí)間取決于乘法的時(shí)間，因此，存取任一元素的時(shí)間相等。通常將具有這一特點(diǎn)的存儲結(jié)構(gòu)成為隨機(jī)存儲結(jié)構(gòu)。3.3.3矩陣的壓縮存儲 壓縮存儲的基本思想：值相同的多個(gè)元素只分配一個(gè)存儲空間，零元素不分配空間。 要壓縮的矩陣分為兩種1 特殊矩陣：對稱矩陣，三角矩陣。值相同的元素或零元素的分布有一定規(guī)律叫特殊矩陣。 對稱矩陣通常存儲下三角，n階方陣需要n*(n+1)/2個(gè)存儲單元 三角矩陣需要n*(n+1)/2+1個(gè)存儲單元，最后一個(gè)單元存儲相同的常數(shù)。2 稀疏矩陣：零元素遠(yuǎn)多于非零元素，且非零元素的分布沒有規(guī)律。用三元組表存儲稀疏矩陣，只存儲非零元素。(

24、I,j,aij)第四章 樹4.1 樹的基本概念 樹的定義： 樹是n(n0)個(gè)結(jié)點(diǎn)的有窮集合，滿足：1 有且僅有一個(gè)稱為根的結(jié)點(diǎn)。2 其余結(jié)點(diǎn)分為m(m=)個(gè)互不相交的非空集合，這些集合中每一個(gè)都是一棵樹，稱為根的子樹。 有關(guān)術(shù)語： 樹上任一結(jié)點(diǎn)所擁有的子樹的數(shù)目稱為該結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。度大于0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支點(diǎn)。一棵樹中所有結(jié)點(diǎn)度的最大值稱為該樹的度。 若結(jié)點(diǎn)A是B的直接前趨，則稱A是B的雙親或父節(jié)點(diǎn)，稱B為A的孩子或子節(jié)點(diǎn)。父節(jié)點(diǎn)相同的結(jié)點(diǎn)互稱為兄弟。 一棵樹的任何結(jié)點(diǎn)（不包括根節(jié)點(diǎn)）稱為根的子孫，根節(jié)點(diǎn)稱為其他節(jié)點(diǎn)的祖先。 結(jié)點(diǎn)的層數(shù)（或深度）從根開始算，

25、根的層數(shù)為1，其他節(jié)點(diǎn)的層數(shù)為其雙親的層數(shù)加1。樹中結(jié)點(diǎn)層數(shù)的最大值稱為該樹的高度或深度。 樹的基本運(yùn)算：1 求根 ROOT(T) 引用型運(yùn)算，結(jié)果是樹T的根結(jié)點(diǎn)。2 求雙親 PARENT (T,X) 引用型運(yùn)算，結(jié)果是結(jié)點(diǎn)X在樹T上的雙親，若X是樹T的根或X不在T上，則結(jié)果為一特殊標(biāo)志。3 求孩子CHILD(T,X,I) 引用型運(yùn)算，結(jié)果是樹T上結(jié)點(diǎn)X的第i個(gè)孩子，若X不在T上或X沒有第i個(gè)孩子，結(jié)果為一特殊標(biāo)志。4 建樹 CREATE (X,T1.，TK) ，K=1，加工型運(yùn)算，建立一棵以X為根，以T1.TK為第1K課子樹的樹。5 剪枝DELETE（T,X,i）加工型運(yùn)算，刪除樹T上結(jié)點(diǎn)X

26、的第i棵子樹，若T無第i棵子樹，則操作為空。4.2 二叉樹 二叉樹是節(jié)點(diǎn)的有窮集合，它或者是空集，或者同時(shí)滿足下述兩個(gè)條件：1 有且僅有一個(gè)稱為根的結(jié)點(diǎn)。2 其余結(jié)點(diǎn)分為兩個(gè)互不相交的集合T1,T2，都是二叉樹，并且T1,T2有順序關(guān)系，T1在T2之前，他們分別稱為根的左子樹和右子樹。二叉樹的五種形態(tài)： 空二叉樹，只含根的二叉樹， 只有非空左子樹的二叉樹，只有非空右子樹的二叉樹，同時(shí)有非空左右子樹的二叉樹。二叉樹的基本運(yùn)算：1 初始化INITIATE(BT) 加工型運(yùn)算，作用是設(shè)置一棵空二叉樹2 求根ROOT(BT)引用型運(yùn)算，結(jié)果是二叉樹BT的根節(jié)點(diǎn)，若BT為空二叉樹，結(jié)果為一特殊標(biāo)志。3

27、求雙親PARENT(BT,X) 引用型運(yùn)算，結(jié)果是結(jié)點(diǎn)X在二叉樹BT上的雙親，若X是根或不在BT上，結(jié)果為一特殊標(biāo)志4 求左孩子LCHILD(BT,X)右孩子RCHILD(BT,X)引用型運(yùn)算，結(jié)果分別為結(jié)點(diǎn)X在BT上的左，右孩子。若X為BT的葉子或X不在BT上，結(jié)果為一特殊標(biāo)志。5 建樹CREAT(X,LBT,RBT)加工型運(yùn)算，建立一棵X為結(jié)點(diǎn)，LBT,RBT為左右子樹的二叉樹。6 剪枝DELETEFT(BT,X)和DELETEHT(BT,X)加工型運(yùn)算，刪除BT結(jié)點(diǎn)X的左右子樹，若無，運(yùn)算為空。 二叉樹的性質(zhì)：1 二叉樹第i(i=1)層上至多有2i-1個(gè)結(jié)點(diǎn)。2 深度為K（k=1）的二叉

28、樹至多有2k -1個(gè)結(jié)點(diǎn)。3 對任何二叉樹，若2度結(jié)點(diǎn)數(shù)為n2,則葉子數(shù)n=n2+1 深度為K（K=1）且有2k-1結(jié)點(diǎn)的二叉樹為滿二叉樹，在第K層刪去最右邊連續(xù)J個(gè)結(jié)點(diǎn)，得到一棵深度為K的完全二叉樹。 完全二叉樹的性質(zhì)：|_x|表示不大于X的最大整數(shù)。1 具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為|_log2n|+12 將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹按層編號，則對任一編號為i的結(jié)點(diǎn)X有： 若i=1，則結(jié)點(diǎn)X是根，若i1，則X的雙親parent（X）的編號為|_i/2| 若2in,則結(jié)點(diǎn)X無左孩子（且無右孩子），否則，X的左孩子LCHILD(X)的編號為2i. 若2i+1n,則結(jié)點(diǎn)X無右孩子，否則,X的右

29、孩子RCHILD(X)的編號為2i+14.3 二叉樹的存儲結(jié)構(gòu) 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)： 二叉鏈表在做求雙親運(yùn)算時(shí)效率不高，此時(shí)可采用三叉鏈表。 具有n個(gè)結(jié)點(diǎn)的二叉樹中，一共有2n個(gè)指針域，其中只有n-1個(gè)用來指向結(jié)點(diǎn)的左右孩子，其余的n+1個(gè)指針域?yàn)镹ULL.P814.3.2二叉樹的順序存儲結(jié)構(gòu) 按層編號然后存儲。 對于非完全二叉樹，可采用增加虛結(jié)點(diǎn)的方式轉(zhuǎn)化成完全二叉樹再進(jìn)行存儲。虛結(jié)點(diǎn)在數(shù)組中用特殊記號表示。但同時(shí)會浪費(fèi)存儲空間。4.4. 二叉樹的遍歷 遍歷一棵二叉樹就是按某種次序系統(tǒng)地“訪問”二叉樹上所有結(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)恰好被訪問一次。 先根遍歷：1 訪問根結(jié)點(diǎn) 2 先根遍歷左子樹 3先

30、根遍歷右子樹 中根遍歷：1中根遍歷左子樹 2 訪問根結(jié)點(diǎn) 3中根遍歷右子樹 后根遍歷：1后根遍歷左子樹 2后根遍歷右子樹 3訪問根結(jié)點(diǎn)。4.6 樹和林樹的存儲結(jié)構(gòu)：P931 孩子鏈表示方法：頭結(jié)點(diǎn)分為數(shù)據(jù)域和指針域，表結(jié)點(diǎn)分為孩子域和指針域 可以在頭結(jié)點(diǎn)中增加雙親域，稱為帶雙親的孩子鏈表示方法。2 孩子兄弟鏈表示法：存儲結(jié)點(diǎn)均含三個(gè)域：數(shù)據(jù)域，孩子域（存放指向本結(jié)點(diǎn)第一個(gè)孩子的指針），兄弟域（存放指向本結(jié)點(diǎn)下一個(gè)兄弟的指針）。3 雙親表示法：數(shù)據(jù)域，指針域（指示本結(jié)點(diǎn)的雙親所在的存儲結(jié)點(diǎn)）將指針域定義為高級語言中的指針類型的鏈?zhǔn)酱鎯Y(jié)構(gòu)成為“動(dòng)態(tài)鏈表”，相應(yīng)的指針成為動(dòng)態(tài)指針。將指針域定義為整

31、形，子界型的鏈?zhǔn)酱鎯Y(jié)構(gòu)成為靜態(tài)鏈表，相應(yīng)的指針稱為靜態(tài)指針。動(dòng)態(tài)鏈表的結(jié)構(gòu)通過庫函數(shù)malloc（size）動(dòng)態(tài)生成，無需事先規(guī)定表的容量。而靜態(tài)鏈表容量須事先說明。4.6.2樹的遍歷 1 先根遍歷：若樹非空1 訪問根結(jié)點(diǎn) 2依次先根遍歷根的各個(gè)子樹 2 后根遍歷： 1 依次后根遍歷根的各個(gè)子樹2 訪問根結(jié)點(diǎn) 3 層次遍歷： 2 訪問根結(jié)點(diǎn) 2從左到右，從上到下依次訪問每層。二叉樹與樹，林的關(guān)系 P97 將二叉樹的二叉鏈表和數(shù)的孩子兄弟鏈表的左孩子指針，右孩子指針和孩子指針，兄弟指針對應(yīng)起來。 與樹對應(yīng)的二叉樹的右子樹一定為空。判定樹和哈夫曼樹 用于描述分類過程的二叉樹稱為判定樹。判定樹的每

32、個(gè)非終端結(jié)點(diǎn)包含一個(gè)條件，因而對應(yīng)于一次比較火判斷，每個(gè)終端結(jié)點(diǎn)包含一個(gè)種類標(biāo)記，對應(yīng)于一種分類結(jié)果。 哈夫曼樹： 給定一組值p1pK，如何構(gòu)造一棵有k個(gè)葉子且分別以這些值為權(quán)的判定樹，使得其平均比較次數(shù)最小。滿足上述條件的判定樹稱為哈夫曼樹。第五章 圖圖中的小圓圈稱為頂點(diǎn)，連線稱為邊，連線附帶的數(shù)值稱為邊的權(quán)。任何兩點(diǎn)間相關(guān)聯(lián)的無向圖稱為無向完全圖，一個(gè)N個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為n(n-1)/2.任何兩頂點(diǎn)間都有弧的有向圖稱為有向完全圖。一個(gè)N個(gè)頂點(diǎn)的有向完全圖弧數(shù)位n(n-1)每條邊或弧都帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)。一個(gè)連通圖的生成樹，是含有該連通圖的全部頂點(diǎn)的一個(gè)極小聯(lián)通子圖。若連通圖的頂

33、點(diǎn)個(gè)數(shù)位N,則生成樹的邊數(shù)為N-1,如果它的一個(gè)子圖的邊數(shù)大于N-1,則其中一定有環(huán)，如果小于，則一定不連通。5.2 圖的存儲結(jié)構(gòu) 鄰接矩陣 對于無向圖，頂點(diǎn)VI的度是矩陣中第I行（或列）的元素之和。 對于有向圖，行元素之和為出度，列元素之和為入度。鄰接表 為每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中每個(gè)結(jié)點(diǎn)稱為表結(jié)點(diǎn)，包括兩個(gè)域，鄰接點(diǎn)域，用以存放與VI相鄰接的頂點(diǎn)序號，鏈域，用以指向同VI鄰接的下一個(gè)的頂點(diǎn)。 另外，每個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。每個(gè)表頭結(jié)點(diǎn)有兩個(gè)域，一個(gè)存放頂點(diǎn)VI的信息，另一個(gè)指向鄰接表中的第一個(gè)結(jié)點(diǎn)。 若一個(gè)無向圖有N個(gè)頂點(diǎn)，E條變，則它的鄰接表需要N個(gè)頭結(jié)點(diǎn)和2E個(gè)表結(jié)點(diǎn)，所以在

34、邊稀疏的情況下，用鄰接表比鄰接矩陣更節(jié)省存儲空間。對于無向圖，第I個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)即為VI的度。對于有向圖，第I個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是VI的出度，為求入度，必須遍歷整個(gè)鄰接表，所有單鏈表中，鄰接點(diǎn)域的值為I的結(jié)點(diǎn)個(gè)數(shù)即為入度。 有時(shí)為了方便 的求入度，可以建立逆鄰接表。5.3 圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，每個(gè)頂點(diǎn)僅訪問一次，叫做圖的遍歷。增設(shè)visitedn數(shù)組。初值為0,vi被訪問后，置為1遍歷方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。最小生成樹問題拓?fù)渑判虻诹?查找表 集合的特點(diǎn)：在集合這種邏輯結(jié)構(gòu)中，任何結(jié)點(diǎn)間都不存在邏輯關(guān)系。用來標(biāo)識數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)稱為關(guān)鍵字，簡稱鍵，

35、該數(shù)據(jù)項(xiàng)的值稱為鍵值。靜態(tài)查找表：以集合為邏輯結(jié)構(gòu)，包括三種基本運(yùn)算1 建表 CREATE(ST) 加工型運(yùn)算，生成一個(gè)由用戶給定的若干數(shù)據(jù)元素組成的靜態(tài)查找表ST.2 查找 SEARCH(ST,K)引用型運(yùn)算，若ST中存在鍵值等于K，結(jié)果為該鍵在ST中的位置，否則為一特殊標(biāo)志3 讀表元GET(ST,pos)引用型運(yùn)算，結(jié)果是pos位置上的數(shù)據(jù)元素。動(dòng)態(tài)查找表：包括查找，讀表元（同上）和以下三種基本運(yùn)算。1 插入INSERT(ST,K)加工型運(yùn)算，若ST中不存在鍵值等于K的數(shù)據(jù)元素，則將一個(gè)鍵值等于K的數(shù)據(jù)元素插入到ST中。2 刪除DELETE(ST,K)加工型運(yùn)算，刪除ST中鍵值等于K的數(shù)據(jù)元素。3 初始化INITIATE(ST)加工型運(yùn)算，設(shè)置一個(gè)空 的動(dòng)態(tài)查找表。62 靜態(tài)查找表的實(shí)現(xiàn) 6.2.1順序表上的查找 順序查找法：從表的第n個(gè)位置開始，從后往前依次將各個(gè)位置上的數(shù)據(jù)元素的鍵值與給定值K比較。若相等，回送該位置作為結(jié)果。若不等，查找不成功。 在第0個(gè)單元設(shè)置哨崗，所有當(dāng)查找不成功時(shí)