數(shù)據(jù)結(jié)構(gòu)與算法

公共基礎(chǔ)知識部分之第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.3線性表及其順序存儲結(jié)構(gòu)1.4棧和隊列1.5線性鏈表1.6樹與二叉樹1.7查找技術(shù)1.8排序技術(shù)1精選ppt課件1.1.1算法的基本概念

所謂算法是指解題方案的準(zhǔn)確而完整的描述。1.1算法

1、算法的基本特征>可行性：算法原則上能夠精確地執(zhí)行，甚至人們只用筆和紙做有限次運算即可完成。>確定性：算法的每一步都必須有確切的定義>有窮性：一個算法必須在執(zhí)行有窮步后結(jié)束，即算法必須能夠終止>擁有足夠的情報：我們要使算法有效就必須擁有足夠的情報2精選ppt課件2、算法的基本要素>數(shù)據(jù)對象的運算和操作A.算術(shù)運算（+、-、*、/）B.邏輯運算（&、||、!）C.關(guān)系運算（>、<、=、#）D.數(shù)據(jù)傳輸（賦值、輸入、輸出）>算法的控制結(jié)構(gòu)一個算法一般都可以用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。3精選ppt課件3、算法設(shè)計基本方法列舉法：指針對待解決的問題，列舉所有可能的情況，并用問題中給定的條件來檢驗。歸納法：特殊——一般的抽象過程遞推：從已知初始條件出發(fā)，逐次推出所要求的各中間結(jié)構(gòu)和最后結(jié)果遞歸：將復(fù)雜的問題逐層分解，最后歸結(jié)為一個簡單的問題，再沿原分解的逆過程逐步進行綜合。分為直接遞歸和間接遞歸減半遞推技術(shù)：把規(guī)模較大較復(fù)雜的問題，分成幾個規(guī)模較小較簡單的問題回溯法：通過對問題的分析，找出一個解決問題的線索，多次試探，若成功，則得出解，若失敗，則回退，換別的路線再進行試探4精選ppt課件1.1.2算法復(fù)雜度算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。兩者之間沒有必然的聯(lián)系。1、算法的時間復(fù)雜度

指執(zhí)行算法所需要的計算工作量。工作量可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量。其中基本運算次數(shù)是問題規(guī)模的函數(shù)，即

算法的工作量=f(n)。>平均性態(tài)>最壞情況復(fù)雜性注意:算法程序執(zhí)行的具體時間受使用計算機、程序設(shè)計語言以及算法實現(xiàn)過程中的許多細(xì)節(jié)的影響。而算法的時間復(fù)雜度與此無關(guān)5精選ppt課件2、算法的空間復(fù)雜度

指執(zhí)行這個算法所需要的內(nèi)存空間，包含：>算法程序所占的空間>輸入的初始數(shù)據(jù)所占的空間>算法執(zhí)行過程中所需要的額外空間6精選ppt課件1.2數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究以下三個方面的問題：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)（2）數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算數(shù)據(jù)結(jié)構(gòu)學(xué)科的研究目的：提高數(shù)據(jù)處理的效率。主要包括1、數(shù)據(jù)的處理速度2、盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間

7精選ppt課件1.2.1數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)處理：是指對數(shù)據(jù)集合中的各元素以各種形式進行運算。包括插入、刪除、查找、更改等運算，也包括對數(shù)據(jù)元素進行分析。

數(shù)據(jù)元素：在數(shù)據(jù)處理領(lǐng)域中，每一個需要處理的對象都可以抽象為數(shù)據(jù)元素。

數(shù)據(jù)結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。8精選ppt課件1、數(shù)據(jù)的邏輯結(jié)構(gòu)

所謂邏輯結(jié)構(gòu)實際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。其中前后件關(guān)系是指它們的邏輯關(guān)系，而與他們在計算機中的存儲位置無關(guān)。它包含兩個要素：數(shù)據(jù)元素的集合，通常記為D；數(shù)據(jù)元素之間的關(guān)系（前后件關(guān)系），通常記為R。形式表示如下：

B=（D，R）其中B表示數(shù)據(jù)結(jié)構(gòu)

9精選ppt課件2、數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（即數(shù)據(jù)的物理結(jié)構(gòu)）。常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。

10精選ppt課件1.2.2數(shù)據(jù)結(jié)構(gòu)的圖形表示

圖形表示方法：對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱為數(shù)據(jù)結(jié)點，簡稱結(jié)點，對關(guān)系R中每一個二元組，用一條有向線段從前件指向后件結(jié)點，以表示數(shù)據(jù)之間的前后件關(guān)系。

春夏冬秋父親兒子女兒圖1.2一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示圖1.3家庭成員輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)的圖形表示11精選ppt課件例1.2用圖形表示數(shù)據(jù)結(jié)構(gòu)B=(D,R),其中：D={di|1<=i<=6}={d1,d2,d3,d4,d5,d6}R={(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6)}d1d3d5d2d6d4圖1.4數(shù)據(jù)結(jié)構(gòu)的圖形表示12精選ppt課件1.2.3線性結(jié)構(gòu)與非線性結(jié)構(gòu)如果一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱為數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。在一個空的數(shù)據(jù)結(jié)構(gòu)中插入一個元素后就變成了非空。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)（又稱為線性表）非線性結(jié)構(gòu)線性結(jié)構(gòu)滿足如下兩個條件：（1）、有且只有一個根結(jié)點；（2）、每一個結(jié)點最多有一個前件，也最對多有一個后件。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點還是線性結(jié)構(gòu)常見的線性結(jié)構(gòu)：線性表、棧、隊列、線性鏈表常見的非線性結(jié)構(gòu)：樹、二叉樹、圖

13精選ppt課件1.3線性表及其順序存儲結(jié)構(gòu)

1.3.1線性表的基本概念

線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列：a1，a2，……，ai，……，an其中n稱作表的長度，當(dāng)n=0時，稱作空表。n(n>=0)，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。14精選ppt課件

1.3.2線性表的順序存儲結(jié)構(gòu)

線性表的順序存儲結(jié)構(gòu)有以下兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依

次存放的。邏輯上相鄰的結(jié)點，物理位置上也相鄰在程序設(shè)計語言中，通常定義一個一維數(shù)組來表示線性表的順序存儲空間，該一維數(shù)組的長度通常要定義得比線性表的實際長度大一些，以便對線性表進行各種運算，特別是插入運算。

線性表的主要操作有：

（1）插入、（2）刪除、（3）查找、（4）排序、（5）分解、（6）合并、（7）復(fù)制、（8）逆轉(zhuǎn)。15精選ppt課件元素an……..元素ai……..元素a2元素a1bb+mb+(i-1)*mb+(maxlen-1)*m存儲地址內(nèi)存狀態(tài)Loc(元素i)=b+（i-1)*m順序存儲結(jié)構(gòu)示意圖(順序表)：首地址起始地址基地址每個元素所占用的存儲單元個數(shù)16精選ppt課件1.4棧和隊列

1.4.1棧及其基本運算

1、棧（stack）的定義棧是限定在一端進行插入和刪除的線性表。性質(zhì)：a.按照“先進后出”（FILO–firstinlastout)或“后進先出”（LIFO—lastinfirstout)的原則組織數(shù)據(jù)。b.通常用指針top來指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。c.當(dāng)表中沒有元素時稱棧為空棧d.棧具有記憶功能e.往棧中插入一個元素稱為入棧運算，從棧中刪除一個元素（即刪除棧頂元素）稱為退棧運算。Top棧頂指針反映了棧中元素的變化17精選ppt課件2、棧的順序存儲及其運算在程序設(shè)計語言中，一般用一維數(shù)組S(1:m)作為棧的順序存儲空間，其中m為棧的最大容量。在S(1:m)中，S(bottom)通常為棧底元素（在棧非空的情況下），S(top)為棧頂元素。top=0表示?？?；top=m表示棧滿。棧的基本運算有3種：入棧運算退棧運算讀棧頂元素棧中的運算：1.設(shè)置空棧；2.插入一個新的棧頂元素3.刪除棧頂元素；4.讀取棧頂元素。18精選ppt課件

1.4.2隊列及其基本運算

1、隊列（queue）的定義

隊列是允許在一端(隊尾rear)進行插入、而在另一端(隊頭front)進行刪除的線性表。它按照“先進先出”（FIFO–firstinfirstout)或“后進后出”（LILO—lastinlastout)的原則組織數(shù)據(jù)。

a1,

a2,

a3,

a4,…………

an-1,

an隊列示意圖隊頭隊尾frontrear19精選ppt課件

舉例1：到醫(yī)院看病，首先需要到掛號處掛號，然后，按號碼順序救診。舉例2：乘坐公共汽車，應(yīng)該在車站排隊，車來后，按順序上車。

20精選ppt課件隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。隊列是“先進先出”（FIFO）或“后進后出”（LILO）的線性表。隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。循環(huán)隊列:在循環(huán)隊列中，用隊尾指針r指向隊尾，用排頭指針f指向隊頭的前一個位置

*循環(huán)對隊中的元素的個數(shù)=rear-front(r>f)=rear-front+容量(r<f)m=50r=20f=3521精選ppt課件線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱線性鏈表

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示數(shù)據(jù)元素間的邏輯關(guān)系，對于每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息。這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：

datalink指針域，用來存放結(jié)點的直接后繼的地址數(shù)據(jù)域，用來存放結(jié)點的值

將線性表的元素放到一個具有頭指針的鏈表中，鏈表中每個結(jié)點包含數(shù)據(jù)域和指針域。

數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點的地址，最后一個結(jié)點的指針域為空。邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的物理存儲空間不一定相鄰。1.5線性鏈表

22精選ppt課件例如：線性表（a,b,c,d)23精選ppt課件

術(shù)語表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點；其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）；表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）。

headd^

cba單鏈表結(jié)構(gòu)示意圖datalink24精選ppt課件其中，head是頭指針，它指向單鏈表中的第一個結(jié)點，這是單鏈表操作的入口點。由于最后一個結(jié)點沒有直接后繼結(jié)點，所以，它的指針域放入一個特殊的值NULL。NULL值在圖示中常用（^）符號表示。帶頭結(jié)點的單鏈表為了簡化對鏈表的操作，人們經(jīng)常在鏈表的第一個結(jié)點之前附加一個結(jié)點，并稱為頭結(jié)點。這樣可以免去對鏈表第一個結(jié)點的特殊處理。如下圖所示：帶頭結(jié)點的單鏈表結(jié)構(gòu)示意圖head^空表headd^

cba25精選ppt課件110hat200130cat135135eat170160matnil165bat130170fat110200jat205205lat160165head頭指針數(shù)據(jù)域指針域例如：線性表（bat,cat,eat,fat,hat,jat,lat,mat）單鏈表只注重結(jié)點的邏輯順序，不關(guān)心每個結(jié)點的實際存儲位置，因此用箭頭來表示鏈域中的指針。batcateatmat∧head26精選ppt課件1.6樹和二叉樹

1.6.1樹的基本概念

樹是一種簡單的非線性結(jié)構(gòu)，由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。27精選ppt課件樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式28精選ppt課件(C)是有13個結(jié)點的樹，其中A是根，其余結(jié)點分成3個子集：T1

、T2、T3。都是根A的子樹，且本身也是一棵樹。例如：T1其根為B，兩棵子樹為T11={F}T12={E,K,L}，T12又是一棵子樹，樹根為F，{K}和{L}是E的兩個互不相交的子集。29精選ppt課件結(jié)點：數(shù)據(jù)元素的內(nèi)容及其指向其子樹根的分支統(tǒng)稱為結(jié)點。結(jié)點的度（Degree):結(jié)點的分支數(shù)，即結(jié)點擁有的子樹數(shù)。終端結(jié)點（葉子leaf）:度為0的結(jié)點。非終端結(jié)點:度不為0的結(jié)點。結(jié)點的層次:樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推。樹的度:樹中所有結(jié)點度的最大值。樹的深度:樹中所有結(jié)點層次的最大值。有序樹、無序樹:如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。術(shù)語30精選ppt課件

相關(guān)概念：父結(jié)點、根結(jié)點、子結(jié)點、葉子結(jié)點、結(jié)點的度、樹的度、樹的深度、子樹。

A

C

GT2D

HIT3J

M

BEL

KT1F31精選ppt課件

1.6.2二叉樹及其基本性質(zhì)1、什么是二叉樹

二叉樹具有以下兩個特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個根結(jié)點最多只有兩棵子樹，且分別為該結(jié)點的左子樹和右子樹。（子樹有左右之分，左右樹不能互換）32精選ppt課件二叉樹的五種基本形態(tài)空二叉樹僅有根結(jié)點右子樹為空左子樹為空左右子樹均非空兩棵不同的二叉樹33精選ppt課件2、二叉樹的基本性質(zhì)

（1）在二叉樹的K層上，最多有2k-1(k>=1)個結(jié)點；（2）深度為m的二叉樹最多有2m-1個結(jié)點；（3）在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點數(shù)多一個；（4）具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取不大于log2n的最大整數(shù)。[2007.9.8]題：一棵二叉樹中共有70個葉子結(jié)點和80個度為1的結(jié)點，則二叉樹中總結(jié)點數(shù)為：A.219B.221C.229D.23134精選ppt課件3、滿二叉樹和完全二叉樹

（1）滿二叉樹除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。即在第K層上有2k-1個結(jié)點。深度為m的滿二叉樹有2m-1個結(jié)點423167891011121314155特點：每一層上都含有最大結(jié)點數(shù)。35精選ppt課件（2）完全二叉樹除最后一層外，每一層上的結(jié)點數(shù)都達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點。423167891011125

非完全二叉樹423167891011125

完全二叉樹特點：除最后一層外，每一層都取最大結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置。36精選ppt課件891011124567231789456231

456231一棵滿二叉樹一定是一棵完全二叉樹，而一棵完全二叉樹不一定是滿二叉樹。37精選ppt課件2i+2

2i2i+12i+22i+3i+12i2i+1i

i

i+1另：性質(zhì)：完全二叉樹中度為1的結(jié)點數(shù)為0或1完全二叉樹總數(shù)為奇數(shù)時，度為1的結(jié)點數(shù)為0為偶數(shù)時，度為1的結(jié)點數(shù)為138精選ppt課件

1.6.4二叉樹的遍歷所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結(jié)點一次且僅一次的過程。這里的訪問可以是輸出、比較、更新、查看元素內(nèi)容等等各種操作。1、前序遍歷（DLR）若二叉樹為空，則結(jié)束遍歷操作；否則訪問根結(jié)點，按前序遍歷左子樹，按前序遍歷右子樹。2、中序遍歷（LDR）若二叉樹為空，則結(jié)束遍歷操作；否則按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。3、后序遍歷（LRD）若二叉樹為空，則結(jié)束遍歷操作；否則按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。39精選ppt課件GHBCADEF先序序列： ABDGCEFH 中序序列： DGBAECHF 后序序列： GDBEHFCA 先序：DLR中序：LDR后序：LRD40精選ppt課件ACEFGBH