1

1.1什么是數據結構

1.2基本概念和術語

1.3抽象數據類型的表示和實現

1.4算法和算法分析第1章緒論2一、數據結構課程的研究內容電子計算機的主要用途：早期：主要用于數值計算。后來：

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

電話號碼查詢問題。例1.2

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

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

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

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

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

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

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

表示為：

Data_Structure=(D,S)元素有限集關系有限集例1：用數據結構表示一周中的七天。Data_Structure=(D,S),其中，D={}S={}Mon,Tue,Wen,Thu,Fri,Sat,Sun<Mon,Tue>,<Tue,Wen>,<Wen,Thu>…1.2基本概念和術語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：將下述表達式用圖形的形式表示出來集合結構線性結構1.2基本概念和術語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樹形結構圖狀結構1.2基本概念和術語14邏輯結構--數據元素之間的邏輯關系，即結構中定義的“關系”。邏輯結構可細分為4類：集合結構線性結構樹形結構圖狀結構一對一關系一對多關系多對多關系非線性結構1.2基本概念和術語1501000101物理結構--也稱存儲結構，是數據的邏輯結構在計算機存儲器內的表示（映像）。順序映像非順序映像特點是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。特點是借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。例：復數3.0-2.3i

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

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

抽象數據類型名{

數據對象：〈數據對象的定義〉

數據關系：〈數據關系的定義〉

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

抽象數據類型名ADT常用定義格式1.3抽象數據類型的表示與實現17例：給出自然數（NaturalNumber）的抽象數據類型定義。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數據對象:數據關系:數據操作:一個整數的有序子集合,它開始于0,結束于機器能表示的最大整數。1.3抽象數據類型的表示與實現18一、算法：算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。二、算法的5個特性：

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

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

T（n）=O（f（n））隨著問題規模的增大，算法執行時間的增長率和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常數階O(1)對數階O(log2n)線性階O(n)線性對數階O(nlog2n)平方階O(n2)立方階O(n3)……K次方階O(nk)指數階O(2n)1.4算法和算法分析22

教學要求：

1、了解數據結構的相關術語:數據、數據元素、數據對象、數據類型、數據結構、數據的邏輯結構與物理結構概念及邏輯結構與物理結構間的關系。

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

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

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