數(shù)據(jù)結構的概述1.1數(shù)據(jù)結構模塊一緒論課程思政點（找視頻）BAT是中國三大互聯(lián)網(wǎng)公司的合稱，分別為百度公司（Baidu）、阿里巴巴集團（Alibaba）、騰訊公司（Tencent）。百度擁有數(shù)萬名研發(fā)工程師，這是中國乃至全球最為優(yōu)秀的技術團隊。這支隊伍掌握著世界上最為先進的搜索引擎技術，使百度成為中國掌握世界尖端科學核心技術的中國高科技企業(yè)，也使中國成為美國、俄羅斯、和韓國之外，全球僅有的4個擁有搜索引擎核心技術的國家之一。阿里巴巴是全球最大的零售交易平臺，它以技術驅動，包含數(shù)字商業(yè)、金融科技、智慧物流、云計算、人地關系文化娛樂等場景的平臺，服務數(shù)以億計的消費者和數(shù)千萬的中小企業(yè)。阿里巴巴致力于讓天下沒有難做的生意，開拓數(shù)字經(jīng)濟時代的商業(yè)基礎設施，助力消費市場繁榮，推動各行各業(yè)走向數(shù)字化、智能化。騰訊是中國最大的互聯(lián)網(wǎng)綜合服務提供商之一，也是中國服務用戶最多的互聯(lián)網(wǎng)企業(yè)之一。它的服務包括：社交和通信服務QQ及微信/WeChat、社交網(wǎng)絡平臺QQ空間、騰訊游戲旗下QQ游戲平臺、門戶網(wǎng)站騰訊網(wǎng)、騰訊新聞客戶端和網(wǎng)絡視頻服務騰訊視頻等。BAT已經(jīng)成為中國最大的三家互聯(lián)網(wǎng)公司。中國互聯(lián)網(wǎng)發(fā)展了20年，現(xiàn)在形成了三足鼎立的格局，三家巨頭各自形成自己的體系和戰(zhàn)略規(guī)劃，分別掌握著中國的信息型數(shù)據(jù)、交易型數(shù)據(jù)、關系型數(shù)據(jù)。這些數(shù)據(jù)遠遠超出數(shù)值型數(shù)據(jù)的范圍，很多為非數(shù)值型數(shù)據(jù)的處理。那么研究非數(shù)值形數(shù)據(jù)離不開數(shù)據(jù)結構。1.1.1什么是數(shù)據(jù)結構·數(shù)據(jù)結構的重要性谷歌擁有高性能的計算機硬件系統(tǒng)更重要的是設計了優(yōu)秀的圍棋軟件什么是軟件？尼古拉斯·沃斯瑞士圖靈獎獲得者軟件=程序+文檔算法+數(shù)據(jù)結構=程序懂得數(shù)據(jù)結構+好的算法=

高質量程序唐納德·克努特美國圖靈獎獲得者數(shù)據(jù)結構教材的多數(shù)內(nèi)容來源此書數(shù)據(jù)結構=計算機程序設計藝術1968年克努特教授開創(chuàng)了數(shù)據(jù)結構的最初體系，闡述

數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。數(shù)據(jù)結構的重要性

學好數(shù)據(jù)結構=編寫高質量的程序

“數(shù)據(jù)結構”在計算機科學中是一門綜合性的專業(yè)基礎課，是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程，其內(nèi)容不僅是一般程序設計(特別是非數(shù)值性程序設計)的基礎，而且是設計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎。什么是數(shù)據(jù)結構？·早期的計算機主要處理數(shù)值計算·現(xiàn)在更多地應用于控制、管理等非數(shù)值處理領域·計算機處理的數(shù)據(jù)也由純粹的數(shù)值發(fā)展到字符、表格、圖形、圖象、聲音等具有一定結構的數(shù)據(jù)·處理的數(shù)據(jù)量也越來越大，這就給程序設計帶來一個問題：應如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關系（結構）例1：電話號碼查詢問題順序存儲結構索引存儲結構例2：人機對弈1997年IBM“深藍”計算機戰(zhàn)勝世界棋王卡斯帕羅夫2006年浪潮“天梭”計算機戰(zhàn)勝柳大華等五位中國象棋大師例2：人機對弈2016年谷歌AlphaGo4：1戰(zhàn)勝世界圍棋冠軍李世石2017年谷歌AlphaGo3：0戰(zhàn)勝世界圍棋冠軍柯潔例3：教學計劃編排問題課程編號課程名稱先修課程C1計算機導論無C2數(shù)據(jù)結構C1、C4C3網(wǎng)頁制作C1C4C語言程序設計C1C5AC2、C3、C4C6JavascriptC3C7數(shù)據(jù)庫C2、C9C8JavaC4C9軟件工程C2

拓撲排序方法數(shù)據(jù)結構定義：數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象、對象之間的關系以及在此之上的一系列操作的學科。

討論數(shù)據(jù)結構的目的是為了在計算機中實現(xiàn)其所需的各種操作?；镜牟僮髦饕幸韵聨追N：

插入、刪除、修改、查找、排序1.1.2基本概念和術語

描述客觀事物的符號，能夠被計算機識別、存儲和加工處理。比如，我們現(xiàn)在離不開的“百度”，其中有網(wǎng)頁、音樂、圖片、視頻等分類，音樂就是音頻數(shù)據(jù)，圖片是圖像數(shù)據(jù)，網(wǎng)頁則包括數(shù)值、文字、圖片等多種數(shù)據(jù)。我們這里所說的數(shù)據(jù)，其實就是具備以下兩個條件的符號：①可以輸入到計算機；②能被計算機程序處理。1.數(shù)據(jù)1.1.2基本概念和術語2.數(shù)據(jù)元素

一個數(shù)據(jù)元素是由用來描述一個特定事物的名稱、數(shù)量、特征、性質的一組相關信息組成的，在計算機中通常把數(shù)據(jù)元素作為一個整體進行考慮和處理。是數(shù)據(jù)的基本單位，有時也稱為元素、結點、頂點或記錄。例如，學生的信息管理1.1.2基本概念和術語3.數(shù)據(jù)項是數(shù)據(jù)最小單位，有時也稱為字段、域或屬性。學號姓名性別專業(yè)年級……130102彭麗姣女信息與計算科學13級……130103李麗女軟件工程13級……130104張漢濤男信息與計算科學13級……130106高媛女計算機應用13級……………………每一個學生的所有信息形成了一個數(shù)據(jù)元素，通?？梢苑Q為一個學生記錄。學生的學號、姓名、性別、專業(yè)等就是其數(shù)據(jù)項(或稱字段)。討論問題時，數(shù)據(jù)元素才是數(shù)據(jù)結構中建立數(shù)學模型的著眼點。例如，學生的信息管理1.1.2基本概念和術語4.數(shù)據(jù)對象性質相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。在現(xiàn)實世界中，數(shù)據(jù)元素之間不是孤立的、雜亂無章的，它們之間或多或少存在著某一些關系。我們把這些關系稱為結構。相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。也就是說，數(shù)據(jù)結構研究的是帶結構的數(shù)據(jù)元素的集合。5.結構6.數(shù)據(jù)結構數(shù)據(jù)（邏輯）結構的形式定義數(shù)據(jù)結構是一個二元組

Data_Structure=(D,R)其中: D

是數(shù)據(jù)元素的有限集，

R

是D上關系的有限集。例如:一維數(shù)組{a1,a2,a3,a4,a5,a6}的形式定義

D={a1,a2,a3,a4,a5,a6}

R={<ai,ai+1>|i=1,2,3,4,5}邏輯結構：數(shù)據(jù)結構定義中所說的“元素之間關系”即是指數(shù)據(jù)元素之間的邏輯關系。171.1.2基本概念和術語1.1.2基本概念和術語研究數(shù)據(jù)元素及其關系在計算機中的具體存儲形式，也就是數(shù)據(jù)的存儲結構，或者稱為物理結構。7.存儲結構四種基本邏輯結構19【集合】——數(shù)據(jù)元素間除了“同屬于一個集合”外，無其他關系?！揪€性結構】——

1對1的關系比如線性表、棧、隊列?！緲湫谓Y構】——

1對多的關系比如樹?！緢D形結構】——多對多的關系比如圖。1.2基本概念和術語數(shù)據(jù)的存儲結構（又稱物理結構）

物理結構是指數(shù)據(jù)的邏輯結構在計算機中的存儲形式，是邏輯結構在計算機中的實現(xiàn)。包括數(shù)據(jù)元素的存儲及元素之間關系的存儲。順序存儲結構鏈式存儲結構數(shù)據(jù)的存儲結構要能正確反映數(shù)據(jù)元素之間的邏輯關系。如何存儲數(shù)據(jù)元素之間的關系，是實現(xiàn)物理結構的重點和難點。

數(shù)據(jù)元素的存儲結構形式常見有兩種：1.1.2

基本概念和術語

順序存儲結構是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元中，其數(shù)據(jù)元素之間的邏輯關系和物理位置一致。

S=（a1,a2,a3,……,an）順序存儲結構內(nèi)存：1.1.2

基本概念和術語鏈式存儲結構

鏈式存儲結構是把數(shù)據(jù)元素存放在任意的存儲單元中，這組存儲單元可以連續(xù)也可以不連續(xù)。其數(shù)據(jù)元素之間的物理位置不能反映其邏輯關系，用指針來反映數(shù)據(jù)元素之間的邏輯關系。a1a2an

^…HS=（a1,a2,a3,……,an）1.1.2

基本概念和術語數(shù)據(jù)結構主要研究數(shù)據(jù)的邏輯結構、存儲結構和運算三方面的內(nèi)容?！ね贿壿嫿Y構采用不同存儲結構，得到的是不同的數(shù)據(jù)結構；例如：線性表采用順序存儲，我們稱之為順序表；采用鏈式存儲是則稱之為鏈表?！ね贿壿嫿Y構定義不同的運算也會導致不同的數(shù)據(jù)結構；例如：若限制線性表的插入、刪除在表一端進行，則該結構稱為棧；

若限定在一端插入，另一端刪除稱為隊列。·運算的定義取決于數(shù)據(jù)邏輯結構?！み\算的實現(xiàn)取決于數(shù)據(jù)存儲結構。抽象數(shù)據(jù)類型的表示與實現(xiàn)1.2數(shù)據(jù)結構模塊一緒論1.2.1數(shù)據(jù)類型最早出現(xiàn)于高級語言中，是指一組性質相同的值的集合及定義在集合上的一些操作的總稱。在高級語言中，每個變量、常量、表達式都有各自的類型。類型用來說明變量或表達式的取值范圍和允許施加的操作。25

我們已熟悉C/C++語言常用的基本數(shù)據(jù)類型包括字符型、整型、實型、指針類型等。這些數(shù)據(jù)類型的值是不可分割的?，F(xiàn)實世界最終可以用這些基本數(shù)據(jù)類型來表示。另一類是結構類型。結構類型的數(shù)據(jù)的值是由若干成分按某種結構組成的，因此是可以分解的。數(shù)組和結構體是C/C—-+語言提供的兩種非常有效的組織數(shù)據(jù)的機制。26例如，C語言中inta,b;規(guī)定了變量a、b在內(nèi)存中所占的字節(jié)數(shù)、取值范圍以及施加于a、b上的運算。在使用int類型時，既不需要了解在計算機內(nèi)部是如何表示的，也不需要知道其操作如何實現(xiàn)。如a?+?b，設計者僅僅關注其“數(shù)學上求和”的抽象特征。高級語言中的數(shù)據(jù)類型，其操作是需要通過編譯器或者解釋器的轉化，由底層的匯編語言或者機器語言的數(shù)據(jù)類型來實現(xiàn)，而底層的數(shù)據(jù)類型的操作則是通過指令系統(tǒng)，由電路系統(tǒng)來完成的。因此，引入數(shù)據(jù)類型的目的在于，對于底層的硬件而言，數(shù)據(jù)類型是解釋計算機內(nèi)存中信息含義的一種手段。而對于程序設計者來說，也就是使用數(shù)據(jù)類型的用戶來說，它實際上是信息的屏蔽。將用戶不必要了解的所有的細節(jié)都封裝在類型中，這樣子用戶在使用數(shù)據(jù)類型時，只要把注意力放在數(shù)據(jù)類型的抽象特性上即可。281.2.2抽象數(shù)據(jù)類型1.數(shù)據(jù)抽象抽象可以被理解為一種機制，其實質是抽取共同的和實質的東西，忽略非本質的細節(jié)。抽象可以使我們的求解問題過程以自頂向下的方式分步進行：首先考慮問題的最主要方面，然后再逐步細化，進一步考慮問題的某些細節(jié)，并最終實現(xiàn)之。292.抽象數(shù)據(jù)類型（AbstractDataType,ADT)抽象數(shù)據(jù)類型，簡稱ADT，是一個數(shù)學模型以及定義在該模型上的一組操作。所謂抽象的本質就是抽取數(shù)據(jù)類型的數(shù)學特性，也就是說，Adt的定義僅取決于它的一組邏輯特性，與其在計算機內(nèi)部的表示和實現(xiàn)無關。不論其內(nèi)部的結構如何變化，只要它的數(shù)學特性不變，就不會影響其外部的使用。303.抽象數(shù)據(jù)類型分類按值的不同性質，抽象數(shù)據(jù)類型也可分為原子類型和結構類型，其中結構類型還可以再細分為固定聚合類型和可變聚合類型。固定聚合類型是由確定數(shù)目的成分按某種結構組成。例如，二維平面中的點可以分別對應X軸和Y軸坐標的兩個實數(shù)，它們按照固定的次序構成。可變聚合類型構成成分的數(shù)目是不確定的、可變的。例如集合這樣的抽象數(shù)據(jù)類型，其中的元素個數(shù)是可變的。31抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結構的定義。用三元組描述如下: ADT=(D,S,P)

其中：D是數(shù)據(jù)對象，S是D上的關系的集合，P是對D的基本操作的集合。

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

{

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

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

基本操作：<基本操作的定義> }ADT

抽象數(shù)據(jù)類型名32抽象數(shù)據(jù)類型表示的示例ADT

抽象數(shù)據(jù)類型名{Data

數(shù)據(jù)對象的定義 數(shù)據(jù)元素之間邏輯關系的定義Operation

操作1

初始條件 操作結果描述 操作2 ……

操作n ……}endADT33ADTComplex{ D={r1,r2|r1,r2都是實數(shù)} S={<r1,r2>|

r1是實部，r2是虛部} assign(&C,v1,v2)

初始條件：復數(shù)C已存在 操作結果：構造復數(shù)C，r1,r2分別

被賦以參數(shù)v1,v2的值。

destroy(&C)

初始條件：復數(shù)C已存在 操作結果：復數(shù)C被銷毀。

……}ADTComplex3.抽象數(shù)據(jù)類型的表示和實現(xiàn)表示和實現(xiàn)抽象數(shù)據(jù)類型時可以使用固有的數(shù)據(jù)類型（如整型、實型、字符型等）。抽象數(shù)據(jù)類型有些類似C語言中的結構（struct）類型，但增加了相關的服務。我們采用類C語言（介于偽代碼和C語言之間）作為描述工具。不拘泥于C語言的細節(jié)又容易實現(xiàn)。注意：上機時仍要用具體的編程語言實現(xiàn)，如C或C++。34算法1.3數(shù)據(jù)結構模塊一緒論田忌賽馬秦九韶算法楊輝《詳解九章算法》（楊輝三角）張邱建算經(jīng)（百雞百錢）課程思政點：1.3算法及其評價用C語言編寫程序計算1?+?2?+?3?+?4?+?…?+?100，大家都會寫出這樣一段代碼：這是最簡單的一個計算機程序，它就是一種算法。這個算法效率怎樣呢?實際上對于這個問題，據(jù)說高斯在上小學時就給出了一個高效算法：sum?=1?+??2??+??3??+…+100sum?=?100+?99?+?98?+…+12*sum=?101?+?101?+?101?+…+?101

共100個101所以sum=5050。

main(){ inti,sum=0,n=100;

for(i=1;i<=n;i++) sum=sum+i; printf(″%d″,sum);

}

main(){ inti,sum=0,n=100;

sum=(1+100)*100/2; printf(″%d″,sum);

}1.3算法及其評價·有窮性：有限步驟之內(nèi)完成,不能形成無窮循環(huán)。

算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法的5大特性1算法的基本概念·確定性：每一個步驟必須有確定含義,無二義性?！た尚行裕翰僮骺赏ㄟ^已實現(xiàn)的基本運算執(zhí)行有限次完成?！ぽ斎耄河?個或多個輸入。·輸出：至少有一個或多個輸出。算法和程序的區(qū)別：算法代表了對問題的求解過程，程序則是算法在計算機上的特定的實現(xiàn)，算法若用程序設計語言來描述，則是一個程序。1.3算法及其評價2算法的描述·使用自然語言優(yōu)點是簡單且便于人們對算法的閱讀，缺點是不夠嚴謹，容易產(chǎn)生二義性。·使用流程圖算法描述工具特點是描述過程簡潔、明了。計算表達式1的值表達式2執(zhí)行語句計算表達式3的值真假1.3算法及其評價2算法的描述·使用某種程序設計語言（c語言、c++語言、java語言）符合嚴格的語法定義，常常需要注釋才能使人看明白。·使用一種偽語言（類pascal、類c、類java）以某種程序設計語言為基礎，對其略加改造而形成的一種“非正規(guī)”的語言。后期學習采用C語言作為算法描述工具。1.3算法及其評價3算法的設計要求·正確性算法的執(zhí)行結果應當滿足預先規(guī)定的功能和性能要求?！た勺x性算法要轉換成計算機可執(zhí)行的程序，同時必須可以供他人使用。所以一個算法應當思路清晰，層次分明，簡單明了，易讀易懂。··健壯性當輸入的數(shù)據(jù)不符合要求時，算法應能判斷數(shù)據(jù)的非法性，并能進行適當?shù)奶幚??！じ咝运惴ǖ男适侵杆惴▓?zhí)行的時間和占用的存儲空間。如果對于同一個問題有多個算法可供選擇，應盡可能選擇執(zhí)行時間短、占用存儲空間少的算法?！?.3算法及其評價4算法的評價用C語言編寫程序計算1?+?2?+?3?+?4?+?…?+?100

main(){ inti,sum=0,n=100;

for(i=1;i<=n;i++) sum=sum+i; printf(″%d″,sum);

}

main(){ inti,sum=0,n=100;

sum=(1+100)*100/2; printf(″%d″,sum);

}一個算法首先要具有正確性，然后是可讀性和健壯性。在具備上述三個條件后，就應考慮算法的效率問題，即算法的時間效率和空間效率。算法效率的度量事后統(tǒng)計方法通過設計好的測試程序和數(shù)據(jù)，利用計算機測量其運行時間。缺陷：需要先編寫程序；和計算機軟硬件相關；和測試數(shù)據(jù)相關。431.3算法及其評價4算法的評價事前分析估算方法（我們的選擇）依據(jù)統(tǒng)計方法對算法進行估算。m=f(n)，m是語句總的執(zhí)行次數(shù)，n是輸入的規(guī)模。和問題輸入規(guī)模相關，獨立于程序設計語言和計算機軟硬件算法效率的度量1.3算法及其評價4算法的評價1.3算法及其評價4算法的評價（1）時間效率算法運行時所需時間的多少。影響算法運行所需時間的因素：·策略問題的規(guī)?！鴮懗绦虻恼Z言·編譯程序所生成目標代碼的質量·機器執(zhí)行指令的速度結論：不能用實際的時間來考量，應以算法中基本操作重復執(zhí)行的次數(shù)來考量?！に惴ú捎玫姆椒?.3算法及其評價4算法的評價（1）時間效率算法時間復雜度算法中基本操作重復執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。記作：T(n)?=?O(f(n))時間復雜度一般不是算法的精確執(zhí)行次數(shù)，而是估算的數(shù)量級。1.3算法及其評價4算法的評價下面給出推導大O方法。第一步，找到原操作的執(zhí)行次數(shù)。第二步，用常數(shù)1取代運行時間中的所有加法常數(shù)。第三步，在修改后的執(zhí)行次數(shù)中，只保留最高階項。第四步，如果最高階項存在與這個項相乘的常數(shù)，則去掉這個常數(shù)。這樣就可得到大O階。

(1)順序結構的時間復雜度。

inti,sum=0,n=100;/*執(zhí)行1次*/sum=(1+100)*100/2; /*執(zhí)行1次*/printf(″%d″,sum); /*執(zhí)行1次*/這個算法的運行次數(shù)為f(n)?=?3。

所以T(n)=O(1)

順序結構、分支結構的程序，不管代碼有多少行，執(zhí)行次數(shù)不會隨著n的變化而發(fā)生變化，它與問題規(guī)模n的大小無關，執(zhí)行次數(shù)是恒定的。1.3算法及其評價4算法的評價(2)單循環(huán)結構的時間復雜度。

for(i=1;i<n;i++) /*執(zhí)行n+1次*/sum=sum+i; /*原操作執(zhí)行n次*/其時間復