tp-1764數(shù)據(jù)結(jié)構(gòu)第一章ppt

1、數(shù)據(jù)結(jié)構(gòu) ??C++實現(xiàn)第一章繆淮扣 顧訓(xùn)穰 沈 俊 編著科 學(xué) 出 版 社,新世紀(jì)計算機(jī)專業(yè)系列教材,內(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ū)ο蟮母拍睿?/p>

2、介紹了線性表、棧、隊列、數(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ù)人員閱讀參考。,為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？,作為計算機(jī)程序組成部分的數(shù)據(jù)結(jié)構(gòu)和算法的研究，一直受到計算機(jī)領(lǐng)域工作者的高度重視。數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)教學(xué)計劃中的一門核心課程，也是信息

3、管理、通信電子、自動控制等與計算機(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)？,面

4、向?qū)ο蠹夹g(shù)是軟件工程領(lǐng)域中的重要技術(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ū)ο蟪?/p>

5、序設(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í)量大； 隱藏在各部分內(nèi)容中的方法和技術(shù)多； 貫穿于全書的動態(tài)鏈表存儲結(jié)構(gòu)和遞歸技術(shù)令不少初學(xué)者望而生畏。 本書的編寫者長期來從事數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)，對該課程的教學(xué)特點和

6、難點有比較深切的體會。,作者的努力,作者在認(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++語言時

7、盡可能給出比較完整的程序，使學(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

8、  （算法+數(shù)據(jù)結(jié)構(gòu)）= 程序 計算機(jī)神通廣大，聰明能干。 計算機(jī)的本領(lǐng)是人是用“程序”來“教” 的。 讓計算機(jī)解題實際上就是為計算機(jī)編程序。因而解題的過程就不僅僅是編程序，而是一個包括編程序在內(nèi)的軟件開發(fā)過程。,軟件不僅僅指程序，而是包括程序以及開發(fā)程序的過程中所產(chǎn)生的各種文檔。軟件開發(fā)的目標(biāo)是產(chǎn)生能讓計算機(jī)有效工作的程序，因此程序是軟件的核心。程序到底是什么呢？N.Wirth給出的一個著名的公式：

9、算法+數(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)=程序 ?（算法+數(shù)據(jù)結(jié)構(gòu)）= 程序,本書以

10、面向?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è)計算法和編制程序從對問題的分析中提取操作的對

11、象，并找出這些操作對象之間的關(guān)系，然后用數(shù)學(xué)的語言加以描述。,1.2.1 兩個簡單的數(shù)據(jù)結(jié)構(gòu)實例,例 1-1 人事登記表 線性數(shù)據(jù)結(jié)構(gòu),例1-2 一個典型的學(xué)校行政機(jī)構(gòu),層次型數(shù)據(jù)結(jié)構(gòu),,1.2.2 什么是數(shù)據(jù)結(jié)構(gòu),一個水平再高的廚師,盡管他可以把烹調(diào)某個菜肴的過程掌握得很好，但如果不給他原料，他是做不出色、香、味俱全的菜。 “巧婦難為無米之炊”。 對一個程序來講，數(shù)據(jù)就是“原料”。 大千世界中有各種各樣的信

12、息，交通燈，交通卡，交易，思想。這些信息必須轉(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ù)的子集。自然數(shù)集合 ={0, 1, 2, …}是“數(shù)”的數(shù)據(jù)對象；所有的字符是數(shù)據(jù)

13、，字母集合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)系；

14、 ⑷ 圖形結(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)，是面向問題的。它描述的是數(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++

15、語言基礎(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 程序結(jié)構(gòu),一個C++程序可由若干個文件組成。C++的文件分為頭文件和源文件兩類。頭文件以.h為后綴，用于

16、存放函數(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 *)；

17、# endif,/* 源代碼文件hello.cpp */# include //含有sprint( )的原型# include // 含有求字符串長度函數(shù)strlen( )的原型# include //含有hello( )的原型char * hello(char* world){char *result = new char[9+strlen(world)]；/* Return the string “

18、Hello, world”. */sprintf(result,”Hello,%s.”,world)；return result；}/* 源代碼文件main.cpp */# include # include“hello.h”main( ){cout << hello(“Hello, shanghai”)；},頭文件hello.h 是hello函數(shù)的原型。源文件hello.cpp定義了hello 函數(shù)，該

19、函數(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++中有兩種注

20、釋方法,多行注釋：包含在定界符“/*”和“*/”之間的所有文本，如: /* This book is designed to present the fundamentals of data structures from an object-oriented perspective. */單行注釋：在符號//之后至本行末的所有文本內(nèi)容。 例如，C注釋 /* This is

21、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)行修飾數(shù)據(jù)聲明的主要形式：⑴ 常數(shù)值⑵ 變量：數(shù)據(jù)類型的實例，可被修改。⑶ 常量：在其生命期中不可被賦值的變量

22、。如 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) 引用：引用類型用于為一個對象提供一個可替換的名字。對于某一個類型的對象的引用，所采用的聲明方式就是在該類型后面添上一個符號?。例如,

23、int x=9; int ?y=x; x=13printf(“x=%d,y=%d”,x,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)的

24、程序塊內(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++的局部變量的作用域從其聲明開始到結(jié)束程序塊的右花括號終止。因此，變量聲明之前的語句即使在同一個程序塊內(nèi)也不能引用該變量。變量聲明不能放在while 、do/wh

25、ile、for 和 if 結(jié)構(gòu)的條件中。 把變量聲明放在靠近首次引用的位置，即用到時再聲明后寫上使用，可提高程序的可讀性。,在整個程序中都能引用的變量叫全局變量。如果一個全局變量在文件1中聲明，而在文件2中使用，則在文件2中必須使用關(guān)鍵字extern對該變量進(jìn)行聲明。 在構(gòu)成一個程序的兩個文件中，如果分別聲明了具有相同名字的一個全局變量，它們分別代表不同的實體，此時就要在兩個文件中分別使用關(guān)鍵字static對變量進(jìn)行聲明，以保證不發(fā)

26、生混淆。 如果一個程序塊中某個局部變量與某個全局變量同名，但又要在該程序塊中引用該全局變量，則可以使用域操作符::來引用全局變量。,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和將被輸

27、出的每一內(nèi)容之間用操作符<< 分開。。此外，定向到錯誤文件的命令由cerr定義。,例1-3 程序：C++中的輸入輸出,# include void main( ) {int x,y;cin > >x > >y;cout< <“x=”< < x < < endl;cout < <“y=”< < y < < endl;

28、},執(zhí)行上述程序時，按照輸入格式 5 10 〈回車〉或 5 〈回車〉 10 〈回車〉均使變量X和Y分別得到輸入值5和10，并輸出如下結(jié)果： x=5 y=10,C++中的輸入輸出， “自由格式”。程序員不必使用格式化符號來指明輸入輸出項的類型

29、和順序。 輸入輸出操作符能夠被重載。 如有對文件的輸入輸出，則必須在程序中包含頭文件 fstream.h，它定義了類 ifstream 、ofstream 和 fstream。 要創(chuàng)建一個輸入流，必須聲明它為類ifstream。要創(chuàng)建一個輸出流，必須聲明它為類ofstream。而執(zhí)行輸入輸出的流必須聲明為類fstream。,例1-4 含有文件輸入輸出的程序# include# includevoid main

30、（ ）{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

31、<< “f:”<< f << endl;},1.3.4 函數(shù),C++中有兩種函數(shù)：常規(guī)函數(shù)和成員函數(shù)。成員函數(shù)用于類方法的定義，完成一個特定的功能。 無論是常規(guī)函數(shù)還是成員函數(shù)，其定義都包括四個部分： 函數(shù)名 形式參數(shù)表 返回類型 函數(shù)體。函數(shù)的使用者通過函數(shù)名來調(diào)用函數(shù)，調(diào)用過程把實際參數(shù)傳送給相應(yīng)的形

32、式參數(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;

33、},對于不返回值的函數(shù)，其返回類型要聲明為 void。在C++中，指定空參數(shù)列表的方法是在圓括號中寫入void,或什么也不寫。,下面的程序例子，演示了聲明和使用不帶參數(shù)的函數(shù)的方法。,例1-6 使用不帶參數(shù)的函數(shù)# includevoid f1( )；void f2 (void)；main( ) { f1( )； f2( )；return 0;},void f1 ( ) {cout < <“Func

34、tion f1 takes no arguments \n”；}void f2(void) {cout < <“Function f2 also takes no arguments\n”；},輸出結(jié)果為： Function f1 takes no arguments Function f2 also takes no arguments,1.3.5 參數(shù)傳遞,函數(shù)調(diào)用時傳送

35、給形參表的實參與形參在類型、個數(shù)以及順序上必須保持一致。 C++中函數(shù)的參數(shù)傳遞有四種方式： 值參數(shù)傳遞 引用參數(shù)傳遞 常值參數(shù)傳遞 常值引用參數(shù)傳遞 值參數(shù)傳遞是缺省的參數(shù)傳遞方式。若采用這種傳遞方式，程序在運(yùn)行時，對應(yīng)的實際參數(shù)的值傳送給形式參數(shù)所對應(yīng)的局部工作區(qū)中的單元。,當(dāng)函數(shù)的執(zhí)行終止時，函數(shù)修改的是形式參數(shù)所對應(yīng)的工作單元的值，而該

36、值不傳回給實際參數(shù)。因此值參數(shù)的傳遞方式不會改變對應(yīng)形式參數(shù)的實際參數(shù)的值。使用引用參數(shù)傳遞方式時，需要在函數(shù)的形參表中將形參聲明為引用類型，即在參數(shù)名前加上一個“＆”。當(dāng)一個實參與一個引用類型形參結(jié)合時，被傳遞的不是實參的值，而是實參的地址，函數(shù)通過地址存取被引用的實參。當(dāng)函數(shù)執(zhí)行時，任何對形式參數(shù)的改變也就是對實際參數(shù)的改變。,當(dāng)要求一個函數(shù)調(diào)用返回多于一個參數(shù)時，也應(yīng)采用參數(shù)傳遞方式。此時，將參數(shù)中的一個由return語句

37、返回，而其它參數(shù)由引用返回。常值引用參數(shù)傳遞方式的格式為const T﹠a，其中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 ExampleByRefer(i

38、nt ＆a, int ＆b, int ＆c) {代碼同上}int ExampleByConsRefer(const int＆a,const int＆b,const int＆c) {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:”<< p<<q&l

39、t;<r<<s<<“\n”;s=ExampleByRefer(p,q,r);cout<<“p,q,r and S:”<<p<<q<<r<<s<<“\n”;s=ExampleByConsRefer(p,q,r);cout<<“p,q,r, and s:”<<p<<q<<r<&l

40、t;s<<“\n”;},輸出結(jié)果： 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

41、，9，12，3。調(diào)用 ExampleByConsRefer 時，實際參數(shù)p，g、r不會改變，保留字const保證只能對其值初始化一次，因而輸出結(jié)果為6，9，12，9。,1.3.6 函數(shù)名重載,在C++中，允許在同一個程序中用同一個名字定義多個函數(shù)，但它們的形參表不同。這種能力稱為函數(shù)名重載。 在調(diào)用一個重載的函數(shù)時，編譯程序通過檢查參數(shù)的個數(shù)、類型和順序,自動選擇一個合適的函數(shù)。函數(shù)重載通常用來建立在不同數(shù)據(jù)類型的基礎(chǔ)上完

42、成類似任務(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( ) {

43、 printf(“sum(2,3)= %d”,sum(2,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

44、、float等等）。則語句 ptr=new ptrtype 從程序的空閑內(nèi)存區(qū)中為ptrtype類型的對象分配內(nèi)存。new運(yùn)算符以類型為參數(shù)，自動建立一個具有合適大小的對象，并返回指向該類型對象的指針，此處類型為ptrtype，返回的指針為ptr。如果分配內(nèi)存不成功，則返回一個空指針，在C++中，以0而不是null來表示空指針。,在C++中，用如下語句來釋放該對象所占用的空間：delete ptr；運(yùn)算符delete 只

45、能釋放用運(yùn)算符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語言中

46、的malloc( )和free（ ）類似，但更方便。首先new按指定類型自動分配足夠的空間，不要求調(diào)用者提供所需存儲空間的數(shù)量并使用sizeof 運(yùn)算符進(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)

47、C++用數(shù)組存儲許多相同類型的相關(guān)信息。有些數(shù)據(jù)信息是由若干不同數(shù)據(jù)類型的數(shù)據(jù)所組成。例如，一個職工工資記錄包括姓名、工號和工資等，這些數(shù)據(jù)信息的類型是不一樣的，不能用數(shù)組直接把它們組織起來。用結(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ù)類型的說明

48、括起來。 通常，結(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)類型變量，右操作元為結(jié)構(gòu)中的成員。,在數(shù)組中，稱數(shù)組分量為元素，在結(jié)構(gòu)中，稱結(jié)構(gòu)

49、分量為成員。數(shù)組的[]運(yùn)算符與結(jié)構(gòu)的點運(yùn)算符具有相同的運(yùn)算優(yōu)先級，它們是所有運(yùn)算符中優(yōu)先級最高的。每個分量數(shù)據(jù)類型可以相異。結(jié)構(gòu)的成員有自己單獨(dú)的名字。結(jié)構(gòu)可以被賦值。,例1-9 聲明一個關(guān)于職工工資記錄的結(jié)構(gòu)，并使用它。// Person-salary. cpp # include struct person{char name [20]; // 姓名unsigned l

50、ong id; // 工號 int salary; // 工資 };,void main( ){ person pr1={″Frank Voltaire″,12345678, 2456};person pr2;pr2=pr1;cout << pr2.name <<″ ″ << pr2.id <

51、;<″ ″ << pr2.salary <<endl;}運(yùn)行結(jié)果為： Frank Voltaire 12345678 2456,在結(jié)構(gòu)Person中，成員name是一個字符數(shù)組，通過結(jié)構(gòu)變量的賦值，該數(shù)組作為成員也被賦值了。 兩個不同結(jié)構(gòu)名的變量是不允許相互賦值的，即使兩者包含有同樣的成員。 根據(jù)結(jié)構(gòu)類型可以定義一個變量，是變量就有地址。結(jié)構(gòu)變量不是指針。通過取地址“&

52、amp;”操作，可以得到結(jié)構(gòu)變量的地址，這個地址就是結(jié)構(gòu)的第一個成員地址。 可以將結(jié)構(gòu)變量的地址賦給結(jié)構(gòu)指針，結(jié)構(gòu)指針通過箭頭操作符“->”（也是一種結(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];

53、 unsigned long id; int salary;};,void main( ){ person pr1; person * prPtr; prPtr= & pr1; // 定義了一個結(jié)構(gòu)類型的指針 strcpy(prPtr->name, “David Marat”); prPtr- > id =987654321; prPtr

54、-> salary =2567; cout name id salary << endl;},運(yùn)行結(jié)果為： Davit Marat 987654321 2567 使用箭頭操作符就是對結(jié)構(gòu)成員進(jìn)行操作。但必須清楚，當(dāng)用點操作符時，它的左邊應(yīng)是一個結(jié)構(gòu)變量，當(dāng)用箭頭操作符時，它的左邊應(yīng)是一個結(jié)構(gòu)指針。 指針是有類型的，引用一個整型指針得到一個整數(shù)，引用一個結(jié)構(gòu)指針得到一個結(jié)構(gòu)。

55、結(jié)構(gòu)是一個數(shù)據(jù)類型，所以也可以擁有結(jié)構(gòu)數(shù)組。要定義結(jié)構(gòu)數(shù)組，必須先聲明一個結(jié)構(gòu)，然后定義這個結(jié)構(gòu)類型的數(shù)組。,例1-11 定義一個100個元素組成的Person結(jié)構(gòu)類型數(shù)組。,struct person{char name [20]; unsigned long id; int salary;};person allone [100]; // 定義一個person 類型的數(shù)組,結(jié)構(gòu)數(shù)組中，每個元素都是結(jié)構(gòu)變

56、量，訪問結(jié)構(gòu)數(shù)組元素中的成員，方法與前類似。,2.聯(lián) 合,聯(lián)合(union)是一種變量，它可以在不同時間內(nèi)維持不同類型和不同長度的對象。它提供了在單個存儲區(qū)域中操作不同類型數(shù)據(jù)的方法，而無需在程序中存放與機(jī)器有關(guān)的信息。聯(lián)合的語法是以結(jié)構(gòu)為基礎(chǔ)的。例 1-12 定義一個聯(lián)合,union utag {int ival; float fval; char *pval;} uval；,聯(lián)合元素的引用，語法

57、上也類似于結(jié)構(gòu)成分的引用：union-name.member 或 union-pointer->member如果變量utype是用來記錄存儲在uval中的最近類型的，那么可使用下列程序段存取聯(lián)合中的元素。,if (utype == INT) printf(“%d\n”, uval.ival);else if (utype == FLOAT) printf(“%d\n”, uval.fval);e

58、lse if (utype == STRING) printf(“%d\n”, uval.pval);elseprintf(“bad type %d in utype\n”, utype);,聯(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

59、 flags; int utype; union { int ival; float fval; char *pval; } uval;} symtab[NSYM];,聯(lián)合是一種形式特殊的結(jié)構(gòu)變量。和結(jié)構(gòu)一樣，對聯(lián)合施加的操作只

60、能是存取成員和取其地址。不能把聯(lián)合作為參數(shù)傳遞給函數(shù)，也不能由函數(shù)返回聯(lián)合。 聯(lián)合只是一種變量，為了弄請在聯(lián)合中存儲的是哪一種類型，通常是在聯(lián)合外設(shè)置一個變量以作表征。正如在systab中，每一個結(jié)構(gòu)，都含有整型變量utype以指出在該結(jié)構(gòu)的聯(lián)合uval中存儲的是什么類型的變量。 結(jié)構(gòu)中往往含有幾個不同類型的變量。如systab中就有四個變量。,1.4 算法性能與復(fù)雜度,公元825年，一位名叫阿爾? 花拉子米（al-Kho

61、warizmi）的波斯數(shù)學(xué)家寫了一本教科書，書中概括了進(jìn)行數(shù)字四則算術(shù)運(yùn)算的法則，所有的數(shù)字都是用今天的印度十進(jìn)制形式來表示的（按個、十、百位等排列，并有表示小數(shù)部位的小數(shù)點）?，F(xiàn)代名詞“算法” (algorithm) 就來源于這位數(shù)學(xué)家的名字。 在計算機(jī)科學(xué)里，算法這個詞有一個專門的解釋：算法─用計算機(jī)解題的精確描述。1.4.1 算法的定義通常，人們將算法定義為一個用于實現(xiàn)某個特定任務(wù)的有窮指令集，這些指令規(guī)定了一個

62、運(yùn)算序列。,一個算法應(yīng)當(dāng)具有以下特性：⑴ 輸入性 一個算法必須具有零個或多個輸入量。⑵ 輸出性 一個算法應(yīng)有一個或多個輸出量，輸出量是算法計算的結(jié)果。⑶ 確定性 算法中的每一條指令應(yīng)含義明確，無歧義。⑷ 有窮性 算法中的指令執(zhí)行序列是有窮的。⑸ 有效性 每條指令必須是足夠基本的。一個程序與一個算法對于上述⑷是有重大區(qū)別的。一個程序可以不滿足特性⑷。一個程序可能會不終止。本書中所給出的程序均是可終止的，所以在本書中對“算法”

63、和“程序”這兩個術(shù)語不作嚴(yán)格的區(qū)分。,算法設(shè)計者在構(gòu)思和設(shè)計了一個算法之后，必須準(zhǔn)確清楚地將所設(shè)計的解題步驟記錄下來，或提供交流，或編寫成程序供計算機(jī)執(zhí)行。記錄算法中的解題步驟又叫描述算法。常用的描述算法的方式有自然語言、流程圖和程序設(shè)計語言等。自然語言(如漢語或英語)： 優(yōu)點：使用者不必對描述工具本身花精力去學(xué)習(xí)，對寫出來的算法的理解是接的。缺點：容易出現(xiàn)二義性；語句一般太長， 使得所建立的算法也顯得冗長

64、；算法中的分支及循環(huán)等結(jié)構(gòu)表示不能清晰地顯示出來,規(guī)定式樣的圖形、指向線和文字說明組合起來的流程圖方式：優(yōu)點：直觀、清晰、易懂，便于檢查、修改和交流。缺陷：嚴(yán)密性不如程序設(shè)計語言，靈活性不及自然語言；此外，對于大型的算法描述有困難。計算機(jī)程序設(shè)計語言：優(yōu)點：顯得清晰、明了，寫出的算法一步到位，能由計算機(jī)處理。事實上，用程序設(shè)計語言來描述算法，就是對算法的實現(xiàn)。缺點：抽象性差一些，可能會使寫算法的人拘泥于計算步驟描述的細(xì)節(jié)，而忽

65、略算法的實質(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é)合的方式來描述算法，有時

66、對算法加以合適的注釋。,1.4.2 算法的性能標(biāo)準(zhǔn),算法的設(shè)計主要有以下幾個標(biāo)準(zhǔn)：(1) 正確性 算法應(yīng)確切地滿足所要求解的問題的需求。(2) 可用性 算法應(yīng)能很方便地使用。 (3) 可讀性 算法應(yīng)是可讀的，即易于理解的。 (4) 效率 算法的效率主要是指算法執(zhí)行時存儲單元的開銷和運(yùn)行時間的耗費(fèi)，前者稱為算法的空間代價，后者稱為算法的時間代價。(5) 健壯性 當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)能作出適當(dāng)?shù)奶幚?，而不?yīng)當(dāng)產(chǎn)生不可預(yù)料的結(jié)

67、果。,在設(shè)計一個算法時，上述的幾條標(biāo)準(zhǔn)有時會有矛盾，如可用性強(qiáng)、可讀性強(qiáng)會降低算法的效率。而對效率這個標(biāo)準(zhǔn)，算法的低時間代價和低空間代價也會產(chǎn)生矛盾。例如，有些問題若采用較多的內(nèi)存空間可使時間代價降低，若采用較少的內(nèi)存空間，則使時間代價提高。在計算機(jī)硬件價格快速下降的趨勢下，算法的時間效率應(yīng)首先予以考慮。,1.4.3 算法復(fù)雜度,算法效率的度量一般采用兩種方法: 事前估計 后期測試?yán)鐚τ诔绦蜻\(yùn)行

68、的時間耗費(fèi)，后期測試主要通過在算法中的某些部位插裝計時函數(shù)來測定算法完成某一規(guī)定功能所需的時間。但這種方法與算法的運(yùn)行環(huán)境有關(guān)。同樣的算法在速度不同的計算機(jī)上運(yùn)行，執(zhí)行速度相差卻非常大；此外，一個算法用不同的編譯系統(tǒng)編譯出的目標(biāo)代碼的長度不一樣，質(zhì)量也不一樣，完成同樣的功能所需時間也不同；,還有，對于一個存儲需求很大的算法，如果可用的存儲空間不夠，在運(yùn)行時不得不頻繁地進(jìn)行內(nèi)外存交換，需要的運(yùn)行時間就很多。而如果可用的存儲空間足夠大，

69、運(yùn)行時間就可以大大減少。因此，算法的實際運(yùn)行時間依賴于所用的計算機(jī)系統(tǒng)。在不同的機(jī)型、不同的編譯系統(tǒng)版本、不同的硬軟件配置情況下，想通過后期測試的方法來測定算法的復(fù)雜度是比較困難的。因此人們常常采用事前估計即對算法進(jìn)行分析的方法來測定算法的復(fù)雜度。因為算法的復(fù)雜度與具體的運(yùn)行環(huán)境和編譯系統(tǒng)無關(guān)，所以可以通過復(fù)雜度的分析來對算法進(jìn)行比較和評估。,1. 算法的時間復(fù)雜度,算法的時間復(fù)雜度與具體的機(jī)器以及運(yùn)行環(huán)境無關(guān)，它與所求解的問題的