6數(shù)據(jù)的組織結(jié)構(gòu)與算法1ppt課件

1、第六章 數(shù)據(jù)的組織構(gòu)造與算法6.1 數(shù)據(jù)構(gòu)造的根本概念6.2 常用的幾種數(shù)據(jù)構(gòu)造6.3 算法6.4 程序設(shè)計(jì)方法16.1數(shù)據(jù)構(gòu)造的根本概念6.1.1 數(shù)值計(jì)算與非數(shù)值計(jì)算數(shù)據(jù)是描畫客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處置的各種符號集合。換句話說，數(shù)據(jù)對客觀事物采用計(jì)算機(jī)可以識別、存貯和處置方式所進(jìn)展的描畫。簡言之，數(shù)據(jù)就是計(jì)算機(jī)化的信息。數(shù)學(xué)模型有定量模型和定性模型兩類之分，定量模型指的是可以用數(shù)值方程表示的一類計(jì)算模型，而定性模型那么是指非數(shù)值性的數(shù)據(jù)構(gòu)造,如表、樹和圖等及其運(yùn)算。2 數(shù)據(jù)構(gòu)造Data Structure問題來源于程序設(shè)計(jì)的開展。 第一個8008芯片只需4K的內(nèi)存，微軟的

2、最初成立就是為這個芯片的機(jī)器編寫B(tài)ASIC言語，優(yōu)化在每一處都非常重要。逐漸地，人們留意了數(shù)據(jù)表示與操作的構(gòu)造化，把一些確實(shí)可以有效處理問題的數(shù)據(jù)表示和算法總結(jié)出來，如表、棧、隊(duì)、樹、圖稍后會引見這些術(shù)語等被單獨(dú)抽出研討，而這些方法便構(gòu)成一門學(xué)問，這就是“數(shù)據(jù)構(gòu)造這門學(xué)科的來源。6.1.2 數(shù)據(jù)構(gòu)造的來源3數(shù)據(jù)構(gòu)造有邏輯上的數(shù)據(jù)構(gòu)造和物理上的數(shù)據(jù)構(gòu)造之分 。邏輯上的數(shù)據(jù)構(gòu)造反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系。物理上的數(shù)據(jù)構(gòu)造反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲安排。 6.1.3 對數(shù)據(jù)構(gòu)造的了解41.表示 對象/實(shí)體及其關(guān)系在計(jì)算機(jī)中的表示。只需對象及其相互關(guān)系已存儲表示在計(jì)算機(jī)中，才干被進(jìn)一步處置；2.操

3、作：對對象/實(shí)體進(jìn)展處置、訪問。數(shù)據(jù)構(gòu)造的普通定義：相互之間存在著一定關(guān)系的數(shù)據(jù)元素的集合及定義在其上的操作運(yùn)算稱為數(shù)據(jù)構(gòu)造。 51.插入：在數(shù)據(jù)構(gòu)造中的指定位置增添新的數(shù)據(jù)元素2.刪除：刪去數(shù)據(jù)構(gòu)造中指定的數(shù)據(jù)元素。3.查找：在數(shù)據(jù)構(gòu)造中尋覓某個特定要求的數(shù)據(jù)元素。4.排序：在線性構(gòu)造中重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使之按某個關(guān)鍵字值由小到大或由大到小的次序陳列。5.遍歷：按某一次序訪問數(shù)據(jù)構(gòu)造中的每一個數(shù)據(jù)元素。6.1.4 對數(shù)據(jù)構(gòu)造中數(shù)據(jù)元素的操作6 例6.1 解一元二次方程ax2+bx+c=0. 利用計(jì)算機(jī)解此方程，第一個問題就是如何在計(jì)算機(jī)中表示該方程。分析該方程，可知決議方程

4、的是方程的三個系數(shù)值：a、b、c，而它們的次序表示它們分別屬于那一項(xiàng)，其他符號是為添加可讀性而引入的，因此，可用這三個系數(shù)的線性陳列在計(jì)算機(jī)中表示該方程。例如： 3x2-x+1=0表示為3, -1, 1 x2-3=0 表示為(1, 0, -3) 在數(shù)據(jù)構(gòu)造中，將假設(shè)干個數(shù)線性陳列的數(shù)元素稱為線性表，因此，一元二次方程ax2+bx+c=0就在計(jì)算機(jī)中表示為線性表a, b, c。解方程本質(zhì)上是對線性表(a, b, c)進(jìn)展操作。6.1.5 數(shù)據(jù)構(gòu)造能處理什么問題7定義變量X和一個線性表，如數(shù)組int S3; S2，S1，S0可以分別存放三個系數(shù)值輸入S2，S1，S0三個系數(shù)值輸入恣意一個值X開場S

5、2*X*X+S1*X+S00，從編號為1的人開場，按順時(shí)針方向1開場順序報(bào)數(shù)，報(bào)到m時(shí)停頓。報(bào)m的人出圈，同時(shí)留下他的密碼作為新的m值，從他在順時(shí)針方向上的下一個人開場，重新從1開場報(bào)數(shù)，如此下去，直至一切的人出列為止。 17當(dāng)n和m較大時(shí)，用人工求解約瑟夫環(huán)問題是相當(dāng)繁瑣的。采用單循環(huán)鏈表就容易處理。其根本思緒是： 人圍成一圈，把一人看成一個結(jié)點(diǎn)，人之間的關(guān)系采用鏈接方式，即每一結(jié)點(diǎn)有一個前趨結(jié)點(diǎn)和一個后繼結(jié)點(diǎn)，每一個結(jié)點(diǎn)有一個指針指向下一個結(jié)點(diǎn)，最后一個結(jié)點(diǎn)指針指向第一個結(jié)點(diǎn)。這就是單循環(huán)鏈的數(shù)據(jù)構(gòu)造。當(dāng)人出列時(shí)，將結(jié)點(diǎn)的前趨結(jié)點(diǎn)指針指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)指針，即把結(jié)點(diǎn)驅(qū)出循環(huán)鏈。18 1樹的

6、定義 樹是由一個或多個結(jié)點(diǎn)組成的有限集合，如圖6-12所示。6.2.2 樹構(gòu)造19必有一個特定的稱為根ROOT的結(jié)點(diǎn)，根的每個分支稱為子樹sub-tree，子樹也是一棵樹樹中的每一個結(jié)點(diǎn)都可以不止一個直接后繼，結(jié)點(diǎn)的后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的“子結(jié)點(diǎn)Children除根結(jié)點(diǎn)外的一切結(jié)點(diǎn)有且只需一個直接前趨,結(jié)點(diǎn)的前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的“父結(jié)點(diǎn)Parent同一父結(jié)點(diǎn)的子結(jié)點(diǎn)稱為“兄弟Sibling結(jié)點(diǎn)下不再有分支的稱為樹葉leaf，或者葉子結(jié)點(diǎn)樹構(gòu)造的特點(diǎn)20二叉樹的特點(diǎn)：樹中的每個結(jié)點(diǎn)最多只需兩棵子樹，即樹中任何結(jié)點(diǎn)的度數(shù)不得大于。二叉樹的子樹有左右之分，稱為左子樹和右子樹。而且子樹的左右次序是重要的

7、，即使在只需一棵子樹的情況下，也應(yīng)分清楚。例如圖6-13是兩棵不同的二叉樹。 2二叉樹21所謂遍歷二叉樹，就是按一定的規(guī)那么和順序走遍二叉樹的一切結(jié)點(diǎn)，使每一個結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。 二叉樹的遍歷可分為先序遍歷中序遍歷后序遍歷 3二叉樹的遍歷221先序遍歷遞歸算法定義：假設(shè)二叉樹非空，那么依次執(zhí)行操作： (1) 訪問根結(jié)點(diǎn)； (2) 遍歷左子樹； (3) 遍歷右子樹。ABDGECF2.中序遍歷遞歸算法定義：假設(shè)二叉樹非空，那么依次執(zhí)行操作： (1)遍歷左子樹； (2)訪問根結(jié)點(diǎn)； (3)遍歷右子樹。GDBEACF3后序遍歷遞歸算法定義：假設(shè)二叉樹非空，那么依次執(zhí)行操作： (1)遍

8、歷左子樹； (2)遍歷右子樹； (3)訪問根結(jié)點(diǎn)。GDEBFCA23一個圖由有限的頂點(diǎn)Vertices和邊Edge組成，所以可方式化地用GV，E代表一個圖。圖中的結(jié)點(diǎn)稱為頂點(diǎn)，頂點(diǎn)之間的連線代表邊。6.2.3 圖構(gòu)造24圖(Graph)是由非空的頂點(diǎn)集合和一個描畫頂點(diǎn)之間關(guān)系邊或者弧的集合組成。其方式化定義為：GV，EVvi| vidataobjectE( vi,vj)| vi, vj V P(vi, vj)其中，G表示一個圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線，即偶對(vi,vj)表示一條邊。6.2.3 圖構(gòu)造25以下圖

9、無向圖G1給出了一個圖的例如，在該圖中：集合Vv1,v2,v3,v4；集合E(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)6.2.3 圖構(gòu)造26假設(shè)數(shù)據(jù)構(gòu)造中，數(shù)據(jù)元素之間不思索關(guān)系問題無前趨/后繼之分，那么稱這種構(gòu)造為集合。在集合中，各元素是“平等的，它們的共同關(guān)系是：都屬于同一個集合。6.2.4 集合276.3 算法6.3.1 算法的特性算法是對問題求解過程的一種描畫，是為處理一個或一類問題給出的一個確定的、有限長的操作序列。 1.有窮性2.確定性3.可行性4.有輸入5.有輸出28算法的五個特性1有窮性：對任何合法的輸入值，一個算法必需總是在執(zhí)行有窮步之后終

10、了，且每一步都可在有窮時(shí)間內(nèi)完成；2確定性：算法中每一條指令必需有確切的含義，不會產(chǎn)生二義性，對于一樣的輸入只能得出一樣的輸出。3可行性：即算法中描畫的操作都可以經(jīng)過曾經(jīng)實(shí)現(xiàn)的根本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。4輸入：一個算法有0個或多個輸入，這些輸入取自于某個特定的數(shù)據(jù)對象的集合，它可以運(yùn)用輸入語句從外部提供，也可以在算法內(nèi)經(jīng)過賦初值給定。5輸出：一個算法有一個或多個的輸出，這些輸出是同輸入有著某些特定關(guān)系的量。29在設(shè)計(jì)算法時(shí)，通常應(yīng)思索以下原那么：首先設(shè)計(jì)的算法必需是“正確的其次應(yīng)有很好的“可讀性，還必需具有“強(qiáng)壯性最后還應(yīng)思索所設(shè)計(jì)算法的復(fù)雜性，即有“高效率與低存儲量。6.3.2 什么是“好

11、的算法30算法的正確性所謂算法的正確性，也稱可靠性或有效性，是指：程序不含語法錯誤。程序?qū)τ趲捉M輸入的數(shù)據(jù)可以得出滿足規(guī)格闡明要求的結(jié)果。程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)可以得出滿足規(guī)格闡明要求的結(jié)果。程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格闡明要求的結(jié)果。31在算法是正確的前提下，算法的可讀性是擺在第一位的。可讀性好有助于人們對算法的了解，難懂的程序易隱藏較多錯誤，難以調(diào)試和修正。算法的效率指的是算法執(zhí)行時(shí)計(jì)算機(jī)資源的耗費(fèi)，它包括運(yùn)轉(zhuǎn)時(shí)間代價(jià)和存儲空間代價(jià)。算法的強(qiáng)壯性指的是，算法應(yīng)對非法輸入的數(shù)據(jù)做出恰當(dāng)反映或進(jìn)展相應(yīng)處置。它強(qiáng)調(diào)的是，假設(shè)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)能加

12、以識別并做出處置，而不是產(chǎn)生誤動作或墮入癱瘓。32算法的復(fù)雜性是算法運(yùn)轉(zhuǎn)所需求的計(jì)算機(jī)資源的量。算法的復(fù)雜性是算法效率的度量，是評價(jià)算法優(yōu)劣的重要根據(jù)。 算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。需求的時(shí)間資源的量，即算法的運(yùn)轉(zhuǎn)速度，稱作時(shí)間復(fù)雜性。 需求的空間即存儲器資源的量稱作空間復(fù)雜性。 6.3.3 算法復(fù)雜性331自然言語 自然言語是人們?nèi)粘Ｋ玫难哉Z，如漢語、英語、德語等。 例如，求3個數(shù)中最大者的問題，可以描畫為： 比較前兩個數(shù)。 將中較大的數(shù)與第三個數(shù)進(jìn)展比較。 步驟中較大的數(shù)即為所求。6.3.4 算法的表示342流程圖 流程圖是描畫算法的常用工具。它采用美國國家規(guī)范化協(xié)會ANS

13、IAmerican National Standard Institute規(guī)定的一組圖形符號來表示算法 起止框判別框處置框輸入/輸出框注釋框流向線銜接點(diǎn)353偽代碼 偽代碼是用介于自然言語和計(jì)算機(jī)言語之間的文字和符號來描畫算法的工具。它不用圖形符號，因此書寫方便格式緊湊，易于了解，便于向計(jì)算機(jī)程序設(shè)計(jì)言語過渡。 例：求兩個數(shù)的較大者，用偽代碼描畫算法如下： Find the bigger Input: two number s:a,b 1. if (the first number a is greater than or equal to the second number b) then

14、1.1 return a else 1.2 return b end if end364計(jì)算機(jī)程序設(shè)計(jì)言語 普通而言，計(jì)算機(jī)程序設(shè)計(jì)言語描畫的算法是明晰的、簡明的，最終也能由計(jì)算機(jī)處置的，然而也不是完善無缺。它需求設(shè)計(jì)者用特定程序設(shè)計(jì)言語編寫的算法，限制了與他人的交流；容易墮入描畫計(jì)算步驟的細(xì)節(jié)而忽視算法的本質(zhì)。 376.4 程序設(shè)計(jì)方法6.4.1 計(jì)算機(jī)程序的性質(zhì)計(jì)算機(jī)程序包含兩方面的內(nèi)容：對象及對象之間關(guān)系(數(shù)據(jù)構(gòu)造)；描畫對這些對象進(jìn)展處置的加工規(guī)那么(算法) 。38目的性 程序有明確的目的，程序運(yùn)轉(zhuǎn)時(shí)能完成賦予它的功能。 分步性 程序?yàn)橥瓿善鋸?fù)雜的功能，由一系列計(jì)算機(jī)可執(zhí)行的步驟組成。

15、 有序性 程序的執(zhí)行步驟是有序的，不可隨意改動程序步驟的執(zhí)行順序。 有限性 程序是有限的指令序列，程序所包含的步驟是有限的。 操作性 有意義的程序總是對某些對象進(jìn)展操作，使其改動形狀，完成其功能。計(jì)算機(jī)程序具有以下性質(zhì)： 39數(shù)據(jù)構(gòu)造是數(shù)據(jù)構(gòu)造的邏輯表示方式，算法是處置問題的方法和步驟，最后問題的解由計(jì)算機(jī)程序給出。這是程序員在程序設(shè)計(jì)時(shí)應(yīng)思索的主要問題。 6.4.2 程序設(shè)計(jì)與數(shù)據(jù)構(gòu)造、算法之間的關(guān)系401. 程序的控制構(gòu)造一個可以用順序、選擇、循環(huán)和跳轉(zhuǎn)(如goto語句)四種程序構(gòu)造處理的問題，也一定能用順序、選擇、循環(huán)三種程序構(gòu)造處理。但確實(shí)存在這樣的問題，它可以用順序、選擇、循環(huán)三種程

16、序構(gòu)造處理，但不能用其中任何兩種處理。換句話說，順序、選擇、循環(huán)三種程序構(gòu)造構(gòu)成了一個最小完備集。我們將這三種程序構(gòu)造叫根本程序構(gòu)造。6.4.3 構(gòu)造化程序設(shè)計(jì) 41三種根本構(gòu)造的圖示：順序構(gòu)造選擇構(gòu)造42循環(huán)構(gòu)造的圖示：當(dāng)型(While型)循環(huán)構(gòu)造 直到型(Until型)循環(huán) 43順序程序設(shè)計(jì)44分支構(gòu)造45循環(huán)構(gòu)造462.構(gòu)造化程序設(shè)計(jì)方法構(gòu)造化程序設(shè)計(jì)方法主要包括程序構(gòu)造的自頂向下和模塊化設(shè)計(jì)方法。47程序設(shè)計(jì)的普通步驟如下： 1.分析問題 對要處理的問題，首先必需分析清楚，明確標(biāo)題的要求，列出一切知量，找出標(biāo)題的求解范圍、解的精度等。2.建立數(shù)學(xué)模型 對實(shí)踐問題進(jìn)展分析之后，找出它的內(nèi)在規(guī)律，就可以建立數(shù)學(xué)模型。只需建立了模型的問題，才干能夠利用計(jì)算機(jī)來處理。3.確定算法 建立