數(shù)據(jù)結(jié)構(gòu)第一張幻燈片第1頁，課件共49頁，創(chuàng)作于2023年2月先修課程C語言高等數(shù)學(xué)離散數(shù)學(xué)第2頁，課件共49頁，創(chuàng)作于2023年2月學(xué)時(shí)及安排學(xué)時(shí)：17×4學(xué)時(shí)實(shí)驗(yàn)：6個(gè)實(shí)驗(yàn)考試類型：考試（筆試）成績(jī)=試卷成績(jī)+平時(shí)成績(jī)作業(yè)：周二中午之前交到教研室第3頁，課件共49頁，創(chuàng)作于2023年2月公共郵箱用戶名：datexinxi@163.com密碼：xinxidate第4頁，課件共49頁，創(chuàng)作于2023年2月第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析第5頁，課件共49頁，創(chuàng)作于2023年2月1.1什么是數(shù)據(jù)結(jié)構(gòu)NiklausWirth

Algorithm+DateStructures=Programs

算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編制一組指令集算法：處理問題的策略數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型全球氣象預(yù)報(bào)

球面坐標(biāo)系下的一般環(huán)流模式方程數(shù)值計(jì)算的程序設(shè)計(jì)問題第6頁，課件共49頁，創(chuàng)作于2023年2月1、求一組（n個(gè)）整數(shù)中的最大值算法?

基本操作是比較兩個(gè)數(shù)的大小模型？整數(shù)2、計(jì)算機(jī)對(duì)弈算法？對(duì)弈的規(guī)則和策略模型？棋盤，棋子3、足協(xié)的數(shù)據(jù)庫算法？需要管理的項(xiàng)目？如何管理？用戶界面模型？表格，數(shù)據(jù)庫第7頁，課件共49頁，創(chuàng)作于2023年2月概括的說數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。第8頁，課件共49頁，創(chuàng)作于2023年2月1.2基本概念和術(shù)語一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)

所有能被輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)處理的所有這些符號(hào)的集合，可見，數(shù)據(jù)是計(jì)算機(jī)操作的對(duì)象的總稱，是計(jì)算機(jī)處理的信息的載體，是信息的某一種特定的符號(hào)表示形式。第9頁，課件共49頁，創(chuàng)作于2023年2月數(shù)據(jù)元素?cái)?shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合例如：運(yùn)動(dòng)員(數(shù)據(jù)元素)姓名俱樂部名稱出生日期參加日期職務(wù)業(yè)績(jī)年月日組合項(xiàng)第10頁，課件共49頁，創(chuàng)作于2023年2月數(shù)據(jù)對(duì)象

是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集例如，整數(shù)數(shù)據(jù)對(duì)象:N={0,±1,±2,…}，字母字符數(shù)據(jù)對(duì)象:C={‘A’,‘B’,…

‘Z’,}第11頁，課件共49頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。例如，一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示，

457834292610—a1(4578),a2(3429),a3(2610)

在a1,a2,a3之間存在“次序”關(guān)系

<a1,a2>,<a2,a3>4578,3429,2610a1,a2,a33429,4578,2610a2,a1,a3

≠是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合第12頁，課件共49頁，創(chuàng)作于2023年2月又例，2行3列的矩陣{a1,a2,a3,a4,a5,a6}行的次序關(guān)系

row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序關(guān)系

col={<a1,a4>,<a2,a5>,<a3,a6>}a1a2a3a4a5a6

a1,a2,a3a4,a5,a6

a1,a2,a3a5,a4,a6

≠第13頁，課件共49頁，創(chuàng)作于2023年2月再例，一維數(shù)組{a1,a2,a3,a4,a5,a6}中存在次序關(guān)系:

{<ai,ai+1>|i=1,2,3,4,5}第14頁，課件共49頁，創(chuàng)作于2023年2月數(shù)據(jù)的邏輯結(jié)構(gòu)可以歸結(jié)為以下四類：

(1)線性結(jié)構(gòu)

(2)樹形結(jié)構(gòu)

(3)圖狀結(jié)構(gòu)

(網(wǎng)狀結(jié)構(gòu))(4)集合結(jié)構(gòu)第15頁，課件共49頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Date_Structures=(D,S)

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

S是D上關(guān)系的有限集。例如：由a1,a2,a3,a4,a5,a6構(gòu)成的矩陣定義矩陣是一種數(shù)據(jù)結(jié)構(gòu)E={D,S}D={a1,a2,a3,a4,a5,a6}S={<ai,ai+1>|i=1,2,3,4,5}第16頁，課件共49頁，創(chuàng)作于2023年2月數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

——數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映像)

——數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)映像包括數(shù)據(jù)元素的映像和關(guān)系的映像數(shù)據(jù)元素的映像方法：

用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素

(321)10=(501)8=(101000001)2A=(101)8=(001000001)2第17頁，課件共49頁，創(chuàng)作于2023年2月關(guān)系的映像方法：（表示<x,y>的方法）

順序映像：以數(shù)據(jù)元素在存儲(chǔ)器之間一個(gè)固定的相對(duì)位置的關(guān)系來表示數(shù)據(jù)元素的關(guān)系y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C。而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。a1a2a3a4a5a6<a1,a2><a1,a3><a1,a4><a3,a5><a3,a6>有序?qū)υ谟?jì)算機(jī)中有兩種表示方法：順序映像和鏈?zhǔn)接诚竦?8頁，課件共49頁，創(chuàng)作于2023年2月（a1,a2,a3）a1a2a3第19頁，課件共49頁，創(chuàng)作于2023年2月鏈?zhǔn)接诚裼址Q非順序映像，在整個(gè)結(jié)構(gòu)中x和y的存儲(chǔ)位置之間沒有固定的關(guān)系，就是說它們的存儲(chǔ)位置是隨意的。以附加信息(指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置。x元素的存儲(chǔ)映像是一個(gè)結(jié)點(diǎn)，包含兩部分信息，其中一部分信息是數(shù)據(jù)元素x，另一部分信息是指向后繼元素的指針。<x,y>yx第20頁，課件共49頁，創(chuàng)作于2023年2月在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述之。例如，以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語言中提供的整數(shù)數(shù)組類型,定義整數(shù)為：

typedefintLong_int[3]第21頁，課件共49頁，創(chuàng)作于2023年2月三、數(shù)據(jù)類型在用高級(jí)程序語言編寫的程序中,必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明他們所屬的數(shù)據(jù)類型。每個(gè)類型明顯或者隱含的規(guī)定了在程序制定期間它的變量或者表達(dá)式所明確取值的范圍以及允許進(jìn)行的操作。數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。第22頁，課件共49頁，創(chuàng)作于2023年2月抽象數(shù)據(jù)類型(AbstractDataType,簡(jiǎn)稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。ADT有兩個(gè)重要特征：

數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征，其所能完成的功能以及它和外部用戶的接口(即外界使用它的方法)

數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)規(guī)范。第23頁，課件共49頁，創(chuàng)作于2023年2月例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義

ADTComplex{

數(shù)據(jù)對(duì)象：D={e1,e2|e1,e2∈RealSet}

數(shù)據(jù)關(guān)系:R1={<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分，e2是復(fù)數(shù)的虛數(shù)部分}

基本操作：

InitComplex（&Z,v1,v2）操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值

DestroyComplex（&Z）操作結(jié)果：復(fù)數(shù)Z被銷毀

第24頁，課件共49頁，創(chuàng)作于2023年2月GetReal（Z，&realPart）初始條件：復(fù)數(shù)已存在操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部GetImage（Z,&ImagPart）初始條件：復(fù)數(shù)已存在操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的實(shí)部Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值}ADTComplex假設(shè)：z1,z2是上述定義的復(fù)數(shù)，則Add(z1,z2,z3)操作的結(jié)果將得到第25頁，課件共49頁，創(chuàng)作于2023年2月抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用(D,S,P)三元組表示其中，D是數(shù)據(jù)對(duì)象

S是D上的關(guān)系集

P是對(duì)D的基本操作集第26頁，課件共49頁，創(chuàng)作于2023年2月1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。第27頁，課件共49頁，創(chuàng)作于2023年2月1.4算法和算法分析一、算法算法是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：

1、有窮性2、確定性3、可行性

4、有輸入5、有輸出第28頁，課件共49頁，創(chuàng)作于2023年2月1、有窮性

對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即:算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；2、確定性

對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有明確的規(guī)定，使算法的執(zhí)行者或閱讀者能明確其含義及如何執(zhí)行，并且在任何條件下，算法都只有一條執(zhí)行路徑；第29頁，課件共49頁，創(chuàng)作于2023年2月3、可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4、有輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中；5、有輸出它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。第30頁，課件共49頁，創(chuàng)作于2023年2月作業(yè)描述算法的特征。第31頁，課件共49頁，創(chuàng)作于2023年2月課前復(fù)習(xí)數(shù)據(jù)

所有能被輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)處理的所有這些符號(hào)的集合，數(shù)據(jù)元素?cái)?shù)據(jù)中的一個(gè)“個(gè)體”，數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)中討論的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個(gè)子集數(shù)據(jù)結(jié)構(gòu)

是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)的邏輯結(jié)構(gòu)可以歸結(jié)為以下四類：

(1)線性結(jié)構(gòu)

(2)樹形結(jié)構(gòu)

(3)圖狀結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu))(4)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Date_Structures=(D,S)

其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。抽象數(shù)據(jù)類型可用(D,S,P)三元組表示其中，D是數(shù)據(jù)對(duì)象S是D上的關(guān)系集P是對(duì)D的基本操作集算法滿足五個(gè)特性：1、有窮性2、確定性3、可行性4、有輸入5、有輸出第32頁，課件共49頁，創(chuàng)作于2023年2月二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1、正確性2、可讀性3、健壯性4、高效率與低存儲(chǔ)量需求第33頁，課件共49頁，創(chuàng)作于2023年2月1、正確性首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：

a.程序中不含語法錯(cuò)誤；

b.程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；

c.程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。

d.程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果。第34頁，課件共49頁，創(chuàng)作于2023年2月2、可讀性算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難懂的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。第35頁，課件共49頁，創(chuàng)作于2023年2月3、健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)淖龀龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以使在更高的抽象層次上進(jìn)行處理。第36頁，課件共49頁，創(chuàng)作于2023年2月4、高效率和低存儲(chǔ)量需求通常算法的效率指的是算法執(zhí)行的時(shí)間，存儲(chǔ)量指的是算法執(zhí)行過程中所需要的最大存儲(chǔ)空間，兩者都和問題的規(guī)模有關(guān)。第37頁，課件共49頁，創(chuàng)作于2023年2月三、算法效率的衡量方法和準(zhǔn)則

通常有兩種衡量算法效率的方法：

事后統(tǒng)計(jì)法缺點(diǎn)：1、必須執(zhí)行程序

2、其它因素掩蓋算法本質(zhì)

事先分析估算法

和算法執(zhí)行時(shí)間有關(guān)的因素：1、算法選用的策略2、問題的規(guī)模3、編寫程序的語言4、編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5、計(jì)算機(jī)執(zhí)行指令的速度第38頁，課件共49頁，創(chuàng)作于2023年2月一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模(通常用整數(shù)n表示)，或者說，它是問題規(guī)模的函數(shù)。第39頁，課件共49頁，創(chuàng)作于2023年2月假如，隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間T(n)的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記為：

T(n)=O(f(n))

稱T(n)為算法的(漸進(jìn))時(shí)間復(fù)雜度。第40頁，課件共49頁，創(chuàng)作于2023年2月算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間=

∑原操作(i)的執(zhí)行次數(shù)×每個(gè)原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間與原操作的執(zhí)行次數(shù)之和成正比

從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。第41頁，課件共49頁，創(chuàng)作于2023年2月例一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]+=a[i,k]*b[k,j];}

基本操作：乘法操作時(shí)間復(fù)雜度：O（n3）第42頁，課件共49頁，創(chuàng)作于2023年2月例二

voidselect_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小到大有序的整數(shù)序列

for(i=0;i<n-1;++i){j=i;for(k=i+1;k<n;++k)if(a[k]<a[j])j=k;if(j≠i)a[j]←→a[i];}}//select_sort

基本操作：乘法操作時(shí)間復(fù)雜度：O（n2）第43頁，課件共49頁，創(chuàng)作于2023年2月例三voidbubble_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列

for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<=i;++j)if(a[j]>a