《數(shù)據(jù)結(jié)構(gòu)》課件第一章

數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）程序設(shè)計(jì)猶如寫英語(yǔ)作文，每個(gè)人都知道語(yǔ)法句型，但作文質(zhì)量確有好有壞！如何寫出好程序？找出解決問(wèn)題適合的方法來(lái)設(shè)計(jì)程序的流程采用最簡(jiǎn)潔的數(shù)據(jù)的結(jié)構(gòu)來(lái)表示程序中的數(shù)據(jù)和變量問(wèn)題舉例如何設(shè)計(jì)程序的存儲(chǔ)結(jié)構(gòu)和算法才能以最快的速度查詢出學(xué)校內(nèi)某個(gè)學(xué)生的成績(jī)單？學(xué)習(xí)要求及時(shí)復(fù)習(xí)和預(yù)習(xí)，及時(shí)理解知識(shí)活躍的思維能力和嚴(yán)格的推理過(guò)程注重?cái)?shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)方法或流程，掌握部分程序的代碼實(shí)現(xiàn)過(guò)程大量的手工繪圖——流程圖良好的C++語(yǔ)言基礎(chǔ)

C++語(yǔ)言+數(shù)據(jù)結(jié)構(gòu)=問(wèn)題的解決數(shù)組、結(jié)構(gòu)指針控制語(yǔ)句——循環(huán)、條件判斷、順序最基本的輸入輸出操作良好的抽象思維能力能夠針對(duì)算法流程圖逐一闡述出算法的完整實(shí)現(xiàn)流程關(guān)于流程圖的介紹每個(gè)流程圖都有一個(gè)開始標(biāo)記每個(gè)流程圖至少有一個(gè)結(jié)束標(biāo)記程序模塊的確定——順序語(yǔ)句條件分支的畫法如何用“條件分支”來(lái)實(shí)現(xiàn)“循環(huán)”的邏輯推薦畫圖工具——VISIO第一章緒論內(nèi)容概述數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念算法及算法復(fù)雜度分析什么是數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符、圖表、圖象等各種具有一定結(jié)構(gòu)的數(shù)據(jù)。用計(jì)算機(jī)解決一個(gè)具體問(wèn)題的時(shí)候一般有幾個(gè)步驟：從具體問(wèn)題抽象出一個(gè)數(shù)學(xué)模型設(shè)計(jì)解決這個(gè)模型的算法（找到處理的對(duì)象的特性和對(duì)象之間的關(guān)系）編程、測(cè)試、得到最終解基本概念和術(shù)語(yǔ)（一）數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，是所有被計(jì)算機(jī)程序處理的符號(hào)總稱（數(shù)字、圖象、聲音、字符串）。數(shù)據(jù)元素

：數(shù)據(jù)的基本單位。由多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)元素可以是單一數(shù)據(jù)，也可以是一條記錄數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。（整數(shù)數(shù)據(jù)集合、學(xué)籍表）基本概念和術(shù)語(yǔ)（二）數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)是指數(shù)據(jù)間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)是指是相互之間存在某種特定關(guān)系的數(shù)據(jù)元素的集合。（模型）數(shù)據(jù)結(jié)構(gòu)包括三個(gè)方面的內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算一個(gè)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)圖書館查詢系統(tǒng)線性關(guān)系(一對(duì)一)人機(jī)對(duì)羿樹狀關(guān)系(一對(duì)多)交通燈問(wèn)題圖狀（網(wǎng)狀）關(guān)系(多對(duì)多)數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及他們之間的關(guān)系和操作的學(xué)科。是計(jì)算機(jī)專業(yè)或相關(guān)專業(yè)的一門基礎(chǔ)學(xué)科。001高等數(shù)學(xué)樊映川S01…002理論力學(xué)羅遠(yuǎn)祥L(zhǎng)01…003高等數(shù)學(xué)華羅庚S01…004線性代數(shù)欒汝書S02………………高等數(shù)學(xué)001,003…理論力學(xué)002…線性代數(shù)004………樊映川001,…華羅庚003…欒汝書004………L002…S001,003………XXXXXXXXXXXXXXXXX如何對(duì)博弈問(wèn)題進(jìn)行抽象？1234512354BACDE如何對(duì)交通線路圖進(jìn)行抽象？數(shù)據(jù)結(jié)構(gòu)的形式化定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組:Data_Structure＝（D，R）

其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。

D={學(xué)校，系，處，研究機(jī)構(gòu)，教研室，實(shí)驗(yàn)室}R={<學(xué)校，系〉，<學(xué)校,處>,<學(xué)校，研究機(jī)構(gòu)>,<系,教研室>,<系,實(shí)驗(yàn)室>}數(shù)據(jù)類型的表示和實(shí)現(xiàn)數(shù)據(jù)類型：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。一個(gè)高級(jí)程序語(yǔ)言的數(shù)據(jù)類型可分為：原子型：不可分解結(jié)構(gòu)類型：由若干分量組成抽象數(shù)據(jù)類型（ADT）:是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。（與邏輯特性有關(guān)，與存儲(chǔ)、實(shí)現(xiàn)無(wú)關(guān)）算法和算法分析（一）算法的5個(gè)重要特性：程序=算法+數(shù)據(jù)結(jié)構(gòu)評(píng)價(jià)一個(gè)算法的原則：正確性：要求P14可讀性健壯性：當(dāng)輸入非法時(shí)，能適當(dāng)做出反映或進(jìn)行處理效率與低存儲(chǔ)量需求算法的描述算法的描述可以是自然語(yǔ)言、偽語(yǔ)言、框圖、類語(yǔ)言完成條列式：以文字形式來(lái)描述步驟流程圖：以圖形符號(hào)來(lái)描述解決問(wèn)題的方法（僅適合于小問(wèn)題）偽碼：夾雜程序語(yǔ)法和自然語(yǔ)言的形式描述解決問(wèn)題的方法。程序語(yǔ)句：程序語(yǔ)法形式描述解決問(wèn)題的方法算法的時(shí)間復(fù)雜度分析算法執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。語(yǔ)句頻度：該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)

最佳狀況（下限）、最壞狀況（上限）算法的時(shí)間復(fù)雜度：指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間。也是算法中語(yǔ)句總的執(zhí)行次數(shù)T(n)。隨n的變化確定數(shù)量級(jí)，用“O”來(lái)表示數(shù)量級(jí)，記作：T(n)=O(f(n))x=x+1；其時(shí)間復(fù)雜度為O(1)，算法的時(shí)間復(fù)雜性與輸入規(guī)模n無(wú)關(guān)我們稱之為常量階；

for(i=1;i<=n;i++)x=x+1;其時(shí)間復(fù)雜度為O(n)，我們稱之為線性階；for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;

其時(shí)間復(fù)雜度為O(n2),我們稱之為平方階。for(i=1;i<=n;i*2)for(j=1;j<=n;j++)x=x+1;

其時(shí)間復(fù)雜度為O(n*logn),我們稱之為線性對(duì)數(shù)階。2一般地，隨n的增大，T(n)的增長(zhǎng)較慢的算法為最優(yōu)的算法。對(duì)于足夠大的n，常用的時(shí)間復(fù)雜性存在以下順序：O(1)<O(logn)<O(n)<O(n*logn)<O(n2)<

O(n3)…<O(2n)<O(3n)<…<O(n!)22程序步確定方法關(guān)于復(fù)雜度數(shù)量級(jí)的表示方法O(n)C+O(n)O(n)C*O(n)O(n)O(n)*O(n)順序語(yǔ)句C一重循環(huán)n多重循環(huán)m*n、m*n*l、m*n*l*t

……條件判斷Max(u,v)（u和v也可能是常數(shù)）例：For(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}n次n次n次整個(gè)算法的執(zhí)行時(shí)間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù)n3成正比，記作T(n)=O(n3)對(duì)于一個(gè)多項(xiàng)式的時(shí)間復(fù)雜度，只記它最高的冪次。算法平均時(shí)間復(fù)雜度：所有可能的輸入實(shí)例都以等概率的情況出現(xiàn)時(shí)，算法的預(yù)期運(yùn)行時(shí)間。算法最壞時(shí)間復(fù)雜度：算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界。

算法的時(shí)間復(fù)雜度不僅僅依賴于問(wèn)題的規(guī)模，還取決于輸入實(shí)例的初始狀態(tài)

e.g折半查找法最好情況：1（x=n/2）最壞情況：logn

一般來(lái)說(shuō)，在普通應(yīng)用場(chǎng)合中使用折半查找法時(shí)，以最壞情況時(shí)的復(fù)雜度作為該算法的復(fù)雜度2算法的空間復(fù)雜度分析空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束時(shí)所需的最大存儲(chǔ)量。(自身運(yùn)行所需的內(nèi)存單元、輔助內(nèi)存單元）記為S(n)=O(f(n))思考：某程序的時(shí)間復(fù)雜度為(14n+n*lgn+n2+37），其數(shù)量級(jí)表示為O（？）有一個(gè)程序片段：……X=1000;While(x!=5)X=x/10;……時(shí)間復(fù)雜度為O（n）對(duì)不對(duì)？

O（lg(n)）呢？數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的模型，描述操作對(duì)象之間的關(guān)系，它與數(shù)據(jù)的存儲(chǔ)方式、位置無(wú)關(guān)。研究表明：元素之間必是下列四種關(guān)系之一：集合線性結(jié)構(gòu)(表、棧、隊(duì)列）樹圖或網(wǎng)狀數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的