講數據結構概述

第1講數據結構概述

1.1數據結構的基本概念與術語

1.2數據類型和抽象數據類型

1.3算法和算法分析第2頁,共41頁，2024年2月25日，星期天

1.1數據結構的基本概念與術語

一、為什么要學習數據結構？電子計算機的主要用途：早期：

主要用于數值計算。后來：

處理逐漸擴大到非數值計算領域（能處理多種復雜的具有一定結構關系的數據）。第3頁,共41頁，2024年2月25日，星期天非數值計算的程序設計問題

算法+數據結構=程序設計算法即處理問題的策略，而數據結構即為問題的數學模型。尋求數學模型的實質提取操作的對象找出這些操作對象之間含有的關系用數學模型加以描述第4頁,共41頁，2024年2月25日，星期天非數值計算的程序設計問題例1:求一組(n個)整數中的最大值算法:基本操作是“比較兩個數的大小”模型：線性表58137902第5頁,共41頁，2024年2月25日，星期天例2：計算機對弈算法：對弈的規則和策略模型：樹第6頁,共41頁，2024年2月25日，星期天例3田徑賽的時間安排問題：

設有六個比賽項目，規定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）設計比賽日程表，使得在盡可能短的時間內完成比賽。算法:染色模型:無向圖第7頁,共41頁，2024年2月25日，星期天（1）用頂點代表比賽項目，設用如下六個不同的代號代表不同的項目：跳高跳遠標槍鉛球100米200米

A B CDE F（2）不能同時進行比賽的項目之間連上一條邊。某選手比賽的項目必定有邊相連（不能同時比賽）（3）對圖上的每個頂點染一種顏色，并且要求有線相連的兩個頂點不能具有相同顏色，而總的顏色種類應盡可能地少。同色可以同時比賽----田徑賽的時間安排問題解法第8頁,共41頁，2024年2月25日，星期天姓名項目1項目2項目3丁一ABE馬二CD

張三CEF李四DFA王五BFAEBFDC比賽時間比賽項目1A，C2B，D3E4F只需安排四個單位時間進行比賽（無向圖）第9頁,共41頁，2024年2月25日，星期天

數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的學科數據結構的定義(從研究對象來看):第10頁,共41頁，2024年2月25日，星期天《數據結構課程》所處的地位：介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。第11頁,共41頁，2024年2月25日，星期天二、數據結構的基本概念與術語1、數據(Data):

描述客觀事物的存在計算機中的并可為計算機處理的符號的總稱，是計算機程序加工的”原料”。（分兩類：數值型數據和非數值型數據）2、數據元素(DataElement):

是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。

或稱：元素、結點、頂點、記錄

對于文件，每個記錄就是它的數據元素對于數組，每個數組元素就是數據元素對于字符串，字符就是數據元素

第12頁,共41頁，2024年2月25日，星期天3、數據項(DataItem)：

是具有獨立意義的不可分割的最小數據單位。一個數據元素可由若干個數據項組成。數據元素:運動員數據項:姓名俱樂部名稱出生日期參加日期職務業績數據元素與數據項的例子：第13頁,共41頁，2024年2月25日，星期天4、數據對象(DataObject)：

具有相同性質的數據元素的集合。是數據的一個子集。整數數據對象：N＝{0，±1，±2…….}，字母字符數據對象：C={‘A’,’B’,…’Z’}學生成績數據對象:Cj={(‘101’,‘jane’,80),(‘102’,‘jack’,90),(‘103’,‘jerry’,75)}數據對象的例子：第14頁,共41頁，2024年2月25日，星期天5、邏輯結構

客觀事物中數據元素之間的關系，與計算機無關分兩大類：線性結構集合非線性結構樹型結構圖型結構（網狀結構）（1）集合：結構中的數據元素除了同屬于一種類型外，別無其它關系。（2）線性結構：結構中的數據元素之間存在一對一的關系。（3）樹型結構：結構中的數據元素之間存在一對多的關系。（4）圖型結構：結構中的數據元素之間存在多對多的關系。第15頁,共41頁，2024年2月25日，星期天

（a）集合結構

（b）線性結構

（c）樹型結構（d）圖型結構四類基本結構的示意圖第16頁,共41頁，2024年2月25日，星期天數據的邏輯結構二元組表示：

B=(K，R)其中：K：數據元素的有限集合（數據對象）

R：K上的關系的有限集合，用<ai,aj>表示.ai稱為直接前驅或弧尾,aj稱為直接后繼或弧頭.圖示為:aiaj弧aiaj邊有向關系無向關系第17頁,共41頁，2024年2月25日，星期天數據結構二元組表示法示例：

例如，有5個人，分別記為a,b,c,d,e,其中a是b的父親，b是c的父親，c是d的父親,d是e的父親，如果只討論他們之間所存在的父子關系，則可以用下面的二元組形式化地予以表達:B=（K，R）其中：K={a,b,c,d,e}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>}第18頁,共41頁，2024年2月25日，星期天

說明：a是b的直接前驅，b是a的直接后繼a是開始結點，e為終端結點，b、c、d為內部結點

abcde線性邏輯結構

用圖形方式表示如下：第19頁,共41頁，2024年2月25日，星期天6、存儲結構（物理結構）

數據結構在計算機中的表示(或稱映象）稱為數據的存儲結構，與計算機密切相關。四種基本的存儲結構：（1）順序存儲結構：用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。（2）鏈式存儲結構：在每一個數據元素中增加一個存放地址的指針（→），用此指針來表示數據元素之間的邏輯關系。（3）索引存儲結構（4）散列存儲結構第20頁,共41頁，2024年2月25日，星期天數據結構：B=（K，R）其中K={k1,k2,k3,k4,k5,k6,k7,k8,k9}R={r}r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>,<k7,k8>,<k8,k9>}這是一個線性結構，它的順序存儲方式如圖所示:順序存儲結構示例：第21頁,共41頁，2024年2月25日，星期天k1k2k3k6k5k4k7k8k9存儲地址M100110021003100410051006100710081009特點：邏輯上相鄰的元素物理位置上也相鄰第22頁,共41頁，2024年2月25日，星期天數據結構：B=（K，R）其中K={k1,k2,k3,k4,k5}R={r}r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}這是一個線性結構，它的鏈式存儲如圖所示。鏈式存儲結構示例：第23頁,共41頁，2024年2月25日，星期天100010011002100310041005100610071008存儲地址infonextk41006k21007k11003k5∧k31005特點:邏輯上相鄰物理上不一定相鄰。第24頁,共41頁，2024年2月25日，星期天

7、數據的運算集合注意：數據的運算是定義在數據的邏輯結構之上的，而運算的具體實現就依賴于數據的存儲結構。

數據的運算集合要視情況而定，一般而言，數據的運算包括插入、刪除、檢索、輸出、排序等。插入：在一個結構中增加一個新的結點。刪除：在一個結構刪除一個結點。檢索：在一個結構中查找滿足條件的結點。輸出：將一個結構中所有結點的值打印、輸出。排序：將一個結構中所有結點按某種順序重新排列。第25頁,共41頁，2024年2月25日，星期天

8、數據結構定義的術語描述

按一定的邏輯結構組成的一批數據（或稱帶結構的數據元素的集合），使用某種存儲結構將這批數據存儲于計算機中，并在這些數據上定義了一個運算集合。

注：同一種邏輯結構可采用不同的存儲方法（以上四種之一或組合），這主要考慮的是運算方便及算法的時空要求。第26頁,共41頁，2024年2月25日，星期天

數據的邏輯結構

數據的存儲結構運算：檢索、排序、插入、刪除、修改等

線性結構

非線性結構

順序存儲

鏈式存儲線性表棧隊列樹型結構圖型結構數據結構研究的三個方面：

散列存儲索引存儲串及數組第27頁,共41頁，2024年2月25日，星期天1.2數據類型和抽象數據類型

數據的抽象經歷了三個發展階段：從無類型的二進制數到基本數據類型的產生從基本數據類型到用戶自定義類型的產生從用戶自定義類型到抽象數據類型的出現第28頁,共41頁，2024年2月25日，星期天1.2數據類型和抽象數據類型

1、數據類型(DataType)

數據對象和在該集合上的一組操作。（如C中的int型，它的值是[-MAXINT,MAXINT]區間上的整數，操作為：加、減、乘、除、取余等運算）原子數據類型

C語言中基本類型：整型、實型、字符型等結構數據類型

C語言中數組和結構類型等第29頁,共41頁，2024年2月25日，星期天2、抽象數據類型（

AbstractDataTypes）由用戶定義，用以表示應用問題的數據模型由基本的數據類型組成,并包括一組相關的運算信息隱蔽和數據封裝，使用與實現相分離對一個抽象數據類型進行定義時，必須給出它的名字及各運算的運算符名，即函數名，并且規定這些函數的參數性質。第30頁,共41頁，2024年2月25日，星期天抽象數據類型描述的一般形式如下：ADT抽象數據類型名稱{

數據對象：

……

數據關系：

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數據類型名稱第31頁,共41頁，2024年2月25日，星期天練習：指出下列二元組表示法的數據結構是屬于何種邏輯結構。（1）B=(K,R)K={a,b,c,d,e,f}R={<a,e>,<b,c>,<c,a>,<e,f>,<f,d>}（2）B=(K,R)

K={di|1≤i≤5}

R={<di,dj>,i<j}第32頁,共41頁，2024年2月25日，星期天1.3算法和算法分析一、算法的概念和描述：1、什么是算法？求解問題的方法和步驟。

2、算法的特性（1）有窮性（2）確定性（3）可行性（4）輸入（有或沒有）（5）輸出（一定有）第33頁,共41頁，2024年2月25日，星期天3、判斷算法好壞的標準(1)正確性(2)可讀性(3)健壯性(4)時空效率時間效率空間效率4、算法的描述程序流程圖偽代碼自然語言(中文)

類高級語言（如：a<=>b）程序語言5、算法的實現本課程采用C語言第34頁,共41頁，2024年2月25日，星期天二、算法的效率算法隨問題的規模變大時效率變化情況。一個算法效率的評價主要從時間復雜度和空間復雜度來考慮。1、時間復雜度（著重評價）計算算法中主要語句執行的次數——語句頻度時間復雜度—T(n)當問題規模n→∞時，算法執行時間增長率。用大“O”表示法。記作T(n)=O(f(n))（f(n)：為語句頻度之和的最高次項的數量級階）問題規?！猲

算法求解問題的輸入量（或初始數據量）。第35頁,共41頁，2024年2月25日，星期天例：分析以下程序段的時間復雜度（1）A、B兩數交換

C=A;A=B;B=C；時間復雜度：T(n)=1+1+1=O(1)——常量階頻度是：1頻度是：1頻度是：1第36頁,共41頁，2024年2月25日，星期天（2）二重循環for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;

時間復雜度：

T(n)=1+2+3+…+n=

——平方階頻度是：1+2+3+…+n第37頁,