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