大話資料結構Java版第一節

為追求學習中的完美，再次拿起書本梳理資料結構與算法，此筆記是按照程傑老師的《大話資料結構》為教材進行學習，如有不妥之處請聯系作者删除。

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

1、基本概念

• 資料結構：是互相之間存在一種或多種特定關系的資料元素的集合；
• 資料：是描述客觀事物的符号，是計算機中可以操作的對象，是能被計算機識别，并輸入給計算機處理的符号集合；
  • 可以輸入到計算機中；
  • 能被計算機程式處理。
• 資料元素：是組成資料的、有一定意義的基本機關，在計算機中通常作為整體處理。也被稱為記錄。
• 資料項：一個資料元素可以由若幹個資料項組成；
  • 資料項是資料不可分割的最小單元。
• 資料對象：是性質相同的資料元素的集合，是資料的子集。

2、邏輯結構與實體結構

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

2.1、邏輯結構

• 是指資料對象元素之間的互相關系。可以分為下面幾種：
  • 集合結構：集合中的資料元素除了同屬一集合外，他們之間沒有任何關系。
  • 線性結構：線性結構中的資料元素之間是一對一的關系。
  • 樹形結構：樹形結構中的資料元素之間存在一種一對多的層次關系。
  • 圖形結構：圖形結構的資料元素是多對多的關系。
• 邏輯結構是針對具體問題的，是為了解決某個問題，在對問題的了解基礎上，選擇一個合适的資料結構來表示資料元素之間的邏輯關系。

2.2、實體結構（存儲結構）

• 是指資料的邏輯結構在計算機中的存儲形式。
• 資料元素的存儲結構有兩種：順序存儲 和 鍊式存儲
• 順序存儲結構
  • 是把資料元素存放在位址連續的存儲單元裡，其資料間的邏輯關系和實體關系是一緻的。
• 鍊式存儲結構
  • 是把資料元素存放在任意的存儲單元裡，這組存儲單元可以是連續的，也可以是不連續的。
  • 邏輯結構是面向問題的，而實體結構是面向計算機的，其基本的目标就是将資料及其邏輯關系存儲到計算機的記憶體中。

3、抽象資料類型

3.1、資料類型

• 資料類型：是指一組性質相同的值的集合及定義在此集合的上的一些操作總稱。
• 抽象是指抽取事物具有的普遍性質。
  • 抽出問題的特征而忽略非本質的細節是對具體事物的一個概括；
  • 抽象是一種思考問題的方式，它隐藏了複雜的細節，隻保留實作目标所必須的資訊。

3.2、抽象資料類型

• 對已有的資料類型進行抽象，就有了抽象資料類型。
• 抽型資料類型（Abstract Data Type ADT）：是指一個數學模型及定義在該模型上的一組操作。
  • 抽象的意義在于資料類型的數學抽象特征。
  • 抽象資料類型展現了程式設計中 問題分解、抽象和資訊隐藏的特性。