大話資料結構（1）資料結構緒論

• 資料結構緒論
• • 啟示錄
  • 資料結構起源
  • 基本概念和術語
  • • 資料
    • 資料元素
    • 資料項
    • 資料對象
    • 資料結構
  • 邏輯結構與實體結構
  • • 邏輯結構
    • • 1. 集合結構
      • 2. 線性結構
      • 3. 樹形結構
      • 4. 圖形結構
    • 實體結構
    • • 1.順序存儲結構
      • 2.鍊式存儲結構
    • 抽象資料類型
    • • 資料類型
      • 抽象資料類型
      • 抽象資料類型的标準格式

資料結構緒論

If you give someone a program, you will frustrate them for a day; if you teach them how to program, you will frustrate them for a lifetime.

（如果你交給某人一個程式，你 将折磨他一整天；如果你教某人如何編寫程式，你将折磨他一輩子。）

啟示錄

資料結構：是互相之間存在一種或多種特定關系的資料元素的集合

程式設計 = 資料結構 + 算法

為編寫岀一個“好”的程式，必須分析待處理對象的特性及各處理對象之間存在的關系，
這也就是研究資料結構的意義所在。
           

資料結構起源

資料結構是一門研究非數值計算的程式設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。
           

1968年，美國的高德納（Donald E. Knuth）教授在其所寫的《計算機程式設計藝 術》第一卷《基本算法》中，較系統地闡述了資料的邏輯結構和存儲結構及其操作， 開創了資料結構的課程體系。

基本概念和術語

資料

是描述客觀事物的符号，是計算機中可以操作的對象，是能被計算機識别，并輸入給計算機處理的符号集合。

資料不僅僅包括整型、實型等數值類型，還包括字元及聲音、圖像、視訊等非數值類型。

資料，其實就是符号，而且這些符号必須具備兩個前 提：
■	可以輸入到計算機中。
■	能被計算機程式處理。
           

對于整型、實型等數值類型，可以進行數值計算。

對于字元資料類型，就需要進行非數值的處理。而聲音、圖像、視訊等其實是可以通過編碼的手段變成字元資料來處理的。

資料元素

資料元素（記錄）：是組成資料的、有一定意義的基本機關，在計算機中通常作為整體處理。
           

比如，在人類中，人是資料元素。

資料項

資料項：一個資料元素可以由若幹個資料項組成。

具體有哪些資料項，要視你做的 系統來決定。
           

資料對象

資料對象：是性質相同的資料元素的集合，是資料的子集。

在實際應用中，處理的資料元素通常具有相同性質
在不産生混淆的情況下，我們都将資料對象簡稱為資料。
           

資料結構

不同資料元素之間不是獨立的，而是存在特定的關系，我們将這些關系稱為結構。

資料結構：是互相之間存在一種或多種特定關系的資料元素的集合。

資料元素之間存在的一種或多種特定關系，也就是資料的組織形式。
           

邏輯結構與實體結構

按照視點的不同，我們把資料結構分為邏輯結構和實體結構。

邏輯結構

邏輯結構：是指資料對象中資料元素之間的互相關系。

邏輯結構是針對具體問題的，是為了解決某個問題
在對問題了解的基礎上，選擇一個合适的資料結構表示資料元素之間的邏輯關系。
           

邏輯結構分為以下四種：

1. 集合結構

集合結構：集合結構中的資料元素除了同屬于一個集合外，它們之間沒有其他關 系。
           

如圖所示，類似于數學中的集合。

2. 線性結構

線性結構：線性結構中的資料元素之間是一對一的關系
           

3. 樹形結構

樹形結構：樹形結構中的資料元素之間存在一種一對多的層次關系
           

4. 圖形結構

圖形結構：圖形結構的資料元素是多對多的關系
           

實體結構

首先需要知道：存儲器主要是針對記憶體而言的，像硬碟、軟碟、CD光牒等外部存儲器的資料組織通常用檔案結構來描述。

實體結構（存儲結構）：是指資料的邏輯結構在計算機中的存儲形式。

資料的存儲結構應正确反映資料元素之間的邏輯關系。
如何存儲資料元素之間的邏輯關系，是實作實體結構的重點和難點。
           

資料元素的存儲結構形式有兩種：順序存儲和鍊式存儲。

1.順序存儲結構

順序存儲結構：是把資料元素存放在位址連續的存儲單元裡，其資料間的邏輯關系和實體關系是一緻的。
           

2.鍊式存儲結構

鍊式存儲結構是為了解決時常處于變化中的結構的。

鍊式存儲結構：是把資料元素存放在任意的存儲單元裡，這組存儲單元可以是連續的，也可以是不連續的。
           

資料元素的存儲關系并不能反映其邏輯關系，是以需要用 一個指針存放資料元素的位址，這樣通過位址就可以找到相關聯****資料元素的位置。

抽象資料類型

抽象資料類型展現了程式設計中問題分解、抽象和資訊隐藏的特性。

抽象資料類型把實際生活中的問題分解為多個規模小且容易處理的問題，然後建立一個 計算機能處理的資料模型，并把每個功能子產品的實作細節作為一個獨立的單元，進而 使具體實作過程隐藏起來。

資料類型

資料類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

資料類型是按照值的不同進行劃分的。
           

在C語言中，按照取值的不同，資料類型可以分為兩類：

■	原子類型：是不可以再分解的基本類型，包括整型、實型、字元型等。
■	結構類型：由若幹個類型組合而成，是可以再分解的。例如，整型數組是由若幹整 型資料組成的。
           

進階語言的程式設計者不關心資料在計算機内部是如何表示的，以及CPU為實作對這些資料操作進行了什麼工作。是以，對于如整數運算、實數運算、字元運算等這些基本操作，我們可以考慮把它們都抽象出來。

抽象是指抽取出事物具有的普遍性的本質。
抽出問題的特征而忽略非本質的細節，是對具體事物的一個概括。
           

抽象資料類型

對已有的資料類型進行抽象，就有了抽象資料類型。

抽象資料類型（Abstract Data Type, ADT）:是指一個數學模型及定義在該模型 上的一組操作。
抽象資料類型的定義僅取決于它的一組邏輯特性，而與其在計算機内部如何表示和實作無關。
           

抽象資料類型的标準格式