最新數(shù)據(jù)結(jié)構(gòu)推薦書(shū)目 數(shù)據(jù)結(jié)構(gòu)筆記整理(四篇)

在日常學(xué)習(xí)、工作或生活中，大家總少不了接觸作文或者范文吧，通過(guò)文章可以把我們那些零零散散的思想，聚集在一塊。大家想知道怎么樣才能寫(xiě)一篇比較優(yōu)質(zhì)的范文嗎？這里我整理了一些優(yōu)秀的范文，希望對(duì)大家有所幫助，下面我們就來(lái)了解一下吧。

數(shù)據(jù)結(jié)構(gòu)推薦書(shū)目 數(shù)據(jù)結(jié)構(gòu)筆記整理篇一

數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)的組織形式，也可看成是包含數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)表，說(shuō)明數(shù)據(jù)之間存在著一定的相互關(guān)系或約束。數(shù)據(jù)結(jié)構(gòu)被形式地定義為(d,r),其中d是數(shù)據(jù)元素的有限集合,r是d上的關(guān)系有限集合.數(shù)據(jù)類(lèi)型：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱；數(shù)據(jù)運(yùn)算：對(duì)數(shù)據(jù)施加的一種操作；數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型兩個(gè)概念之間區(qū)別：簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類(lèi)型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。

邏輯結(jié)構(gòu)：我們把只表現(xiàn)元素之間邏輯關(guān)系，而不涉及它們?cè)谟?jì)算機(jī)中的表示，只是理論的、反映在紙面上的東西，這種抽象的數(shù)據(jù)結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。

物理結(jié)構(gòu)：抽象的數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的表示，也就是映射在存儲(chǔ)空間上的、具體的數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)表示，也就是映射在存儲(chǔ)空間上的、具體的數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱；數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。

數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

數(shù)據(jù)結(jié)構(gòu)：是相互之間一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)（線性結(jié)構(gòu)，如線性表，棧，隊(duì)，串，數(shù)組 和非線性結(jié)構(gòu)如 樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)）、物理（存儲(chǔ)）結(jié)構(gòu)（集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)）和數(shù)據(jù)運(yùn)算如插入、刪除、修改、排序、查找。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的數(shù)據(jù)叫邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

四大類(lèi)存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。順序存儲(chǔ)包括數(shù)據(jù)存儲(chǔ)（把邏輯上相鄰的元素存儲(chǔ)在地址連續(xù)的存儲(chǔ)單位）和數(shù)據(jù)關(guān)系存儲(chǔ)（通過(guò)連續(xù)的物理地址體現(xiàn)關(guān)系）；鏈?zhǔn)酱鎯?chǔ)包括數(shù)據(jù)存儲(chǔ)（把邏輯上相鄰的元素存放在物理地址隨意的存儲(chǔ)單元）和數(shù)據(jù)關(guān)系存儲(chǔ)（不僅存放數(shù)據(jù)本身還存放數(shù)據(jù)元素的物理地址）

抽象數(shù)據(jù)類(lèi)型adt：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作，包括_數(shù)據(jù)和操作_兩個(gè)部分 算法的特性：有窮性（執(zhí)行有窮步結(jié)束）、確定性（確切含義，不會(huì)產(chǎn)生二義性）、可行性、輸入（零個(gè)或多個(gè)輸入）和輸出（一個(gè)或多個(gè)輸出）

算法設(shè)計(jì)的要求：正確性、可讀寫(xiě)、健壯性、效率與低存儲(chǔ)量需求。

2、數(shù)據(jù)的邏輯結(jié)構(gòu)是指圖形結(jié)構(gòu)_三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)_。數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)４種。

17_稱為存儲(chǔ)結(jié)構(gòu).1821、算法的執(zhí)行時(shí)間是

371、某算法的時(shí)間復(fù)雜度為o(n2),表明該算法的_____.2.算法分析的目的是問(wèn)題規(guī)模之間的關(guān)系;算法分析的兩個(gè)主要方面是空間復(fù)雜度和時(shí)間復(fù)雜度

5．在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮

a.各結(jié)點(diǎn)的值如何b.結(jié)點(diǎn)個(gè)數(shù)的多少c.對(duì)數(shù)據(jù)有哪些運(yùn)算d.編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。

10．程序段i ＝ 0；while（i<=n）｛i = i * 3

12數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類(lèi)型要一致 1.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的系和運(yùn)算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)式相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。10.數(shù)據(jù)的運(yùn)算最常用的有5-1-

第二章 線性表

1.線性表:一個(gè)線性表是n個(gè)類(lèi)型相同的數(shù)據(jù)元素的有限序列。線性表的順序表示：用一組地址連

續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：優(yōu)，可隨機(jī)存取表中任一元素，方便快捷；缺，再插入或刪除時(shí)，需移動(dòng)大量元素，數(shù)組的靜態(tài)空間分配。

2.線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一的，非線性結(jié)構(gòu)反

映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。

3.從一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較個(gè)結(jié)點(diǎn),4.在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入*s結(jié)點(diǎn)，則執(zhí)行 5.對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的，刪除一個(gè)

元素時(shí)大約要移動(dòng)表中的(n-1)/2兩種情況下求平均個(gè)元素。

6.設(shè)單鏈表中指針p指著結(jié)點(diǎn)m，指針f指著將要插入的新結(jié)點(diǎn)x，當(dāng)x插在鏈表中最后一個(gè)結(jié)點(diǎn)

m之后時(shí)，只要先修改后修改p->link=f即可。

7.在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素(1<=i<=n)時(shí)，需要從前向后依次前移i個(gè)元素前插入元素需移動(dòng)

存儲(chǔ)結(jié)構(gòu)需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表

9、在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時(shí)需修改指針

1.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是12.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用_結(jié)點(diǎn)的雙循環(huán)鏈表__存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間；某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插

入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用_僅有尾指針的單循環(huán)鏈表存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間；對(duì)

于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲(chǔ)結(jié)構(gòu)為用尾指針表示的循環(huán)單鏈表

14.15.16.17、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 帶頭結(jié)點(diǎn)的~是

19、帶頭結(jié)點(diǎn)的雙循環(huán)表l為空表的條件是。

20、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足21.在一個(gè)長(zhǎng)度為n(n>1)操作與鏈表的長(zhǎng)度有關(guān)；與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活

23線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)鏈接指針決定的。

24、從順序表中刪除第i個(gè)元素時(shí)，首先把第i個(gè)元素賦給_針開(kāi)始向后的所有元素均前移一個(gè)位置，最后使線性表的長(zhǎng)度減1。

25,26、循環(huán)單鏈表l為空的條件是

27、在以ｈｌ為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為。

28、在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為，若p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)的a[p].next。

29、在由數(shù)組a中元素結(jié)點(diǎn)構(gòu)成的單鏈表中，在下標(biāo)為i的結(jié)點(diǎn)的后面插入一個(gè)下標(biāo)為j的結(jié)點(diǎn)

時(shí)，需要進(jìn)行的操作為a[j].next=a[i].next和a[i].next=j語(yǔ)句。

第三章 棧和隊(duì)列

1.棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧又稱為先進(jìn)后出lifo的線性表。

2.判定一個(gè)棧st（最多元素為m0）為空的條件是

2.棧的兩種存儲(chǔ)方法：一是順序棧，即棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存

放自棧底到棧頂?shù)脑?；二是棧的鏈?zhǔn)奖硎尽?/p>

3.隊(duì)列：隊(duì)列是一種先進(jìn)先出fifo的線性表。允許插入的一端叫做隊(duì)尾rear，允許刪除的一段則

稱為隊(duì)頭front

4.鏈隊(duì)的出隊(duì)入隊(duì)操作：s入隊(duì),rear->next=s;rear=s;p出隊(duì)：front->next=p->next

5.順序隊(duì)：插入元素：front不變，rear加1；刪除元素：rear不變，front加1。判定一個(gè)順序棧

st(最多元素為maxsize)為空的條件是6.循環(huán)隊(duì)列:空隊(duì)滿隊(duì)都是rea=r=front為區(qū)分,規(guī)定循環(huán)隊(duì)列中剩一個(gè)元素即為滿隊(duì),front=rear+1

7.8.9.向一個(gè)棧項(xiàng)指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，則執(zhí)行。

10.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則進(jìn)行插入*s結(jié)點(diǎn)的操作時(shí)

應(yīng)執(zhí)行rear->next=s;rear=s;

11.若己知一個(gè)棧的進(jìn)棧序列是1,2,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi(1

23、判定一個(gè)環(huán)形隊(duì)列qu(最多元素為maxsize)為空的條件是是(qu->rear+1)%maxsize==qu->front

列的元素個(gè)數(shù)是(rear-front+maxsize)%maxsize。

24.從一個(gè)不帶頭結(jié)點(diǎn)的棧頂指針為1st的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x保存被刪結(jié)點(diǎn)的值,則執(zhí)行5.棧頂指針

7.在鏈表qu中,判定只有一個(gè)結(jié)點(diǎn)的條件是設(shè)有一個(gè)順序棧s,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個(gè)元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1,則順序棧的容量至少應(yīng)為3。

9.設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用數(shù)據(jù)結(jié)構(gòu)最佳

例：設(shè)有編號(hào)為1，2，3，4的四輛列車(chē)，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車(chē)站，具體寫(xiě)出這四輛

列車(chē)開(kāi)出車(chē)站的所有可能的順序。

答：至少有14種①全進(jìn)之后再出情況,只有1種：4，3，2，1②進(jìn)3個(gè)之后再出的情況，有

3種，3,4,2,13,2,4,13,2,1,4③進(jìn)2個(gè)之后再出的情況,有5種，2,4,3,12,3,4,12,1, 3,4

2,1,4,32,1,3,4④進(jìn)1個(gè)之后再出的情況,有5種，1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,3

第四章 串

1.串：由零個(gè)或多個(gè)字符組成的有限序列；串中字符的數(shù)目n稱為串的長(zhǎng)度，零個(gè)字符的串稱為

空串。包含子串的串相應(yīng)的稱為主串，通常稱字符在序列中的序號(hào)為該字符在串中的位置。

2．空串是，其長(zhǎng)度等于度等于其包含的空格個(gè)數(shù)。組成串的數(shù)據(jù)元素只能是 單個(gè)字符。

4．一個(gè)字符串中稱為該串的子串。

5.若串s= ‘software’,其子串的數(shù)目是字符串長(zhǎng)度為n的字串的個(gè)數(shù)計(jì)算公式 :[n+(n-1)+...+ 1+1]）

60．串是一種特殊的線性表，其特殊性體現(xiàn)在61．設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為 串：1。kmp算法，求next函數(shù)值等。時(shí)間：o(n+m)。其中，模式匹配為o（n）；預(yù)處理為

o（m）；求兩串的最長(zhǎng)公共子串，時(shí)間為o（n）是不行的，至少要o（n2）。

第五章 數(shù)組（線性結(jié)構(gòu)，元素受限，操作不限）和廣義表

1.矩陣的壓縮存儲(chǔ)：是指為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間，對(duì)零元不分配空間。

2.樹(shù)的存儲(chǔ)結(jié)構(gòu)：

一、雙親表示法：就是用一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)

一個(gè)指示器指示其雙親的結(jié)點(diǎn)在數(shù)組中位置。特點(diǎn)：找雙親容易，找孩子難；

二、孩子兄弟表示

法（又稱二叉樹(shù)和二叉鏈表表示法）鏈表結(jié)構(gòu)中的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的的第一個(gè)孩子結(jié)點(diǎn)

和下一個(gè)兄弟結(jié)點(diǎn)。操作容易，破壞了樹(shù)的層次

第六章 樹(shù)和二叉樹(shù)

1.樹(shù)：樹(shù)是由n個(gè)類(lèi)型相同的元素構(gòu)成的有限集。

2.二叉樹(shù)的性質(zhì)：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)；深度為k的二叉樹(shù)最多有2k-1個(gè)結(jié)點(diǎn)；

葉子結(jié)點(diǎn)比度為2的結(jié)點(diǎn)個(gè)數(shù)多1。

3.遍歷二叉樹(shù)：先序遍歷（根左右）、中序遍歷（左根右）、后序遍歷（左右根）。前后序遍歷確定

跟，中序遍歷確定左右子樹(shù)，依次判斷，方法是：由前序先確定root，由中序可確定root的左、右子樹(shù)。然后由其左子樹(shù)的元素集合和右子樹(shù)的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼

續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定.第七章圖

一、圖的定義和術(shù)語(yǔ)：

1、圖(graph)——圖g是由兩個(gè)集合v(g)和e(g)組成的,記為g=(v,e)

其中：v(g)是頂點(diǎn)的非空有限集 e(g)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)?/p>

2、有向圖—有向圖g是由兩個(gè)集合v(g)和e(g)組成的其中：v(g)是頂點(diǎn)的非空有限集e(g)是有

向邊（也稱?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記?p>，v,w是頂點(diǎn)，v為弧尾，w為弧頭

e(g)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（v,w）或（w,v），并且（v,w）=(w,v)

4、n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1)； n個(gè)頂點(diǎn)的無(wú)向圖最大邊數(shù)是n(n-1)/26、權(quán)——與圖的邊或弧相關(guān)的數(shù)叫~；簡(jiǎn)單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫~

14、簡(jiǎn)單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫~

16、連通圖——圖中任意兩個(gè)頂點(diǎn)都是連通的叫~；連通分量——非連通圖的每一個(gè)連通部分叫~

18、強(qiáng)連通圖——有向圖中，如果對(duì)每一對(duì)vi,vj?v, vi1vj,從vi到vj 和從vj到 vi都存在路徑

1、深度優(yōu)先搜索----從圖的某一頂點(diǎn)v0出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從v0的未被訪問(wèn)的鄰接點(diǎn)

出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和v0相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被

訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止

深度遍歷：v1-> v2->v4-> v8->v5->v3->v6->v72、廣度優(yōu)先遍歷(bfs)——方法：從圖的某一頂點(diǎn)v0出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)v0的各個(gè)

未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖 中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作

起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止

第九章 查找

1.靜態(tài)查找——拆半查找：確定待查記錄所在的范圍，然后逐步縮小范圍知道找到或找不到該記

錄為止。假設(shè)low和high分別為待查元素所在范圍的上下界，指針mid指示區(qū)域中間的位置，mid=[low+high]/2.此處low和high分別為位置而非數(shù)值。比較時(shí)與mid做比較，比mid大，low=mid+1，反之high=mid-1，mid重新計(jì)算。查找成功或失敗最多比較關(guān)鍵字個(gè)數(shù)不超過(guò)[log2n]+1

例：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它

將依次與表中20，70，30，50 比較大小，查找結(jié)果是失敗。

2.靜態(tài)查找——順序查找：從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，相等則查找成功，反之失敗。平均查找長(zhǎng)度：asl=(n+1)/2

3.二叉排列樹(shù)：或是一棵空樹(shù)；或者是具有以下性質(zhì)的二叉樹(shù)：1.若它的左子樹(shù)不空，則左子樹(shù)

上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的的值；2.若它的右子樹(shù)不空，則右子樹(shù)上所有借點(diǎn)得知均大

于它的根節(jié)點(diǎn)的值；3.它的左右子樹(shù)上也分別為二叉排列樹(shù)。

數(shù)據(jù)結(jié)構(gòu)推薦書(shū)目 數(shù)據(jù)結(jié)構(gòu)筆記整理篇二

“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)

計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)從1994年開(kāi)始為我校?？粕_(kāi)設(shè)“數(shù)據(jù)結(jié)構(gòu)”課程，2004年開(kāi)始為本科生開(kāi)設(shè)這門(mén)課程。由于本門(mén)課程的教學(xué)從教材、講授、實(shí)驗(yàn)指導(dǎo)都體現(xiàn)了先進(jìn)的教育理念，該課程的教學(xué)體系科學(xué)、完整，教學(xué)手段與方法先進(jìn)，課程特色鮮明，2006年被評(píng)為赤峰學(xué)院本科層次精品課。幾年來(lái)，數(shù)據(jù)結(jié)構(gòu)課題組成員從以下幾個(gè)方面對(duì)本門(mén)課程進(jìn)行了建設(shè)和改革。

一、課程建設(shè)指導(dǎo)思想、定位和特色 1．學(xué)科地位

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門(mén)學(xué)科基礎(chǔ)課，是本專業(yè)和相關(guān)專業(yè)必修課。本課程的教學(xué)目標(biāo)是培養(yǎng)學(xué)生通過(guò)理解、分析和研究計(jì)算機(jī)處理的數(shù)據(jù)對(duì)象的特性，從而選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法，并熟練掌握算法的時(shí)間分析和空間分析技巧?！皵?shù)據(jù)結(jié)構(gòu)”還是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)部分專業(yè)課的先導(dǎo)課，如“數(shù)據(jù)庫(kù)原理與應(yīng)用”、“計(jì)算機(jī)操作系統(tǒng)”、“計(jì)算機(jī)編譯原理”和“面向?qū)ο蟮某绦蛟O(shè)計(jì)”等。所以本課程的教學(xué)效果將直接影響到學(xué)生對(duì)其它后續(xù)專業(yè)課的學(xué)習(xí)，因此，該課程在專業(yè)建設(shè)的地位十分重要。

“數(shù)據(jù)結(jié)構(gòu)”是一門(mén)應(yīng)用性很強(qiáng)的課程，本課程要求學(xué)生在掌握各種數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)和有關(guān)算法的基礎(chǔ)上，通過(guò)大量的上機(jī)實(shí)例把難以理解的、抽象的概念轉(zhuǎn)化為計(jì)算機(jī)能夠正確運(yùn)行的程序，從而提高學(xué)生運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力。2．課程特色

根據(jù)課程建設(shè)的規(guī)劃和我系實(shí)際，我們針對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)開(kāi)展討論，并就實(shí)驗(yàn)、圖書(shū)資料等方面進(jìn)行建設(shè)。在不斷的教學(xué)實(shí)踐中，我們按照精品課建設(shè)要求，積極探索，積累了豐富的教學(xué)經(jīng)驗(yàn)。

采用國(guó)內(nèi)經(jīng)典教材，結(jié)合前沿的研究領(lǐng)域和最新科研動(dòng)態(tài)，豐富教學(xué)內(nèi)容，讓學(xué)生了解數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用價(jià)值。

采用課堂教學(xué)與大作業(yè)相結(jié)合，上機(jī)實(shí)踐為補(bǔ)充的教學(xué)模式，培養(yǎng)學(xué)生的創(chuàng)業(yè)創(chuàng)新素質(zhì)和團(tuán)隊(duì)協(xié)作精神。

二、教師隊(duì)伍建設(shè)

1．良好的學(xué)緣結(jié)構(gòu)

任課教師的業(yè)務(wù)水平和教學(xué)水平是影響課程建設(shè)質(zhì)量的重要因素。為此，我們不斷加強(qiáng)師資隊(duì)伍建設(shè)，特別注重青年教師和實(shí)驗(yàn)指導(dǎo)教師的培養(yǎng)。在擔(dān)任該課程教學(xué)任務(wù)的5名教師中，教授1名、副教授2名、講師2名，學(xué)歷結(jié)構(gòu)為碩士4人、學(xué)士1人，45歲以下3人，35歲以下2人。本教師梯隊(duì)學(xué)歷層次較高，職稱、年齡結(jié)構(gòu)合理，便于本門(mén)課程的建設(shè)和發(fā)展。

2．加強(qiáng)學(xué)術(shù)交流，不斷提高團(tuán)隊(duì)整體教學(xué)和科研水平

在教學(xué)過(guò)程中，我們采取了互相聽(tīng)課，舉行公開(kāi)課、觀摩課等方式，經(jīng)常交流教書(shū)育人和教學(xué)改革方面的經(jīng)驗(yàn)，不斷提高任課教師的教學(xué)水平和學(xué)術(shù)水平。

以范體貴教授為學(xué)科帶頭人的教學(xué)研究梯隊(duì)，具有豐富的教學(xué)經(jīng)驗(yàn)和高昂的教學(xué)熱情，同時(shí)具備較高的教學(xué)研究和科學(xué)研究水平。教學(xué)梯隊(duì)成員在搞好教學(xué)的同時(shí)，積極申報(bào)承擔(dān)各級(jí)各類(lèi)教學(xué)研究和科學(xué)研究課題，并參加國(guó)內(nèi)外相關(guān)學(xué)科的科研、教學(xué)等方面的學(xué)術(shù)交流活動(dòng)。選派范體貴、門(mén)愛(ài)華兩位老師參加全國(guó)計(jì)算機(jī)年會(huì)和全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議，與國(guó)內(nèi)其他高校著名學(xué)者進(jìn)行了教學(xué)、科研等方面的交流，學(xué)到許多寶貴的經(jīng)驗(yàn)和方法。

注重與其他高校的合作和交流，學(xué)習(xí)其他院校好的教學(xué)經(jīng)驗(yàn)和方法。選派主講教師門(mén)愛(ài)華老師到清華大學(xué)計(jì)算機(jī)系做訪問(wèn)學(xué)者，訪學(xué)期間門(mén)老師聽(tīng)取了本課程的講授，經(jīng)常與講授本門(mén)課程的資深教授嚴(yán)蔚敏老師、殷仁昆老師進(jìn)行交流、學(xué)習(xí)。二位老師都給予了具體的指導(dǎo)和建議，為我校本門(mén)課程的改革和發(fā)展提供了有利的幫助。請(qǐng)國(guó)內(nèi)著名高校學(xué)者來(lái)我系講學(xué)傳授經(jīng)驗(yàn)，在教學(xué)、科研等方面給予具體的指導(dǎo)。2008年10月清華大學(xué)著名數(shù)據(jù)庫(kù)專家馮建華教授來(lái)我系講學(xué)，課題組成員與馮教授進(jìn)行了深入的交流，在教學(xué)和科研方面都有很大的收獲。

3．開(kāi)展科學(xué)研究，積極申請(qǐng)科研立項(xiàng)

數(shù)據(jù)結(jié)構(gòu)課題小組成員積極進(jìn)行相關(guān)領(lǐng)域的科學(xué)研究，幾年來(lái)發(fā)表相關(guān)論文30余篇，承擔(dān)自治區(qū)級(jí)科研項(xiàng)目四個(gè)，赤峰市科技局科研項(xiàng)目一個(gè)，院級(jí)項(xiàng)目一個(gè)，其中3個(gè)項(xiàng)目已經(jīng)完成并通過(guò)驗(yàn)收。目前在研的一個(gè)科研項(xiàng)目是與清華大學(xué)合作申請(qǐng)的計(jì)算機(jī)前沿領(lǐng)域研究課題，相信通過(guò)該項(xiàng)目的研究和合作，對(duì)我系的科研工作會(huì)起到極大的促進(jìn)作用，同時(shí)能夠使我系科研水平上一個(gè)新的臺(tái)階。課題組成員經(jīng)過(guò)幾年的努力，在各方面都取得了一些成績(jī)。范體貴、門(mén)愛(ài)華、張國(guó)祥、王玉紅四位教師分別獲得“赤峰學(xué)院課堂教學(xué)質(zhì)量?jī)?yōu)秀獎(jiǎng)”，范體貴、門(mén)愛(ài)華兩位教師多次獲得“赤峰學(xué)院科研成果優(yōu)秀獎(jiǎng)”的獎(jiǎng)勵(lì)。王玉紅老師獲得“畢業(yè)實(shí)習(xí)優(yōu)秀指導(dǎo)教師“稱號(hào)，門(mén)愛(ài)華老師2007年、2008年連續(xù)獲得“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎(jiǎng)勵(lì)。

建立了良好的人才培養(yǎng)制度，在學(xué)校和系里的大力支持下，鼓勵(lì)現(xiàn)有教師提高學(xué)歷與引進(jìn)高學(xué)歷教師相結(jié)合，經(jīng)過(guò)幾年的建設(shè)，已經(jīng)形成了一支以中青年為主的學(xué)科梯隊(duì)。積極鼓勵(lì)中青年教師到國(guó)內(nèi)名校進(jìn)修或攻讀碩士、博士學(xué)位，門(mén)愛(ài)華、董潔、王玉紅分別考取了東北大學(xué)和遼寧工程技術(shù)大學(xué)的碩士研究生，已圓滿完成學(xué)業(yè)并獲得碩士學(xué)位。

三、教學(xué)內(nèi)容、教材建設(shè)

1．理論環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時(shí)分配

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)課程體系中核心課程之首，作為學(xué)科的專業(yè)基礎(chǔ)課，具有承上啟下的重要作用。對(duì)應(yīng)于學(xué)科中問(wèn)題求解的理論、抽象和設(shè)計(jì)的方法論，本課程內(nèi)容體系結(jié)構(gòu)分為概念表述、構(gòu)建數(shù)據(jù)模型、設(shè)計(jì)算法三個(gè)層面，突出數(shù)據(jù)組織方法與處理技術(shù)，貫穿程序設(shè)計(jì)和軟件工程新思想和新觀點(diǎn)。理論學(xué)時(shí)設(shè)置為72學(xué)時(shí)。

2.實(shí)踐環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時(shí)分配

上機(jī)實(shí)踐和課程設(shè)計(jì)重在培養(yǎng)學(xué)生軟件設(shè)計(jì)的綜合能力。在基本的課程實(shí)習(xí)基礎(chǔ)上,自2001年起開(kāi)設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，使課程的實(shí)踐環(huán)節(jié)總學(xué)時(shí)數(shù)增加到60學(xué)時(shí)。提出了課程設(shè)計(jì)的規(guī)范要求，突出關(guān)鍵技術(shù)要點(diǎn)，貫穿基本技能訓(xùn)練主線，加強(qiáng)實(shí)踐能力培養(yǎng)。

通過(guò)課程設(shè)計(jì)的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，提高了學(xué)生組織數(shù)據(jù)與進(jìn)行編寫(xiě)大型程序能力，使學(xué)生更好地理解和掌握了算法設(shè)計(jì)所需的技術(shù)，為專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。課程設(shè)計(jì)題目（動(dòng)態(tài)更新、完善）：航空客運(yùn)訂票系統(tǒng)；電梯模擬；簡(jiǎn)單行編輯程序；工資管理系統(tǒng)；醫(yī)院排隊(duì)看病活動(dòng)的模擬；學(xué)籍管理系統(tǒng)；圖書(shū)管理系統(tǒng)等。3．教材建設(shè)

教材建設(shè)是課程建設(shè)的重要環(huán)節(jié)。為此，根據(jù)教學(xué)大綱和本課程的發(fā)展需要，在本課程教材的選用上注重教材的先進(jìn)性和科學(xué)性，我們選用了清華大學(xué)出版社嚴(yán)蔚敏教授等編寫(xiě)的《數(shù)據(jù)結(jié)構(gòu)》（c語(yǔ)言版）作為教材，本書(shū)內(nèi)容豐富、體系結(jié)構(gòu)嚴(yán)謹(jǐn)、概念清晰、易學(xué)易懂，也是多所院校指定的考研參考教材，完全適合我系計(jì)算機(jī)科學(xué)與技術(shù)、信息與計(jì)算科學(xué)專業(yè)學(xué)生的需要。任課教師則多方面參考相關(guān)教材，選擇部分編寫(xiě)精彩的內(nèi)容充實(shí)到教案中。任課教師們廣泛閱讀相關(guān)文獻(xiàn)，了解該領(lǐng)域前沿知識(shí)，并且在授課過(guò)程中介紹給學(xué)生，以開(kāi)闊學(xué)生的視野，拓寬學(xué)生的知識(shí)面。同時(shí)，根據(jù)教材內(nèi)容和實(shí)際教學(xué)要求，編寫(xiě)了《數(shù)據(jù)結(jié)構(gòu)上機(jī)指導(dǎo)與習(xí)題就解答》，并正式出版了《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程》一書(shū)，該書(shū)作為自治區(qū)教育廳統(tǒng)編教材已在各高校廣泛使用。

四、教學(xué)方法和教學(xué)手段

1．教學(xué)方法

在教學(xué)方法上，講課、討論和專題講座等多種形式并用，以科學(xué)、生動(dòng)靈活的講授方式傳授知識(shí)，培養(yǎng)學(xué)生的創(chuàng)造思維。教師在認(rèn)真組織課堂講授，注意各環(huán)節(jié)正常運(yùn)行的同時(shí)，還針對(duì)不同的教學(xué)內(nèi)容采取不同的方法進(jìn)行講解，做到課程內(nèi)容既條理清晰、深入淺出，又重點(diǎn)突出、特色鮮明。教學(xué)內(nèi)容靈活，既有必講的內(nèi)容，也有針對(duì)不同專業(yè)需要和特點(diǎn)選講的內(nèi)容。

通過(guò)布置適量的課后習(xí)題，使學(xué)生能夠進(jìn)一步鞏固和提高對(duì)課上所學(xué)知識(shí)的領(lǐng)悟和應(yīng)用能力。我們?cè)谶x擇習(xí)題時(shí)，一方面注重三基（基本理論，基本方法，基本技能）知識(shí)的掌握，另一方面也充分考慮知識(shí)的靈活應(yīng)用，使學(xué)生能多角度、多方法地解決問(wèn)題，既鍛煉他們的系統(tǒng)性思維，又提高分析解決問(wèn)題的能力。每?jī)芍馨才乓淮瘟?xí)題課，由指導(dǎo)教師集中解決同學(xué)課上課下遇到的問(wèn)題。

上機(jī)實(shí)踐是學(xué)生對(duì)本門(mén)課程所學(xué)知識(shí)的一種全面、綜合的能力訓(xùn)練，是與課堂聽(tīng)講、自學(xué)和練習(xí)相輔相成必不可少的一個(gè)教學(xué)環(huán)節(jié)，也是對(duì)課堂教學(xué)效果的一種檢驗(yàn)。通常，實(shí)習(xí)題中的問(wèn)題比平時(shí)的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)題注重原理與應(yīng)用的結(jié)合，目的讓學(xué)生學(xué)會(huì)如何把書(shū)上學(xué)到的知識(shí)運(yùn)用于解決實(shí)際問(wèn)題的過(guò)程中去，培養(yǎng)從事軟件開(kāi)發(fā)設(shè)計(jì)工作所必需的基本技能。同時(shí)，通過(guò)實(shí)踐能使書(shū)上的知識(shí)變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的作用。平時(shí)的練習(xí)較偏重于如何編寫(xiě)功能單一的“小”算法，而實(shí)習(xí)題是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問(wèn)題分析，總體結(jié)構(gòu)設(shè)計(jì)，用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧，可以多人合作，有利于一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，實(shí)踐環(huán)節(jié)中有很重要的一點(diǎn)，就是機(jī)器是比任何教師都嚴(yán)格的主考官。

2．教學(xué)手段

為了適應(yīng)現(xiàn)代化教學(xué)的需求，我們?cè)趥鹘y(tǒng)教學(xué)的基礎(chǔ)上，充分利用現(xiàn)代科學(xué)技術(shù)，廣泛應(yīng)用多媒體教學(xué)課件和教學(xué)軟件。將授課內(nèi)容制作成了圖文并茂的多媒體課件，利用多媒體技術(shù)對(duì)數(shù)據(jù)結(jié)構(gòu)輔之以形象的動(dòng)畫(huà)，動(dòng)態(tài)演示抽象的復(fù)雜數(shù)據(jù)結(jié)構(gòu)的變化，用板書(shū)補(bǔ)充某些推導(dǎo)過(guò)程并完成和學(xué)生互動(dòng)的內(nèi)容，改變了以前課堂教學(xué)單調(diào)的弊病，激發(fā)了學(xué)生的學(xué)習(xí)興趣。使用多媒體技術(shù)還可以直接在課堂上演示算法的實(shí)現(xiàn)過(guò)程，讓學(xué)生熟悉算法實(shí)現(xiàn)的環(huán)境和方法，增強(qiáng)了該門(mén)課的實(shí)踐性，提高了課堂授課效率和教學(xué)質(zhì)量，取得了滿意的教學(xué)效果。教師們?yōu)榱烁玫剡m應(yīng)社會(huì)的發(fā)展和改革的需要，本著強(qiáng)化算法的思想，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)內(nèi)容的基礎(chǔ)上，補(bǔ)充了新的算法，拓寬了學(xué)生的知識(shí)面。

五、課程建設(shè)取得的成果

1．教學(xué)科研論文

1）the boundary element analysis for the thermal conduction of the thermal equipment。proceedings of international conference on computational physics, rinton press, us,(2005)199-202（sci）

2）基于訪問(wèn)控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究。計(jì)算機(jī)與網(wǎng)絡(luò) 24,(2004)52-53(核刊)3）信息系統(tǒng)在企業(yè)現(xiàn)代化管理中的應(yīng)用?！渡虉?chǎng)現(xiàn)代化（學(xué)術(shù)版）》，2005.2 25-26(核刊)4）可信網(wǎng)絡(luò)基本概念與基本屬性研究?！冻喾鍖W(xué)院學(xué)報(bào) 》2007.5 5）基于包過(guò)濾技術(shù)路由器防火墻在網(wǎng)絡(luò)安全中的研究?！队?jì)算機(jī)應(yīng)用研究》,2007,vol23 6）research on the architecture of tru-network。2008 international symposium on information science and engineering 7）路由器防火墻對(duì)沖擊波、震蕩波病毒的過(guò)濾研究?！冻喾鍖W(xué)院學(xué)報(bào)》 2005.1 67-68 8）菲涅耳圓孔衍射的數(shù)值模擬?！冻喾鍖W(xué)院學(xué)報(bào)》 2006.1 9）復(fù)雜軸承流體動(dòng)力學(xué)特性的邊界元分析。《潤(rùn)滑與密封》 2006.3(核刊 ei核心刊源)10）三葉軸承流體動(dòng)力學(xué)特性的邊界元分析。《潤(rùn)滑與密封》 2006.5(核刊 ei核心刊源)11）164-182hf核的低能譜和電磁躍遷的相互作用玻色子模型?！陡吣芪锢砼c核物理》 28(12),(2004)119-122(核刊, sci收錄)12）基于訪問(wèn)控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究?！队?jì)算機(jī)與網(wǎng)絡(luò)》 2004.24 13）赤峰學(xué)院校園網(wǎng)路由器、交換機(jī)的選型及遠(yuǎn)程登錄?！冻喾褰逃龑W(xué)院學(xué)報(bào)》2004.5 81-82 14）《xml數(shù)據(jù)庫(kù)存儲(chǔ)策略綜述》 《計(jì)算機(jī)科學(xué)》 2005年9月（核刊）15）《xml數(shù)據(jù)庫(kù)結(jié)構(gòu)連接算法之研究》《計(jì)算機(jī)科學(xué)》 2007年6月（核刊）16）《xml中xpath包含關(guān)系判定算法》《內(nèi)蒙古大學(xué)學(xué)報(bào)》2008年10月（核刊）17）《基于關(guān)系數(shù)據(jù)庫(kù)的xml數(shù)據(jù)的存儲(chǔ)研究》《赤峰學(xué)院學(xué)報(bào)》 2006年 3 月 18）《xml數(shù)據(jù)庫(kù)模式匹配算法研究》 《赤峰學(xué)院學(xué)報(bào)》 2007年 5月 19）《internet蠕蟲(chóng)的分析與研究》 《赤峰學(xué)院學(xué)報(bào)》 2005年 4月 20）《如何防止外部網(wǎng)絡(luò)的攻擊》 《赤峰學(xué)院學(xué)報(bào)》 2004年2月 21）《射頻ic卡消費(fèi)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)》 《赤峰學(xué)院學(xué)報(bào)》 2008年10月 22）《xpath片斷的分析與研究》 《赤峰學(xué)院學(xué)報(bào)》 2008年1月 23）《一種基于層次結(jié)構(gòu)的xml編碼技術(shù)》 中國(guó)教育信息化》 2009年4月（核刊）24）《vc++實(shí)現(xiàn)圖形、數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)的思路》赤峰教育學(xué)院學(xué)報(bào) 2002年第2月 25）《基于ip組播的多媒體會(huì)議系統(tǒng)的設(shè)計(jì)》 赤峰教育學(xué)院學(xué)報(bào) 2002年6月 26）論文《個(gè)性化windows系統(tǒng)“開(kāi)始”菜單》赤峰教育學(xué)院學(xué)報(bào) 2003年4月 27）淺談debug程序的主要命令用法 赤峰學(xué)院學(xué)報(bào) 2007年5月 28）powerpoint技巧在課件制作中的妙用 赤峰學(xué)院學(xué)報(bào) 2006年1月 29）淺談?dòng)胢asm運(yùn)行匯編程序 赤峰學(xué)院學(xué)報(bào) 2005年 1月 30）xml數(shù)字簽名淺析 赤峰學(xué)院學(xué)報(bào) 2008年 5月 31）《網(wǎng)絡(luò)層的靜態(tài)路由選擇綜述》 赤峰學(xué)院學(xué)報(bào) 2005年3月 32）《離散數(shù)學(xué)在計(jì)算機(jī)教學(xué)中的作業(yè)》 赤峰學(xué)院學(xué)報(bào) 2008年1月 33）《基于模擬退火算法的油井工礦數(shù)據(jù)挖掘的應(yīng)用研究》

赤峰學(xué)院學(xué)報(bào)2009年1月

2.教研課題

1）赤峰學(xué)院校園網(wǎng)項(xiàng)目 赤峰學(xué)院 2002年-2003年（已驗(yàn)收）2）基于ip網(wǎng)qos動(dòng)態(tài)控制研究 內(nèi)蒙教育廳 2005年-2007年（已結(jié)題）3）基于結(jié)構(gòu)索引xml模式匹配方法研究 內(nèi)蒙教育廳 2005年—2007年（已結(jié)題）4）xml數(shù)據(jù)庫(kù)研究 赤峰學(xué)院 2006年—2008年（已結(jié)題）5）cai系統(tǒng)中知識(shí)個(gè)性化組織與導(dǎo)航研究 內(nèi)蒙教育廳 2003年-2005年（已結(jié)題）6）xml安全數(shù)據(jù)發(fā)布關(guān)鍵問(wèn)題研究 內(nèi)蒙教育廳 2009年—2010年（在研）3.教學(xué)獲獎(jiǎng)

1）范體貴、門(mén)愛(ài)華、張國(guó)祥、王玉紅分別獲赤峰學(xué)院2005、2006年、2007年、2008年“課堂教學(xué)質(zhì)量?jī)?yōu)秀獎(jiǎng)”；

2）門(mén)愛(ài)華2007年、2008年連續(xù)獲的“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎(jiǎng)勵(lì)； 3）王玉紅2007年獲院級(jí)“畢業(yè)實(shí)習(xí)優(yōu)秀實(shí)習(xí)指導(dǎo)教師”獎(jiǎng)勵(lì)；

4）2009年《數(shù)據(jù)結(jié)構(gòu)課程教學(xué)和實(shí)踐》課題”獲赤峰學(xué)院“優(yōu)秀教學(xué)成果二等獎(jiǎng)”。

數(shù)據(jù)結(jié)構(gòu)課程組 2009年5月14日

數(shù)據(jù)結(jié)構(gòu)推薦書(shū)目 數(shù)據(jù)結(jié)構(gòu)筆記整理篇三

數(shù)據(jù)結(jié)構(gòu)與算法課程論文綜述

摘要

如何合理的組織數(shù)據(jù)、高效率的處理數(shù)據(jù)是擴(kuò)大計(jì)算機(jī)應(yīng)用領(lǐng)域、提高軟件效率的關(guān)鍵。在軟件開(kāi)發(fā)過(guò)程中要求“高效地”組織數(shù)據(jù)和設(shè)計(jì)出“好的”算法，并使算法用程序來(lái)實(shí)現(xiàn)，通過(guò)調(diào)試而成為軟件，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計(jì)領(lǐng)域的專門(mén)知識(shí)。

《數(shù)據(jù)結(jié)構(gòu)與算法》課程就是主要學(xué)習(xí)在軟件開(kāi)發(fā)中涉及的各種常用數(shù)據(jù)結(jié)構(gòu)及其常用算法，在此基礎(chǔ)上，學(xué)習(xí)如何利用數(shù)據(jù)結(jié)構(gòu)和算法解決一些基本的應(yīng)用問(wèn)題。

課程主要內(nèi)容

本學(xué)期一共學(xué)習(xí)了十章的內(nèi)容，下面就這十章的內(nèi)容作了詳細(xì)的介紹。第一章：數(shù)據(jù)結(jié)構(gòu)與算法概述

本章主要是對(duì)數(shù)據(jù)、數(shù)據(jù)類(lèi)型、數(shù)據(jù)結(jié)構(gòu)、算法及算法分析等基本概念的掌握，而如何合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)正是擴(kuò)大計(jì)算機(jī)領(lǐng)域、提高軟件效率的關(guān)鍵，所以對(duì)這些概念的理解就顯得十分重要。

數(shù)據(jù)是指描述客觀事物的數(shù)值、字符、相關(guān)符號(hào)等所有能夠輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱，其基本單位是數(shù)據(jù)元素，而數(shù)據(jù)類(lèi)型是一個(gè)同類(lèi)值的集合和定義在這個(gè)值集上的一組操作的總稱。在高級(jí)程序語(yǔ)言中定義一種數(shù)據(jù)類(lèi)型時(shí)，編譯程序編譯系統(tǒng)就能獲得如下信息：（1）、一組性質(zhì)相同的值的集合；（2）、一個(gè)預(yù)訂的存儲(chǔ)體系；（3）、定義在這個(gè)值集合上的一組操作。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系，它包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、一組運(yùn)算集合；數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)方法有：順序存儲(chǔ)方法、鏈接存儲(chǔ)方法、索引存儲(chǔ)方法和散列存儲(chǔ)方法。接下來(lái)便是關(guān)于算法的有關(guān)概念，算法是為解決一個(gè)特定問(wèn)題而采取的確定的有限步驟集合，它具有有窮性、確定性、可行性、輸入和輸出。關(guān)于算法的性能分析，分為時(shí)間性能分析和空間性能分析。第二章：順序表及其應(yīng)用

本章主要是對(duì)順序表、順序表的結(jié)構(gòu)、數(shù)據(jù)類(lèi)型、基本算法及相關(guān)應(yīng)用的介紹。順序表是一種簡(jiǎn)單而常用的數(shù)據(jù)結(jié)構(gòu)，其應(yīng)用范圍較為廣泛，包括查找問(wèn)題、排序問(wèn)題、字符處理問(wèn)題等內(nèi)容。第三章：鏈表及其應(yīng)用

鏈表是一種簡(jiǎn)單、常用的數(shù)據(jù)結(jié)構(gòu)，與順序表相比，具有插入、刪除結(jié)點(diǎn)不需要移動(dòng)元素，不必事先估計(jì)存儲(chǔ)空間大小等優(yōu)點(diǎn)，操作較為靈活。它有六種基本運(yùn)算：（1）、置空表（2）、求表長(zhǎng)（3)、按序號(hào)取元素（4）、按值查找

(5)、插入（6）、刪除。

單鏈表即鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，用來(lái)存儲(chǔ)其直接后繼的存儲(chǔ)位置。但是這樣就使得對(duì)結(jié)點(diǎn)前面的元素的操作很困難，所以就在每個(gè)結(jié)點(diǎn)增加一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域，從而構(gòu)成雙向鏈表。同時(shí)由于每個(gè)結(jié)點(diǎn)的地址既存放在其前驅(qū)結(jié)點(diǎn)的后繼指針中，又存放在其后繼結(jié)點(diǎn)的前驅(qū)指針域中，所以雙向鏈表的插入操作分為前插和后插。第四章：堆棧及其應(yīng)用

首先要明白棧是一種受限制的線性結(jié)構(gòu)，遵守“先進(jìn)后出”的規(guī)則，其插入與刪除操作都在棧頂進(jìn)行。

其次根據(jù)順序存儲(chǔ)和鏈接存儲(chǔ)，棧分為順序棧和鏈棧。其中順序棧棧是用地址連續(xù)的存儲(chǔ)空間依次存儲(chǔ)棧中數(shù)據(jù)元素，并記錄當(dāng)前棧頂數(shù)據(jù)元素的位置；基本算法包括置空棧、判?？铡⑴袟M、取棧頂元素、入棧和出棧。而鏈棧則使用鏈?zhǔn)酱鎯?chǔ)堆棧的數(shù)據(jù)元素，并記錄當(dāng)前棧頂數(shù)據(jù)元素的位置；每個(gè)結(jié)點(diǎn)包括data數(shù)據(jù)域：用來(lái)存放數(shù)據(jù)元素的值，next指針域：用來(lái)存放其直接后繼結(jié)點(diǎn)的存儲(chǔ)地址，其基本運(yùn)算和順序棧相同。

最后是關(guān)于堆棧的應(yīng)用：（1）、數(shù)值轉(zhuǎn)換問(wèn)題；由于在將十進(jìn)制數(shù)n轉(zhuǎn)換為d進(jìn)制數(shù)時(shí)，最先得到的余數(shù)是d進(jìn)制數(shù)的最低位，在顯示結(jié)果時(shí)需要最后輸出；而最后求得的余數(shù)是d進(jìn)制數(shù)的最高位，需要最先輸出。這與棧的“先入后出”性質(zhì)相吻合，所以可用棧來(lái)存放逐次求得的余數(shù)，然后輸出。（2）、括號(hào)匹配問(wèn)題；當(dāng)讀取一個(gè)表達(dá)式時(shí)，一旦讀到括號(hào)就進(jìn)棧，而讀到下一個(gè)括號(hào)時(shí)就與棧中括號(hào)比較，若相匹配，則出棧，否則繼續(xù)讀取表達(dá)式。到最后，如果棧為空棧，則說(shuō)明括號(hào)匹配，否則括號(hào)不匹配。第五章：隊(duì)列及其應(yīng)用

首先和棧一樣，要知道隊(duì)列是一種受限制的線性結(jié)構(gòu)，遵守“先進(jìn)先出”的規(guī)則，其插入在隊(duì)尾、刪除在對(duì)頭。

其次根據(jù)順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，隊(duì)列也分為順序隊(duì)列和鏈隊(duì)列。其中順序隊(duì)列是用地址連續(xù)的向量空間依次存儲(chǔ)隊(duì)列中的元素，同時(shí)記錄當(dāng)前對(duì)頭元及隊(duì)尾元素在向量中的位置。然后是鏈隊(duì)列，即在存儲(chǔ)器中占用任意的、連續(xù)或不連續(xù)的物理存儲(chǔ)區(qū)域，使用動(dòng)態(tài)結(jié)點(diǎn)空間分配；在這其中，值得注意的是鏈隊(duì)列不存在隊(duì)滿的情況。

第六章：特殊矩陣、廣義表及其應(yīng)用

首先是關(guān)于矩陣的概念即存儲(chǔ)方法；

1、二維數(shù)組中元素aij的地址為：（1）、以行序?yàn)橹鞔鎯?chǔ)，loc（aij）=loc（a00）+[j*（m+1）+i]*d（2）、以列序?yàn)橹鞔鎯?chǔ)，loc（aij）=loc（a00）+[i*（n+1）+j]*d，其中m為行數(shù)、n為列數(shù)、d為每個(gè)元素所占的存儲(chǔ)單元的個(gè)數(shù)。

2、對(duì)稱矩陣：即將下三角存儲(chǔ)在一個(gè)一維數(shù)組sa[k]中，其中0≤k<(n+1)/2；當(dāng)i≥j時(shí)，k=i*（i+1）/2+j，當(dāng)i

3、三角矩陣：和對(duì)稱矩陣的存儲(chǔ)思路一樣用一維數(shù)組sa[k]存儲(chǔ)，若是上三角矩陣（下三角中元素均為常數(shù)c），則當(dāng)i≥j時(shí)，k=i*（i+1）/2+j，當(dāng)i

j時(shí)，k=n*（n+1）/2

5、稀疏矩陣：即矩陣中非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)，可用三元組表存儲(chǔ)，將非零元素的值與其行號(hào)、列號(hào)存放在一起。

其次是關(guān)于廣義表的概念；廣義表是n（n≥0）個(gè)元素a1、a2、a3、?、an的有限序列，而ai或是原子或是一個(gè)廣義表，所以廣義表是遞歸定義。第七章：二叉樹(shù)及其應(yīng)用

首先關(guān)于二叉樹(shù)的概念及其性質(zhì)；二叉樹(shù)是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。在這其中有兩種特殊的二叉樹(shù)，滿二叉樹(shù)和完全二叉樹(shù)。同時(shí)二叉樹(shù)具有如下五個(gè)性質(zhì)：（1）、在二叉樹(shù)的第i層上至多有2（i-1）個(gè)結(jié)點(diǎn)（i>0）（2）、深度為k的二叉樹(shù)至多有2（k）-1個(gè)結(jié)點(diǎn)（k>0）（3）、對(duì)任意一棵非空二叉樹(shù)，若果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1（4）、有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（n>0）的高度為∟log2n」+1（5）、若對(duì)滿二叉樹(shù)或完全二叉樹(shù)按照“從上到下，每層從左到右，根結(jié)點(diǎn)編號(hào)為1”的方式編號(hào)，則編號(hào)為i的結(jié)點(diǎn)，它的兩個(gè)孩子結(jié)點(diǎn)編號(hào)分別為2i和2i+1，它的父節(jié)點(diǎn)編號(hào)為i/2。

其次是二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)和鏈接存儲(chǔ)。順序存儲(chǔ)是按在完全二叉樹(shù)中的編號(hào)順序，依次存儲(chǔ)在一維數(shù)組中。這樣的存儲(chǔ)方式可以很方便地找到任一結(jié)點(diǎn)的父結(jié)點(diǎn)及左右孩子，但對(duì)于一般的二叉樹(shù)會(huì)造成很大的空間浪費(fèi)，且在插入或刪除結(jié)點(diǎn)時(shí)需大量移動(dòng)節(jié)點(diǎn)，不利于運(yùn)算的實(shí)現(xiàn)。那么就引出了二叉樹(shù)的鏈接存儲(chǔ)，每個(gè)結(jié)點(diǎn)包括三個(gè)域，lchild指針域：記錄該結(jié)點(diǎn)左孩子的地址、rchild指針域：記錄該結(jié)點(diǎn)右孩子的地址、data域：存儲(chǔ)該結(jié)點(diǎn)的信息。

接下來(lái)是二叉樹(shù)的遍歷及線索化，不僅要能對(duì)二叉樹(shù)進(jìn)行遍歷、線索化操作，而且還要能夠根據(jù)給出的遍歷結(jié)果構(gòu)造出二叉樹(shù)。最后是二叉樹(shù)的應(yīng)用，例如哈夫曼樹(shù)：為數(shù)據(jù)壓縮提供了一種方法、二叉排序樹(shù)：即中序遍歷的結(jié)果是遞增的有序序列。

第八章：樹(shù)和森林及其應(yīng)用

首先是關(guān)于樹(shù)和森林的有關(guān)概念及存儲(chǔ)結(jié)構(gòu)；樹(shù)或森林與二叉樹(shù)之間有一個(gè)自然地一一對(duì)應(yīng)關(guān)系，任何一個(gè)森林或一棵樹(shù)可以唯一地對(duì)應(yīng)到一棵二叉樹(shù)；反之，任何一棵二叉樹(shù)也能唯一地對(duì)應(yīng)到一個(gè)森林或一棵樹(shù)。在這里，要會(huì)如何將樹(shù)或森林轉(zhuǎn)換成二叉樹(shù)、二叉樹(shù)轉(zhuǎn)換成樹(shù)或森林。對(duì)于樹(shù)的順序存儲(chǔ)結(jié)構(gòu)：雙親表示法，鏈接存儲(chǔ)結(jié)構(gòu)：（1）、孩子表示法（2）、孩子兄弟表示法，只需了解。

其次是樹(shù)和森林的遍歷，要知道樹(shù)只有先序遍歷和后序遍歷、森林只有先序遍歷和中序遍歷，且（1）、樹(shù)的先序遍歷與二叉樹(shù)的先序遍歷相同（2）、樹(shù)的后序遍歷與二叉樹(shù)的中序遍歷相同（3）、森林的先序遍歷和中序遍歷分別與二叉樹(shù)的先序遍歷和中序遍歷結(jié)果相同。

最后是樹(shù)的一個(gè)典型應(yīng)用——b樹(shù)，它是一種平衡的多路查找樹(shù)，學(xué)習(xí)是根據(jù)實(shí)例走一遍算法，理解算法即可。第九章：散列結(jié)構(gòu)及其應(yīng)用

散列結(jié)構(gòu)是以存儲(chǔ)結(jié)點(diǎn)中的關(guān)鍵字作為自變量，通過(guò)確定的函數(shù)h（即散列函數(shù)或哈希函數(shù)）進(jìn)行計(jì)算，把所求的函數(shù)值作為地址存儲(chǔ)該結(jié)點(diǎn)。

首先是散列函數(shù)有：（1）、直接定址法（2）、除留余數(shù)法（3）、數(shù)字分析法（4）、平方取中法（5）、折疊法

其次是沖突處理，由于散列函數(shù)很可能將不同的關(guān)鍵字計(jì)算出相同的散列地址，所以就需要為發(fā)生沖突的關(guān)鍵字結(jié)點(diǎn)找到一個(gè)“空”的散列地址。沖突處理的方法有

1、開(kāi)放定址法：hi=（h（key）+di）mod m，i=1,2,3，?，k（k≤m-1）例如（1）、線性探測(cè)再散列，取di=1,2,3，?，m-1（2）、二次探測(cè)再散列，取di=1（2），-1（2），2（2），-2（2），?（3）、偽隨機(jī)探測(cè)再散列，取di=偽隨機(jī)數(shù)；

2、鏈地址法：在散列表的每一個(gè)存儲(chǔ)單元中增加一個(gè)指針域，把產(chǎn)生沖突的關(guān)鍵字以鏈表結(jié)構(gòu)存放在指針指向的單元中。第十章：圖及其應(yīng)用 首先是圖的有關(guān)概念；圖是一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組表示，形式化定義為：graph（v，vr），其中v={x|x∈dataobject}，r={vr}，vr={＜x，y＞ p（x，y）∧（x，y∈v）}。頂點(diǎn)的度、入度和出度，以頂點(diǎn)v為頭的弧的數(shù)目稱為v的入度，以頂點(diǎn)v為尾的弧的數(shù)目稱為v的出度，而出度與入度之和即為頂點(diǎn)v的度。

其次是圖的存儲(chǔ)結(jié)構(gòu)；（1）、鄰接矩陣（2)、鄰接表

最后的圖遍歷和圖的典型應(yīng)用；對(duì)于遍歷圖的深度優(yōu)先算法或廣度優(yōu)先算法、最小生成樹(shù)的普利姆算法或克魯斯卡爾算法、最短路徑的迪杰特斯拉算法和弗洛伊德算法以及有向無(wú)環(huán)圖拓?fù)渑判蛩惴?，都需要根?jù)實(shí)例走一遍算法，從而掌握這些算法。

心得體會(huì)

最開(kāi)始學(xué)習(xí)這門(mén)課時(shí)，我對(duì)它沒(méi)有很深刻的認(rèn)識(shí)，只是聽(tīng)說(shuō)這門(mén)課比較難。學(xué)習(xí)起來(lái)會(huì)比較累。通過(guò)這一學(xué)期的學(xué)習(xí)也確實(shí)證實(shí)了這一點(diǎn)。在學(xué)習(xí)這門(mén)課的過(guò)程中自己也確實(shí)遇到了一些問(wèn)題，主要是書(shū)本上的知識(shí)與老師的講解都比較容易理解，但是當(dāng)自己利用已學(xué)的知識(shí)編寫(xiě)程序時(shí)就感到非常的棘手，很多時(shí)候都是把大概的算法思想想出來(lái)后，又把書(shū)本上的程序抄寫(xiě)一遍來(lái)完成程序的編寫(xiě)。針對(duì)這一問(wèn)題以后自己會(huì)盡量學(xué)習(xí)擺脫掉書(shū)本，自己慢慢學(xué)會(huì)獨(dú)立編寫(xiě)程序。

結(jié)語(yǔ)

通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的整理和實(shí)際應(yīng)用，我深刻了解到數(shù)據(jù)結(jié)構(gòu)與算法的重要性，同時(shí)也加深了對(duì)它的認(rèn)識(shí)和了解，了解到了數(shù)據(jù)結(jié)構(gòu)與算法在生活、工作等生活各個(gè)方面的重要性和不可缺少性。我通過(guò)整理數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)而獲得的極大收獲。我相信這次的學(xué)習(xí)會(huì)對(duì)我以后的學(xué)習(xí)和工作產(chǎn)生非常大的影響力。

參考文獻(xiàn)

《數(shù)據(jù)結(jié)構(gòu)與算法》（第二版）王昆侖

李紅 主編

數(shù)據(jù)結(jié)構(gòu)推薦書(shū)目 數(shù)據(jù)結(jié)構(gòu)筆記整理篇四

《數(shù)據(jù)結(jié)構(gòu)與算法》課程學(xué)習(xí)總結(jié)報(bào)告

本學(xué)期開(kāi)設(shè)的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落，現(xiàn)就其知識(shí)點(diǎn)及其掌握情況、學(xué)習(xí)體會(huì)以及對(duì)該門(mén)課程的教學(xué)建議等方面進(jìn)行學(xué)習(xí)總結(jié)。

一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識(shí)點(diǎn)

第一章是這門(mén)學(xué)科的基礎(chǔ)章節(jié)，從整體方面介紹了“數(shù)據(jù)結(jié)構(gòu)和算法”，同時(shí)引入相關(guān)的學(xué)術(shù)概念和術(shù)語(yǔ)，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類(lèi)型以及數(shù)據(jù)結(jié)構(gòu)的定義。重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)的括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合的含義及其相互聯(lián)系。數(shù)據(jù)結(jié)構(gòu)和兩大邏輯結(jié)構(gòu)的4四種常用存儲(chǔ)方法；邏輯結(jié)構(gòu)分為四類(lèi)：集合型、線性、樹(shù)形和圖形結(jié)構(gòu)，數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)和散列存儲(chǔ)四類(lèi)。難點(diǎn)是算法復(fù)雜度的分析方法和性能的分析。

第二章詳細(xì)地分析了順序表。介紹了順序表的相關(guān)概念及其有關(guān)運(yùn)算。基本運(yùn)算有：初始化表、求表長(zhǎng)、排序、元素的查找、插入及刪除等。元素查找方法有：簡(jiǎn)單順序查找、二分查找和分塊查找。排序方法有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等，在各種算法思想的先分析后，要弄清各種算法的時(shí)間復(fù)雜度與空間性能的優(yōu)點(diǎn)和缺點(diǎn)，在什么特定的場(chǎng)合適合哪種算法思想。最后介紹了順序串的概念，順序串是順序表的一個(gè)特例；區(qū)別在于組成順序串的數(shù)據(jù)元素是一組字符，其重點(diǎn)在于串的模式匹配。

第三章介紹鏈表。鏈表中數(shù)據(jù)元素的存儲(chǔ)不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲(chǔ)區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動(dòng)元素，給算法的效率帶來(lái)較大的提高，且在存儲(chǔ)空間上有動(dòng)態(tài)申請(qǐng)的優(yōu)點(diǎn)。這一章中介紹了鏈表的節(jié)點(diǎn)結(jié)構(gòu)、靜態(tài)與動(dòng)態(tài)鏈表的概念、鏈表的基本運(yùn)算（如求表長(zhǎng)、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。弄清其個(gè)運(yùn)算的算法思想及其時(shí)間復(fù)雜度和空間性能。最后介紹了鏈表之中存儲(chǔ)結(jié)構(gòu)在實(shí)際中的相關(guān)應(yīng)用。

第四章，堆棧是運(yùn)算受限制的線性結(jié)構(gòu)。其基本運(yùn)算方法與順序表和鏈表運(yùn)算方法基本相同，不同的是堆棧須遵循“先進(jìn)后出”的規(guī)則，對(duì)堆棧的操作只能在棧頂進(jìn)行；堆棧在文字處理，匹配問(wèn)題和算術(shù)表達(dá)式的求值問(wèn)題方面的應(yīng)用。

第五章，隊(duì)列是一種夠類(lèi)似堆棧的線性結(jié)構(gòu)。其基本運(yùn)算方法與順序表和鏈表運(yùn)算方法基本相同，不同的是堆棧須遵循“先進(jìn)先出”的規(guī)則，對(duì)堆棧的操作只能在棧頂進(jìn)行；其運(yùn)算有入隊(duì)、出隊(duì)等操作。在介紹隊(duì)列時(shí)，提出了循環(huán)隊(duì)列的概念，以避免“假溢出”的現(xiàn)象。

第六章介紹了特殊矩陣和廣義表的概念與應(yīng)用。其中，特殊矩陣包括對(duì)稱矩陣、三角矩陣、對(duì)角矩陣和稀疏矩陣，書(shū)中分別詳細(xì)介紹了它們的存儲(chǔ)結(jié)構(gòu)。其中三元組和十字鏈表這兩種結(jié)構(gòu)尤為重要；對(duì)著兩種結(jié)構(gòu)的建立了應(yīng)用要掌握。稀疏矩陣的應(yīng)用包括轉(zhuǎn)置和加法運(yùn)算等。最后介紹了廣義表的相關(guān)概念及存儲(chǔ)結(jié)構(gòu)，關(guān)于它的應(yīng)用，課本中舉了m元多項(xiàng)式的表示問(wèn)題。

第七章二叉樹(shù)的知識(shí)是重點(diǎn)內(nèi)容。在介紹有關(guān)概念時(shí)，提到了二叉樹(shù)的性質(zhì)以及兩種特殊的二叉樹(shù)：完全二叉樹(shù)和滿二叉樹(shù)。接著介紹二叉樹(shù)的順序存儲(chǔ)和鏈接存儲(chǔ)以及生成算法。重點(diǎn)介紹二叉樹(shù)的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹(shù)。二叉樹(shù)的應(yīng)用：基本算法、哈弗曼樹(shù)、二叉排序樹(shù)和堆排序，其中關(guān)于二叉排序樹(shù)和哈弗曼書(shū)的構(gòu)建是重點(diǎn)。

第八章介紹了樹(shù)。樹(shù)與二叉樹(shù)是不同的概念。教材介紹了樹(shù)和森林的概念、遍歷和存儲(chǔ)結(jié)構(gòu)，還有樹(shù)、森林和二叉樹(shù)的相互關(guān)系，樹(shù)或森林怎樣轉(zhuǎn)化成二叉樹(shù)，二叉樹(shù)又如何轉(zhuǎn)換為樹(shù)和森林等算法。

第九章，散列結(jié)構(gòu)是一種查找效率很高的一種數(shù)據(jù)結(jié)構(gòu)。本章的主要知識(shí)點(diǎn)有：散列結(jié)

構(gòu)的概念及其存儲(chǔ)結(jié)構(gòu)、散列函數(shù)、兩種沖突處理方法、線性探測(cè)散列和鏈地址散列的基本算法以及散列結(jié)構(gòu)的查找性能分析。

最后一章介紹了圖的概念及其應(yīng)用，是本書(shū)的難點(diǎn)。圖的存儲(chǔ)結(jié)構(gòu)的知識(shí)點(diǎn)有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識(shí)點(diǎn)有：有向圖、連通圖、生成樹(shù)和森林、最短路徑問(wèn)題和有向無(wú)環(huán)圖及其應(yīng)用。有向無(wú)環(huán)圖重點(diǎn)理解aov網(wǎng)和拓?fù)渑判蚣捌渌惴ā?/p>

二、對(duì)各知識(shí)點(diǎn)的掌握情況

總體來(lái)看，對(duì)教材中的知識(shí)點(diǎn)理解較為完善，但各個(gè)章節(jié)均出現(xiàn)有個(gè)別知識(shí)點(diǎn)較為陌生的現(xiàn)象，對(duì)某些具體的問(wèn)題和應(yīng)用仍有一些模糊與措手。各個(gè)章節(jié)出現(xiàn)的知識(shí)點(diǎn)理解和掌握情況明確一下。

第一章中我對(duì)數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹，熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。算法的時(shí)間、空間性能分析是重點(diǎn)，同樣也是難點(diǎn)，尤其是空間性能分析需要加強(qiáng)。在某些強(qiáng)大與復(fù)雜的算法面前的處理有些棘手。

第二章，順序表的概念、生成算法理解較為清晰，并且熟悉簡(jiǎn)單順序查找和二分查找，對(duì)分塊查找較為含糊。刪除方面的問(wèn)題比較容易些。排序問(wèn)題中，由于冒泡排序在大一c語(yǔ)言課上已經(jīng)學(xué)習(xí)過(guò)，再來(lái)學(xué)習(xí)感覺(jué)相對(duì)輕松些。對(duì)插入排序和選擇排序理解良好，但是，在實(shí)際運(yùn)用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習(xí)中感覺(jué)較吃力，現(xiàn)在對(duì)這種排序方法仍然非常模糊，所以需要花較多的時(shí)間來(lái)補(bǔ)習(xí)。此外串的模式匹配也是較難理解的一個(gè)地方。

第三章鏈表中，除對(duì)雙向循環(huán)鏈表這一知識(shí)點(diǎn)理解困難之外，在對(duì)鏈表進(jìn)行插入刪除和排序相關(guān)操作上同順序表的操作基本相當(dāng)。其他的知識(shí)點(diǎn)像單鏈表的建立和基本算法等都較為熟悉。

第四章和第五章有關(guān)堆棧以及隊(duì)列的知識(shí)點(diǎn)比較少，除有關(guān)算法較為特殊以外，其余算法都是先前學(xué)過(guò)的順序表和鏈表的知識(shí)，加上思想上較為重視，因此這部分內(nèi)容是我對(duì)全書(shū)掌握最好的一部分。在一些實(shí)際問(wèn)題的應(yīng)用與處理方面，對(duì)其進(jìn)行存儲(chǔ)結(jié)構(gòu)的選擇還是需要認(rèn)真考慮的。在算法的時(shí)間復(fù)雜度和空間性能的分析仍有些困難。

第六章的學(xué)習(xí)感覺(jué)較為困難的部分在于矩陣的應(yīng)用上。在矩陣的存儲(chǔ)結(jié)構(gòu)中，使用三元組表發(fā)相對(duì)較為簡(jiǎn)單，而使用十字鏈表就有些困難了。但在某些問(wèn)題的處理上又必須或從節(jié)省空間考慮采用十字鏈表來(lái)處理，想矩陣的加法運(yùn)算。廣義表的定義還是比較容易理解的，其存儲(chǔ)結(jié)構(gòu)也不難掌握，關(guān)于應(yīng)用也只局限于在多項(xiàng)式的表示上。

第七章是全書(shū)的重點(diǎn)。在這一章中概念和定義都很多，有些很昏人但都很重要，要區(qū)分開(kāi)來(lái)。二叉樹(shù)的性質(zhì)容易懂卻很難記憶。對(duì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好，能夠熟練運(yùn)用。關(guān)于二叉排序樹(shù)和的哈弗曼樹(shù)卻相對(duì)有些壓力，其生成和對(duì)其關(guān)鍵字的插入和刪除時(shí)重點(diǎn)。

第八章關(guān)于樹(shù)的分析，首先要明確樹(shù)和二叉樹(shù)的區(qū)別，以及書(shū)中的相關(guān)定義和概念。關(guān)于二叉樹(shù)、樹(shù)和森林之間的轉(zhuǎn)換和遍歷方法是重點(diǎn)，但不算是難。接著就是數(shù)的存儲(chǔ)結(jié)構(gòu)的選擇及轉(zhuǎn)化為二叉樹(shù)的算法，這部分有些吃力。再就介紹了特殊的樹(shù)-b樹(shù)，關(guān)于對(duì)b樹(shù)的操作，插入關(guān)鍵字是中帶領(lǐng)和難點(diǎn)。

第九章散列結(jié)構(gòu)這一章理解比較完善的知識(shí)點(diǎn)有：基本概念和存儲(chǔ)結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學(xué)得比較扎實(shí)，對(duì)數(shù)字分析法等方法則感覺(jué)較為陌生。對(duì)兩種沖突處理的算法思想的理解良好，問(wèn)題在于用c語(yǔ)言描述上。

最后一章，圖及其應(yīng)用中，相關(guān)定義及其概念很多，容易混淆，這就要慢慢來(lái)，仔細(xì)分辨。圖的鄰接矩陣、鄰接表表示法及其之間的轉(zhuǎn)換時(shí)重點(diǎn)和難點(diǎn)。而對(duì)十字鏈表和鄰接多重表的表示法則較為陌生。感覺(jué)理解較為吃力的內(nèi)容有圖的遍歷（包括深度和廣度優(yōu)先遍歷），以及最小生成樹(shù)的問(wèn)題。最短路徑、aov網(wǎng)、關(guān)鍵路徑、aoe網(wǎng)和拓?fù)渑判虻膶W(xué)習(xí)也是相對(duì)較輕松的。，三、學(xué)習(xí)體會(huì)

在學(xué)習(xí)開(kāi)始，王教授就明確提出它不是一種計(jì)算機(jī)語(yǔ)言，不會(huì)介紹新的關(guān)鍵詞，而是通過(guò)學(xué)習(xí)可以設(shè)計(jì)出良好的算法，高效地組織數(shù)據(jù)。一個(gè)程序無(wú)論采用何種語(yǔ)言，其基本算法思想不會(huì)改變。聯(lián)系到在大一和大二上學(xué)期學(xué)習(xí)的c和c++語(yǔ)言，我深刻認(rèn)識(shí)到了這一點(diǎn)。“軟件開(kāi)發(fā)好比寫(xiě)作文，計(jì)算機(jī)語(yǔ)言提供了許多華麗的辭藻，而數(shù)據(jù)結(jié)構(gòu)則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來(lái)。”在學(xué)習(xí)這門(mén)課中，要熟悉對(duì)算法思想的一些描述手段，包括文字描述、圖形描述和計(jì)算機(jī)語(yǔ)言描述等。因此，計(jì)算機(jī)語(yǔ)言基礎(chǔ)是必須的，因?yàn)樗峁┝艘环N重要的算法思想描述手段——機(jī)器可識(shí)別的描述。

這門(mén)課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問(wèn)題，最為突出的，書(shū)本上的知識(shí)與老師的講解都比較容易理解，但是當(dāng)自己采用剛學(xué)的知識(shí)點(diǎn)編寫(xiě)程序時(shí)卻感到十分棘手，有時(shí)表現(xiàn)在想不到適合題意的算法，有時(shí)表現(xiàn)在算法想出來(lái)后，只能將書(shū)本上原有的程序段謄寫(xiě)到自己的程序中再加以必要的連接以完成程序的編寫(xiě)。針對(duì)這一情況，我會(huì)嚴(yán)格要求自己，熟練掌握算法思想，盡量獨(dú)立完成程序的編寫(xiě)與修改工作，只有這樣，才能夠提高運(yùn)用知識(shí)，解決問(wèn)題的能力。

四、對(duì)《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)的建議

1、建議在上課過(guò)程中加大隨堂練習(xí)的分量，以便學(xué)生能當(dāng)堂消化課堂上學(xué)習(xí)的知識(shí)，也便于及時(shí)了解學(xué)生對(duì)知識(shí)點(diǎn)的掌握情況，同時(shí)有助于學(xué)生保持良好的精神狀態(tài)。

2、建議在課時(shí)允許的情況下，增加習(xí)題課的分量，通過(guò)課堂的習(xí)題講解，加深對(duì)知識(shí)點(diǎn)的掌握，同時(shí)對(duì)各知識(shí)點(diǎn)的運(yùn)用有一個(gè)更為直觀和具體的認(rèn)識(shí)。

以上便是我對(duì)《數(shù)據(jù)結(jié)構(gòu)與算法》這門(mén)課的學(xué)習(xí)總結(jié)，我會(huì)抓緊時(shí)間將沒(méi)有吃透的知識(shí)點(diǎn)補(bǔ)齊。今后我仍然會(huì)繼續(xù)學(xué)習(xí)，克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁進(jìn)！

【本文地址：http://www.aiweibaby.com/zuowen/1088639.html】