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

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

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

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

4、和內(nèi)在聯(lián)系。掌握算法的計算復(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ù)計人口增長情況，現(xiàn)有人口13億，要在5年內(nèi)控制在15億以內(nèi)，每年的增長率不能超過多少？數(shù)學(xué)模型：數(shù)學(xué)方程數(shù)值計算問題：92022/9/15非數(shù)值計算問題例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 書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表112022/9/15 對表中任一結(jié)點，與它相鄰且在它前面的結(jié)點最多只有一個（亦稱為直接前驅(qū)）； 與表中任一結(jié)點相鄰且在其后的結(jié)點也最多只有一個（亦稱為直接后繼）； 表中只有第一個結(jié)點沒有直接前驅(qū)（亦稱為開始結(jié)點）； 表中只有最后一個結(jié)點沒有直接后繼（亦稱為終端結(jié)點）。邏輯特征：一對一122022/9/15例2 人機對奕問題樹.132022/9/15 若將從對弈開始到結(jié)束的過程中所有可能出現(xiàn)的格局都畫在一張圖上，則可得到一棵倒長的“

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

7、2022/9/15數(shù)據(jù)組織的特點：線性（一對一）樹（一對多）圖（多對多）邏輯結(jié)構(gòu)182022/9/15數(shù)據(jù)結(jié)構(gòu)定義: 是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科192022/9/151.2 基本概念和術(shù)語數(shù)據(jù)（data)所有能輸入到計算機中去的描述客觀事物的符號數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱結(jié)點（node）或記錄（record）數(shù)據(jù)項（data item）有獨立含義的數(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ù)元素間除“同屬于一個集合”外，無其它關(guān)系線性結(jié)構(gòu)一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)一個對多個，如樹圖狀結(jié)構(gòu)多個對多個，如圖202022/9/15數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲（物理）結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)212022/9/15 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲 鏈式存儲 線性表棧隊樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：2022/9/15221.3 什么是抽象數(shù)據(jù)類型1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？2 抽象數(shù)據(jù)類型如何定義？3 抽象數(shù)據(jù)類型如何表示和實現(xiàn)？ 討論：抽象數(shù)據(jù)類型和

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

10、ral Number )的抽象數(shù)據(jù)類型定義。ADT Natural_Number isobjects: 一個整數(shù)的有序子集合，它開始于0，結(jié)束于機器能表示的最大整數(shù) (MAX INT)functions: 對于所有的 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ù)類型如何表示和實現(xiàn) 抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。 即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。

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