講數(shù)據(jù)結構概述

講數(shù)據(jù)結構概述

第1講數(shù)據(jù)結構概述

1.1數(shù)據(jù)結構的基本概念與術語

1.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型

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

1.1數(shù)據(jù)結構的基本概念與術語

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

主要用于數(shù)值計算。后來：

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

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

設有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）設計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。算法:染色模型:無向圖第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日，星期天

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

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

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

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

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

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

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

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

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

（a）集合結構

（b）線性結構

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

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

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

例如，有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為內(nèi)部結點

abcde線性邏輯結構

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

數(shù)據(jù)結構在計算機中的表示(或稱映象）稱為數(shù)據(jù)的存儲結構，與計算機密切相關。四種基本的存儲結構：（1）順序存儲結構：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。（2）鏈式存儲結構：在每一個數(shù)據(jù)元素中增加一個存放地址的指針（→），用此指針來表示數(shù)據(jù)元素之間的邏輯關系。（3）索引存儲結構（4）散列存儲結構第20頁,共41頁，2024年2月25日，星期天數(shù)據(jù)結構：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日，星期天數(shù)據(jù)結構：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、數(shù)據(jù)的運算集合注意：數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結構之上的，而運算的具體實現(xiàn)就依賴于數(shù)據(jù)的存儲結構。

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

8、數(shù)據(jù)結構定義的術語描述

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

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

數(shù)據(jù)的邏輯結構

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

線性結構

非線性結構

順序存儲

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

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

數(shù)據(jù)的抽象經(jīng)歷了三個發(fā)展階段：從無類型的二進制數(shù)到基本數(shù)據(jù)類型的產(chǎn)生從基本數(shù)據(jù)類型到用戶自定義類型的產(chǎn)生從用戶自定義類型到抽象數(shù)據(jù)類型的出現(xiàn)第28頁,共41頁，2024年2月25日，星期天1.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型

1、數(shù)據(jù)類型(DataType)

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

C語言中基本類型：整型、實型、字符型等結構數(shù)據(jù)類型

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

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

數(shù)據(jù)對象：

……

數(shù)據(jù)關系：

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數(shù)據(jù)類型名稱第31頁,共41頁，2024年2月25日，星期天練習：指出下列二元組表示法的數(shù)據(jù)結構是屬于何種邏輯結構。（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、算法的實現(xiàn)本課程采用C語言第34頁,共41頁，2024年2月25日，星期天二、算法的效率算法隨問題的規(guī)模變大時效率變化情況。一個算法效率的評價主要從時間復雜度和空間復雜度來考慮。1、時間復雜度（著重評價）計算算法中主要語句執(zhí)行的次數(shù)——語句頻度時間復雜度—T(n)當問題規(guī)模n→∞時，算法執(zhí)行時間增長率。用大“O”表示法。記作T(n)=O(f(n))（f(n)：為語句頻度之和的最高次項的數(shù)量級階）問題規(guī)?！猲

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

C=A;A=B;B=C；時間復雜度：T(n)=1+1+1=O(1)——常量階頻度是：1頻度是：1頻度是：1第36頁,共41頁，2024年2月25日，星期天（2）二重循環(huán)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頁,