講數(shù)據(jù)結(jié)構(gòu)概述

第1講數(shù)據(jù)結(jié)構(gòu)概述

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語

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

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

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語

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

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

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

算法+數(shù)據(jù)結(jié)構(gòu)=程序設計算法即處理問題的策略，而數(shù)據(jù)結(jié)構(gòu)即為問題的數(shù)學模型。尋求數(shù)學模型的實質(zhì)提取操作的對象找出這些操作對象之間含有的關(guān)系用數(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ù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科數(shù)據(jù)結(jié)構(gòu)的定義(從研究對象來看):第10頁,共41頁，2024年2月25日，星期天《數(shù)據(jù)結(jié)構(gòu)課程》所處的地位：介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。第11頁,共41頁，2024年2月25日，星期天二、數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語1、數(shù)據(jù)(Data):

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

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

或稱：元素、結(jié)點、頂點、記錄

對于文件，每個記錄就是它的數(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)：

具有相同性質(zhì)的數(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、邏輯結(jié)構(gòu)

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

（a）集合結(jié)構(gòu)

（b）線性結(jié)構(gòu)

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

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

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

例如，有5個人，分別記為a,b,c,d,e,其中a是b的父親，b是c的父親，c是d的父親,d是e的父親，如果只討論他們之間所存在的父子關(guān)系，則可以用下面的二元組形式化地予以表達: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的直接前驅(qū)，b是a的直接后繼a是開始結(jié)點，e為終端結(jié)點，b、c、d為內(nèi)部結(jié)點

abcde線性邏輯結(jié)構(gòu)

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

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

7、數(shù)據(jù)的運算集合注意：數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的，而運算的具體實現(xiàn)就依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。

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

8、數(shù)據(jù)結(jié)構(gòu)定義的術(shù)語描述

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

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

數(shù)據(jù)的邏輯結(jié)構(gòu)

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

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

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

散列存儲索引存儲串及數(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語言中基本類型：整型、實型、字符型等結(jié)構(gòu)數(shù)據(jù)類型

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

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

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

……

數(shù)據(jù)關(guān)系：

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數(shù)據(jù)類型名稱第31頁,共41頁，2024年2月25日，星期天練習：指出下列二元組表示法的數(shù)據(jù)結(jié)構(gòu)是屬于何種邏輯結(jié)構(gòu)。（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頁,