第1章-數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

數(shù)據(jù)結(jié)構(gòu)2020.2第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第1頁。第1章數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第2頁。為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)如何學(xué)好數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的概念算法和算法分析習(xí)題0102030405目錄第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第3頁。本章要點(diǎn)掌握數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)方法掌握數(shù)據(jù)結(jié)構(gòu)基本概念掌握算法時(shí)間復(fù)雜度的分析方法第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第4頁。

基本準(zhǔn)備，初識數(shù)據(jù)與結(jié)構(gòu)1.1第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)+結(jié)構(gòu)人們常說的大數(shù)據(jù)時(shí)代與信息時(shí)代，究竟什么是數(shù)據(jù)，什么是信息呢？數(shù)據(jù):數(shù)字、文字、圖片、聲音、視頻都是數(shù)據(jù)信息：是對數(shù)據(jù)進(jìn)行操作和分析之后得出的產(chǎn)物。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的容器，裝載數(shù)據(jù)達(dá)到最終的目的。1.1初識數(shù)據(jù)與結(jié)構(gòu)第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)的概念1.2第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第7頁。1.2數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)：一切可以被計(jì)算機(jī)所識別的文字符號圖像音視頻等都屬于數(shù)據(jù)因此數(shù)據(jù)是一個(gè)相當(dāng)龐大、抽象和籠統(tǒng)的概念。數(shù)據(jù)元素:是有一定意義數(shù)據(jù)的基本單位，作為整體處理的單位。數(shù)據(jù)項(xiàng):是數(shù)據(jù)的最小標(biāo)識單位。

一個(gè)記錄可稱為一個(gè)數(shù)據(jù)元素，一個(gè)字段就是一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)對象:是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)結(jié)構(gòu):相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第8頁?！纠?-1】這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄,每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)

(即學(xué)號、姓別、性別和C語言)組成。

1.2數(shù)據(jù)結(jié)構(gòu)的概念第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第9頁。1.2數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)物理結(jié)構(gòu):

是數(shù)據(jù)元素在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。(實(shí)現(xiàn)層)邏輯結(jié)構(gòu):

是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。屬于用戶視圖，

是面向問題的，反映數(shù)據(jù)內(nèi)部的構(gòu)成方式。(抽象層)第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第10頁。1.2.1數(shù)據(jù)的物理結(jié)構(gòu)物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))是數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)實(shí)現(xiàn)，

分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。順序存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素按某種順序依此存放在計(jì)算機(jī)存儲(chǔ)器的連續(xù)存儲(chǔ)單元中，其存儲(chǔ)的地址由起始地址和元素所占的存儲(chǔ)空間來決定鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):

把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可連續(xù)的，也可不連續(xù)的，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第11頁。1.2.1數(shù)據(jù)的物理結(jié)構(gòu)—順序存儲(chǔ)S是起始地址，H是每個(gè)元素所占的空間則第i個(gè)元素的存儲(chǔ)地址為:

Loc(i)=Loc(1)+(i-1)*H=S+(i-1)*H

第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第12頁。1.2.1數(shù)據(jù)的物理結(jié)構(gòu)—順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn):結(jié)點(diǎn)中只有自身數(shù)據(jù)域。因此存儲(chǔ)密度大，利用率高?？梢酝ㄟ^計(jì)算確定數(shù)據(jù)結(jié)構(gòu)中第i個(gè)元素的位置，可以(直接)隨機(jī)存取。插入和刪除操作會(huì)引起大量的元素移動(dòng)。

必須存儲(chǔ)在一片地址連續(xù)的存儲(chǔ)單元中。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第13頁。1.2.1數(shù)據(jù)的物理結(jié)構(gòu)—鏈?zhǔn)酱鎯?chǔ)把邏輯上相鄰的元素存放在物理上不相鄰的存儲(chǔ)單元中。主要特點(diǎn)：有表示連接信息的指針域。因此存儲(chǔ)密度小，利用率低。邏輯上相鄰的結(jié)點(diǎn)在物理上不一定鄰接。

插入和刪除操作靈活方便;只要修改指針域的值即可?？梢源鎯?chǔ)在不連續(xù)的存儲(chǔ)單元中。

第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第14頁。1.2.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間關(guān)系的描述，可看作是從具體問題抽象出來的數(shù)學(xué)模型。與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。通常邏輯結(jié)構(gòu)有四類：集合結(jié)構(gòu):

數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。線性結(jié)構(gòu):

該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對一的關(guān)系。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第15頁。1.2.2數(shù)據(jù)的邏輯結(jié)構(gòu)樹型結(jié)構(gòu):該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的關(guān)系。圖形結(jié)構(gòu):該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，

也稱作網(wǎng)狀結(jié)構(gòu)。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第16頁。1.2.2數(shù)據(jù)的邏輯結(jié)構(gòu)-舉例說明線性數(shù)據(jù)結(jié)構(gòu)樹型數(shù)據(jù)結(jié)構(gòu)圖形數(shù)據(jù)結(jié)構(gòu)第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第17頁。1.2.3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=數(shù)據(jù)+數(shù)據(jù)的物理結(jié)構(gòu)+數(shù)據(jù)的邏輯結(jié)構(gòu)第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第18頁。1.2.3數(shù)據(jù)類型與抽象數(shù)據(jù)類型數(shù)據(jù)類型是編程中對不同種類數(shù)據(jù)的一種分類與定義。

常見的數(shù)據(jù)類型有整型，浮點(diǎn)型，字符型，布爾型等

抽象數(shù)據(jù)類型是用基本數(shù)據(jù)類型來描述事物的各個(gè)屬性，再把

所有屬性當(dāng)做一個(gè)整體來看待。

數(shù)據(jù)結(jié)構(gòu)的運(yùn)算插入、刪除、更新、檢索、排序加工型操作:操作改變了存儲(chǔ)結(jié)構(gòu)的值。引用型操作:操作只是查詢或求得結(jié)點(diǎn)的值。

第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第19頁。為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1.3第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第20頁。1.3為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。要想有效地使用計(jì)算機(jī)、充分發(fā)揮計(jì)算機(jī)的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第21頁。如何學(xué)好數(shù)據(jù)結(jié)構(gòu)1.4第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第22頁。1.4

如何學(xué)好數(shù)據(jù)結(jié)構(gòu)(1)要求掌握基本的C語言知識，掌握模塊化程序設(shè)計(jì)的基本思想，能夠利用C語言熟練編寫一些簡單的程序。(2)在學(xué)習(xí)時(shí)，首先要掌握各種基本的數(shù)據(jù)結(jié)構(gòu)，并對各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)有足夠的認(rèn)識。

(3)對基于各種數(shù)據(jù)結(jié)構(gòu)的常見的操作及其算法要重點(diǎn)掌握，并要了解評價(jià)某個(gè)具體算法優(yōu)劣的方法。

(4)多思考、多做練習(xí)題、多上機(jī)實(shí)踐。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第23頁。算法與算法分析基礎(chǔ)1.5第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第24頁。1.5

算法和算法分析基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)+算法=編程

算法是描述解決問題的方法。在計(jì)算機(jī)中表現(xiàn)指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第25頁。1.5.1

算法特性(1)有窮性：一個(gè)算法必須在有窮步之后結(jié)束，即有限時(shí)間內(nèi)完成。如計(jì)算機(jī)需要30年的時(shí)間才能結(jié)束，算法的意義就不大。(2)確定性：算法的每一步必須有確切的定義，無二義性。相同的輸入僅有唯一的輸出結(jié)果。(3)可行性：算法中的每一步都可實(shí)現(xiàn)，即每一步都是經(jīng)過有限次數(shù)執(zhí)行得以實(shí)現(xiàn)。(4)輸入：一個(gè)算法具有零個(gè)或多個(gè)輸入，可以沒有輸入。

(5)輸出：一個(gè)算法具有一個(gè)或多個(gè)輸出，至少有一個(gè)輸出。

第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第26頁。1.5.1

算法特性要設(shè)計(jì)一個(gè)好的算法通常要考慮以下的要求：(1)正確性：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。

(2)可讀性：一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。

(3)健壯性(魯棒性)：當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后果，陷入死機(jī)。(4)高效率和低存儲(chǔ)量：有效使用存儲(chǔ)空間和有較高的時(shí)間效率。

第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第27頁?！纠?-5】求n個(gè)數(shù)的最大值。分析健壯性

main(){ intmax=0,x; for(inti=1;i<=n;i++){ scanf(“%d”,&x); if(x>max) max=x; } printf(“%d”,max); }提示：本程序無語法錯(cuò)誤，當(dāng)輸入全為正數(shù)時(shí)，結(jié)果正確；當(dāng)輸入全為負(fù)數(shù)時(shí)，求得的最大值為0，結(jié)果不正確。既要輸入正確的數(shù)據(jù)，也要輸入錯(cuò)誤的數(shù)據(jù)進(jìn)行健壯性測試。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第28頁。1.5.2

算法性能分析與度量評價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。好的算法具備時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)。對同一問題，有多個(gè)算法，執(zhí)行時(shí)間短的效率高，存儲(chǔ)量是指執(zhí)行過程需要的最少存儲(chǔ)量。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第29頁。1.5.2

算法性能分析與度量（1）關(guān)于算法執(zhí)行時(shí)間一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語句執(zhí)行時(shí)間的總和語句的執(zhí)行時(shí)間是指該語句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。兩個(gè)算法的第一條、最后一條語句是一樣的，中間部分是要關(guān)注的，把循環(huán)當(dāng)作一個(gè)整體，忽略頭尾循環(huán)判斷的次數(shù)，這兩個(gè)算法的差別就是1與n的區(qū)別。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第30頁。1.5.2

算法性能分析與度量（2）時(shí)間復(fù)雜度（Time

Complexity）

對于算法分析，我們關(guān)心的是算法中語句總的執(zhí)行次數(shù)T（n）是關(guān)于問題規(guī)模n的函數(shù)。T（n）隨n的變化情況并確定T（n）的數(shù)量級。常用“大O表示法”表示：T(n)=O(f(n))。它表示隨著問題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第31頁。函數(shù)的漸近增長：兩個(gè)函數(shù)f(n)和g(n)，如果存在一個(gè)整數(shù)N，使得對于所有的n>N時(shí)，總有f(n)>g(n)，稱f(n)的增長漸近快于g(n)。如C算法、D算法與E算法。1.5.2

算法性能分析與度量當(dāng)n=1,2時(shí)，C算法不如D算法。但當(dāng)n>2時(shí)，C算法優(yōu)于D算法。隨n的增加，算法C比D越來越好。于是我們可以說，當(dāng)輸入數(shù)據(jù)n，只要超過某一數(shù)值N時(shí)，這個(gè)函數(shù)就總是大于另一函數(shù)，我們稱函數(shù)是漸近增長的。當(dāng)n>2時(shí)，即N=3時(shí)，算法D與E的漸近增長是相同的。都記為O（n2）。第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第32頁。推導(dǎo)大O階的方法1）程序運(yùn)行時(shí)間中的常數(shù)用1代替。如運(yùn)行3次，記O(1),運(yùn)行100次，也記為O(1)。2）在大O()函數(shù)中運(yùn)行次數(shù)只取最高階項(xiàng)，并且最高階項(xiàng)的常數(shù)為1。如5n2記O(n2)。一般情況下，隨n的增大，T（n）的增長較慢的算法為最優(yōu)的算法。

按大O階推導(dǎo)方法：A算法f(n)=3,常數(shù)項(xiàng)3次用1代替，記O(1)。 B算法f(n)=2n+3，常數(shù)項(xiàng)3次用1代替，2n的系數(shù)2也改為1，記O（n）C算法f(n)=C(3n+5)，記為O（n）。D算法f(n)=(2n2)，記為O(n2)。E算法f(n)=(2n2+3n+5),記為O(n2)。按最高項(xiàng)，其余忽略不計(jì)。1.5.2

算法性能分析與度量第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第33頁?！纠?-6】在下列三段程序段中，給出原操作x=x+1的時(shí)間復(fù)雜度分析。（1）x=x+1；

程序執(zhí)行1次，其時(shí)間復(fù)雜度為O(1)

稱為常量階；（2）for(i=1;i<=n;i++)//執(zhí)行2n+2次x=x+1; //執(zhí)行n次程序共執(zhí)行3n+2,取最高項(xiàng)，去掉該項(xiàng)的系數(shù)，T(n)=O(n)，稱為線性階；（3）for(i=1;i<=n;i++)//執(zhí)行2n+2次

for(j=1;j<=n;j++)//執(zhí)行n(2n+2)次x=x+1; //執(zhí)行n2次,程序共執(zhí)行3n2+4n+2,只取最高項(xiàng)，去掉該項(xiàng)的系數(shù)，T(n)=O(n2),

稱為平方階。常見的時(shí)間復(fù)雜度：O(1)＜O(log2n)＜O(n)＜O(n2)＜O(n3)＜O(2n)1.5.2

算法性能分析與度量第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第34頁。（3）算法的空間復(fù)雜度空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。算法的存儲(chǔ)空間需求，類似于算法的時(shí)間復(fù)雜度，為算法所需存儲(chǔ)空間的量度，記做：S(n)=O(f(n))其中n為問題的規(guī)模。一個(gè)程序在機(jī)器上執(zhí)行時(shí)，除了需要寄存本身所用的指令，常數(shù)，變量和輸入數(shù)據(jù)以外，還需要一些對數(shù)據(jù)進(jìn)行操作的輔助存儲(chǔ)空間。其中對于輸入數(shù)據(jù)所占的具體存儲(chǔ)量只取決于問題本身，與算法無關(guān)。若算法執(zhí)行時(shí)所需要的輔助空間相對于輸入數(shù)據(jù)量而言是個(gè)常數(shù)，則稱這個(gè)算法為原地工作，輔助空間為O(1)。算法的執(zhí)行時(shí)間的耗費(fèi)和所序的存儲(chǔ)空間的耗費(fèi)兩者是矛盾的，難以兼得。即算法執(zhí)行時(shí)間上的節(jié)省一定是以增加空間存儲(chǔ)為代價(jià)的，反之亦然。常常以算法執(zhí)行時(shí)間做為算法優(yōu)劣的主要衡量指標(biāo)。1.5.2

算法性能分析與度量第1章--數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)全文共38頁，當(dāng)前為第35頁。1.5.2

算法的大致分類本書涵蓋的算法大致可以被分為蠻力算法、分治算法、減治算法、變治算法以及動(dòng)態(tài)規(guī)劃算法等幾大類。蠻力法(BruteForce)