全套電子課件：數(shù)據(jù)結(jié)構(gòu)-第七套

1、數(shù)據(jù)結(jié)構(gòu) C+實現(xiàn)第一章內(nèi) 容 簡 介 數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)教學(xué)計劃中的一門核心課程，也是信息管理、通信電子、自動控制等與計算機(jī)技術(shù)關(guān)系密切的專業(yè)的一門基礎(chǔ)課程。從事與計算機(jī)科學(xué)與技術(shù)相關(guān)的工作， 尤其是計算機(jī)應(yīng)用領(lǐng)域的開發(fā)和研制工作，必須具備堅實的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。 本書對C+語言作了簡單介紹，敘述了抽象數(shù)據(jù)類型和面向?qū)ο蟮母拍?，介紹了線性表、棧、隊列、數(shù)組、廣義表、樹、圖等數(shù)據(jù)結(jié)構(gòu)，并介紹了查找和排序的方法。全書用C+語言描述并實現(xiàn)了所有數(shù)據(jù)結(jié)構(gòu)的類和程序，并附有習(xí)題，便于教學(xué)。 本書是為高等院校開設(shè)數(shù)據(jù)結(jié)構(gòu)課程編著的教材，可供計算機(jī)等專業(yè)，也可供從事計算機(jī)開發(fā)和應(yīng)用的工程技術(shù)人員閱讀參考。

2、 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？ 作為計算機(jī)程序組成部分的數(shù)據(jù)結(jié)構(gòu)和算法的研究，一直受到計算機(jī)領(lǐng)域工作者的高度重視。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)教學(xué)計劃中的一門核心課程，也是信息管理、通信電子、自動控制等與計算機(jī)技術(shù)關(guān)系密切的專業(yè)的一門基礎(chǔ)課程。 要從事與計算機(jī)科學(xué)與技術(shù)相關(guān)的工作，尤其是計算機(jī)應(yīng)用領(lǐng)域的開發(fā)和研制工作，必須具備堅實的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目的 數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目的是使學(xué)生學(xué)會分析研究計算機(jī)所要加工處理的數(shù)據(jù)的特征，掌握組織數(shù)據(jù)、存儲數(shù)據(jù)和處理數(shù)據(jù)的基本方法，并加強(qiáng)在實際應(yīng)用中選擇合適的數(shù)據(jù)結(jié)構(gòu)和相應(yīng)算法的訓(xùn)練。 為什么用面向?qū)ο蟮挠^點來描述數(shù)據(jù)結(jié)構(gòu)？ 面向?qū)ο蠹夹g(shù)是軟件工程領(lǐng)域

3、中的重要技術(shù)，它不僅是一種程序設(shè)計方法，更重要的是一種對真實世界的抽象思維方式。 目前，面向?qū)ο蟮能浖治龊驮O(shè)計技術(shù)已發(fā)展成為軟件開發(fā)的主流方法。為了適應(yīng)軟件開發(fā)方法與技術(shù)的發(fā)展以及應(yīng)用領(lǐng)域的要求，就有必要改進(jìn)和充實數(shù)據(jù)結(jié)構(gòu)的教學(xué)內(nèi)容。 因此，用面向?qū)ο蟮挠^點來描述數(shù)據(jù)結(jié)構(gòu)就成為一種既順理成章又緊迫的選擇。采用C+描述數(shù)據(jù)結(jié)構(gòu) 用面向?qū)ο蟮挠^點來描述數(shù)據(jù)結(jié)構(gòu)，要涉及到面向?qū)ο蟪绦蛟O(shè)計語言的選用問題。 目前被廣泛采用作為程序設(shè)計語言教學(xué)的是C語言，C+是以C語言為基礎(chǔ)的、使用比較普遍的面向?qū)ο蟪绦蛟O(shè)計語言。因此本書采用了C+作為數(shù)據(jù)結(jié)構(gòu)的描述語言。 數(shù)據(jù)結(jié)構(gòu)課程的特點 數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容豐富，學(xué)習(xí)

4、量大； 隱藏在各部分內(nèi)容中的方法和技術(shù)多； 貫穿于全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)令不少初學(xué)者望而生畏。 本書的編寫者長期來從事數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)，對該課程的教學(xué)特點和難點有比較深切的體會。作者的努力 作者在認(rèn)真總結(jié)二十多年講授數(shù)據(jù)結(jié)構(gòu)課程的基礎(chǔ)上參考了美國ACM/IEEE CS所頒布的計算2001教程，吸收了國內(nèi)外各種數(shù)據(jù)結(jié)構(gòu)教材的優(yōu)點，對多年來形成的數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)內(nèi)容進(jìn)行了合理的剪裁，既強(qiáng)調(diào)了數(shù)據(jù)結(jié)構(gòu)的原理和方法，又注重了其實踐性，使之適應(yīng)于現(xiàn)代大學(xué)生的學(xué)習(xí)特點和要求。本書的一個重要特點 本書的一個重要特點就是將程序設(shè)計的基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)的方法盡可能的結(jié)合起來。第一、二章介紹C+語言時盡

5、可能給出比較完整的程序，使學(xué)生能對C+語言有比較全面和深入的了解，也便于上機(jī)實習(xí)，從而為數(shù)據(jù)結(jié)構(gòu)課程的實驗建立良好的基礎(chǔ)。本書的組織結(jié)構(gòu) 全書共分九章，第一、二章介紹了數(shù)據(jù)結(jié)構(gòu)、算法及其復(fù)雜度的基本概念，對C+作了簡單介紹，并敘述了抽象數(shù)據(jù)類型和面向?qū)ο蟮母拍?。第三章至第五章介紹了線性結(jié)構(gòu)線性表、棧、隊列、數(shù)組、廣義表；第六章和第七章介紹了非線性結(jié)構(gòu)樹和圖；第八章和第九章分別介紹了查找和排序的方法。1 緒論1.1（算法+數(shù)據(jù)結(jié)構(gòu)）= 程序 計算機(jī)神通廣大，聰明能干。 計算機(jī)的本領(lǐng)是人是用“程序”來“教” 的。 讓計算機(jī)解題實際上就是為計算機(jī)編程序。因而解題的過程就不僅僅是編程序，而是一個包括編

6、程序在內(nèi)的軟件開發(fā)過程。軟件不僅僅指程序，而是包括程序以及開發(fā)程序的過程中所產(chǎn)生的各種文檔。軟件開發(fā)的目標(biāo)是產(chǎn)生能讓計算機(jī)有效工作的程序，因此程序是軟件的核心。程序到底是什么呢？N.Wirth給出的一個著名的公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序曾經(jīng)產(chǎn)生了深遠(yuǎn)的影響?，F(xiàn)在受到了挑戰(zhàn)。20世紀(jì)90年代，面向?qū)ο蟮姆椒ㄊ艿搅撕艽蟮闹匾?，并得到比較廣泛的推廣和應(yīng)用。在面向?qū)ο蟪绦蛟O(shè)計中，密切相關(guān)的數(shù)據(jù)與過程被定義為一個整體（即對象），而且一旦作為一個整體定義了之后，就可以使用它，而無需了解其內(nèi)部的實現(xiàn)細(xì)節(jié)，從而提高軟件開發(fā)的效率。封裝和數(shù)據(jù)隱藏是面向?qū)ο髥栴}解和面向?qū)ο蟪绦蛟O(shè)計的基本要素。算法+數(shù)據(jù)結(jié)構(gòu)=程序

7、（算法+數(shù)據(jù)結(jié)構(gòu)）= 程序 本書以面向?qū)ο蟮挠^點來介紹各種數(shù)據(jù)結(jié)構(gòu)以及與這些數(shù)據(jù)結(jié)構(gòu)有關(guān)的算法的知識。第一章將介紹數(shù)據(jù)結(jié)構(gòu)以及算法的基本概念，并介紹用來描述數(shù)據(jù)結(jié)構(gòu)和算法的語言C+。1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念計算機(jī)科學(xué)是一門研究信息表示和處理的科學(xué)，人們是用程序來處理信息的。對程序設(shè)計方法進(jìn)行系統(tǒng)的研究。這不僅涉及到研究程序結(jié)構(gòu)和算法，同時也涉及到研究程序加工的對象。用計算機(jī)解題：具體問題 數(shù)學(xué)模型設(shè)計算法和編制程序從對問題的分析中提取操作的對象，并找出這些操作對象之間的關(guān)系，然后用數(shù)學(xué)的語言加以描述。1.2.1 兩個簡單的數(shù)據(jù)結(jié)構(gòu)實例例 1-1 人事登記表 線性數(shù)據(jù)結(jié)構(gòu) 例1-2 一個典型的

8、學(xué)校行政機(jī)構(gòu)層次型數(shù)據(jù)結(jié)構(gòu)1.2.2 什么是數(shù)據(jù)結(jié)構(gòu) 一個水平再高的廚師,盡管他可以把烹調(diào)某個菜肴的過程掌握得很好，但如果不給他原料，他是做不出色、香、味俱全的菜。 “巧婦難為無米之炊”。 對一個程序來講，數(shù)據(jù)就是“原料”。 大千世界中有各種各樣的信息，交通燈，交通卡，交易，思想。這些信息必須轉(zhuǎn)換成數(shù)據(jù)才能在計算機(jī)中進(jìn)行處理。“什么是數(shù)據(jù)”以及與之相關(guān)的概念數(shù)據(jù)（data）：信息的載體， 數(shù)、字符、圖形、圖象、聲音以及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)元素（data element）：數(shù)據(jù)的基本單位。數(shù)據(jù)項（data item）：數(shù)據(jù)的最小單位數(shù)據(jù)對象：數(shù)據(jù)的子集。

9、自然數(shù)集合 =0, 1, 2, 是“數(shù)”的數(shù)據(jù)對象；所有的字符是數(shù)據(jù)，字母集合AS=A, B, Z, a, b, , Z是該數(shù)據(jù)的數(shù)據(jù)對象。 數(shù)據(jù)結(jié)構(gòu)(data structure) ：數(shù)據(jù)以及數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。這兩類結(jié)構(gòu)通常又可分為下列四類基本結(jié)構(gòu) 集合，結(jié)構(gòu)中的數(shù)據(jù)元素之間就是“同屬于一個集合” ； 線性結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在的是一種線性關(guān)系，即一對一的關(guān)系； 樹形結(jié)構(gòu)，結(jié)構(gòu)中的元素存在著一對多的關(guān)系； 圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)，結(jié)構(gòu)中的元素之間存在著多對多的關(guān)系。 四種不同結(jié)構(gòu)的關(guān)系圖 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是用戶所看到的數(shù)據(jù)結(jié)構(gòu)，

10、是面向問題的。它描述的是數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的物理結(jié)構(gòu)，又稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的物理存儲方式，它屬于具體實現(xiàn)的視圖，是面向計算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個方面。一般來說，算法設(shè)計是基于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法實現(xiàn)則基于數(shù)據(jù)的物理結(jié)構(gòu)。1.3 C+語言基礎(chǔ) 本書以面向?qū)ο蟮挠^點來介紹數(shù)據(jù)結(jié)構(gòu)。所涉及的程序設(shè)計的方法自然是面向?qū)ο蟮某绦蛟O(shè)計方法。描述數(shù)據(jù)結(jié)構(gòu)所采用的語言應(yīng)該是面向?qū)ο蟮某绦蛟O(shè)計語言。選擇了目前比較流行的C+語言來描述各種數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的算法。實用和易學(xué)C+與C具有許多相同的功能，C+對C有很多擴(kuò)充的功能。假設(shè)讀者已經(jīng)熟悉C語言。1.3.1

11、 程序結(jié)構(gòu)一個C+程序可由若干個文件組成。C+的文件分為頭文件和源文件兩類。頭文件以.h為后綴，用于存放函數(shù)聲明，它給出了函數(shù)的參數(shù)類型，個數(shù)以及函數(shù)的返回類型，稱為原型。有一些頭文件是系統(tǒng)定義的，如,而另一些頭文件是用戶定義的；而源文件是用來存放C+的源代碼。用于源文件的后綴為.CPP?？赏ㄟ^預(yù)處理指令#include，將頭文件包含在適當(dāng)?shù)奈募小Ｒ粋€典型的C+程序/* 頭文件hello.h */# ifndef FILENAME_H# define FILENAME_Hchar *hello(char *)；# endif/* 源代碼文件hello.cpp */# include /含有s

12、print( )的原型# include / 含有求字符串長度函數(shù)strlen( )的原型# include /含有hello( )的原型char * hello(char* world)char *result = new char9+strlen(world)；/* Return the string “Hello, world”. */sprintf(result,”Hello,%s.”,world)；return result；/* 源代碼文件main.cpp */# include # include“hello.h”main( )cout hello(“Hello, shangha

13、i”)； 頭文件hello.h 是hello函數(shù)的原型。源文件hello.cpp定義了hello 函數(shù)，該函數(shù)有一個形式參數(shù)，其類型為string，返回函數(shù)的類型為string。main.cpp 是打印“hello, Shanghai”的主程序，它構(gòu)造并打印一個歡迎詞字符串。sprintf（ ）是系統(tǒng)內(nèi)定義的打印函數(shù)。main.cpp中調(diào)用的hello函數(shù)，其參數(shù)的類型、個數(shù)以及函數(shù)的返回類型必須與預(yù)處理指令“include”所定向的頭文件“hello.h”所給出的原型中的函數(shù)的參數(shù)類型、個數(shù)、函數(shù)的返回類型相匹配。 C+中有兩種注釋方法多行注釋：包含在定界符“/*”和“*/”之間的所有文本，

14、如: /* This book is designed to present the fundamentals of data structures from an object-oriented perspective. */單行注釋：在符號/之后至本行末的所有文本內(nèi)容。 例如，C注釋 /* This is a C+ program.*/可寫為C+的單行注釋 /This is a C+ program.1.3.2 數(shù)據(jù)聲明和作用域 數(shù)據(jù)聲明的作用C+的基本數(shù)據(jù)類型：char、int、float和double，這些數(shù)據(jù)類型中的某些又可以用short、long、signed和unsigned進(jìn)行

15、修飾數(shù)據(jù)聲明的主要形式： 常數(shù)值 變量：數(shù)據(jù)類型的實例，可被修改。 常量：在其生命期中不可被賦值的變量。如 const int pi=3.1415926。 (4) 枚舉：聲明一個整型常數(shù)序列的方式。用關(guān)鍵字enum聲明的。例如聲明： enum month=Jan=1, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec(5) 引用：引用類型用于為一個對象提供一個可替換的名字。對于某一個類型的對象的引用，所采用的聲明方式就是在該類型后面添上一個符號。例如 int x=9; int y=x; x=13printf(“x=%d,y=%d”,x

16、,y,); 在C中，程序塊的所有聲明都必須出現(xiàn)在所有可執(zhí)行語句之前。在C+中，聲明可放在使用所聲明的內(nèi)容之前的任何地方。例如printf（“Enter two integers：” ）；int x,y;printf（“x=%d, y=%d”, x, y,）變量也可以在for結(jié)構(gòu)的初始化部分予以聲明，其作用域仍然是在定義for結(jié)構(gòu)的程序塊內(nèi)。例如for（int i=0; i=5; i+）printf（“i=%d”,i） 在for結(jié)構(gòu)中把變量i聲明為一個整數(shù)并把它初始化為0。 作用域 函數(shù)中聲明的變量只能在函數(shù)內(nèi)部使用；在類中定義的變量，只能在該類內(nèi)部使用。這些變量都稱為局部變量。 C+的局部變量

17、的作用域從其聲明開始到結(jié)束程序塊的右花括號終止。因此，變量聲明之前的語句即使在同一個程序塊內(nèi)也不能引用該變量。變量聲明不能放在while 、do/while、for 和 if 結(jié)構(gòu)的條件中。 把變量聲明放在靠近首次引用的位置，即用到時再聲明后寫上使用，可提高程序的可讀性。在整個程序中都能引用的變量叫全局變量。如果一個全局變量在文件1中聲明，而在文件2中使用，則在文件2中必須使用關(guān)鍵字extern對該變量進(jìn)行聲明。 在構(gòu)成一個程序的兩個文件中，如果分別聲明了具有相同名字的一個全局變量，它們分別代表不同的實體，此時就要在兩個文件中分別使用關(guān)鍵字static對變量進(jìn)行聲明，以保證不發(fā)生混淆。 如果一

18、個程序塊中某個局部變量與某個全局變量同名，但又要在該程序塊中引用該全局變量，則可以使用域操作符:來引用全局變量。1.3.3 輸入/輸出執(zhí)行輸入輸出操作，必須用#include預(yù)處理指令包括一個頭文件。關(guān)鍵字cin用于C+中的輸入，操作符用于分開輸入的變量?？瞻祝磘eb鍵、回車或空格鍵）用于在標(biāo)準(zhǔn)輸入設(shè)備上將不同變量的值分開。關(guān)鍵字cout用于輸出到一個標(biāo)準(zhǔn)輸出設(shè)備。cout和將被輸出的每一內(nèi)容之間用操作符 分開。此外，定向到錯誤文件的命令由cerr定義。 例1-3 程序：C+中的輸入輸出# include void main( ) int x,y;cin x y;cout “x=” x en

19、dl;cout “y=” y endl;執(zhí)行上述程序時，按照輸入格式 5 10 回車或 5 回車 10 回車均使變量X和Y分別得到輸入值5和10，并輸出如下結(jié)果： x=5 y=10 C+中的輸入輸出， “自由格式”。程序員不必使用格式化符號來指明輸入輸出項的類型和順序。 輸入輸出操作符能夠被重載。 如有對文件的輸入輸出，則必須在程序中包含頭文件 fstream.h，它定義了類 ifstream 、ofstream 和 fstream。 要創(chuàng)建一個輸入流，必須聲明它為類ifstream。要創(chuàng)建一個輸出流，必須聲明它為類ofstream。而執(zhí)行輸入輸出的流必須聲明為類fstream。 例1-4 含

20、有文件輸入輸出的程序# include# includevoid main （ ）ofstream outFile（“my.out”, ios:out）；if（!outFile） cerr “can not open my .out” endl；/standard error device return；int n=70；float f =30.2;outFile “n:”n endl;outFile “f:” f endl; 1.3.4 函數(shù) C+中有兩種函數(shù)：常規(guī)函數(shù)和成員函數(shù)。成員函數(shù)用于類方法的定義，完成一個特定的功能。 無論是常規(guī)函數(shù)還是成員函數(shù)，其定義都包括四個部分： 函數(shù)名 形式

21、參數(shù)表 返回類型 函數(shù)體。函數(shù)的使用者通過函數(shù)名來調(diào)用函數(shù)，調(diào)用過程把實際參數(shù)傳送給相應(yīng)的形式參數(shù)作為數(shù)據(jù)的輸入；然后通過執(zhí)行函數(shù)體中的語句實現(xiàn)該函數(shù)的功能；最終得到的返回值由函數(shù)名帶回給函數(shù)的調(diào)用者。函數(shù)如果有返回值，則該值的類型就是該函數(shù)的返回類型。函數(shù)的返回值是通過函數(shù)體中的return語句返回的。return 語句的作用是返回一個其類型與返回類型相同的值，并終止函數(shù)的執(zhí)行。例1-5 一個函數(shù)int min （int a, int b）if a b return a;else return b;對于不返回值的函數(shù)，其返回類型要聲明為 void。在C+中，指定空參數(shù)列表的方法是在圓括號中寫

22、入void,或什么也不寫。下面的程序例子，演示了聲明和使用不帶參數(shù)的函數(shù)的方法。例1-6 使用不帶參數(shù)的函數(shù)# includevoid f1( )；void f2 (void)；main( ) f1( )； f2( )；return 0;void f1 ( ) cout “Function f1 takes no arguments n”；void f2(void) cout “Function f2 also takes no argumentsn”； 輸出結(jié)果為： Function f1 takes no arguments Function f2 also takes no argume

23、nts1.3.5 參數(shù)傳遞 函數(shù)調(diào)用時傳送給形參表的實參與形參在類型、個數(shù)以及順序上必須保持一致。 C+中函數(shù)的參數(shù)傳遞有四種方式： 值參數(shù)傳遞 引用參數(shù)傳遞 常值參數(shù)傳遞 常值引用參數(shù)傳遞 值參數(shù)傳遞是缺省的參數(shù)傳遞方式。若采用這種傳遞方式，程序在運行時，對應(yīng)的實際參數(shù)的值傳送給形式參數(shù)所對應(yīng)的局部工作區(qū)中的單元。當(dāng)函數(shù)的執(zhí)行終止時，函數(shù)修改的是形式參數(shù)所對應(yīng)的工作單元的值，而該值不傳回給實際參數(shù)。因此值參數(shù)的傳遞方式不會改變對應(yīng)形式參數(shù)的實際參數(shù)的值。使用引用參數(shù)傳遞方式時，需要在函數(shù)的形參表中將形參聲明為引用類型，即在參數(shù)名前加上一個“”。當(dāng)一個實參與一個引用類型形參結(jié)合時，被傳遞的不是

24、實參的值，而是實參的地址，函數(shù)通過地址存取被引用的實參。當(dāng)函數(shù)執(zhí)行時，任何對形式參數(shù)的改變也就是對實際參數(shù)的改變。當(dāng)要求一個函數(shù)調(diào)用返回多于一個參數(shù)時，也應(yīng)采用參數(shù)傳遞方式。此時，將參數(shù)中的一個由return語句返回，而其它參數(shù)由引用返回。常值引用參數(shù)傳遞方式的格式為const Ta，其中T是參數(shù)的類型。在函數(shù)體中，不能對常值參數(shù)修改。例1-7 參數(shù)傳遞的方式# include int ExampleByValue(int a, int b, int c) int x,y,z;x=a; y=b; z=c;a=3*a ;b=3*b ;c=3*c;return(x+y+z)/3;int Examp

25、leByRefer(int a, int b, int c) 代碼同上int ExampleByConsRefer(const inta,const intb,const intc) return(a+b+c)/3；main( )int s=0, p=2, q=3, r=4; s=ExampleByValue(p,q,r);cout “p,q,r,and s:” pqrs“n”;s=ExampleByRefer(p,q,r);cout“p,q,r and S:”pqrs“n”;s=ExampleByConsRefer(p,q,r);cout“p,q,r, and s:”pqrs“n”;輸出結(jié)果

26、： p, q, r and s: 2 3 4 3 p, q, r and s: 6 9 12 3 p, q, r and s: 6 9 12 9函數(shù)ExampleByValue以值參數(shù)傳遞方式調(diào)用的，第一次輸出的p，q，r的值為2、3、4。ExampleByRefer 是以引用參數(shù)傳遞方式調(diào)用的，輸出的結(jié)果p、q、 r、s為6，9，12，3。調(diào)用 ExampleByConsRefer 時，實際參數(shù)p，g、r不會改變，保留字const保證只能對其值初始化一次，因而輸出結(jié)果為6，9，12，9。1.3.6 函數(shù)名重載 在C+中，允許在同一個程序中用同一個名字定義多個函數(shù)，但它們的形參表不同。這種能力

27、稱為函數(shù)名重載。 在調(diào)用一個重載的函數(shù)時，編譯程序通過檢查參數(shù)的個數(shù)、類型和順序,自動選擇一個合適的函數(shù)。函數(shù)重載通常用來建立在不同數(shù)據(jù)類型的基礎(chǔ)上完成類似任務(wù)的多個同名函數(shù)，這可使程序易于閱讀和理解。例1-8 用重載函數(shù)sum來計算兩個int類型值的和及三個float類型值的和。在該例中，兩個sum函數(shù)的返回類型不同，參數(shù)個數(shù)也不同。#includeint sum(int a, int b) return a+b;float sum(float a, float b, float c) return a+b+c;void main( ) printf(“sum(2,3)= %d”,sum(2

28、,3)； printf(”sum(1.1,2.2,3.3)= %f ”,sum(1.1,2.2,3.3); 1.3.7 動態(tài)內(nèi)存分配在ANSI C中，malloc（ ）和free（ ）。 C+兼容了C語言中的這兩個函數(shù)，并提供了兩個新的操作符：new 和 deleteptrtype *ptr 語句中的ptrtype可以是任何數(shù)據(jù)類型（如int、char、float等等）。則語句 ptr=new ptrtype 從程序的空閑內(nèi)存區(qū)中為ptrtype類型的對象分配內(nèi)存。new運算符以類型為參數(shù)，自動建立一個具有合適大小的對象，并返回指向該類型對象的指針，此處類型為ptrtype，返回的指針為ptr

29、。如果分配內(nèi)存不成功，則返回一個空指針，在C+中，以0而不是null來表示空指針。在C+中，用如下語句來釋放該對象所占用的空間：delete ptr；運算符delete 只能釋放用運算符new分配的內(nèi)存。把delete 用于空指針對程序執(zhí)行沒有任何影響，但把delete用于已經(jīng)釋放的指針是不允許的。C+允許初始化新分配的對象，例如，語句int *thisptr=new int（57）；建立了一個指向int類型對象的指針thisptr，把新分配的int類型的對象初始化為57。該語句把指針thisptr 的聲明與動態(tài)內(nèi)存分配以及初始化放在一條語句中了。雖然new和delete所完成的功能與C語言中

30、的malloc( )和free（ ）類似，但更方便。首先new按指定類型自動分配足夠的空間，不要求調(diào)用者提供所需存儲空間的數(shù)量并使用sizeof 運算符進(jìn)行計算；其次，new自動返回指定類型的指針，不必像malloc（ ）那樣在分配時需要顯式地使用強(qiáng)制類型； 此外，new和delete 可以重載。1.3.8 結(jié)構(gòu)與聯(lián)合如果想要把多個不同數(shù)據(jù)類型的數(shù)據(jù)項組合成一個數(shù)據(jù)元素，則可以使用結(jié)構(gòu)這樣的數(shù)據(jù)類型。1結(jié) 構(gòu)C+用數(shù)組存儲許多相同類型的相關(guān)信息。有些數(shù)據(jù)信息是由若干不同數(shù)據(jù)類型的數(shù)據(jù)所組成。例如，一個職工工資記錄包括姓名、工號和工資等，這些數(shù)據(jù)信息的類型是不一樣的，不能用數(shù)組直接把它們組織起來

31、。用結(jié)構(gòu)變量就可以有組織地把這些不同數(shù)據(jù)類型的數(shù)據(jù)信息存放在一起。 結(jié)構(gòu)是用戶自定義數(shù)據(jù)類型，它可與int、float等基本數(shù)據(jù)類型一樣被使用。聲明結(jié)構(gòu)類型時，先指定關(guān)鍵字struct和結(jié)構(gòu)名，然后用用一對花括號將若干個結(jié)構(gòu)成員及其數(shù)據(jù)類型的說明括起來。 通常，結(jié)構(gòu)聲明在所有函數(shù)之外，位于main函數(shù)之前。這就使所聲明的數(shù)據(jù)類型在程序的任何地方都可以被使用。 聲明一個結(jié)構(gòu)并不分配內(nèi)存，內(nèi)存分配發(fā)生在定義這個新數(shù)據(jù)類型的變量時。 結(jié)構(gòu)中包含的數(shù)據(jù)變量稱為該結(jié)構(gòu)的成員。定義了相應(yīng)結(jié)構(gòu)變量，分配了空間，就可以使用點操作符“”（或稱結(jié)構(gòu)成員操作符）來訪問結(jié)構(gòu)中的成員。左操作元為結(jié)構(gòu)類型變量，右操作元為

32、結(jié)構(gòu)中的成員。在數(shù)組中，稱數(shù)組分量為元素，在結(jié)構(gòu)中，稱結(jié)構(gòu)分量為成員。數(shù)組的運算符與結(jié)構(gòu)的點運算符具有相同的運算優(yōu)先級，它們是所有運算符中優(yōu)先級最高的。每個分量數(shù)據(jù)類型可以相異。結(jié)構(gòu)的成員有自己單獨的名字。結(jié)構(gòu)可以被賦值。例1-9 聲明一個關(guān)于職工工資記錄的結(jié)構(gòu)，并使用它。/ Person-salary. cpp # include struct personchar name 20; / 姓名unsigned long id; / 工號 int salary; / 工資 ;void main( ) person pr1=Frank Voltaire,12345678, 2456;person

33、 pr2;pr2=pr1;cout pr2.id pr2.salary ”（也是一種結(jié)構(gòu)成員操作符）來訪問結(jié)構(gòu)成員。例1-10 定義結(jié)構(gòu)指針，通過結(jié)構(gòu)指針來訪問結(jié)構(gòu)成員：/ Structure-pointer.cpp # include #include struct person char name 20; unsigned long id; int salary;void main( ) person pr1; person * prPtr; prPtr= & pr1; / 定義了一個結(jié)構(gòu)類型的指針 strcpy(prPtr-name, “David Marat”); p

34、rPtr- id =987654321; prPtr- salary =2567; cout name id salary member如果變量utype是用來記錄存儲在uval中的最近類型的，那么可使用下列程序段存取聯(lián)合中的元素。if (utype = INT) printf(“%dn”, uval.ival);else if (utype = FLOAT) printf(“%dn”, uval.fval);else if (utype = STRING) printf(“%dn”, uval.pval);elseprintf(“bad type %d in utypen”, utype);

35、 聯(lián)合可以和結(jié)構(gòu)、數(shù)組組合使用。存取結(jié)構(gòu)中的聯(lián)合或聯(lián)合中的結(jié)構(gòu)的記號與存取嵌套結(jié)構(gòu)是一樣的。例1-13 結(jié)構(gòu)、數(shù)組和聯(lián)合的組合struct char *name; int flags; int utype; union int ival; float fval; char *pval; uval; symtabNSYM;聯(lián)合是一種形式特殊的結(jié)構(gòu)變量。和結(jié)構(gòu)一樣，對聯(lián)合施加的操作只能是存取成員和取其地址。不能把聯(lián)合作為參數(shù)傳遞給函數(shù)，也不能由函數(shù)返回聯(lián)合。 聯(lián)合只是一種變量，為了弄請在聯(lián)合中存儲的是哪一種類型，通常是在聯(lián)合外設(shè)置一個變量以作表征。正如在systab中，每一個結(jié)構(gòu)，都含有整型變量u

36、type以指出在該結(jié)構(gòu)的聯(lián)合uval中存儲的是什么類型的變量。 結(jié)構(gòu)中往往含有幾個不同類型的變量。如systab中就有四個變量。 1.4 算法性能與復(fù)雜度 公元825年，一位名叫阿爾 花拉子米（al-Khowarizmi）的波斯數(shù)學(xué)家寫了一本教科書，書中概括了進(jìn)行數(shù)字四則算術(shù)運算的法則，所有的數(shù)字都是用今天的印度十進(jìn)制形式來表示的（按個、十、百位等排列，并有表示小數(shù)部位的小數(shù)點）?，F(xiàn)代名詞“算法” (algorithm) 就來源于這位數(shù)學(xué)家的名字。 在計算機(jī)科學(xué)里，算法這個詞有一個專門的解釋：算法用計算機(jī)解題的精確描述。1.4.1 算法的定義通常，人們將算法定義為一個用于實現(xiàn)某個特定任務(wù)的有窮

37、指令集，這些指令規(guī)定了一個運算序列。一個算法應(yīng)當(dāng)具有以下特性： 輸入性 一個算法必須具有零個或多個輸入量。 輸出性 一個算法應(yīng)有一個或多個輸出量，輸出量是算法計算的結(jié)果。 確定性 算法中的每一條指令應(yīng)含義明確，無歧義。 有窮性 算法中的指令執(zhí)行序列是有窮的。 有效性 每條指令必須是足夠基本的。一個程序與一個算法對于上述是有重大區(qū)別的。一個程序可以不滿足特性。一個程序可能會不終止。本書中所給出的程序均是可終止的，所以在本書中對“算法”和“程序”這兩個術(shù)語不作嚴(yán)格的區(qū)分。算法設(shè)計者在構(gòu)思和設(shè)計了一個算法之后，必須準(zhǔn)確清楚地將所設(shè)計的解題步驟記錄下來，或提供交流，或編寫成程序供計算機(jī)執(zhí)行。記錄算法中

38、的解題步驟又叫描述算法。常用的描述算法的方式有自然語言、流程圖和程序設(shè)計語言等。自然語言(如漢語或英語)： 優(yōu)點：使用者不必對描述工具本身花精力去學(xué)習(xí)，對寫出來的算法的理解是接的。缺點：容易出現(xiàn)二義性；語句一般太長， 使得所建立的算法也顯得冗長；算法中的分支及循環(huán)等結(jié)構(gòu)表示不能清晰地顯示出來規(guī)定式樣的圖形、指向線和文字說明組合起來的流程圖方式：優(yōu)點：直觀、清晰、易懂，便于檢查、修改和交流。缺陷：嚴(yán)密性不如程序設(shè)計語言，靈活性不及自然語言；此外，對于大型的算法描述有困難。計算機(jī)程序設(shè)計語言：優(yōu)點：顯得清晰、明了，寫出的算法一步到位，能由計算機(jī)處理。事實上，用程序設(shè)計語言來描述算法，就是對算法的實

39、現(xiàn)。缺點：抽象性差一些，可能會使寫算法的人拘泥于計算步驟描述的細(xì)節(jié)，而忽略算法的實質(zhì)。此外，必須熟練掌握程序設(shè)計語言及其編程技巧。 考慮到本書的使用者已經(jīng)熟悉了像C這樣的程序設(shè)計語言，并且掌握了程序設(shè)計的基本方法和技術(shù)，并因本書的內(nèi)容是以面向?qū)ο蟮姆椒▉碛懻摂?shù)據(jù)結(jié)構(gòu)，因而采用C+來描述算法。 它的優(yōu)點是類型豐富、語句精練，具有面向過程和面向?qū)ο蟮碾p重特點。此外，C+也支持抽象數(shù)據(jù)類型。為了使寫出的算法可讀性和可理解性更強(qiáng), 本書有時還采用了C+語句與自然語言結(jié)合的方式來描述算法，有時對算法加以合適的注釋。1.4.2 算法的性能標(biāo)準(zhǔn)算法的設(shè)計主要有以下幾個標(biāo)準(zhǔn)：(1) 正確性 算法應(yīng)確切地滿足所

40、要求解的問題的需求。(2) 可用性 算法應(yīng)能很方便地使用。 (3) 可讀性 算法應(yīng)是可讀的，即易于理解的。 (4) 效率 算法的效率主要是指算法執(zhí)行時存儲單元的開銷和運行時間的耗費，前者稱為算法的空間代價，后者稱為算法的時間代價。(5) 健壯性 當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)能作出適當(dāng)?shù)奶幚恚粦?yīng)當(dāng)產(chǎn)生不可預(yù)料的結(jié)果。在設(shè)計一個算法時，上述的幾條標(biāo)準(zhǔn)有時會有矛盾，如可用性強(qiáng)、可讀性強(qiáng)會降低算法的效率。而對效率這個標(biāo)準(zhǔn)，算法的低時間代價和低空間代價也會產(chǎn)生矛盾。例如，有些問題若采用較多的內(nèi)存空間可使時間代價降低，若采用較少的內(nèi)存空間，則使時間代價提高。在計算機(jī)硬件價格快速下降的趨勢下，算法的時間效率

41、應(yīng)首先予以考慮。1.4.3 算法復(fù)雜度算法效率的度量一般采用兩種方法: 事前估計 后期測試?yán)鐚τ诔绦蜻\行的時間耗費，后期測試主要通過在算法中的某些部位插裝計時函數(shù)來測定算法完成某一規(guī)定功能所需的時間。但這種方法與算法的運行環(huán)境有關(guān)。同樣的算法在速度不同的計算機(jī)上運行，執(zhí)行速度相差卻非常大；此外，一個算法用不同的編譯系統(tǒng)編譯出的目標(biāo)代碼的長度不一樣，質(zhì)量也不一樣，完成同樣的功能所需時間也不同；還有，對于一個存儲需求很大的算法，如果可用的存儲空間不夠，在運行時不得不頻繁地進(jìn)行內(nèi)外存交換，需要的運行時間就很多。而如果可用的存儲空間足夠大，運行時間就可以大大減少。因此，算法的實際運行時間依賴于所用的

42、計算機(jī)系統(tǒng)。在不同的機(jī)型、不同的編譯系統(tǒng)版本、不同的硬軟件配置情況下，想通過后期測試的方法來測定算法的復(fù)雜度是比較困難的。因此人們常常采用事前估計即對算法進(jìn)行分析的方法來測定算法的復(fù)雜度。因為算法的復(fù)雜度與具體的運行環(huán)境和編譯系統(tǒng)無關(guān)，所以可以通過復(fù)雜度的分析來對算法進(jìn)行比較和評估。1. 算法的時間復(fù)雜度 算法的時間復(fù)雜度與具體的機(jī)器以及運行環(huán)境無關(guān)，它與所求解的問題的規(guī)模有關(guān)，可以說，它是問題規(guī)模的函數(shù)。 一般來說，問題的規(guī)?？梢詮膯栴}的描述中找到。 例如，在一個具有n個教職工記錄的文件中查找某個名叫李華的教師，則該問題的規(guī)模為n。又如，對一個具有n個整數(shù)組成的數(shù)組進(jìn)行排序，則問題的規(guī)模也是

43、n。一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和基本操作構(gòu)成的，則算法的時間復(fù)雜度與這兩者有關(guān)。為了能比較解同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題來說是基本運算的操作，即基本操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。有時也需要同時考慮幾種基本操作，甚至可以對不同的操作賦以不同權(quán)值，以反映執(zhí)行不同操作所需的相對時間，這種做法便于綜合比較解決同一問題的那些完全不同的算法。算法的時間效率分析通常采用O(f(n)表示法，讀作“大O的f(n)” 。其定義可敘述為T(n)=O(f(n)當(dāng)且僅當(dāng)存在正常數(shù)c和n0，使得對所有的n，當(dāng)nn0時，都滿足T(n)cf(n)。換句

44、話說，O(f(n)給出了函數(shù)T(n)的上界。T(n)=O(f(n)表示：隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度（asymptotic time complexity）,簡稱時間復(fù)雜度。或者說兩者具有相同的數(shù)量級。例 1-14 設(shè)a和b是兩個已經(jīng)賦了值的數(shù)組，對如下求解了兩個NxN矩陣相乘的算法求其時間復(fù)雜度。for (i=0; in; i+) for (j=0; jn; j+) Ci,j=0; / 基本操作語句1for (k=0; kn; k+) Cij=Cij+aik*bkj； / 基本操作 語句2 解: 設(shè)基本操作語句的總執(zhí)行次數(shù)為T(n)

45、，因為(基本)操作語句“cij=0”的執(zhí)行次數(shù)為n2?！癱ij=Cij+aik*bkj ”的執(zhí)行次數(shù)為n3，因此T(n)=n2+n3。而T(n)=n2+n3cn3，選擇c2，則T(n)cn3=O(n3)。所以該算法的時間復(fù)雜度為O(n3) 因為算法的時間復(fù)雜度當(dāng)算法的時間復(fù)雜度T(n)和問題的規(guī)模n無關(guān)時： T(n)c*1，此時算法的時間復(fù)雜度T(n)=O(1)，稱為常量級； 當(dāng)算法的時間復(fù)雜度T(n)與問題規(guī)模n為線性關(guān)系時，T(n)c*n ，此時算法的時間復(fù)雜度T(n)=O(n)，稱為線性級； 當(dāng)算法的時間復(fù)雜度T(n)和問題的規(guī)模n為平方關(guān)系時，T(n)c*n2，此時算法的時間復(fù)雜度T(

46、n)=O(n2)，稱為平方級。 例1-15 求出下面三個程序段的時間復(fù)雜度。(1) x=x+1 (2) for (i=1; i=n; i+) x=x+1 (3) for (i=1; i=n; i+) for (j=1; i=n;j+) x=x+1解：這三個程序段中均含基本語句x=x+1，各自所含的次數(shù)為1、n 和n2，所以這三個程序段所表示的算法的時間復(fù)雜度分別O(1)、O(n)和O(n2)依次類推，還有O(logn)、O(2n)等時間復(fù)雜度。例1-16 設(shè)n為如下算法處理的數(shù)據(jù)個數(shù)，求出其時間復(fù)雜度。 for (i=1; i=n; i=2*i) printf(“i= %d n” , i) /

47、 基本語句解：設(shè)基本語句的執(zhí)行次數(shù)為T(n)，有2T(n)n，即有T(n)log2n， 因T(n)log2nc*log2n=O(logn)，其中c為常數(shù)，所以該算法的時間復(fù)雜度為O(logn)。由于算法的時間復(fù)雜度考慮的是對于問題規(guī)模的增長率，則在難以精確計算基本操作語句執(zhí)行次數(shù)的情況下，只需求出它關(guān)于n的增長率或數(shù)量級即可。在許多情況下，算法的時間復(fù)雜度會隨著算法中數(shù)據(jù)元素的取值情況的不同而不同。例如，下面的算法是用冒泡排序法對數(shù)組a中的n個整數(shù)類型的數(shù)據(jù)元素（a0an-1）從小到大排序。例1-17 冒泡排序算法void BubbleSort(int a , int n) int i, j,

48、 flag=1;int temp;for(i=1; in & flag=1; i+) flag=0; （接下頁）for (j=0; jaj+1)flag=1, temp=aj, aj=aj+1; aj+1=temp; 這個算法的時間復(fù)雜度隨待排序數(shù)據(jù)的不同而不同。當(dāng)某次排序過程中沒有任何兩個數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時算法將因標(biāo)記flag=0不滿足循環(huán)條件而結(jié)束。 “交換兩個相鄰的整數(shù)”為基本操作，當(dāng)a中的初始序列為“正序”，即自小至大有序時，基本操作的執(zhí)行次數(shù)為0，這是最好的情況；當(dāng)初始序列為“逆序”，即自大至小有序時，基本操作的執(zhí)行次數(shù)為n(n-1)/2，這是最壞情況。

49、再從“兩個相鄰元素比較”這一基本操作來看，當(dāng)初始序列為“正序”時，則i循環(huán)體執(zhí)行一次，在j循環(huán)中進(jìn)行了n1次關(guān)鍵字之間的比較。反之，若初始序列為“逆序”時，則i循環(huán)體執(zhí)行n一1次，需要進(jìn)行的關(guān)鍵字之間的比較為(i1)=n(n1)次。對這類算法的分析，一種解決的辦法是計算它的平均值，即考慮它對所有可能的輸入數(shù)據(jù)集的期望值，此時相應(yīng)的時間復(fù)雜度為算法的平均時間復(fù)雜度。 如假設(shè)a中初始輸入數(shù)據(jù)可能出現(xiàn)n!種排列情況的概率相等，則冒泡排序算法的平均時間復(fù)雜度為Ta(n)=O(n2)。然而，在許多情況下，各種輸入數(shù)據(jù)集出現(xiàn)的概率難以確定，算法的平均時間復(fù)雜度也就難以確定。因此，另一種更可行也更常用的辦法

50、是討論算法在最壞情況下的時間復(fù)雜度，即分析在最壞情況下，估算出算法執(zhí)行時間的一個上界。例如，上述冒泡排序的最壞情況為a中初始序列為自大至小有序，則冒泡排序算法在最壞情況下的時間復(fù)雜度為O（n2）。算法的時間復(fù)雜度是衡量一個算法優(yōu)劣的重要指標(biāo)。一般來說，具有多項式時間復(fù)雜度的算法是可接受、可實際使用的算法。具有指數(shù)時間復(fù)雜度的算法，只有當(dāng)n足夠小時才是可使用的算法。表1-1給出了多項式增長和指數(shù)增長的比較。從表中可看出，當(dāng)n=50時，多項式函數(shù)n3=125000，而指數(shù)函數(shù)2n=1.01015, n!=3.01064，nn=8.91084。解題時，應(yīng)盡可能選用多項式級O（nk）的算法，而不希望用

51、指數(shù)級的算法。2算法的空間復(fù)雜度可以用空間復(fù)雜度（Space Complexity）作為算法所需存儲空間的量度，記作S（n）=O（f(n)）它表示隨著問題規(guī)模n的增大，算法執(zhí)行時所需存儲空間的增長率和f(n)的增長率相同，稱為算法的漸進(jìn)空間復(fù)雜度（asymptotic Space Complexity），簡稱空間復(fù)雜度。這里所說的存儲空間是指解題過程所需要的輔助空間。例如在排序算法中，為移動數(shù)據(jù)元素所需的臨時工作單元、在遞歸算法中所需的遞歸工作棧等。若輔助空間相對輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。通常，只有完成同一功能的幾個算法之間才具有可比性。例如同樣是排序算法，待排序的數(shù)據(jù)元素是

52、n個，作為輸入和存放這些數(shù)據(jù)的數(shù)組或鏈表結(jié)點同樣是n個，則這些輸入數(shù)據(jù)所占用的存儲空間是不必進(jìn)行比較的，可比較的就是各個算法所需要的輔助空間。數(shù)據(jù)結(jié)構(gòu) C+實現(xiàn)第二章第二章 抽象數(shù)據(jù)類型和C+類 抽象數(shù)據(jù)類型(Abstract Data Type，ADT)是用戶在數(shù)據(jù)類型基礎(chǔ)上定義和實現(xiàn)的數(shù)據(jù)類型。一種抽象數(shù)據(jù)類型定義了一種新的數(shù)據(jù)元素集合和該數(shù)據(jù)元素集合上所允許的操作集合。抽象數(shù)據(jù)類型在更高一級的抽象程度上實現(xiàn)了信息的隱藏和封裝。C+中類的定義體現(xiàn)了抽象數(shù)據(jù)類型的思想。C+中對于面向?qū)ο蟪绦蛟O(shè)計的支持，核心部分就是類的定義。2.1 抽象數(shù)據(jù)類型 2.1.1 從數(shù)據(jù)類型到抽象數(shù)據(jù)類型數(shù)據(jù)類型是

53、一組性質(zhì)相同的值的集合以及定義于這個集合上的一組操作的總稱。在程序設(shè)計語言中，它是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。以C語言為例，它的基本數(shù)據(jù)類型是字符型、整型、浮點型和雙精度型，分別以保留字char、int、float和double標(biāo)識。此外還有一種特殊的基本類型，稱之為無值，即沒有值，以保留字void標(biāo)識。 數(shù)據(jù)類型規(guī)定了其值的集合中元素的取值范圍和對這些元素所能采用的操作。 例如，整型所定義數(shù)據(jù)集合中元素可取的值是機(jī)器所能表示的最小負(fù)整數(shù)和最大正整數(shù)之間的任何一個整數(shù)?？捎玫牟僮饔袉文窟\算符+、，雙目運算符+、*、/、%，關(guān)系運算符、=、=、!=和賦值運算符=等。 在程序設(shè)計語言如C中，除了基本數(shù)據(jù)類型以

54、外，還提供了一些定義數(shù)組、結(jié)構(gòu)、文件等組合數(shù)據(jù)類型的規(guī)則。 討論抽象數(shù)據(jù)類型。 所謂抽象，就是抽取問題本質(zhì)的東西而忽略非本質(zhì)的細(xì)節(jié)。 抽象是與具體相對應(yīng)的。一個人名是抽象，它代表某人的一切屬性，包括身高，年齡，體重，文化程度等。 抽象是具體事物描述的一個概括。 抽象數(shù)據(jù)類型是用戶自己定義和實現(xiàn)的數(shù)據(jù)類型。它類似于在計算機(jī)機(jī)器語言的位、字節(jié)和字的基礎(chǔ)上引入字符、整數(shù)、浮點數(shù)和雙精度數(shù)等數(shù)據(jù)類型這樣一種方法。 計算機(jī)是使用二進(jìn)制定點數(shù)和浮點數(shù)來實現(xiàn)數(shù)據(jù)的存儲和運算的。從計算機(jī)硬件系統(tǒng)的角度看，計算機(jī)能處理的數(shù)據(jù)類型只包括位、字節(jié)和字。 高級程序設(shè)計語言中引入了字符、整數(shù)、浮點數(shù)、雙精度數(shù)。編程者可

55、以直接使用“A”，“57”，“1.3E10”等數(shù)據(jù)表示，而不必使用它們的二進(jìn)制表示。 編譯程序會將這些數(shù)據(jù)值轉(zhuǎn)換成二進(jìn)制碼。這些數(shù)值是二進(jìn)制數(shù)據(jù)的抽象。 一個抽象數(shù)據(jù)類型定義了一種新的數(shù)據(jù)元素集合和數(shù)據(jù)元素集合上所允許的操作集合。 在高級程序設(shè)計語言中，由基本數(shù)據(jù)類型可以定義出更高一級的抽象數(shù)據(jù)類型，如各種表、隊列、圖甚至窗口、管理器等。 我們可以以隊列來理解抽象數(shù)據(jù)類型。一個隊列由若干個元素組成的一個序列以及這個序列上的相關(guān)操作所構(gòu)成。其操作遵循的是“先到先服務(wù)”的原則。 新的元素進(jìn)隊列：加入在隊列的尾部。 元素出隊列時，總是取出隊列頭的元素。 隊列中的元素可以是各種不同類型的對象。它們可以

56、是整數(shù)，也可以是字符，也可以是字符串，甚至可以是關(guān)于一個學(xué)生的記錄 無論是由什么對象組成隊列，都不影響我們對“隊列”本質(zhì)的理解。 可以把隊列看成是一個抽象數(shù)據(jù)類型。 這種數(shù)據(jù)類型的層次使程序設(shè)計者可以從抽象的概念出發(fā)，從整體上考慮然后自頂向下，逐條展開和具體化，直至獲得最后的結(jié)果。抽象數(shù)據(jù)類型與具體應(yīng)用無關(guān)，這可使編程者把注意力集中在數(shù)據(jù)及其操作的理想模型上。2.1.2 封裝和信息隱藏 當(dāng)一個技術(shù)員要安裝一臺電腦時，他將各個設(shè)備組裝起來。 當(dāng)他想要一個聲卡時，不需要用原始的集成電路芯片和材料去制作一個聲卡，而是來到電腦設(shè)備商店購買一個他所需要的某種功能的聲卡。 技術(shù)員關(guān)心的是聲卡的功能，并不關(guān)

57、心聲卡內(nèi)部的工作原理。聲卡是自成一體的，這種自成一體性稱為封裝性。 無需知道封裝部件內(nèi)部是如何工作就能使用的思想稱為數(shù)據(jù)隱藏。聲卡的所有屬性都封裝在聲卡中，不會擴(kuò)展到聲卡之外。聲卡的數(shù)據(jù)隱藏在聲卡的電路板上。技術(shù)員無需知道聲卡的工作原理就能有效地使用它?，F(xiàn)在來討論抽象數(shù)據(jù)類型中的封裝和信息隱藏 抽象數(shù)據(jù)類型的特征是使用和實現(xiàn)分離，實行封裝和信息隱藏。 在設(shè)計抽象數(shù)據(jù)類型時，把類型的聲明與其實現(xiàn)分離開來。因為每種抽象數(shù)據(jù)類型要有確切的數(shù)據(jù)元素集合和所允許的操作集合的定義。抽象數(shù)據(jù)類型定義了需要包含的數(shù)據(jù)信息，并根據(jù)功能確定了公共界面的服務(wù)。 一方面使用者是依據(jù)這些定義使用這些抽象數(shù)據(jù)類型的，即通

58、過公共界面中的服務(wù)對該抽象數(shù)據(jù)類型進(jìn)行操作的。 另一方面，抽象數(shù)據(jù)類型的設(shè)計者依據(jù)這些定義設(shè)計該抽象數(shù)據(jù)類型及各種操作的具體實現(xiàn)，抽象數(shù)據(jù)類型的物理實現(xiàn)作為私有部分封裝在其實現(xiàn)模塊內(nèi)。 使用者不能看到，也不能直接對該類型所存儲的數(shù)據(jù)進(jìn)行操作，而只能通過界面中的服務(wù)來訪問這些數(shù)據(jù)。這樣，嚴(yán)格區(qū)分了抽象數(shù)據(jù)類型的兩個不同的視圖。從使用者的角度來看，只要了解該抽象數(shù)據(jù)類型的規(guī)格說明，就可以利用公共界面中的服務(wù)來使用這個類型，而不必關(guān)心其物理實現(xiàn)。這與我們?nèi)粘Ｉ钪小半娨暀C(jī)”也非常相似。一個“電視機(jī)”提供給用戶的是一個屏幕和一組功能按鈕（包括遙控器上的功能按鈕）用戶是通過對這組功能按鈕的操作和屏幕來看

59、電視節(jié)目的。用戶可以用電視機(jī)提供的按紐來選擇頻道、控制音量、調(diào)整色彩與對比度和亮度等，而不必知道電視機(jī)是如何實現(xiàn)這些功能的。電視機(jī)把選擇頻道、控制音量、調(diào)整色彩與對比度和亮度等功能的實現(xiàn)都封閉起來了。2.1.3 抽象數(shù)據(jù)類型描述每種抽象數(shù)據(jù)類型的描述應(yīng)包括： 抽象數(shù)據(jù)類型的名、數(shù)據(jù)集合的定義， 以及每種操作的名稱和該操作的輸入、 前置條件、功能、輸出和后置條件等定義。一個抽象數(shù)據(jù)類型的描述在形式上可繁可簡，其概括說明的描述形式是：ADT 抽象數(shù)據(jù)類型名 is Data 數(shù)據(jù)元素集合和數(shù)據(jù)元素間的關(guān)系Operation構(gòu)造函數(shù)數(shù)據(jù)值的初始化操作1輸入：用戶輸入的數(shù)據(jù)值 前置條件：執(zhí)行此操作前數(shù)據(jù)

60、所必需的狀態(tài) 動作：對數(shù)據(jù)進(jìn)行的處理 輸出：操作后的返回值描述后置條件：系統(tǒng)執(zhí)行操作后數(shù)據(jù)的狀態(tài)操作2 操作3endADT 抽象數(shù)據(jù)類型名 例2-1 要設(shè)計一個擲骰子的程序，骰子可設(shè)計成一個抽象數(shù)據(jù)類型Dice，其數(shù)據(jù)類型包括被擲骰子數(shù)目N，擲出骰子的總點數(shù)和每個骰子的點數(shù)；其操作包括擲骰子、返回該次投擲的骰子總點數(shù)以及打印所擲每個骰子的點數(shù)。ADT Dice isData 該次投擲骰子的個數(shù)。這是一個大于或等于1的整數(shù)。 該次擲出的總點數(shù)。這是一個大于等于N且小于等于6N的整數(shù)。 該次擲出的每個骰子的點數(shù)。這是一個表，表中的數(shù)值均為1到6的整數(shù)。 Operation Constructor