數(shù)據(jù)結構-合肥工業(yè)大學 1(合肥工大)

祝同學們新學期愉快

學習進步！祝同學們

新學期愉快

學習進步！華電計算機系數(shù)據(jù)結構(DataStructure)教材名稱：

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

1.1課程簡介算法+數(shù)據(jù)結構=程序（Algorithm+Datastructure=Program)程序設計：為計算機處理問題編寫的一組指令。算法：處理問題的策略。數(shù)據(jù)結構：問題的數(shù)學模型。程序設計的實質是數(shù)據(jù)的表示和數(shù)據(jù)處理,為此應提出問題的數(shù)學模型和設計相應的算法。華電計算機系例如1.鋪設煤氣管道問題

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)鋪設煤氣管道設計圖華電計算機系例如2.圖書館的書目檢索問題登錄號書名作者分類號………………172832離散數(shù)學樊映川S01…172833理論力學羅遠祥S01…172834高等數(shù)學華羅庚S01…172835線性代數(shù)灤汝書S02………………書名登錄號……高等數(shù)學172832、172834…理論力學172833…線性代數(shù)172835………作者登錄號……樊映川172832…華羅庚172834…灤汝書172835………類別登錄號……L172833…S172832、172834………華電計算機系

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

數(shù)據(jù)元素數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素也可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項數(shù)據(jù)處理的最小單位。980604劉曄女188010學號姓名性別年月日組合項原子項出生日期（學生情況）華電計算機系

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

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

1.2基本概念

數(shù)據(jù)的存儲結構邏輯結構及數(shù)據(jù)元素在計算機中的表示.1）順序存儲方式（向量存儲）2）鏈式存儲方式3）索引存儲方式4）散列存儲方式

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

1.2基本概念

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

例如：ADTComplex{

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

數(shù)據(jù)關系：R1={<e1,e2>|e1是復數(shù)的實數(shù)部分、e2

是復數(shù)的虛數(shù)部分}

基本操作：InitComplex(v1,v2)；初始化：v1,v2的值賦值

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

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

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

1.2基本概念

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

結構結構是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素之間存在的關系。華電計算機系

1.

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

2.

研究具有某種邏輯關系的數(shù)據(jù)在計算機存儲器內的存儲方式。3.研究如何在數(shù)據(jù)的各種結構(邏輯的和物理的)的基礎上對數(shù)據(jù)實施一系列有效的基本操作。

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

基本運算算法比較及分析華電計算機系

1.3算法及算法評價

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

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

1.3算法及算法評價

算法分類1、程序設計語言描述的算法2、偽語言算法3、非形式算法（自然語言算法）

算法評價1、算法的正確性

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

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

4、算法所占空間

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

一條語句的頻度是指該語句被執(zhí)行的次數(shù)，而整個算法的頻度是指算法中所有語句的頻度之和。華電計算機系例如：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；機器只執(zhí)行一次，則它的頻度為一次，即f（n）=1執(zhí)行時間復雜度為O(1)。其語句執(zhí)行n次，頻度為n次，執(zhí)行時間與n成正比，f（n）=n，復雜度為O(n）。其語句執(zhí)行n2次，頻度為n2次，執(zhí)行時間與n2成正比，f（n

）=n2

，復雜度為O(n2）。華電計算機系算法的頻度:

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華電計算機系

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

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

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

。其中,

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

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

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

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

的值,算法到此結束。

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

intM,N;{

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

}}

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

函數(shù)類型

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

{//算法說明

語句序列;

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

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

while循環(huán)條件

語句;

do-while語句do{

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

for語句

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

華電計算機系

函數(shù)結束語句

return表達式；

return；case結束語句break；異常結束語句exit(異常代碼)；開關語句1switch(表達式){case值1：語句序列1；break；

case值2：語句序列2；break；