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)。正由於有此轉變,因此新型態的資料結構已經不能再以文字上的意義-「結構」來解釋,它還應該包含了運算。因此是更高層次抽象化的結果。

抽象類別、介面與資料結構的抽象化描述(待續..)

陳錦輝著作列表


陳錦輝著作如下(含規劃、審校)

76. "大話重構", 博碩文化, 2015(審校)
75. "掌握Java SE8程式設計──Lambda的逆襲", 博碩文化, 2015.
74. "ASP.NET 4.5.1 初學指引[2] ── 使用Visual Basic 2013 : 網頁資料庫超簡單", 博碩文化, 2014.
73. "ASP.NET 4.5.1 初學指引[1] ── 使用Visual Basic 2013 : 網頁開發快速上手", 博碩文化, 2014.
72."我的程式碼會說話", 博碩文化, 2014.(審校)
71."C++沉思錄 (Ruminations on C++: a Decade of Programming Insight and Experience) , 博碩文化, 2014.(審校)
70. "Arduino完全實戰手冊 (Arduino in action) , 博碩文化, 2014.(審校)
69. "HBase:搞定BigData ── NoSQL實戰 (HBase in action) , 博碩文化, 2014.(審校)
68. "Kent Beck 的實作模式" (Implementation Patterns) , 博碩文化, 2013.(審校)
67. "無瑕的程式碼──番外篇──專業程式設計師的生存之道" (The Clean Coder: A Code of Conduct for Professional Programmers) , 博碩文化, 2013.(審校)
66. "計算機概論──邁向資訊第四版", 博碩文化, 2013.(合著)
65. "計算機概論──探索未來第八版", 博碩文化, 2013.(合著)
64. "無瑕的程式碼 ── 敏捷軟體開發技巧守則" (Clean Code: A Handbook of Agile Software Craftsmanship) , 博碩文化, 2013.(審校)......天瓏書局2013年銷售總冠軍
63. "資料結構初學指引-入門精要版", 博碩文化, 2012.

62. 求職加分!進入IT產業必讀的324個 Java面試決勝題:從求職準備、面試流程、開發心得、重點回顧到經典試題的完整剖析, 博碩文化, 2012.(審校)
61. "計算機概論-邁向資訊2013", 博碩文化, 2012.(合著)
60. "計算機概論-探索未來2013", 博碩文化, 2012.(合著)
59. "Java初學指引 - 使用SE7", 博碩文化, 2011.
58. "ASP.NET 4.0初學指引 - 使用Visual Basic 2010", 博碩文化, 2011.

57. "計算機概論-邁向資訊2012", 博碩文化, 2011.(合著)
56. "計算機概論-探索未來2012", 博碩文化, 2011.(合著)

55. "C語言初學指引", 第四版 博碩文化, 2011.



54. "最新 ASP.NET 3.5初學指引 - 使用Visual Basic 2008", 文魁行銷, 2010.
53. "新世紀計算機概論2011", 文魁行銷, 2010.(合著)
52. "計算機概論-邁向資訊2011", 博碩文化, 2010.(合著)
51. "新視野計算機概論2011", 文魁行銷, 2010.(合著)
50. "計算機概論-探索未來2011", 博碩文化, 2010.(合著)
49. "ASP.NET 3.5初學指引 - 使用Visual Basic 2008", 博碩文化, 2009.
48. "Java初學指引 - 使用SE6", 博碩文化, 2009.
47. "資料結構初學指引 - 使用C語言", 博碩文化, 2008.
46. "C/C++初學指引", 第二版, 博碩文化, 2008.
45. "Visual Basic 6初學指引", 第四版, 博碩文化, 2008.
44. "HTML初學指引", 上奇科技, 2008.
43. "C語言初學指引", 第三版 上奇科技, 2008.
42. "ASP初學指引", 第二版, 博碩文化, 2008.
41. "計算機概論 邁向資訊2010", 博碩文化, 2009.(合著)
40. "計算機概論 探索未來2009", 博碩文化, 2008.
39. "計算機概論 探索未來2008", 金禾資訊, 2007.

38. "C/C++
初學指引", 金禾資訊, 2005.
37. "
電腦概論", 金禾資訊, 2004.(合著)
36. "
計算機概論 探索未來", 金禾資訊, 2004.
35. "ASP
初學指引", 金禾資訊, 2004.
34. "Visual Basic 6
初學指引",第一版、第二版、第三版(修訂版), 金禾資訊, 2004, 2005, 2006
33. "C
語言初學指引",第一版、第二版(修訂版) 金禾資訊, 2003 , 2005.
32. "
計算機概論 掌握未來", 金禾資訊, 2003.(合著)
31. "
專業HTML網頁設計寶典", 金禾資訊, 2003.
30. "C++ Builder 6
完全攻略", 金禾資訊, 2003. (合著)
29. "C/C++
初學指引-Linux程式設計", 金禾資訊, 2003.
28. "Linux C/C++
網路程式設計", 金禾資訊, 2003. (合著)
27. "
專案開發- DELPHI會計系統實作", 金禾資訊, 2003. (規劃)
26. "JDBC
資料庫程式設計", 金禾資訊, 2003. (合著)
25. "300
好題教您學會C/C++", 金禾資訊, 2002. (合著)
24. "Visual Basic 6
學習手冊", 金禾資訊, 2002.
23. "HTML/XHTML
網頁設計寶典", 金禾資訊, 2002.
22. "Linux
常用指令集", 金禾資訊, 2002. (合著)
21. "ASP.NET
設計師入門手冊", 金禾資訊, 2002. (合著)
20. "Linux7.2
建構與實務", 金禾資訊, 2002. (合著)
19. "JSP
設計師入門手冊", 金禾資訊, 2002. (合著)
18. "
超好學Word2002一看就懂", 金禾資訊, 2002.
17. "
超好學Access2002一看就懂", 金禾資訊, 2002.
16. "
超好學 Excel2002一看就懂", 金禾資訊, 2002. (規劃)
15. "
超好學PowerPoint2002一看就懂", 金禾資訊, 2002. (規劃)
14. "
超好學Outlook2002一看就懂", 金禾資訊, 2002.(規劃)
13. "
超好學FrontPage2002一看就懂", 金禾資訊, 2002.(規劃)
12. "XML
ASP網站實作大全", 金禾資訊, 2001
11. "XML
Java程式設計大全", 金禾資訊, 2001(合著)
10. "Delphi6
資料庫程式設計", 金禾資訊, 2001(合著)
9. "PHP4
MySQL程式設計", 金禾資訊, 2001(合著)
8. "Java Swing
程式設計", 金禾資訊, 2001(合著)
7. "C++
函式庫精華錄", 金禾資訊, 2001(規劃)
6. "C/C++
入門與應用", 知城數位, 2001. (合著)
5. "Access
使用寶典", 文魁出版社, 2001. (合著)
4. "Excel
使用寶典", 文魁出版社, 2001. (合著)
3. "Word
使用寶典", 文魁出版社, 2001. (合著)
2. "
HTMLXML", 文魁出版社, 2000.
1.
最新版職訓局丙級技能檢定:電腦軟體應用術科測驗詳解, 文魁出版社, 2000.

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 資料與抽象化(下一篇)

1.1 何謂資料結構

何謂「資料結構」?這是一個基本問題,也是最廣泛的問題,事實上,在不同的時代中,對於此問題,也存在著不同的答案。在本節中,我們將以不同的角度來說明何謂「資料結構」。
「資料結構」是電腦程式設計中,常使用的資料項目,而資料結構之課程的目的在於介紹這些資料項目。這些資料項目包含「串列」、「樹」、「圖」等等,當進行程式設計時,我們常常需要取用這些資料結構來完成應用的設計,舉例如下:
資料結構應用一:樂透歷史記錄
假設我們需要記錄樂透開獎之歷史記錄,也需要將各期獎號進行遞增排序,則可以使用「陣列」這種資料結構來完成,因為陣列可以依照順序存放多個相同的資料型態,例如整數,並且新型態的陣列(例如C#的陣列)也提供了排序功能。
資料結構應用二:GPS
GPS衛星定位導航系統是目前常見的車用電腦設備,假設我們要從高雄出發抵達宜蘭,則GPS能夠找出一條最短行程作為建議並引導您如何前進。而GPS事實上是將實際地圖轉化(或抽象化)為資料結構的「加權圖」,並藉由「最短路徑」運算找出最短行程。由實際的經驗可知,GPS提供的路徑常常會出現各種問題,例如有時會帶您走崎曲的山路或嚴重塞車的路段,這些問題是由於將實際地圖(Map)轉化為加權圖(Weighted Graph)時,考量的因素不夠所導致。
資料結構應用三:資料庫
假設我們需要儲存全台灣的人口資料並能夠快速尋找所需資料。大量資料一般會使用資料庫來存放,而為了要讓搜尋資料能夠快速完成,通常會製作索引,而資料庫的索引則通常使用「B+樹」這種資料結構來設計。

如果您只學習過一般的程式設計,則以上的三個範例,您可能了解何謂「陣列」,但並不了解「加權圖」與「B+樹」。而此時若要您設計一個GPS系統,就會不知如何下手,因此,本書與「資料結構」或「演算法」之課程的目的,就是讓您了解各種資料結構以及了解各種運算應該如何設計。因此,在本書中,我們不但會介紹何謂「加權圖」與「B+樹」,也會介紹如何在「加權圖」中尋找「最短路徑」。除此之外,我們也會讓您對於「陣列」有更深一層的認識。

1.1.1 資料與結構化(下一篇)