范文為教學中作為模范的文章，也常常用來指寫作的模板。常常用于文秘寫作的參考，也可以作為演講材料編寫前的參考。那么我們該如何寫一篇較為完美的范文呢？下面我給大家整理了一些優秀范文，希望能夠幫助到大家，我們一起來看一看吧。

數據結構讀書筆記5000篇一

一、選擇

1.如果在數據結構中每個數據元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是（）

a.棧 b.隊列 c.樹 d.圖 2.下面程序段的時間復雜度為（）for(i=0;i

next =hl;b.p->next=hl;hl=p;c.p->next=hl;p=hl;d.p->next=hl->next;hl->next=p;4.兩個字符串相等的條件是（）

c.都是非空串 d.串的長度相等且對應的字符相同 5．若以s和x分別表示進棧和退棧操作，則對初始狀態為空的棧可以進行的棧操作系列是（）

xx sx sx xx 6.已知一棵含50個結點的二叉樹中只有一個葉子結點，則該樹中度為1的結點個數為（）a.0 b.1 c.48 d.49 7.已知用某種排序方法對關鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結果為

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）

a.插入排序 b.冒泡排序 c.快速排序 d.歸并排序

8.已知散列表的存儲空間為t[0..16]，散列函數h（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關鍵字：t[5]=39，t[6]=57和t[7]=7，則下一個關鍵字23插入的位置是（）

a.t[2] b.t[4] c.t[8] d.t[10] 9.如果將矩陣an×n的每一列看成一個子表，整個矩陣看成是一個廣義表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為dout，則所有頂點的入度之和為（）

-1 +1 d.n 11．從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（）a線性結構 b.樹形結構 c.線性結構和樹型結構 d.線性結構和圖狀結構

12．棧的插入和刪除操作在()進行。

a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）a.24 b.71 c.48 d.53 14．一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關于棧和隊列的說法中正確的是（）

a．棧和隊列都是線性結構 b.棧是線性結構，隊列不是線性結構 c.棧不是線性結構，隊列是線性結構 d.棧和隊列都不是線性結構 16．關于存儲相同數據元素的說法中正確的是（）a．順序存儲比鏈式存儲少占空間 b.順序存儲比鏈式存儲多占空間

c.順序存儲和鏈式存儲都要求占用整塊存儲空間 d.鏈式存儲比順序存儲難于擴充空間

17．已知一個單鏈表中，指針q指向指針p的前趨結點，若在指針q所指結點和指針p所指結點之間插入指針s所指結點，則需執行（）a.q→next=s；p→next=s； b.q→next=s；s→next=p； c.q→next=s；q→next=p； d.q→next=s；s→next=q；

18．設一組記錄的關鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結點個數是（）a.1 b.2 c.3 d.4 19．執行下面程序段時，s語句被執行的次數為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在長度為n的線性表中刪除一個指針p所指結點的時間復雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（）

a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．關于串的敘述中，正確的是（）a．空串是只含有零個字符的串 b.空串是只含有空格字符的串

c.空串是含有零個字符或含有空格字符的串

d.串是含有一個或多個字符的有窮序列

23．在具有m個單元的循環隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（）

a．front==rear

b.(front+1)%m==rear

+1==front

d.(rear+1)%m==front 24．設有二維數組

?1????a［n］［n］表示如下：?23456??????????，則a［i］［i］（0≤i≤n-1）的d.i2/2 值為（）

a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中，結點數最多為（）

ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵結點數為n的樹組成的森林，將其轉化為一棵二叉樹，則該二叉樹中根結點的右子樹上具有的結點個數是（）

-1 c.n(m-1)d.m(n-1)27．在一個具有n個頂點的無向圖中，每個頂點度的最大值為（）a.n b.n-1 c.n+1 d.2(n-1)28．關于無向圖的鄰接矩陣的說法中正確的是（）a.矩陣中非全零元素的行數等于圖中的頂點數

b.第i行上與第i列上非零元素總和等于頂點vi的度數 c.矩陣中的非零元素個數等于圖的邊數

d.第i行上非零元素個數和第i列上非零元素個數一定相等

29．設一組記錄的關鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結點個數是（）a.1 b.2 c.3 d.4 30．設有一組初始關鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關鍵字值為基準得到的一次劃分為（）

a.36，44，49，55，81，88 b.44，36，49，55，81，88 c.44，36，49，81，55，88 d.44，36，49，55，88，81

二、填空題

1.數據是計算機加工處理的對象（）。2.數據結構的概念包括數據的邏輯結構、數據在計算機中的存儲方式和數據的運算三個方面()。

3.線性表是由n≥0個相同類型組成的有限序列（）。4.棧是一種后進先出的線性表（）。

5.從循環鏈表的某一結點出發，只能找到它的后繼結點，不能找到它的前驅結點（）。6.單鏈表設置頭結點的目的是為了簡化運算（）。7.樹的最大特點是一對多的層次結構（）。8.組成數據的基本單位稱為數據元素（）。

9.從非循環鏈表的某一結點出發，既能找到它的后繼結點，又能找到它的前驅結點（）。

10.單鏈表結點的指針域是用來存放其直接后繼結點的首地址的（）

11.數據的存儲結構是數據的邏輯結構的存儲映象（）。

12.用順序表來存儲線性表時，不需要另外開辟空間來保存數據元素之間的相互關系（）。

13.在非線性結構中，至少存在一個元素不止一個直接前驅或不止一個直接后驅（）。14.樹的最大特點是一對多的層次結構（）。15.隊列的特點是先進先出（）。

16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數據的存儲結構獨立于計算機（）。18.線性表簡稱為”順序表”。（）

19.對數據的任何運算都不能改變數據原有的結構特性（）。20.從循環單鏈表的任一結點出發，可以找到表中的所有結點（）。21.棧是一種先進先出的線性表（）。22.鏈表的主要缺點是不能隨機訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩定的排序（）。25.算法是對解題方法和步驟的描述（）。26.算法可以用任意的符號來描述（）。

27.數據的邏輯結構可以看作是從具體問題抽象出來的數學模型（）。

28.線性表的順序存儲方式是按邏輯次序將元素存放在一片地址連續的空間中（）。29.棧是一種先進后出的線性表（）。

30.將插入和刪除限定在表的同一端進行的線性表是隊列（）。

三、畫圖題

1.請根據下列二元組畫出相應的數據結構

k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據下列二元組畫出相應的數據結構

k={a,b,c,d,e,f,g,h,i,j} r={,,

,

,

,

,

,

,

} 3．請根據下列二元組畫出相應的數據結構 k={1,2,3,4,5,6,7} r={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.請根據下列二元組畫出相應的數據結構

k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}

四、運算題

1．已知一個圖的頂點集v和邊集h分別為：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。

2.一個線性表為b=（12，23，45，57，20，03，78，31，15，36），設散列表為ht[0..12]，散列函數為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。

平均查找長度：（寫出計算過程）

3．已知一個圖的頂點集v和邊集h分別為：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點2出發）

____

__，___

_，___

___，__

____，___ ___，__ ____，___ ___。4.寫出下圖所示的二叉樹的前中后序遍歷結果：

前序： 中序： 后序：

5.設有一個輸入數據的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。

五、編程題

1.請編寫一個算法，實現十進制整數與二進制數的轉換。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：

int search_bin(keytype k,sstable st){ 3.請編寫一個算法，實現單鏈表的就地逆置（單鏈表不帶頭結點）。linklist *invertlink(linklist *h){

數據結構讀書筆記5000篇二

0913011037信息管理與信息系統李二勇

數據結構讀書筆記

第一章是緒論部分，因為大家都是剛剛接觸這門課，所以還有很多不是很多的了解，隨著計算機的迅速發展，計算機的應用領域已經不再只是科學計算領域，而更多的應用于控制管理以及數據處理等非數值計算的處理工作，與此對應，計算機加工處理的對象由純粹的數值發展到字符，表格和圖像等各種具有一定結構的數據，這就給程序設計帶來了一些新的問題，為了編寫出一個好的程序，必須分析待處理的對象的特性以及各處理對象之間存在的關系。所以在這種環境下，數據結構這門課就誕生了。

第二章.線性表的相關基本概念，如:前驅、后繼、表長、空表、首元結點，頭結點，頭指針等概念。

2.線性表的結構特點，主要是指:除第一及最后一個元素外，每個結點都只有一個前趨和只有一個后繼。

3.線性表的順序存儲方式及其在具體語言環境下的兩種不同實現:表空間的靜態分配和動態分配。靜態鏈表與順序表的相似及不同之處

4.線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算:單鏈表、循環鏈表，雙向鏈表，雙向循環鏈表。其中，單鏈表的歸并算法、循環鏈表的歸并算法、雙向鏈表及雙向循環鏈表的插入和刪除算法等都是較為常見的考查

方式。此外，近年來在不少學校中還多次出現要求用遞歸算法實現單鏈表輸出（可能是順序也可能是倒序）的問題。

5.線性表的順序存儲及鏈式存儲情況下，其不同的優缺點比較，即其

各自適用的場合。單鏈表中設置頭指針、循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。

第三章本章主要重點是1.棧、隊列的定義及其相關數據結構的概念，包括:順序棧，鏈棧，共享棧循環隊列，鏈隊等。棧與隊列存取數據（請注意包括:存和取兩部分）的特點。

2.遞歸算法。棧與遞歸的關系，以及借助棧將遞歸轉向于非遞歸的經典算法

:n!階乘問題，fib數列問題，hanoi問題，背包問題，3.棧的應用:數值表達式的求解，括號的配對等的原理

4.循環隊列中判隊空、隊滿條件，循環隊列中入隊與出隊算法。

第四章1.串的基本概念，串與線性表的關系（串是其元素均為字符型數據的特殊線

性表），空串與空格串的區別，串相等的條件

2.串的基本操作，以及這些基本函數的使用，包括:取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的算法是很多學校在基本操作上的考查重點。

3.順序串與鏈串及塊鏈串的區別和聯系，實現方式。

算法思想。kmp中next數組以及nextval數組的求法。明確傳統模式匹配算法的不足，明確next數組需要改進之外。其中，理解算法是核心，會求數組是得分點。

查方式是:求next和nextval數組值，根據求得的next或nextval數組值給出運用kmp算法進行匹配的匹配過程。

第五章廣義表的概念，是數據結構里第一次出現的。它是線性表或表元素的有限序列，構成該結構的每個子表或元素也是線性結構

1.多維數組中某數組元素的position求解。一般是給出數組元素的首元素地址和每個元素占用的地址空間并組給出多維數組的維數，然后要求你求出該數組中的某個元素所在的位置。

2.明確按行存儲和按列存儲的區別和聯系

3.將特殊矩陣中的元素按相應的換算方式存入數組中。這些矩陣包括:對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式:三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的算法。

4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點，是理解整個廣義表一節算法的基礎。

5.與廣義表有關的遞歸算法。由于廣義表的定義就是遞歸的，所以，與廣義表有關的算法也常是遞歸形式的。比如:求表深度，復制廣義表等。這種題

目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答:一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。第六章1.二叉樹的概念、性質和存儲結構

考查方法可有:直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區別；考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質:第i層的最多結點數，深度為k的二叉樹的最多結點數，n0=n2+

1的性質，n個結點的完全二叉樹的深度，順序存儲二叉樹時孩子結點與父結點之間的換算關系（左為:2*i，右為:2*i+1）。

2.二叉樹的三種遍歷算法

二叉樹的遍歷算法有三種:先序，中序和后序。其劃分的依據是視其每個算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸算法，理解其執行的實際步驟，并且應該熟練掌握三種遍歷的非遞歸算法。由于二叉樹一章的很多算法，可以直接根據三

種遞歸算法改造而來（比如:求葉子個數），所以，掌握了三種遍歷的非遞歸算法后，對付諸如:“利用非遞歸算法求二叉樹葉子個數”

3.可在三種遍歷算法的基礎上改造完成的其它二叉樹算法:

求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞

歸遍歷算法，那么解決以上問題就是小菜一碟了。

4.線索二叉樹:

線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。對于線索二叉樹，應該掌握:線索化的實質，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如:查找某一類線索二叉樹中指定結點的前驅或后繼結點就是一類常考題）。

5.最優二叉樹（哈夫曼樹）:

最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。

6.樹與森林:

二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最多為2以及其它特征，一個最重要的特殊之處是在于:二叉樹是有序的！即:二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹我們認為是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質。

樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷算法:先根與后根（對于森林而言稱作:先序與后序遍歷）。在難度比較大的考試中，也有基于此種算法的基礎上再進行擴展要求你利用這兩種算法設計其它算法的，但一般院校很少有這種考法，最多只是要求你根據先根或后根寫出他們的遍歷序列。此二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應關系的:先根遍歷對應二叉樹的先序遍歷，而后根遍歷對應二叉樹的中序遍歷。

第七章 圖

圖這一章的特點是:概念繁多，與離散數學中圖的概念聯系緊密，算法復雜與圖兩章的知識這一章的重點是:圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，回路，連通圖，（強）連通分量等概念。

2.圖的幾種存儲形式:

圖的存儲形式包括:鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。

3.圖的兩種遍歷算法:深度遍歷和廣度遍歷

深度遍歷和廣度遍歷是圖的兩種基本的遍歷算法，這兩個算法對圖一章的重要性等同于“先序、中序、后序遍歷”對于二叉樹一章的重要性。在考查時，圖一章的算法設計題常常是基于這兩種基本的遍歷算法而設計的，比如:“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為k的簡單路徑問題”，就分別用到了廣度遍歷和深度遍歷算法。

4.生成樹、最小生成樹的概念以及最小生成樹的構造rim算法和kruskal

7.最短路徑問題:

最短路徑問題分為兩種:一是求從某一點出發到其余各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。

主要還是體現在平時做實驗的時候，因為做其他課的實驗最起碼會知道一些基本的做法，但是遇到數據結構就會發現真的很難，有時真的什么都不會，看也看不懂，感覺很吃力，就感覺數據結構這個模塊不簡單，有點復雜，總體感覺學不好，但是上次期中考試時候，發現也不是傳說中的那么難，有些題真的很死，可以用固定的方法去寫，但是那種題不多，大部分的題還是要自己去構造一種思想，并用代碼實現它！感覺這樣的題不好做，有點難度！其實，剛開始講的時候，因為課下沒有預習，上課節奏也沒有跟上，所以就失去信心了。

這幾天，因為考試在即，所以花了一些功夫復習，自我感覺收獲還算不小，最起碼了解了一些，學到了一些！但是課程已經結束了，還

是感覺缺少很多，所以自己還是要其他方面多多努力，接下來的復習還是要靠自己理解，如果理解好了以后對做題的幫助確實不小，所以說，理解透徹了就好辦了！現在大多是自學，相比以前的學習方法，感覺有點不一樣，但是我相信如果努力還會有很大的提高的。

數據結構讀書筆記5000篇三

實驗：線性表的基本操作

【實驗目的】

學習掌握線性表的順序存儲結構、鏈式存儲結構的設計與操作。對順序表建立、插入、刪除的基本操作，對單鏈表建立、插入、刪除的基本操作算法。

【實驗內容】

1.順序表的實踐

1)建立4個元素的順序表s=sqlist[]={1，2，3，4，5}，實現順序表建立的基本操作。

2)在sqlist []={1，2，3，4，5}的元素4和5之間插入一個元素9，實現順序表插入的基本操作。

3)在sqlist []={1，2，3，4，9，5}中刪除指定位置（i=5）上的元素9，實現順序表的刪除的基本操作。2.單鏈表的實踐

3.1)建立一個包括頭結點和4個結點的（5，4，2，1）的單鏈表，實現單鏈表建立的基本操作。

2)將該單鏈表的所有元素顯示出來。

3)在已建好的單鏈表中的指定位置（i=3）插入一個結點3，實現單鏈表插入的基本操作。

4)在一個包括頭結點和5個結點的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個結點，實現單鏈表刪除的基本操作。5)實現單鏈表的求表長操作。

【實驗步驟】

1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

線性是我們學習數據結構中，碰到的第一個數據結構。學習線性表的重點掌握順序表和單鏈表的各種算法和時間性能分析。線性表右兩種存儲方式即順序存儲結構和鏈式存儲結構。通過學習我知道了對線性表進行建立、插入、刪除，同時單鏈表也是進行建立、插入、刪除。而對于順序表的插入刪除運算，其平均時間復雜度均為0（n）.通過這次的學習，掌握的太熟練，主要是課本上的知識點沒有徹底的理解，回去我會多看書，理解重要的概念。總之，這次實驗我找到了自己的不足之處，以后會努力的。

實驗二：棧的表示與實現及棧的應用

【實驗目的】

（1）掌握棧的順序存儲結構及其基本操作的實現。（2）掌握棧后進先出的特點，并利用其特性在解決實際問題中的應用。（3）掌握用遞歸算法來解決一些問題。【實驗內容】

1.編寫程序，對于輸入的任意一個非負十進制整數，輸出與其等值的八進制數。

2.編寫遞歸程序，實現n！的求解。3.編寫遞歸程序，實現以下函數的求解。

n,n?0,1?fib(n)?? ?fib(n?1)?fib(n?2),n?1

4.編寫程序，實現hanoi塔問題。【實驗步驟】 1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

通過這次的學習我掌握了棧這種抽象數據類型的特點，并能在相應的應用任務中正確選用它；總的來說，棧是操作受限的線性表，是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應地，表頭端稱為棧底（botton）；棧又稱為后進先出（last in first out）的線性表,簡稱lifo結構，因為它的修改是按后進先出的原則進行的。

加上這個實驗，我已經學了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學習有很大的作用，可以說這是學習以后知識的總要基礎。

實驗三：二叉樹的建立及遍歷

【實驗目的】

（1）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序、中序和后序遍歷算法。【實驗內容】

1.編寫程序，實現二叉樹的建立，并實現先序、中序和后序遍歷。如：輸入先序序列abc###de###，則建立如下圖所示的二叉樹。

并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實驗步驟】 1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

這次試驗是關于二叉樹的常見操作，主要是二叉樹的建立和遍歷，在這次實驗中我按先序方式建立二叉樹的，而遍歷方式則相對要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個數的計算和遍歷相差不大，只是加些判斷條件，總體來說，本次試驗不太好做，期間出現了很多邏輯錯誤，變量初始化的問題等，不過經過仔細排查最后都一一解決了。

實驗四：查找與排序

【實驗目的】

（1）掌握折半查找算法的實現。（2）掌握冒泡排序算法的實現。【實驗內容】

1.編寫折半查找程序，對以下數據查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.編寫冒泡排序程序，對以下數據進行排序。49，38，65，97，76，13，27，49 【實驗步驟】 1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

（1）查找算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st){ int i,n;

=

(elemtype*)

malloc(elemtype));

if(!)return(overflow);

printf(“輸入元素個數和各元素的值:”);

scanf(“%dn”,&n);

for(i=1;i<=n;i++){

(maxnum*sizeof

scanf(“%d”,&[i]);}

= n;

return ok;} int seq_search(sstable st,elemtype key){

int i;

[0]=key;

for(i=;[i]!=key;--i);

return i;} int binarysearch(sstable st,elemtype key){

int mid,low,high,i=1;

low=1;

high=;

while(low<=high)

{

mid=(low+high)/2;

if([mid]==key)

return mid;

else if(key

high=mid-1;

else

}

return 0;} void main(){ sstable st;initlist(st);

elemtype key;int n;printf(“ key= ”);

scanf(“%d”,&key);

printf(“nn”);

/*printf(“after seqsearch:: ”);

n=seq_search(st,key);

printf(“position is in %d nn”,n);*/

printf(“after binary search::”);

n=binarysearch(st,key);

low=mid+1;if(n)printf(“position is in %d nn”,n);else

} 實驗結果如下所示：

（2）排序算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;

(elemtype));

if(!)return(overflow);

printf(“輸入元素個數和各元素的值:”);

scanf(“%dn”,&n);

for(i=1;i<=n;i++){

scanf(“%d”,&[i]);}

= n;

return ok;} void sort(sstable st){

int i,j,t;

for(i=1;i

for(j=i+1;j<=;j++)

if([i]>[j]){ t=[i];=

(elemtype*)

malloc

(maxnum*sizeof

}

} [i]=[j];[j]=t;void display(sstable st){ int i;

for(i=1;i<=;i++){

printf(“%d

”,[i]);}

} void main(){

sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 實驗結果如下所示：

【實驗心得】

通過這次實驗,我明白了程序里的折半查找和冒泡查找.其實排序可以有很多種，但是其目的應該都是為了能夠在海量的數據里迅速查找到你要的數據信息，折半查找是種比較快的方式，但前提是要是有 序的排序才可以。對于有序表，查找時先取表中間位置的記錄關鍵字和所給關鍵字進行比較，若相等，則查找成功；如果給定值比該記錄關鍵字大，則在后半部分繼續進行折半查找；否則在前半部分進行折半查找，直到查找范圍為空而查不到為止。折半查找的過程實際上死先確定待查找元素所在的區域，然后逐步縮小區域，直到查找成功或失敗為止。算法中需要用到三個變量，low表示區域下界，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.

數據結構讀書筆記5000篇四

數據結構】二叉排序樹的建立，查找，插入和刪除實踐題 /*sy53.c*/

#include

typedef struct node{

keytype key;

struct node *lchild,*rchild;

}bstnode;

typedef bstnode *bstree;

bstree createbst(void);

void searchbst(bstree t,keytype key);

void insertbst(bstree *tptr,keytype key);

void delbstnode(bstree *tptr,keytype key);

void inorderbst(bstree t);

main()

{bstree t;

char ch1,ch2;

keytype key;

printf(“建立一棵二叉排序樹的二叉鏈表存儲n”);

t=createbst();

ch1='y';

while(ch1=='y' || ch1=='y')

{printf(“請選擇下列操作：n”);

printf(“1------------------更新二叉排序樹存儲n”);

printf(“2------------------二叉排序樹上的查找n”);

printf(“3------------------二叉排序樹上的插入n”);

printf(“4------------------二叉排序樹上的刪除n”);

printf(“5------------------二叉排序樹中序輸出n”);

printf(“6------------------退出n”);

scanf(“n%c”,&ch2);

switch(ch2)

{case '1':t=createbst();break;

case '2':printf(“n請輸入要查找的數據：”);

scanf(“n%d”,&key);

searchbst(t,key);

printf(“查找操作完畢。n”);break;

case '3': printf(“n請輸入要插入的數據：”);

scanf(“n%d”,&key);

insertbst(&t,key);

printf(“插入操作完畢。n”);break;

case '4': printf(“n請輸入要刪除的數據：”);

scanf(“n%d”,&key);

delbstnode(&t,key);

printf(“刪除操作完畢。n”);break;

case '5': inorderbst(t);

printf(“n二叉排序樹輸出完畢。n”);break;

case '6':ch1='n';break;

default:ch1='n';

}

}

}

bstree createbst(void)

{bstree t;

keytype key;

t=null;

printf(“請輸入一個關鍵字(輸入0時結束輸入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“請輸入下一個關鍵字(輸入0時結束輸入)：n”);scanf(“n%d”,&key);

}

return t;

}

void searchbst(bstree t, keytype key)

{ bstnode *p=t;

while(p)

{if(p->key==key)

{printf(“已找到n”);

return;

}

p=(key

key)? p->lchild:p->rchild;

}

printf(“沒有找到n”);

}

void insertbst(bstree *t,keytype key)

{bstnode *f,*p;

p=(*t);

while(p)

{if(p->key==key)

{printf(“樹中已有key不需插入n”);

return;

}

f=p;

p=(key

key)?p->lchild:p->rchild;

}

p=(bstnode*)malloc(sizeof(bstnode));

p->key=key;

p->lchild=p->rchild=null;

if((*t)==null)(*t)=p;

else if(key

key)f->lchild=p;

}/*insertbst*/

void delbstnode(bstree *t,keytype key)

{bstnode *parent=null, *p, *q,*child;

p=*t;

while(p)

{if(p->key==key)break;

parent=p;

p=(key

key)?p->lchild:p->rchild;

}

if(!p){printf(“沒有找到要刪除的結點n”);return;}

q=p;

if(q->lchild && q->rchild)

for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;

if(!parent)*t=child;

else {if(p==parent->lchild)

parent->lchild=child;

else parent->rchild=child;

if(p!=q)

q->key=p->key;

}

free(p);

}

void inorderbst(bstree t){ if(t!=null)

{inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);}

}

數據結構讀書筆記5000篇五

《數據結構與算法》教學大綱

課程編號：030816 適用專業：教育技術學 總學時數：64

學 分：4 編制單位：茂名學院理學院教育與信息技術系 編制時間：2008年6月20日

一、課程地位、性質和任務

《數據結構與算法》課程是計算機相關學科專業的基礎課程中的一門重要的核心課程。通過本課程的教學，使學生知道求解非數值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據問題設計和選擇好的算法，為學習后續的操作系統、編譯原理和軟件工程等專業課程，設計應用程序打下基礎。

本課程以提高學生的計算機應用能力和綜合素質為目標，通過課程教學，為學生構建數據結構與算法方面的知識體系，使學生一方面能夠根據問題選擇合適的數據結構，設計高效的算法，提高程序設計能力，另一方面，在工程應用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學生的程序設計能力。

二、與其他課程的關系

先修課：程序設計基礎、離散數學、計算機組成原理、計算機文化基礎

三、教學內容、課時安排和基本要求

（一）教學部分 第1章 緒論（2學時）1.1什么是數據結構 1.2 基本概念和術語

1.3 抽象數據類型的表示與實現

1.4 算法和算法分析（算法及其設計的要求，算法效率的度量，算法的存儲空間需求）1.5 問題求解

基本要求：

了解：抽象數據類型，算法設計方法與算法分析。

掌握：數據與數據結構、算法的基本概念；問題求解的方法與步驟 重點：數據結構和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟 難點：評價算法的標準和評價方法，最壞情況和平均情況的區分。

第2章 線性表（8學時）2.1 線性表的類型定義 2.2 線性表的順序表示和實現

2.3 線性表的鏈式表示和實現（線性鏈表，循環鏈表，雙向鏈表）2.4 一元多項式的表示及相加

基本要求：

了解：兩種存儲結構（順序存儲結構和鏈式存儲結構）及一元多項式的表示及相加。

掌握：要求熟練掌握處理線性表的各種算法。為后繼章節的學習打基礎。重點：各種算法。難點：鏈表的理解。

第3章 棧與隊列（4學時）

3.1 棧（定義，棧的表示和實現）

3.2 棧的應用舉例（數制轉換，括號匹配的檢驗，行編輯程序，迷宮求解，表達式求值）

3.3 棧與遞歸的實現

3.4 隊列及其實現（定義，鏈隊列，循環隊列）3.5 *離散事件模擬

教學要求：熟練掌握棧和隊列的特性和在不同存儲結構前提下的算法實現。棧和隊列是表最基本和重要的數據結構，是數據結構課程的基礎。

基本要求：

了解： 棧和隊列的定義及其實現。

掌握： 熟練掌握棧和隊列的特性和在不同存儲結構前提下的算法實現。重點： 棧和隊列的算法實現。難點： 棧和隊列的算法實現。

第4章 串（2學時）4.1 串類型的定義

4.2 串的表示和實現（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3 串的模式匹配算法（求子串位置的定位函數，模式匹配的一種改進算法）4.4 串操作應用舉例（文本編輯，建立詞索引表）

基本要求：

了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應用。

第5章 數組（2學時）5.1 數組的定義

5.2 數組的順序表示和實現

5.3 矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲結構 5.6 m元多項式的表示

5.7 廣義表的遞歸算法（求廣義表的深度，復制廣義表，建立廣義表的存儲結構）

基本要求：

了解：了解作為抽象數據類型的數組和c語言的數組。認識到數組可以作為順序存儲結構用于順序表、字符串和稀疏矩陣的實現。也可以采用鏈式存儲結構。

掌握：掌握基本概念和算法。重點：算法。

難點：廣義表的遞歸算法。

第6章 樹與二叉樹（15學時）6.1 樹的定義和基本術語

6.2 二叉樹（二叉樹的定義，二叉樹的性質，二叉樹的存儲結構）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹）

6.4 樹和森林（樹的存儲結構，森林與二叉樹的轉換，樹和森林的遍歷）6.5 樹與等價問題

6.6 赫夫曼樹及其應用（最優二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計數

基本要求：

了解：理解樹與森林的定義與術語。

掌握：熟練掌握二叉樹性質和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。掌握哈夫曼樹構造的方法和算法。重點： 樹的存儲結構和遍歷算法。難點：哈夫曼樹構造的方法和算法

第7章 圖（11學時）7.1 圖的定義和術語

7.2 圖的存儲結構（數組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優先搜索，廣度優先搜索）

7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強連通分量，最小生成樹，關節點和重連通分量）

7.5 有向無環圖及其應用（拓撲排序，關鍵路徑）

7.6 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求：

了解：圖的基本概念和相關術語。

掌握：圖的兩種主要存儲結構及遍歷算法。掌握最小生成樹、最短路徑和活動網算法的思想。

重點：圖的兩種主要存儲結構及遍歷算法。難點：圖的遍歷算法，最短路徑算法。

第8章 查找（8學時）

9.1 靜態查找表（順序表，有序表，靜態樹表，索引順序表）9.2 動態查找表（二叉排序樹和平衡二叉樹，b_樹和b+樹，鍵樹）9.3 哈希表（定義，構造方法，處理沖突的方法，查找及其分析）

基本要求：

了解： 各種查找法的基本概念及實現的基本思想。

掌握：熟練掌握搜索結構的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點：各種算法的基本思想及實現。難點：哈希表查找算法。

第9章 內部排序（8學時）10.1 概述

10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序

10.6 基數排序（多關鍵字，鏈式）10.7 排序算法分析

基本要求：

了解：基數排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點：內部排序算法

難點：基數排序（多關鍵字，鏈式）

第10章 *外部排序（2學時）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實現 11.4 置換-選擇排序 11.5 最佳歸并樹

基本要求：

了解：外部排序的基本概念和相關術語。

掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點：外部排序算法 難點：多路平衡歸并的實現 第11章 算法設計的一般方法（2學時）

1．重點

（1）有效算法的概念，問題固有難度的概念；

（2）遞歸法；分治法；平衡原則；貪心法；動態規劃的基本原理；（3）搜索-回溯法的基本原理和本質.2．難點

（1）問題固有難度的概念；

（2）遞歸分治法的效率分析（寫出時間耗費的遞推式，并求解）；（3）動態規劃法中的狀態轉移方程的確定。

（二）實驗、實習部分

課程安排五個類別的實驗，實驗時數為12課時，其中： 實驗

一、線性鏈表及運算 2課時 實驗

二、棧和隊列 2課時 實驗

三、樹和二叉樹 4課時 實驗

四、圖及其應用 2課時 實驗

五、查找與排序 2課時

四、課程考核方式

閉卷考試70%、平時作業與實驗30%

五、建議教材和教學參考書 參考教材：

1、《數據結構》（c語言描述）高等教育出版社 耿國華主編

2、《數據結構》（c語言版）清華大學出版社 嚴蔚敏，吳偉民編者

3、《數據結構題集》（c語言版）清華大學出版社 嚴蔚敏，吳偉民編者

4、《數據結構》算法實現及解析（第二版）西安電子科技大學出版社 高一凡

六、說明

1、因課時安排少，教學內容多。建議采用多媒體教學。

2、由于本課程內容較多，在實際教學中可根據大綱內容，進行適當調整。