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

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

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

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

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

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

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

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

數(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)，如線性表，棧，隊，串，數(shù)組 和非線性結(jié)構(gòu)如 樹結(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ù)運算如插入、刪除、修改、排序、查找。數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的數(shù)據(jù)叫邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指數(shù)據(jù)的存儲結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

第二章 線性表

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

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

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

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

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

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

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

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

7.在一個長度為n的順序存儲的線性表中，刪除第i個元素(1<=i<=n)時，需要從前向后依次前移i個元素前插入元素需移動

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

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

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

入一個結(jié)點或刪除第一個結(jié)點，故采用_僅有尾指針的單循環(huán)鏈表存儲方式最節(jié)省運算時間；對

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

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

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

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

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

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

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

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

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

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

時，需要進行的操作為a[j].next=a[i].next和a[i].next=j語句。

第三章 棧和隊列

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

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

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

放自棧底到棧頂?shù)脑?；二是棧的鏈式表示?/p>

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

稱為隊頭front

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

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

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

7.8.9.向一個棧項指針為hs的鏈棧中插入一個*s結(jié)點時，則執(zhí)行。

10.在一個鏈隊列中，假定front和rear分別為隊首指針和隊尾指針，則進行插入*s結(jié)點的操作時

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

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

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

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

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

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

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

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

列車開出車站的所有可能的順序。

答：至少有14種①全進之后再出情況,只有1種：4，3，2，1②進3個之后再出的情況，有

3種，3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況,有5種，2,4,3,12,3,4,12,1, 3,4

2,1,4,32,1,3,4④進1個之后再出的情況,有5種，1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,3

第四章 串

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

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

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

4．一個字符串中稱為該串的子串。

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

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

o（m）；求兩串的最長公共子串，時間為o（n）是不行的，至少要o（n2）。

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

1.矩陣的壓縮存儲：是指為多個值相同的元只分配一個存儲空間，對零元不分配空間。

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

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

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

二、孩子兄弟表示

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

和下一個兄弟結(jié)點。操作容易，破壞了樹的層次

第六章 樹和二叉樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、連通圖——圖中任意兩個頂點都是連通的叫~；連通分量——非連通圖的每一個連通部分叫~

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

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

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

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

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

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

起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止

第九章 查找

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3．開展科學(xué)研究，積極申請科研立項

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

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

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

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

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

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

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

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

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

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

1．教學(xué)方法

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

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

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

2．教學(xué)手段

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

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

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

2.教研課題

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

1）范體貴、門愛華、張國祥、王玉紅分別獲赤峰學(xué)院2005、2006年、2007年、2008年“課堂教學(xué)質(zhì)量優(yōu)秀獎”；

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

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

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

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

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

摘要

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

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

課程主要內(nèi)容

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

j時，k=n*（n+1）/2

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

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

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

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

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

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

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

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

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

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

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

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

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

2、鏈地址法：在散列表的每一個存儲單元中增加一個指針域，把產(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）}。頂點的度、入度和出度，以頂點v為頭的弧的數(shù)目稱為v的入度，以頂點v為尾的弧的數(shù)目稱為v的出度，而出度與入度之和即為頂點v的度。

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

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

心得體會

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

結(jié)語

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

參考文獻

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

李紅 主編

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最后一章介紹了圖的概念及其應(yīng)用，是本書的難點。圖的存儲結(jié)構(gòu)的知識點有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應(yīng)用。有向無環(huán)圖重點理解aov網(wǎng)和拓撲排序及其算法。

二、對各知識點的掌握情況

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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