TOCEC
資訊學群
總評比分數: 4.54 顆星

Open Data Structures: An Introduction


本書作者:Pat Morin
出版年份:2013

書評教師:淡江大學 資訊工程學系 王英宏 教授

【總評】

整體評價:
本書是資訊相關科系必修的資料結構(Data Structure)課程用書,內容包含循序資料結構之Array、Linked List、以及Linked List的變化應用,階層式資料結構之Binary Tree、Binary Search Tree、以及Binary Tree的變化應用,網狀式資料結構之Graph等特定主題。本書的最後二章則是分別探討程式開發如何處理超長整數(超過最大記憶體存取單元長度)的資料結構,以及外部記憶體資料搜尋問題的資料結構應用。每個章節適當地展示以Java語言所編寫的程式函式範例,並且,在每一章(Chapter)的最後一節提出開放性與延伸性的討論問題與練習題(Discussion and Exercises)。本書作者同時以開源碼(Open Source)的型式架構本書所有的原始程式碼,包含以C、C++、Java三種語言分別開發的原始程式碼,提供以創用CC(Creative Commons)屬性授權方式授權使用者進行運用或改寫,同時也開放任何有興趣的程式開發者在本書專屬的開源碼網站一起貢獻或修正相關的原始程式碼。
【分項評比】

完整性(Comprehensiveness):
此開放式教科書(Open textbook)是資訊相關科系的必修課程,資料結構之學習範疇。本書書名特別標榜Open Data Structure,強調它的開放性,它不僅開放書本的圖文內容,並建立了本書的專屬非營利性網站http://opendatastructures.org,書本中所有的程式碼範例,除了在前述作者建立的專屬網站外,也同時放置於具可靠性的原始碼管理網站https://github.com/patmorin/ods,提供下載。
不過,由於資料結構(Data Structure)範疇廣泛,作者對於資料結構應該講授的範圍有個人的認知,認為有一些主題,例如AVL tree(平衡樹),是較老舊的主題,故不在本書編輯範圍。
不過,除了作者認定的老舊主題範疇未被納入本書教材外,作者對於Singly Linked List的主題與資料存取操作直接就從Stack與Queue的課題切入,缺少依儲存資料值(Data value)大小循序排列與存取操作的介紹,無法用以對照Linked List與Array二種做為循序性資料(Sequential data)的資料結構與資料存取操作的差異及優劣比較。
再者,本書對於圖形結構(Graph)也缺少具權重值的圖形結構(Weight graph)相關主題,是以缺少如Minimal Cost Spanning Tree與Shortest Path等圖形結構的應用課題與相關操作演算法。
內容正確性(Content Accuracy):
本書對於相關的資料結構主題,例如Array Stack、Array Queue、Singly List Stack、Singly Queue、Doubly Linked List、Hash Table Functions等等皆賦予對應的資料結構宣告(以Java語言為例的Class宣告),以及操作指令的函式(Function)。對於必要的定理、複雜度分析,也都適時地提供證明與推算論述。
一致性(Consistency):
本書每一章有一個資料結構課程的專屬主題,每一個主題所使用的專業名詞(Terminology)、程式範例的類別名稱(Class title)、函式名稱(Function title)、資料型別(Datatype)、變數(Variable)均具一致性。
不同的章節之間,包含有跨章節關聯性的觀念、型別結構,例如Linked List與Tree都有的Node、Link,或是Tree與Graph都有的Traversal、Search等等,以及電腦科學總體性的知識等亦皆具一致性。
清晰性(Clarity):
從下載的教科書PDF檔閱覽此開放式教科書,本書的印刷清晰,文筆清楚流暢,公式與圖表內含的文字、線條、方向標記,程式範例的結構化層次等皆能清楚呈現,雖全書僅以黑白為主體呈現,但仍可清晰表達,足以讓閱讀者一目瞭然。
組織結構流暢度(Organization Structure Flow):
此開放式教科書的組織架構尚稱流暢,每章各小節均是循序漸進解說,介紹完一個主題與程式範例後,再進入另一個主題,條理分明,每一章的最後則以討論與練習(Discussion and Exercises)綜覽整個主題在程式開發的應用與延伸議題,循序漸進逐步建構學習者對每一個單元主題觀念的理解。
各章之間大體上也保有資料結構由簡入繁的漸進式解說,例如,從Array進入Singly Linked List,再到Doubly Linked List,接著再進入Binary Tree與Graph等主題。
不過,本書對於Hash Table and Functions的介紹是安排於Linked List之後,第5章,Binary Tree之前;各類排序演算法(Sorting Algorithms)則是安排於Heaps之後,第11章,Graph之前。這樣的章節組織對於Hash相較於Sorting,可以更有效率的方法用於處理資料儲存安排與存取之對照就無法彰顯。
語法誤差度(Grammatical Errors):
本書英語敘述流暢,用詞扼要,英語時態適切。學習者應能快速掌握課本內容,每一個章節都有大標題,次標題,協助學習者可以迅速找出所欲加強了解與學習的主題領域。
文化相關性(Cultural Relevance):
資訊科技與電腦科學源於美國,擴展於全球,本書所涉及之電腦硬體結構、記憶體組成、程式語言的指令與語法皆屬全球性共通,故無文化差異問題。
模組性(Modularity):
本書每章皆以一個資料結構的學習主題為界定,每章再以數個小節循序從基本的定義、程式設計宣告方式、操作方法邏輯描述、函式指令設計範例等,隨後再衍伸此一資料結構的應用與操作。例如第2章為Array-based List、第3章為Linked List、第4章為Skiplists等,第3章的小節則再細分為3.1 A Singly-Linked List、3.2 A Doubly-Linked List、3.3 A Space-Efficient Linked List等,全書架構相當具有模組性。
Relevance Longevity(銜接新知之容易度-教科書內容之敘述方式、範例或時事等…):
本書對於資料結構相關主題的觀念與邏輯敘述扼要簡明,對應的程式範例採個別化函式逐一對照與循序串連,另於本書的專屬網站提供完整的程式範例。對於學習者銜接新知的歷程可以循序漸進地進行。
Interface(介面之適用性-是否因為不同瀏覽器或不同行動載具,而格式不正確或圖片扭曲):
本書內文採PDF下載閱讀,不會因瀏覽器與上網載具的差異而有使用介面上的差異,學習者可以全書下載,亦可從本書專屬網頁的目錄,點選個別的章節下載。下載後才能閱覽章節或全書內容,不從網頁直接開啟電子書內容。
開啟後的PDF檔內容,文字、文字圖表格式均正常,不會有格式跑掉或圖片不清的問題。
專業程度(Professional knowledge):

由於資訊科技的範疇廣泛,程式設計與軟體開發的專業知識科目未必能有一致性的分割界定標準,涵蓋內容或許見仁見智,是以誠如前完整性項目所提及,部分常見的資料結構單元,例如AVL tree、Insertion Sort、Bubble Sort等題材並未被涵蓋在本書教材內。
不過,若就Singly-Linked List之基礎結構觀念與基本資料存取操作議題、圖形結構於具權重值的議題與應用,例如Minimal Cost Spanning Tree、Shortest Paths等,在本書並未被納入。
再者,本書雖然在第1章有介紹到Asymptotic Notation與Big-Oh的定義,但是在隨後的個單元中,相關的演算法與函式範例,例如不同的排序方法Merge Sort與Radix Sort或使用Adjacency Matrix與Adjacency List在Spanning Tree演算法上,對應於計算效能(Performance)也就是Big-Oh的差異比較則是完全未提。
是以,上述的不完整性可能無法讓學習者透過資料結構課程的學習深切了解到資料結構與演算法的應用對於程式設計與軟體開發所造成的影響。

教學資源(Supplementary Resources):
本電子書設有專屬非營利性網站http://opendatastructures.org,書本中所有的程式碼範例,除了在前述作者建立的專屬網站外,也同時放置於具可靠性的原始碼管理網站https://github.com/patmorin/ods,提供下載。
本書每一章的最後皆討論與練習(Discussion and Exercises)讓學習者複習與確認全章學習的重點與自我評估學習成效。
不過,稍有不足之處乃本書並未提供練習題Exercise的參考解答,是以對於使用本書自學的學習者而言,會有不確定是否正確學習的問題。

Go to open textbook
https://open.umn.edu/opentextbooks/textbooks/open-data-structures-an-introduction