數(shù)據(jù)結(jié)構(gòu)-麗水學(xué)院課件

麗水學(xué)院工學(xué)院第1章緒論

麗水學(xué)院工學(xué)院編程基礎(chǔ)計(jì)算機(jī)及相關(guān)專業(yè)考研考博課程計(jì)算機(jī)等級(jí)考試課程程序員考試課程為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)編程基礎(chǔ)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)指導(dǎo)1.提前預(yù)習(xí)、認(rèn)真聽課、按時(shí)完成書面及上機(jī)作業(yè)2.注意先修課程的知識(shí)準(zhǔn)備離散數(shù)學(xué)、C語(yǔ)言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)容靈活、不易掌握課程學(xué)習(xí)指導(dǎo)1.提前預(yù)習(xí)、認(rèn)真聽課、按時(shí)完成書面及上機(jī)作業(yè)課平時(shí)成績(jī):40%考勤20%、課堂表現(xiàn)10%、作業(yè)20%、實(shí)驗(yàn)50%課堂紀(jì)律無(wú)故遲到：無(wú)故曠課：-5上機(jī)：玩游戲、上網(wǎng)聊天-5期末成績(jī):60%(閉卷筆試)考核方式麗水學(xué)院工學(xué)院平時(shí)成績(jī):40%考核方式麗水學(xué)院工學(xué)院教材和參考書教材：《數(shù)據(jù)結(jié)構(gòu)》(第2版)，嚴(yán)蔚敏，李冬梅等，人民郵電出版社

參考書：《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏，清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++描述》，殷人昆等，清華大學(xué)出版社《算法藝術(shù)與信息學(xué)競(jìng)賽》，劉汝佳，黃亮清華大學(xué)出版社

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

教學(xué)目標(biāo)麗水學(xué)院工學(xué)院第1章緒論1.了解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容教學(xué)目標(biāo)麗水學(xué)院1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法與算法分析教學(xué)內(nèi)容麗水學(xué)院工學(xué)院1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容教學(xué)內(nèi)容麗水學(xué)院工學(xué)院N.沃思（NiklausWirth)教授提出：

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

早期：主要用于數(shù)值計(jì)算

后來(lái)：

處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域，能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容N.沃思（NiklausWirth)教授提出：1.1書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表麗水學(xué)院工學(xué)院書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版人機(jī)對(duì)奕問題樹……..……..…...…...…...…...人機(jī)對(duì)奕問題樹……..……..…...…...…...…../(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖樹麗水學(xué)院工學(xué)院/(root)binlibuseretcmathdsswy

*

多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖頂點(diǎn)：一條通路連線：不能同時(shí)通行染色：有連線的兩個(gè)頂點(diǎn)不能具有相同顏色*多求解非數(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)系和操作。求解非數(shù)值計(jì)算的問題：北京林業(yè)大學(xué)信息學(xué)院

*

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

麗水學(xué)院工學(xué)院北京林業(yè)大學(xué)信息學(xué)院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é)院1、數(shù)據(jù)（data)—所有能輸入到計(jì)算機(jī)中去的描述客觀事物的整數(shù)數(shù)據(jù)對(duì)象

N={0,1,2,…}學(xué)生數(shù)據(jù)對(duì)象學(xué)生記錄的集合4、數(shù)據(jù)對(duì)象(DataObject)：相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集整數(shù)數(shù)據(jù)對(duì)象4、數(shù)據(jù)對(duì)象(DataObject)：相同特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)系。麗水學(xué)院工學(xué)院5、數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一數(shù)據(jù)結(jié)構(gòu)的兩個(gè)層次：邏輯結(jié)構(gòu)---數(shù)據(jù)元素間抽象化的相互關(guān)系，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，獨(dú)立于計(jì)算機(jī)，它是從具體問題抽象出來(lái)的數(shù)學(xué)模型。存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）----數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。麗水學(xué)院工學(xué)院數(shù)據(jù)結(jié)構(gòu)的兩個(gè)層次：麗水學(xué)院工學(xué)院劃分方法一（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)麗水學(xué)院工學(xué)院劃分方法一邏輯結(jié)構(gòu)麗水學(xué)院工學(xué)院線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系圖形結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖邏輯結(jié)構(gòu)劃分方法二麗水學(xué)院工學(xué)院線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系存儲(chǔ)結(jié)構(gòu)麗水學(xué)院工學(xué)院存儲(chǔ)結(jié)構(gòu)分為：存儲(chǔ)結(jié)構(gòu)麗水學(xué)院工學(xué)院元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)麗水學(xué)院工學(xué)院元素n……..元素i……..元素2元素1LoLo+mLo+(1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

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

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

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

h麗水學(xué)院工學(xué)院1536元素21400元素11346元素3∧元素41345邏輯結(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)算邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同,但運(yùn)算不同,則數(shù)據(jù)結(jié)構(gòu)不同。例定義：在一種程序設(shè)計(jì)語(yǔ)言中，變量所具有的數(shù)據(jù)種類數(shù)據(jù)類型FORTRAN語(yǔ)言：整型、實(shí)型、和復(fù)數(shù)型C語(yǔ)言：基本數(shù)據(jù)類型：

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

數(shù)據(jù)類型是一組性質(zhì)相同的值的集合,以及定義于這個(gè)集合上的一組運(yùn)算的總稱定義：在一種程序設(shè)計(jì)語(yǔ)言中，變量所具有的數(shù)據(jù)種類數(shù)據(jù)類型F抽象數(shù)據(jù)類型

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

(ADTs:AbstractData抽象數(shù)據(jù)類型可以用以下的三元組來(lái)表示：

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常用定義格式麗水學(xué)院工學(xué)院抽象數(shù)據(jù)類型可以用以下的三元組來(lái)表示：ADT抽象數(shù)據(jù)類型名{1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來(lái)表示和實(shí)現(xiàn)。它有些類似C語(yǔ)言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的操作教材中用的是類C語(yǔ)言（介于偽碼和C語(yǔ)言之間）作為描述工具但上機(jī)時(shí)要用具體語(yǔ)言實(shí)現(xiàn)，如C或C++等麗水學(xué)院工學(xué)院1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可以通過固有的(1)預(yù)定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK1#defineERROR0#defineOVERFLOW-2//Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedefintStatus;(1)預(yù)定義常量及類型(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。(3)算法描述為以下的函數(shù)形式：函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

語(yǔ)句序列；

}(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具（4）內(nèi)存的動(dòng)態(tài)分配與釋放使用new和delete動(dòng)態(tài)分配和釋放內(nèi)存空間分配空間指針變量=new數(shù)據(jù)類型;釋放空間delete指針變量;（5）賦值語(yǔ)句（6）選擇語(yǔ)句（7）循環(huán)語(yǔ)句麗水學(xué)院工學(xué)院（4）內(nèi)存的動(dòng)態(tài)分配與釋放（5）賦值語(yǔ)句麗水學(xué)院工學(xué)院（8）使用的結(jié)束語(yǔ)句形式有：函數(shù)結(jié)束語(yǔ)句return循環(huán)結(jié)束語(yǔ)句break;異常結(jié)束語(yǔ)句exit（異常代碼）；麗水學(xué)院工學(xué)院（8）使用的結(jié)束語(yǔ)句形式有：麗水學(xué)院工學(xué)院（9）輸入輸出語(yǔ)句形式有：輸入語(yǔ)句cin(scanf())輸出語(yǔ)句cout(printf())（10）擴(kuò)展函數(shù)有：求最大值max求最小值min麗水學(xué)院工學(xué)院（9）輸入輸出語(yǔ)句形式有：麗水學(xué)院工學(xué)院算法定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列算法的描述：

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

偽碼1.4算法和算法分析算法定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了算法的特性：

輸入

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

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

確定性

每步定義都是確切、無(wú)歧義的有窮性

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

每一條運(yùn)算應(yīng)足夠基本麗水學(xué)院工學(xué)院算法的特性：麗水學(xué)院工學(xué)院算法的評(píng)價(jià)正確性可讀性健壯性高效性（時(shí)間代價(jià)和空間代價(jià)）算法的評(píng)價(jià)正確性算法效率：用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來(lái)度量 算法的效率的度量事后統(tǒng)計(jì)事前分析估計(jì)算法效率：用依據(jù)該算法編制的程序在計(jì)算機(jī)上執(zhí)行所消耗的時(shí)間來(lái)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)劣

麗水學(xué)院工學(xué)院1.事后統(tǒng)計(jì)：利用計(jì)算機(jī)內(nèi)的計(jì)時(shí)功能，不同算法的程序可以用一2.事前分析估計(jì)：一個(gè)高級(jí)語(yǔ)言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：

依據(jù)的算法選用何種策略問題的規(guī)模程序語(yǔ)言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在不同的計(jì)算機(jī)上運(yùn)行，效率均不同，———使用絕對(duì)時(shí)間單位衡量算法效率不合適麗水學(xué)院工學(xué)院2.事前分析估計(jì)：同一個(gè)算法用不同的語(yǔ)言、不同的編譯程序、在算法中基本語(yǔ)句重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間量度記作：T(n)=O(f(n))

時(shí)間復(fù)雜度的漸進(jìn)表示法數(shù)學(xué)符號(hào)“O”的定義為：若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)

=

O(f(n))表示存在正的常數(shù)C和n0，使得當(dāng)n≥n0時(shí)都滿足0≤T(n)≤Cf(n)。表示隨著n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱漸近時(shí)間復(fù)雜度。n越大算法的執(zhí)行時(shí)間越長(zhǎng)排序：n為記錄數(shù)矩陣：n為矩陣的階數(shù)多項(xiàng)式：n為多項(xiàng)式的項(xiàng)數(shù)集合：n為元素個(gè)數(shù)樹：n為樹的結(jié)點(diǎn)個(gè)數(shù)圖：n為圖的頂點(diǎn)數(shù)或邊數(shù)算法中重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的語(yǔ)句對(duì)算法運(yùn)行時(shí)間的貢獻(xiàn)最大麗水學(xué)院工學(xué)院算法中基本語(yǔ)句重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n),n*n階矩陣加法：for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=a[i][j]+b[i][j]; 語(yǔ)句的頻度（FrequencyCount):重復(fù)執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運(yùn)算量和問題的規(guī)模n的平方是同一個(gè)量級(jí)麗水學(xué)院工學(xué)院n*n階矩陣加法：麗水學(xué)院工學(xué)院x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)

for(intj=0;j<n;j++)y++;找出語(yǔ)句頻度最大的那條語(yǔ)句作為基本語(yǔ)句計(jì)算基本語(yǔ)句的頻度得到問題規(guī)模n的某個(gè)函數(shù)f(n)取其數(shù)量級(jí)用符號(hào)“O”表示分析算法時(shí)間復(fù)雜度的基本方法f(n)=n2T(n)=O(n2)麗水學(xué)院工學(xué)院x=0;y=0;找出語(yǔ)句頻度最大的那條語(yǔ)句作為基

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

sum[i]=0.0;

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

sum[i]+=x[i][j];

}

for(i=0;i<m;i++)

cout<<i<<“:”<<sum[i]<<endl;

}時(shí)間復(fù)雜度是由嵌套最深層語(yǔ)句的頻度決定的f(n)=m*nT(n)=O(m*n)麗水學(xué)院工學(xué)院voidexam(floatx[][],in例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];} 算法中的基本操作語(yǔ)句為c[i][j]=c[i][j]+a[i][k]*b[k][j];

麗水學(xué)院工學(xué)院例1：N×N矩陣相乘算法中的基本操作語(yǔ)句為c[i][j]=c例2：for(i=1;i<=n;i++)

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

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

x=x+1;語(yǔ)句頻度

=定理1.1若f(n)=amnm+am-1nm-1+

+a1n+a0是m次多項(xiàng)式，則T(n)=O(nm)。忽略所有低次冪項(xiàng)和最高次冪系數(shù)，體現(xiàn)出增長(zhǎng)率的含義麗水學(xué)院工學(xué)院例2：語(yǔ)句頻度=定理1.1忽略所有低次冪項(xiàng)和最高次冪系數(shù)，例3：分析以下程序段的時(shí)間復(fù)雜度i=1;①while(i<=n) i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時(shí)間復(fù)雜度T(n)=O(log2n)麗水學(xué)院工學(xué)院例3：分析以下程序段的時(shí)間復(fù)雜度i=1;例4：順序查找，在數(shù)組a[i]中查找值等于e的元素，返回其所