《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》
作者: [美]Ellis Horowitz 霍羅維茲
譯者: 朱仲濤
出版社: 清華大學(xué)出版社
ISBN: 9787302186960
在 豆瓣讀書 中查看本書
數(shù)據(jù)類型
- 定義：數(shù)據(jù)類型是 數(shù)據(jù)對象 和 施加在數(shù)據(jù)對象上操作 的聚合體。
- 操作可以是前綴算符，如
atoi，或中綴算符，如+。 - 將數(shù)據(jù)對象的表示格式隱藏，提供接口處理數(shù)據(jù)對象。操作接口不變，但卻可以修改表示方法。
抽象數(shù)據(jù)對象
- 定義：抽象數(shù)據(jù)類型（ADT）中的 數(shù)據(jù)對象和數(shù)據(jù)操作的規(guī)范聲明 與 數(shù)據(jù)對象的表示和數(shù)據(jù)操作的實現(xiàn) 相互分離。
- C語言并未明顯地提供實現(xiàn)ADT的機制，但仍可利用C語言的現(xiàn)有機制構(gòu)造類似的數(shù)據(jù)類型。
- 抽象數(shù)據(jù)類型應(yīng)獨立于實現(xiàn)。
- 常用ADT至少包括以下類別中的一種函數(shù)：
- 構(gòu)造函數(shù)/創(chuàng)建函數(shù)：這類函數(shù)為特定類型創(chuàng)建新實例。
-
變換函數(shù)：這類函數(shù)也為特定類型創(chuàng)建實例，但通常使用一個或多個其他實例。
變換函數(shù)與構(gòu)造函數(shù)的差別。 - 觀察函數(shù)/報告函數(shù)：這類函數(shù)提供數(shù)據(jù)類型的實例信息，但不修改實例。
定義ADT
示例
定義ADT NaturalNumber（摘自《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》P16）
解釋
- 該自然數(shù)抽象數(shù)據(jù)類型，從定義關(guān)鍵字
ADT開始，主要內(nèi)容分兩節(jié)：數(shù)據(jù)對象 和 成員函數(shù)。 - 數(shù)據(jù)對象是計算機系統(tǒng)中的整數(shù)類型，但此時并未顯式指明整數(shù)的表示。
- 定義新的數(shù)據(jù)類型，可能會用到其他數(shù)據(jù)類型的操作。
- 每個成員函數(shù)的形式為：返回結(jié)果類型 函數(shù)名稱 定義
- 符號
::=的意思是“定義為”。 - 第一個函數(shù)的名稱是
Zero，無參量，返回自然數(shù)0，是構(gòu)造函數(shù)。 - 函數(shù)
Successor(x)返回自然數(shù)序列中x的下一個，是變換函數(shù)。
如果數(shù)列中不再有后繼元素，即x就是INT_MAX的話，函數(shù)返回INT_MAX。有些程序員這時傾向于返回出錯信息，也可以。
習(xí)題
- 為自然數(shù)ADT加上如下成員函數(shù)：Predecessor,IsGreater,Multiply,Divide。（前驅(qū)，大于，乘法，除法）。
習(xí)題1 -by Cytosine
