大學數(shù)據(jù)結(jié)構(gòu)課件-第1章緒論

1

1.1什么是數(shù)據(jù)結(jié)構(gòu)

1.2基本概念和術(shù)語

1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)

1.4算法和算法分析第1章緒論2一、數(shù)據(jù)結(jié)構(gòu)課程的研究內(nèi)容電子計算機的主要用途：早期：主要用于數(shù)值計算。后來：

處理逐漸擴大到非數(shù)值計算領(lǐng)域（能處理多種復雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）數(shù)學模型→選擇計算機語言→編出程序→測試→最終解答數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學方程加以描述1.1什么是數(shù)據(jù)結(jié)構(gòu)3非數(shù)值計算問題例1.1

電話號碼查詢問題。例1.2

田徑賽的時間安排問題：設有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）。要求設計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。1.1什么是數(shù)據(jù)結(jié)構(gòu)4（1）設用如下六個不同的編碼代表不同的項目：

跳高跳遠標槍鉛球100米200米

AB CDE F姓名項目1項目2項目3丁一ABE馬二CD

張三CEF李四DFA王五BF（2）用頂點（圓圈）代表比賽項目

不能同時進行比賽的項目之間連上一條邊。AEBFDC比賽時間比賽項目1A，C2B，D3E4F1.1什么是數(shù)據(jù)結(jié)構(gòu)5因此，可以認為：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科。由此可見：對于解決非數(shù)值計算的問題首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？1.1什么是數(shù)據(jù)結(jié)構(gòu)61.許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，國防科技大學計算機研究所，1985年“按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲表示方式把它存儲在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合，就叫做一個數(shù)據(jù)結(jié)構(gòu)?！碧攸c：從三個方面來看數(shù)據(jù)結(jié)構(gòu)。2.李春葆，《數(shù)據(jù)結(jié)構(gòu)（C語言篇）習題與解析》，清華大學出版社，2000年“數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)又可以分為下述三個組成部分，它們分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算。”特點：明確強調(diào)“關(guān)系”，且細分“關(guān)系”。1.1什么是數(shù)據(jù)結(jié)構(gòu)73.黃國瑜，葉乃菁，《數(shù)據(jù)結(jié)構(gòu)》，清華大學出版社，2001年“在程序語言中，“數(shù)據(jù)類型”是指程序語言中變量所能表示并存儲的數(shù)據(jù)種類，“數(shù)據(jù)實體”則是指在一種數(shù)據(jù)類型中的所有可能元素的集合。而“數(shù)據(jù)結(jié)構(gòu)”，大致上說來，就是數(shù)據(jù)實體中元素之間的關(guān)系，包括數(shù)據(jù)的表示法和運算?！碧攸c：指出“關(guān)系”為表示法和運算。4.陳慧南，《數(shù)據(jù)結(jié)構(gòu)——C語言描述》，西安電子科技大學出版社，2003年“從數(shù)學概念上講，一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。研究數(shù)據(jù)結(jié)構(gòu)是為了解決應用問題，所以討論數(shù)據(jù)結(jié)構(gòu)必須同時討論在數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的相關(guān)運算及其算法才有意義?！碧攸c：從邏輯聯(lián)系入手，兼顧其它方面。1.1什么是數(shù)據(jù)結(jié)構(gòu)8計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算則要依靠數(shù)據(jù)結(jié)構(gòu)。同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。程序設計實質(zhì)=好算法+好結(jié)構(gòu)二、學習數(shù)據(jù)結(jié)構(gòu)課程的用處1.1什么是數(shù)據(jù)結(jié)構(gòu)9是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程數(shù)學硬件軟件三、數(shù)據(jù)結(jié)構(gòu)課程的地位1.1什么是數(shù)據(jù)結(jié)構(gòu)10數(shù)據(jù)--是對客觀事物的符號表示，在計算機科學中是指所有（Data）

能輸入到計算機中并被計算機程序處理的符號的總稱(整數(shù)、實數(shù)、字符串、圖像、聲音等)。數(shù)據(jù)元素--是數(shù)據(jù)的基本單位，具有完整確定的實際意義，（DataElement）在計算機程序中通常作為一個整體進行考慮和處理(又稱記錄、結(jié)點等)。數(shù)據(jù)項--

一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，是數(shù)據(jù)的（DataItem）不可分割的最小單位(又稱字段等)。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例：學生檔案>個人記錄>姓名、性別、籍貫…1.2基本概念和術(shù)語11數(shù)據(jù)對象（DataObject）--是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)（DataStructure）--是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

表示為：

Data_Structure=(D,S)元素有限集關(guān)系有限集例1：用數(shù)據(jù)結(jié)構(gòu)表示一周中的七天。Data_Structure=(D,S),其中，D={}S={}Mon,Tue,Wen,Thu,Fri,Sat,Sun<Mon,Tue>,<Tue,Wen>,<Wen,Thu>…1.2基本概念和術(shù)語12（1）Data_Structure=(D,S)，其中，

D={01，02，03，04，05}S={}（2）S=(D,R)D={a,b,c,d,e,f

}R={<a,e>,<

b,c>,<

c,a>,<

e,f>,<

f,d>}解:

上述表達式可用圖形表示為：aebcfd例2：將下述表達式用圖形的形式表示出來集合結(jié)構(gòu)線性結(jié)構(gòu)1.2基本概念和術(shù)語13（3）

Data_Structure=(D,S),其中，

D={01，02，03，04，05，06，07}S={(01,02)，(01,03)，(01,04)，(02,05)，(02,06)，(03,07)}（4）S=(D,R)

D={di|1≤i≤5,1≤j≤5}

R={<di,dj>,i<j}d1d2d3d4d501020304050607樹形結(jié)構(gòu)圖狀結(jié)構(gòu)1.2基本概念和術(shù)語14邏輯結(jié)構(gòu)--數(shù)據(jù)元素之間的邏輯關(guān)系，即結(jié)構(gòu)中定義的“關(guān)系”。邏輯結(jié)構(gòu)可細分為4類：集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)一對一關(guān)系一對多關(guān)系多對多關(guān)系非線性結(jié)構(gòu)1.2基本概念和術(shù)語1501000101物理結(jié)構(gòu)--也稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示（映像）。順序映像非順序映像特點是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。特點是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。例：復數(shù)3.0-2.3i

的存儲形式3.0-20-2.3算法的設計取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)----順序存儲結(jié)構(gòu)----鏈式存儲結(jié)構(gòu)1.2基本概念和術(shù)語16數(shù)據(jù)類型--是一個值的集合和定義在這個值集上的一組操作

的總稱。抽象數(shù)據(jù)類型—由用戶定義，用以表示應用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型組成，并包含一組相關(guān)的操作。抽象數(shù)據(jù)類型可用ADT=（D，S，P）三元組表示數(shù)據(jù)對象D上的關(guān)系集D上的操作集ADT

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

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名ADT常用定義格式1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)17例：給出自然數(shù)（NaturalNumber）的抽象數(shù)據(jù)類型定義。IsZero(x):Booleanif(x==0)返回Trueelse返回FalseAdd(x,y):NaturalNumberif(x+y<=MaxInt)返回x+yelse返回MaxIntSubtract(x,y):NaturalNumberif(x<y)返回0else返回x-yEqual(x,y):Booleanif(x==y)返回Trueelse返回FalseADTNaturalNumber

{}NaturalNumber數(shù)據(jù)對象:數(shù)據(jù)關(guān)系:數(shù)據(jù)操作:一個整數(shù)的有序子集合,它開始于0,結(jié)束于機器能表示的最大整數(shù)。1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)18一、算法：算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。二、算法的5個特性：

有窮性、確定性、可行性、輸入和輸出三、算法設計的要求：

正確性、可讀性、健壯性、效率與低存儲需求時間復雜度空間復雜度1.4算法和算法分析19時間復雜度：一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中語句的執(zhí)行次數(shù)稱為語句頻度或時間頻度，記為T(n)。算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作

T（n）=O（f（n））隨著問題規(guī)模的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同，稱為算法的漸近時間復雜度，簡稱時間復雜度。1.4算法和算法分析20①{++x;s=0;}②for(i=1;i<=n;++i){++x;s+=x;}③for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}O

（1）O

（n）O

（n2）算法的時間復雜度由嵌套最深的語句的頻度決定的④i=1;while(i<=n)i=i*2;O

（log2n）1.4算法和算法分析21常數(shù)階O(1)對數(shù)階O(log2n)線性階O(n)線性對數(shù)階O(nlog2n)平方階O(n2)立方階O(n3)……K次方階O(nk)指數(shù)階O(2n)1.4算法和算法分析22

教學要求：

1、了解數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語:數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)概念及邏輯結(jié)構(gòu)與物理結(jié)構(gòu)間的關(guān)系。

2、了解算法的定義、算法的特性、算法的時間代價、算法的空間代價。

3、掌握計算語句頻度和估算算法時間復雜度的方法。第1章總結(jié)231、把矩形定義及其運算設計成一種抽象數(shù)據(jù)類型，其數(shù)據(jù)部分包括矩形的長度和寬度，操作部分包括初始化矩形的尺寸、求矩形的周長和面積。2、試用圖形的形式表示下列二元組表示的數(shù)據(jù)結(jié)構(gòu)，并指出它們分別屬于何種結(jié)構(gòu)。

(1)A=(K,R)，其中K={a1,a2,a3……an}