第一講-數(shù)據(jù)結(jié)構基本概念講述課件

2023/7/20濱州學院信息工程系1數(shù)據(jù)結(jié)構概述數(shù)據(jù)結(jié)構基本概念22023/7/20

數(shù)據(jù)結(jié)構課程的地位它是計算機專業(yè)及相關專業(yè)的核心課程之一，是計算機及相關專業(yè)的重要骨干基礎課程。它針對非數(shù)值計算的程序設計問題，研究計算機的操作對象以及它們之間的關系和操作。即其研究目的是研究有效地組織和處理非數(shù)值類型數(shù)據(jù)的理論、技術和方法。32023/7/20數(shù)據(jù)結(jié)構的核心研究內(nèi)容數(shù)據(jù)的邏輯結(jié)構、存儲結(jié)構及它們之間的關系和相應的基本操作運算的定義和實現(xiàn)。教材圍繞數(shù)據(jù)結(jié)構的三種基本結(jié)構：線性結(jié)構（第2-5章）、樹形結(jié)構（第6章）和圖形結(jié)構（第7章）展開討論，研究解決如下問題：一個具體問題的邏輯結(jié)構是什么？適宜選用什么樣的存儲結(jié)構？采用什么樣的操作實現(xiàn)算法效率更高？42023/7/20學時數(shù)：96（64學時授課＋32學時上機）教材：嚴蔚敏編著，數(shù)據(jù)結(jié)構（C語言版），清華大學出版社52023/7/20章內(nèi)容學時

章內(nèi)容學時

1緒論47圖82線性表88查找83棧和隊列89排序104串45數(shù)組與廣義表6上機326樹和二叉樹8合計96內(nèi)容安排62023/7/20本節(jié)內(nèi)容數(shù)據(jù)結(jié)構討論的范疇數(shù)據(jù)結(jié)構中的基本概念72023/7/20NiklausWirth：

Algorithm

+DataStructures=Programs算法:數(shù)據(jù)結(jié)構:處理問題的策略問題的數(shù)學模型一、數(shù)據(jù)結(jié)構討論的范疇82023/7/20概括地說：

數(shù)據(jù)結(jié)構是一門討論“描述現(xiàn)實世界實體的數(shù)學模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學科。92023/7/201、問題舉例

學生信息包括學號、姓名、性別、籍貫。建立一個學生檔案，要求：查找“王紅”是否存在。如何記錄所有學生記錄（及選擇何種邏輯數(shù)據(jù)結(jié)構）？選擇何種存儲結(jié)構？若把所有記錄依次存儲在一個數(shù)組中——采用順序存儲結(jié)構若采用指針鏈表——采用鏈式存儲結(jié)構102023/7/20學生信息管理系統(tǒng)計算機處理的對象是表元素間的關系是線性關系施加于對象上的操作常見有查詢、插入、刪除等112023/7/20n皇后問題oooxxxoooxooxxooxxxooxoooxxoooxxoooxxxooxooxoo122023/7/20N皇后問題

計算機處理的對象是樹形結(jié)構元素間的關系是層次關系施加于對象上的操作有查詢、插入、刪除等132023/7/20

勝利

發(fā)生疫情的五個村子河源長利太華樺南1275344123

村子聯(lián)系網(wǎng)絡圖v1v5v2v4v31275413432已知五個村子發(fā)生了疫情，由一人將疫苗送達到5個村莊。目標是尋找一條耗時最少的路線。142023/7/20快速送達疫苗計算機處理的對象是圖元素間的關系是復雜的圖形或網(wǎng)狀關系施加于對象上的操作有查詢、插入、刪除等152023/7/202、數(shù)據(jù)結(jié)構研究的范疇由以上三個例子可見，描述這類非數(shù)值計算問題的數(shù)學模型不再是數(shù)學方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構。因此，簡單說來，數(shù)據(jù)結(jié)構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作的學科。162023/7/203、數(shù)據(jù)結(jié)構課程的特點數(shù)據(jù)結(jié)構是介于數(shù)學、計算機硬件和計算機軟件之間的一門計算機科學與技術專業(yè)的核心課程，是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫、人工智能等課程的基礎。同時，數(shù)據(jù)結(jié)構技術也廣泛應用于信息科學、系統(tǒng)工程、應用數(shù)學以及各種工程技術領域。172023/7/20數(shù)據(jù)結(jié)構課程特點（續(xù)）數(shù)據(jù)結(jié)構課程集中討論軟件開發(fā)過程中的設計階段、同時涉及編碼和分析階段的若干基本問題。此外，為了構造出好的數(shù)據(jù)結(jié)構及其實現(xiàn)，還需考慮數(shù)據(jù)結(jié)構及其實現(xiàn)的評價與選擇。因此，數(shù)據(jù)結(jié)構的內(nèi)容包括三個層次的五個“要素”，如下圖所示：182023/7/20方面層次

數(shù)據(jù)表示數(shù)據(jù)處理

抽象

邏輯結(jié)構基本運算

實現(xiàn)

存儲結(jié)構

算法

評價不同結(jié)構的比較及算法分析數(shù)據(jù)結(jié)構課程內(nèi)容體系192023/7/204、學習的目的程序設計＝好算法＋好結(jié)構計算機內(nèi)的數(shù)值問題依靠方程，而非數(shù)值問題（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構。202023/7/205、學習目標對每個數(shù)據(jù)結(jié)構加強對存在代價與效益的觀念掌握常用的數(shù)據(jù)結(jié)構——將常用的數(shù)據(jù)結(jié)構放入你的工具包理解怎樣去衡量一個數(shù)據(jù)結(jié)構或程序的代價212023/7/20

重基礎(牢固準確掌握)講實際(實現(xiàn)、分析算法)

上課認真聽講、適當做好筆記，認真獨立完成作業(yè)做好預習和及時復習；課后需要多讀教材和參考書，查看相關內(nèi)容，在理解基本內(nèi)容的基礎上，勤思考多練習上機實驗十分重要，一定要在上機前做好充分準備，多采用不同的數(shù)據(jù)存儲結(jié)構和不同的實現(xiàn)算法解決同一個問題。6、怎樣學習數(shù)據(jù)結(jié)構222023/7/20二、數(shù)據(jù)結(jié)構中的基本概念數(shù)據(jù)與數(shù)據(jù)結(jié)構數(shù)據(jù)類型抽象數(shù)據(jù)類型232023/7/201、數(shù)據(jù)與數(shù)據(jù)結(jié)構數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。是計算機操作的對象的總稱。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，具有完整確定的實際意義。在程序中常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。242023/7/20數(shù)據(jù)項：是數(shù)據(jù)不可分割的最小單位，是構成數(shù)據(jù)元素的項目。數(shù)據(jù)對象：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。整數(shù)數(shù)據(jù)對象N={0,1,2,…}字母字符數(shù)據(jù)對象C={‘A’,’B’,……‘Z’}252023/7/20數(shù)據(jù)結(jié)構：是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合帶結(jié)構的數(shù)據(jù)元素的集合262023/7/20線性結(jié)構樹形結(jié)構圖狀結(jié)構集合結(jié)構常見的數(shù)據(jù)結(jié)構272023/7/20數(shù)據(jù)結(jié)構的表示二元組表示Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關系的有限集。282023/7/20

例：設計一數(shù)據(jù)結(jié)構表示復數(shù)，并給出其二元組定義。

復數(shù)由實部和虛部構成（構成元素），兩者之間存在著一種次序關系（邏輯關系）?？梢员硎緸椋?/p>

Complex=(C,R)

其中,C={c1,c2}、R={<c1,c2>}說明:<>表示有序數(shù)對，用圖示法表示時畫箭頭；()表示無序數(shù)對，用圖示法表示時畫線段。292023/7/20數(shù)據(jù)的存儲結(jié)構邏輯結(jié)構在存儲器中的表示（映像）“元素”的映像“關系”的映像302023/7/20元素的映像方法用二進制位串存儲數(shù)據(jù)元素312023/7/20關系的映像方法即如何表示<x,y>，習慣稱為前驅(qū)后繼關系順序映像：用存儲位置的關系表示前驅(qū)后繼關系鏈式映像：用附加信息（指針）表示前驅(qū)后繼關系322023/7/20

當用某種高級程序設計語言進行編程時，通常可用該語言中提供的數(shù)據(jù)類型描述之。兩種常見存儲方法比較順序映像：占用最少的存儲空間，但易產(chǎn)生較多碎片鏈式映像：不會產(chǎn)生碎片，但占用空間較多（包含線索信息）332023/7/20集合結(jié)構：僅同屬一個集合線性結(jié)構:一對一（1:1)

樹結(jié)構:一對多（1:n)

圖結(jié)構:多對多(m:n)非線性線性重點概念分析解釋1：什么叫數(shù)據(jù)的邏輯結(jié)構？答：指數(shù)據(jù)元素之間的邏輯關系。即從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是獨立于計算機的。342023/7/20（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達式可用圖形表示為：bcaefd此結(jié)構為線性的。

用圖形表示下列數(shù)據(jù)結(jié)構，并指出它們是屬于線性結(jié)構還是非線性結(jié)構。舉例352023/7/20

d1d5d2d4d3該結(jié)構是非線性（圖狀）的。解：上述表達式可用圖形表示為：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}362023/7/20解釋2：什么叫數(shù)據(jù)的物理結(jié)構？答：物理結(jié)構亦稱存儲結(jié)構，是數(shù)據(jù)的邏輯結(jié)構在計算機存儲器內(nèi)的表示（或映像），它依賴于計算機。

存儲結(jié)構可分為4大類：順序、鏈式、索引、散列。重點概念分析372023/7/20

不同類型的變量，其取值范圍不同，所能進行的操作（運算）不同。2、數(shù)據(jù)類型

在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所屬的數(shù)據(jù)類型。

定義：一組性質(zhì)相同的值的集合,以及定義于這個值集合上的一組操作的總稱.382023/7/20答：在數(shù)據(jù)的邏輯結(jié)構上定義的操作算法。它在數(shù)據(jù)的存儲結(jié)構上實現(xiàn)。最常用的數(shù)據(jù)運算有5種：插入、刪除、修改、查找、排序解釋3：什么是數(shù)據(jù)的運算？392023/7/20

數(shù)據(jù)結(jié)構涵蓋的內(nèi)容402023/7/203、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（AbstractDataTypeADT）是一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關。即不論其內(nèi)部結(jié)構如何變化，只要它的數(shù)學特性不變，都不影響其外部的使用。412023/7/20(1)抽象數(shù)據(jù)類型的特點

由用戶定義，用以表示應用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關的服務（或稱操作）信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離422023/7/20(2)抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。其中：D是數(shù)據(jù)對象；

S是D上的關系集；

P是對D的基本操作集432023/7/20其中基本操作的定義格式為:基本操作名（參數(shù)表）初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

一般定義格式ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關系：〈數(shù)據(jù)關系的定義〉

基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名442023/7/20說明賦值參數(shù)

只為操作提供輸入值。引用參數(shù)

以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件

描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結(jié)果

說明了操作正常完成之后，數(shù)據(jù)結(jié)構的變化狀況和應返回的結(jié)果。若初始條件為空，則省略之。452023/7/20

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

D＝{e1,e2｜e1,e2∈RealSet}

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

R1＝{<e1,e2>|e1是復數(shù)的實數(shù)部分

|e2是復數(shù)的虛數(shù)部分}ADTComplex{ADT定義舉例例如，抽象數(shù)據(jù)類型復數(shù)的定義：462023/7/20基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構造復數(shù)Z,其實部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復數(shù)已存在。操作結(jié)果：用realPart返回復數(shù)Z的實部值。472023/7/20

GetImag(Z,&ImagPart)初始條件：復數(shù)已存在。操作結(jié)果：用ImagPart返回復數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復數(shù)。操作結(jié)果：用sum返回兩個復數(shù)z1,z2的和。

}ADTComplex482023/7/20則Add(z1,z2,z3)操作的結(jié)果即為用戶企求的結(jié)果，即z3=是z1和z2的和假設:z1和z2是上述定義的復數(shù)492023/7/20抽象數(shù)據(jù)類型與數(shù)據(jù)類型的區(qū)別

它與數(shù)據(jù)類型實質(zhì)上是一個概念，但其特征是使用與實現(xiàn)分離，實行封裝和信息隱蔽（獨立于計算機）502023/7/20

例如，對以上定義的Complex，可有如下實現(xiàn)：(3)抽象數(shù)據(jù)類型的實現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。512023/7/20typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲結(jié)構的定義//-----基本操作的函數(shù)原型說明void

Assign(complex&Z,floatrealval,floatimagval)；//

構造復數(shù)Z,其實部和虛部分別被賦以參數(shù)//realval

和imagval

的值522023/7/20floatGetReal(cpmplexZ)；

//返回復數(shù)Z的實部值float

Getimag(cpmplexZ)；

//返回復數(shù)Z的虛部值voidadd(co