數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 1(合肥工大)

祝同學(xué)們新學(xué)期愉快

學(xué)習(xí)進(jìn)步！祝同學(xué)們

新學(xué)期愉快

學(xué)習(xí)進(jìn)步！華電計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)(DataStructure)教材名稱：

《數(shù)據(jù)結(jié)構(gòu)》王翠茹編著中國(guó)電力出版社任課教師：劉軍工作單位：計(jì)算機(jī)系華電教材科有售華電計(jì)算機(jī)系開設(shè)本課程的必要性以及課程的特點(diǎn)：1.計(jì)算機(jī)學(xué)科綜合性的專業(yè)基礎(chǔ)課之一.2.需要有關(guān)“程序設(shè)計(jì)語(yǔ)言”和“離散數(shù)學(xué)”的知識(shí)作為課程的基礎(chǔ).3.實(shí)踐性較強(qiáng).華電計(jì)算機(jī)系第一章緒論華電計(jì)算機(jī)系1.1課程簡(jiǎn)介1.2基本概念1.3算法及算法評(píng)價(jià)1.4算法語(yǔ)言的說明華電計(jì)算機(jī)系

1.1課程簡(jiǎn)介算法+數(shù)據(jù)結(jié)構(gòu)=程序（Algorithm+Datastructure=Program)程序設(shè)計(jì)：為計(jì)算機(jī)處理問題編寫的一組指令。算法：處理問題的策略。數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型。程序設(shè)計(jì)的實(shí)質(zhì)是數(shù)據(jù)的表示和數(shù)據(jù)處理,為此應(yīng)提出問題的數(shù)學(xué)模型和設(shè)計(jì)相應(yīng)的算法。華電計(jì)算機(jī)系例如1.鋪設(shè)煤氣管道問題

ABCDIHGEF32.844.612.18.756.421.341.167.310.585.698.752.579.2(a)居民區(qū)示意圖ABCDIHGEF32.812.18.721.341.110.579.2(b)鋪設(shè)煤氣管道設(shè)計(jì)圖華電計(jì)算機(jī)系例如2.圖書館的書目檢索問題登錄號(hào)書名作者分類號(hào)………………172832離散數(shù)學(xué)樊映川S01…172833理論力學(xué)羅遠(yuǎn)祥S01…172834高等數(shù)學(xué)華羅庚S01…172835線性代數(shù)灤汝書S02………………書名登錄號(hào)……高等數(shù)學(xué)172832、172834…理論力學(xué)172833…線性代數(shù)172835………作者登錄號(hào)……樊映川172832…華羅庚172834…灤汝書172835………類別登錄號(hào)……L172833…S172832、172834………華電計(jì)算機(jī)系

1.2基本概念數(shù)據(jù)數(shù)據(jù)是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并為計(jì)算機(jī)程序處理的對(duì)象的集合。

數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位，有時(shí)一個(gè)數(shù)據(jù)元素也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)數(shù)據(jù)處理的最小單位。980604劉曄女188010學(xué)號(hào)姓名性別年月日組合項(xiàng)原子項(xiàng)出生日期（學(xué)生情況）華電計(jì)算機(jī)系

1.2基本概念數(shù)據(jù)對(duì)象性質(zhì)相同的數(shù)據(jù)元素的集合。

數(shù)據(jù)的邏輯結(jié)構(gòu)對(duì)數(shù)據(jù)元素之間邏輯關(guān)系的描述。它可以用一個(gè)數(shù)據(jù)元素的集合和定義在這個(gè)集合上的若干關(guān)系來表示。DataStructure=(D,S)D:數(shù)據(jù)元素的集合;S:D上關(guān)系的集合1）集合：集合中任何兩個(gè)結(jié)點(diǎn)之間都沒有邏輯關(guān)系，組織形式松散。華電計(jì)算機(jī)系2）線性結(jié)構(gòu)：元素之間存在著一對(duì)一的關(guān)系。依次排列形成一條“鎖鏈”。3）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系，具有分支、層次特性。4）圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系，元素之間互相纏繞，具有網(wǎng)絡(luò)特性。華電計(jì)算機(jī)系

1.2基本概念

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)及數(shù)據(jù)元素在計(jì)算機(jī)中的表示.1）順序存儲(chǔ)方式（向量存儲(chǔ)）2）鏈?zhǔn)酱鎯?chǔ)方式3）索引存儲(chǔ)方式4）散列存儲(chǔ)方式

數(shù)據(jù)類型是程序設(shè)計(jì)語(yǔ)言中允許的變量種類，一個(gè)值的集合和定義在這個(gè)值上的一組操作。分為兩類：1）原子類型2）結(jié)構(gòu)類型華電計(jì)算機(jī)系

1.2基本概念

抽象數(shù)據(jù)類型一個(gè)數(shù)學(xué)模型和定義在這個(gè)數(shù)學(xué)模型的一組操作。特性數(shù)據(jù)抽象：用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征，其完成的功能以及和外部的接口。數(shù)據(jù)封裝：將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)分離，并對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名華電計(jì)算機(jī)系

例如：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(v1,v2)；初始化：v1,v2的值賦值

DestroyComplex(Z)；銷毀復(fù)數(shù)Z

GetReal(Z,realPart)；得到Z的實(shí)部

GetImag(Z,ImagPart)；得到Z的虛部Add(Z1,Z2,Sum)；復(fù)數(shù)Z1、Z2相加Subtract(Z1,Z2,Difference)；復(fù)數(shù)Z1、Z2相減Multiply(Z1,Z2,Product)；復(fù)數(shù)Z1、Z2相乘}ADTComplex華電計(jì)算機(jī)系

1.2基本概念

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是要研究數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系。具體來說，它包括數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及在這些結(jié)構(gòu)上定義的相應(yīng)的運(yùn)算。按照某種邏輯結(jié)構(gòu)組織的一組數(shù)據(jù)，按一定的存儲(chǔ)方式將它們映射到計(jì)算機(jī)的存儲(chǔ)器中，并且在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，運(yùn)算的結(jié)果保持原來的結(jié)構(gòu)。

結(jié)構(gòu)結(jié)構(gòu)是指同一數(shù)據(jù)對(duì)象中各數(shù)據(jù)元素之間存在的關(guān)系。華電計(jì)算機(jī)系

1.

研究數(shù)據(jù)元素之間的客觀聯(lián)系。

2.

研究具有某種邏輯關(guān)系的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)方式。3.研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的)的基礎(chǔ)上對(duì)數(shù)據(jù)實(shí)施一系列有效的基本操作。

邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程研究的主要內(nèi)容算法華電計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)舉例例1：一系列整數(shù)，我們可以用算術(shù)運(yùn)算“+、-、*、/”等進(jìn)行運(yùn)算，此時(shí)數(shù)據(jù)對(duì)象是整數(shù)集合，那么，數(shù)據(jù)對(duì)象整數(shù)再加上“+、-、*、/”等符號(hào)的運(yùn)算就構(gòu)成了一個(gè)數(shù)據(jù)結(jié)構(gòu)的定義。例2：建立一個(gè)大學(xué)教師檔案，邏輯結(jié)構(gòu)如下圖，數(shù)據(jù)對(duì)象為教師情況的集合，構(gòu)成了一種數(shù)結(jié)構(gòu)，這種數(shù)結(jié)構(gòu)就是其邏輯關(guān)系，教師檔案這個(gè)數(shù)據(jù)對(duì)象再加上查找，刪除，插入等操作就構(gòu)成了一個(gè)數(shù)據(jù)結(jié)構(gòu)的定義。華電計(jì)算機(jī)系計(jì)算機(jī)教研室發(fā)電教研室華電電力系動(dòng)力系計(jì)算機(jī)系…軟件教研室…教師A…………華電計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)課程研究的主要內(nèi)容三個(gè)層次：抽象實(shí)現(xiàn)評(píng)價(jià)主要內(nèi)容可以歸納為三個(gè)層次五個(gè)要素：五個(gè)要素：邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)不同結(jié)構(gòu)的

基本運(yùn)算算法比較及分析華電計(jì)算機(jī)系

1.3算法及算法評(píng)價(jià)

算法概念解決問題的方法和步驟，指為解決一個(gè)或一類問題給出的一個(gè)確定的、有限長(zhǎng)的操作序列。

算法特性1、有窮性2、確定性3、可行性4、有輸入5、有輸出華電計(jì)算機(jī)系

1.3算法及算法評(píng)價(jià)

算法分類1、程序設(shè)計(jì)語(yǔ)言描述的算法2、偽語(yǔ)言算法3、非形式算法（自然語(yǔ)言算法）

算法評(píng)價(jià)1、算法的正確性

2、算法是否易讀、易寫、易改

3、算法執(zhí)行速度

4、算法所占空間

華電計(jì)算機(jī)系假如隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則記作T(n)=O(f(n))，稱T(n)為算法的時(shí)間復(fù)雜性時(shí)間復(fù)雜度頻度統(tǒng)計(jì)法以語(yǔ)句執(zhí)行的次數(shù)的多少作為算法的時(shí)間量度的分析方法稱為頻度統(tǒng)計(jì)法。

一條語(yǔ)句的頻度是指該語(yǔ)句被執(zhí)行的次數(shù)，而整個(gè)算法的頻度是指算法中所有語(yǔ)句的頻度之和。華電計(jì)算機(jī)系例如：1）x=x+1：2）For(i=1;i<=n;i++)x=x+1;

3)For(i=1;i<=n;i++)For(j=1;j<=n;j++)x=x+1；機(jī)器只執(zhí)行一次，則它的頻度為一次，即f（n）=1執(zhí)行時(shí)間復(fù)雜度為O(1)。其語(yǔ)句執(zhí)行n次，頻度為n次，執(zhí)行時(shí)間與n成正比，f（n）=n，復(fù)雜度為O(n）。其語(yǔ)句執(zhí)行n2次，頻度為n2次，執(zhí)行時(shí)間與n2成正比，f（n

）=n2

，復(fù)雜度為O(n2）。華電計(jì)算機(jī)系算法的頻度:

f(n)

=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

4）voidMATRIX(A,B,C,n){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]=C[i][j]+A[i][k]

B[k][j];}}}

--------------------------

n+1

-------------------

n(n+1)

----------------------------------

n2-----------

n2(n+1)

----

n3華電計(jì)算機(jī)系

當(dāng)n→∞時(shí)，有f(n)/g(n)=常數(shù)≠0，則稱函數(shù)f(n)與g(n)同階,或者說，f(n)與g(n)同一個(gè)數(shù)量級(jí)，記作

f(n)=O(g(n))

稱上式為算法的時(shí)間復(fù)雜度,或稱該算法的時(shí)間復(fù)雜度為O(g(n))

。其中,

n為問題的規(guī)模(大小)的量度。算法的時(shí)間復(fù)雜度為O(n3)lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)

=2n→∞n→∞關(guān)于符號(hào)O的的數(shù)學(xué)定義華電計(jì)算機(jī)系假如隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行所需存儲(chǔ)量的增長(zhǎng)率和g(n)的增長(zhǎng)率相同，則記作S(n)=O(g(n))，稱S(n)為算法的空間復(fù)雜性?？臻g復(fù)雜度算法的存儲(chǔ)空間1.輸入數(shù)據(jù)所占的空間2.程序本身所占的空間3.輔助變量所占的空間華電計(jì)算機(jī)系1.4、算法語(yǔ)言的說明1.采用自然語(yǔ)言來描述

(1)M除以N，將余數(shù)送中間變量R；(2)測(cè)試余數(shù)R是否等于零？

a)若R等于零，求得的最大公因子為當(dāng)前N

的值,算法到此結(jié)束。

b)若R不等于零，將N送入M，將R送N,重復(fù)算法的(1)和(2)。問題：求兩個(gè)正整數(shù)M與N的最大公因子。華電計(jì)算機(jī)系2.采用程序流程圖的形式來描述開始M除以N的余數(shù)送R余數(shù)R為0否？輸出N的值結(jié)束將N送M將R送Nnoyes華電計(jì)算機(jī)系3.采用某種具體程序語(yǔ)言來描述COMFACTOR(M,N)

intM,N;{

intR;while(1){R=M%N;if(R==0)returnN;M=N;N=R;

}}

用C語(yǔ)言描述的求兩個(gè)正整數(shù)最大公因子的算法(C函數(shù))華電計(jì)算機(jī)系類C語(yǔ)言4.設(shè)計(jì)一種既脫離某種具體的程序設(shè)計(jì)語(yǔ)言，又具有各種程序設(shè)計(jì)語(yǔ)言的共同特點(diǎn)的形式化語(yǔ)言來描述華電計(jì)算機(jī)系類C語(yǔ)言簡(jiǎn)介一、算法的格式Pascal語(yǔ)言PROGRAM程序名(input,output);說明部分；BEGIN語(yǔ)句串；END.C語(yǔ)言函數(shù)名(參數(shù)表)參數(shù)說明；{說明部分；語(yǔ)句串；}procedure過程名(參數(shù)表)說明部分；begin語(yǔ)句串；End;華電計(jì)算機(jī)系北航計(jì)算機(jī)系類C語(yǔ)言的特點(diǎn)1、算法中使用的輔助變量可以不做變量說明(函數(shù)類型及函數(shù)參數(shù)需要說明類型)，重要的變量須在注解中說明其類型和作用。2、基本操作的算法都用以下形式的函數(shù)描述。

函數(shù)類型

函數(shù)名(函數(shù)參數(shù)表）

{//算法說明

語(yǔ)句序列;

}//函數(shù)名華電計(jì)算機(jī)系北航計(jì)算機(jī)系類C語(yǔ)言的特點(diǎn)3、在函數(shù)中除了值調(diào)用方式之外，（類似于pascal中的形參調(diào)用），增添了C++語(yǔ)言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)，引用參數(shù)能被函數(shù)本身更新值，可以作為輸出數(shù)據(jù)的管道。華電計(jì)算機(jī)系4、內(nèi)存的動(dòng)態(tài)分配與釋放

使用new和delete動(dòng)態(tài)分配和釋放內(nèi)存空間。分配空間指針變量=new數(shù)據(jù)類型；釋放空間delete指針變量；5.循環(huán)語(yǔ)句(三種)while語(yǔ)句

while循環(huán)條件

語(yǔ)句;

do-while語(yǔ)句do{

語(yǔ)句序列}while循環(huán)條件

for語(yǔ)句

for(賦值表達(dá)式序列；條件；修改表達(dá)式序列)語(yǔ)句；

華電計(jì)算機(jī)系

函數(shù)結(jié)束語(yǔ)句

return表達(dá)式；

return；case結(jié)束語(yǔ)句break；異常結(jié)束語(yǔ)句exit(異常代碼)；開關(guān)語(yǔ)句1switch(表達(dá)式){case值1：語(yǔ)句序列1；break；

case值2：語(yǔ)句序列2；break；