數(shù)據(jù)結構第一章

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

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

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

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

5、學學 內內 容容第一章第一章 緒論緒論第二章第二章 線性表線性表第三章第三章 棧和隊列棧和隊列第四章第四章 串串第五章第五章 數(shù)組和廣義表數(shù)組和廣義表第六章第六章 樹和二叉樹樹和二叉樹第七章第七章 圖圖第八章第八章 查找查找第九章第九章 內部排序內部排序 本本 課課 程程 內內 容容 結結 構構數(shù)數(shù)據(jù)據(jù)結結構構線線性性結結構構非非線線性性結結構構線性表線性表棧棧隊列隊列串串數(shù)組和廣義表數(shù)組和廣義表順序表順序表鏈表鏈表兩種存兩種存儲結構儲結構順序存儲順序存儲鏈式存儲鏈式存儲樹樹圖圖二叉樹的存儲二叉樹的存儲二叉樹的遍歷二叉樹的遍歷樹和森林樹和森林哈夫曼樹及哈夫曼編碼哈夫曼樹及哈夫曼編碼圖的存儲圖的

6、存儲圖的遍歷圖的遍歷最小生成樹最小生成樹拓撲排序和關鍵路徑拓撲排序和關鍵路徑最短路徑最短路徑查找查找排序排序靜態(tài)靜態(tài)動態(tài)動態(tài)哈希表哈希表內部內部外部外部 第一章第一章 緒緒 論論本章主要內容：本章主要內容：了解數(shù)據(jù)結構興起與發(fā)展了解數(shù)據(jù)結構興起與發(fā)展 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念算法的概念、分析和評價算法的概念、分析和評價學習重點及要求：學習重點及要求： 掌握數(shù)據(jù)結構的基本概念掌握數(shù)據(jù)結構的基本概念 掌握算法的概念及評價掌握算法的概念及評價本章難點本章難點: : 對數(shù)據(jù)結構的理解對數(shù)據(jù)結構的理解 算法時間復雜度的分析算法時間復雜度的分析1.1 數(shù)據(jù)結構的興起和發(fā)展數(shù)據(jù)結構的興起和發(fā)展1

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

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

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

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

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

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

13、立意義的具有獨立意義的最小數(shù)據(jù)單位最小數(shù)據(jù)單位，是對數(shù)據(jù)元素，是對數(shù)據(jù)元素 屬性的描述屬性的描述。 有時稱有時稱域或字段域或字段。 學學 號號 姓姓 名名 性性別別 籍籍 貫貫 出出生生年年月月 1 98131 劉劉激激揚揚 男男 北北 京京 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ù)元素數(shù)據(jù)項1.3 1.3 數(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ù)。數(shù)據(jù)。 組成組成組成組成1.3 1.3 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念 數(shù)據(jù)元素數(shù)據(jù)元素是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位，是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項一般不予考慮。其中的數(shù)據(jù)項一般不予考慮。 4.4.數(shù)據(jù)對象數(shù)據(jù)對象 具有具

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

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

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

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

19、結構：數(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 1.3 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念batcateat起始地址起始地址例：（例

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

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

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

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

24、集合操作集合數(shù)據(jù)結構數(shù)據(jù)結構l存儲結構存儲結構l算法設計算法設計類類使用視圖使用視圖設計視圖設計視圖實現(xiàn)視圖實現(xiàn)視圖 成員變量成員變量 成員函數(shù)成員函數(shù)ADT的定義的定義 ADT的設計的設計 ADT的實現(xiàn)的實現(xiàn)1.3 1.3 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念定義格式：定義格式：ADT ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象： 數(shù)據(jù)關系：數(shù)據(jù)關系： 基本操作：基本操作： （相當于聲明若干函數(shù)（相當于聲明若干函數(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ù)對象，是數(shù)據(jù)對象， S S是是D D上的關系集，上的關系集， P P是對是對D D的基本操作集。的基本操作集。1.3 1.3 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念 如：如：ADT ListADT List 數(shù)據(jù)對象：數(shù)據(jù)對象：D=aD=ai i|a|ai iElemSet, i=1,2,3,ElemSet, i=1,2,3,n,n0,n,n0 數(shù)據(jù)關系：數(shù)據(jù)關系：R1=aR1=|a|ai-1i-1,a,ai iD,i=2,D,i=2,nn 基本操作：基本操作： InitList(&L)InitList(&L)要點：要點： 操作結果：構造一

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

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

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

29、結構數(shù)據(jù)的存儲結構 順序存儲順序存儲鏈式存儲鏈式存儲集合集合線性結構線性結構樹結構樹結構圖結構圖結構 非數(shù)值問題非數(shù)值問題 數(shù)數(shù)據(jù)據(jù)表表示示小結小結1.3 1.3 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念 n數(shù)據(jù)結構主要研究內容：數(shù)據(jù)結構主要研究內容： u數(shù)據(jù)的各種邏輯結構和存儲結構，以及它們數(shù)據(jù)的各種邏輯結構和存儲結構，以及它們之間的相應關系之間的相應關系u并對每種結構定義相應的各種運算并對每種結構定義相應的各種運算u設計出相應的算法設計出相應的算法u分析算法的效率分析算法的效率1.3 1.3 數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念1.4 1.4 算法和算法分析算法和算法分析一、算法一、算法二、算

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

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

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

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

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;程序設計語言例：歐幾里德算法例：歐幾里德算法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 算法和算法分析算法和算法分析三、算法分析三、算法分析設計算法時，通常應考慮達到以下目標：設計算法時，通常應考慮達到以下目標：1.1.正確性正確性2.2.可讀性可讀性3.3.健壯性健壯性4.4.高效率與低存儲量的需求高效率與低存儲量的需求1.4 1.4 算法和算法分析算法和算法分析例：八枚硬幣中有一枚重，現(xiàn)有一個天秤例：八枚硬幣中有一枚重，現(xiàn)有一個天秤 怎樣選出？怎樣選出？方法一：方法一：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 算法和算法分析算法和算法分析三、算法分析三、算法分析 算法分析算法分析：對算法所需要的計算機資源：對算法所需要的計算機資源時間時間和和空間空間進行估算。進行估算。 時間復雜性（時間復雜性（Time Complexity） 空間復雜性（空間復雜性（Space Complexity）三、算法分析三、算法分析1.4 1.4 算法和算法分析算法和算法分析 算法分析的目：算法分析的目：改進算法改進算法提高算法的時間效提高算法的時間效率和空間效率。率和空間效率。 度量算法效率的方法：度量

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

38、法的執(zhí)行次整個算法的執(zhí)行次數(shù)成數(shù)成 正比的操作指令。正比的操作指令。問題規(guī)模：問題規(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ù)量級（階）時，把時間復雜

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

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

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

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

43、要研究的三方面內容：數(shù)據(jù)結構主要研究的三方面內容： （1）數(shù)據(jù)的邏輯結構）數(shù)據(jù)的邏輯結構 （線性結構和非線結構）（線性結構和非線結構） （2）數(shù)據(jù)的存儲結構）數(shù)據(jù)的存儲結構 （順序方式、鏈式方式、（順序方式、鏈式方式、索引方式和散列方式索引方式和散列方式） （3）對數(shù)據(jù)實施的基本運算）對數(shù)據(jù)實施的基本運算: 算法算法算法分析：時間性能算法分析：時間性能時間復雜度時間復雜度 空間性能空間性能空間復雜度空間復雜度緒緒 論論數(shù)據(jù)結構數(shù)據(jù)結構算算 法法基基本本概概念念邏邏輯輯結結構構存存儲儲結結構構數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)元素數(shù)據(jù)對象數(shù)據(jù)對象ADT邏輯結構邏輯結構數(shù)據(jù)結構數(shù)據(jù)結構的分類的分類存儲結構存儲結構常用存儲常用存儲方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性評價算法評價算法描述算法描述算法問題規(guī)模問題規(guī)?；菊Z句基本語句時間復雜度時間復雜度大大O記號記號關關 系系習習 題題1.( )1.( )是數(shù)據(jù)的最小單位，（是數(shù)據(jù)的最小單位，（ ）是討論數(shù)）是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位（基本單位）。據(jù)結構時涉及的最小數(shù)據(jù)單位（基本單位）。2.2.順序存儲結構中數(shù)據(jù)元素之間的邏輯關系由（順序存儲結構中數(shù)據(jù)元素之間的邏輯關系由（ ) )表表示的，鏈式存儲結構中的數(shù)