數(shù)據(jù)結(jié)構(gòu)c(王紅梅)課件1.ppt

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