數(shù)據(jù)結(jié)構(gòu)緒論

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)c+語言描述 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社教學(xué)基本要求教學(xué)基本要求 平時(shí)提問，課堂練習(xí)。 書面作業(yè)，每周交一次。分紙質(zhì)與電子兩種。 完成2個(gè)左右實(shí)驗(yàn)和報(bào)告，實(shí)驗(yàn)課上機(jī)測試。 平時(shí)成績10%，實(shí)驗(yàn)成績20%，期中考試10%，期終考試60%。 考勤：遲到、曠課扣平時(shí)分。 禁止在實(shí)驗(yàn)課上做與教學(xué)無關(guān)的事。 上課應(yīng)關(guān)閉手機(jī)或置于禁音狀態(tài)，違者 嚴(yán)禁課上吃食物(可以喝水)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人 程序=算法+數(shù)據(jù)結(jié)構(gòu)算法和程序設(shè)計(jì)技術(shù)的

2、先驅(qū)者，計(jì)算機(jī)排版系統(tǒng)tex和metafont的發(fā)明者，他因這些成就和大量創(chuàng)造性的影響深遠(yuǎn)的著作(19部書和160篇論文)而譽(yù)滿全球。作為斯坦福大學(xué)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)的榮譽(yù)退休教授，他當(dāng)前正全神貫注于完成其關(guān)于計(jì)算機(jī)科學(xué)的史詩性的七卷集。這一偉大工程在1962年他還是加利福尼亞理工學(xué)院的研究生時(shí)就開始了。 knuth教授獲得了許多獎(jiǎng)項(xiàng)和榮譽(yù)，包括美國計(jì)算機(jī)協(xié)會(huì)圖靈獎(jiǎng)(acm turing award)，美國前總統(tǒng)卡特授予的科學(xué)金獎(jiǎng)(medal of science)，美國數(shù)學(xué)學(xué)會(huì)斯蒂爾獎(jiǎng)(ams steele prize)，以及1996年11月由于發(fā)明先進(jìn)技術(shù)榮獲的極受尊重的京都獎(jiǎng)(kyoto

3、prize)?，F(xiàn)與其妻jill生活于斯坦福校園內(nèi)。d.e.knuth(唐納德.e.克努特)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)的重要性數(shù)據(jù)結(jié)構(gòu)的重要性 計(jì)算機(jī)程序設(shè)計(jì)語言不等于程序，是實(shí)現(xiàn)程序的工具。 通過算法訓(xùn)練培養(yǎng)計(jì)算思維的能力，通過程序設(shè)計(jì)的技能訓(xùn)練來促進(jìn)綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。 本課程是研究生入學(xué)考試必考內(nèi)容，也是高級(jí)程序員證書、軟件公司用人必考內(nèi)容。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社第第 1 章章 緒緒 論論數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)的研究對象 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念算法

4、及算法分析算法及算法分析本章的基本內(nèi)容是：本章的基本內(nèi)容是：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社1.1 數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展 程序設(shè)計(jì)的實(shí)質(zhì)是什么程序設(shè)計(jì)的實(shí)質(zhì)是什么?數(shù)據(jù)表示：數(shù)據(jù)表示：將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中數(shù)據(jù)處理：數(shù)據(jù)處理：處理數(shù)據(jù)，求解問題處理數(shù)據(jù)，求解問題數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社 數(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é)

5、構(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ā)展 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社1.2 數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)的研究對象 計(jì)算機(jī)求解問題計(jì)算機(jī)求解問題: 問題問題抽象出問題的模型抽象出問題的模型求模型的解求模型的解 問題問題數(shù)值問題、非數(shù)值問題數(shù)值問題、非數(shù)值問題 數(shù)數(shù) 值值 問問 題題數(shù)學(xué)方程數(shù)學(xué)方程 非數(shù)值問題非數(shù)值問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社例例1 學(xué)籍管理問題學(xué)籍管理問題表結(jié)構(gòu)表結(jié)構(gòu)學(xué)號(hào)學(xué)號(hào)姓

6、名姓名性別性別出生日期出生日期政治面貌政治面貌0001王王 軍軍男男1983/09/02團(tuán)員團(tuán)員0002李李 明明男男1982/12/25黨員黨員0003湯曉影湯曉影女女1984/03/26團(tuán)員團(tuán)員1.2 數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)的研究對象完成什么功能完成什么功能?各表項(xiàng)之間是什么關(guān)系？各表項(xiàng)之間是什么關(guān)系？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社例例2 人機(jī)對弈問題人機(jī)對弈問題樹結(jié)構(gòu)樹結(jié)構(gòu)1.2 數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)的研究對象如何實(shí)現(xiàn)對弈如何實(shí)現(xiàn)對弈?各格局之間是什么關(guān)系？各格局之間是什么關(guān)系？.數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社例例3 教學(xué)

7、計(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)1.2 數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)的研究對象c1c2c3c4c6c5c7如何表示課程之間的先修關(guān)系？如何表示課程之間的先修關(guān)系？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值非數(shù)值問題中計(jì)問題中計(jì)算機(jī)的算機(jī)的操作對象操作對象以及它們之間的以及它們之間的關(guān)系

8、關(guān)系和和操作操作的學(xué)科。的學(xué)科。1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)的研究對象數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)：所有能：所有能輸入輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別識(shí)別和處理和處理的符號(hào)集合。的符號(hào)集合。 數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等 非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等 數(shù)據(jù)元素?cái)?shù)據(jù)元素：數(shù)據(jù)的：數(shù)據(jù)的基本基本單位，在計(jì)算機(jī)程序中通常作單位，在計(jì)算機(jī)程序中通常作為一個(gè)為一個(gè)整體整體進(jìn)行考慮和處理。進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)：構(gòu)成數(shù)

9、據(jù)元素的不可分割的最小單位。：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)對象數(shù)據(jù)對象：具有相同：具有相同性質(zhì)性質(zhì)的數(shù)據(jù)元素的集合。的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系包含關(guān)系：數(shù)據(jù)是由數(shù)據(jù)元素組成，數(shù)據(jù)包含關(guān)系：數(shù)據(jù)是由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項(xiàng)組成。元素是由數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素?cái)?shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念

10、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定：相互之間存在一定關(guān)系關(guān)系的數(shù)據(jù)元素的集合。的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系邏輯關(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ù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型數(shù)據(jù)模型學(xué)籍管理問題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？學(xué)籍管理問題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？人機(jī)對弈問

11、題中，格局之間的邏輯關(guān)系指的是什么？人機(jī)對弈問題中，格局之間的邏輯關(guān)系指的是什么？教學(xué)計(jì)劃編排問題中，課程之間的邏輯關(guān)系指的是什么？教學(xué)計(jì)劃編排問題中，課程之間的邏輯關(guān)系指的是什么？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定：相互之間存在一定關(guān)系關(guān)系的數(shù)據(jù)元素的集合。的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(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é)

12、構(gòu)在計(jì)算機(jī)計(jì)算機(jī)中的表示。中的表示。1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念存儲(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ī)語言。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是集合：數(shù)據(jù)元素之間就是 “屬于同一個(gè)集合屬于同一個(gè)集合” ；1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：數(shù)據(jù)結(jié)構(gòu)從

13、邏輯上分為四類： 集合：數(shù)據(jù)元素之間就是集合：數(shù)據(jù)元素之間就是 “屬于同一個(gè)集合屬于同一個(gè)集合” ； 線性結(jié)構(gòu)：數(shù)據(jù)元素之間線性結(jié)構(gòu)：數(shù)據(jù)元素之間 存在著一對一的線性關(guān)系；存在著一對一的線性關(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ù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(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ù)元素之間 存在著一對一的線性關(guān)系；存在著一對一的線性關(guān)系； 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在樹結(jié)構(gòu)：

14、數(shù)據(jù)元素之間存在 著一對多的層次關(guān)系；著一對多的層次關(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ù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(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ù)元素之間 存在著一對一的線性關(guān)系；存在著一對一的線性關(guān)系； 樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在 著一對多的層次關(guān)系；著一對多的層次關(guān)系； 圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在 著多對多的任意關(guān)系。著多對多

15、的任意關(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ù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社通常有兩種存儲(chǔ)結(jié)構(gòu)：通常有兩種存儲(chǔ)結(jié)構(gòu)：1. 順序存儲(chǔ)結(jié)構(gòu)：用一組順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)數(shù)據(jù)元素，存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元數(shù)據(jù)元素之間的邏輯關(guān)系由元素的素的存儲(chǔ)位置存儲(chǔ)位置來表示。來表示。batcateat起始地址起始地址例：（例：（bat, cat, eat）1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出

16、版社通常有兩種存儲(chǔ)結(jié)構(gòu)：通常有兩種存儲(chǔ)結(jié)構(gòu)：1. 順序存儲(chǔ)結(jié)構(gòu)：用一組順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)連續(xù)的存儲(chǔ)單元的存儲(chǔ)單元依次依次存儲(chǔ)數(shù)據(jù)元素，存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元數(shù)據(jù)元素之間的邏輯關(guān)系由元素的素的存儲(chǔ)位置存儲(chǔ)位置來表示。來表示。2. 鏈接存儲(chǔ)結(jié)構(gòu)：用一組鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用據(jù)元素之間的邏輯關(guān)系用指針指針來表示來表示 。例：（例：（bat, cat, eat）1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念0200020803000325 bat0200 cat03

17、25 eat 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社邏輯結(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)的視圖，是面向計(jì)算機(jī)面向計(jì)算機(jī)的。的。 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。率往往是不同的。 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基

18、本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)的訪問接口數(shù)據(jù)結(jié)構(gòu)的訪問接口 對數(shù)據(jù)結(jié)構(gòu)的對數(shù)據(jù)結(jié)構(gòu)的訪問訪問是指對數(shù)據(jù)的讀取、修改、是指對數(shù)據(jù)的讀取、修改、加工、處理等操作。加工、處理等操作。 數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的基本操作基本操作：各種應(yīng)用都能通過這些：各種應(yīng)用都能通過這些操作實(shí)現(xiàn)對數(shù)據(jù)結(jié)構(gòu)的各種訪問。操作實(shí)現(xiàn)對數(shù)據(jù)結(jié)構(gòu)的各種訪問。 基本操作的特性：抽象性、基本性、完備性、一般性基本操作的特性：抽象性、基本性、完備性、一般性 訪問接口訪問接口：操作的調(diào)用形式與規(guī)范（例如形參：操作的調(diào)用形式與規(guī)范（例如形參表、返回類型等）。表、返回類型等）。 數(shù)據(jù)結(jié)構(gòu)的訪問接口數(shù)據(jù)結(jié)構(gòu)

19、的訪問接口：數(shù)據(jù)結(jié)構(gòu)基本操作接口：數(shù)據(jù)結(jié)構(gòu)基本操作接口的全體。的全體。 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型1. 數(shù)據(jù)類型數(shù)據(jù)類型（data type）：一組）：一組值值的集合以及定義的集合以及定義于這個(gè)值集上的一組于這個(gè)值集上的一組操作操作的總稱。的總稱。 例如：例如：c+中的整型變量中的整型變量 2. 抽象抽象（abstract）:抽出問題本質(zhì)的特征而忽略非抽出問題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)。本質(zhì)的細(xì)節(jié)。 例如：例如： 地圖、駕駛汽車地圖、駕駛汽車3. 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（abstract d

20、ata type，adt）:一個(gè)一個(gè)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的以及定義在該結(jié)構(gòu)上的一組操作一組操作的總稱。的總稱。 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社adt是對數(shù)據(jù)類型的進(jìn)一步抽象是對數(shù)據(jù)類型的進(jìn)一步抽象 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)算法設(shè)計(jì)算法設(shè)計(jì)類類成員變量成員變量成員函數(shù)成員函數(shù)(a)使用視圖使用視圖 (b) 設(shè)計(jì)視圖設(shè)計(jì)視圖 (c) 實(shí)現(xiàn)視圖實(shí)現(xiàn)視圖adt的定義的定義 adt的設(shè)計(jì)的設(shè)計(jì) adt的實(shí)現(xiàn)的實(shí)現(xiàn) adt的不同視圖的不同視圖1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)

21、的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社adt 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名data 數(shù)據(jù)元素之間邏輯關(guān)系的定義數(shù)據(jù)元素之間邏輯關(guān)系的定義operation 操作操作1 前置條件前置條件：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài)：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài) 輸輸 入入：執(zhí)行此操作所需要的輸入：執(zhí)行此操作所需要的輸入 功功 能能：該操作將完成的功能：該操作將完成的功能 輸輸 出出：執(zhí)行該操作后產(chǎn)生的輸出：執(zhí)行該操作后產(chǎn)生的輸出 后置條件后置條件：執(zhí)行該操作后數(shù)據(jù)的狀態(tài)：執(zhí)行該操作后數(shù)據(jù)的狀態(tài) 操作操作2 操作操作n endadt adt的定義形式的定義形式1.3 數(shù)據(jù)結(jié)構(gòu)的基本

22、概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(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ù)表表示示數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社1.算法算法（algorithm）:是對是對特定問題特定問題求解步驟的求解步驟的一種描述，是一種描述，是指令指令的的有限序列有限

23、序列。2. 算法的五大特性：算法的五大特性： 輸入輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。：一個(gè)算法有零個(gè)或多個(gè)輸入。 輸出輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。：一個(gè)算法有一個(gè)或多個(gè)輸出。 有窮性有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。每一步都在有窮時(shí)間內(nèi)完成。 確定性確定性：算法中的每一條指令必須有確切的含義，對于：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出。相同的輸入只能得到相同的輸出。 可行性可行性：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作：算法描述的操作可以通過已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來實(shí)現(xiàn)。

24、執(zhí)行有限次來實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社 歐幾里德算法mnr例：歐幾里德算法例：歐幾里德算法輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)求兩個(gè)自然數(shù) m 和和 n 的最大公約數(shù)的最大公約數(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社算法的描述方法算法的描述方法自然語言自然語言 優(yōu)點(diǎn)：容易理解優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長、二義性缺點(diǎn)：冗長、二義性使用方法：粗線條描述算法思想使用方法：粗線條描述算法思想 注意事項(xiàng)：避免寫成自然段注意事項(xiàng)：避免寫成自然段數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社 輸入輸入m 和和n； 求求m除以除以n的余數(shù)的余數(shù)r；

25、 若若r等于等于0 0，則，則n為最大公約數(shù)，為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第算法結(jié)束；否則執(zhí)行第步；步； 將將n的值放在的值放在m中，將中，將r的值放的值放在在n中；中； 重新執(zhí)行第重新執(zhí)行第步。步。例：歐幾里德算法例：歐幾里德算法自然語言數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社優(yōu)點(diǎn)：流程直觀優(yōu)點(diǎn)：流程直觀 缺點(diǎn)：缺少嚴(yán)密性、靈活性缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡單算法使用方法：描述簡單算法注意事項(xiàng)：注意抽象層次注意事項(xiàng)：注意抽象層次算法的描述方法算法的描述方法流程圖流程圖 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社n開始輸入m和n r=m % n

26、r=0m=n；n=r 輸出n結(jié)束y流 程 圖例：歐幾里德算法例：歐幾里德算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行 缺點(diǎn)：抽象性差，對語言要求高缺點(diǎn)：抽象性差，對語言要求高使用方法：算法需要驗(yàn)證使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)注意事項(xiàng)：將算法寫成子函數(shù)算法的描述方法算法的描述方法程序設(shè)計(jì)語言程序設(shè)計(jì)語言 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社#include int commonfactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m

27、% n; return n;void main( ) coutcommonfactor(63, 54)endl;程序設(shè)計(jì)語言例：歐幾里德算法例：歐幾里德算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社偽代碼偽代碼（pseudocode）：介于自然語言和）：介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。然語言來設(shè)計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解使用方

28、法：使用方法：7 2算法的描述方法算法的描述方法偽代碼偽代碼 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社 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. 輸出輸出 n ;偽 代 碼上述偽代碼再具體一些，用上述偽代碼再具體一些，用c+的函數(shù)來的函數(shù)來描述。請同學(xué)們自行完成！描述。請同學(xué)們自行完成！例：歐幾里德算法例：歐幾里德算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社度量算法效率的方法：度量算法效率的方法： 事后統(tǒng)計(jì)事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測算其時(shí)間和空間開銷。：將

29、算法實(shí)現(xiàn)，測算其時(shí)間和空間開銷。 缺點(diǎn)：缺點(diǎn)： 編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力； 所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素。所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素。 事前分析事前分析：對算法所消耗資源的一種估算方法。：對算法所消耗資源的一種估算方法。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社算法分析算法分析（algorithm analysis）：對算法所需要的）：對算法所需要的計(jì)算機(jī)資源計(jì)算機(jī)資源時(shí)間時(shí)間和和空間空間進(jìn)行估算。進(jìn)行估算。 時(shí)間復(fù)雜性（時(shí)間復(fù)雜性（time complexity） 空間復(fù)雜性（空間復(fù)雜性（sp

30、ace complexity）數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社算法的時(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ù)之和之和for (i=1; i=n; i+) for (j=1; j=n; j+) x+;基本語句基本語句的執(zhí)行次數(shù)的執(zhí)行次數(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社問題規(guī)模：問題規(guī)模：輸入量的多少。輸入量的多少?；菊Z句：基本語句：是執(zhí)行次數(shù)與

31、整個(gè)算法的執(zhí)行次是執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成數(shù)成正比的操作指令。正比的操作指令。for (i=1; i=n; i+) for (j=1; j=n; j+) x+;問題規(guī)模：n基本語句：x+數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社定義定義 若存在兩個(gè)正的常數(shù)若存在兩個(gè)正的常數(shù)c和和n0，對于任意，對于任意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( (n) )v當(dāng)問題規(guī)模充分大時(shí)在漸近意義下的階當(dāng)問題規(guī)模充分大時(shí)在漸近意義下

32、的階大大o符號(hào)符號(hào)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社定理：若定理：若a(n)=amnm+am-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ù)。大大o符號(hào)符號(hào)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社例例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;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）版）清華大學(xué)出版社清華大學(xué)出版社例例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!) 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（c版）