數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全集

數(shù)據(jù)結(jié)構(gòu)

實(shí)踐教程

前言

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的必修。主干課程之一，它旨在使讀者學(xué)會(huì)分析研究數(shù)據(jù)對(duì)象的特

性，學(xué)會(huì)數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及相應(yīng)的運(yùn)算（操

作），把現(xiàn)實(shí)世界中的問(wèn)題轉(zhuǎn)化為計(jì)算機(jī)內(nèi)部的表示和處理，這是一個(gè)良好的程序設(shè)計(jì)技能訓(xùn)練

的過(guò)程.在整個(gè)教學(xué)或?qū)W習(xí)過(guò)程中，解題能力和技巧的訓(xùn)練是一個(gè)重要的環(huán)節(jié)。為了幫助教師

講授“數(shù)據(jù)結(jié)構(gòu)”，滿足指導(dǎo)和評(píng)價(jià)''課程設(shè)計(jì)”的需要，為了幫助和指導(dǎo)讀者更好地學(xué)習(xí)數(shù)據(jù)

結(jié)構(gòu)這門課程，我們特編寫了這本《數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程》輔助教材，旨在彌補(bǔ)課堂教學(xué)和實(shí)驗(yàn)中的

不足，顰助學(xué)生充分理解和鞏固所學(xué)的基本概念、原理和方法，達(dá)到融會(huì)貫通、舉一反三的目的。

實(shí)踐證明，理解課程內(nèi)容與較好地解決實(shí)際問(wèn)題之間存在著明顯差距，而算法設(shè)計(jì)完成

的質(zhì)量與基本的程序設(shè)計(jì)素質(zhì)的培養(yǎng)是密切相關(guān)的。要想理解和鞏固所學(xué)的基本概念。原理和

方法，牢固地掌握所學(xué)的基本知識(shí)?；炯寄?，達(dá)到融會(huì)貫通。舉一反三的目的，就必須多

做。多練。多見(jiàn)（見(jiàn)多識(shí)廣）。正是為了達(dá)到上述目的，書中用一些實(shí)際的應(yīng)用，對(duì)一些

重要的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行解讀。經(jīng)過(guò)循序漸進(jìn)地訓(xùn)練，就可以使讀者掌握更多的程序設(shè)計(jì)技巧

和方法，提高分析。解決問(wèn)題的能力。

本書根據(jù)學(xué)生的基礎(chǔ)知識(shí)和興趣愛(ài)好將內(nèi)容分為基礎(chǔ)篇和提高篇兩個(gè)部分。第一部分基礎(chǔ)篇精

選出適當(dāng)?shù)摹⑴c實(shí)際生活結(jié)合密切的課程設(shè)計(jì)實(shí)例加以分析實(shí)現(xiàn)。第二部分提高篇旨在使讀者通過(guò)

運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)及復(fù)雜算法去解決現(xiàn)實(shí)世界中的一些實(shí)際問(wèn)題。

本書依據(jù)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱要求，同時(shí)又獨(dú)立于具體的教科書，既重視實(shí)踐應(yīng)用，又重視

理論分析，本書的主要特點(diǎn)有：

?本書精選出來(lái)的實(shí)例項(xiàng)目經(jīng)典、實(shí)用、具有一定的趣味性，其內(nèi)容豐富、涉及面廣、難易適

當(dāng)，能給讀者以啟發(fā)，達(dá)到讓讀者掌握相關(guān)知識(shí)和開(kāi)闊視野的目的

?為了提高學(xué)生分析問(wèn)題、解決問(wèn)題的能力，本書對(duì)實(shí)例項(xiàng)目進(jìn)行分析，其設(shè)計(jì)思路清晰流暢，

值得參考.

?本書不僅僅是對(duì)照數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱舉些例子說(shuō)明數(shù)據(jù)結(jié)構(gòu)能解決什么問(wèn)題，而是通

過(guò)分析具體的實(shí)例項(xiàng)目，得到對(duì)數(shù)據(jù)組織關(guān)系的需求，從而選擇某個(gè)數(shù)據(jù)結(jié)構(gòu)適應(yīng)一些特定的問(wèn)題和

算法，并說(shuō)明使用這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn).

?所有實(shí)例項(xiàng)目都給出了參考算法和源程序代碼并在TurboC和VisualC++6.0環(huán)境下運(yùn)

行通過(guò)。

由于作者水平有限、時(shí)間倉(cāng)促，本書難免存在一些缺點(diǎn)和錯(cuò)誤，懇請(qǐng)廣大讀者及同行們批評(píng)指正。

目錄

第一部分基礎(chǔ)篇

第一章線性表

1.1學(xué)生成績(jī)管理

1.1.1項(xiàng)目簡(jiǎn)介

1.1.2設(shè)計(jì)思路

1.1.3數(shù)據(jù)結(jié)構(gòu)

1.1.4程序清單

1.1.5運(yùn)行結(jié)果

1.2考試報(bào)名管理

1.2.1項(xiàng)目簡(jiǎn)介

1.2.2設(shè)計(jì)思路

1.2.3數(shù)據(jù)結(jié)構(gòu)

1.2.4程序清單

1.2.5運(yùn)行結(jié)果

1.3約瑟夫生者死者游戲

1.3.1項(xiàng)目簡(jiǎn)介

1.3.2設(shè)計(jì)思路

1.3.3數(shù)據(jù)結(jié)構(gòu)

1.3.4程序清單

1.3.5運(yùn)行結(jié)果

1.4約瑟夫雙向生死游戲

1.4.1項(xiàng)目簡(jiǎn)介

1.4.2設(shè)計(jì)思路

1.4.3數(shù)據(jù)結(jié)構(gòu)

1.4.4程序清單

1.4.5運(yùn)行結(jié)果

第二章棧和隊(duì)列

2.1迷宮旅行游戲

2.1.1項(xiàng)目簡(jiǎn)介

2.1.2知識(shí)要點(diǎn)

2?1.3設(shè)計(jì)思路

2.1?4程序清單

2?1.5運(yùn)行結(jié)果

2.2八皇后問(wèn)題

2。1.1項(xiàng)目簡(jiǎn)介

2?1.2知識(shí)要點(diǎn)

201.3設(shè)計(jì)思路

2.1o4程序清單

2.1?5運(yùn)行結(jié)果

2。3停車場(chǎng)的停車管理

2,1.1項(xiàng)目簡(jiǎn)介

2o1.2知識(shí)要點(diǎn)

2.1.3設(shè)計(jì)思路

2o1.4程序清單

2。1。5運(yùn)行結(jié)果

第三章串、數(shù)組和廣義表

3.1單詞檢索統(tǒng)計(jì)程序

3.1.1項(xiàng)目簡(jiǎn)介

3。1,2設(shè)計(jì)思路

3.1o3數(shù)據(jù)結(jié)構(gòu)

3.1.4程序清單

3.1?5運(yùn)行結(jié)果

3。2Internet網(wǎng)絡(luò)通路管理

3.2.1項(xiàng)目簡(jiǎn)介

3.2?2設(shè)計(jì)思路

3.2.3數(shù)據(jù)結(jié)構(gòu)

3?2.4程序清單

3?2.5運(yùn)行結(jié)果

第四章樹(shù)和二叉樹(shù)

4.1家譜管理

4.1.1項(xiàng)目簡(jiǎn)介

4.1.2設(shè)計(jì)思路

4.1.3數(shù)據(jù)結(jié)構(gòu)

4.1.4程序清單

4?1.5運(yùn)行結(jié)果

4.2表達(dá)式求值問(wèn)題

4,2.1項(xiàng)目簡(jiǎn)介

4.2?2設(shè)計(jì)思路

4.2,3數(shù)據(jù)結(jié)構(gòu)

4。2o4程序清單

4?2.5運(yùn)行結(jié)果

4.4圖像壓縮編碼優(yōu)化

4.4?1項(xiàng)目簡(jiǎn)介

4.4.2設(shè)計(jì)思路

4.4。3數(shù)據(jù)結(jié)構(gòu)

4。4。4程序清單

4o4.5運(yùn)行結(jié)果

第五章圖

5.1公交路線管理

5.1.1項(xiàng)目簡(jiǎn)介

5?1.2設(shè)計(jì)思路

5.1?3數(shù)據(jù)結(jié)構(gòu)

5.1.4程序清單

5?1.5運(yùn)行結(jié)果

5。2導(dǎo)航最短路徑查詢

5.2.1項(xiàng)目簡(jiǎn)介

5.2?2設(shè)計(jì)思路

5,2.3數(shù)據(jù)結(jié)構(gòu)

5.12.4程序清單

5.2.5運(yùn)行結(jié)果

5。4電網(wǎng)建設(shè)造價(jià)計(jì)算

5.4,1項(xiàng)目簡(jiǎn)介

5。4?2設(shè)計(jì)思路

5.4。3數(shù)據(jù)結(jié)構(gòu)

5?4。4程序清單

5.4.5運(yùn)行結(jié)果

5.4軟件工程進(jìn)度規(guī)劃

5.4.1項(xiàng)目簡(jiǎn)介

5.4.2設(shè)計(jì)思路

5?4.3數(shù)據(jù)結(jié)構(gòu)

5.4。4程序清單

5o4.5運(yùn)行結(jié)果

第六章查找

6.1電話號(hào)碼查詢系統(tǒng)

6o1.1項(xiàng)目簡(jiǎn)介

6.1o2知識(shí)要點(diǎn)

6o1.3設(shè)計(jì)思路

6o1.4程序清單

6?1.5運(yùn)行結(jié)果

6.2高校錄取分?jǐn)?shù)線查詢系統(tǒng)

6。2.1項(xiàng)目簡(jiǎn)介

5.2.2知識(shí)要點(diǎn)

6.2.3設(shè)計(jì)思路

6?2.4程序清單

6.2.5運(yùn)行結(jié)果

6?3儲(chǔ)蓄賬戶查詢系統(tǒng)

6?3?1項(xiàng)目簡(jiǎn)介

6。3.2知識(shí)要點(diǎn)

6。3.3設(shè)計(jì)思路

6.3.4程序清單

6.3?5運(yùn)行結(jié)果

6.3期刊稿件查詢系統(tǒng)

6.3.1項(xiàng)目簡(jiǎn)介

6.3o2知識(shí)要點(diǎn)

6.3.3設(shè)計(jì)思路

6.3.4程序清單

6?3.5運(yùn)行結(jié)果

第七章排序

7.1設(shè)備清單排序

7.1.1項(xiàng)目簡(jiǎn)介

7o1o2知識(shí)要點(diǎn)

7.1.3設(shè)計(jì)思路

7.1.4程序清單

7.1?5運(yùn)行結(jié)果

7。2地名排序

7.2。1項(xiàng)目簡(jiǎn)介

7.2.2知識(shí)要點(diǎn)

7。2.3設(shè)計(jì)思路

7?2.4程序清單

7.2.5運(yùn)行結(jié)果

7.3工廠產(chǎn)量排序

7.3?1項(xiàng)目簡(jiǎn)介

7.3o2知識(shí)要點(diǎn)

7。3。3設(shè)計(jì)思路

7.3.4程序清單

7。3.5運(yùn)行結(jié)果

7。4高?？蒲谐晒判?/p>

7.4,1項(xiàng)目簡(jiǎn)介

7.4.2知識(shí)要點(diǎn)

7.4.3設(shè)計(jì)思路

7.404程序清單

7.4。5運(yùn)行結(jié)果

7.5火車車次排序

7。5。1項(xiàng)目簡(jiǎn)介

7.5.2知識(shí)要點(diǎn)

7.5.3設(shè)計(jì)思路

7?5.4程序清單

7.5o5運(yùn)行結(jié)果

7.6IP地址排序

7?6.1項(xiàng)目簡(jiǎn)介

7.6.2知識(shí)要點(diǎn)

7O6.3設(shè)計(jì)思路

7.6o4程序清單

7.6.5運(yùn)行結(jié)果

第二部分綜合篇

8.1益智游戲之七巧板

8.1.1項(xiàng)目需求

8.1o2知識(shí)要點(diǎn)

8.1.3設(shè)計(jì)流程

8o1.4程序清單

8.1.5運(yùn)行測(cè)試

8?2航空客運(yùn)定票系統(tǒng)

8.2.1項(xiàng)目需求

8o202知識(shí)要點(diǎn)

8o2.3設(shè)計(jì)流程

8.2?4程序清單

8.2.5運(yùn)行測(cè)試

8?4景區(qū)旅游信息管理系統(tǒng)

8。4o1項(xiàng)目需求

8.202知識(shí)要點(diǎn)

8.4,2設(shè)計(jì)流程

8.4。4程序清單

8.4o5運(yùn)行測(cè)試

第一部分基礎(chǔ)篇

第一章線性表

線性表是數(shù)據(jù)結(jié)構(gòu)中最簡(jiǎn)單、最常用的一種線性結(jié)構(gòu)，也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)全部?jī)?nèi)容的基

礎(chǔ)，其掌握的好壞直接影響著后繼知識(shí)的學(xué)習(xí)。本章通過(guò)四個(gè)模擬項(xiàng)目來(lái)學(xué)習(xí)線性表的順序和

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，首先通過(guò)使用有關(guān)數(shù)組的操作實(shí)現(xiàn)學(xué)生成績(jī)管理，其次通過(guò)使用有關(guān)線性鏈

表的操作實(shí)現(xiàn)考試報(bào)名管理，然后通過(guò)使用循環(huán)鏈表的操作實(shí)現(xiàn)約瑟夫生者死者游戲。

1.1學(xué)生成績(jī)管理

1o1o1項(xiàng)目簡(jiǎn)介

學(xué)生成績(jī)管理是學(xué)校教務(wù)部門日常工作的重要組成部分，其處理信息量很大.本項(xiàng)目是對(duì)

學(xué)生成績(jī)管理的簡(jiǎn)單模擬，用菜單選擇方式完成下列功能：輸入學(xué)生數(shù)據(jù)；輸出學(xué)生數(shù)據(jù)；

學(xué)生數(shù)據(jù)查詢；添加學(xué)生數(shù)據(jù)；修改學(xué)生數(shù)據(jù)；刪除學(xué)生數(shù)據(jù)。

1o1.2設(shè)計(jì)思路

本項(xiàng)目的實(shí)質(zhì)是完成對(duì)學(xué)生成績(jī)信息的建立、查找、插入、修改、刪除等功能，可以首

先定義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來(lái)完成對(duì)數(shù)據(jù)的操作，最后完成主函數(shù)

以臉證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。

1.1.3數(shù)據(jù)結(jié)構(gòu)

本項(xiàng)目的數(shù)據(jù)是一組學(xué)生的成績(jī)信息，每條學(xué)生的成績(jī)信息由學(xué)號(hào)、姓名和成績(jī)組成，

這組學(xué)生的成績(jī)信息具有相同特性，屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由

此可以看出，這些數(shù)據(jù)具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)采用線性表來(lái)存儲(chǔ)。

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，是指用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元

素。在順序存儲(chǔ)結(jié)構(gòu)下，邏輯關(guān)系相鄰的兩個(gè)元素在物理位置上也相鄰，這是順序表的特點(diǎn)。

本項(xiàng)目可以采用順序表的線性表順序存儲(chǔ)結(jié)構(gòu)。

若一個(gè)數(shù)據(jù)元素僅占一個(gè)存儲(chǔ)單元，則其存儲(chǔ)方式參見(jiàn)圖1-1?

從圖1—1中可見(jiàn)，第i個(gè)數(shù)據(jù)元素的地址為

Loc(ai)=loc(a1)+(i-1)

假設(shè)線性表中每個(gè)元素占用k個(gè)存儲(chǔ)單元，那么在順序表中，線性表的第i個(gè)元素的存儲(chǔ)

位置與第1個(gè)元素的存儲(chǔ)位置的關(guān)系是

Loc(ai)=loc(a1)+(i—1)*k

這里L(fēng)oc(ai)是第i個(gè)元素的存儲(chǔ)位置，loc(a1)是第1個(gè)元素的存儲(chǔ)位置，也稱為

線性表的基址.顯然，順序表便于進(jìn)行隨機(jī)訪問(wèn)，故線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存儲(chǔ)結(jié)

構(gòu)。

順序表適宜于做查找這樣的靜態(tài)操作；順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率高.

缺點(diǎn)是插入或刪除元素時(shí)不方便.

由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存儲(chǔ)的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，

可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)的優(yōu)點(diǎn)是可以隨

機(jī)存取表中任一元素0(1),存儲(chǔ)空間使用緊湊：缺點(diǎn)是在插入，刪除某一元素時(shí)，需要移

動(dòng)大量元素0(n),預(yù)先分配空間需按最大空間分配，利用不充分，表容量難以擴(kuò)充.

用結(jié)構(gòu)體類型定義每個(gè)學(xué)生數(shù)據(jù)，故該數(shù)組中的每個(gè)數(shù)據(jù)的結(jié)構(gòu)可描述為：

typedefstructSTU

{。charstuno[10];//學(xué)號(hào)

?charname[10];//姓名

fIoatscore;??〃成績(jī)

}ElemType;

1.1.4程序清單

#include(iostream.h>

#incIude〈iomanipoh〉

#incIude<maIIoc.h>

#incIude<stringoh>

#defineMaxListSize20

#defineEQUAL1

typedefstructSTU{

charstuno[10];

charname[10]；

fIoatscore;

jElemType;

classList

{private:

//線性表的數(shù)組表示

EIemTypeelem[MaxListSize];

intIength;

intMaxSize；

pubIic:

//輸入學(xué)生數(shù)據(jù)

voidinit(List**L,intms);

//刪除所有學(xué)生數(shù)據(jù)

voidDestroyList(List&L){free(&L);}

//將順序表置為空表

voidCiearList0{length=0;}

//判斷順序表是否為空表

boolListEmpty0

{returnIength=0；}

〃判斷順序表是否為滿

boolListFuII()

{returnlength=MaxSize;)

//刪除某個(gè)學(xué)生數(shù)據(jù)

boolListDeIete(int,EIemType&e);

//遍歷順序表

voidListTraverse();

〃返回順序表的長(zhǎng)度

intListLength()；

//學(xué)生數(shù)據(jù)查詢

voidGetEIem(int,EIemType*);

〃修改學(xué)生數(shù)據(jù)

booIUpdateList(EIemType&e,EIemType);

//添加學(xué)生數(shù)據(jù)

booIListInsert(int,ElemType&);

//對(duì)學(xué)生數(shù)據(jù)按升序或降序輸出

voidprintIist(int);

);

voidList::init(List**L,intms)

{*1■二(List*)malloc(sizeof(List));

(*L)—〉Iength=0;

(*L)->MaxSize=ms;

)

intList::ListLength()

{returnIength;}

booIList::ListDelete(intmark,EIemType&e)

{inti,j;

if(ListEmpty0)returnfaIse;

if(mark>0){//刪除表頭元素

e=eIem[0];

for(i=1；i<length；i++)

elem[i—1]=elem[i];}

else//刪除表尾元素

if(mark(0)e=eIem[Iength-1];

else{//刪除值為e的元素

for(i=O;i<Iength;i++)

if(strcmp(eIem[i].name,e.name)==0)break；

if(i>=length)returnfalse;

elsee=eIem[i]；

for(j=i+1;j<length;j++)

elem[j—1]=elem[j];}

Iength—;

returntrue;

}

voidList::ListTraverse()

{for(inti=0;i<Iength;i++)

{cout<<setw(8)(<elem[i]?name；

cout<<setw(10)<<eIem[i].stuno;

cout<<setw(9)<<eIemEi]oage;

cout<<setw(8)<<elem[i].score<〈endI；)

)

voidList::GetEIem(inti,EIemType*e)

{*e=elem[i];}

booIList:：EquaIList(EIemTypeElemType*e2)

{if(strcmp(e1->name,e2->name))

returnfalse：

if(strcmp(e1->stuno,e2—>stuno))

returnfalse;

if(e1—>age!=e2—>age)

returnfalse;

if(e1—>score!=e2-)score)

returnfalse;

returntrue;

}

booIList::Less_EqualList(ElemType*e1,ElemType*e2)

{if(strcmp(e1—>name,e2—)name)<=0)returntrue;

eIsereturnfaIse;

)

booIList:：LocateEIem(ElemTypee,inttype)

{inti;

switch(type)

{caseEQUAL:

for(i=0：i(Iength;i++)

if(EquaIList(&eIem[i],&e))

?>returntrue;

obreak；

defauIt:break;)

returnfaIse;

)

//修改學(xué)生數(shù)據(jù)

booIList:：UpdateList(EIemType&e,ElemTypee1)

{for(inti=0;i<Iength;i++)

if(strcmp(eIem[i].name,e.name)==0){

eIem[i]=e1;returntrue;1

returnfaIse;

)

booIList::ListInsert(inti,EIemType&e)

{EIemType*p,*q;

if(i<1||i>Iength+1)returnfalse；

q=&elem[i—1];

for(p=&elem[Iength-1];p>=q;—p)

*(p+1)=*p;

*q=e;

++length；

returntrue;

1

〃對(duì)學(xué)生成績(jī)按升序或降序輸出

voidList::printIist(intmark)

{int*b=newint[Iength];

inti,k;

cout<<"姓名學(xué)號(hào)成績(jī)\n";

if(mark!=0){

for(i=0;i<length;i++)b[i]=i;

for(i=0;i<Iength;i++){k=i;

for(intj=i+1;j<length;j++){

if(mark==1&&elem[b[j]].score<eIem[b[k]].score)k=j；

if(mark==T&&elem[b[k]].score<eIem[b[j]].score)k=j；}

if(k!=i){intx=b[i];b[i]=b[k];b[k]=x;}}

for(inti=0;i〈Iength;i++)

{cout?setw(8)〈〈elem[b[i]]。name;

cout<<setw(10)〈<eIem[b[i]].stuno;

cout<<setw(9)<<elem[b[i]].age；

cout<<setw(8)?eIemscore<<endI;}}

else{

for(i=0;i<Iength;i++)

{cout<<setw(8)<<elem[i].name：

cout〈Vsetw(10)(<eIemLi].stuno;

cout<<setw(9)<<eIem[i]oage；

cout<<setw(8)<<elem[i].score<(endI;}}

}

voidmain()

{cout?"IineIist1m.cpp運(yùn)行結(jié)果：\n”;

ElemTypee,e1,e2,e3,e4,e5,e6;

List*La,*l_b,*Lc;

intk:

cout〈〈"首先調(diào)用插入函數(shù)。\n";

La->init(&La,4)；

w

strcpy(e1oname,"stu1);

strcpy(e1ostuno,100001"):

e1.age=22;

e1oscore=88;

La—>ListInsert(1,e1);

strcpy(e2.name,"stu2”);

strcpy(e2.stuno,”100002");

e2oage=21;

e2.score=79；

La—>ListInsert(2,e2);

strcpy(e3.name,Hstu3");

strepy(e3ostuno,"100003");

e3.age=19;

e3.score=87;

La-)ListInsert(3,e3);

La-)printIist(0);

cout<〈”表L.a長(zhǎng)："〈<La—〉ListLength()<(endI;

cinoget();

Lb—>init(&Lb,4);

strcpy(e4.name,uzmofun");

strepy(e4ostuno,"100001");

=

e4oage20;

e4oscore=94；

Lb—)ListInsert(1,e4)；

strcpy(e5.name,"bobjin")；

strcpy(e5.stuno,”100002")；

e5oage=23;

e5oscore=69;

Lb-〉Lis11nsert(2,e5);

strcpy(e6oname,"stu1;

strcpy(e6.stuno,"100001");

e6.age-22;

e6oscore=88;

Lb—〉ListInsert(3,e6);

Lb—>printIist(0);

cout〈V"表b長(zhǎng)："<〈l_b—>ListLength()〈<endI;

cin.get0;

k=Lc—>ListDelete(-1,e6);

if(k==0)cout〈〈”刪除失??！\n”；

eIsecout〈V"刪除成功！、n”；

cout<〈"輸出表Lc:\n";

Lc—〉printlist(0);

cin.get();

cout<〈"按成績(jī)升序輸出表Lc\n"；

Lc—>printIist(1);cinoget();

cout<<v按成績(jī)降序輸出表Lc\n";

Lc—〉printIist(-1);cin。get();

)

1o1.5運(yùn)行結(jié)果

首先建立學(xué)生信息管理，輸出結(jié)果為：

姓名。學(xué)號(hào)成績(jī)

Stu1。。100001&。80。

Stu2100002。91。

Stu3。。100003o56

其次查詢學(xué)號(hào)為100002的學(xué)生的成績(jī)，輸出結(jié)果為:

91

再次調(diào)用插入函數(shù)，插入Stu4成功！輸入結(jié)果為：

姓名。學(xué)號(hào)。成績(jī)。

Stu1o100001。。80b

Stu2oo100002?91。

Stu30100003?56?。

Stu4100004oo75。。

最后刪除Stu2成果！輸出結(jié)果為：

姓名。學(xué)號(hào)。成績(jī)

Stu110000180。

Stu3。。100003。。56。?>

Stu4。100004。。75o6。

查詢不及格的學(xué)生，輸出結(jié)果為：

Stu3*100003。。56?。

1.2考試報(bào)名管理

1.2.1項(xiàng)目簡(jiǎn)介

考試報(bào)名工作給各高校報(bào)名工作帶來(lái)了新的挑戰(zhàn)，給教務(wù)管理部門增加了很大的工作量，

報(bào)名數(shù)據(jù)手工錄入既費(fèi)時(shí)又會(huì)不可避免地出現(xiàn)錯(cuò)誤，同時(shí)也給不少學(xué)生以可乘之機(jī).本項(xiàng)目是

對(duì)考試報(bào)名管理的簡(jiǎn)單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信息；

查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。

1o2o2設(shè)計(jì)思路

本項(xiàng)目的實(shí)質(zhì)是完成對(duì)考生信息的建立、查找、插入、修改、刪除等功能，可以首先定

義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來(lái)完成對(duì)數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)

證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果.

1o2o3數(shù)據(jù)結(jié)構(gòu)

本項(xiàng)目的數(shù)據(jù)是一組考生信息，每條考生信息由準(zhǔn)考證號(hào)、姓名、性別、年齡、報(bào)考類別

等信息組成，這組考生信息具有相同特性，屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)

系。由此可以看出，這些數(shù)據(jù)也具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)可以采用

線性表來(lái)存儲(chǔ).

從上一節(jié)的例子中可見(jiàn)，線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系相鄰的兩個(gè)元素在物

理位置上也相鄰，因此可以隨機(jī)存儲(chǔ)表中任一元素，它的存儲(chǔ)位置可用一個(gè)簡(jiǎn)單、直觀的公式

來(lái)表示。然而，從另一個(gè)方面來(lái)看，這個(gè)特點(diǎn)也鑄成了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)：在做插入或刪

除操作時(shí)，需要移動(dòng)大量元素。為克服這一缺點(diǎn)，我們引入另一種存儲(chǔ)形式一一鏈?zhǔn)酱鎯?chǔ)。鏈

式存儲(chǔ)是線性表的另一種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因

此它沒(méi)有順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)，但同時(shí)也失去了順序表可隨機(jī)存取的特點(diǎn).

鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間利

用率低。事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價(jià)來(lái)?yè)Q取時(shí)間.

順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表

的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；若線性表的長(zhǎng)度變化較大，且其主要

操作是插入、刪除操作，則采用鏈表。

本項(xiàng)目對(duì)考生數(shù)據(jù)主要進(jìn)行插入、刪除、修改等操作，所以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比較適合。

用結(jié)構(gòu)體類型定義每個(gè)考生信息，故該單鏈表中的每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)可描述為：

typedefstructexaminee

{charexamno[10]；?//準(zhǔn)考證號(hào)

。charname[10];。。//姓名

charsex;

floatage；

charexamtype[5];?°〃成績(jī)

}ElemType;

1.2.4程序清單

//單鏈表的類定義IinkIist3oh

#ifndefIinkIis13H

#defineIinkIist3H

#defineLEN30

//定義EIemType為int

typedefintElemType;

//單鏈表中結(jié)點(diǎn)的類型

typedefstructLNode{

EIemTypedata;//值域

LNode*next;〃指針域

}LNode;

cIassLinkList(

LNode*head;

publie:

//構(gòu)造函數(shù)

LinkList();

//析構(gòu)函數(shù)

"LinkList0;

//清空單鏈表

voidClearList();

//求單鏈表長(zhǎng)度

intListSize();

//檢查單鏈表是否為空

booIListEmpty();

//返回單鏈表中指定序號(hào)的結(jié)點(diǎn)值

EIemTypeGetEIem(intpos);

//遍歷單鏈表

voidTraverseList(voidf(EIemType&));

//從單鏈表中查找元素

booIFindList(ElemType&item);

//更新單鏈表中的給定元素

boolUpdateList(constElemType&item,ElemTypee);

//向單鏈表插入元素，mark二0插在表首，否則插在表尾

voidInsertList(EIemTypeitem,intmark);

//從單鏈表中刪除元素，mark為要?jiǎng)h除的第幾個(gè)元素

boolDeleteList(ElemType&item,intmark);

//對(duì)單鏈表進(jìn)行有序排列mark>0升序，否則降序

voidpaiIie(intmark=1);

//對(duì)單鏈表進(jìn)行有序輸出，mark二0不排序，mark〉0升序，markVO降序

voidOrderOutputList(intmark=0);

)；

#endif

//IinkIist3.cpp

#include”IinkIist3.h”

LinkList::LinkList()//構(gòu)造函數(shù)

{head=newLNode;

head—>next=NULL;

)

LinkList:LinkList()//析構(gòu)函數(shù)

{LNode*p=head—〉next,*q;

while(p)

{q=p-)next;

free(p);

PF；

)

)

voidLinkList::ClearList()//清空單鏈表

{LNode*p=head—〉next,*q;

whiIe(p)

{q=p-)next;

free(p);

p=q;

)

head->next=NULL;

)

intLinkList::ListSize()//求單鏈表長(zhǎng)度

{LNode*p=head->next;

inti=O;

while(p)

{i++;

p=p->next;}

returni;

}

boolLinkList::ListEmptyO//檢查單鏈表是否為空

{returnListSize0=0;}

//返回單鏈表中指定序號(hào)的結(jié)點(diǎn)值

EIemTypeLinkList::GetEIem(intpos)

{LNode*p=head—〉next;

inti=1;

whiIe(p)

{if(i++==pos)returnp—〉data;

p=p-〉next;

)

returnhead—〉data;

)

voidLinkList::TraverseList(voidf(ElemType&))//遍歷單鏈表

{LNode*p=head—>next;

whiIe(p)

{f(p->data);

p=p—>next:}

)

boolLinkList:：FindList(EIemType&item)//從單鏈表中查找元素

{l_Node*p二head-〉next;

whiIe(p)

{if(p-〉data==itern)return1;

p=p—>next;)

return0;

}

//更新單鏈表中的給定元素

booILinkList::UpdateList(constElemType&item,EIemTypee)

{LNode*p=head—〉next；

boolfIag=0；

whiIe(p)

{if(p-)data二二item)

{p—>data=e;

flag=1;)

p=p->next;}

returnflag;

)

//向單鏈表插入元素

voidLinkList::InsertList(ElemTypeitem,intmark)

{LNode*q=newLNode;

q->data=item；

if(mark==0)

{q->next=head—〉next;

head-〉next=q;

return;}

LNode*p=head;

whiIe(p->next)

{p=p->next;}

q->next=NULL;

p->next=q;

)

//從單鏈表中刪除元素

booILinkList::DeleteList(EIemType&itern,intmai

{if(ListEmpty()|Imark<1IImark>ListSize())return0;

LNode*p=head,*q;

for(inti=0;i<mark-1;i++)

p=p—〉next;

item=p->next->data;

q=p->next->next;

free(p->next);

p->next=q;

return1；

}

//對(duì)單鏈表進(jìn)行有序排列mark>0升序，否則降序

voidLinkList::paiIie(intmark)

{ElemTypea[LEN+1]；

LNode*p=head-)next;

intk;

for(k=1;p!=NULL；k++,p=p—>next)

a[k]=p—〉data;

k----;

for(inti=1;i<k;i++)

for(intj=1;j<=k-i;j++)

{intt;

if(mark)0&&a[j])a[j+1]||mark<0&&a[j]<a[j+1])

{t=a[j+1];

a[j+1]=a[J];

a[j]=t;}}

p=head->next;

for(intj=1;j<=k;j++,p=p—〉next)

p->data=a[j];

)

〃對(duì)單鏈表進(jìn)行有序輸出

voidLinkList::0rder0utputList(intmark)

{EIemTypea[LEN+1];

LNode*p=head->next;

intk;

for(k=1;p!=NULL;k++,p=p—>next)

a[k]=p—>data;

k----;

for(inti=1;i<k;i++)

for(intj=1;j<=k—i;j++)

{intt;

if(mark>0&&a[j]>a[j+1]IImark<0&&a[j]

{t=a[j+1];

a[j+1]=a[j];

a[j]=t；}}

for(intj=1;j<=k;j++)

cout<<a[j]<<""；

}

#incIude〈iostream.h>

#incIude<iomanip.h>

#include(stdIib.h)

//#incIude<stdio.h>

#incIudevlinkIist3.cpp”

voidff(int&a)//用于遍歷的函數(shù)

{cout<<a<<""：}

voidmain()

{cout<<"\nIinkIist3m.cpp運(yùn)行結(jié)果：\n”;

intinit_size,seed,xu;

cout〈〈"首先請(qǐng)構(gòu)造單鏈表list";

cout〈〈"\n初始化長(zhǎng)度(1---30):“；

cin>>init_size;

seed=150;

。0戊〈<“是否排序：(二0不排序，=1升序，=—1降序)：”；

cin>>xu;

cout〈<”\n單鏈表list構(gòu)造成功！u<〈”\n它是：”；

Iist.TraverseList(ff);

coutV<”\n它為空嗎？(1:是；0:不是)："<〈Iist.ListEmpty0;

cout〈〈"\n長(zhǎng)度為：“〈〈Iist.ListSize();

inti;

cout<〈”\n請(qǐng)輸入你想得到第幾個(gè)元素的值(1--”<<init_si

cin>>i;

cout<<"單鏈表list中第“〈〈iVV”的值是“〈〈list。GetElem(i);

intit;

cout<〈”\n請(qǐng)輸入你想刪除第幾個(gè)元素的值(1--”〈<init_size〈V”)：”；

cin>>i;

Iist.DeleteList(it,i);

cout<〈”\n單鏈表Iist刪除第"?i?w個(gè)元素”〈V”「<Vit〈<"、'“<

<”后變?yōu)椋骸?

IistoTraverseList(ff);//對(duì)單鏈表Iist每個(gè)數(shù)進(jìn)行遍歷.

intnews,olds;

cout<<"\n請(qǐng)輸入要被修改的元素："；cin>>olds;

cout<〈"請(qǐng)輸入修改后要變成的元素：";cin>>news;

list.UpdateList(oIds,news);

cout<〈"\n修改后單鏈表Iist變?yōu)椋?;

IistoTraverseList(ff);

cout<<v\n下面請(qǐng)構(gòu)造單鏈表Iist2"；

cout<V"\n請(qǐng)輸入單鏈表Iist2初始化長(zhǎng)度(1——30):";

cin〉〉init_size;

seed=120;

coutV<”請(qǐng)選擇是否排序：(=0不排序，二1升序，二-1降序)：

cin>〉xu；

cout〈〈”\n按回車犍結(jié)束；

cin.get();cin0get();}

1.2.5運(yùn)行結(jié)果

1o3約瑟夫生者死者游戲

1.3。1項(xiàng)目簡(jiǎn)介

約瑟夫生者死者游戲的大意是：30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，

危險(xiǎn)萬(wàn)分；因此船長(zhǎng)告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無(wú)奈，

大家只得同意這種辦法，并議定30個(gè)人圍成一圈，由第一個(gè)人開(kāi)始，依次報(bào)數(shù)，數(shù)到第9

人，便把他投入大海中，然后從他的下一個(gè)人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，

直到剩下15個(gè)乘客為止。問(wèn)哪些位置是將被扔下大海的位置。

1.3.2設(shè)計(jì)思路

本游戲的數(shù)學(xué)建模如下：假設(shè)n個(gè)旅客排成一個(gè)環(huán)形，依次順序編號(hào)1,2,…，n?從某

個(gè)指定的第1號(hào)開(kāi)始，沿環(huán)計(jì)數(shù)，每數(shù)到第m個(gè)人就讓其出列，且從下一個(gè)人開(kāi)始重新計(jì)數(shù)，

繼續(xù)進(jìn)行下去。這個(gè)過(guò)程一直進(jìn)行到剩下k個(gè)旅客為止。

本游戲的要求用戶輸入的內(nèi)容包括：

1.旅客的個(gè)數(shù)，也就是n的值；

2.離開(kāi)旅客的間隔數(shù)，也就是m的值；

3.所有旅客的序號(hào)作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。

本游戲要求輸出的內(nèi)容是包括

1o離開(kāi)旅客的序號(hào)；

2o剩余旅客的序號(hào)；

所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進(jìn)行算法實(shí)

現(xiàn)。

1o3.3數(shù)據(jù)結(jié)構(gòu)

為了解決這一問(wèn)題，可以用長(zhǎng)度為30的數(shù)組作為線性存儲(chǔ)結(jié)構(gòu)，并把該數(shù)組看成是一個(gè)

首尾相接的環(huán)形結(jié)構(gòu)，那么每投入大海一個(gè)乘客，就要在該數(shù)組的相應(yīng)位置做一個(gè)刪除標(biāo)記，

該單元以后就不再作為計(jì)數(shù)單元。這樣做不僅算法較為復(fù)雜，而且效率低，還要移動(dòng)大量的元

素.用單循環(huán)鏈表解決這一問(wèn)題，實(shí)現(xiàn)的方法相對(duì)要簡(jiǎn)單得多.首先要定義鏈表結(jié)點(diǎn)，單循環(huán)鏈

表的結(jié)點(diǎn)結(jié)構(gòu)與一般的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一個(gè)整數(shù)來(lái)表示位置；然后將它們組

成具有30個(gè)結(jié)點(diǎn)的單循環(huán)鏈表。接下來(lái)從位置為1的結(jié)點(diǎn)開(kāi)始數(shù)，數(shù)到第8個(gè)結(jié)點(diǎn)，就將

下一個(gè)結(jié)點(diǎn)從循環(huán)鏈表中刪去，然后再?gòu)膭h去結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開(kāi)始數(shù)起，數(shù)到第8個(gè)結(jié)點(diǎn)，

再將其下一個(gè)結(jié)點(diǎn)刪去，如此進(jìn)行下去，直到剩下15個(gè)結(jié)點(diǎn)為止。

為了不失一般性，將30改為一個(gè)任意輸入的正整數(shù)n,而報(bào)數(shù)上限(原為9)也為一個(gè)任

選的正整數(shù)k.這樣該算法描述如下：

(1)創(chuàng)建含有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表；

(2)生著與死者的選擇：

p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始i置為1;

while(i<=n/2)//刪除一半的結(jié)點(diǎn)

{從p指向的結(jié)點(diǎn)沿鏈前進(jìn)k—1步：

刪除第k個(gè)結(jié)點(diǎn)(q所指向的結(jié)點(diǎn))；

p指向q的下一個(gè)結(jié)點(diǎn)；

榆出其位置q->data;

。i自增1;

)

(3)輸出所有生者的位置.

1.3.4程序清單

LinkListInitRing(intn,LinkListR)//尾插入法建立單循

環(huán)鏈表函數(shù)

1°

ListNode*p,*q;

ointI;

oR=q=(LinkNode*)maIIoc(sizeof(LinkNode));

for(i=1;i〈n；i++){

。。p=(LinkNode*)maIloc(sizeof(LinkNode));

。。q—〉data=i;

oq->next=p;

6q-P；

6)

op->data=n;

p->next=R;

R二P；

t>returnR：

)

LinkListDeleteDeath(intn,intk,LinkListR)//

生者與死者的選擇

(

。inti,j;

ListNode*p,*q;

。P=R;

for(i=1;i<n/2；i++){//刪除一半結(jié)點(diǎn)

。for(j=1;j<k—1：j++)//沿鏈前進(jìn)k-1步

。。p=p—>next；

eq=p-〉next;

p->next=q—〉next;

oprintf(“%4d"，q->data);

。free(q);

}

R=p;returnR;

°}

ovoid0utRing(intn,LinkListR){//輸

出所有生者

。inti;

LinkNode*p;

°°p=R;

for(i=1;i〈二n/2;i++,p=p—)next){

。。printf(u%4d",p->data)

)

有了上述算法分析和設(shè)計(jì)之后，實(shí)現(xiàn)就比較簡(jiǎn)單了。首先要定義一個(gè)鏈表結(jié)構(gòu)類型，然后

編寫一個(gè)主函數(shù)調(diào)用上面已定義好的函數(shù)即可.主函數(shù)的源程序如下:

#include<stdio.h)

#incIude〈stdlib.h〉

typed