《普通高等教育"十一五"國家級規劃教材:C/C++與數據結構(上冊)(第4版)》由清華大學出版社出版。《普通高等教育"十一五"國家級規劃教材:C/C++與數據結構(上冊)(第4版)》特色有:1、綜合連貫。把C、C++和C++標準類模板貫穿起來,一氣呵成,系統地展示了從C到C++、再到C++標準類模板的必然發展。2、對比易懂。不僅學習,而且將C++與C進行對照,因為只有這樣,才會使人感到心智在生長、在擴展。3、標準規范。實現了類模板庫的string、vector和list及適配器,高屋建瓴。4、課件配套。《普通高等教育"十一五"國家級規劃教材:C/C++與數據結構(上冊)(第4版)》配有基于Authorware開發的多媒體助學助教軟件,所有程序在課件中都有數據結構、算法、代碼、運行及結果的跟蹤演示,而且數據自由輸入,為微課和MOOC的建設給予應有的技術支撐。
縱觀短暫的計算機發展史,算法和數據結構這兩個主要方面一直保持不變。發展演化的只是它們之間的關系,就是所謂的程序設計。——Stanley B.Lippman當一門學科的實證的知識材料積累到相當豐富的時候,就需要依據這些材料的內在聯系把它們條理化、系統化,以便更有效地把握和運用這些知識。因此,這門學科就走進了邏輯思維(即理論思維)的領域。
每一個中學畢業生都學過幾何學,即來自《幾何原本》的幾何學。它就是對人類四百多年的幾何知識材料進行系統化的結果。它從幾個公理出發,按照形式邏輯規則,推導出所有幾何定理。這便是著名的數學公理化方法,也稱為形式邏輯。這種方法是把學科的知識材料系統化的一種有效手段。
但是,某一學科的公理化方法只有在這個學科成熟的時候才會出現。如果一個學科在不斷的發展中,例如,計算機程序語言,盡管有機器語言、匯編語言、C語言、C++語言、C#和Java,但每年還有幾十種程序語言出現,對這種學科的知識材料進行系統化,就需要另一種邏輯——辯證邏輯,因為辯證邏輯是從事物的發展和變化中來觀察事物。
辯證邏輯的出現主要依賴于自然科學和工業的強大而日益迅猛的發展,例如,細胞、能量轉換和進化論的發現。這些發現使人們不僅能夠說明自然界中各個領域內的過程之間的聯系,而且總的說來也能夠說明各個領域之間的聯系。
辯證邏輯的核心是對立統一規律:一切事物都存在矛盾,矛盾的雙方既對立又統一,從而推動著事物的發展。
程序語言的矛盾實質上是程序設計的矛盾,這個矛盾是數據結構和算法。數據結構是一組有組織的數據和對數據的基本操作,算法是用基本操作表示的對數據進行處理的有限步驟。而程序語言是表示某類數據結構的語言,因此數據結構和算法的矛盾,也是程序語言和算法的矛盾。
為什么說數據結構和算法是一對矛盾呢?因為沒有不依賴數據結構的算法,也沒有不支持算法的數據結構,這是它們的相互統一;數據結構是相對穩定的,就像程序語言是相對穩定的一樣,而算法是越來越復雜的, 當算法復雜到一定程度的時候, 就要求數據結/C/C++與數據結構(第4版)(上冊)前言/構繼續發展,這是它們的相互對立。
因為C和C++屬于核心的程序語言,所以本書把它們和數據結構作為研究對象,對它們的知識進行系統化。本書不從概念出發,而從算法的需要出發,一個問題解決了,新的問題又出現了,一個問題的鏈條,對應一個解答的鏈條;每一個問題都是程序設計中的問題,每一個問題的解決都產生新的程序,并產生新的概念;因此,從C到C++,再到C++標準模板庫,其概念都是在針對具體問題而精心設計的程序鏈條中,沿著必然的發展過程,以一個擴展一個、一個轉換一個的方式彼此聯系著。在這個過程中,你感受最深的不是有一個高高在上的思想者的存在,他要你做什么,而是實實在在的你個人的存在,你知道要做什么,你可以清楚地描述出每一個問題是如何產生又如何解決的,而且這個過程不因人而異。
本書的脈絡如下。
(1) 第1章機器語言模式。機器語言并不是本書要具體學習的內容,而僅僅是作為全書的邏輯起點,在這個起點上,計算機僅僅是可以逐條執行機器指令的工具。
為此,本章僅用很少的、虛擬的機器指令構成一臺計算機,同時通過執行一個簡單的求和程序,引入存儲器、地址、寄存器、程序計數器等基本概念,它們屬于計算機體系結構的內容。
例1.1和例1.2闡述了數據結構和算法在機器語言層面上的相互作用,在這個過程中產生的程序入口地址、子程序調用、斷口地址、現場保護、棧等基本概念。
機器語言的局限性首先是不易閱讀,克服這個局限性產生了匯編語言和匯編程序。
機器語言的另一個局限性是算法描述力不足,一個簡單的算法就需要很多條機器指令,為了克服這個局限性,產生了高級語言。
(2) 第2章C語言模式。C語言主要用基本數據類型表示數據結構,基本操作的形式主要是運算符表達式。每一個運算符表達式都對應一個機器語言程序,這是數據結構和算法在不同層面上的相互轉換。
(3) 第3章函數。函數是對運算符表達式的擴展,即對運算符表達式的局限性的克服。程序設計由此進入過程化。
(4) 第4章一維數組和指針。由處理一個對象擴展到處理一組對象,即數組,使對象的訪問方式由基于對象名稱的直接訪問方式發展到基于對象指針的間接訪問方式。
(5) 第5章C字符串。C字符串不僅是一個構造類型,也是C語言提供的過程化程序設計的范例。
(6) 第6章結構體、聯合體和枚舉。C語言提供了半類型自定義機制。所謂半類型,是指因為不能封裝和不能深復制等原因,所以不能和基本類型一樣使用的自定義類型。
(7) 第7章順序表。順序表是改進的數組。
(8) 第8章鏈表。順序表是線性連續結構,鏈表是線性非連續結構,與順序表相比,鏈表在插入和刪除操作方面提高了效率。
(9) 第9章C的流與文件。每一個文件都對應一個指針,在標準文件的讀寫函數中,這個指針被隱藏了。把隱藏的指針顯式地表示出來,通過類比,輕松地進入磁盤文件的讀寫操作。
(10) 第10章二維數組和指針。它是一維數組和指針的自然推廣。
(11) 第11章從C到C++。順序表暴露出C語言固有的局限性,由此產生了C++的基本概念,逐一克服了這些局限性。
(12) 第12章順序表類。綜合運用第11章的C++基本概念,把C順序表轉換為C++順序表類。
(13) 第13章String類。把C字符串轉換為C++的String類。
(14) 第14章Date類。把C結構體Date擴展為C++的Date類。
(15) 第15章非線性結構與遞歸。把遞歸與樹形結構聯系起來講解,是本書的特色之一。
(16) 第16章繼承和多態性。由C過程化程序設計進入C++面向對象程序設計。
(17) 第17章向量類模板。把順序表類擴展為向量類模板。
(18) 第18章鏈表類模板和適配器。把C鏈表擴展為C++鏈表類模板,并以此為底層結構,生成鏈隊列和鏈棧。
(19) 第19章C++綜合設計實例。
(20) 第20章C++的流與文件。把C的文件讀寫函數轉換為C++的文件讀寫函數。
(21) 第21章名字空間。
編者2015年9月
第1章機器語言模式1
1.1模擬機器指令集與程序設計舉例1
1.2機器語言的局限性7
問題與練習8第2章C語言模式9
2.1基于基本類型的編程模式9
2.2基本數據類型19
2.2.1整型19
2.2.2實型21
2.2.3字符型22
2.3運算符和表達式25
2.3.1自增、自減運算符和表達式25
2.3.2復合賦值運算符和表達式26
2.3.3條件表達式和逗號表達式26
2.3.4關系運算符和邏輯運算符27
2.3.5運算符優先級29
2.4類型轉換29
2.5程序流程控制結構30
2.5.1ifelse語句31
2.5.2switchcase語句32
2.5.3break語句和continue語句34
問題與練習35/C/C++與數據結構(第4版)(上冊)目錄/第3章函數38
3.1函數自定義與調用38
3.2函數聲明與定義43
3.3函數與變量的存儲類別44
3.3.1自動局部變量45
3.3.2靜態局部變量48
3.3.3外部變量49
3.4函數應用設計舉例51
3.4.1階乘累加51
3.4.2求π的近似值52
3.4.3求最大公約數53
3.4.4判斷質數54
3.4.5數制轉換55
3.5模塊化程序設計56
3.5.1全局外部函數57
3.5.2靜態外部函數58
3.5.3全局外部變量59
3.5.4靜態外部變量60
3.6編譯預處理61
3.6.1無參宏指令61
3.6.2帶參宏指令62
3.6.3條件編譯指令64
3.6.4文件包含指令66
問題與練習68第4章一維數組和指針70
4.1指針和指針傳遞70
4.2一維數組和指針75
4.2.1一維數組75
4.2.2指向一維數組的指針78
4.2.3數組類型和數組首元素類型81
4.3const型指針83
4.4動態數組86
4.5數組和指針應用舉例90
4.5.1Josephus問題90
4.5.2選擇排序93
4.5.3起泡排序96
4.5.4劃分數組元素98
4.5.5刪除數組中的重復數據101
4.5.6篩法求質數102
4.5.7順序搜索和二分搜索104
4.6索引和指針107
4.7指針和左值108
4.8函數指針108
問題與練習109第5章C字符串111
5.1字符串常量和字符串變量111
5.2字符串基本操作函數原型117
5.3字符串基本操作函數實現118
5.4字符串基本操作函數的補充122
5.4.1取子串123
5.4.2子串插入125
5.4.3子串刪除127
5.4.4字符查找128
5.5模式匹配129
問題與練習131第6章結構體、聯合體和枚舉133
6.1結構體133
6.1.1結構體定義133
6.1.2結構體變量和typedef名字134
6.1.3結構體變量的初始化和賦初值135
6.1.4結構體數組136
6.1.5結構體的嵌套138
6.1.6結構體返回值和指針傳遞139
6.1.7數組和含有數組的結構體變量140
6.2聯合體142
6.3枚舉145
6.4結構體應用設計舉例147
6.4.1模擬洗牌147
6.4.2Date結構體149
6.4.3三天打魚,兩天曬網153
問題與練習154第7章順序表158
7.1數組的局限性158
7.2順序表聲明與實現159
7.2.1順序表聲明160
7.2.2順序表實現164
7.3索引和指針169
7.4數據抽象和封裝171
問題與練習171第8章鏈表173
8.1鏈表的結構分析173
8.2鏈表的聲明和實現179
問題與練習185第9章C的流與文件186
9.1文件指針186
9.2文件打開與關閉187
9.3文件的讀寫191
9.3.1字符的讀寫 191
9.3.2字符串的讀寫193
9.3.3無格式讀寫194
9.3.4格式讀寫197
9.3.5文件的隨機訪問199
問題與練習201第10章二維數組和指針204
10.1二維數組和指針204
10.2二維數組和一維數組211
10.3馬鞍點213
10.4指針數組和二級指針215
10.5指針數組與二維數組217
問題與練習219第11章從C到C++221
11.1C語言的固有局限性221
11.2內聯函數224
11.3運算符重載和函數重載225
11.3.1運算符重載225
11.3.2函數重載227
11.4引用型230
11.4.1概念的由來230
11.4.2引用型及其應用233
11.5函數模板235
11.6提取符和插入符237
11.7默認參數239
11.8深入討論——函數模板實例化中的問題241
問題與練習242第12章順序表類243
12.1從C順序表到C++順序表類243
12.2new和delete操作符249
12.3需要增加、刪除和修改的成員函數250
12.4順序表類的聲明和實現258
12.5類模板259
12.6基本類型賦值形式的擴展264
問題與練習265第13章String類266
13.1String類的聲明266
13.2String類的實現269
13.2.1構造函數和析構函數269
13.2.2成員賦值運算符271
13.2.3成員轉換272
13.2.4串連接274
13.2.5關系運算278
13.2.6求子串279
13.2.7子串插入280
13.2.8子串刪除284
13.2.9下標運算符285
13.2.10字符查找285
13.2.11輸入輸出287
13.3模式匹配289
13.4String類的深入討論291
13.4.1轉換賦值運算符函數的替代291
13.4.2成員函數“類串+C串”的替代291
13.4.3explicit修飾符292
問題與練習293第14章Date類295
14.1Date類的聲明295
14.2Date類的實現299
14.3靜態數據成員和靜態成員函數304
14.4封裝的典型應用307
問題與練習309第15章非線性結構與遞歸310
15.1樹形結構與遞歸310
15.2C++遞歸函數315
15.3漢諾塔問題316
15.4快速排序320
15.5八皇后321
問題與練習326第16章繼承和多態性327
16.1構造函數的參數初始化表327
16.2繼承330
16.3受保護成員332
16.4多態性和虛函數333
16.5虛析構函數337
16.6純虛函數和抽象類338
問題與練習342第17章向量類模板344
17.1向量類模板的聲明和實現344
17.2函數對象351
問題與練習354第18章鏈表類模板和適配器356
18.1鏈表類模板List356
18.2鏈表和鏈表類模板的代碼對比368
18.3適配器371
18.3.1鏈棧371
18.3.2鏈隊列372
18.3.3優先級鏈隊列373
問題與練習374第19章C++綜合設計實例375
19.1中綴表達式求值375
19.2事件驅動模擬380
問題與練習391第20章C++的流與文件392
20.1格式化輸入輸出393
20.1.1設置流的格式化標志393
20.1.2格式輸出函數395
20.1.3操作算子396
20.2文件的讀寫399
20.2.1字符讀寫函數400
20.2.2字符串讀寫函數402
20.2.3無格式讀寫函數402
20.2.4格式讀寫404
20.2.5隨機訪問406
20.3文件錯誤處理407
問題與練習408第21章命名空間409
21.1命名空間的定義409
21.2using namespace語句410
21.3命名空間的成員412
21.4命名空間的別名414
問題與練習414附錄A命名規則415附錄B常用的ANSI C標準庫函數416參考文獻423