《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課堂課件-第1章-引論

1、2022/9/151算法與數(shù)據(jù)結(jié)構(gòu)22022/9/15學(xué)時(shí)安排與成績?cè)u(píng)定總學(xué)時(shí)90 = 授課（72）+ 上機(jī)（18）總評(píng)成績 = 考試（70%）+ 平時(shí)成績（10%）+上機(jī)（20%）32022/9/15為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計(jì)的發(fā)展程序設(shè)計(jì)經(jīng)歷了三個(gè)階段：1.無結(jié)構(gòu)階段：四十年代六十年代 程序設(shè)計(jì)主要針對(duì)科學(xué)計(jì)算，數(shù)據(jù)對(duì)象單純，程序以算法為中心， 程序設(shè)計(jì)技術(shù)以機(jī)器語言、匯編語言的機(jī)制為基礎(chǔ)2.結(jié)構(gòu)化程序設(shè)計(jì)階段：六十年代末八十年代 認(rèn)識(shí)到程序設(shè)計(jì)的規(guī)范性，提出程序結(jié)構(gòu)模塊化，以功能為中心 主要標(biāo)志：1968年D.E.Knuth的巨著 “The art of compu

2、ter programming” 的發(fā)表 3.面向?qū)ο箅A段：八十年代初興起，九十年代流行 數(shù)據(jù)是程序的“主人”，對(duì)象是劃分與構(gòu)造程序的主要單位 42022/9/15為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 從60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)化程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們就越來越重視數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的引入，對(duì)程序設(shè)計(jì)的規(guī)范化起到重大作用。認(rèn)為程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)確定的問題選擇一種好的結(jié)構(gòu)，加上一種好的算法: 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序52022/9/15 數(shù)據(jù)結(jié)構(gòu)作為一們獨(dú)立的課程在國外是從1968年開始設(shè)立的。它是計(jì)算機(jī)科學(xué)的一門綜合性的專業(yè)基礎(chǔ)課。它不僅是一般程序設(shè)計(jì)

3、的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型程序的重要基礎(chǔ)。 程序設(shè)計(jì)是計(jì)算機(jī)專業(yè)的“入門課” 數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)軟件課程系列中最主要的 “看家本領(lǐng)” 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)62022/9/15教學(xué)目的：學(xué)習(xí)常用的數(shù)據(jù)結(jié)構(gòu)，熟悉各種基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示、運(yùn)算方法、典型應(yīng)用；了解每一種數(shù)據(jù)結(jié)構(gòu)的使用代價(jià)和益處，培養(yǎng)同學(xué)根據(jù)實(shí)際問題的要求，選擇合適的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法的能力；掌握一些典型算法，培養(yǎng)算法分析的能力；進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練，解題能力和技巧的訓(xùn)練是整個(gè)教學(xué)活動(dòng)的重要環(huán)節(jié)；72022/9/15第1章 引 論理解算法的概念。理解什么是程序，程序與算法的區(qū)別

4、和內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。熟悉抽象數(shù)據(jù)類型的基本概念。熟悉數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的概念。理解數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型三者的區(qū)別和聯(lián)系。掌握用C語言描述數(shù)據(jù)結(jié)構(gòu)與算法的方法。82022/9/15例1 雞兔同籠，雞腳 X 只，兔腳 Y 只，問雞、兔各幾只？例2 預(yù)計(jì)人口增長情況，現(xiàn)有人口13億，要在5年內(nèi)控制在15億以內(nèi)，每年的增長率不能超過多少？數(shù)學(xué)模型：數(shù)學(xué)方程數(shù)值計(jì)算問題：92022/9/15非數(shù)值計(jì)算問題例1 圖書管理系統(tǒng)關(guān)鍵：如何有效組織圖書？例2 學(xué)生信息表關(guān)鍵：如何合理存放記錄？數(shù)學(xué)模型：數(shù)據(jù)結(jié)構(gòu)102022/9/15第一章 引論1.1

5、什么是數(shù)據(jù)結(jié)構(gòu) 程序=數(shù)據(jù)結(jié)構(gòu)+算法例1 書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表112022/9/15 對(duì)表中任一結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)最多只有一個(gè)（亦稱為直接前驅(qū)）； 與表中任一結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)也最多只有一個(gè)（亦稱為直接后繼）； 表中只有第一個(gè)結(jié)點(diǎn)沒有直接前驅(qū)（亦稱為開始結(jié)點(diǎn)）； 表中只有最后一個(gè)結(jié)點(diǎn)沒有直接后繼（亦稱為終端結(jié)點(diǎn)）。邏輯特征：一對(duì)一122022/9/15例2 人機(jī)對(duì)奕問題樹.132022/9/15 若將從對(duì)弈開始到結(jié)束的過程中所有可能出現(xiàn)的格局都畫在一張圖上，則可得到一棵倒長的“

6、樹”?！皹涓笔菍?duì)弈開始之前的棋盤格局，而所有的“葉子”就是可能出現(xiàn)的結(jié)局，對(duì)弈的過程就是從樹根沿樹叉到某個(gè)葉子的過程。邏輯特征：一對(duì)多142022/9/15多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖152022/9/15101582551750810109220在N個(gè)城市之間建立通信網(wǎng)絡(luò)問題：如何使該網(wǎng)絡(luò)造價(jià)最低？邏輯特征：多對(duì)多數(shù)據(jù)結(jié)構(gòu)：圖162022/9/15邏輯特征：多對(duì)多 每個(gè)城市表示成一個(gè)頂點(diǎn)，城市之間的通信線路表示成一個(gè)連線。若干個(gè)頂點(diǎn)及其連線構(gòu)成一個(gè)圖的結(jié)構(gòu)。 不同的連線方法得到不同的圖，造價(jià)最低的通信網(wǎng)絡(luò)就是求最小連通圖的問題。17

7、2022/9/15數(shù)據(jù)組織的特點(diǎn)：線性（一對(duì)一）樹（一對(duì)多）圖（多對(duì)多）邏輯結(jié)構(gòu)182022/9/15數(shù)據(jù)結(jié)構(gòu)定義: 是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科192022/9/151.2 基本概念和術(shù)語數(shù)據(jù)（data)所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱結(jié)點(diǎn)（node）或記錄（record）數(shù)據(jù)項(xiàng)（data item）有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)數(shù)據(jù)結(jié)構(gòu)（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）數(shù)

8、據(jù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系線性結(jié)構(gòu)一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)一個(gè)對(duì)多個(gè)，如樹圖狀結(jié)構(gòu)多個(gè)對(duì)多個(gè)，如圖202022/9/15數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)212022/9/15 數(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ǔ) 線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：2022/9/15221.3 什么是抽象數(shù)據(jù)類型1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？2 抽象數(shù)據(jù)類型如何定義？3 抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn)？ 討論：抽象數(shù)據(jù)類型和

9、偽碼是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的工具2022/9/15231 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別數(shù)據(jù)類型：是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）它與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）2022/9/15242 抽象數(shù)據(jù)類型如何定義抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = （D，R，P）ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作 ： ADT抽象數(shù)據(jù)類型名ADT常用定義格式數(shù)據(jù)對(duì)象D上的關(guān)系集D上的操作集例：給出自然數(shù)(Natu

10、ral Number )的抽象數(shù)據(jù)類型定義。ADT Natural_Number isobjects: 一個(gè)整數(shù)的有序子集合，它開始于0，結(jié)束于機(jī)器能表示的最大整數(shù) (MAX INT)functions: 對(duì)于所有的 x, y Natural_Number； TRUE, FALSE Boolean； +, -, , = = ,=等都是可用的服務(wù)。Zero ( )： Natural Number 返回 0IsZero(x)： Boolean if (x=0) 返回TRUE else 返回 FALSEAdd(x, y)： Natural Number if (x+y = MAX INT)返回 x+

11、y else 返回 MAX INTSubtract(x,y): Natural Number if (xy)返回0 else 返回x-yEqual(x,y): Boolean if (x= y)返回TRUE else 返回FALSESuccessor(x) : Natural Number if (x = MAX INT)返回x else 返回x+1end Natural_Number 2022/9/15263 抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn) 抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。 即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。

12、注 ：它有些類似C語言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的服務(wù)。但上機(jī)時(shí)要用具體語言實(shí)現(xiàn)，如C或C+等272022/9/151.4 算法的描述和算法分析簡介算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列算法特性算法的描述采用C語言算法的評(píng)價(jià)衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)可讀性(readability)健壯性(robustness)效率與低存儲(chǔ)量282022/9/15評(píng)價(jià)算法的標(biāo)準(zhǔn)： 評(píng)價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。 292022/9/15時(shí)間復(fù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)的階數(shù) T(n)=O(f(n)空間復(fù)雜度：S(n)=O(f(n)算法語句 對(duì)應(yīng)的語句頻度 1for（i=0；i n;i+） n 2 for （j=0；jn;j+） n2 3 cij=0; n2 4 for (k=0;k=(y+1)*(y+1) y+;C312022/9/15 空間效率的分析 一個(gè)算法的空間效率是指在算法的執(zhí)行過程中，所占據(jù)的輔助空間數(shù)量。輔助空間就是除算法代碼本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時(shí)開辟的存儲(chǔ)空間單元。在有些