第一章 數(shù)據(jù)結構緒論

基本概念和術語

數(shù)據(jù)

描述客觀事物的符號，計算機中可以操作的對象，能被計算機識別并輸入給計算機處理的符號的集合。包括整型、實型等數(shù)值類型和字符、聲音、圖像、視頻等非數(shù)值類型。

數(shù)據(jù)元素

組成數(shù)據(jù)的、有一定意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。

• 例如：禽類的數(shù)據(jù)元素為雞、鴨、鵝等。

數(shù)據(jù)項

一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。

• 例如：對于人這個數(shù)據(jù)元素，可以有眼、耳、嘴、鼻等數(shù)據(jù)項，也可以有姓名、年齡、性別等數(shù)據(jù)項，具體選取哪些數(shù)據(jù)項視所構建的系統(tǒng)決定。

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

是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。其中“性質(zhì)相同”指數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項。通常將數(shù)據(jù)對象簡稱為數(shù)據(jù)。

數(shù)據(jù)結構

是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。計算機中的數(shù)據(jù)元素并不是孤立、雜亂無序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合。

邏輯結構與物理結構

邏輯結構

是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系。

用示意圖表示數(shù)據(jù)的邏輯結構時：

• 將每一個數(shù)據(jù)元素看作一個節(jié)點，用圓圈表示；
• 元素之間的邏輯關系用節(jié)點之間的連線表示，如果這個關系是有方向的，那么用帶箭頭的連線表示。

集合結構

集合結構中的數(shù)據(jù)元素除了同屬于一個集合外，互相之間沒有其他關系。

線性結構

線性結構中數(shù)據(jù)元素之間是一對一的關系。

樹形結構

樹形結構中數(shù)據(jù)元素之間存在一種一對多的層次關系。

圖形結構

圖形結構的數(shù)據(jù)元素是多對多的關系

物理結構(存儲結構)

物理結構是指數(shù)據(jù)的邏輯結構在計算機中的存儲形式。數(shù)據(jù)的存儲結構應正確反映數(shù)據(jù)元素之間的邏輯關系，如何存儲數(shù)據(jù)元素之間的邏輯關系是實現(xiàn)物理結構的重點和難點。

順序存儲結構

把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關系和物理關系是一致的。如數(shù)組。

數(shù)據(jù)結構中經(jīng)常會需要添加新的數(shù)據(jù)元素、去掉舊的數(shù)據(jù)元素，面對這種時刻變化的情況，順序結構不夠科學。

鏈式存儲結構

鏈式存儲結構把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)元素的存儲關系并不能反應其邏輯關系，需要用一個指針存放數(shù)據(jù)元素的地址，這樣通過地址就可以找到相關聯(lián)的數(shù)據(jù)元素的位置。

邏輯結構是面向問題的，物理結構則是面向計算機的，其基本目標就是將數(shù)據(jù)及其邏輯關系存儲到計算機的內(nèi)存中。

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

數(shù)據(jù)類型

數(shù)據(jù)類型是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。例如在高級語言中，每個變量、常量和表達式都有各自的取值范圍，類型就用來說明變量或表達式的取值范圍和所能進行的操作。

在C語言中，按照取值的不同，數(shù)據(jù)類型可以分成兩類：

• 原子類型：是不可以再分解的基本類型，包括整型、實型、字符型等；
• 結構類型：由若干個類型組合而成，是可以再分解的。例如。整型數(shù)組是由若干整型數(shù)據(jù)組成的。

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

對已有數(shù)據(jù)類型進行抽樣，就得到了抽象數(shù)據(jù)類型。

抽象數(shù)據(jù)類型(Abstract Data Type, ADT)是指一個數(shù)學模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，與其在計算機內(nèi)部如何表示和實現(xiàn)無關。

例如各種計算機，無論是超算、PC、平板、智能手機等，都擁有“整數(shù)”類型，也需要整數(shù)間的運算，那么整型就是一個抽象數(shù)據(jù)類型，盡管它在上面提到的各種計算機中的實現(xiàn)方法可能不一樣，但由于其定義的數(shù)學特征相同，在編程者看來，它們就是相同的。因此，抽象的意義在于數(shù)據(jù)類型的數(shù)學抽象特性。

抽象數(shù)據(jù)類型體現(xiàn)了程序設計中問題分解、抽象和信息隱藏的特性。抽象數(shù)據(jù)類型把實際生活中的問題分解為多個規(guī)模小且容易處理的問題，然后建立一個計算機能處理的數(shù)據(jù)模型，并把每個功能模塊的實現(xiàn)細節(jié)作為一個獨立的單元，從而使具體實現(xiàn)過程隱藏起來。

這里給出描述抽象數(shù)據(jù)類型的標準格式：

ADT 抽象數(shù)據(jù)類型名 Data數(shù)據(jù)元素之間邏輯關系的定義 Operation 操作1初始條件操作結果描述操作2......操作n...... endADT

總結回顧

數(shù)據(jù)結構相關概念

數(shù)據(jù)結構定義

數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。

數(shù)據(jù)結構分類

抽象數(shù)據(jù)類型及其描述方法

ADT 抽象數(shù)據(jù)類型名 Data數(shù)據(jù)元素之間邏輯關系的定義 Operation 操作1初始條件操作結果描述操作2......操作n...... endADT

轉載于:https://www.cnblogs.com/communedefence/p/8513152.html

總結

以上是生活随笔為你收集整理的数据结构学习笔记（一）——《大话数据结构》的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。