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

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

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

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

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

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

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

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

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

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

數(shù)據(jù)元素：在數(shù)據(jù)處理領(lǐng)域中，每一個(gè)需要處理的對象都可以抽象為數(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í)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。其中前后件關(guān)系是指它們的邏輯關(guān)系，而與他們在計(jì)算機(jī)中的存儲(chǔ)位置無關(guān)。它包含兩個(gè)要素：數(shù)據(jù)元素的集合，通常記為D；數(shù)據(jù)元素之間的關(guān)系（前后件關(guān)系），通常記為R。形式表示如下：

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

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

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

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

圖形表示方法：對于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱為數(shù)據(jù)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)，對關(guān)系R中每一個(gè)二元組，用一條有向線段從前件指向后件結(jié)點(diǎn)，以表示數(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)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素都沒有，則稱為數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。在一個(gè)空的數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)元素后就變成了非空。根據(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)滿足如下兩個(gè)條件：（1）、有且只有一個(gè)根結(jié)點(diǎn)；（2）、每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最對多有一個(gè)后件。在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)還是線性結(jié)構(gòu)常見的線性結(jié)構(gòu)：線性表、棧、隊(duì)列、線性鏈表常見的非線性結(jié)構(gòu)：樹、二叉樹、圖

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

1.3.1線性表的基本概念

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

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

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

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

線性表的主要操作有：

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

1.4.1棧及其基本運(yùn)算

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

1.4.2隊(duì)列及其基本運(yùn)算

1、隊(duì)列（queue）的定義

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

a1,

a2,

a3,

a4,…………

an-1,

an隊(duì)列示意圖隊(duì)頭隊(duì)尾frontrear19精選ppt課件

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

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

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

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

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

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

數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點(diǎn)的地址，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭铡＿壿嬌舷噜彽臄?shù)據(jù)元素在內(nèi)存中的物理存儲(chǔ)空間不一定相鄰。1.5線性鏈表

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

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

headd^

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

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

1.6.1樹的基本概念

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

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

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

A

C

GT2D

HIT3J

M

BEL

KT1F31精選ppt課件

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

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

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

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

非完全二叉樹423167891011125

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

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

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

i

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

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