數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）習(xí)題解答及實(shí)訓(xùn)指導(dǎo)

1．配套教材的習(xí)題解答及典型例題分析、上機(jī)實(shí)訓(xùn)指導(dǎo)、模擬試題及參考答案

2．典型例題的算法分析、算法實(shí)現(xiàn)

3．10個(gè)上機(jī)實(shí)訓(xùn)內(nèi)容，均有實(shí)訓(xùn)目的、算法提示、算法分析、算法實(shí)現(xiàn)

4．10套模擬試題，以檢測(cè)學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、掌握數(shù)據(jù)結(jié)構(gòu)知識(shí)的程度

5．與《數(shù)據(jù)結(jié)構(gòu)（C++版）》一書(shū)的內(nèi)容緊密結(jié)合

   數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)專(zhuān)業(yè)及相關(guān)專(zhuān)業(yè)的一門(mén)重要專(zhuān)業(yè)基礎(chǔ)課，也是一門(mén)必修的核心課程。在計(jì)算機(jī)科學(xué)的各領(lǐng)域中，都將會(huì)用到各種不同的數(shù)據(jù)結(jié)構(gòu)，如編譯系統(tǒng)中要使用棧、散列表、語(yǔ)法樹(shù)等；操作系統(tǒng)中要使用隊(duì)列、存儲(chǔ)管理表、目錄樹(shù)等；數(shù)據(jù)庫(kù)系統(tǒng)中要使用線(xiàn)性表、鏈表、索引樹(shù)等；人工智能中要使用廣義表、檢索樹(shù)、有向圖等；同樣在面向?qū)ο蟮某绦蛟O(shè)計(jì)、計(jì)算機(jī)圖形學(xué)、軟件工程、多媒體技術(shù)、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域，都將會(huì)用到各種不同的數(shù)據(jù)結(jié)構(gòu)。因此，學(xué)好數(shù)據(jù)結(jié)構(gòu)這門(mén)課程，對(duì)于從事計(jì)算機(jī)技術(shù)及相關(guān)領(lǐng)域工作的人員來(lái)說(shuō)是非常重要的，它可以使你掌握好各種不同的數(shù)據(jù)結(jié)構(gòu)、在什么場(chǎng)合使用及算法的具體實(shí)現(xiàn)，以及每一種算法的時(shí)間復(fù)雜度分析和空間復(fù)雜度分析，知道在哪種情況下使用哪種數(shù)據(jù)結(jié)構(gòu)最方便，為以后開(kāi)發(fā)大型程序而使用各種不同的數(shù)據(jù)結(jié)構(gòu)奠定基礎(chǔ)。

    由于數(shù)據(jù)結(jié)構(gòu)的原理和算法比較抽象，而該課程一般在剛學(xué)完程序設(shè)計(jì)后開(kāi)設(shè)，學(xué)生程序設(shè)計(jì)方面的知識(shí)較少，因此，對(duì)于僅具有一些計(jì)算機(jī)程序設(shè)計(jì)知識(shí)的初學(xué)者來(lái)說(shuō)，理解和掌握數(shù)據(jù)結(jié)構(gòu)中的原理和算法就比較困難，在解答數(shù)據(jù)結(jié)構(gòu)習(xí)題時(shí)，往往感到無(wú)從下手，更不知道算法如何描述、如何編寫(xiě)，作者在多年的教學(xué)過(guò)程中深有感觸。作者通過(guò)多年的教學(xué)實(shí)踐，收集、整理進(jìn)而編寫(xiě)了這本《數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）習(xí)題解答及實(shí)訓(xùn)指導(dǎo)》，目的是通過(guò)對(duì)習(xí)題的解答，使學(xué)生充分掌握數(shù)據(jù)結(jié)構(gòu)的原理、求解數(shù)據(jù)結(jié)構(gòu)問(wèn)題的思路和方法，以及最后編寫(xiě)出正確的算法，進(jìn)一步加深對(duì)基本概念的理解，提高分析問(wèn)題和解決問(wèn)題的能力，為整個(gè)專(zhuān)業(yè)的學(xué)習(xí)打下堅(jiān)實(shí)基礎(chǔ)，為適應(yīng)今后的大型軟件開(kāi)發(fā)提供和積累較豐富的經(jīng)驗(yàn)。

    本書(shū)是《數(shù)據(jù)結(jié)構(gòu)（C++版）》（第二版）的配套指導(dǎo)教材。全書(shū)內(nèi)容共分三大部分。第一部分為習(xí)題解答部分，包含配套教材中的習(xí)題和一些綜合題，主要是對(duì)配套教材中的習(xí)題給出解答思路提示、算法分析，最后再給出完整的答案、算法或程序。每章的習(xí)題都包含基本概念和算法設(shè)計(jì)方面的題型，以幫助學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，提高用各種不同的數(shù)據(jù)結(jié)構(gòu)分析問(wèn)題、解決問(wèn)題的能力。第二部分為上機(jī)實(shí)驗(yàn)及指導(dǎo)部分，包含C++的上機(jī)環(huán)境介紹，并給出了10個(gè)上機(jī)實(shí)習(xí)內(nèi)容，每個(gè)上機(jī)實(shí)習(xí)都給出了多道上機(jī)題目，在每個(gè)上機(jī)實(shí)習(xí)中，都介紹了實(shí)習(xí)目的、采用的主要方法和算法設(shè)計(jì)技巧，最后給出了完整的C++源程序來(lái)實(shí)現(xiàn)算法，所有C++源程序都在C++環(huán)境下運(yùn)行通過(guò)。通過(guò)這些實(shí)驗(yàn)，可以使學(xué)生了解并學(xué)會(huì)如何運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)去解決現(xiàn)實(shí)世界中的某些實(shí)際問(wèn)題，并具備設(shè)計(jì)較復(fù)雜算法的基本能力。第三部分為模擬試題部分，包含模擬試題和參考答案。模擬試題主要是為了幫助學(xué)生在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程后自我檢驗(yàn)學(xué)習(xí)的效果。有易、較易、中等、較難等各種難度的題目分布在各套試題中，每套試題中有選擇、判斷、填空、應(yīng)用、算法設(shè)計(jì)等各種題型，試題覆蓋了教材中的大部分知識(shí)點(diǎn)，有助于學(xué)生對(duì)課程的系統(tǒng)復(fù)習(xí)。

    本書(shū)的目的是幫助學(xué)生學(xué)好數(shù)據(jù)結(jié)構(gòu)這門(mén)課程，所以在使用本書(shū)的過(guò)程中，請(qǐng)注意以下幾點(diǎn)：第一，使用該書(shū)要與《數(shù)據(jù)結(jié)構(gòu)（C++版）》（第二版）這本教材配套使用，以便與課程內(nèi)容同步，有利于進(jìn)一步掌握和理解各種基礎(chǔ)知識(shí)，加深對(duì)課堂所講授內(nèi)容的理解；第二，算法設(shè)計(jì)是不唯一的，每道題除了書(shū)中給出的算法外，讀者可能還會(huì)有其他的算法，這說(shuō)明讀者對(duì)這方面的知識(shí)掌握得很好；第三，該習(xí)題解答及指導(dǎo)是幫助學(xué)習(xí)和理解數(shù)據(jù)結(jié)構(gòu)知識(shí)的，請(qǐng)學(xué)生在做作業(yè)前，先自己動(dòng)腦思考、動(dòng)手寫(xiě)，不要盲目照抄，否則只會(huì)收到事倍功半的效果。

    本書(shū)的最大特點(diǎn)是采用面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言（C++語(yǔ)言）作為算法的描述語(yǔ)言，所有算法都已經(jīng)上機(jī)調(diào)試通過(guò)。但是，由于篇幅所限，大部分算法都是以單獨(dú)的函數(shù)形式給出，若讀者要運(yùn)行這些算法，還必須給出一些變量的說(shuō)明及主函數(shù)來(lái)調(diào)用所給的函數(shù)。因此，本書(shū)中的算法描述比原來(lái)數(shù)據(jù)結(jié)構(gòu)教材中用類(lèi)C/C++語(yǔ)言描述算法更直觀，學(xué)生更容易理解和接受。作者在十幾年的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中，對(duì)數(shù)據(jù)結(jié)構(gòu)中的各種算法進(jìn)行了認(rèn)真的研究和分析，在這方面積累了豐富的經(jīng)驗(yàn)，因此，本書(shū)中所選的綜合題和習(xí)題都具有一定的針對(duì)性，都是針對(duì)特定的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行描述的，方便學(xué)生理解和接受，并能為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)算法描述架橋鋪路。

    本書(shū)可以作為高等院校本、專(zhuān)科學(xué)生和教師學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的參考資料，也可以作為數(shù)據(jù)結(jié)構(gòu)自學(xué)者的參考書(shū)和參加碩士研究生入學(xué)考試的參考教材，同時(shí)還可供從事計(jì)算機(jī)應(yīng)用工作的工程與技術(shù)人員參考。選用該指導(dǎo)書(shū)上機(jī)實(shí)習(xí)的學(xué)校，可以根據(jù)學(xué)校本身的條件，在10個(gè)實(shí)習(xí)題中有針對(duì)性地選擇一部分或者全選。

    本書(shū)由李根強(qiáng)任主編，負(fù)責(zé)全書(shū)的統(tǒng)稿、修改、定稿工作，倪飛舟、鐘志水、郭清溥任副主編。主要編寫(xiě)人員分工如下：李根強(qiáng)編寫(xiě)第一部分的第6～8章和第二部分的第2章，倪飛舟編寫(xiě)第一部分的第1～3章和第二部分的第1章，鐘志水編寫(xiě)第一部分的第4、5章，史瑞芳編寫(xiě)第三部分，郭清溥編寫(xiě)第一部分的第9～11章。另外參加本書(shū)部分編寫(xiě)工作的還有：王剛、汪貴生、姚?、袁雋媛、蔡益紅、謝月娥、秦志、杜四春、銀紅霞、滿(mǎn)淑穎等。在本書(shū)的編寫(xiě)過(guò)程中，得到了湖南大學(xué)計(jì)算機(jī)與通信學(xué)院老師的大力支持，在此深表感謝。

    由于時(shí)間倉(cāng)促及作者水平有限，書(shū)中不妥和錯(cuò)誤之處在所難免，敬請(qǐng)廣大讀者批評(píng)指正。

前言
第一部分  習(xí)題與解答
第1章  緒論 1
1.1  基本概念 1
1.1.1  數(shù)據(jù)結(jié)構(gòu) 1
1.1.2  存儲(chǔ)方式 1
1.1.3  算法及評(píng)價(jià) 1
1.2  習(xí)題及解答 2
1.2.1  配套教材中的習(xí)題 2
1.2.2  綜合題 10
第2章  線(xiàn)性表 14
2.1  線(xiàn)性表的基本概念及其運(yùn)算 14
2.1.1  順序表 14
2.1.2  線(xiàn)性鏈表 14
2.1.3  雙向鏈表 14
2.1.4  循環(huán)鏈表 14
2.2  習(xí)題及解答 14
2.2.1  配套教材中的習(xí)題 14
2.2.2  綜合題 32
第3章  棧和隊(duì)列 38
3.1  基本概念及其運(yùn)算 38
3.1.1  棧 38
3.1.2  隊(duì)列 38
3.2  習(xí)題及解答 38
3.2.1  配套教材中的習(xí)題 38
3.2.2  綜合題 47
第4章  串 54
4.1  基本概念及運(yùn)算 54
4.1.1  串的順序存儲(chǔ)及運(yùn)算 54
4.1.2  串的鏈?zhǔn)酱鎯?chǔ)及運(yùn)算 54
4.2  習(xí)題及解答 54
4.2.1  配套教材中的習(xí)題 54
4.2.2  綜合題 63
第5章  多維數(shù)組和廣義表 68
5.1  基本概念及運(yùn)算 68
5.1.1  多維數(shù)組的概念及存儲(chǔ) 68
5.1.2  特殊矩陣及壓縮存儲(chǔ) 68
5.1.3  稀疏矩陣及壓縮存儲(chǔ) 68
5.1.4  廣義表的存儲(chǔ)及運(yùn)算 68
5.2  習(xí)題及解答 69
5.2.1  配套教材中的習(xí)題 69
5.2.2  綜合題 76
第6章  樹(shù)和二叉樹(shù) 82
6.1  樹(shù)的基本概念 82
6.1.1  樹(shù)的定義 82
6.1.2  基本術(shù)語(yǔ) 82
6.1.3  樹(shù)的表示 83
6.2  二叉樹(shù)的基本概念和性質(zhì) 83
6.2.1  二叉樹(shù)的定義 83
6.2.2  二叉樹(shù)的性質(zhì) 83
6.2.3  二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 84
6.2.4  二叉樹(shù)的基本運(yùn)算 84
6.2.5  二叉樹(shù)的應(yīng)用 84
6.2.6  樹(shù)、森林和二叉樹(shù)之間的相互關(guān)系 84
6.3  習(xí)題及解答 84
6.3.1  配套教材中的習(xí)題 84
6.3.2  綜合題 94
第7章  圖 103
7.1  圖的基本概念及運(yùn)算 103
7.1.1  圖的基本術(shù)語(yǔ) 103
7.1.2  圖的存儲(chǔ)形式 104
7.1.3  圖的基本運(yùn)算 104
7.2  習(xí)題及解答 104
7.2.1  配套教材中的習(xí)題 104
7.2.2  綜合題 126
第8章  查找 135
8.1  基本概念 135
8.1.1  順序查找 135
8.1.2  二分查找 135
8.1.3  分塊查找 135
8.1.4  二叉排序樹(shù)查找 135
8.1.5  散列查找 136
8.2  習(xí)題及解答 136
8.2.1  配套教材中的習(xí)題 136
8.2.2  綜合題 142
第9章  內(nèi)排序 148
9.1  基本概念 148
9.1.1  插入排序 148
9.1.2  交換排序 148
9.1.3  選擇排序 148
9.1.4  歸并排序 148
9.1.5  分配排序 148
9.2  習(xí)題及解答 148
9.2.1  配套教材中的習(xí)題 148
9.2.2  綜合題 159
第10章  外排序 164
10.1  外排序的基本概念 164
10.1.1  基本概念 164
10.1.2  初始?xì)w并段的生成 164
10.1.3  多路平衡歸并 164
10.2  習(xí)題及解答 164
第11章  文件 177
11.1  文件的基本概念 177
11.1.1  基本概念 177
11.1.2  文件的存儲(chǔ)和組織 177
11.2  習(xí)題及解答 178
第二部分  實(shí)訓(xùn)指導(dǎo)
第1章  上機(jī)環(huán)境 180
1.1  Turbo C++上機(jī)環(huán)境 180
1.1.1  建立C++源程序 180
1.1.2  打開(kāi)已存在的C++源程序 180
1.1.3  編譯并運(yùn)行C++源程序 181
1.2  Visual C++上機(jī)環(huán)境 183
1.2.1  新建C++源程序并編譯和運(yùn)行 183
1.2.2  打開(kāi)已經(jīng)存在的源程序并編譯和運(yùn)行 187
1.2.3  源程序的保存 189
第2章  實(shí)訓(xùn)內(nèi)容 190
實(shí)訓(xùn)題一  線(xiàn)性表的順序存儲(chǔ) 190
實(shí)訓(xùn)題二  線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ) 194
實(shí)訓(xùn)題三  棧和隊(duì)列的應(yīng)用 203
實(shí)訓(xùn)題四  多維數(shù)組的應(yīng)用 212
實(shí)訓(xùn)題五  二叉樹(shù)的遍歷和應(yīng)用 218
實(shí)訓(xùn)題六  哈夫曼樹(shù)的建立及應(yīng)用 227
實(shí)訓(xùn)題七  圖的鄰接矩陣和遍歷 229
實(shí)訓(xùn)題八  圖的鄰接表和遍歷 232
實(shí)訓(xùn)題九  查找 235
實(shí)訓(xùn)題十  排序 239
第三部分  模擬試題及參考答案
模擬試題一 247
模擬試題二 250
模擬試題三 253
模擬試題四 255
模擬試題五 258
模擬試題六 260
模擬試題七 263
模擬試題八 265
模擬試題九 269
模擬試題十 272
模擬試題一參考答案 275
模擬試題二參考答案 277
模擬試題三參考答案 279
模擬試題四參考答案 281
模擬試題五參考答案 282
模擬試題六參考答案 283
模擬試題七參考答案 285
模擬試題八參考答案 286
模擬試題九參考答案 289
模擬試題十參考答案 291
參考文獻(xiàn) 294

1. 程序設(shè)計(jì)基礎(chǔ)實(shí)踐教程（C/C++語(yǔ)言版） [張桂芬 葛麗娜]
2. C++案例項(xiàng)目精講 [主編 楊國(guó)興]
3. 數(shù)據(jù)結(jié)構(gòu)（Python語(yǔ)言描述） [曹岳輝　劉衛(wèi)國(guó)　康松林　編著]
4. C++程序設(shè)計(jì)實(shí)踐教程（第三版） [主編 劉衛(wèi)國(guó) 曹岳輝]
5. C++程序設(shè)計(jì)（第三版） [主編 曹岳輝 劉衛(wèi)國(guó)]
6. 數(shù)據(jù)挖掘算法—基于C++及CUDA C [蒂莫西•馬斯特斯（Timothy]
7. 數(shù)據(jù)結(jié)構(gòu)——C語(yǔ)言（微課版） [主編 梁海英]
8. C++程序設(shè)計(jì)簡(jiǎn)明教程 [黃能耿 黃致遠(yuǎn) 胡麗丹]
9. Visual C++6.0程序項(xiàng)目案例教程 [朱 銘 曾強(qiáng)聰 編著]
10. 嵌入式應(yīng)用Qt_C++傳感數(shù)據(jù)采集開(kāi)發(fā)實(shí)訓(xùn)教程 [主編 劉和文 文燕 謝忠敏]
11. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）習(xí)題解答及實(shí)訓(xùn)指導(dǎo) [李根強(qiáng) 謝月娥]
12. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） [主編 李根強(qiáng) 劉浩 謝月娥]
13. 數(shù)據(jù)結(jié)構(gòu)（Java版） [主編 李云平]
14. C++程序設(shè)計(jì)簡(jiǎn)明教程（第二版） [主 編 王曉東 副主編 陳艷海 ]
15. C++ STL基礎(chǔ)案例教程 [鐘琪 著]
16. 數(shù)據(jù)結(jié)構(gòu) [主編 韓利凱 朱浩悅]
17. C++程序設(shè)計(jì)基礎(chǔ)教程 [主編 劉志寶 朱偉華 謝利民]
18. Visual C++ & Android程序設(shè)計(jì)綜合實(shí)訓(xùn)（第二版） [主編 梁建武]
19. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版） [主編 庫(kù)波 曹靜]
20. 數(shù)據(jù)結(jié)構(gòu)（Java版） [孫琳 張宇]
21. Visual C++程序設(shè)計(jì)教程（第二版） [梁建武]
22. 數(shù)據(jù)結(jié)構(gòu) [許繪香 段明義]
23. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述） [李素若 陳萬(wàn)華 游明坤 編著]
24. 數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及上機(jī)指導(dǎo) [李素若 琚輝 嚴(yán)永松 編著]
25. C++應(yīng)用程序設(shè)計(jì) [劉彥姝 謝景偉]
26. C++程序設(shè)計(jì) [陳國(guó)志 叢華 單正 編著]
27. C++面向?qū)ο蟪绦蛟O(shè)計(jì)習(xí)題解答及上機(jī)指導(dǎo) [李素若 杜華兵]
28. C++面向?qū)ο蟪绦蛟O(shè)計(jì) [李素若 杜華兵]
29. C/C++程序設(shè)計(jì)學(xué)習(xí)輔導(dǎo) [李婷 李云峰 編著]
30. C/C++程序設(shè)計(jì) [李云峰 李婷 編著]