第八章 生成數(shù)據(jù)
這一章是講如何有效生成數(shù)據(jù)。
好的數(shù)據(jù)結構所帶來的收益往往是在需求分析和結構設計階段體現(xiàn)出來的。為了盡可能地利用好的數(shù)據(jù)結構帶來的收益，應在需求分析和結構設計階段就定義主要數(shù)據(jù)結構。
8.1 數(shù)據(jù)識別
有效生成數(shù)據(jù)的第一步是應該知道該生成什么樣的數(shù)據(jù)結構。
- 線性表
- 數(shù)組實現(xiàn)
- 鏈表
- 棧與隊列
- 樹與二叉樹
- 樹
- 二叉樹基本概念
- 二叉查找樹
- 平衡二叉樹
- 紅黑樹
- 圖
8.2 自建數(shù)據(jù)類型的原因
程序語言所賦予你的闡明自己對程序理解的最強有力的工具之一便是程序員定義的變量類型。它們可以使程序更容易閱讀。
建立自己的類型的幾條理由：
- 使得改動更加容易。建立一種新類型工作量極小，但這卻可以帶來極大的使用靈活性。
對于一個浮點數(shù)
Coordinate_t，你認為可能會用到雙精度浮點數(shù)，但是在十分確定之前，你只想用單精度浮點數(shù)。可以專門定義一種變量。
typedef float Coordinate_t；
現(xiàn)在，假設程序發(fā)生了變化，發(fā)現(xiàn)最終還是得用雙精度變量。由于專門定義了一種類型，因此所要做的就是改變一下類型定義而已。而且只需在一個地方進行改動.
- 為了增加可靠性。
在 Ada 和 Pascal 中，可以定義類似
Age_t = 1~99的類型。然后，編譯程序會產生運行檢查信息，以保證Age_t類型總是在 1~99 的范圍內。
- 為了補償語言的弱點。
C 中不含邏輯類型，通過建立你自己的類型，很容易彌補這個缺點：
typedef int Boolean_t;
8.3 自建數(shù)據(jù)類型的準則
建立具有面向功能名稱的類型
應避免用暗指計算機本身數(shù)據(jù)類型的名稱,要使用代表實際問題某一部分的名稱。
要避免使用含有已定義變量類型的名稱
比如像 BigInteger 和 LongString 等指的是計算機數(shù)據(jù)而不是客觀世界中實體的名稱就應避免使用。
避免使用已定義類型
如果類型存在變動的可能性，那么除了在 typedef 和 type 定義之外，不要再使用已定義的類型。建立面向功能的類型是非常容易的，而改變程序中該類型的數(shù)據(jù)是非常困難的。而且，當使用自建的面向功能類型說明變量時，也同時對變量進行了說明。Coordinate_x 所告訴你的關于 x 的信息要比 float x 多得多。因此應盡可能使用自建類型。
不要對已定義類型重新定義
例如，語言中已經有了Integer 類型，而你又自建了叫作 Integer 的類型。程序的閱讀者往往會記住你所定義的Integer 的含義，而仍把它當作語言中的標準 Integer 類型。
定義替換類型以增強移植性。
與避免重新定義標準類型的建議相反，你可能想為標準類型定義一種替換類型，從而++使得在不同的硬件環(huán)境下變量所代表的都是同一實體++?。例如，你可以定義 INT 類型來代替標準的 int 類型，它們之間的唯一區(qū)別便是字母的大小寫。但當你把程序移到新的硬件環(huán)境下時，你只要重新定義一個 INT 類型，就可以在新的硬件環(huán)境下使得數(shù)據(jù)類型與舊環(huán)境下相容。
使用其它類型來建立新類型
可以在已經建立的簡單類型的基礎上建立復雜類型。這種變量類型可以進一步推廣你用原來類型所達到的靈活性。
8.4 使變量說明更容易
使用模板（template）進行變量說明
在一個文件中存儲一個變量說明模板。需要說明新的變量時，你可以把這個模板調入程序，對其進行編輯以說明新變量。下面是用 C 寫成的一個模板：
extern * *; /* */
static * *; /* */
* *; /* */
extern告訴編譯器這個變量或函數(shù)在其他文檔里已被定義了。
這個模板有幾個優(yōu)點。首先，很容易從中選擇出與你要求最接近的行，然后刪掉其余各行；第二，每行中“*”的作用是占有位置，這使得進入每行的編輯位置都非常容易；第三，如果你忘記了更改“*”，那么一定會產生語法錯誤，從而起到了提醒的作用；第四，使用模板可以保持說明形式的一致性；最后，預留的注釋空格將提醒你在說明變量時進行注釋，這簡化了以后的程序注釋工作。
隱式說明
有些語言具有隱含變量說明功能。
隱式說明是所有語言特性中的最具危害性的特性之一。
比如說在js代碼中的某一行，我想使用的一個已聲明的變量x，結果由于打字或者拼寫錯誤，這個變量被寫成y了，結果相當于“隱式”聲明了一個變量y，這種錯誤有時比較難以發(fā)現(xiàn)。
要求你對變量進行顯式說明的語言其主要優(yōu)點之一，便是可以使你在使用變量時更加謹慎。
8.5 初始化數(shù)據(jù)的準則
在編程中，最大的錯誤原因之一便是對數(shù)據(jù)不恰當?shù)某跏蓟?/strong>
下面是如何避免初始化錯誤的一些準則：
- 檢查輸入?yún)?shù)的有效性。
在賦給輸入?yún)?shù)任何值之前，要首先確認它是合理的。
- 在使用變量的位置附近對其進行初始化
防止改動后忘記初始化
- 要特別注意計數(shù)器和累加器
常見的錯誤是在下次用到它們時，忘記了對其進行清零操作。
- 查找需要重新進行初始化的地方
重新初始化的原因可能是由于變量在循環(huán)中被用過多次，也可能是由于變量在對子程序的調用中間要保持原值且需清零。如果需要重新初始化的話，要確保初始化語句是在被重復的代碼段中。
- 對命名常量只初始化一次，用可執(zhí)行代碼初始化變量
應在使用變量的位置附近的可執(zhí)行代碼對其進行初始化。
- 按照所說明的對每個變量進行初始化
- 利用編譯程序的警告信息
- 設置編譯程序使其自動初始化所有變量
- 使用內存存取檢查程序來查找無效的指針
在某些操作系統(tǒng)中，操作系統(tǒng)會自動查找無效指針，也可以買一個內存存取檢查程序來檢查程序中的指針操作。
Coverity代碼靜態(tài)檢測工具
- 列出不會被執(zhí)行到的代碼
- 列出沒被初始化的類成員變量
- 列出沒有被捕獲的異常
- 列出沒有給出返回值的return語句
- 某個函數(shù)雖然有返回值，但調用該函數(shù)的地方沒有用到它的返回值，這也會被列出來
- 列出沒有被回收的new出來的對象
- 列出沒有被關閉的句柄
- 精確定位到代碼行，并提供逐層展開函數(shù)的功能
- 列出可能的數(shù)值類型溢出。例如，無符號int數(shù)做 ++ 操作，可能導致int溢出，都會被檢測到。
- 什么地方該用&位運算，而不應該用|位運算，都能定位出來并作出建議
- ostream在一個函數(shù)中被修改了格式，但退出該函數(shù)之后沒有將ostream恢復成先前的格式，也會被檢測到
- .....
- 在程序開始初始化工作內存
小結
- 推薦準備一張全部數(shù)據(jù)結構的清單，以便用最合適的方法處理每一種問題。
- 建立自己的數(shù)據(jù)類型，以增加程序的可變動性，并使其成為自說明的。
- 數(shù)據(jù)初始化很容易產生錯誤，避免由于未初始值所產生的錯誤。
