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

1、 數(shù) 據(jù) 結(jié) 構(gòu)教材和教學(xué)參考資源教材和教學(xué)參考資源教材：教材：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C語言描述語言描述 耿國華耿國華 高等教育出版社高等教育出版社參考教材參考教材 ：1.1.數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C C語言版）語言版） 嚴(yán)蔚敏嚴(yán)蔚敏 清華大學(xué)出版社清華大學(xué)出版社2.2.數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 許卓群編許卓群編 高等教育出版社（高等教育出版社（C+)C+)3.3.數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 齊德昱編齊德昱編 清華大學(xué)出版社清華大學(xué)出版社(C+)(C+)4.4.數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析 李春葆編李春葆編 清華大學(xué)出版社清華大學(xué)出版社5.5.數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典李春

2、葆等編李春葆等編 清華大學(xué)出版社清華大學(xué)出版社 6.6.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析 陳守禮等主編陳守禮等主編 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社7. 7. 網(wǎng)絡(luò)資源網(wǎng)絡(luò)資源(http:/ (http:/ 課程性質(zhì)課程性質(zhì)v數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課專業(yè)基礎(chǔ)課 公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課v在教學(xué)計(jì)劃中的地位：在教學(xué)計(jì)劃中的地位：核心、承上啟下核心、承上啟下 前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語言前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語言 后續(xù)課：數(shù)據(jù)庫、操作系統(tǒng)、編譯原理后續(xù)課：數(shù)據(jù)

3、庫、操作系統(tǒng)、編譯原理v屬于武術(shù)中的屬于武術(shù)中的“練功練功”科目科目 “練武不練功，到頭一場(chǎng)空練武不練功，到頭一場(chǎng)空”v考研科目，面試科目考研科目，面試科目學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo) 知識(shí)方面知識(shí)方面掌握基本的數(shù)據(jù)結(jié)構(gòu)掌握基本的數(shù)據(jù)結(jié)構(gòu) 工具箱工具箱復(fù)用、修改、重組復(fù)用、修改、重組掌握數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法以及經(jīng)典算法掌握數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法以及經(jīng)典算法 學(xué)習(xí)經(jīng)典算法學(xué)習(xí)經(jīng)典算法模仿模仿掌握初步的算法分析技術(shù)掌握初步的算法分析技術(shù) 評(píng)價(jià)算法、改進(jìn)算法評(píng)價(jià)算法、改進(jìn)算法學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo) 能力方面能力方面培養(yǎng)算法設(shè)計(jì)能力、程序設(shè)計(jì)能力培養(yǎng)算法設(shè)計(jì)能力、程序設(shè)計(jì)能力 算法算法程序的靈魂程序的靈魂 問題求解過程：?jiǎn)栴}

4、問題求解過程：?jiǎn)栴}想法想法算法算法程序程序 程序設(shè)計(jì)研究的層次：算法程序設(shè)計(jì)研究的層次：算法方法學(xué)方法學(xué)語言語言工具工具培養(yǎng)計(jì)算機(jī)思維能力培養(yǎng)計(jì)算機(jī)思維能力 計(jì)算機(jī)思維：邏輯思維和抽象思維計(jì)算機(jī)思維：邏輯思維和抽象思維 計(jì)算機(jī)求解問題的思路：計(jì)算機(jī)求解問題的思路： 問題問題形式化描述形式化描述自動(dòng)化計(jì)算自動(dòng)化計(jì)算學(xué)習(xí)要求學(xué)習(xí)要求v循序漸進(jìn)，切忌心浮氣躁循序漸進(jìn)，切忌心浮氣躁 提高課外學(xué)習(xí)的時(shí)間和內(nèi)容提高課外學(xué)習(xí)的時(shí)間和內(nèi)容 理解科學(xué)而不是背誦科學(xué)理解科學(xué)而不是背誦科學(xué) 會(huì)讀書，會(huì)學(xué)習(xí)會(huì)讀書，會(huì)學(xué)習(xí) 正確對(duì)待考試正確對(duì)待考試v作習(xí)題作習(xí)題v作實(shí)驗(yàn)作實(shí)驗(yàn)v聽課筆記聽課筆記 本本 課課 程程 教教

5、學(xué)學(xué) 內(nèi)內(nèi) 容容第一章第一章 緒論緒論第二章第二章 線性表線性表第三章第三章 棧和隊(duì)列棧和隊(duì)列第四章第四章 串串第五章第五章 數(shù)組和廣義表數(shù)組和廣義表第六章第六章 樹和二叉樹樹和二叉樹第七章第七章 圖圖第八章第八章 查找查找第九章第九章 內(nèi)部排序內(nèi)部排序 本本 課課 程程 內(nèi)內(nèi) 容容 結(jié)結(jié) 構(gòu)構(gòu)數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)線線性性結(jié)結(jié)構(gòu)構(gòu)非非線線性性結(jié)結(jié)構(gòu)構(gòu)線性表線性表?xiàng)ｊ?duì)列隊(duì)列串串?dāng)?shù)組和廣義表數(shù)組和廣義表順序表順序表鏈表鏈表兩種存兩種存儲(chǔ)結(jié)構(gòu)儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)樹樹圖圖二叉樹的存儲(chǔ)二叉樹的存儲(chǔ)二叉樹的遍歷二叉樹的遍歷樹和森林樹和森林哈夫曼樹及哈夫曼編碼哈夫曼樹及哈夫曼編碼圖的存儲(chǔ)圖的

6、存儲(chǔ)圖的遍歷圖的遍歷最小生成樹最小生成樹拓?fù)渑判蚝完P(guān)鍵路徑拓?fù)渑判蚝完P(guān)鍵路徑最短路徑最短路徑查找查找排序排序靜態(tài)靜態(tài)動(dòng)態(tài)動(dòng)態(tài)哈希表哈希表內(nèi)部?jī)?nèi)部外部外部 第一章第一章 緒緒 論論本章主要內(nèi)容：本章主要內(nèi)容：了解數(shù)據(jù)結(jié)構(gòu)興起與發(fā)展了解數(shù)據(jù)結(jié)構(gòu)興起與發(fā)展 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念算法的概念、分析和評(píng)價(jià)算法的概念、分析和評(píng)價(jià)學(xué)習(xí)重點(diǎn)及要求：學(xué)習(xí)重點(diǎn)及要求： 掌握數(shù)據(jù)結(jié)構(gòu)的基本概念掌握數(shù)據(jù)結(jié)構(gòu)的基本概念 掌握算法的概念及評(píng)價(jià)掌握算法的概念及評(píng)價(jià)本章難點(diǎn)本章難點(diǎn): : 對(duì)數(shù)據(jù)結(jié)構(gòu)的理解對(duì)數(shù)據(jù)結(jié)構(gòu)的理解 算法時(shí)間復(fù)雜度的分析算法時(shí)間復(fù)雜度的分析1.1 數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展1

7、.2 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.4 算法和算法分析算法和算法分析 第一章第一章 緒緒 論論1938年出生，年出生，25歲畢業(yè)于加州理工歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。歲任副教授。30歲時(shí)，加盟斯坦歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從福大學(xué)計(jì)算機(jī)系，任教授。從31歲歲起，開始出版他的歷史性經(jīng)典巨著：起，開始出版他的歷史性經(jīng)典巨著：The Art of Computer Programming他計(jì)劃共寫他計(jì)劃共寫7卷，然而出版三卷之后，卷，然而出版三卷之后，已震驚世界，使

8、他獲得計(jì)算機(jī)科學(xué)已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年僅僅36歲。歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人克努思克努思http:/ 1.1 數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展 數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展 數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)1. 無結(jié)構(gòu)階段無結(jié)構(gòu)階段2. 結(jié)構(gòu)化階段：數(shù)據(jù)結(jié)構(gòu)算法程序結(jié)構(gòu)化階段：數(shù)據(jù)結(jié)構(gòu)算法程序3. 面向?qū)ο箅A段：面向?qū)ο箅A段： （數(shù)據(jù)結(jié)構(gòu)算法）程序（數(shù)據(jù)結(jié)構(gòu)算法）程序1.1 數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展 1.2 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

9、計(jì)算機(jī)求解問題計(jì)算機(jī)求解問題: 問題問題 抽象出問題的模型抽象出問題的模型 求模型的解求模型的解 問題問題數(shù)值問題數(shù)值問題數(shù)學(xué)方程數(shù)學(xué)方程 非數(shù)值問題非數(shù)值問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)例例1 學(xué)籍管理問題學(xué)籍管理問題表結(jié)構(gòu)表結(jié)構(gòu)學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別出生日期出生日期政治面貌政治面貌0001王王 軍軍男男1983/09/02團(tuán)員團(tuán)員0002李李 明明男男1982/12/25黨員黨員0003湯曉影湯曉影女女1984/03/26團(tuán)員團(tuán)員完成什么功能完成什么功能?各表項(xiàng)之間是什么關(guān)系？各表項(xiàng)之間是什么關(guān)系？1.2 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象例例2 人機(jī)對(duì)弈問題人機(jī)對(duì)弈問題樹結(jié)構(gòu)樹結(jié)構(gòu)如何實(shí)現(xiàn)對(duì)弈如

10、何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？各格局之間是什么關(guān)系？.1.2 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象例例3 教學(xué)計(jì)劃編排問題教學(xué)計(jì)劃編排問題圖結(jié)構(gòu)圖結(jié)構(gòu)C4, C5, C6數(shù)據(jù)庫原理數(shù)據(jù)庫原理C7C2, C4計(jì)算機(jī)原理計(jì)算機(jī)原理C6C3, C4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C5C1, C2程序設(shè)計(jì)程序設(shè)計(jì)C4C1離散數(shù)學(xué)離散數(shù)學(xué)C3無無計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論C2無無高等數(shù)學(xué)高等數(shù)學(xué)C1先修課先修課課程名稱課程名稱編號(hào)編號(hào)C1C2C3C4C6C5C7如何表示課程之間的先修關(guān)系？如何表示課程之間的先修關(guān)系？1.2 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值非數(shù)值問題中計(jì)問題中計(jì)算機(jī)

11、的算機(jī)的操作對(duì)象操作對(duì)象以及它們之間的以及它們之間的關(guān)系關(guān)系和和操作操作的學(xué)科。的學(xué)科。1.2 數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象1.1.數(shù)據(jù)數(shù)據(jù)2.2.數(shù)據(jù)元素?cái)?shù)據(jù)元素3.3.數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)4.4.數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象5.5.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)6.6.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.數(shù)據(jù)數(shù)據(jù) 能被輸入計(jì)算機(jī)且能被能被輸入計(jì)算機(jī)且能被計(jì)算機(jī)處理計(jì)算機(jī)處理的一切的一切對(duì)象。是信息的載體，是客觀事物的對(duì)象。是信息的載體，是客觀事物的符號(hào)符號(hào)表示。表示。數(shù)據(jù)有兩大類：數(shù)據(jù)有兩大類：數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等非數(shù)據(jù)數(shù)據(jù)：圖形、圖像、聲音

12、、文字等非數(shù)據(jù)數(shù)據(jù)：圖形、圖像、聲音、文字等數(shù)值計(jì)算數(shù)值計(jì)算非數(shù)值計(jì)算非數(shù)值計(jì)算1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念2.2.數(shù)據(jù)元素?cái)?shù)據(jù)元素 是是數(shù)據(jù)數(shù)據(jù)這個(gè)集合中的一個(gè)個(gè)體。這個(gè)集合中的一個(gè)個(gè)體。 是現(xiàn)實(shí)世界中某是現(xiàn)實(shí)世界中某獨(dú)立實(shí)體獨(dú)立實(shí)體的數(shù)據(jù)描述。的數(shù)據(jù)描述。在計(jì)算在計(jì)算機(jī)程序中通常作為一個(gè)機(jī)程序中通常作為一個(gè)整體整體進(jìn)行考慮和處理。進(jìn)行考慮和處理。數(shù)數(shù)據(jù)結(jié)構(gòu)討論的據(jù)結(jié)構(gòu)討論的基本單位基本單位，一般由若干，一般由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成。組成。有時(shí)稱為有時(shí)稱為結(jié)點(diǎn)結(jié)點(diǎn)、記錄或表目。、記錄或表目。1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念3.3.數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) 具有獨(dú)

13、立意義的具有獨(dú)立意義的最小數(shù)據(jù)單位最小數(shù)據(jù)單位，是對(duì)數(shù)據(jù)元素，是對(duì)數(shù)據(jù)元素 屬性的描述屬性的描述。 有時(shí)稱有時(shí)稱域或字段域或字段。 學(xué)學(xué) 號(hào)號(hào) 姓姓 名名 性性別別 籍籍 貫貫 出出生生年年月月 1 98131 劉劉激激揚(yáng)揚(yáng) 男男 北北 京京 1979.12 2 98164 衣衣春春生生 男男 青青 島島 1979.07 3 98165 盧盧聲聲凱凱 男男 天天 津津 1981.02 4 98182 袁袁秋秋慧慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊熊南南燕燕 女女 蘇蘇 州州 1980.03 7 98297 宮宮

14、力力 男男 北北 京京 1981.01 8 98310 蔡蔡曉曉莉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間是包含關(guān)系：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間是包含關(guān)系： 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) 數(shù)據(jù)元素?cái)?shù)據(jù)元素 數(shù)據(jù)。數(shù)據(jù)。 組成組成組成組成1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)元素?cái)?shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位，是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。其中的數(shù)據(jù)項(xiàng)一般不予考慮。 4.4.數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 具有具

15、有相同特征相同特征的數(shù)據(jù)元素的集合。數(shù)據(jù)的的數(shù)據(jù)元素的集合。數(shù)據(jù)的子集。子集。例如：例如： 數(shù)據(jù)集合數(shù)據(jù)集合D=0,1,A,B,Z 則：數(shù)據(jù)對(duì)象正整數(shù)則：數(shù)據(jù)對(duì)象正整數(shù)N=0,1, 數(shù)據(jù)對(duì)象字母數(shù)據(jù)對(duì)象字母C=A,B,Z 數(shù)據(jù)元素是數(shù)據(jù)的一個(gè)個(gè)體，數(shù)據(jù)元素是數(shù)據(jù)的一個(gè)個(gè)體，0,1,A,B 數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集，數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集，N，C1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念5.5.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 相互之間存在一種或多種特定相互之間存在一種或多種特定關(guān)系關(guān)系的數(shù)據(jù)元素的數(shù)據(jù)元素的集合的集合。1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽

16、象出來的數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型數(shù)據(jù)模型學(xué)籍管理問題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？學(xué)籍管理問題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？人機(jī)對(duì)弈問題中，格局之間的邏輯關(guān)系指的是什么？人機(jī)對(duì)弈問題中，格局之間的邏輯關(guān)系指的是什么？教學(xué)計(jì)劃編排問題中，課程之間的邏輯關(guān)系指的是什么？教學(xué)計(jì)劃編排問題中，課程之間的邏輯關(guān)系指的是什么？1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)和和存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系邏輯關(guān)系的整體。的整體。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為按

17、照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)和和存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系邏輯關(guān)系的整體。的整體。存儲(chǔ)結(jié)構(gòu)：又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在存儲(chǔ)結(jié)構(gòu)：又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)計(jì)算機(jī)中的表示中的表示。存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語言。在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語言。1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是集合：數(shù)據(jù)元素之間就是 “屬于同一個(gè)

18、集合屬于同一個(gè)集合” ；1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是集合：數(shù)據(jù)元素之間就是 “屬于同一個(gè)集合屬于同一個(gè)集合” ； 線性結(jié)構(gòu)：數(shù)據(jù)元素之間線性結(jié)構(gòu)：數(shù)據(jù)元素之間 存在著一對(duì)一的線性關(guān)系；存在著一對(duì)一的線性關(guān)系；1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是集合：數(shù)據(jù)元素之間就是 “屬于同一個(gè)集合屬于同一個(gè)集合” ； 線性結(jié)構(gòu)：數(shù)據(jù)元素之間線性結(jié)構(gòu)：數(shù)據(jù)元素之間 存在著一對(duì)一的線性關(guān)系；存在著一對(duì)一的線性關(guān)系； 樹

19、結(jié)構(gòu)：數(shù)據(jù)元素之間存在樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在 著一對(duì)多的層次關(guān)系；著一對(duì)多的層次關(guān)系； 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是集合：數(shù)據(jù)元素之間就是 “屬于同一個(gè)集合屬于同一個(gè)集合” ； 線性結(jié)構(gòu)：數(shù)據(jù)元素之間線性結(jié)構(gòu)：數(shù)據(jù)元素之間 存在著一對(duì)一的線性關(guān)系；存在著一對(duì)一的線性關(guān)系； 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在 著一對(duì)多的層次關(guān)系；著一對(duì)多的層次關(guān)系； 圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在 著多對(duì)多的任意關(guān)系。著多對(duì)多的任意關(guān)系。1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念batcateat起始地址起始地址例：（例

20、：（bat, cat, eat）1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 通常有兩種存儲(chǔ)結(jié)構(gòu)：通常有兩種存儲(chǔ)結(jié)構(gòu)：(1)(1)順順序存儲(chǔ)結(jié)構(gòu)序存儲(chǔ)結(jié)構(gòu)：用一組：用一組連續(xù)連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)數(shù)據(jù)元素，存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素?cái)?shù)據(jù)元素之間的邏輯關(guān)系由元素的的存儲(chǔ)位置存儲(chǔ)位置來表示。來表示。 通常有兩種存儲(chǔ)結(jié)構(gòu)：通常有兩種存儲(chǔ)結(jié)構(gòu)：(1)(1)順序存儲(chǔ)結(jié)構(gòu)：用一組順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)數(shù)據(jù)元素，存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素?cái)?shù)據(jù)元素之間的邏輯關(guān)系由元素的的存儲(chǔ)位置存儲(chǔ)位置來表示。來表示。(2) (2)

21、鏈接存儲(chǔ)結(jié)構(gòu)：用一組鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用元素之間的邏輯關(guān)系用指針指針來表來表示示例：（例：（bat, cat, eat）0200020803000325 bat0200 cat0325 eat 1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題面向問題的，反的，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具體實(shí)現(xiàn)的視圖，是體實(shí)現(xiàn)的視圖，是面

22、向計(jì)算機(jī)面向計(jì)算機(jī)的。的。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。不同的。 1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念6.6.抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(1)(1)數(shù)據(jù)類型數(shù)據(jù)類型 數(shù)據(jù)類型是一個(gè)數(shù)據(jù)類型是一個(gè)值的集合值的集合和定義在這個(gè)值集上的一和定義在這個(gè)值集上的一組組操作操作的總稱。的總稱。 數(shù)據(jù)類型是數(shù)據(jù)類型是數(shù)據(jù)存儲(chǔ)數(shù)據(jù)存儲(chǔ)和和操作操作的的“封裝封裝” 。了解其了解其抽抽象特性象特性，如是什么類型，能進(jìn)行什么操作即可。，如是什么類型

23、，能進(jìn)行什么操作即可。 如：如：int、 float等等(2)(2)抽象抽象 抽出問題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具抽出問題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具體事物的一個(gè)概括。體事物的一個(gè)概括。 如：如： 地圖、駕駛汽車地圖、駕駛汽車1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念(3)(3)抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（ Abstract Data Type:ADT)Abstract Data Type:ADT) 一個(gè)一個(gè)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的以及定義在該結(jié)構(gòu)上的一組操作一組操作的總的總稱。稱。 ADT的三個(gè)不同的視圖：的三個(gè)不同的視圖：ADTl邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)l操作

24、集合操作集合數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)l存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)l算法設(shè)計(jì)算法設(shè)計(jì)類類使用視圖使用視圖設(shè)計(jì)視圖設(shè)計(jì)視圖實(shí)現(xiàn)視圖實(shí)現(xiàn)視圖 成員變量成員變量 成員函數(shù)成員函數(shù)ADT的定義的定義 ADT的設(shè)計(jì)的設(shè)計(jì) ADT的實(shí)現(xiàn)的實(shí)現(xiàn)1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念定義格式：定義格式：ADT ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： 基本操作：基本操作： （相當(dāng)于聲明若干函數(shù)（相當(dāng)于聲明若干函數(shù)) ) ADT ADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型定義用三元組表示：抽象數(shù)據(jù)類型定義用三元組表示：（D D，S S，

25、P P），）， 其中，其中，D D是數(shù)據(jù)對(duì)象，是數(shù)據(jù)對(duì)象， S S是是D D上的關(guān)系集，上的關(guān)系集， P P是對(duì)是對(duì)D D的基本操作集。的基本操作集。1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 如：如：ADT ListADT List 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=aD=ai i|a|ai iElemSet, i=1,2,3,ElemSet, i=1,2,3,n,n0,n,n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1=aR1=|a|ai-1i-1,a,ai iD,i=2,D,i=2,nn 基本操作：基本操作： InitList(&L)InitList(&L)要點(diǎn)：要點(diǎn)： 操作結(jié)果：構(gòu)造一

26、個(gè)空的線性表操作結(jié)果：構(gòu)造一個(gè)空的線性表L L。 ListLength(L)ListLength(L) 初始條件：線性表初始條件：線性表L L已存在。已存在。 操作結(jié)果：返回操作結(jié)果：返回L L中數(shù)據(jù)元素個(gè)數(shù)中數(shù)據(jù)元素個(gè)數(shù)( (線性表的長(zhǎng)度線性表的長(zhǎng)度) ) ListInsert(&L,i,e) ListInsert(&L,i,e) 初始條件：線性表初始條件：線性表L L已存在，已存在，1iListLength(L)+11iListLength(L)+1 操作結(jié)果：在操作結(jié)果：在L L中第中第I I個(gè)位置之前插入新的數(shù)據(jù)元素個(gè)位置之前插入新的數(shù)據(jù)元素e e，L L的的 長(zhǎng)度加長(zhǎng)

27、度加1 1。 1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念對(duì)數(shù)據(jù)結(jié)構(gòu)設(shè)置的操作集合，實(shí)現(xiàn)各對(duì)數(shù)據(jù)結(jié)構(gòu)設(shè)置的操作集合，實(shí)現(xiàn)各種應(yīng)用對(duì)數(shù)據(jù)的各種訪問種應(yīng)用對(duì)數(shù)據(jù)的各種訪問 總結(jié)總結(jié)(1)ADT(1)ADT可理解為對(duì)數(shù)據(jù)類型的進(jìn)一步抽象可理解為對(duì)數(shù)據(jù)類型的進(jìn)一步抽象(2)(2)數(shù)據(jù)類型和數(shù)據(jù)類型和ADTADT的區(qū)別：的區(qū)別： 數(shù)據(jù)類型數(shù)據(jù)類型指的是高級(jí)程序設(shè)計(jì)語言支持的基本數(shù)據(jù)類型指的是高級(jí)程序設(shè)計(jì)語言支持的基本數(shù)據(jù)類型 ADTADT指的是指的是自定義的數(shù)據(jù)類型自定義的數(shù)據(jù)類型(3)ADT=(3)ADT=數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + + 一組一組基本操作基本操作 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的

28、基本概念 用標(biāo)準(zhǔn)用標(biāo)準(zhǔn)C C語言表示和實(shí)現(xiàn)語言表示和實(shí)現(xiàn)ADTADT描述時(shí)，主要包括以下兩描述時(shí)，主要包括以下兩個(gè)方面?zhèn)€方面: : (1) (1) 通過結(jié)構(gòu)體將通過結(jié)構(gòu)體將intint、 floatfloat等固有類型組合到一起等固有類型組合到一起, , 構(gòu)成一個(gè)結(jié)構(gòu)類型構(gòu)成一個(gè)結(jié)構(gòu)類型, , 再用再用typedeftypedef為該類型或該類型指針為該類型或該類型指針重新起一個(gè)名字。重新起一個(gè)名字。 (2) (2) 用用C C語言函數(shù)實(shí)現(xiàn)各操作。語言函數(shù)實(shí)現(xiàn)各操作。 數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)

29、結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)集合集合線性結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)圖結(jié)構(gòu) 非數(shù)值問題非數(shù)值問題 數(shù)數(shù)據(jù)據(jù)表表示示小結(jié)小結(jié)1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 n數(shù)據(jù)結(jié)構(gòu)主要研究?jī)?nèi)容：數(shù)據(jù)結(jié)構(gòu)主要研究?jī)?nèi)容： u數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及它們數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系之間的相應(yīng)關(guān)系u并對(duì)每種結(jié)構(gòu)定義相應(yīng)的各種運(yùn)算并對(duì)每種結(jié)構(gòu)定義相應(yīng)的各種運(yùn)算u設(shè)計(jì)出相應(yīng)的算法設(shè)計(jì)出相應(yīng)的算法u分析算法的效率分析算法的效率1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.4 1.4 算法和算法分析算法和算法分析一、算法一、算法二、算

30、法描述二、算法描述三、算法分析三、算法分析一、算法一、算法 算法算法是對(duì)特定問題是對(duì)特定問題求解步驟求解步驟的一種描述，的一種描述，是一個(gè)有限的指令集或指令的有限序列是一個(gè)有限的指令集或指令的有限序列。 1. 1. 算法（算法（AlgorithmAlgorithm）的定義）的定義1.4 1.4 算法和算法分析算法和算法分析2. 2. 算法的特性算法的特性 有限性有限性：有限步驟之內(nèi)正常結(jié)束，：有限步驟之內(nèi)正常結(jié)束， 不能形成無不能形成無窮循環(huán)。窮循環(huán)。 確定性確定性： 算法中的每一個(gè)步驟必須有確定含義，算法中的每一個(gè)步驟必須有確定含義， 無二義性。無二義性。 (3)(3)可行性可行性： 原則上

31、能精確進(jìn)行，原則上能精確進(jìn)行， 操作可通過已操作可通過已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成。實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成。(4)(4)輸入輸入： 有多個(gè)或有多個(gè)或0 0個(gè)輸入。個(gè)輸入。 (5)(5)輸出輸出： 至少有一個(gè)或多個(gè)輸出。至少有一個(gè)或多個(gè)輸出。一、算法一、算法1.4 1.4 算法和算法分析算法和算法分析 算法是解決問題的一種方法或一個(gè)過程，考慮如何將算法是解決問題的一種方法或一個(gè)過程，考慮如何將輸入轉(zhuǎn)換輸出，一個(gè)問題可以有多種算法。輸入轉(zhuǎn)換輸出，一個(gè)問題可以有多種算法。 程序是用某種程序設(shè)計(jì)語言對(duì)算法的具體實(shí)現(xiàn)。程序是用某種程序設(shè)計(jì)語言對(duì)算法的具體實(shí)現(xiàn)。 主要區(qū)別體現(xiàn)在有窮性、正確性和

32、描述方法：主要區(qū)別體現(xiàn)在有窮性、正確性和描述方法：(1)程序可以是無窮的，例如：程序可以是無窮的，例如：OS，算法是有窮的；，算法是有窮的；(2)程序可以是錯(cuò)誤的，算法必須是正確的；程序可以是錯(cuò)誤的，算法必須是正確的；(3)程序是用程序設(shè)計(jì)語言描述的，在機(jī)器上可以執(zhí)行；程序是用程序設(shè)計(jì)語言描述的，在機(jī)器上可以執(zhí)行； 算法可以用多種方式描述。算法可以用多種方式描述。3. 3. 算法與程序的區(qū)別算法與程序的區(qū)別 1.4 1.4 算法和算法分析算法和算法分析一、算法一、算法 歐幾里德算法mnr例：求兩個(gè)自然數(shù)例：求兩個(gè)自然數(shù) m 和和 n 的最大公的最大公約數(shù)。約數(shù)。 歐幾里德算法歐幾里德算法輾轉(zhuǎn)相

33、除法輾轉(zhuǎn)相除法1.4 1.4 算法和算法分析算法和算法分析二、算法的描述二、算法的描述自然語言自然語言流程圖流程圖程序設(shè)計(jì)語言程序設(shè)計(jì)語言偽代碼偽代碼1.4 1.4 算法和算法分析算法和算法分析 輸入輸入m 和和n； 求求m除以除以n的余數(shù)的余數(shù)r； 若若r等于等于0 0，則，則n為最大公約數(shù)，為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第算法結(jié)束；否則執(zhí)行第步；步； 將將n的值放在的值放在m中，將中，將r的值放的值放在在n中；中； 重新執(zhí)行第重新執(zhí)行第步。步。例：歐幾里德算法例：歐幾里德算法自然語言1.4 1.4 算法和算法分析算法和算法分析N開始輸入m和n r=m % nr=0m=n；n=r 輸出n結(jié)

34、束Y流 程 圖例：歐幾里德算法例：歐幾里德算法1.4 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ì)語言例：歐幾里德算法例：歐幾里德算法1.4 1.4 算法和算法分析算法和算法分析 1. r = m % n; 2. 循環(huán)直到循環(huán)直到 r 等于等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3.

35、輸出輸出 n ;偽 代 碼例：歐幾里德算法例：歐幾里德算法1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1.1.正確性正確性2.2.可讀性可讀性3.3.健壯性健壯性4.4.高效率與低存儲(chǔ)量的需求高效率與低存儲(chǔ)量的需求1.4 1.4 算法和算法分析算法和算法分析例：八枚硬幣中有一枚重，現(xiàn)有一個(gè)天秤例：八枚硬幣中有一枚重，現(xiàn)有一個(gè)天秤 怎樣選出？怎樣選出？方法一：方法一：1-2、3-4、5-6、7-8最好秤最好秤1 1次，最壞秤次，最壞秤4 4次次方法二：方法二：8/2、4/2、2/23 3次一定能選出次

36、一定能選出方法三：方法三：6/2，若平：，若平：2/2 否則：否則：2/22 2次一定能選出次一定能選出1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析 算法分析算法分析：對(duì)算法所需要的計(jì)算機(jī)資源：對(duì)算法所需要的計(jì)算機(jī)資源時(shí)間時(shí)間和和空間空間進(jìn)行估算。進(jìn)行估算。 時(shí)間復(fù)雜性（時(shí)間復(fù)雜性（Time Complexity） 空間復(fù)雜性（空間復(fù)雜性（Space Complexity）三、算法分析三、算法分析1.4 1.4 算法和算法分析算法和算法分析 算法分析的目：算法分析的目：改進(jìn)算法改進(jìn)算法提高算法的時(shí)間效提高算法的時(shí)間效率和空間效率。率和空間效率。 度量算法效率的方法：度量

37、算法效率的方法：事后統(tǒng)計(jì)事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開銷。：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開銷。 事前分析事前分析：對(duì)算法所消耗資源的一種估算方法。：對(duì)算法所消耗資源的一種估算方法。1.1.算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度算法的算法的執(zhí)行時(shí)間執(zhí)行時(shí)間每條語句執(zhí)行時(shí)間之和每條語句執(zhí)行時(shí)間之和執(zhí)行次數(shù)執(zhí)行次數(shù)執(zhí)行一次的時(shí)間執(zhí)行一次的時(shí)間指令系統(tǒng)、編譯的代碼質(zhì)量指令系統(tǒng)、編譯的代碼質(zhì)量單位時(shí)間單位時(shí)間每條語句每條語句執(zhí)行次數(shù)執(zhí)行次數(shù)之和之和基本語句基本語句的執(zhí)行次數(shù)的執(zhí)行次數(shù)1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析基本語句：基本語句：是執(zhí)行次數(shù)與是執(zhí)行次數(shù)與整個(gè)算

38、法的執(zhí)行次整個(gè)算法的執(zhí)行次數(shù)成數(shù)成 正比的操作指令。正比的操作指令。問題規(guī)模：?jiǎn)栴}規(guī)模：輸入量的多少。輸入量的多少。for (i=1; i=n; i+) for (j=1; j=n; j+) x+;問題規(guī)模：n基本語句：x+三、算法分析三、算法分析1.4 1.4 算法和算法分析算法和算法分析void MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) Cij = 0; for ( int k = 0; k 時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)（階）時(shí)，把時(shí)間復(fù)雜

39、度的數(shù)量級(jí)（階）稱為算法的稱為算法的漸進(jìn)時(shí)間復(fù)雜度漸進(jìn)時(shí)間復(fù)雜度 T(n) = O(f(n)1.4 1.4 算法和算法分析算法和算法分析2.2.大大O表示表示 定義定義 若存在兩個(gè)正的常數(shù)若存在兩個(gè)正的常數(shù)c和和n0，對(duì)于任意，對(duì)于任意nn0，都有，都有T( (n)cf( (n) )，則稱，則稱T( (n) )=O( (f( (n)n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之前的之前的情況無關(guān)情況無關(guān)緊要緊要T( (n) )cf f(n nv當(dāng)問題規(guī)模充分大時(shí)在漸近意義下的階當(dāng)問題規(guī)模充分大時(shí)在漸近意義下的階1.4 1.4 算法和算法分析算法和算法分析 定理：若定理：若A(n)=amnm+am

40、-1nm-1+a1n+a0是一個(gè)是一個(gè)m次多項(xiàng)式，則次多項(xiàng)式，則A(n)=O(nm)。說明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有說明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)。低次冪和最高次冪的系數(shù)。1.4 1.4 算法和算法分析算法和算法分析 用大用大O表示評(píng)估算法的復(fù)雜性，得到的只是表示評(píng)估算法的復(fù)雜性，得到的只是當(dāng)當(dāng)規(guī)模充分大規(guī)模充分大時(shí)的一個(gè)時(shí)的一個(gè)上界，上界，這個(gè)上界的這個(gè)上界的階越低階越低，則評(píng)估就則評(píng)估就越精確越精確，結(jié)果就越有價(jià)值。，結(jié)果就越有價(jià)值。f(n) = 2n3 + 2n2 + 2n +1T(n)=O(f(n)=O(n3) 常見時(shí)間復(fù)雜度常見時(shí)間復(fù)雜度

41、（按數(shù)量級(jí)遞增排列）（按數(shù)量級(jí)遞增排列） (1)、log2n) 、 n)、nlog2n)、 n2)、n3 )、 O 2n )、 3n)1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析n例：設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行例：設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為時(shí)間分別為 100n2 和和 2n，問：要使前者快于，問：要使前者快于后者，后者，n 至少要取多大？至少要取多大？ 解答：解答： 問題是找出滿足問題是找出滿足 100n2 2n = 8192 n = 14時(shí)，時(shí)，100n2 = 19600 2n = 16384 n = 15時(shí)，時(shí)，100n2 = 2250

42、0 2n = 32764 取取 n = 15 滿足要求。滿足要求。1.4 1.4 算法和算法分析算法和算法分析 n算法在運(yùn)行過程中附加的輔助存儲(chǔ)空間，與算法有關(guān)算法在運(yùn)行過程中附加的輔助存儲(chǔ)空間，與算法有關(guān) 空間復(fù)雜度是對(duì)算法執(zhí)行過程需要的輔助空空間復(fù)雜度是對(duì)算法執(zhí)行過程需要的輔助空間進(jìn)行度量，是問題規(guī)模的函數(shù)，間進(jìn)行度量，是問題規(guī)模的函數(shù)，表示為：表示為： S(n)=O(g(n)1.4 1.4 算法和算法分析算法和算法分析3.3.空間復(fù)雜度空間復(fù)雜度三、算法分析三、算法分析本本 章章 小小 結(jié)結(jié) 數(shù)據(jù)組織的三個(gè)層次：數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)數(shù)據(jù)組織的三個(gè)層次：數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng) 數(shù)據(jù)結(jié)構(gòu)主

43、要研究的三方面內(nèi)容：數(shù)據(jù)結(jié)構(gòu)主要研究的三方面內(nèi)容： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)）數(shù)據(jù)的邏輯結(jié)構(gòu) （線性結(jié)構(gòu)和非線結(jié)構(gòu)）（線性結(jié)構(gòu)和非線結(jié)構(gòu)） （2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) （順序方式、鏈?zhǔn)椒绞?、（順序方式、鏈?zhǔn)椒绞?、索引方式和散列方式索引方式和散列方式?（3）對(duì)數(shù)據(jù)實(shí)施的基本運(yùn)算）對(duì)數(shù)據(jù)實(shí)施的基本運(yùn)算: 算法算法算法分析：時(shí)間性能算法分析：時(shí)間性能時(shí)間復(fù)雜度時(shí)間復(fù)雜度 空間性能空間性能空間復(fù)雜度空間復(fù)雜度緒緒 論論數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算算 法法基基本本概概念念邏邏輯輯結(jié)結(jié)構(gòu)構(gòu)存存儲(chǔ)儲(chǔ)結(jié)結(jié)構(gòu)構(gòu)數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)元素?cái)?shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象ADT邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的分類的分類存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)常用存儲(chǔ)常用存儲(chǔ)方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性評(píng)價(jià)算法評(píng)價(jià)算法描述算法描述算法問題規(guī)模問題規(guī)模基本語句基本語句時(shí)間復(fù)雜度時(shí)間復(fù)雜度大大O記號(hào)記號(hào)關(guān)關(guān) 系系習(xí)習(xí) 題題1.( )1.( )是數(shù)據(jù)的最小單位，（是數(shù)據(jù)的最小單位，（ ）是討論數(shù)）是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位（基本單位）。據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位（基本單位）。2.2.順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系由（順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系由（ ) )表表示的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的數(shù)