CS自學筆記 Data Structure 1.1–1.4

#Data Structure基本概念

1.1資料結構定義:

In computer science, a data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

以上是Wikipedia所給定的定義,參照其他書籍後補充如下:

  1. 是一種程式設計最佳化的理論。
  2. 不僅討論資料的儲存,同時也考慮到彼此之間的關係與運算。
  3. 最終達到加快執行速度與減少記憶體佔用空間等功能

1.2 資料與資訊的意義:

DIKW模型

資料(data):可以為數字、文字、符號,通常透過觀察、測量獲得。

資訊(information):當資料被處理為訊息後,通常可以回答一些具體的問題,例如誰(who)、什麼(what)、什麼時候(when)、哪裡(where)等問題,所以也可以看成被人或者電腦處理和理解過後的資料。

知識(knowledge):藉由對資訊的學習、歸納或推導而來,知識使人類和電腦能在行動上應用所學習與理解的資訊。在此階段,知識通常可以回答到如何(How)層次的問題。

智慧(Intelligence):智慧是一種活用知識,對事物進行思考、分析的能力。智慧是哲學探索的本質,具有判斷是非和好壞,能夠提出還尚未有答案的問題。智慧是人類所特有的,是目前唯一不能用任何工具與演算法做良好的實現,而人工智慧(artificial intelligence)則是為了逼近這個目標所形成的領域。在智慧層次可以回答為什麽(Why)的問題。

在理解了DIKW架構後,在CS領域中:

資料(Data) →處理(Process) →資訊(Information)

這個過程我們稱之為資料處理(Data Processing)。

1.3資料的特性:主要可以分成以下三種型態

→基本資料型態(Primitive Data Type)

→結構化資料型態(Structured Data Type)

→抽象資料型態(Abstract Data Type, ADT)

詳細請自行Google,這在就不展開太多了。

1.4演算法基礎

Algorithms + Data Structures = Programs (by Niklaus)

資料結構和演算法都是程式設計中最重要的內功,所以在資料結構的學習中,也要提及基本的演算法概念。

Definition of algorithm: a procedure for solving a mathematical problem in a finite number of steps that frequently involves repetition of an operation.(as of finding the greatest common divisor)

根據以上定義,演算法就是:「在有限的步驟內解決數學問題的程序」

演法算法必須以下五個條件成立:

→輸入 (Input):可以由外界輸入0個、1個或多個以上的資料。

→明確性(Definiteness):個指令或步驟都必須是明確而不含糊的。

→有限性(Finiteness):須在有限步驟內結束,不會產生無窮迴路。

→有效性(Effectiveness):步驟必須清楚且可行的,並能讓使用者用紙和筆也可以計算出這些步驟的答案。

→輸出(Output):少要有一個以上的輸出結果,不可以沒有輸出結果。

而程序(procedure)與演算法最大的差異在於,程序不需滿足有限性(Finiteness)的要求。