數(shù)據(jù)結(jié)構(gòu)圖總結(jié)(五篇)

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)圖總結(jié)(五篇)當(dāng)工作或?qū)W習(xí)進(jìn)行到一定階段或告一段落時(shí)，需要回過(guò)頭來(lái)對(duì)所做的工作認(rèn)真地分析研究一下，確定成績(jī)，找出問(wèn)題，歸納出經(jīng)驗(yàn)教訓(xùn)，提高認(rèn)識(shí)，明確方向，以便進(jìn)一步做好工作，并把這些用文字表述出來(lái)，就叫做總結(jié)。怎樣寫(xiě)總結(jié)才更能起到其作用呢？總結(jié)應(yīng)當(dāng)怎么寫(xiě)呢？下面是我為大家?guī)?lái)的總結(jié)書(shū)優(yōu)秀范文，希望大家可以喜歡。

key)f-lchild=p;數(shù)據(jù)結(jié)構(gòu)圖總結(jié)篇三

數(shù)據(jù)結(jié)構(gòu)參考題目

一、選擇

1.假使在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼，則該結(jié)構(gòu)是（）

a.棧b.隊(duì)列c.樹(shù)d.圖2.下面程序段的時(shí)間繁雜度為（）for(i=0;inext=hl;b.p-next=hl;hl=p;c.p-next=hl;p=hl;d.p-next=hl-next;hl-next=p;4.兩個(gè)字符串相等的條件是（）

c.都是非空串d.串的長(zhǎng)度相等且對(duì)應(yīng)的字符一致5．若以s和x分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的棧可以進(jìn)行的棧操作系列是（）

xxsxsxxx6.已知一棵含50個(gè)結(jié)點(diǎn)的二叉樹(shù)中只有一個(gè)葉子結(jié)點(diǎn)，則該樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù)為（）a.0b.1c.48d.497.已知用某種排序方法對(duì)關(guān)鍵字序列（51，35，93，24，13，68，56，42，77）進(jìn)行排序時(shí)，前兩趟排序的結(jié)果為

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

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

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

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

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

-1+1d.n11．從規(guī)律關(guān)系來(lái)看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（）a線性結(jié)構(gòu)b.樹(shù)形結(jié)構(gòu)c.線性結(jié)構(gòu)和樹(shù)型結(jié)構(gòu)d.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)

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

a．棧頂b.棧底c.任意位置d指定位置13．由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）a.24b.71c.48d.5314．一個(gè)棧的輸入序列為123，則以下序列中不可能是棧的輸出序列的是()a.231b.321c.312d.12315．關(guān)于棧和隊(duì)列的說(shuō)法中正確的是（）

a．棧和隊(duì)列都是線性結(jié)構(gòu)b.棧是線性結(jié)構(gòu)，隊(duì)列不是線性結(jié)構(gòu)c.棧不是線性結(jié)構(gòu)，隊(duì)列是線性結(jié)構(gòu)d.棧和隊(duì)列都不是線性結(jié)構(gòu)16．關(guān)于存儲(chǔ)一致數(shù)據(jù)元素的說(shuō)法中正確的是（）a．順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)少占空間b.順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)多占空間

c.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)都要求占用整塊存儲(chǔ)空間d.鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)難于擴(kuò)展空間

17．已知一個(gè)單鏈表中，指針q指向指針p的前趨結(jié)點(diǎn)，若在指針q所指結(jié)點(diǎn)和指針p所指結(jié)點(diǎn)之間插入指針s所指結(jié)點(diǎn)，則需執(zhí)行（）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．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數(shù)為h(key)=keymod13，則它的開(kāi)散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）a.1b.2c.3d.419．執(zhí)行下面程序段時(shí)，s語(yǔ)句被執(zhí)行的次數(shù)為：（）for(inti=1;i=n;i++)for(intj=1;j=i;j++)s;a.n*nb.n*n/2c.n(n+1)d.n(n+1)/220．在長(zhǎng)度為n的線性表中刪除一個(gè)指針p所指結(jié)點(diǎn)的時(shí)間繁雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設(shè)一個(gè)棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過(guò)程中允許出棧）不可能出現(xiàn)的是（）

a.a，b，c，db.a，b，d，cc.d，c，b，ad.c，d，a，b22．關(guān)于串的表達(dá)中，正確的是（）a．空串是只含有零個(gè)字符的串b.空串是只含有空格字符的串

c.空串是含有零個(gè)字符或含有空格字符的串

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

23．在具有m個(gè)單元的循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，則隊(duì)滿的條件是（）

a．front==rear

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

+1==front

d.(rear+1)%m==front24．設(shè)有二維數(shù)組

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

a．i*(i-1)/2b.i*(i+1)/2c.(i+2)*(i+1)/225．高度為h的完全二叉樹(shù)中，結(jié)點(diǎn)數(shù)最多為（）

ha．2h-1b.2h+1c.2-1d.2h26．由m棵結(jié)點(diǎn)數(shù)為n的樹(shù)組成的森林，將其轉(zhuǎn)化為一棵二叉樹(shù)，則該二叉樹(shù)中根結(jié)點(diǎn)的右子樹(shù)上具有的結(jié)點(diǎn)個(gè)數(shù)是（）

-1c.n(m-1)d.m(n-1)27．在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，每個(gè)頂點(diǎn)度的最大值為（）a.nb.n-1c.n+1d.2(n-1)28．關(guān)于無(wú)向圖的鄰接矩陣的說(shuō)法中正確的是（）a.矩陣中非全零元素的行數(shù)等于圖中的頂點(diǎn)數(shù)

b.第i行上與第i列上非零元素總和等于頂點(diǎn)vi的度數(shù)c.矩陣中的非零元素個(gè)數(shù)等于圖的邊數(shù)

d.第i行上非零元素個(gè)數(shù)和第i列上非零元素個(gè)數(shù)一定相等

29．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為h(key)=keymod13，則它的開(kāi)散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）a.1b.2c.3d.430．設(shè)有一組初始關(guān)鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個(gè)關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）

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

二、填空題

1.數(shù)據(jù)是計(jì)算機(jī)加工處理的對(duì)象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的規(guī)律結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面()。

3.線性表是由n≥0個(gè)一致類(lèi)型組成的有限序列（）。4.棧是一種后進(jìn)先出的線性表（）。

5.從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，只能找到它的后繼結(jié)點(diǎn)，不能找到它的前驅(qū)結(jié)點(diǎn)（）。6.單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡(jiǎn)化運(yùn)算（）。7.樹(shù)的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)（）。8.組成數(shù)據(jù)的基本單位稱(chēng)為數(shù)據(jù)元素（）。

9.從非循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，既能找到它的后繼結(jié)點(diǎn)，又能找到它的前驅(qū)結(jié)點(diǎn)（）。

10.單鏈表結(jié)點(diǎn)的指針域是用來(lái)存放其直接后繼結(jié)點(diǎn)的首地址的（）

11.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的規(guī)律結(jié)構(gòu)的存儲(chǔ)映象（）。

12.用順序表來(lái)存儲(chǔ)線性表時(shí)，不需要另外開(kāi)拓空間來(lái)保存數(shù)據(jù)元素之間的相互關(guān)系（）。

13.在非線性結(jié)構(gòu)中，至少存在一個(gè)元素不止一個(gè)直接前驅(qū)或不止一個(gè)直接后驅(qū)（）。14.樹(shù)的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)（）。15.隊(duì)列的特點(diǎn)是先進(jìn)先出（）。

16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹(shù)（）。17.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)（）。18.線性表簡(jiǎn)稱(chēng)為〞順序表〞。（）

19.對(duì)數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）。20.從循環(huán)單鏈表的任一結(jié)點(diǎn)出發(fā)，可以找到表中的所有結(jié)點(diǎn)（）。21.棧是一種先進(jìn)先出的線性表（）。22.鏈表的主要缺點(diǎn)是不能隨機(jī)訪問(wèn)（）。23.二叉樹(shù)是樹(shù)的特別形式（）。24.冒泡排序法是穩(wěn)定的排序（）。25.算法是對(duì)解題方法和步驟的描述（）。26.算法可以用任意的符號(hào)來(lái)描述（）。

27.數(shù)據(jù)的規(guī)律結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型（）。

28.線性表的順序存儲(chǔ)方式是按規(guī)律次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）。29.棧是一種先進(jìn)后出的線性表（）。

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

三、畫(huà)圖題

1.請(qǐng)根據(jù)以下二元組畫(huà)出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)

k={15,11,20,8,14,13}r={15,11,15,20,11,8,11,14,14,13}2.請(qǐng)根據(jù)以下二元組畫(huà)出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)

k={a,b,c,d,e,f,g,h,i,j}r={,,,,,,,,}3．請(qǐng)根據(jù)以下二元組畫(huà)出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)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.請(qǐng)根據(jù)以下二元組畫(huà)出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)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）}

四、運(yùn)算題

1．已知一個(gè)圖的頂點(diǎn)集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}；

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

2.一個(gè)線性表為b=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為ht[0..12]，散列函數(shù)為h（key）=key%13并用線性探查法解決沖突，請(qǐng)畫(huà)出散列表，并計(jì)算等概率狀況下查找成功的平均查找長(zhǎng)度。

平均查找長(zhǎng)度：（寫(xiě)出計(jì)算過(guò)程）

3．已知一個(gè)圖的頂點(diǎn)集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}；

依照普里姆算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。（從頂點(diǎn)2出發(fā)）

____

__，___

_，___

___，__

____，______，______，______。4.寫(xiě)出下圖所示的二叉樹(shù)的前中后序遍歷結(jié)果：

前序：中序：后序：

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

五、編程題

1.請(qǐng)編寫(xiě)一個(gè)算法，實(shí)現(xiàn)十進(jìn)制整數(shù)與二進(jìn)制數(shù)的轉(zhuǎn)換。voidshi_to_er(unsignedx){2.寫(xiě)出二分法查找的算法：

intsearch_bin(keytypek,sstablest){3.請(qǐng)編寫(xiě)一個(gè)算法，實(shí)現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點(diǎn)）。linklist*invertlink(linklist*h){

數(shù)據(jù)結(jié)構(gòu)圖總結(jié)篇四

試驗(yàn)：線性表的基本操作

學(xué)習(xí)把握線性表的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的設(shè)計(jì)與操作。對(duì)順序表建立、插入、刪除的基本操作，對(duì)單鏈表建立、插入、刪除的基本操作算法。

1.順序表的實(shí)踐

1)建立4個(gè)元素的順序表s=sqlist[]={1，2，3，4，5}，實(shí)現(xiàn)順序表建立的基本操作。

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

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

3.1)建立一個(gè)包括頭結(jié)點(diǎn)和4個(gè)結(jié)點(diǎn)的（5，4，2，1）的單鏈表，實(shí)現(xiàn)單鏈表建立的基本操作。

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

3)在已建好的單鏈表中的指定位置（i=3）插入一個(gè)結(jié)點(diǎn)3，實(shí)現(xiàn)單鏈表插入的基本操作。

4)在一個(gè)包括頭結(jié)點(diǎn)和5個(gè)結(jié)點(diǎn)的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個(gè)結(jié)點(diǎn)，實(shí)現(xiàn)單鏈表刪除的基本操作。5)實(shí)現(xiàn)單鏈表的求表長(zhǎng)操作。

1.開(kāi)啟vc++。

2.建立工程：點(diǎn)file-new，選project標(biāo)簽，在列表中選win32consoleapplication，再在右邊的框里為工程起好名字，選好路徑，點(diǎn)ok-finish。至此工程建立完畢。

3.創(chuàng)立源文件或頭文件：點(diǎn)file-new，選file標(biāo)簽，在列表里選c++sourcefile。給文件起好名字，選好路徑，點(diǎn)ok。至此一個(gè)源文件就被添加到了你剛創(chuàng)立的工程之中。

4．寫(xiě)好代碼

5．編譯－＞鏈接－＞調(diào)試

線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中，碰見(jiàn)的第一個(gè)數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點(diǎn)把握順序表和單鏈表的各種算法和時(shí)間性能分析。線性表右兩種存儲(chǔ)方式即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。通過(guò)學(xué)習(xí)我知道了對(duì)線性表進(jìn)行建立、插入、刪除，同時(shí)單鏈表也是進(jìn)行建立、插入、刪除。而對(duì)于順序表的插入刪除運(yùn)算，其平均時(shí)間繁雜度均為0（n）.通過(guò)這次的學(xué)習(xí)，把握的太熟練，主要是課本上的知識(shí)點(diǎn)沒(méi)有完全的理解，回去我會(huì)多看書(shū)，理解重要的概念?？傊?，這次試驗(yàn)我找到了自己的不足之處，以后會(huì)努力的。

試驗(yàn)二：棧的表示與實(shí)現(xiàn)及棧的應(yīng)用

（1）把握棧的順序存儲(chǔ)結(jié)構(gòu)及其基本操作的實(shí)現(xiàn)。（2）把握棧后進(jìn)先出的特點(diǎn)，并利用其特性在解決實(shí)際問(wèn)題中的應(yīng)用。（3）把握用遞歸算法來(lái)解決一些問(wèn)題。

1.編寫(xiě)程序，對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，輸出與其等值的八進(jìn)制數(shù)。

2.編寫(xiě)遞歸程序，實(shí)現(xiàn)n！的求解。3.編寫(xiě)遞歸程序，實(shí)現(xiàn)以下函數(shù)的求解。

n,n0,1fib(n)fib(n1)fib(n2),n1

4.編寫(xiě)程序，實(shí)現(xiàn)hanoi塔問(wèn)題。1.開(kāi)啟vc++。

2.建立工程：點(diǎn)file-new，選project標(biāo)簽，在列表中選win32consoleapplication，再在右邊的框里為工程起好名字，選好路徑，點(diǎn)ok-finish。至此工程建立完畢。

3.創(chuàng)立源文件或頭文件：點(diǎn)file-new，選file標(biāo)簽，在列表里選c++sourcefile。給文件起好名字，選好路徑，點(diǎn)ok。至此一個(gè)源文件就被添加到了你剛創(chuàng)立的工程之中。

4．寫(xiě)好代碼

5．編譯－＞鏈接－＞調(diào)試

通過(guò)這次的學(xué)習(xí)我把握了棧這種抽象數(shù)據(jù)類(lèi)型的特點(diǎn)，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它；總的來(lái)說(shuō)，棧是操作受限的線性表，是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對(duì)棧來(lái)說(shuō)，表尾端有其特別含義，稱(chēng)為棧頂（top），相應(yīng)地，表頭端稱(chēng)為棧底（botton）；棧又稱(chēng)為后進(jìn)先出（lastinfirstout）的線性表,簡(jiǎn)稱(chēng)lifo結(jié)構(gòu)，由于它的修改是按后進(jìn)先出的原則進(jìn)行的。

加上這個(gè)試驗(yàn)，我已經(jīng)學(xué)了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對(duì)以后的學(xué)習(xí)有很大的作用，可以說(shuō)這是學(xué)習(xí)以后知識(shí)的總要基礎(chǔ)。

試驗(yàn)三：二叉樹(shù)的建立及遍歷

（1）把握利用先序序列建立二叉樹(shù)的二叉鏈表的過(guò)程。（2）把握二叉樹(shù)的先序、中序和后序遍歷算法。

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

并顯示其先序序列為：abcde中序序列為：cbaed后序序列為：cbeda1.開(kāi)啟vc++。

2.建立工程：點(diǎn)file-new，選project標(biāo)簽，在列表中選win32consoleapplication，再在右邊的框里為工程起好名字，選好路徑，點(diǎn)ok-finish。至此工程建立完畢。

3.創(chuàng)立源文件或頭文件：點(diǎn)file-new，選file標(biāo)簽，在列表里選c++sourcefile。給文件起好名字，選好路徑，點(diǎn)ok。至此一個(gè)源文件就被添加到了你剛創(chuàng)立的工程之中。

4．寫(xiě)好代碼

5．編譯－＞鏈接－＞調(diào)試

這次試驗(yàn)是關(guān)于二叉樹(shù)的常見(jiàn)操作，主要是二叉樹(shù)的建立和遍歷，在這次試驗(yàn)中我按先序方式建立二叉樹(shù)的，而遍歷方式則相對(duì)要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹(shù)高度和葉子個(gè)數(shù)的計(jì)算和遍歷相差不大，只是加些判斷條件，總體來(lái)說(shuō)，本次試驗(yàn)不太好做，期間出現(xiàn)了好多規(guī)律錯(cuò)誤，變量初始化的問(wèn)題等，不過(guò)經(jīng)過(guò)細(xì)心排查最終都一一解決了。

試驗(yàn)四：查找與排序

（1）把握折半查找算法的實(shí)現(xiàn)。（2）把握冒泡排序算法的實(shí)現(xiàn)。

1.編寫(xiě)折半查找程序，對(duì)以下數(shù)據(jù)查找37所在的位置。5，13，19，21，37，56，64，75，80，88，922.編寫(xiě)冒泡排序程序，對(duì)以下數(shù)據(jù)進(jìn)行排序。49，38，65，97，76，13，27，491.開(kāi)啟vc++。

2.建立工程：點(diǎn)file-new，選project標(biāo)簽，在列表中選win32consoleapplication，再在右邊的框里為工程起好名字，選好路徑，點(diǎn)ok-finish。至此工程建立完畢。

3.創(chuàng)立源文件或頭文件：點(diǎn)file-new，選file標(biāo)簽，在列表里選c++sourcefile。給文件起好名字，選好路徑，點(diǎn)ok。至此一個(gè)源文件就被添加到了你剛創(chuàng)立的工程之中。

4．寫(xiě)好代碼

5．編譯－＞鏈接－＞調(diào)試

（1）查找算法的代碼如下所示：#include“stdio.h〞#include“malloc.h〞#defineoverflow-1#defineok1#definemaxnum100#definen10typedefintelemtype;typedefintstatus;typedefstruct{

elemtype*elem;

intlength;}sstable;statusinitlist(sstablest){inti,n;

=

(elemtype*)

malloc(elemtype));

if(!)return(overflow);

printf(“輸入元素個(gè)數(shù)和各元素的值:〞);

scanf(“%dn〞,n);

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

(maxnum*sizeof

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

=n;

returnok;}intseq_search(sstablest,elemtypekey){

inti;

[0]=key;

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

returni;}intbinarysearch(sstablest,elemtypekey){

intmid,low,high,i=1;

low=1;

high=;

while(low=high)

{

mid=(low+high)/2;

if([mid]==key)

returnmid;

elseif(keyhigh=mid-1;

else

}

return0;}voidmain(){sstablest;initlist(st);

elemtypekey;intn;printf(“key=〞);

scanf(“%d〞,key);

printf(“nn〞);

/*printf(“afterseqsearch::〞);

n=seq_search(st,key);

printf(“positionisin%dnn〞,n);*/

printf(“afterbinarysearch::〞);

n=binarysearch(st,key);

low=mid+1;if(n)printf(“positionisin%dnn〞,n);else

}試驗(yàn)結(jié)果如下所示：

（2）排序算法的代碼如下所示：#include“stdio.h〞#include“malloc.h〞#defineoverflow-1#defineok1#definemaxnum100#definen10typedefintelemtype;typedefintstatus;typedefstruct{

elemtype*elem;

intlength;}sstable;statusinitlist(sstablest)printf(“notinnn〞);{inti,n;

(elemtype));

if(!)return(overflow);

printf(“輸入元素個(gè)數(shù)和各元素的值:〞);

scanf(“%dn〞,n);

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

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

=n;

returnok;}voidsort(sstablest){

inti,j,t;

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

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

(elemtype*)

malloc

(maxnum*sizeof

}

}[i]=[j];[j]=t;voiddisplay(sstablest){inti;

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

printf(“%d

〞,[i]);}

}voidmain(){

sstablest;initlist(st);intn;printf(“beforesort::n〞);display(st);sort(st);printf(“naftersort::n〞);display(st);}試驗(yàn)結(jié)果如下所示：

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

數(shù)據(jù)結(jié)構(gòu)圖總結(jié)篇五

一、基本概念

1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。

2、數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。

3、數(shù)據(jù)結(jié)構(gòu)的

規(guī)律結(jié)構(gòu)（抽象的，與實(shí)現(xiàn)無(wú)關(guān)）

物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）順序映像（順序存儲(chǔ)結(jié)構(gòu)）位置“相鄰〞非順序映像（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）指針表示關(guān)系

4、算法特性：算法具有正確性、有窮性，確定性，（可行性）、輸入，輸出正確性：能按設(shè)計(jì)要求解決具體問(wèn)題，并得到正確的結(jié)果。

有窮性：任何一條指令都只能執(zhí)行有限次，即算法必需在執(zhí)行有限步后終止。確定性：算法中每條指令的含義必需明確，不允許由二義性

可行性：算法中待執(zhí)行的操作都十分基本，算法應(yīng)當(dāng)在有限時(shí)間內(nèi)執(zhí)行完畢。

輸入：一個(gè)算法的輸入可以包含零個(gè)或多個(gè)數(shù)據(jù)。輸出：算法有一個(gè)或多個(gè)輸出

5、算法設(shè)計(jì)的要求：

（1）正確性：算法應(yīng)能滿足設(shè)定的功能和要求。（2）可讀性：思路明了、層次明顯、易讀易懂。

（3）健壯性：輸入非法數(shù)據(jù)時(shí)應(yīng)能作適當(dāng)?shù)姆磻?yīng)和處理。

（4）高效性（時(shí)間繁雜度）：解決問(wèn)題時(shí)間越短，算法的效率就越高。（5）低存儲(chǔ)量（空間繁雜度）：完成同一功能，占用存儲(chǔ)空間應(yīng)盡可能少。

二、線性表

1、線性表list：最常用且最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。含有大量記錄的線性表稱(chēng)為文件。

2、線性表是n個(gè)數(shù)據(jù)元素的有限序列。

線性結(jié)構(gòu)的特點(diǎn)：①“第一個(gè)〞②“最終一個(gè)〞③前驅(qū)④后繼。

3、順序表——線性表的順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)

a)規(guī)律上相鄰的元素在物理位置上相鄰。b)隨機(jī)訪問(wèn)。

2)表長(zhǎng)為n時(shí)，線性表進(jìn)行插入和刪除操作的時(shí)間繁雜度為o（n），插入一個(gè)元素時(shí)大約移動(dòng)表中的一半元素，刪除一個(gè)元素時(shí)大約移動(dòng)表中的（n-1）2。

4、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1)類(lèi)型定義

簡(jiǎn)而言之，“數(shù)據(jù)+指針〞

2)不帶頭結(jié)點(diǎn)的空表判定為l==null帶頭結(jié)點(diǎn)的空表判定為l-next==null循環(huán)單鏈表為空的判定條件為==l線性鏈表的最終一個(gè)結(jié)點(diǎn)的指針為null頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?，指針域指向第一個(gè)元素的指針。

5、順序表和單鏈表的比較

6、順序存儲(chǔ)：優(yōu)點(diǎn)：存儲(chǔ)密度大，可隨機(jī)存儲(chǔ)

缺點(diǎn)：大小固定；不利于增減節(jié)點(diǎn);存儲(chǔ)空間不能充分利用；容量難擴(kuò)展鏈?zhǔn)酱鎯?chǔ)：優(yōu)點(diǎn)：易于插入刪除；可動(dòng)態(tài)申請(qǐng)空間；表容量?jī)H受內(nèi)存空間限制缺點(diǎn)：增加了存儲(chǔ)空間的開(kāi)銷(xiāo)；不可以隨機(jī)存儲(chǔ)元素

三、棧與隊(duì)列

1、棧

棧：限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧頂：表尾端棧底：表頭

棧是先進(jìn)后出的線性表。

插入棧頂元素稱(chēng)為入棧，刪除棧頂元素稱(chēng)為出棧。

類(lèi)似于順序表，插入和刪除操作固定于表尾。

3、隊(duì)列

先進(jìn)先出的線性表。隊(duì)尾入隊(duì)對(duì)頭出隊(duì)

允許插入的一端叫做隊(duì)尾允許刪除的一端叫做對(duì)頭

4、鏈隊(duì)列

1.樹(shù)的定義

樹(shù)（tree）：是n（n≥0）個(gè)有限數(shù)據(jù)元素的集合。在任意一棵非空樹(shù)t中：

（1）有且僅有一個(gè)特定的稱(chēng)為樹(shù)根（root）的結(jié)點(diǎn)，根結(jié)點(diǎn)無(wú)前趨結(jié)點(diǎn)；

（2）當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m(m0)個(gè)互不相交的集合t1，t2，?，tm，其中每一個(gè)集合ti（1≤i≤m）本身又是一棵樹(shù)，并且稱(chēng)為根的子樹(shù)。2.基本術(shù)語(yǔ)：

結(jié)點(diǎn)的度數(shù)：結(jié)點(diǎn)的非空子樹(shù)（即后綴）個(gè)數(shù)叫作結(jié)點(diǎn)的度數(shù)

樹(shù)葉、分支結(jié)點(diǎn)：左（右）子樹(shù)均為空二叉樹(shù)的結(jié)點(diǎn)稱(chēng)作樹(shù)葉否則稱(chēng)作分支結(jié)點(diǎn)。

結(jié)點(diǎn)的層數(shù)：規(guī)定根的層數(shù)是0，其余結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)的層數(shù)加1孩子和雙親：樹(shù)的深度：

樹(shù)的度數(shù)：樹(shù)中度數(shù)最大的結(jié)點(diǎn)度數(shù)叫作樹(shù)的度數(shù)樹(shù)林：是由零個(gè)或多個(gè)不相交的樹(shù)所組成的集合。3.二叉樹(shù)性質(zhì)：

1)二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。2)深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。滿二叉樹(shù)：深度為k，有2k-1個(gè)結(jié)點(diǎn)。

完全二叉樹(shù)：給滿二叉樹(shù)的結(jié)點(diǎn)編號(hào)，從上至下，從左至右，n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中結(jié)點(diǎn)在對(duì)應(yīng)滿二叉樹(shù)中的編號(hào)正好是從1到n。

3)葉子結(jié)點(diǎn)n0，度為2的結(jié)點(diǎn)為n2，則n0=n2+1?？紤]結(jié)點(diǎn)個(gè)數(shù)：n=n0+n1+n2考慮分支個(gè)數(shù)：n-1=2n2+n1可得n0=n2+1

5.遍歷二叉樹(shù)（先序dlr、中序ldr、后序lrd）方法與c語(yǔ)言描述

由二叉樹(shù)的遞歸定義可知，一棵二叉樹(shù)由根結(jié)點(diǎn)（d）、根結(jié)點(diǎn)的左子樹(shù)（l）和根結(jié)點(diǎn)的右子樹(shù)（r）三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹(shù)。一般有三種方法：先序(前序)遍歷dlr（根左右）、中序遍歷ldr（左根右）、后序遍歷lrd（左右根）。

7.樹(shù)和森林

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

雙親表示法，孩子表示法，孩子兄弟表示法。特點(diǎn)：雙親表示法簡(jiǎn)單求得雙親，但不簡(jiǎn)單求得孩子；孩子表示法簡(jiǎn)單求得孩子，但求雙親麻煩；兩者可以結(jié)合起來(lái)使用。孩子兄弟表示法，簡(jiǎn)單求得孩子和兄弟，求雙親麻煩，也可以增加指向雙親的指針來(lái)解決。

赫夫曼編碼(前綴碼)向左分支為0，向右分支為1，從根到葉子的路徑構(gòu)成葉子的前綴編碼。

五、圖1．

完全圖：有12n(n-1)條變得無(wú)向圖

有向完全圖：具有n（n-1）條弧的有向圖。權(quán)：與圖的邊或弧相關(guān)的數(shù)。

頂點(diǎn)v的度：和v相關(guān)聯(lián)的邊的數(shù)目。

入度：以頂點(diǎn)v為頭的弧的數(shù)目出度：以頂點(diǎn)v為尾的弧的數(shù)目回路或環(huán)：第一個(gè)頂點(diǎn)和最終一個(gè)頂點(diǎn)一致的路徑。

簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。

邊(弧)多則需要存儲(chǔ)空間多。

·十字鏈表：

十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)的一種鏈表。在十字鏈表中，對(duì)應(yīng)于有向圖中每一條弧有一個(gè)結(jié)點(diǎn)，對(duì)應(yīng)于每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)。

·鄰接多重表3.圖的遍歷

1)深度優(yōu)先（dfs）探尋

訪問(wèn)方式：從圖中某頂點(diǎn)v出發(fā)：a）訪問(wèn)頂點(diǎn)v；

b）從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷，若從某點(diǎn)出發(fā)所有鄰接點(diǎn)都已訪問(wèn)過(guò)，退回前一個(gè)點(diǎn)繼續(xù)上述過(guò)程，若退回開(kāi)始點(diǎn)，終止。2)廣度（寬度，bfs）優(yōu)先探尋a）訪問(wèn)頂點(diǎn)v；

b）訪問(wèn)同v相鄰的所有未被訪問(wèn)的鄰接點(diǎn)w1,w2,?wk；

c）依次從這些鄰接點(diǎn)出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn);依此類(lèi)推，直到圖中所有訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)；

4.生成樹(shù)和最小生成樹(shù)

每次遍歷一個(gè)連通圖將圖的邊分成遍歷所經(jīng)過(guò)的邊和沒(méi)有經(jīng)過(guò)的邊兩部分，將遍歷經(jīng)過(guò)的邊同圖的頂點(diǎn)構(gòu)成一個(gè)子圖，該子圖稱(chēng)為生成樹(shù)。因此有dfs生成樹(shù)和bfs生成樹(shù)。

1)最小生成樹(shù)

·kruskal算法

一句話，“不構(gòu)成環(huán)的狀況下，每次選取最小邊〞。

-網(wǎng)

用頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)的優(yōu)先關(guān)系的有向圖稱(chēng)為aov網(wǎng)。

拓?fù)渑判颍簩?duì)aov網(wǎng)絡(luò)中頂點(diǎn)構(gòu)造拓?fù)溆行蛐蛄械倪^(guò)程。拓?fù)渑判虻姆椒?1)在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之(2)從圖中刪除該頂點(diǎn)和所有以它為尾的弧6.關(guān)鍵路徑

aoe網(wǎng)，關(guān)鍵路徑

aoe網(wǎng)(activityonedge)——帶權(quán)的有向無(wú)環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間。在工程上常用來(lái)表示工程進(jìn)度計(jì)劃。

關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)的一條路徑，或者全部由關(guān)鍵活動(dòng)構(gòu)成的路徑。7.最短路徑

(1)迪杰斯特拉算法

求一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短路徑。

算法：(a)初始化：用起點(diǎn)v到該頂點(diǎn)w的直接邊(弧)初始化最短路徑，否則設(shè)為∞；

(b)從未求得最短路徑的終點(diǎn)中選擇路徑長(zhǎng)度最小的終點(diǎn)u：即求得v到u的最短路徑；

(c)修改最短路徑：計(jì)算u的鄰接點(diǎn)的最短路徑，若(v,?,u)+(u,w)(v,?,w)，則以(v,?,u,w)代替。

(d)重復(fù)(b)-(c)，直到求得v到其余所有頂點(diǎn)的最短路徑。特點(diǎn)：總是依照從小到大的順序求得最短路徑。

六、查找

1.查找分為：靜態(tài)查找表、動(dòng)態(tài)查找表、哈希查找表2.靜態(tài)查找表：對(duì)查找表只作查找操作的查找表。動(dòng)態(tài)查找表：查找過(guò)程中同時(shí)插入表中不含的元素，或者刪除查找表中已有的元素的操作的查找表。

3.順序查找：順序查找又稱(chēng)線性查找，是最基本的查找方法之一。順序查找既適用于順序表，也適用于鏈表。

4.二分法（折半）查找：是一種效率較高的查找方法，但前提是表中元素必需按關(guān)鍵字有序（按關(guān)鍵字遞增或遞減）排列。

5.索引順序表查找又稱(chēng)分塊查找。分塊查找：塊內(nèi)無(wú)序、塊間有序、如何分塊效率最高

6.動(dòng)態(tài)查找表：二叉排序樹(shù)查找：二叉排序樹(shù)的生成

二叉