電子科數(shù)據(jù)結(jié)構(gòu)pascal版課件ds第一章

數(shù)據(jù)結(jié)構(gòu)（第二版）嚴(yán)蔚敏吳偉民

清華大學(xué)出版社主講：王曉斌

電子科技大學(xué)計(jì)算機(jī)學(xué)院1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的要求1.掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲(chǔ)結(jié)構(gòu)2.提高閱讀和編寫算法的能力3.能針對(duì)給定問(wèn)題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計(jì)和分析算法1.2<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容2108006011班號(hào)83202670計(jì)算機(jī)學(xué)院辦公室電話號(hào)碼610054電子科技大學(xué)郵編身份證號(hào)碼例1：187482結(jié)論1.

雜亂的數(shù)據(jù)不能表達(dá)和交流信息1.2<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例2: 電話號(hào)碼簿(a1，b1)(a2，b2)…(an，bn)其中：ai為某人姓名，bi為該人的電話號(hào)碼。要求：設(shè)計(jì)一個(gè)算法，給定一個(gè)姓名時(shí)，能查出此人的電話號(hào)碼。如果姓名和電話號(hào)碼的排列次序無(wú)規(guī)律，則只能逐一比較姓名進(jìn)行查找如果姓名按字典順序組織，則查找就快捷多了結(jié)論2. 數(shù)據(jù)之間是有聯(lián)系的這些聯(lián)系常常影響算法的選擇和效率?！禗S》就是要研究數(shù)據(jù)之間的聯(lián)系。1.2<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例3：大學(xué)學(xué)生管理機(jī)構(gòu)

學(xué)校 一系．．．八系．．．

一年級(jí)二年級(jí)三年級(jí)四年級(jí)

１班．．．８班張三．．．李四結(jié)論３． 數(shù)據(jù)之間是有結(jié)構(gòu)的例３中數(shù)據(jù)之間呈分層結(jié)構(gòu)（樹狀結(jié)構(gòu)）《DS》就是要研究數(shù)據(jù)之間的各類結(jié)構(gòu)。1.2<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例４：圖書目錄管理設(shè)每個(gè)書目含：書名，作者，登錄號(hào)，分類號(hào)，出版年月，對(duì)圖書目錄常有如下操作：查找：某書在書庫(kù)中是否存在？插入：購(gòu)進(jìn)新書時(shí)的登錄；刪除：報(bào)廢或丟失的書，需從目錄中去掉；結(jié)論４． 在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運(yùn)算《DS》就是要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算。1.2<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容綜上所述：《DS》主要研究?jī)?nèi)容：計(jì)算機(jī)的操作對(duì)象——數(shù)據(jù)；數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系；并對(duì)每種結(jié)構(gòu)定義相適應(yīng)的各種運(yùn)算；設(shè)計(jì)出相應(yīng)的算法；分析算法的效率。常見的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組、棧、隊(duì)列、表、串、樹、圖和文件等。1.３基本術(shù)語(yǔ)數(shù)據(jù)（Data)：所有能被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù)元素（DataElement）：是數(shù)據(jù)這個(gè)集合中的一個(gè)個(gè)體。設(shè)給定數(shù)據(jù)集合為：

D={d1，d2，．．．，dn}

則di屬于D，并稱di為數(shù)據(jù)元素。數(shù)據(jù)項(xiàng)（DataItem）：數(shù)據(jù)元素常常還可分為若干個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)具有意義的最小單位。1.３基本術(shù)語(yǔ)數(shù)據(jù)對(duì)象（DataObject）:具有相同特性的數(shù)據(jù)元素的集合。例如：數(shù)據(jù)集合D={0，1，…，A，B，…，Z}則：數(shù)據(jù)對(duì)象正整數(shù)N＝｛0，1，…｝

數(shù)據(jù)對(duì)象字母C＝｛A，B，…，Z｝ 數(shù)據(jù)元素是數(shù)據(jù)的一個(gè)個(gè)體， 數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集。1.３基本術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)（DataStructure）：是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。

所謂結(jié)構(gòu)就是數(shù)據(jù)元素之間的關(guān)系，可有一種或多種特定的關(guān)系。用集合的形式描述，數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：

DS=(D，R)

其中：D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。簡(jiǎn)言之，數(shù)據(jù)元素和其相互關(guān)系稱為數(shù)據(jù)結(jié)構(gòu)1.３基本術(shù)語(yǔ)例1：復(fù)數(shù)的表示

Complex=（C，R）C={c1，c2|c1，c2是實(shí)數(shù)}

R={P}P={<c1,c2>|c1,c2C}1.３基本術(shù)語(yǔ)例2：課題小組的描述

Group=（P，R）P={T,G1,…,Gn,S11,…,Snm|1n3,1m2}

R={R1,R2}R1={<T,Gi>|1in,1n3}R2={<Gi,Sij>|1in,1jm,1n3,1m2}1.３基本術(shù)語(yǔ)邏輯結(jié)構(gòu)（LogicalStructure）：指數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。物理結(jié)構(gòu)（PhysicalStructure）：指數(shù)據(jù)結(jié)構(gòu)在機(jī)內(nèi)的表示。也稱存儲(chǔ)結(jié)構(gòu)，通常有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。一點(diǎn)說(shuō)明：算法的設(shè)計(jì)取決于邏輯結(jié)構(gòu)；算法的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)。1.３基本術(shù)語(yǔ)數(shù)據(jù)類型（DataType）：一個(gè)值的集合和定義在這個(gè)值集上的操作的總稱?；静僮鞯姆诸悾阂眯汀檎?；加工型——插入、刪除、更新、排序。1.４算法描述和算法分析一．算法（Algorithm）１．算法概念：算法是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。２．算法基本特性：

有窮性：算法經(jīng)有限步后結(jié)束；

確定性：每一步必須有明確的含義；

可行性：每一步是可執(zhí)行的。1.４算法描述和算法分析３．算法與程序的區(qū)別算法是解決問(wèn)題的一種方法或一個(gè)過(guò)程，考慮如何將輸入轉(zhuǎn)換成輸出，一個(gè)問(wèn)題可以有多種算法。程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn)。主要區(qū)別在：有窮性和描述方法程序可以是無(wú)窮的，例如OS，算法是有窮的；程序是用程序設(shè)計(jì)語(yǔ)言描述，在機(jī)器上可以執(zhí)行；算法還可以用框圖、自然語(yǔ)言等方式描述。1.４算法描述和算法分析二．算法描述語(yǔ)言——類Pascal

為了便于理解掌握算法的思想和實(shí)質(zhì)，本課程采用類Pascal語(yǔ)言來(lái)描述各種算法。所有的算法均以過(guò)程或函數(shù)的形式表示；

PROC

過(guò)程名(參數(shù)表);｛算法說(shuō)明｝語(yǔ)句組

ENDP;{過(guò)程名}1.４算法描述和算法分析

FUNC函數(shù)名(參數(shù)表)：類型;｛函數(shù)說(shuō)明｝語(yǔ)句組

RETURN(f)

ENDF;{函數(shù)名}

可有若干值參或變參；參數(shù)必須說(shuō)明類型，局部變量可省缺說(shuō)明；過(guò)程或函數(shù)均允許嵌套或遞歸調(diào)用1.４算法描述和算法分析布爾運(yùn)算：AND、OR、NOT、CAND、CORCAND和COR稱為DelayComputation，其含義

ACANDB：ifAthenBelsefalseACORB：ifAthentrueelseB1.４算法描述和算法分析例1:用過(guò)程實(shí)現(xiàn)求n!PROCfac1(n:integer;VARf:integer);ifn<0thenERROR;f:=1;fori:=1TOnDOf:=f*iENDP;1.４算法描述和算法分析例2:用函數(shù)實(shí)現(xiàn)求n!FUNCfac2(n:integer):integer;ifn<0thenERROR;f:=1;fori:=1TOnDOf:=f*i;RETURN(f)ENDF;1.４算法描述和算法分析例3:用遞歸函數(shù)實(shí)現(xiàn)求n!FUNCfac3(n:integer):integer;ifn<0thenERROR;ifn=0thenRETURN(1);RETURN(n*fac3(n-1))ENDF;1.４算法描述和算法分析例4:將x、y、z中的整數(shù)值由大到小排列PROCsort(VARx,y,z:integer);ifx<ythen[t:=x;x:=y;y:=t];ify<zthen[t:=z;z:=y;ifxttheny:=telse[y:=x;x:=t]]ENDP;1.４算法描述和算法分析三．算法分析 如何衡量一個(gè)正確算法的好壞？ 衡量的三個(gè)尺度：運(yùn)行所花費(fèi)的時(shí)間（算法的時(shí)間特性）；所占用存儲(chǔ)空間的大?。ㄋ惴ǖ目臻g特性）；其它（正確性、可讀性、健壯性等）。 時(shí)間和空間特性的巨大改進(jìn)源于更好的數(shù)據(jù)結(jié)構(gòu)或算法。1.４算法描述和算法分析語(yǔ)句頻度（FrequencyCount）：

語(yǔ)句可能重復(fù)執(zhí)行的最大次數(shù)。時(shí)間復(fù)雜度（TimeComplexity）：

設(shè)算法中所有語(yǔ)句的語(yǔ)句頻度為t(n)， f(n)是當(dāng)n趨向無(wú)窮大時(shí)與t(n)為同階無(wú)窮大， 則算法的時(shí)間復(fù)雜度T(n)=O(f(n))

其中：n為算法計(jì)算量或稱為規(guī)模（size）； f(n)是運(yùn)算時(shí)間隨n增大時(shí)的增長(zhǎng)率；

O(f(n))是算法時(shí)間特性的量度。1.４算法描述和算法分析例：程序段語(yǔ)句頻度時(shí)間復(fù)雜度1.x:=x+1;1O(1)常數(shù)階2.FORi:=1TOnDOx:=x+1;n+1O(n)線性階3.FORi:=1TOnDOn+1FORj:=1TOnDOx:=x+1;n(n+1)O(n2)平方階1.４算法描述和算法分析4.FORi:=2TOnDOnFORj:=2TOi-1DOn(n-1)/2x:=x+1;(n-1)(n-2)/2O(n2)平方階5.FORi:=1TOnDOn+1FORj:=1TOnDOn(n+1)[c[i,j]:=0;n2FORk:=1TOnDOn2(n+1)c[i,j]:=c[i,j]+a[i,k]*b[k,j]n3O(n3)]1.４算法描述和算法分析6.有時(shí)，考慮最壞情形PROCbubble-sort(VARa:ARRAY[1..n]OFinteger);i:=1;REPEATchange:=false;FORj:=1TOn-iDOIF