數(shù)據(jù)結(jié)構(gòu)-林業(yè)信息學(xué)院第1章緒論

北京林業(yè)大學(xué)信息學(xué)院

13:45

李冬梅

數(shù)據(jù)結(jié)構(gòu)北京林業(yè)大學(xué)信息學(xué)院

13:45

編程基礎(chǔ)計(jì)算機(jī)及相關(guān)專業(yè)考研考博課程計(jì)算機(jī)等級(jí)考試課程程序員考試課程為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)北京林業(yè)大學(xué)信息學(xué)院

13:45

課程學(xué)習(xí)指導(dǎo)1.提前預(yù)習(xí)、認(rèn)真聽課、按時(shí)完成書面及上機(jī)作業(yè)2.注意先修課程的知識(shí)準(zhǔn)備離散數(shù)學(xué)、C語言3.注意循序漸進(jìn)：基本概念、基本思想、基本步驟、算法設(shè)計(jì)4.注意培養(yǎng)算法設(shè)計(jì)的能力理解所講算法、對(duì)此多做思考：若問題要求不同，應(yīng)如何選擇數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)有效的算法課程特點(diǎn)：內(nèi)容抽象、概念性強(qiáng)、內(nèi)容靈活、不易掌握北京林業(yè)大學(xué)信息學(xué)院

13:45

平時(shí)成績(jī):30%作業(yè)、小測(cè)驗(yàn)、實(shí)驗(yàn)課堂紀(jì)律無故遲到：無故曠課：－５上機(jī)：玩游戲、上網(wǎng)聊天期末成績(jī):70%(閉卷筆試)考核方式北京林業(yè)大學(xué)信息學(xué)院

13:45

教材和參考書教材：《數(shù)據(jù)結(jié)構(gòu)》978-7-115-23490

嚴(yán)蔚敏，李冬梅，人民郵電出版社出版

參考書：《數(shù)據(jù)結(jié)構(gòu)C語言版》，嚴(yán)蔚敏，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++描述》，殷人昆等，清華大學(xué)出版社

13:45

第1章緒論1.了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容2.掌握數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念3.掌握算法、算法的時(shí)間復(fù)雜度及其分析的簡(jiǎn)易方法

教學(xué)目標(biāo)北京林業(yè)大學(xué)信息學(xué)院

13:45

1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法與算法分析教學(xué)內(nèi)容北京林業(yè)大學(xué)信息學(xué)院

13:45

N.沃思（NiklausWirth)教授提出：

程序=算法+數(shù)據(jù)結(jié)構(gòu)電子計(jì)算機(jī)的主要用途：早期：主要用于數(shù)值計(jì)算。后來：

處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域，能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容北京林業(yè)大學(xué)信息學(xué)院

13:45

書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表北京林業(yè)大學(xué)信息學(xué)院

13:45

人機(jī)對(duì)奕問題樹……..……..…...…...…...…...北京林業(yè)大學(xué)信息學(xué)院

13:45

/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖樹北京林業(yè)大學(xué)信息學(xué)院

13:45

多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖頂點(diǎn)：一條通路連線：不能同時(shí)通行染色：有連線的兩個(gè)頂點(diǎn)不能具有相同顏色北京林業(yè)大學(xué)信息學(xué)院

13:45

求解非數(shù)值計(jì)算的問題：設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法即：首先要考慮對(duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容為：研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。北京林業(yè)大學(xué)信息學(xué)院

13:45

數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展：形成階段：60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國(guó)一些大學(xué)計(jì)算機(jī)科學(xué)系的教學(xué)計(jì)劃。發(fā)展階段：數(shù)據(jù)結(jié)構(gòu)的概念不斷擴(kuò)充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。70年代后期，我國(guó)高校陸續(xù)開設(shè)該課程。北京林業(yè)大學(xué)信息學(xué)院

13:45

《數(shù)據(jù)結(jié)構(gòu)》所處的地位：介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程北京林業(yè)大學(xué)信息學(xué)院

13:45

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)學(xué)科中的地位

北京林業(yè)大學(xué)信息學(xué)院

13:45

課程目的能夠分析研究計(jì)算機(jī)加工的對(duì)象的特性，獲得其邏輯結(jié)構(gòu)，根據(jù)需求，選擇合適存貯結(jié)構(gòu)及其相應(yīng)的算法；學(xué)習(xí)一些常用的算法；復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，要求編寫的程序結(jié)構(gòu)清楚和正確易讀；初步掌握算法的時(shí)間分析和空間分析技術(shù)北京林業(yè)大學(xué)信息學(xué)院

13:45

1、數(shù)據(jù)（data)—所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)（多媒體信息處理）2、數(shù)據(jù)元素（dataelement）—數(shù)據(jù)的基本單位，也稱結(jié)點(diǎn)（node）或記錄（record）3、數(shù)據(jù)項(xiàng)（dataitem）—有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：學(xué)生表>個(gè)人記錄>學(xué)號(hào)、姓名……1.2基本概念和術(shù)語北京林業(yè)大學(xué)信息學(xué)院

13:45

整數(shù)數(shù)據(jù)對(duì)象

N={0,1,2,…}學(xué)生數(shù)據(jù)對(duì)象學(xué)生記錄的集合4、數(shù)據(jù)對(duì)象(DataObject)：相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集北京林業(yè)大學(xué)信息學(xué)院

13:45

5、數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。北京林業(yè)大學(xué)信息學(xué)院

13:45

數(shù)據(jù)結(jié)構(gòu)的兩個(gè)層次：邏輯結(jié)構(gòu)---數(shù)據(jù)元素間抽象化的相互關(guān)系，與數(shù)據(jù)的存儲(chǔ)無關(guān)，獨(dú)立于計(jì)算機(jī)，它是從具體問題抽象出來的數(shù)學(xué)模型。存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）----數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。北京林業(yè)大學(xué)信息學(xué)院

13:45

劃分方法一（1）線性結(jié)構(gòu)----有且僅有一個(gè)開始和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)后繼。例如：線性表、棧、隊(duì)列、串（2）非線性結(jié)構(gòu)----一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。例如：樹、圖邏輯結(jié)構(gòu)北京林業(yè)大學(xué)信息學(xué)院

13:45

線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系圖形結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖邏輯結(jié)構(gòu)劃分方法二北京林業(yè)大學(xué)信息學(xué)院

13:45

存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系存儲(chǔ)結(jié)構(gòu)北京林業(yè)大學(xué)信息學(xué)院

13:45

元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)北京林業(yè)大學(xué)信息學(xué)院

13:45

1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h北京林業(yè)大學(xué)信息學(xué)院

13:45

邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同,但運(yùn)算不同,則數(shù)據(jù)結(jié)構(gòu)不同.例如,棧與隊(duì)列對(duì)于一種數(shù)據(jù)結(jié)構(gòu),常見的運(yùn)算插入刪除修改查找排序數(shù)據(jù)的運(yùn)算北京林業(yè)大學(xué)信息學(xué)院

13:45

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：插入、刪除、修改、查找、排序

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表

棧、隊(duì)列

串、數(shù)組樹形結(jié)構(gòu)圖形結(jié)構(gòu)邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)北京林業(yè)大學(xué)信息學(xué)院

13:45

定義：在一種程序設(shè)計(jì)語言中，變量所具有的數(shù)據(jù)種類數(shù)據(jù)類型FORTRAN語言：整型、實(shí)型、和復(fù)數(shù)型C語言：基本數(shù)據(jù)類型：

charintfloatdoublevoid構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、文件

數(shù)據(jù)類型是一組性質(zhì)相同的值的集合,以及定義于這個(gè)集合上的一組運(yùn)算的總稱北京林業(yè)大學(xué)信息學(xué)院

13:45

抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)更高層次的數(shù)據(jù)抽象由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的操作抽象數(shù)據(jù)類型北京林業(yè)大學(xué)信息學(xué)院

13:45

抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，S，P）數(shù)據(jù)對(duì)象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式北京林業(yè)大學(xué)信息學(xué)院

13:45

抽象數(shù)據(jù)類型查找插入刪除修改

線性表接口或用戶界面數(shù)據(jù)類型的物理實(shí)現(xiàn)封裝信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離北京林業(yè)大學(xué)信息學(xué)院

13:45

1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。它有些類似C語言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的操作教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具但上機(jī)時(shí)要用具體語言實(shí)現(xiàn)，如C或C++等北京林業(yè)大學(xué)信息學(xué)院

13:45

(1)預(yù)定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedefintStatus;北京林業(yè)大學(xué)信息學(xué)院

13:45

(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。(3)算法描述為以下的函數(shù)形式：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

語句序列；

}北京林業(yè)大學(xué)信息學(xué)院

13:45

（4）內(nèi)存的動(dòng)態(tài)分配與釋放使用new和delete動(dòng)態(tài)分配和釋放內(nèi)存空間分配空間指針變量=new數(shù)據(jù)類型;釋放空間delete指針變量;（5）賦值語句（6）選擇語句（7）循環(huán)語句北京林業(yè)大學(xué)信息學(xué)院

13:45

（8）使用的結(jié)束語句形式有：函數(shù)結(jié)束語句return循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）；北京林業(yè)大學(xué)信息學(xué)院

13:45

（9）輸入輸出語句形式有：輸入語句cin(scanf())輸出語句cout(printf())（10）擴(kuò)展函數(shù)有：求最大值max求最小值min北京林業(yè)大學(xué)信息學(xué)院

13:45

算法定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列算法的描述：

自然語言流程圖程序設(shè)計(jì)語言

偽碼1.4算法和算法分析北京林業(yè)大學(xué)信息學(xué)院

13:45

算法的特性：

輸入

有0個(gè)或多個(gè)輸入輸出

有一個(gè)或多個(gè)輸出(處理結(jié)果)

確定性

每步定義都是確切、無歧義的有窮性

算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性

每一條運(yùn)算應(yīng)足夠基本北京林業(yè)大學(xué)信息學(xué)院

13:45

算法的評(píng)價(jià)正確性可讀性健壯性高效性（時(shí)間代價(jià)和空間代價(jià)）北京林業(yè)大學(xué)信息學(xué)院

13:45

算法效率：用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來度量 算法的效率的度量事后統(tǒng)計(jì)事前分析估計(jì)北京林業(yè)大學(xué)信息學(xué)院

13:45

1.事后統(tǒng)計(jì)：利用計(jì)算機(jī)內(nèi)的計(jì)時(shí)功能，不同算法的程序可以用一組或多組相同的統(tǒng)計(jì)數(shù)據(jù)區(qū)分

缺點(diǎn)：必須先運(yùn)行依據(jù)算法編制的程序所得時(shí)間統(tǒng)計(jì)量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

北京林業(yè)大學(xué)信息學(xué)院

13:45

2.事前分析估計(jì)：一個(gè)高級(jí)語言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：

依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同的語言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———使用絕對(duì)時(shí)間單位衡量算法效率不合適北京林業(yè)大學(xué)信息學(xué)院

13:45

算法中關(guān)鍵操作（循環(huán)和遞歸）重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間量度記作：T(n)=O(f(n))

時(shí)間復(fù)雜度的漸進(jìn)表示法漸進(jìn)符號(hào)（O）的定義：當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)C和n0

，使得對(duì)所有的

nn0

，有T(n)Cf(n)，則

T(n)=O(f(n))表示隨著n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱漸近時(shí)間復(fù)雜度。北京林業(yè)大學(xué)信息學(xué)院

13:45

n*n階矩陣加法：for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=a[i][j]+b[i][j]; 語句的頻度（FrequencyCount):重復(fù)執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運(yùn)算量和問題的規(guī)模n的平方是同一個(gè)量級(jí)北京林業(yè)大學(xué)信息學(xué)院

13:45

變量計(jì)數(shù)x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)

for(intj=0;j<n;j++)y++;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)北京林業(yè)大學(xué)信息學(xué)院

13:45

voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行

sum[i]=0.0;//數(shù)據(jù)累加

for(intj=0;j<n;j++)

sum[i]+=x[i][j];//關(guān)鍵操作

}

for(i=0;i<m;i++)//打印各行數(shù)據(jù)和

cout<<i<<“:”<<sum[i]<<endl;//關(guān)鍵操作

}漸進(jìn)時(shí)間復(fù)雜度為

O(max(m*n,m))算法的時(shí)間復(fù)雜度是由嵌套最深層語句的頻度決定的北京林業(yè)大學(xué)信息學(xué)院

13:45

例1：N×N矩陣相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0; for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];} 算法中的基本操作語句為c[i][j]=c[i][j]+a[i][k]*b[k][j];

北京林業(yè)大學(xué)信息學(xué)院

13:45

例2：for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

for(k=1;k<=j;k++)

x=x+1;語句頻度

=北京林業(yè)