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

講數(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ù)語

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

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

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

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

設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。算法:染色模型:無向圖第7頁,共41頁，2024年2月25日，星期天（1）用頂點(diǎn)代表比賽項(xiàng)目，設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米

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

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

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

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

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

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

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

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

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

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

客觀事物中數(shù)據(jù)元素之間的關(guān)系，與計(jì)算機(jī)無關(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ù)元素之間存在一對(duì)一的關(guān)系。（3）樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。（4）圖型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(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ù)對(duì)象）

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

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

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

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

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

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

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

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

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

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

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

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

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

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹型結(jié)構(gòu)圖型結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：

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

數(shù)據(jù)的抽象經(jīng)歷了三個(gè)發(fā)展階段：從無類型的二進(jìn)制數(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ù)對(duì)象和在該集合上的一組操作。（如C中的int型，它的值是[-MAXINT,MAXINT]區(qū)間上的整數(shù)，操作為：加、減、乘、除、取余等運(yùn)算）原子數(shù)據(jù)類型

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

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

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

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

……

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

……

操作集合：操作名1：

…………

操作名n：}ADT抽象數(shù)據(jù)類型名稱第31頁,共41頁，2024年2月25日，星期天練習(xí)：指出下列二元組表示法的數(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、判斷算法好壞的標(biāo)準(zhǔn)(1)正確性(2)可讀性(3)健壯性(4)時(shí)空效率時(shí)間效率空間效率4、算法的描述程序流程圖偽代碼自然語言(中文)

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

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

C=A;A=B;B=C；時(shí)間復(fù)雜度：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;

時(shí)間復(fù)雜度：

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

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