本實(shí)驗(yàn)指導(dǎo)教程是配合計(jì)算機(jī)及相關(guān)專業(yè)的“數(shù)據(jù)結(jié)構(gòu)”課程而編寫(xiě)的。在內(nèi)容編排方面，按照循序漸進(jìn)、由淺入深的順序設(shè)計(jì)、選取案例。全書(shū)共分兩個(gè)部分：第一部分為“數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)”；第二部分為“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)”。
第一部分(包括第1～8章)針對(duì)每個(gè)知識(shí)點(diǎn)，首先給出明確的要求，隨后設(shè)計(jì)基礎(chǔ)實(shí)驗(yàn)，特別是前幾章在基礎(chǔ)實(shí)驗(yàn)之后，設(shè)計(jì)了若干應(yīng)用案例。這樣有利于學(xué)生明確知識(shí)點(diǎn)在應(yīng)用中如何使用，消除迷茫感、增強(qiáng)學(xué)習(xí)興趣。
第二部分(即第9章)是課程設(shè)計(jì)，介紹在一個(gè)項(xiàng)目中如何選擇和使用多種基本的數(shù)據(jù)結(jié)構(gòu)，介紹如何有效地將它們?nèi)诤显谝黄�，解決實(shí)際的復(fù)雜應(yīng)用問(wèn)題。
本書(shū)可作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程的實(shí)驗(yàn)教材。
要學(xué)好數(shù)據(jù)結(jié)構(gòu)，僅僅通過(guò)課堂教學(xué)或自學(xué)獲取理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，還必須加強(qiáng)實(shí)際動(dòng)手能力的訓(xùn)練。只有通過(guò)實(shí)驗(yàn)課調(diào)試和運(yùn)行已有的各種典型算法和已編寫(xiě)的程序，從成功和失敗的經(jīng)驗(yàn)中得到鍛煉，才能熟練掌握和運(yùn)用理論知識(shí)解決軟件開(kāi)發(fā)中的實(shí)際問(wèn)題，達(dá)到學(xué)以致用的目的。
本實(shí)驗(yàn)指導(dǎo)教程是配合計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程而編寫(xiě)的。本書(shū)在內(nèi)容編排方面，按照循序漸進(jìn)、由淺入深的順序設(shè)計(jì)、選取案例。根據(jù)教學(xué)內(nèi)容，針對(duì)學(xué)生的實(shí)際情況，本書(shū)在內(nèi)容編排上共分兩個(gè)部分。第一部分為"數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)"；第二部分為"數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)"。
第一部分(包括第1～8章)針對(duì)每個(gè)知識(shí)點(diǎn)，首先給出明確的要求，隨后設(shè)計(jì)基礎(chǔ)實(shí)驗(yàn)，特別是前幾章在基礎(chǔ)實(shí)驗(yàn)之后，設(shè)計(jì)了若干應(yīng)用案例。這樣有利于學(xué)生明確知識(shí)點(diǎn)在應(yīng)用中如何使用，消除學(xué)生的迷茫感、增強(qiáng)學(xué)生的學(xué)習(xí)興趣。
第二部分(即第9章)是課程設(shè)計(jì)，介紹在一個(gè)項(xiàng)目中如何選擇和使用多種基本數(shù)據(jù)結(jié)構(gòu)，介紹如何有效地將它們?nèi)诤显谝黄鸾鉀Q實(shí)際的復(fù)雜應(yīng)用問(wèn)題。這有利于學(xué)生更深層次地掌握數(shù)據(jù)結(jié)構(gòu)原理及其應(yīng)用范圍和過(guò)程。
本書(shū)具有以下特點(diǎn)。
(1)基于案例驅(qū)動(dòng)的教學(xué)內(nèi)容設(shè)計(jì)。在實(shí)驗(yàn)案例的選擇方面，不僅有針對(duì)知識(shí)點(diǎn)的基礎(chǔ)案例，而且有對(duì)應(yīng)的應(yīng)用案例，從而使學(xué)生能夠消除畏難情緒。我們?cè)谠搶?shí)驗(yàn)教材的編寫(xiě)過(guò)程中，選擇案例時(shí)由淺入深并精心設(shè)計(jì)了應(yīng)用案例，以確保應(yīng)用的完整性。
(2)提供大量的源代碼和開(kāi)發(fā)案例。在該實(shí)驗(yàn)教材的編寫(xiě)中，摒棄了偽代碼的描述，全部采用C語(yǔ)言源代碼，這些源代碼都是經(jīng)過(guò)調(diào)試并且在教學(xué)過(guò)程中已經(jīng)應(yīng)用的，學(xué)生可以直接分析和模仿。同時(shí)，在重要的章節(jié)，都提供了較為深入的設(shè)計(jì)案例，例如多項(xiàng)式的運(yùn)算、括號(hào)匹配判斷系統(tǒng)、迷宮求解系統(tǒng)、*短路徑求解等，為學(xué)生提供了更為深入的源碼討論和模仿的機(jī)會(huì)，極大地提高了教材的全面性、深入性和綜合性。
(3)提供典型的課程設(shè)計(jì)內(nèi)容。為了更好地提高學(xué)生的專業(yè)技能訓(xùn)練水平以及提高學(xué)生的學(xué)習(xí)興趣，在本書(shū)的編寫(xiě)過(guò)程中，編寫(xiě)成員根據(jù)自己多年教學(xué)的積累，整理出了適合計(jì)算機(jī)專業(yè)學(xué)生實(shí)際情況的課程設(shè)計(jì)題目，并提供了相應(yīng)的解決思路和源代碼，為學(xué)生提供了很好的學(xué)習(xí)機(jī)會(huì)和訓(xùn)練機(jī)會(huì)。
前 言
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專業(yè)中一門(mén)重要的專業(yè)基礎(chǔ)課程。用計(jì)算機(jī)解決實(shí)際問(wèn)題時(shí)，就要涉及數(shù)據(jù)的表示及數(shù)據(jù)的處理，而這正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象。通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)內(nèi)容的學(xué)習(xí)，可以為后續(xù)課程，尤其是軟件方面的課程打下堅(jiān)實(shí)的基礎(chǔ)，同時(shí)，也提供了必要的技能訓(xùn)練。此課程的學(xué)習(xí)質(zhì)量將直接影響計(jì)算機(jī)軟件系列課程的學(xué)習(xí)效果，因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)專業(yè)中具有舉足輕重的作用。
根據(jù)我們多年的教學(xué)經(jīng)驗(yàn)，認(rèn)為學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的主要困難在于解題。學(xué)生在解題中經(jīng)常會(huì)出現(xiàn)錯(cuò)誤，原因在于實(shí)踐能力不足。
要學(xué)好數(shù)據(jù)結(jié)構(gòu)，僅僅通過(guò)課堂教學(xué)或自學(xué)獲取理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，還必須加強(qiáng)實(shí)際動(dòng)手能力的訓(xùn)練。只有通過(guò)實(shí)驗(yàn)課調(diào)試和運(yùn)行已有的各種典型算法和已編寫(xiě)的程序，從成功和失敗的經(jīng)驗(yàn)中得到鍛煉，才能熟練掌握和運(yùn)用理論知識(shí)解決軟件開(kāi)發(fā)中的實(shí)際問(wèn)題，達(dá)到學(xué)以致用的目的。
本實(shí)驗(yàn)指導(dǎo)教程是配合計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程而編寫(xiě)的。本書(shū)在內(nèi)容編排方面，按照循序漸進(jìn)、由淺入深的順序設(shè)計(jì)、選取案例。根據(jù)教學(xué)內(nèi)容，針對(duì)學(xué)生的實(shí)際情況，本書(shū)在內(nèi)容編排上共分兩個(gè)部分。第一部分為"數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)"；第二部分為"數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)"。
第一部分(包括第1～8章)針對(duì)每個(gè)知識(shí)點(diǎn)，首先給出明確的要求，隨后設(shè)計(jì)基礎(chǔ)實(shí)驗(yàn)，特別是前幾章在基礎(chǔ)實(shí)驗(yàn)之后，設(shè)計(jì)了若干應(yīng)用案例。這樣有利于學(xué)生明確知識(shí)點(diǎn)在應(yīng)用中如何使用，消除學(xué)生的迷茫感、增強(qiáng)學(xué)生的學(xué)習(xí)興趣。
第二部分(即第9章)是課程設(shè)計(jì)，介紹在一個(gè)項(xiàng)目中如何選擇和使用多種基本數(shù)據(jù)結(jié)構(gòu)，介紹如何有效地將它們?nèi)诤显谝黄鸾鉀Q實(shí)際的復(fù)雜應(yīng)用問(wèn)題。這有利于學(xué)生更深層次地掌握數(shù)據(jù)結(jié)構(gòu)原理及其應(yīng)用范圍和過(guò)程。
本書(shū)具有以下特點(diǎn)。
(1) 基于案例驅(qū)動(dòng)的教學(xué)內(nèi)容設(shè)計(jì)。在實(shí)驗(yàn)案例的選擇方面，不僅有針對(duì)知識(shí)點(diǎn)的基礎(chǔ)案例，而且有對(duì)應(yīng)的應(yīng)用案例，從而使學(xué)生能夠消除畏難情緒。我們?cè)谠搶?shí)驗(yàn)教材的編寫(xiě)過(guò)程中，選擇案例時(shí)由淺入深并精心設(shè)計(jì)了應(yīng)用案例，以確保應(yīng)用的完整性。
(2) 提供大量的源代碼和開(kāi)發(fā)案例。在該實(shí)驗(yàn)教材的編寫(xiě)中，摒棄了偽代碼的描述，全部采用C語(yǔ)言源代碼，這些源代碼都是經(jīng)過(guò)調(diào)試并且在教學(xué)過(guò)程中已經(jīng)應(yīng)用的，學(xué)生可以直接分析和模仿。同時(shí)，在重要的章節(jié)，都提供了較為深入的設(shè)計(jì)案例，例如多項(xiàng)式的運(yùn)算、括號(hào)匹配判斷系統(tǒng)、迷宮求解系統(tǒng)、最短路徑求解等，為學(xué)生提供了更為深入的源碼討論和模仿的機(jī)會(huì)，極大地提高了教材的全面性、深入性和綜合性。
(3) 提供典型的課程設(shè)計(jì)內(nèi)容。為了更好地提高學(xué)生的專業(yè)技能訓(xùn)練水平以及提高學(xué)生的學(xué)習(xí)興趣，在本書(shū)的編寫(xiě)過(guò)程中，編寫(xiě)成員根據(jù)自己多年教學(xué)的積累，整理出了適合計(jì)算機(jī)專業(yè)學(xué)生實(shí)際情況的課程設(shè)計(jì)題目，并提供了相應(yīng)的解決思路和源代碼，為學(xué)生提供了很好的學(xué)習(xí)機(jī)會(huì)和訓(xùn)練機(jī)會(huì)。
本書(shū)提供案例程序的源代碼(可運(yùn)行)，并贈(zèng)送C++版案例實(shí)驗(yàn)教程。讀者可以從清華大學(xué)出版社的網(wǎng)站下載。
本書(shū)可作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程的實(shí)驗(yàn)教材。
由于編者水平有限，錯(cuò)誤和不當(dāng)之處在所難免，希望讀者批評(píng)指正。
編 者
第1章 順序表 1
實(shí)驗(yàn)1 順序表的實(shí)現(xiàn) 2
1．實(shí)驗(yàn)?zāi)康?2
2．實(shí)驗(yàn)內(nèi)容 2
3．算法設(shè)計(jì) 2
4．程序?qū)崿F(xiàn) 3
5．運(yùn)行程序 5
實(shí)驗(yàn)2 順序表的應(yīng)用--集合運(yùn)算 5
1．實(shí)驗(yàn)?zāi)康?5
2．實(shí)驗(yàn)內(nèi)容 5
3．算法設(shè)計(jì) 5
4．程序?qū)崿F(xiàn) 6
5．運(yùn)行程序 8
實(shí)驗(yàn)3 順序表的應(yīng)用--回文數(shù)猜想 8
1．問(wèn)題描述 8
2．基本要求 8
3．算法設(shè)計(jì) 8
4．程序?qū)崿F(xiàn) 9
5．運(yùn)行程序 10
第2章 鏈表 11
實(shí)驗(yàn)1 單鏈表的實(shí)現(xiàn) 12
1．實(shí)驗(yàn)?zāi)康?12
2．實(shí)驗(yàn)內(nèi)容 12
3．算法設(shè)計(jì) 12
4．程序?qū)崿F(xiàn) 13
5．運(yùn)行程序 15
實(shí)驗(yàn)2 單鏈表的應(yīng)用--約瑟夫問(wèn)題 16
1．問(wèn)題描述 16
2．基本要求 16
3．算法設(shè)計(jì) 16
4．程序?qū)崿F(xiàn) 16
5．運(yùn)行程序 17
實(shí)驗(yàn)3 單鏈表的應(yīng)用--多項(xiàng)式求和 18
1．問(wèn)題描述 18
2．基本要求 18
3．算法設(shè)計(jì) 18
4．實(shí)現(xiàn)程序 18
5．運(yùn)行程序 21
第3章 棧 23
實(shí)驗(yàn)1 順序棧的實(shí)現(xiàn) 24
1．實(shí)驗(yàn)?zāi)康?24
2．實(shí)驗(yàn)內(nèi)容 24
3．算法設(shè)計(jì) 24
4．程序?qū)崿F(xiàn) 25
5．運(yùn)行程序 26
實(shí)驗(yàn)2 鏈棧的實(shí)現(xiàn) 26
1．實(shí)驗(yàn)?zāi)康?26
2．實(shí)驗(yàn)內(nèi)容 26
3．算法設(shè)計(jì) 27
4．程序?qū)崿F(xiàn) 27
5．程序運(yùn)行 28
實(shí)驗(yàn)3 棧的應(yīng)用--數(shù)制轉(zhuǎn)換 28
1．問(wèn)題描述 28
2．基本要求 28
3．算法設(shè)計(jì) 29
4．程序?qū)崿F(xiàn) 29
5．運(yùn)行程序 30
實(shí)驗(yàn)4 棧的應(yīng)用--括號(hào)匹配問(wèn)題 30
1．問(wèn)題描述 30
2．基本要求 30
3．算法設(shè)計(jì) 30
4．程序?qū)崿F(xiàn) 30
5．運(yùn)行程序 31
實(shí)驗(yàn)5 棧的應(yīng)用--表達(dá)式求值 32
1．問(wèn)題描述 32
2．基本要求 32
3．算法設(shè)計(jì) 32
4．程序?qū)崿F(xiàn) 32
5．運(yùn)行程序 34
第4章 隊(duì)列 35
實(shí)驗(yàn)1 循環(huán)隊(duì)列的實(shí)現(xiàn) 36
1．實(shí)驗(yàn)?zāi)康?36
2．實(shí)驗(yàn)內(nèi)容 36
3．算法設(shè)計(jì) 36
4．程序?qū)崿F(xiàn) 37
5．運(yùn)行程序 38
實(shí)驗(yàn)2 鏈隊(duì)列的實(shí)現(xiàn) 39
1．實(shí)驗(yàn)?zāi)康?39
2．實(shí)驗(yàn)內(nèi)容 39
3．算法設(shè)計(jì) 39
4．程序?qū)崿F(xiàn) 39
5．運(yùn)行程序 41
實(shí)驗(yàn)3 隊(duì)列的應(yīng)用--優(yōu)先隊(duì)列 41
1．問(wèn)題描述 41
2．基本要求 41
3．算法設(shè)計(jì) 41
4．實(shí)現(xiàn)程序 42
5．運(yùn)行程序 44
實(shí)驗(yàn)4 隊(duì)列的應(yīng)用--雙端隊(duì)列 45
1．問(wèn)題描述 45
2．基本要求 45
3．算法設(shè)計(jì) 45
4．程序?qū)崿F(xiàn) 45
5．運(yùn)行程序 48
第5章 二叉樹(shù) 49
實(shí)驗(yàn)1 二叉樹(shù)的建立 50
1．實(shí)驗(yàn)?zāi)康?50
2．實(shí)驗(yàn)內(nèi)容 50
3．算法設(shè)計(jì) 50
4．程序?qū)崿F(xiàn) 51
5．運(yùn)行程序 51
實(shí)驗(yàn)2 二叉樹(shù)的遍歷 52
1．實(shí)驗(yàn)?zāi)康?52
2．實(shí)驗(yàn)內(nèi)容 52
3．算法設(shè)計(jì) 52
4．程序?qū)崿F(xiàn) 53
5．運(yùn)行程序 55
實(shí)驗(yàn)3 二叉樹(shù)的高度、節(jié)點(diǎn)數(shù)、葉子
節(jié)點(diǎn)數(shù) 55
1．實(shí)驗(yàn)?zāi)康?55
2．實(shí)驗(yàn)內(nèi)容 55
3．算法設(shè)計(jì) 55
4．程序?qū)崿F(xiàn) 55
5．運(yùn)行程序 57
實(shí)驗(yàn)4 堆 57
1．問(wèn)題描述 57
2．基本要求 57
3．算法設(shè)計(jì) 57
4．程序?qū)崿F(xiàn) 58
5．運(yùn)行程序 60
第6章 圖 61
實(shí)驗(yàn)1 圖的鄰接矩陣表示 62
1．實(shí)驗(yàn)?zāi)康?62
2．實(shí)驗(yàn)內(nèi)容 62
3．實(shí)現(xiàn)提示 62
4．程序?qū)崿F(xiàn) 62
5．運(yùn)行程序 64
實(shí)驗(yàn)2 圖的鄰接表表示 64
1．實(shí)驗(yàn)?zāi)康?64
2．實(shí)驗(yàn)內(nèi)容 64
3．實(shí)現(xiàn)提示 64
4．程序?qū)崿F(xiàn) 64
5．運(yùn)行程序 66
實(shí)驗(yàn)3 圖的深度優(yōu)先搜索 67
1．問(wèn)題描述 67
2．基本要求 67
3．實(shí)現(xiàn)提示 67
4．程序?qū)崿F(xiàn) 67
5．運(yùn)行程序 69
第7章 排序 71
實(shí)驗(yàn)1 冒泡排序 72
1．實(shí)驗(yàn)?zāi)康?72
2. 實(shí)驗(yàn)內(nèi)容 72
3．實(shí)現(xiàn)提示 72
4．程序?qū)崿F(xiàn) 73
5．運(yùn)行程序 74
實(shí)驗(yàn)2 插入排序、選擇排序 74
1．實(shí)驗(yàn)?zāi)康?74
2．實(shí)驗(yàn)內(nèi)容 74
3．實(shí)現(xiàn)提示 75
4．程序?qū)崿F(xiàn) 75
5．運(yùn)行程序 76
實(shí)驗(yàn)3 歸并排序 76
1．實(shí)驗(yàn)?zāi)康?76
2．實(shí)驗(yàn)內(nèi)容 76
3．實(shí)現(xiàn)提示 76
4．實(shí)現(xiàn)程序 76
5．運(yùn)行程序 78
實(shí)驗(yàn)4 快速排序 78
1．實(shí)驗(yàn)?zāi)康?78
2．實(shí)驗(yàn)內(nèi)容 79
3．實(shí)現(xiàn)提示 79
4．程序?qū)崿F(xiàn) 79
5．運(yùn)行程序 80
實(shí)驗(yàn)5 堆排序 81
1．實(shí)驗(yàn)?zāi)康?81
2．實(shí)驗(yàn)內(nèi)容 81
3．實(shí)現(xiàn)提示 81
4．程序?qū)崿F(xiàn) 81
5．運(yùn)行程序 82
第8章 查找 83
實(shí)驗(yàn)1 折半查找 84
1．實(shí)驗(yàn)?zāi)康?84
2．實(shí)驗(yàn)內(nèi)容 84
3．實(shí)現(xiàn)提示 84
4．程序?qū)崿F(xiàn) 85
5．運(yùn)行程序 86
實(shí)驗(yàn)2 二叉排序樹(shù)查找 87
1．實(shí)驗(yàn)?zāi)康?87
2．實(shí)驗(yàn)內(nèi)容 87
3．實(shí)現(xiàn)提示 87
4．程序?qū)崿F(xiàn) 87
5．運(yùn)行程序 89
實(shí)驗(yàn)3 哈希查找 89
1．實(shí)驗(yàn)?zāi)康?89
2．實(shí)驗(yàn)內(nèi)容 89
3．實(shí)現(xiàn)提示 90
4．程序?qū)崿F(xiàn) 90
5．運(yùn)行程序 91
第9章 課程設(shè)計(jì) 93
問(wèn)題1 學(xué)生成績(jī)管理 94
1．問(wèn)題描述 94
2．任務(wù)要求 94
3．程序?qū)崿F(xiàn) 95
4．運(yùn)行結(jié)果 98
問(wèn)題2 數(shù)據(jù)庫(kù)管理系統(tǒng) 98
1．問(wèn)題描述 98
2．任務(wù)要求 98
3．分析與實(shí)現(xiàn) 99
4．程序?qū)崿F(xiàn) 101
5．運(yùn)行結(jié)果 116
問(wèn)題3 馬踏棋盤(pán) 117
1．問(wèn)題描述 117
2．任務(wù)要求 117
3．分析與實(shí)現(xiàn) 117
4．運(yùn)行結(jié)果 120
問(wèn)題4 停車(chē)場(chǎng)管理 121
1．問(wèn)題描述 121
2．任務(wù)要求 121
3．分析與實(shí)現(xiàn) 122
4．運(yùn)行結(jié)果 126
問(wèn)題5 大整數(shù)計(jì)算器 126
1．問(wèn)題描述 126
2. 任務(wù)要求 127
3．分析與實(shí)現(xiàn) 127
4．運(yùn)行結(jié)果 132
問(wèn)題6 魔方陣 132
1．問(wèn)題描述 132
2．任務(wù)要求 133
3．分析與實(shí)現(xiàn) 133
4．運(yùn)行結(jié)果 134
問(wèn)題7 本科生導(dǎo)師制問(wèn)題 134
1．問(wèn)題描述 134
2．任務(wù)要求 135
3．分析與實(shí)現(xiàn) 135
4．運(yùn)行結(jié)果 144
問(wèn)題8 電文的編碼和譯碼 145
1．問(wèn)題描述 145
2．任務(wù)要求 145
3．分析與實(shí)現(xiàn) 145
4．運(yùn)行結(jié)果 148
問(wèn)題9 家族關(guān)系查詢系統(tǒng) 149
1．問(wèn)題描述 149
2．任務(wù)要求 149
3．分析與實(shí)現(xiàn) 149
4．運(yùn)行結(jié)果 161
問(wèn)題10 地鐵建設(shè)問(wèn)題 162
1．問(wèn)題描述 162
2．任務(wù)要求 162
3．分析與實(shí)現(xiàn) 162
4．運(yùn)行結(jié)果 165
問(wèn)題11 校園導(dǎo)航 165
1．問(wèn)題描述 165
2．任務(wù)要求 165
3．分析與實(shí)現(xiàn) 166
4．運(yùn)行結(jié)果 169
參考文獻(xiàn) 170
第1章 順 序 表
本章要點(diǎn)
(1) 順序表的概念。
(2) 順序表的存儲(chǔ)。
(3) 順序表各種操作的實(shí)現(xiàn)。
學(xué)習(xí)目標(biāo)
(1) 理解順序表和線性表的區(qū)別和聯(lián)系。
(2) 掌握順序存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類(lèi)型定義方法。
(3) 掌握順序存儲(chǔ)結(jié)構(gòu)各種操作的實(shí)現(xiàn)。
(4) 掌握如何使用順序表來(lái)解決相關(guān)的應(yīng)用問(wèn)題。
基本知識(shí)點(diǎn)
順序表是指線性表的順序存儲(chǔ)結(jié)構(gòu)，順序表用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素。順序存儲(chǔ)使用簡(jiǎn)便、無(wú)須為表示表中元素間的邏輯關(guān)系而額外增加存儲(chǔ)空間，并且可以實(shí)現(xiàn)隨機(jī)存取。
實(shí)驗(yàn)1 順序表的實(shí)現(xiàn)
1．實(shí)驗(yàn)?zāi)康?br />
(1) 掌握順序表的存儲(chǔ)結(jié)構(gòu)。
(2) 驗(yàn)證順序表及其基本操作的實(shí)現(xiàn)。
(3) 理解算法與程序的關(guān)系，能夠?qū)㈨樞虮硭惴ㄞD(zhuǎn)換為對(duì)應(yīng)的程序。
2．實(shí)驗(yàn)內(nèi)容
(1) 初始化順序表。
(2) 在順序表的第i位插入元素。
(3) 刪除順序表的第i個(gè)元素。
(4) 輸出順序表。
(5) 判斷順序表是否為空。
(6) 判斷順序表是否滿。
(7) 求順序表第i個(gè)元素的值。
(8) 查找值為x的元素。
3．算法設(shè)計(jì)
用結(jié)構(gòu)體來(lái)描述順序表，結(jié)構(gòu)體中包括表的大小、存放數(shù)據(jù)的數(shù)組、表的最大容量三個(gè)數(shù)據(jù)屬性。
為簡(jiǎn)單起見(jiàn)，本實(shí)驗(yàn)假定線性表的數(shù)據(jù)元素為int型。
結(jié)構(gòu)體的定義如下：
typedef int dataType;
typedef struct {
dataType *data;
int size;
int maxSize;
} SqList;
應(yīng)實(shí)現(xiàn)順序表的初始化、插入、刪除、判空、判滿、求值、查找、輸出等操作。
(1) void InitList(SqList *l)：初始化順序表。
(2) void Insert(SqList *l, int k, dataType x)：在順序表l的第k個(gè)位置插入元素x。
(3) void Delete(SqList *l, int k)：刪除順序表l的第k個(gè)元素。
(4) int Empty(SqList *l)：判斷順序表是否為空。
(5) int Full(SqList *l)：判斷順序表是否滿。
(6) dataType GetData(SqList *l, int i)：求順序表l中第i個(gè)元素的值。
(7) int locate(SqList *l, dataType x)：在順序表l中查找值為x的元素。
(8) void Print(SqList *l)：輸出順序表。
4．程序?qū)崿F(xiàn)
程序完整的實(shí)現(xiàn)代碼如下：
#include
#include
#define INIT_SIZE 100
typedef int dataType;
typedef struct {
dataType *data;
int size;
int maxSize;
} SqList;
//初始化順序表
void InitList(SqList *l) {
l->data = (dataType*)malloc(INIT_SIZE * sizeof(dataType));
l->size = 0;
l->maxSize = INIT_SIZE;
}
//在順序表l的第k個(gè)位置插入元素x
void Insert(SqList *l, int k, dataType x) {
if (k<1 || k>l->size+1) exit(1);
if (l->size == l->maxSize) exit(1);
for (int i=l->size; i>=k; i--)
l->data[i] = l->data[i-1];
l->data[k-1] = x;
l->size++;
}
//刪除順序表l的第k個(gè)元素
void Delete(SqList *l, int k) {
if (k<1 || k>l->size) exit(1);
for (int i=k; isize; i++)
l->data[i-1] = l->data[i];
l->size--;
}
//判斷順序表是否為空
int Empty(SqList *l) {
return l->size == 0;
}
//判斷順序表是否滿
int Full(SqList *l) {
return l->size == l->maxSize;
}
//求順序表l中第i個(gè)元素的值
dataType GetData(SqList *l, int i) {
if (i<1 || i>l->size) exit(1);
return l->data[i-1];
}
//在順序表l中查找值為x的元素
int locate(SqList *l, dataType x) {
for (int i=0; isize; i++)
if (l->data[i] == x)
return i + 1;
return 0;
}
//輸出順序表
void Print(SqList *l) {
for (int i=0; isize; i++)
printf("%d ", l->data[i]);
printf("\n");
}
int main() {
SqList list, *pList=&list;
InitList(pList);
Insert(pList, 1, 10);
Insert(pList, 1, 20);
Delete(pList, 2);
Insert(pList, 1, 30);
Insert(pList, 1, 40);
Print(pList);
printf("%d", GetData(pList, 2));
}
書(shū)單推薦
