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