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

主教材

王紅梅.數(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)于教材主教材

王紅梅.數(shù)據(jù)結(jié)構(gòu)（C＋＋版）.清華大學(xué)出版社

輔導(dǎo)及1課程性質(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)空”考研課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課2學(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í)目標(biāo)掌握基本的數(shù)據(jù)結(jié)構(gòu)3學(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é)合的特征。

學(xué)習(xí)要求循序漸進(jìn)，切忌心浮氣躁4如何使用立體化教材主教材思想火花、人物小傳輔導(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)站如何使用立體化教材主教材5成績(jī)組成實(shí)驗(yàn)成績(jī)

30％：出勤＋程序＋報(bào)告期末考試成績(jī)

70％：接近同類學(xué)?？佳兴秸n程設(shè)計(jì)成績(jī)：優(yōu)、良、中、及、不及成績(jī)組成實(shí)驗(yàn)成績(jī)6第1章緒論數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

數(shù)據(jù)結(jié)構(gòu)的基本概念算法及算法分析本章的基本內(nèi)容是：第1章緒論數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展本章的基本內(nèi)容是：71938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming他計(jì)劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年僅36歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努特1938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留81.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ì)

1.1數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展程序設(shè)計(jì)的實(shí)質(zhì)是什么?數(shù)據(jù)表9數(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ā)展

數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)1101.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.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象計(jì)算機(jī)求解問(wèn)題:11例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)學(xué)號(hào)姓名性別出生日期政治面貌0001王軍男1983/09/02團(tuán)員0002李明男1982/12/25黨員0003湯曉影女1984/03/26團(tuán)員……………1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象完成什么功能?各表項(xiàng)之間是什么關(guān)系？例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)學(xué)號(hào)姓名性別出生日期政治面貌12例2人機(jī)對(duì)弈問(wèn)題——樹結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？…………..……..………...……例2人機(jī)對(duì)弈問(wèn)題——樹結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象13例3教學(xué)計(jì)劃編排問(wèn)題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫(kù)原理C7C2,

C4計(jì)算機(jī)原理C6C3,C4數(shù)據(jù)結(jié)構(gòu)C5C1,C2程序設(shè)計(jì)C4C1離散數(shù)學(xué)C3無(wú)計(jì)算機(jī)導(dǎo)論C2無(wú)高等數(shù)學(xué)C1先修課課程名稱編號(hào)1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象C1C2C3C4C6C5C7如何表示課程之間的先修關(guān)系？例3教學(xué)計(jì)劃編排問(wèn)題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫(kù)14數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之151.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)的基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中并能被16數(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ù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系包含關(guān)系：數(shù)據(jù)是由數(shù)據(jù)元素組17數(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)的基本概念關(guān)聯(lián)方式或鄰接關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型學(xué)籍管理問(wèn)題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？人機(jī)對(duì)弈問(wèn)題中，格局之間的邏輯關(guān)系指的是什么？教學(xué)計(jì)劃編排問(wèn)題中，課程之間的邏輯關(guān)系指的是什么？數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不18數(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)的基本概念內(nèi)存存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語(yǔ)言。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不19數(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)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)20數(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)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)21數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”；⑵線性結(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)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)22數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”；⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系；⑶樹結(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)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)23通常有兩種存儲(chǔ)結(jié)構(gòu)：1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來(lái)表示?！璪atcateat…起始地址例：（bat,cat,eat）1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲(chǔ)結(jié)構(gòu)：…起始地址例：（bat,cat,ea24通常有兩種存儲(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)的基本概念0200020803000325…………bat0200cat0325eat∧通常有兩種存儲(chǔ)結(jié)構(gòu)：例：（bat,cat,eat）1.325邏輯結(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)的基本概念邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是26數(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ù)結(jié)構(gòu)的訪問(wèn)接口對(duì)數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)是指對(duì)數(shù)據(jù)的讀取、修改、加27抽象數(shù)據(jù)類型1.數(shù)據(jù)類型（DataType）：一組值的集合以及定義于這個(gè)值集上的一組操作的總稱。

例如：C++中的整型變量

2.抽象（Abstract）:抽出問(wèn)題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)。

例如：地圖、駕駛汽車3.抽象數(shù)據(jù)類型（AbstractDataType，ADT）:一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型1.數(shù)據(jù)類型（DataType）：一組值的集28ADT是對(duì)數(shù)據(jù)類型的進(jìn)一步抽象ADT·邏輯結(jié)構(gòu)·操作集合數(shù)據(jù)結(jié)構(gòu)·存儲(chǔ)結(jié)構(gòu)·算法設(shè)計(jì)類·成員變量·成員函數(shù)(a)使用視圖(b)設(shè)計(jì)視圖(c)實(shí)現(xiàn)視圖ADT的定義ADT的設(shè)計(jì)ADT的實(shí)現(xiàn)

ADT的不同視圖1.3數(shù)據(jù)結(jié)構(gòu)的基本概念A(yù)DT是對(duì)數(shù)據(jù)類型的進(jìn)一步抽象ADT數(shù)據(jù)結(jié)構(gòu)類(a)使用視29ADT抽象數(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)的基本概念A(yù)DT抽象數(shù)據(jù)類型名ADT的定義形式1.3數(shù)據(jù)結(jié)構(gòu)的基301.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)非數(shù)值問(wèn)題數(shù)據(jù)表示1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)的操作：插入、刪除、修31算法的相關(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算法及算法分析算法的相關(guān)概念1.算法（Algorithm）:是對(duì)特定問(wèn)題求32歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m

和n

的最大公約數(shù)1.4算法及算法分析mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m和n33算法的描述方法——自然語(yǔ)言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想

注意事項(xiàng)：避免寫成自然段1.4算法及算法分析算法的描述方法——自然語(yǔ)言優(yōu)點(diǎn)：容易理解1.4算法及算34①輸入m

和n；②求m除以n的余數(shù)r；③若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。例：歐幾里德算法自然語(yǔ)言1.4算法及算法分析①輸入m和n；例：歐幾里德算法自然語(yǔ)言1.4算法及算35優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次算法的描述方法——流程圖1.4算法及算法分析優(yōu)點(diǎn)：流程直觀算法的描述方法——流程圖1.4算法及算36N開始輸入m和n

r=m%nr=0m=n；n=r輸出n結(jié)束Y流程圖例：歐幾里德算法1.4算法及算法分析N開始輸入m和nr=m%nr=0m=n；n=r37優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)算法的描述方法——程序設(shè)計(jì)語(yǔ)言1.4算法及算法分析優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行算法的描述方法——程序設(shè)計(jì)語(yǔ)言1.438#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}程序設(shè)計(jì)語(yǔ)言例：歐幾里德算法1.4算法及算法分析#include<iostream.h>程序設(shè)計(jì)語(yǔ)言例：歐394算法及算法分析4算法及算法分析40偽代碼（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算法及算法分析偽代碼（Pseudocode）：介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之411.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;偽代碼上述偽代碼再具體一些，用C++的函數(shù)來(lái)描述。請(qǐng)同學(xué)們自行完成！例：歐幾里德算法1.4算法及算法分析1.r=m%n;偽代碼上述偽代碼再具體42算法分析度量算法效率的方法：

事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開銷。

缺點(diǎn)：⑴編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；⑵所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素。

事前分析：對(duì)算法所消耗資源的一種估算方法。1.4算法及算法分析算法分析度量算法效率的方法：1.4算法及算法分析43算法分析算法分析（AlgorithmAnalysis）：對(duì)算法所需要的計(jì)算機(jī)資源——時(shí)間和空間進(jìn)行估算。時(shí)間復(fù)雜性（TimeComplexity）空間復(fù)雜性（SpaceComplexity）1.4算法及算法分析算法分析算法分析（AlgorithmAnalysis）：對(duì)44算法的時(shí)間復(fù)雜度分析1.4算法及算法分析算法分析算法的執(zhí)行時(shí)間＝每條語(yǔ)句執(zhí)行時(shí)間之和執(zhí)行次數(shù)×執(zhí)行一次的時(shí)間指令系統(tǒng)、編譯的代碼質(zhì)量單位時(shí)間每條語(yǔ)句執(zhí)行次數(shù)之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語(yǔ)句的執(zhí)行次數(shù)算法的時(shí)間復(fù)雜度分析1.4算法及算法分析算法分析算法的執(zhí)45問(wèn)題規(guī)模：輸入量的多少?；菊Z(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算法及算法分析算法分析問(wèn)題規(guī)模：輸入量的多少。for(i=1;i<=n;i+46定義

若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))n0問(wèn)題規(guī)模n執(zhí)行次數(shù)n0之前的情況無(wú)關(guān)緊要T(n)c×f(n)當(dāng)問(wèn)題規(guī)模充分大時(shí)在漸近意義下的階1.4算法及算法分析算法分析——大O符號(hào)定義若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T47定理：若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)定理：若A(n)=amnm+am-1nm-1++a1n+a48例1-5

++x;例1-6

for(i=1;i<=n;++i)++x;例1-7for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;

例1-8for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;1.4算法及算法分析算法分析例1-5++x;1.4算法及算法分析算法分析49例1-9for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}例1-10for(i=1;i<=n;i=2*i) ++x;Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)1.4算法及算法分析算法分析例1-9for(i=1;i<=n;++i)Ο(150最好情況、最壞情況、平均情況例：在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為k）。

intFind(intA[],intn)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }1.4算法及算法分析基本語(yǔ)句的執(zhí)行次數(shù)是否只和問(wèn)題規(guī)模有關(guān)？最好情況、最壞情況、平均情況例：在一維整型數(shù)組A[n]中順序51最好情況：出現(xiàn)概率較大時(shí)分析最差情況：實(shí)時(shí)系統(tǒng)平均情況：已知輸入數(shù)據(jù)是如何分布的，通常假設(shè)等概率分布結(jié)論：如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。1.4算法及算法分析最好情況、最壞情況、平均情況最好情況：出現(xiàn)概率較大時(shí)分析結(jié)論：如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)52本章小結(jié)——知識(shí)結(jié)構(gòu)圖緒論數(shù)據(jù)結(jié)構(gòu)算法基本概念邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)⑴數(shù)據(jù)⑵數(shù)據(jù)元素⑶數(shù)據(jù)對(duì)象⑷ADT⑴邏輯結(jié)構(gòu)⑵數(shù)據(jù)結(jié)構(gòu)的分類⑴存儲(chǔ)結(jié)構(gòu)⑵常用存儲(chǔ)方法基本概念算法分析⑴算法⑵算法特性⑶評(píng)價(jià)算法⑷描述算法⑴問(wèn)題規(guī)模⑵基本語(yǔ)句⑶時(shí)間復(fù)雜度⑷大O記號(hào)關(guān)系本章小結(jié)——知識(shí)結(jié)構(gòu)圖緒論數(shù)據(jù)結(jié)構(gòu)算法基本概念邏輯結(jié)53作業(yè)：公元5世紀(jì)末，我國(guó)古代數(shù)學(xué)家張丘建在它所撰定的《算經(jīng)》中，提出這樣一個(gè)問(wèn)題：“雞翁一，值錢五；雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問(wèn)雞翁、母、雛各幾何？”意思是說(shuō)公雞每只5元，母雞每只3元，小雞3只1元，用100元錢買100只雞，求公雞、母雞、小雞的只數(shù)。試設(shè)計(jì)算法求解該問(wèn)題，并分析你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度。（要求：算法分別用偽代碼和C＋＋描述）作業(yè)：公元5世紀(jì)末，我國(guó)古代數(shù)學(xué)家張丘建在它所撰定的《算經(jīng)》54主教材

王紅梅.數(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)于教材主教材

王紅梅.數(shù)據(jù)結(jié)構(gòu)（C＋＋版）.清華大學(xué)出版社

輔導(dǎo)及55課程性質(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)空”考研課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課56學(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í)目標(biāo)掌握基本的數(shù)據(jù)結(jié)構(gòu)57學(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é)合的特征。

學(xué)習(xí)要求循序漸進(jìn)，切忌心浮氣躁58如何使用立體化教材主教材思想火花、人物小傳輔導(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)站如何使用立體化教材主教材59成績(jī)組成實(shí)驗(yàn)成績(jī)

30％：出勤＋程序＋報(bào)告期末考試成績(jī)

70％：接近同類學(xué)?？佳兴秸n程設(shè)計(jì)成績(jī)：優(yōu)、良、中、及、不及成績(jī)組成實(shí)驗(yàn)成績(jī)60第1章緒論數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

數(shù)據(jù)結(jié)構(gòu)的基本概念算法及算法分析本章的基本內(nèi)容是：第1章緒論數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展本章的基本內(nèi)容是：611938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming他計(jì)劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年僅36歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努特1938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留621.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ì)

1.1數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展程序設(shè)計(jì)的實(shí)質(zhì)是什么?數(shù)據(jù)表63數(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ā)展

數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)1641.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.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象計(jì)算機(jī)求解問(wèn)題:65例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)學(xué)號(hào)姓名性別出生日期政治面貌0001王軍男1983/09/02團(tuán)員0002李明男1982/12/25黨員0003湯曉影女1984/03/26團(tuán)員……………1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象完成什么功能?各表項(xiàng)之間是什么關(guān)系？例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)學(xué)號(hào)姓名性別出生日期政治面貌66例2人機(jī)對(duì)弈問(wèn)題——樹結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？…………..……..………...……例2人機(jī)對(duì)弈問(wèn)題——樹結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象67例3教學(xué)計(jì)劃編排問(wèn)題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫(kù)原理C7C2,

C4計(jì)算機(jī)原理C6C3,C4數(shù)據(jù)結(jié)構(gòu)C5C1,C2程序設(shè)計(jì)C4C1離散數(shù)學(xué)C3無(wú)計(jì)算機(jī)導(dǎo)論C2無(wú)高等數(shù)學(xué)C1先修課課程名稱編號(hào)1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象C1C2C3C4C6C5C7如何表示課程之間的先修關(guān)系？例3教學(xué)計(jì)劃編排問(wèn)題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫(kù)68數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之691.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)的基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中并能被70數(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ù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系包含關(guān)系：數(shù)據(jù)是由數(shù)據(jù)元素組71數(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)的基本概念關(guān)聯(lián)方式或鄰接關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型學(xué)籍管理問(wèn)題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？人機(jī)對(duì)弈問(wèn)題中，格局之間的邏輯關(guān)系指的是什么？教學(xué)計(jì)劃編排問(wèn)題中，課程之間的邏輯關(guān)系指的是什么？數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不72數(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)的基本概念內(nèi)存存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語(yǔ)言。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不73數(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)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)74數(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)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)75數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”；⑵線性結(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)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)76數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”；⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系；⑶樹結(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)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)77通常有兩種存儲(chǔ)結(jié)構(gòu)：1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來(lái)表示?！璪atcateat…起始地址例：（bat,cat,eat）1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲(chǔ)結(jié)構(gòu)：…起始地址例：（bat,cat,ea78通常有兩種存儲(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)的基本概念0200020803000325…………bat0200cat0325eat∧通常有兩種存儲(chǔ)結(jié)構(gòu)：例：（bat,cat,eat）1.379邏輯結(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)的基本概念邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是80數(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ù)結(jié)構(gòu)的訪問(wèn)接口對(duì)數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)是指對(duì)數(shù)據(jù)的讀取、修改、加81抽象數(shù)據(jù)類型1.數(shù)據(jù)類型（DataType）：一組值的集合以及定義于這個(gè)值集上的一組操作的總稱。

例如：C++中的整型變量

2.抽象（Abstract）:抽出問(wèn)題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)。

例如：地圖、駕駛汽車3.抽象數(shù)據(jù)類型（AbstractDataType，ADT）:一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型1.數(shù)據(jù)類型（DataType）：一組值的集82ADT是對(duì)數(shù)據(jù)類型的進(jìn)一步抽象ADT·邏輯結(jié)構(gòu)·操作集合數(shù)據(jù)結(jié)構(gòu)·存儲(chǔ)結(jié)構(gòu)·算法設(shè)計(jì)類·成員變量·成員函數(shù)(a)使用視圖(b)設(shè)計(jì)視圖(c)實(shí)現(xiàn)視圖ADT的定義ADT的設(shè)計(jì)ADT的實(shí)現(xiàn)

ADT的不同視圖1.3數(shù)據(jù)結(jié)構(gòu)的基本概念A(yù)DT是對(duì)數(shù)據(jù)類型的進(jìn)一步抽象ADT數(shù)據(jù)結(jié)構(gòu)類(a)使用視83ADT抽象數(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)的基本概念A(yù)DT抽象數(shù)據(jù)類型名ADT的定義形式1.3數(shù)據(jù)結(jié)構(gòu)的基841.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)集合線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)非數(shù)值問(wèn)題數(shù)據(jù)表示1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)的操作：插入、刪除、修85算法的相關(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算法及算法分析算法的相關(guān)概念1.算法（Algorithm）:是對(duì)特定問(wèn)題求86歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m

和n

的最大公約數(shù)1.4算法及算法分析mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m和n87算法的描述方法——自然語(yǔ)言優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想

注意事項(xiàng)：避免寫成自然段1.4算法及算法分析算法的描述方法——自然語(yǔ)言優(yōu)點(diǎn)：容易理解1.4算法及算88①輸入m

和n；②求m除以n的余數(shù)r；③若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第④步；④將n的值放在m中，將r的值放在n中；⑤重新執(zhí)行第②步。例：歐幾里德算法自然語(yǔ)言1.4算法及算法分析①輸入m和n；例：歐幾里德算法自然語(yǔ)言1.4算法及算89優(yōu)點(diǎn)：流程直觀缺點(diǎn)：缺少嚴(yán)密性、靈活性使用方法：描述簡(jiǎn)單算法注意事項(xiàng)：注意抽象層次算法的描述方法——流程圖1.4算法及算法分析優(yōu)點(diǎn)：流程直觀算法的描述方法——流程圖1.4算法及算90N開始輸入m和n

r=m%nr=0m=n；n=r輸出n結(jié)束Y流程圖例：歐幾里德算法1.4算法及算法分析N開始輸入m和nr=m%nr=0m=n；n=r91優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫成子函數(shù)算法的描述方法——程序設(shè)計(jì)語(yǔ)言1.4算法及算法分析優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行算法的描述方法——程序設(shè)計(jì)語(yǔ)言1.492#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}程序設(shè)計(jì)語(yǔ)言例：歐幾里德算法1.4算法及算法分析#include<iostream.h>程序設(shè)計(jì)語(yǔ)言例：歐934算法及算法分析4算法及算法分析94偽代碼（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算法及算法分析偽代碼（Pseudocode）：介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之951.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;偽代碼上述偽代碼再具體一些，用C++的函數(shù)來(lái)描述。請(qǐng)同學(xué)們自行完成！例：歐幾里德算法1.4算法及算法分析1.r=m%n;偽代碼上述偽代碼再具體96算法分析度量算法效率的方法：

事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開銷。

缺點(diǎn)：⑴編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；⑵所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素。

事前分析：對(duì)算法所消耗資源的一種估算方法。1.4算法及算法分析算法分析度量算法效率的方法：1.4算法及算法分析97算法分析算法分析（AlgorithmAnalysis）：對(duì)算法所需要的計(jì)算機(jī)資源——時(shí)間和空間進(jìn)行估算。時(shí)間復(fù)雜性（TimeComplexity）空間復(fù)雜性（SpaceComplexity）1.4算法及算法分析算法分析算法分析（AlgorithmAnalysis）：對(duì)98算法的時(shí)間復(fù)雜度分析1.4算法及算法分析算法分析算法的執(zhí)行時(shí)間＝每條語(yǔ)句執(zhí)行時(shí)間之和執(zhí)行次數(shù)×執(zhí)行一次的時(shí)間指令系統(tǒng)、編譯的代碼質(zhì)量單位時(shí)間每條語(yǔ)句執(zhí)行次數(shù)之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語(yǔ)句的執(zhí)行次數(shù)算法的時(shí)間復(fù)雜度分析1.4算法及算法分析算法分析算法的執(zhí)99問(wèn)題規(guī)模：輸入量的多少?；菊Z(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算法及算法分析算法分析問(wèn)題規(guī)模：輸入量的多少。for(i=1;i<=n;i+100定義

若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)