新觀念的資料結構將首先節錄並披露於 計算機概論-探索未來2011的附錄A
再度披露於 C語言初學指引(第四版)的第12,13章
2010年4月5日 星期一
1.2 何謂資料抽象化
在本書的開頭，首先我們介紹何謂資料抽象化（Data Abstraction）？以及它與資料結構的關係。
資料結構事實上就是資料抽象化（Data Abstraction）的一種結果，而資料抽象化包含了下列兩大項目：
☆ 資料的定義與組識方式：亦即「資料」的抽象化。
☆ 和資料有關的運算操作：亦即「運算」的抽象化。
在真實世界中，許多個體都是資料抽象化的結果，例如，一架飛機，代表的其實是許多個體與功能的集合，其內的個體包含座椅、引擎、操縱桿等等，甚至在這些個體被組裝後，它還具備了某些特性（例如重量、載重量等），也可能具備某些功能（例如引擎點火、起飛、降落、逃生等）。換句話說，在真實世界中，當我們提及『飛機』時，事實上，是提到「眾多特定個體與功能的集合」。因此，『飛機』事實上是資料抽象化後的名詞，而通常抽象化的目的是為了溝通方便。
圖1-1 當不使用資料抽象化，會導致溝通困難
圖1-2 即便使用資料抽象化，也必須雙方了解該名詞
由圖1-1與1-2中，您可以發現，資料抽象化及學習各名詞的重要性。舉例來說，假設某一位資深的軟體設計師告訴您，二元搜尋樹可以解決此一搜尋問題，對於沒有學過資料結構與學過資料結構的人而言，可能會有下列不同的反應。
圖1-3 個人的知識背景將導致不同的結果
因此，學習資料結構的最大用意在於了解各抽象化後之名詞（各種資料結構）的實質意義，例如二元搜尋樹是一種資料結構，它是一個抽象化後的名詞，背後包含了以某種順序配置資料等的詳細意義，而我們應該藉由此課程了解它。
資料結構事實上就是資料抽象化（Data Abstraction）的一種結果，而資料抽象化包含了下列兩大項目：
☆ 資料的定義與組識方式：亦即「資料」的抽象化。
☆ 和資料有關的運算操作：亦即「運算」的抽象化。
在真實世界中，許多個體都是資料抽象化的結果，例如，一架飛機，代表的其實是許多個體與功能的集合，其內的個體包含座椅、引擎、操縱桿等等，甚至在這些個體被組裝後，它還具備了某些特性（例如重量、載重量等），也可能具備某些功能（例如引擎點火、起飛、降落、逃生等）。換句話說，在真實世界中，當我們提及『飛機』時，事實上，是提到「眾多特定個體與功能的集合」。因此，『飛機』事實上是資料抽象化後的名詞，而通常抽象化的目的是為了溝通方便。
由圖1-1與1-2中，您可以發現，資料抽象化及學習各名詞的重要性。舉例來說，假設某一位資深的軟體設計師告訴您，二元搜尋樹可以解決此一搜尋問題，對於沒有學過資料結構與學過資料結構的人而言，可能會有下列不同的反應。
因此，學習資料結構的最大用意在於了解各抽象化後之名詞（各種資料結構）的實質意義，例如二元搜尋樹是一種資料結構，它是一個抽象化後的名詞，背後包含了以某種順序配置資料等的詳細意義，而我們應該藉由此課程了解它。
2009年10月30日 星期五
1.1.2 資料與抽象化
大約在西元1995年之後，一種新觀念的資料結構開始被大眾所接受。此一改變在於物件導向程式語言的流行所造成。在1995年之後，C++開始發展STL標準樣板類別庫，而Java語言也在此時誕生。在此階段，資料結構已經提升為抽象化的資料型式。這明顯的改變可以由struct關鍵字在C與C++中的不同來觀察。
讓我們檢視Algorithms + Data Structures = Programs之名言，在此名言中，資料結構代表的可說是結構化後的資料，但光有資料結構是無法運作的，因此需要演算法使得程式變成是「活」的。舉例來說，光是組織一艘航空母艦是不能完成工作的，必須有前進演算法，使得航空母艦能夠前進。然而戰鬥機也有前進演算法，明顯地，它與航空母艦的前進演算法應該不同，因此，這些演算法應該只侷限於該個體使用。
物件導向程式語言提供了以class類別來撰寫程式的新思維，藉由類別生成的物件實體之互動來達到程式設計之目的。而C++的類別與C語言的結構最大的差別在於，類別除了能夠組織資料，還能夠宣告所屬運算以及設計運算的細節。例如C語言的結構只能宣告「航空母艦」結構、「戰鬥機」結構，而C++的類別，不但能宣告「航空母艦」類別、「戰鬥機」類別，並且這些類別內還可以包含「前進」、「左彎」、「右彎」等成員函式。
到了Java流行的年代，上述名言可完全改為Programs = Classes，因為Java的每一行程式都必定隸屬於某一個類別中，絕對不會在類別之外。而這與原名言是否有衝突呢？嚴格來說，原名言仍是正確的，只需要小幅修正，因為此階段的資料結構已經包含了運算以及實現運算的演算法。換句話說，在純物件導向的程式設計中，Programs = Data Structures = Classes。
更明確地來說，兩者的Data Structures意函並不完全相同，如下整理：
1975~1995年：Programs(in Proc) = Algorithms + Old Data Structures
1995~20xx年：Programs(in OOP) = New Data Structures = Classes
而New Data Structures= Algorithms + Old Data Structures
struct關鍵字可用來觀察上述的時代演變。在C++的程式設計中，建議以類別方式來設計程式，但C++的struct結構體也可以如class類別般宣告成員函式，只不過預設的保護等級不同而已。換句話說，如果我們明確地宣告各成員的保護等級時，則使用struct與使用class具有相同效果。
由此可知，C++'s struct (New Data Structures) = C's struct(Old Data Structures) + Algorithms(implement in MemberFunctions)。正由於有此轉變，因此新型態的資料結構已經不能再以文字上的意義－「結構」來解釋，它還應該包含了運算。因此是更高層次抽象化的結果。
抽象類別、介面與資料結構的抽象化描述(待續..)
讓我們檢視Algorithms + Data Structures = Programs之名言，在此名言中，資料結構代表的可說是結構化後的資料，但光有資料結構是無法運作的，因此需要演算法使得程式變成是「活」的。舉例來說，光是組織一艘航空母艦是不能完成工作的，必須有前進演算法，使得航空母艦能夠前進。然而戰鬥機也有前進演算法，明顯地，它與航空母艦的前進演算法應該不同，因此，這些演算法應該只侷限於該個體使用。
物件導向程式語言提供了以class類別來撰寫程式的新思維，藉由類別生成的物件實體之互動來達到程式設計之目的。而C++的類別與C語言的結構最大的差別在於，類別除了能夠組織資料，還能夠宣告所屬運算以及設計運算的細節。例如C語言的結構只能宣告「航空母艦」結構、「戰鬥機」結構，而C++的類別，不但能宣告「航空母艦」類別、「戰鬥機」類別，並且這些類別內還可以包含「前進」、「左彎」、「右彎」等成員函式。
到了Java流行的年代，上述名言可完全改為Programs = Classes，因為Java的每一行程式都必定隸屬於某一個類別中，絕對不會在類別之外。而這與原名言是否有衝突呢？嚴格來說，原名言仍是正確的，只需要小幅修正，因為此階段的資料結構已經包含了運算以及實現運算的演算法。換句話說，在純物件導向的程式設計中，Programs = Data Structures = Classes。
更明確地來說，兩者的Data Structures意函並不完全相同，如下整理：
1975~1995年：Programs(in Proc) = Algorithms + Old Data Structures
1995~20xx年：Programs(in OOP) = New Data Structures = Classes
而New Data Structures= Algorithms + Old Data Structures
struct關鍵字可用來觀察上述的時代演變。在C++的程式設計中，建議以類別方式來設計程式，但C++的struct結構體也可以如class類別般宣告成員函式，只不過預設的保護等級不同而已。換句話說，如果我們明確地宣告各成員的保護等級時，則使用struct與使用class具有相同效果。
由此可知，C++'s struct (New Data Structures) = C's struct(Old Data Structures) + Algorithms(implement in MemberFunctions)。正由於有此轉變，因此新型態的資料結構已經不能再以文字上的意義－「結構」來解釋，它還應該包含了運算。因此是更高層次抽象化的結果。
抽象類別、介面與資料結構的抽象化描述(待續..)
2009年10月5日 星期一
1.1.1 資料與結構化
杜林獎（Turing Award；相當於計算機科學的諾貝爾獎）得獎人Nicklaus Wirth大師曾於1975年出版一本名為Algorithms + Data Structures = Programs的著作，說明程式是由「演算法」與「資料結構」組成。
在1995年之前，上述名言可精確描述程式的內容，其中，演算法指的是程式的邏輯之處，也就是如何組織各種指令完成程式之目的，而資料結構則指的是將各種資料組織結構化後作為一個個體來使用。
在此階段，「資料結構」視為「資料」的結構，因此造就此一名詞。就如同現實物體的結構般，我們想要生產一架戰鬥機，首先必須了解戰鬥機的結構，想要生產一輛戰車，則必須了解戰車的結構。而戰鬥機與戰車都是一些實際存在於世界上的武器物體，因此，若有一門名為「武器結構」的課程，則該課程將會先介紹何謂戰鬥機、何謂戰車、何謂航空母艦等等，以及介紹這些武器的內部結構。更進一步者，還可能會介紹其下的改良品，例如隱形戰鬥機。
要理解什麼是武器是非常容易的，而想要理解資料結構的「資料」，似乎有些困難。請回顧您在C語言課程中是如何設計程式的，我們通常會在程式中，使用int,double,char等宣告一些資料項目，然後對這些資料項目進行運算以完成工作。這些資料項目是資料結構嗎？嚴格來說，並不是，因為它們沒有一個系統化的組織，通常是想到需要什麼資料項，就宣告該資料項（例如迴圈需要一個迴圈變數i，就宣告一個i整數變數），並沒有更高一層的意義。
不過有兩個特例，即「陣列」與「結構」。在C語言程式設計中，我們可以利用陣列來存放多個相同意義的資料，例如int Month[12];。每一個陣列元素代表一個月份的收入，所有的陣列元素合起來就是整年的收入。
更明顯者，則是C語言的結構（或稱結構體），C語言允許我們利用struct宣告一個結構體，組織各種不同的資料（struct關鍵字源自於英文的structure）。例如我們可能會宣告學生成績結構體，當中可包含學生姓名、學生學號、平均成績等。此時，我們可以將之視為「學生成績」資料的結構，但這種資料結構通用性不大，可能只應用於您所設計的程式，所以別人不需要理解。而在本書中，我們將介紹「堆疊」資料的結構、「佇列」資料的結構、「樹」資料的結構等等。這些種類的資料結構就常被使用在計算機科學的應用中，因此資訊相關科系的學生必須理解，以利於其他課程的教學及未來的應用。
假設我們已經將學生的成績存入我們宣告的結構體中，而現在要求以平均成績為準，遞減輸出各學生的資料時，我們就需要對此結構體進行排序，而排序有許多種方法，這些方法的細節就是「演算法」。換句話說，只有資料結構而無演算法，則程式無法達到目的，就如同現在收到一個任務，要求轟炸機前往甲地轟炸，則光有轟炸機並無法達到目的，還必須讓轟炸機起飛、前進抵達目的地、放下炸彈才能達到目的。而要讓轟炸機起飛有一定的操作順序，這些操作順序就是轟炸機起飛的演算法。
資料結構化與程式開發效率
沒有資料結構只有演算法是否能夠撰寫程式呢？當然還是可以的，不過開發程式時較無效率。撰寫程式的過程就如同堆積木般，因此，我們以「樂高」積木來作比喻。
假設我們想要以樂高完成一艘航空母艦，我們可以利用一塊塊的小型樂高積木慢慢堆積並完成航空母艦的外觀，而此時若想要在其甲板上放置『戰鬥機』，則可以同樣慢慢以樂高拼湊出戰鬥機的外觀（當中可能需要使用各種基本樂高積木，包含長條形、方形、甚至是輪胎），然後放到甲板上，不過這樣頗為費時。樂高公司為了方便玩家，後來直接推出了『戰鬥機』樂高積木，如此，我們只要購買多架的『戰鬥機』，然後放置到甲板上即可。
樂高公司推出的『戰鬥機』積木並非一體成型的，此『戰鬥機』積木事實上是結構化的樂高積木，因為它包含了多種基本的樂高積木。只不過當我們設計航空母艦時，會將這些『戰鬥機』視為一個個體來看待並使用。
在C語言的程式設計中，int,char,double等種類的資料變數就像是這些基本的樂高積木，而C語言的struct結構體可以將眾多不同型態的資料組織在一起成為一個個體，因此，我們可以將『戰鬥機』樂高積木視為struct plane結構體，事先建立，並且在需要時直接取用即可。由此可知，資料經由結構化之後，將有助於程式的設計。
1.1.2 資料與抽象化(下一篇)
在1995年之前，上述名言可精確描述程式的內容，其中，演算法指的是程式的邏輯之處，也就是如何組織各種指令完成程式之目的，而資料結構則指的是將各種資料組織結構化後作為一個個體來使用。
在此階段，「資料結構」視為「資料」的結構，因此造就此一名詞。就如同現實物體的結構般，我們想要生產一架戰鬥機，首先必須了解戰鬥機的結構，想要生產一輛戰車，則必須了解戰車的結構。而戰鬥機與戰車都是一些實際存在於世界上的武器物體，因此，若有一門名為「武器結構」的課程，則該課程將會先介紹何謂戰鬥機、何謂戰車、何謂航空母艦等等，以及介紹這些武器的內部結構。更進一步者，還可能會介紹其下的改良品，例如隱形戰鬥機。
要理解什麼是武器是非常容易的，而想要理解資料結構的「資料」，似乎有些困難。請回顧您在C語言課程中是如何設計程式的，我們通常會在程式中，使用int,double,char等宣告一些資料項目，然後對這些資料項目進行運算以完成工作。這些資料項目是資料結構嗎？嚴格來說，並不是，因為它們沒有一個系統化的組織，通常是想到需要什麼資料項，就宣告該資料項（例如迴圈需要一個迴圈變數i，就宣告一個i整數變數），並沒有更高一層的意義。
不過有兩個特例，即「陣列」與「結構」。在C語言程式設計中，我們可以利用陣列來存放多個相同意義的資料，例如int Month[12];。每一個陣列元素代表一個月份的收入，所有的陣列元素合起來就是整年的收入。
更明顯者，則是C語言的結構（或稱結構體），C語言允許我們利用struct宣告一個結構體，組織各種不同的資料（struct關鍵字源自於英文的structure）。例如我們可能會宣告學生成績結構體，當中可包含學生姓名、學生學號、平均成績等。此時，我們可以將之視為「學生成績」資料的結構，但這種資料結構通用性不大，可能只應用於您所設計的程式，所以別人不需要理解。而在本書中，我們將介紹「堆疊」資料的結構、「佇列」資料的結構、「樹」資料的結構等等。這些種類的資料結構就常被使用在計算機科學的應用中，因此資訊相關科系的學生必須理解，以利於其他課程的教學及未來的應用。
假設我們已經將學生的成績存入我們宣告的結構體中，而現在要求以平均成績為準，遞減輸出各學生的資料時，我們就需要對此結構體進行排序，而排序有許多種方法，這些方法的細節就是「演算法」。換句話說，只有資料結構而無演算法，則程式無法達到目的，就如同現在收到一個任務，要求轟炸機前往甲地轟炸，則光有轟炸機並無法達到目的，還必須讓轟炸機起飛、前進抵達目的地、放下炸彈才能達到目的。而要讓轟炸機起飛有一定的操作順序，這些操作順序就是轟炸機起飛的演算法。
資料結構化與程式開發效率
沒有資料結構只有演算法是否能夠撰寫程式呢？當然還是可以的，不過開發程式時較無效率。撰寫程式的過程就如同堆積木般，因此，我們以「樂高」積木來作比喻。
假設我們想要以樂高完成一艘航空母艦，我們可以利用一塊塊的小型樂高積木慢慢堆積並完成航空母艦的外觀，而此時若想要在其甲板上放置『戰鬥機』，則可以同樣慢慢以樂高拼湊出戰鬥機的外觀（當中可能需要使用各種基本樂高積木，包含長條形、方形、甚至是輪胎），然後放到甲板上，不過這樣頗為費時。樂高公司為了方便玩家，後來直接推出了『戰鬥機』樂高積木，如此，我們只要購買多架的『戰鬥機』，然後放置到甲板上即可。
樂高公司推出的『戰鬥機』積木並非一體成型的，此『戰鬥機』積木事實上是結構化的樂高積木，因為它包含了多種基本的樂高積木。只不過當我們設計航空母艦時，會將這些『戰鬥機』視為一個個體來看待並使用。
在C語言的程式設計中，int,char,double等種類的資料變數就像是這些基本的樂高積木，而C語言的struct結構體可以將眾多不同型態的資料組織在一起成為一個個體，因此，我們可以將『戰鬥機』樂高積木視為struct plane結構體，事先建立，並且在需要時直接取用即可。由此可知，資料經由結構化之後，將有助於程式的設計。
1.1.2 資料與抽象化(下一篇)
1.1 何謂資料結構
何謂「資料結構」？這是一個基本問題，也是最廣泛的問題，事實上，在不同的時代中，對於此問題，也存在著不同的答案。在本節中，我們將以不同的角度來說明何謂「資料結構」。
「資料結構」是電腦程式設計中，常使用的資料項目，而資料結構之課程的目的在於介紹這些資料項目。這些資料項目包含「串列」、「樹」、「圖」等等，當進行程式設計時，我們常常需要取用這些資料結構來完成應用的設計，舉例如下：
資料結構應用一：樂透歷史記錄
假設我們需要記錄樂透開獎之歷史記錄，也需要將各期獎號進行遞增排序，則可以使用「陣列」這種資料結構來完成，因為陣列可以依照順序存放多個相同的資料型態，例如整數，並且新型態的陣列（例如C#的陣列）也提供了排序功能。
資料結構應用二：GPS
GPS衛星定位導航系統是目前常見的車用電腦設備，假設我們要從高雄出發抵達宜蘭，則GPS能夠找出一條最短行程作為建議並引導您如何前進。而GPS事實上是將實際地圖轉化（或抽象化）為資料結構的「加權圖」，並藉由「最短路徑」運算找出最短行程。由實際的經驗可知，GPS提供的路徑常常會出現各種問題，例如有時會帶您走崎曲的山路或嚴重塞車的路段，這些問題是由於將實際地圖(Map)轉化為加權圖(Weighted Graph)時，考量的因素不夠所導致。
資料結構應用三：資料庫
假設我們需要儲存全台灣的人口資料並能夠快速尋找所需資料。大量資料一般會使用資料庫來存放，而為了要讓搜尋資料能夠快速完成，通常會製作索引，而資料庫的索引則通常使用「B+樹」這種資料結構來設計。
如果您只學習過一般的程式設計，則以上的三個範例，您可能了解何謂「陣列」，但並不了解「加權圖」與「B+樹」。而此時若要您設計一個GPS系統，就會不知如何下手，因此，本書與「資料結構」或「演算法」之課程的目的，就是讓您了解各種資料結構以及了解各種運算應該如何設計。因此，在本書中，我們不但會介紹何謂「加權圖」與「B+樹」，也會介紹如何在「加權圖」中尋找「最短路徑」。除此之外，我們也會讓您對於「陣列」有更深一層的認識。
1.1.1 資料與結構化(下一篇)
「資料結構」是電腦程式設計中，常使用的資料項目，而資料結構之課程的目的在於介紹這些資料項目。這些資料項目包含「串列」、「樹」、「圖」等等，當進行程式設計時，我們常常需要取用這些資料結構來完成應用的設計，舉例如下：
資料結構應用一：樂透歷史記錄
假設我們需要記錄樂透開獎之歷史記錄，也需要將各期獎號進行遞增排序，則可以使用「陣列」這種資料結構來完成，因為陣列可以依照順序存放多個相同的資料型態，例如整數，並且新型態的陣列（例如C#的陣列）也提供了排序功能。
資料結構應用二：GPS
GPS衛星定位導航系統是目前常見的車用電腦設備，假設我們要從高雄出發抵達宜蘭，則GPS能夠找出一條最短行程作為建議並引導您如何前進。而GPS事實上是將實際地圖轉化（或抽象化）為資料結構的「加權圖」，並藉由「最短路徑」運算找出最短行程。由實際的經驗可知，GPS提供的路徑常常會出現各種問題，例如有時會帶您走崎曲的山路或嚴重塞車的路段，這些問題是由於將實際地圖(Map)轉化為加權圖(Weighted Graph)時，考量的因素不夠所導致。
資料結構應用三：資料庫
假設我們需要儲存全台灣的人口資料並能夠快速尋找所需資料。大量資料一般會使用資料庫來存放，而為了要讓搜尋資料能夠快速完成，通常會製作索引，而資料庫的索引則通常使用「B+樹」這種資料結構來設計。
如果您只學習過一般的程式設計，則以上的三個範例，您可能了解何謂「陣列」，但並不了解「加權圖」與「B+樹」。而此時若要您設計一個GPS系統，就會不知如何下手，因此，本書與「資料結構」或「演算法」之課程的目的，就是讓您了解各種資料結構以及了解各種運算應該如何設計。因此，在本書中，我們不但會介紹何謂「加權圖」與「B+樹」，也會介紹如何在「加權圖」中尋找「最短路徑」。除此之外，我們也會讓您對於「陣列」有更深一層的認識。
1.1.1 資料與結構化(下一篇)
訂閱：
文章 (Atom)
