《數(shù)據(jù)結構》課件第一章

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

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

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

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

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

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

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

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

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

O(n3)…<O(2n)<O(3n)<…<O(n!)22程序步確定方法關于復雜度數(shù)量級的表示方法O(n)C+O(n)O(n)C*O(n)O(n)O(n)*O(n)順序語句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次整個算法的執(zhí)行時間與該基本操作（乘法）重復執(zhí)行的次數(shù)n3成正比，記作T(n)=O(n3)對于一個多項式的時間復雜度，只記它最高的冪次。算法平均時間復雜度：所有可能的輸入實例都以等概率的情況出現(xiàn)時，算法的預期運行時間。算法最壞時間復雜度：算法在任何輸入實例上運行時間的上界。

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

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

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

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