數(shù)據(jù)結構c(王紅梅)課件1.ppt

主教材 王紅梅.數(shù)據(jù)結構（C版）.清華大學出版社 輔導及實驗教材 王紅梅.數(shù)據(jù)結構學習輔導與實驗指導.清華大學出版社 參考教材 1. 嚴蔚敏.數(shù)據(jù)結構.清華大學出版社.1997 2. 王曉東.數(shù)據(jù)結構與算法設計.電子工業(yè)出版社.2002 3. 曹宏慶譯.如何求解問題.中國水利水電出版社.2003,關于教材,課程性質(zhì),數(shù)據(jù)結構是計算機專業(yè)的專業(yè)基礎課 公共基礎課、專業(yè)基礎課、專業(yè)方向課、專業(yè)選修課 在教學計劃中的地位：核心、承上啟下 前導課：高等數(shù)學、離散數(shù)學、程序設計語言 后續(xù)課：數(shù)據(jù)庫、操作系統(tǒng)、編譯原理 屬于武術中的“練功”科目 “練武不練功，到頭一場空” 考研,學習目標,掌握基本的數(shù)據(jù)結構 工具箱復用、修改、重組 培養(yǎng)算法設計能力、程序設計能力 算法程序的靈魂 問題求解過程：問題想法算法程序 程序設計研究的層次：算法方法學語言工具 培養(yǎng)算法分析能力 評價算法、改進算法,學習要求,循序漸進，切忌心浮氣躁 提高課外學習的時間和內(nèi)容 理解科學而不是背誦科學讀書 正確對待考試 作習題 華羅庚：“學數(shù)學不做習題等于入寶山而空返” 作實驗 計算機學科是一門科學性與工程性并重的學科，表現(xiàn)為理論和實踐緊密結合的特征。,如何使用立體化教材,主教材 思想火花、人物小傳 輔導教材 知識結構、學習要點、重點難點釋疑、習題解析 實驗教材 驗證實驗綜合實驗設計實驗 網(wǎng)站 學校精品課程網(wǎng)站,成績組成,實驗成績 30：出勤程序報告 期末考試成績 70：接近同類學校考研水平 課程設計 成績：優(yōu)、良、中、及、不及,第 1 章 緒 論,數(shù)據(jù)結構的興起和發(fā)展 數(shù)據(jù)結構的研究對象 數(shù)據(jù)結構的基本概念 算法及算法分析,本章的基本內(nèi)容是：,1938年出生，25歲畢業(yè)于加州理工學院數(shù)學系，博士畢業(yè)后留校任教，28歲任副教授。30歲時，加盟斯坦福大學計算機系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著： The Art of Computer Programming 他計劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計算機科學界的最高榮譽圖靈獎，此時，他年僅36歲。,數(shù)據(jù)結構的創(chuàng)始人克努特,1.1 數(shù)據(jù)結構的興起和發(fā)展,程序設計的實質(zhì)是什么?,數(shù)據(jù)表示：將數(shù)據(jù)存儲在計算機中 數(shù)據(jù)處理：處理數(shù)據(jù)，求解問題,數(shù)據(jù)結構問題起源于程序設計,數(shù)據(jù)結構隨著程序設計的發(fā)展而發(fā)展,數(shù)據(jù)結構的發(fā)展并未終結,1. 無結構階段 2. 結構化階段：數(shù)據(jù)結構算法程序 3. 面向?qū)ο箅A段： （數(shù)據(jù)結構算法）程序,1.1 數(shù)據(jù)結構的興起和發(fā)展,1.2 數(shù)據(jù)結構的研究對象,計算機求解問題: 問題抽象出問題的模型求模型的解 問題數(shù)值問題、非數(shù)值問題 數(shù) 值 問 題數(shù)學方程 非數(shù)值問題數(shù)據(jù)結構,例1 學籍管理問題表結構,1.2 數(shù)據(jù)結構的研究對象,完成什么功能?各表項之間是什么關系？,例2 人機對弈問題樹結構,1.2 數(shù)據(jù)結構的研究對象,如何實現(xiàn)對弈?各格局之間是什么關系？,例3 教學計劃編排問題圖結構,1.2 數(shù)據(jù)結構的研究對象,如何表示課程之間的先修關系？,數(shù)據(jù)結構是研究非數(shù)值問題中計算機的操作對象以及它們之間的關系和操作的學科。,1.2 數(shù)據(jù)結構的研究對象,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)：所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。 數(shù)值數(shù)據(jù)：整數(shù)、實數(shù)等 非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等 數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 數(shù)據(jù)項：構成數(shù)據(jù)元素的不可分割的最小單位。 數(shù)據(jù)對象：具有相同性質(zhì)的數(shù)據(jù)元素的集合。,數(shù)據(jù)結構的基本概念,數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項之間的關系,包含關系：數(shù)據(jù)是由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項組成。 數(shù)據(jù)元素是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項一般不予考慮。,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。 邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,數(shù)據(jù)的邏輯結構是從具體問題抽象出來的數(shù)據(jù)模型,數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。 邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。 存儲結構：又稱為物理結構，是數(shù)據(jù)及其邏輯結構在計算機中的表示。,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,存儲結構實質(zhì)上是內(nèi)存分配， 在具體實現(xiàn)時，依賴于計算機語言。,數(shù)據(jù)結構從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是 “屬于同一個集合” ；,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是 “屬于同一個集合” ； 線性結構：數(shù)據(jù)元素之間 存在著一對一的線性關系；,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是 “屬于同一個集合” ； 線性結構：數(shù)據(jù)元素之間 存在著一對一的線性關系； 樹結構：數(shù)據(jù)元素之間存在 著一對多的層次關系；,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是 “屬于同一個集合” ； 線性結構：數(shù)據(jù)元素之間 存在著一對一的線性關系； 樹結構：數(shù)據(jù)元素之間存在 著一對多的層次關系； 圖結構：數(shù)據(jù)元素之間存在 著多對多的任意關系。,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,通常有兩種存儲結構： 1. 順序存儲結構：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系由元素的存儲位置來表示。,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,通常有兩種存儲結構： 1. 順序存儲結構：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系由元素的存儲位置來表示。 2. 鏈接存儲結構：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系用指針來表示 。,例：（bat, cat, eat）,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的基本概念,bat 0200,cat 0325,eat ,邏輯結構和存儲結構之間的關系,數(shù)據(jù)的邏輯結構屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內(nèi)部的構成方式；數(shù)據(jù)的存儲結構屬于具體實現(xiàn)的視圖，是面向計算機的。 一種數(shù)據(jù)的邏輯結構可以用多種存儲結構來存儲，而采用不同的存儲結構，其數(shù)據(jù)處理的效率往往是不同的。,1.3 數(shù)據(jù)結構的基本概念,數(shù)據(jù)結構的訪問接口,對數(shù)據(jù)結構的訪問是指對數(shù)據(jù)的讀取、修改、加工、處理等操作。 數(shù)據(jù)結構的基本操作：各種應用都能通過這些操作實現(xiàn)對數(shù)據(jù)結構的各種訪問。 基本操作的特性：抽象性、基本性、完備性、一般性 訪問接口：操作的調(diào)用形式與規(guī)范（例如形參表、返回類型等）。 數(shù)據(jù)結構的訪問接口：數(shù)據(jù)結構基本操作接口的全體。,1.3 數(shù)據(jù)結構的基本概念,抽象數(shù)據(jù)類型,1. 數(shù)據(jù)類型（Data Type）：一組值的集合以及定義于這個值集上的一組操作的總稱。 例如：C+中的整型變量 2. 抽象（Abstract）:抽出問題本質(zhì)的特征而忽略非本質(zhì)的細節(jié)。 例如： 地圖、駕駛汽車 3. 抽象數(shù)據(jù)類型（Abstract Data Type，ADT）:一個數(shù)據(jù)結構以及定義在該結構上的一組操作的總稱。,1.3 數(shù)據(jù)結構的基本概念,ADT是對數(shù)據(jù)類型的進一步抽象,ADT的不同視圖,1.3 數(shù)據(jù)結構的基本概念,ADT 抽象數(shù)據(jù)類型名 Data 數(shù)據(jù)元素之間邏輯關系的定義 Operation 操作1 前置條件：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài) 輸 入：執(zhí)行此操作所需要的輸入 功 能：該操作將完成的功能 輸 出：執(zhí)行該操作后產(chǎn)生的輸出 后置條件：執(zhí)行該操作后數(shù)據(jù)的狀態(tài) 操作2 操作n endADT,ADT的定義形式,1.3 數(shù)據(jù)結構的基本概念,1.3 數(shù)據(jù)結構的基本概念（小結）,數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等,算法的相關概念,1.算法（Algorithm）:是對特定問題求解步驟的一種描述，是指令的有限序列。,2. 算法的五大特性： 輸入：一個算法有零個或多個輸入。 輸出：一個算法有一個或多個輸出。 有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內(nèi)完成。 確定性：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出。 可行性：算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。,1.4 算法及算法分析,歐幾里德算法,m,n,r,例：歐幾里德算法輾轉相除法求兩個自然數(shù) m 和 n 的最大公約數(shù),1.4 算法及算法分析,算法的描述方法自然語言,優(yōu)點：容易理解 缺點：冗長、二義性 使用方法：粗線條描述算法思想 注意事項：避免寫成自然段,1.4 算法及算法分析, 輸入m 和n； 求m除以n的余數(shù)r； 若r等于0，則n為最大公約數(shù)，算法結束；否則執(zhí)行第步； 將n的值放在m中，將r的值放在n中； 重新執(zhí)行第步。,例：歐幾里德算法,自然語言,1.4 算法及算法分析,優(yōu)點：流程直觀 缺點：缺少嚴密性、靈活性 使用方法：描述簡單算法 注意事項：注意抽象層次,算法的描述方法流程圖,1.4 算法及算法分析,流 程 圖,例：歐幾里德算法,1.4 算法及算法分析,優(yōu)點：能由計算機執(zhí)行 缺點：抽象性差，對語言要求高 使用方法：算法需要驗證 注意事項：將算法寫成子函數(shù),算法的描述方法程序設計語言,1.4 算法及算法分析,#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n; void main( ) coutCommonFactor(63, 54)endl; ,程序設計語言,例：歐幾里德算法,1.4 算法及算法分析,4 算法及算法分析,偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。 優(yōu)點：表達能力強，抽象性強，容易理解,算法的描述方法偽代碼,1.4 算法及算法分析,1. r = m % n; 2. 循環(huán)直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 輸出 n ;,偽 代 碼,上述偽代碼再具體一些，用C+的函數(shù)來描述。請同學們自行完成！,例：歐幾里德算法,1.4 算法及算法分析,算法分析,度量算法效率的方法： 事后統(tǒng)計：將算法實現(xiàn)，測算其時間和空間開銷。 缺點： 編寫程序?qū)崿F(xiàn)算法將花費較多的時間和精力； 所得實驗結果依賴于計算機的軟硬件等環(huán)境因素。 事前分析：對算法所消耗資源的一種估算方法。,1.4 算法及算法分析,算法分析,算法分析（Algorithm Analysis）：對算法所需要的計算機資源時間和空間進行估算。 時間復雜性（Time Complexity） 空間復雜性（Space Complexity）,1.4 算法及算法分析,算法的時間復雜度分析,1.4 算法及算法分析,算法分析,算法的執(zhí)行時間每條語句執(zhí)行時間之和,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,問題規(guī)模：輸入量的多少。 基本語句：是執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的操作指令。,for (i=1; i=n; i+) for (j=1; j=n; j+) x+;,問題規(guī)模：n 基本語句：x+,1.4 算法及算法分析,算法分析,定義 若存在兩個正的常數(shù)c和n0，對于任意nn0，都有T(n)cf(n)，則稱T(n)=O(f(n),當問題規(guī)模充分大時在漸近意義下的階,1.4 算法及算法分析,算法分析大O符號,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一個m次多項式，則A(n)=O(nm)。,說明：在計算算法時間復雜度時，可以忽略所有低次冪和最高次冪的系數(shù)。,1.4 算法及算法分析,算法分析大O符號,例1-5 +x; 例1-6 for (i=1; i=n; +i) +x; 例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j) +x; 例1-8 for (i=1; i=n; +i) for (j=1; j=i-1; +j) +x;,1.4 算法及算法分析,算法分析,例1-9 for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; 例1-10 for (i=1; i=n; i=2*i) +x;,(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!),1.4 算法及算法分析,算法分析,最好情況、最壞情況、平均情況,例：在一維整型數(shù)組An中順序查找與給定值k相等的元素（假設該數(shù)組中有且僅有一個元素值為k）。,int Find(int A , int n) for (i=0; in; i+) if (Ai= =k) break; return i; ,1.4 算法及算法分析,基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關？,最好情況：出現(xiàn)概率較大時分析 最差情況：實時系統(tǒng) 平均情況