數(shù)據(jù)結(jié)構(gòu)課程總結(jié)和思考

1、XX大學(xué)數(shù)據(jù)結(jié)構(gòu)總結(jié)姓 名： 專業(yè)班級(jí)： 學(xué) 號(hào)： 任課教師： 完成時(shí)間： 2目錄 學(xué)習(xí)總結(jié)3 對(duì)赫夫曼樹的研究5 赫夫曼樹的基本定義5 赫夫曼樹的構(gòu)造5 動(dòng)態(tài)赫夫曼編碼的實(shí)現(xiàn) 11 對(duì)各類排序方法的總結(jié)16 學(xué)習(xí)感悟18 學(xué)習(xí)總結(jié)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前、一直以為數(shù)據(jù)結(jié)構(gòu)是一門新的語言、后來才知道學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了更加高效的的組織數(shù)據(jù)、設(shè)計(jì)出良好的算法，而算法則是一個(gè)程序的靈魂。經(jīng)過了一學(xué)期的數(shù)據(jù)結(jié)構(gòu)了，在期末之際對(duì)其進(jìn)行總結(jié)。首先，學(xué)完數(shù)據(jù)結(jié)構(gòu)我們應(yīng)該知道數(shù)據(jù)結(jié)構(gòu)講的是什么，數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的研究的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)處理對(duì)象以及它們之間關(guān)系和操作的學(xué)科。第一章主要介紹了相

2、關(guān)概念，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。其中，數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合。邏輯結(jié)構(gòu)分為四類：集合型、線性、樹形和圖形結(jié)構(gòu)，數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)和散列存儲(chǔ)四類。最后著重介紹算法性能分析，包括算法的時(shí)間性能分析以及算法的空間性能分析。第二章具體地介紹了順序表的定義、特點(diǎn)及其主要操作，如查找、插入和刪除的實(shí)現(xiàn)。需要掌握對(duì)它們的性能估計(jì)。包括查找算法的平均查找長度，插入與刪除算法中的對(duì)象平均移動(dòng)次數(shù)。鏈表中數(shù)據(jù)元素的存儲(chǔ)不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲(chǔ)區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動(dòng)元素，給算法的效率帶來較大的

3、提高。鏈表這一章中介紹了鏈表的節(jié)點(diǎn)結(jié)構(gòu)、靜態(tài)與動(dòng)態(tài)鏈表的概念、鏈表的基本運(yùn)算（如求表長、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。第三章介紹了堆棧與隊(duì)列這兩種運(yùn)算受限制的線性結(jié)構(gòu)。其基本運(yùn)算方法與順序表和鏈表運(yùn)算方法基本相同，不同的是堆棧須遵循“先進(jìn)后出”的規(guī)則，對(duì)堆棧的操作只能在棧頂進(jìn)行；而隊(duì)列要遵循“先進(jìn)先出”的規(guī)則，教材中列出了兩種結(jié)構(gòu)的相應(yīng)算法，如入棧、出棧、入隊(duì)、出隊(duì)等。在介紹隊(duì)列時(shí)，提出了循環(huán)隊(duì)列的概念，以避免“假溢出”的現(xiàn)象。算法上要求掌握進(jìn)棧、退棧、取棧頂元素、判棧空盒置空棧等五種操作及掌握使用元素個(gè)數(shù)計(jì)數(shù)器及少用一個(gè)元素

4、空間來區(qū)分隊(duì)列空、隊(duì)列滿的方法。第四章串和數(shù)組中，我們知道串是一種特殊的線性表，是由零個(gè)或多個(gè)任意字符組成的字符序列。串的儲(chǔ)存結(jié)構(gòu)分為緊縮模式和非緊縮模式?；具\(yùn)算需掌握求串長、串賦值、連接操作、求子串、串比較、串定位、串插入、串刪除、串替換等。第六章二叉樹的知識(shí)是重點(diǎn)內(nèi)容。在介紹有關(guān)概念時(shí)，提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲(chǔ)和鏈接存儲(chǔ)以及生成算法。重點(diǎn)介紹二叉樹的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹。二叉樹的應(yīng)用：基本算法、哈弗曼樹、二叉排序樹和堆排序。樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲(chǔ)

5、結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。第七章介紹了圖的概念及其應(yīng)用，圖的存儲(chǔ)結(jié)構(gòu)的知識(shí)點(diǎn)有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識(shí)點(diǎn)有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應(yīng)用。有向無環(huán)圖重點(diǎn)理解AOV網(wǎng)和拓?fù)渑判蚣捌渌惴?。最后兩章集體說明了查找和排序算法，查找教材上介紹了靜態(tài)查找表和哈希查找表，靜態(tài)查找表中介紹了順序查找、折半查找以及分塊查找。哈希法中，學(xué)習(xí)要點(diǎn)包括哈希函數(shù)的比較；解決地址沖突的線性探查法的運(yùn)用，平均探查次數(shù)；解決地址沖突的

6、二次哈希法的運(yùn)用。排序是使用最頻繁的一類算法，可分為內(nèi)部排序和外部排序。主要需要理解排序的基本概念，在算法上、需要掌握插入排序（包括直接插入排序算法、折半插入排序算法），交換排序（包括冒泡排序算法、快速排序遞歸算法）,選擇排序（包括直接選擇排序算法、堆排序算法）等。由于平時(shí)上機(jī)練習(xí)的少，對(duì)于教材中很多算法都掌握的不是很熟悉、不過這些都是可以彌補(bǔ)的，我會(huì)在剩下的時(shí)間中不斷練習(xí)書上給出的算法和練習(xí)，正如教材上說的，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，僅從書本上學(xué)習(xí)是不夠的，必須經(jīng)過大量的程序設(shè)計(jì)實(shí)踐，在實(shí)踐中體會(huì)構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計(jì)技術(shù)。以上就是我這學(xué)期對(duì)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的總結(jié)。 對(duì)赫夫曼樹的研究 赫夫曼

7、樹的基本定義 赫夫曼樹（ Huffman ）又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。首先需要弄清楚關(guān)于路徑和路徑長度的概念。樹中兩個(gè)結(jié)點(diǎn)之間的路徑由一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)的分支構(gòu)成。兩結(jié)點(diǎn)之間的路徑長度是路徑上分支的數(shù)目。樹的路徑長度是從根結(jié)點(diǎn)到每一個(gè)結(jié)點(diǎn)的路徑長度之和。 赫夫曼樹的構(gòu)造 （1）構(gòu)成初始集合對(duì)給定的n個(gè)權(quán)值W1,W2,W3,.,Wi,.,Wn構(gòu)成n棵二叉樹的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹均為空。（為方便在計(jì)算機(jī)上實(shí)現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列。） （2）選取左右子樹

8、在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。 （3）刪除左右子樹 從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。 （4）重復(fù)左右兩步 重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。 舉個(gè)例子 有個(gè)序列是(7,9,2,6,32,3,21,10)，求赫夫曼樹步驟一：把這些點(diǎn)都看成是一個(gè)只有根結(jié)點(diǎn)的樹的集合F步驟二：選2個(gè)值最小的樹 步驟三：在這些樹的集合F中刪除這2棵樹 然后把2,3 構(gòu)成一顆二叉樹 變成了 （5 = 2 + 3） 然后把這個(gè)樹加入到集合F 5代表這棵樹的權(quán)值然后繼續(xù)上述步驟 選擇5和6

9、，把這2個(gè)構(gòu)成二叉樹。如下圖： 在F中刪除5、6 ，并加入11這棵樹，變成了：繼續(xù)上述步驟選7 和 9在F中刪除7 和9，并加入16這棵樹，則數(shù)變成了： 繼續(xù)上述步驟選 10 和11在F中刪除10 和11 加入21這棵樹繼續(xù)上述步驟選16和21 ，構(gòu)成二叉樹 在F中刪除這16和21這兩棵樹，加入37這棵樹繼續(xù)上述步驟選21和32，構(gòu)成二叉樹在F中刪除21和32這2兩棵樹，加入53這棵樹 還是繼續(xù)上面步驟把F中的兩棵樹合并成一棵樹赫夫曼樹就構(gòu)造完成了。 動(dòng)態(tài)赫夫曼編碼的實(shí)現(xiàn) 所謂動(dòng)態(tài)赫夫曼編碼，指的就是每一個(gè)結(jié)點(diǎn)的權(quán)是不定的，那么在實(shí)現(xiàn)時(shí)，就以從鍵盤輸入結(jié)點(diǎn)個(gè)數(shù)及權(quán)的值作為參考，實(shí)現(xiàn)動(dòng)態(tài)赫夫曼編

10、碼。其主要思想及其過程都在下面的程序中體現(xiàn)。#include<iostream>#include<stdlib.h>#include<math.h>using namespace std;int mecou; /定義全局變量計(jì)碼長 class Huffman /構(gòu)造Huffman類public: int parent; /和的位置int value; /頻率值int prenum; /該數(shù)的初始位置int left; /和的左加數(shù)位置int right; /和的右加數(shù)位置;int main( ) void swap(Huffman &a,Huffma

11、n &b); int Partition(Huffman *a,int p,int r); void QuickSort(Huffman *a,int p,int r); void Hsort(Huffman *a,int n,int nl,int nr); float PHf(Huffman *a,int n,int (*c)3); void CPHf(Huffman *a,Huffman &b,int i); void Renew(Huffman *a,int n); float Unchange(int n,Huffman *a); Huffman p50; /定義類數(shù)組

12、 int copy503; /定義copy三維數(shù)組便于查詢 int num,n; /編碼長num，最后數(shù)組長為n float cnum,ucnum; /定義定長碼所需碼數(shù)總和，哈弗曼編碼所需碼數(shù)的總和 char f1,f2; /用于輸入,兩個(gè)符號(hào) printf"輸入字符數(shù)量：" /輸入所需參數(shù) cin>>num; n=2*num-1; cout<<"輸入"<<num<<"個(gè)字符出現(xiàn)的頻率：" cin>>f1; for(int i=1;i<=num;i+) /對(duì)類的各項(xiàng)賦

13、值 cin>>pi.value; pi.parent=0; pi.prenum=i; pi.left=0; pi.right=0; cin>>f2; cout<<"字符數(shù)量："<<num<<endl; cout<<"字符編號(hào)：" for(int i=1;i<=num;i+) cout<<i<<" " cout<<endl; cout<<"字符頻率：" for(int i=1;i<=nu

14、m;i+) cout<<pi.value<<" " cout<<endl; ucnum=Unchange(num); /得到定碼長所需的碼數(shù)總和 Hsort(p,n,1,num); /根據(jù)頻率值排序并循環(huán)添加和，再排序得到最終的序列 Renew(p,n); /把最終序列里的和結(jié)點(diǎn)與加數(shù)結(jié)點(diǎn)對(duì)應(yīng)便于向后找和結(jié)點(diǎn) cnum=PHf(p,n,copy); /輸出哈弗曼編碼后各編號(hào)的前綴碼，得到哈弗曼編碼所需總碼數(shù) cout<<"壓縮率為"<<cnum/ucnum<<endl; /輸出壓縮率

15、 system("pause");void Renew(Huffman *a,int n) /找到該值的左右加數(shù)將其的位置寫入加數(shù)的和 for(int i=3;i<=n;i+) /對(duì)排完序的數(shù)組進(jìn)行搜索 if(ai.left!=0&&aai.left.parent=0) /找到?jīng)]有完成對(duì)應(yīng)的和結(jié)點(diǎn)和它的加數(shù)結(jié)點(diǎn) aai.left.parent=i; /在其左加數(shù)結(jié)點(diǎn)的和位置寫入其現(xiàn)在的位置 aai.right.parent=i; /在其右加數(shù)結(jié)點(diǎn)的和位置寫入其現(xiàn)在的位置 void swap(Huffman &a,Huffman &b)/

16、交換a,b的類值int l;l=a.value;a.value=b.value;b.value=l;l=a.prenum;a.prenum=b.prenum;b.prenum=l;l=a.left;a.left=b.left;b.left=l;l=a.right;a.right=b.right;b.right=l;int Partition(Huffman *a,int p,int r) /根據(jù)類值中的頻率值由小到大排序int i=p;int j=r+1;int x=ap.value;while(true) while (a+i.value<x&&i<r);whil

17、e (a-j.value>x);if (i>=j) break;swap(ai,aj);swap(ap,aj);return j;void QuickSort(Huffman *a,int p,int r)/根據(jù)類值中的頻率值由小到大排序 if (p<r) int q=Partition(a,p,r);QuickSort(a,p,q-1); QuickSort(a,q+1,r);void Hsort(Huffman *a,int n,int nl,int nr) /根據(jù)類值中的頻率值由小到大排序，取最小的兩個(gè)數(shù)相加，/和放在數(shù)組最后，移動(dòng)指針繼續(xù)排序if(nr<n) Q

18、uickSort(a,nl,nr); a+nr.value=anl.value+anl+1.value; anr.left=nl; anr.right=nl+1; anr.parent=0; anr.prenum=nr; nl=nl+2; Hsort(a,n,nl,nr); void CPHf(Huffman *a,Huffman &b,int i) /輸出字符的前綴碼，得到碼數(shù)的長度值if(b.parent!=0) /當(dāng)該數(shù)的和位置上的數(shù)不為0時(shí)CPHf(a,ab.parent,b.parent); /找到它的和繼續(xù)遞歸mecou+; /編號(hào)i的前綴碼長度加1cout<<

19、(i+1)%2; /輸出編號(hào)i前綴碼中的一個(gè)碼1或0 float PHf(Huffman *a,int n,int (*c)3)int ave=0;int w=(n+1)/2; /得到編碼數(shù)，w=num for(int i=1;i<=n-1;i+)if(ai.prenum<=(n+1)/2) /通過類值的最初位置搜索需要編碼的數(shù)，排除他們的和 cai.prenum0=i; /將編碼值按其最初位置存放在三維數(shù)組C中，第一維放它在a的編號(hào)cai.prenum1=ai.value; /第二維存放其頻率 /c1:w0，c1:w1里存放1-w編號(hào)在a中的編號(hào)值和頻率值for(int i=1;

20、i<=w;i+)int e=ci0; /e等于第i個(gè)編碼在a上的位置ci0mecou=0; /清空mecou的值cout<<"第"<<i<<"個(gè)字符的前綴碼為："CPHf(a,ae,e); /調(diào)用CPHf輸出字符的前綴碼ci2=mecou; /第i個(gè)字符前綴碼的長度mecou，存放在ci2里 ave+=mecou*ci1; /編號(hào)的前綴碼長乘以頻率的總和 cout<<endl; float pp=(float)ave; /轉(zhuǎn)換類型 cout<<"使用變長碼編碼需要"&l

21、t;<pp<<"位"<<endl;return pp; /返回總碼數(shù)float Unchange(int n,Huffman *a) /得到定長編碼的總碼數(shù) float all=0; for(int i=1;i<=n;i+) all+=ai.value; /計(jì)算頻率和all float l=(int)(log(float)n)/log(2.0)+1)*all; /利用方程式計(jì)算定長碼所需編碼位數(shù) cout<<"使用定長碼編碼需要"<<l<<"位"<<e

22、ndl; return l; /返回定長碼所需碼數(shù)的總個(gè)數(shù) 對(duì)各類排序算法的總結(jié)1、快速排序（QuickSort） 快速排序是一個(gè)就地排序，分而治之，大規(guī)模遞歸的算法。從本質(zhì)上來說， 它是歸并排序的就地版本?？焖倥判蚩梢杂上旅嫠牟浇M成。（1） 如果不多于1個(gè)數(shù)據(jù)，直接返回。（2） 一般選擇序列最左邊的值作為支點(diǎn)數(shù)據(jù)。（3） 將序列分成2部分，一部分都大于支點(diǎn)數(shù)據(jù)，另外一部分都小于支點(diǎn)數(shù)據(jù)。（4） 對(duì)兩邊利用遞歸排序數(shù)列。 快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法，但是就通常情況而言，沒有比它更快的了?？焖倥判蚴?/p>

23、遞歸的，對(duì)于內(nèi)存非常有限的機(jī)器來說，它不是一個(gè)好的選擇。 2 歸并排序（MergeSort） 歸并排序先分解要排序的序列，從1分成2，2分成4，依次分解，當(dāng)分解到只有1個(gè)一組的時(shí)候，就可以排序這些分組，然后依次合并回原來的序列中，這樣就可以排序所有數(shù)據(jù)。合并排序比堆排序稍微快一點(diǎn)，但是需要比堆排序多一倍的內(nèi)存空間，因?yàn)樗枰粋€(gè)額外的數(shù)組。3 堆排序（HeapSort） 堆排序適合于數(shù)據(jù)量非常大的場合（百萬數(shù)據(jù)）。 堆排序不需要大量的遞歸或者多維的暫存數(shù)組。這對(duì)于數(shù)據(jù)量非常巨大的序列是合適的。比如超過數(shù)百萬條記錄，因?yàn)榭焖倥判?，歸并排序都使用遞歸來設(shè)計(jì)算法，在數(shù)據(jù)量非常大的時(shí)候，可能會(huì)發(fā)生堆棧

24、溢出錯(cuò)誤。 堆排序會(huì)將所有的數(shù)據(jù)建成一個(gè)堆，最大的數(shù)據(jù)在堆頂，然后將堆頂數(shù)據(jù)和序列的最后一個(gè)數(shù)據(jù)交換。接下來再次重建堆，交換數(shù)據(jù)，依次下去，就可以排序所有的數(shù)據(jù)。4 Shell排序（ShellSort） Shell排序通過將數(shù)據(jù)分成不同的組，先對(duì)每一組進(jìn)行排序，然后再對(duì)所有的元素進(jìn)行一次插入排序，以減少數(shù)據(jù)交換和移動(dòng)的次數(shù)。平均效率是O(nlogn)。其中分組的合理性會(huì)對(duì)算法產(chǎn)生重要的影響?，F(xiàn)在多用D.E.Knuth的分組方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相對(duì)比較簡單，

25、它適合于數(shù)據(jù)量在5000以下并且速度并不是特別重要的場合。它對(duì)于數(shù)據(jù)量較小的數(shù)列重復(fù)排序是非常好的。5 插入排序（InsertSort） 插入排序通過把序列中的值插入一個(gè)已經(jīng)排序好的序列中，直到該序列的結(jié)束。插入排序是對(duì)冒泡排序的改進(jìn)。它比冒泡排序快2倍。一般不用在數(shù)據(jù)大于1000的場合下使用插入排序，或者重復(fù)排序超過200數(shù)據(jù)項(xiàng)的序列。6 冒泡排序（BubbleSort） 冒泡排序是最慢的排序算法。在實(shí)際運(yùn)用中它是效率最低的算法。它通過一趟又一趟地比較數(shù)組中的每一個(gè)元素，使較大的數(shù)據(jù)下沉，較小的數(shù)據(jù)上升。它是O(n2)的算法。7 交換排序（ExchangeSort）和選擇

26、排序（SelectSort） 這兩種排序方法都是交換方法的排序算法，效率都是 O(n2)。在實(shí)際應(yīng)用中處于和冒泡排序基本相同的地位。它們只是排序算法發(fā)展的初級(jí)階段，在實(shí)際中使用較少。8 基數(shù)排序（RadixSort） 基數(shù)排序和通常的排序算法并不走同樣的路線。它是一種比較新穎的算法，但是它只能用于整數(shù)的排序，如果我們要把同樣的辦法運(yùn)用到浮點(diǎn)數(shù)上，我們必須了解浮點(diǎn)數(shù)的存儲(chǔ)格式，并通過特殊的方式將浮點(diǎn)數(shù)映射到整數(shù)上，然后再映射回去，這是非常麻煩的事情，因此，它的使用同樣也不多。而且，最重要的是，這樣算法也需要較多的存儲(chǔ)空間。9 總結(jié) 排序法 平均時(shí)間最差情形穩(wěn)定度額外空間備注冒泡 O(n2)  O(n2) 穩(wěn)定O(1)n小時(shí)較好交換  O(n2)  O(n2)不穩(wěn)定O(1)n小時(shí)較好選擇 O(n2)&#