數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告報(bào)告（八皇后和停車場(chǎng)）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告報(bào)告（八皇后和停車場(chǎng)）第1章八皇后問題

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文

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

學(xué)號(hào)：1005170116姓名：李登班級(jí)：管理101專業(yè)：信息管理與信息系統(tǒng)系別:管理系指導(dǎo)教師：孫鴻飛

2023年12月30日吉林

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文目錄

第1章八皇后問題-1-

1.1課題綜述八皇后問題的來源及意義-1-

1.2面對(duì)的問題-1-

1.2．1解決沖突問題-1-1.2．2所用的知識(shí)-2-1.3需求分析-2-

1.3.1涉及到的知識(shí)點(diǎn)-2-

1.3.2功能要求-2-1.4概要設(shè)計(jì)-2-1.4.1解決沖突問題-3-1.4.2數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)-3-1.4.3流程圖-4-1.5詳細(xì)設(shè)計(jì)-4-1.6調(diào)試分析及測(cè)試-6-

1.6.1遇到的問題及解決方法-6-1.6.2算法的時(shí)空分析-7-1.6.3程序模塊構(gòu)架-7-1.6.4程序使用說明-7-1.6.5測(cè)試結(jié)果-7-

第2章停車場(chǎng)管理問-10-

2.1要解決的問題-10-2.2基本要求-10-

2.2.1解決問題的思路及要求-10-2.2．2對(duì)棧的要求-11-2.2.3算法流程圖-11-2.5.1棧的抽象數(shù)據(jù)類型-13-2.5.2鏈?zhǔn)疥?duì)列的抽象數(shù)據(jù)類型-14-2.6模塊劃分-16-

2.6.1主程序模塊-16-2.6.2兩個(gè)棧模塊-16-2.6.3隊(duì)列模塊-17-實(shí)現(xiàn)隊(duì)列抽象數(shù)據(jù)類型-17-數(shù)據(jù)對(duì)象：D={aiai∈ElemSet,i=1,2,??,n,n=0}-17-2.6.4模塊調(diào)用關(guān)系-17-2.7詳細(xì)設(shè)計(jì)與源程序-17-

I

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文2.7.1詳細(xì)設(shè)計(jì)-17-2.7.2部分源程序-18-2.8調(diào)試過程中的問題及系統(tǒng)測(cè)試狀況-20-

2.8.1出現(xiàn)的問題-20-

2.8.2運(yùn)行過程-20-

課程設(shè)計(jì)心得體會(huì)-26-經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文1.2．2所用的知識(shí)

使用數(shù)據(jù)結(jié)構(gòu)的知識(shí)，用遞歸法解決問題

1.3需求分析

1.3.1涉及到的知識(shí)點(diǎn)

本次課程設(shè)計(jì)中，用到的主要知識(shí)有：遞歸法的運(yùn)用，for語句的靈活運(yùn)用。

數(shù)據(jù)結(jié)構(gòu)中樹知識(shí)的靈活運(yùn)用、棧及數(shù)組的把握。

1.3.2功能要求

當(dāng)運(yùn)行程序時(shí)，在屏幕上顯示每一種方法八個(gè)皇后的相對(duì)位置，要用比較直觀的界面顯示。

進(jìn)入界面后，就會(huì)提醒輸入字符串的輸入形式，在八皇后求解程序中，只要你選擇輸出解的格式，選擇1則顯示為每一列皇后的放置的行數(shù)，，選擇2則顯示的是以矩陣形式形象的顯示皇后的放置位置，選擇0則退出程序的調(diào)試。在調(diào)試結(jié)果中，1的位置也就表示了該皇后應(yīng)當(dāng)所在的位置，0代表了空位置。

1.4概要設(shè)計(jì)

本課件學(xué)生是用循環(huán)遞歸循環(huán)來實(shí)現(xiàn)的，分別一一測(cè)試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來。在這個(gè)程序中，我的主要思路以及思想是這樣的：

-2-

第1章八皇后問題1.4.1解決沖突問題

這個(gè)問題包括了行，列，兩條對(duì)角線；

列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；

行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；

對(duì)角線：對(duì)角線有兩個(gè)方向。在這我把這兩條對(duì)角線稱為：主對(duì)角線和從對(duì)角線。在同一對(duì)角線上的所有點(diǎn)（設(shè)下標(biāo)為(i,j)），要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。因此，當(dāng)?shù)贗個(gè)皇后占領(lǐng)了第J列后，要同時(shí)把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。

1.4.2數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)

而對(duì)于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，學(xué)生則是著重于:

數(shù)組a[I]：a[I]表示第I個(gè)皇后放置的列；I的范圍：1..8;

對(duì)角線數(shù)組：b[j](主對(duì)角線),c[j]（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后

-3-

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文1.4.3流程圖

圖1-1算法流程圖

1.5詳細(xì)設(shè)計(jì)

解析：遞歸實(shí)現(xiàn)n皇后問題。

算法分析：

數(shù)組a、b、c分別用來標(biāo)記沖突，a數(shù)組代表列沖突，從a[0]~a[7]代表第0列到第7列。假使某列上已經(jīng)有皇后，則為1，否則為0。

數(shù)組b代表主對(duì)角線沖突，為b[i-j+7]，即從b[0]~b[14]。假使某條主對(duì)角線上已經(jīng)有皇后，則為1，否則為0。

數(shù)組c代表從對(duì)角線沖突，為c[i+j]，即從c[0]~c[14]。假使某條從對(duì)角線上已經(jīng)有皇后，則為1，否則為0。

代碼如下：

-4-

第1章八皇后問題#include

staticcharQueen[8][8];staticinta[8];staticintb[15];staticintc[15];

staticintiQueenNum=0;//記錄總的棋盤狀態(tài)數(shù)voidqu(inti);//參數(shù)i代表行intmain(){

intiLine,iColumn;

//棋盤初始化，空格為*，放置皇后的地方為@for(iLine=0;iLine第1章八皇后問題1.6.2算法的時(shí)空分析

該算法的運(yùn)行時(shí)間和和皇后的放置方法成正比，在最好狀況下的時(shí)間和空間繁雜度均為O（1），在最差狀況下均為O（n*n），平均狀況在它們之間。

1.6.3程序模塊構(gòu)架

本程序模塊劃分比較合理，且利用指數(shù)組存儲(chǔ)棋盤，操作便利。至于整體的系統(tǒng)架構(gòu)，為了簡(jiǎn)單起見，這樣的系統(tǒng)可以分成兩個(gè)模塊，第一個(gè)模塊是負(fù)責(zé)模擬問題、提供算法，而另外一個(gè)模塊則致力于窗口演示，是一個(gè)窗體應(yīng)用程序

1.6.4程序使用說明

本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)

進(jìn)入演示程序后即顯示文本方式的用戶界面

進(jìn)入界面后，就會(huì)提醒輸入字符串的輸入形式，在八皇后求解程序中，只要你選擇輸出解的格式，選擇1則顯示為每一列皇后的放置的行數(shù)，，選擇2則顯示的是以矩陣形式形象的顯示皇后的放置位置，選擇3則退出程序的調(diào)試。在調(diào)試結(jié)果中，1的位置也就表示了該皇后應(yīng)當(dāng)所在的位置，0代表了空位置。

1.6.5測(cè)試結(jié)果

-7-

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文圖1-2初步運(yùn)行界面

圖1-3位置標(biāo)明每一行皇后放置的列數(shù)

-8-

第1章八皇后問題

圖1-4位置標(biāo)明每一行皇后放置的列數(shù)

圖1-5視圖矩陣形式顯示皇后位置

-9-

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文第2章停車場(chǎng)管理問

2.1要解決的問題

停車場(chǎng)是一條可以停放n輛車的狹窄通道，且只有一個(gè)大門汽車停放安到達(dá)時(shí)間的先后依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停在最北端）若停車場(chǎng)已經(jīng)停滿n輛車，后來的汽車在便道上等候，一旦有車開走，排在便道上的第一輛車可以開入；當(dāng)停車場(chǎng)的某輛車要離開時(shí)，停在他后面的車要先后退為他讓路，等它開出后其他車在依照原次序開入車場(chǎng)，每?jī)赏Ｔ谲噲?chǎng)的車要安時(shí)間長(zhǎng)短繳費(fèi)。要求：以棧模擬停車場(chǎng)，以隊(duì)列車場(chǎng)外的便道，依照從終端輸入的數(shù)據(jù)序列進(jìn)行模擬管理。每一組數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)〞或“離去〞信息、汽車牌照號(hào)碼、以及到達(dá)或離去的時(shí)刻。對(duì)每一組數(shù)據(jù)進(jìn)行操作后的信息為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)的內(nèi)或便道上的位置：若是車輛離去則輸出汽車在停車場(chǎng)內(nèi)的停留時(shí)間和應(yīng)繳納的費(fèi)用（在便道上的停留時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。

2.2基本要求

2.2.1解決問題的思路及要求

以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，依照從終端讀入的輸入

數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車到達(dá)或離去信息，汽車牌照號(hào)碼以及到達(dá)或離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。

-10-

第2章停車場(chǎng)管理問2.2．2對(duì)棧的要求

需要另設(shè)一個(gè)棧，臨時(shí)停放為離去的汽車讓路而從停車場(chǎng)退出來的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻

2.2.3算法流程圖

-11-

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文開始初始化兩個(gè)棧Enter和Temp及一個(gè)隊(duì)列進(jìn)入主菜車到達(dá)車離開列表顯退出是車場(chǎng)是否否車場(chǎng)內(nèi)信便道車信退出列表顯示Room前車輛進(jìn)臨對(duì)room否判斷棧是否為否元素進(jìn)棧Enter判便道是否有是是元素進(jìn)隊(duì)列便道車進(jìn)棧Enter元素隊(duì)列中元素進(jìn)隊(duì)列Wait中元素出終止圖2-1算法流程圖

-12-

第2章停車場(chǎng)管理問

2.4算法基本思想描述

由于停車場(chǎng)是一個(gè)狹窄通道，而且只有一個(gè)大門可供汽車進(jìn)出，問題要求汽車停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列。由此很簡(jiǎn)單聯(lián)想到數(shù)據(jù)結(jié)構(gòu)中的堆棧模型，因此可首先設(shè)計(jì)一個(gè)堆棧，以堆棧來模擬停車場(chǎng)，我設(shè)計(jì)用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)停車場(chǎng)內(nèi)的車輛信息，并給車輛按進(jìn)棧順序編號(hào)，當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在他之后進(jìn)入的車輛必需先退出車場(chǎng)為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入停車場(chǎng)。這是個(gè)一退一進(jìn)的過程，而且讓道的汽車必需保持原有的先后順序，因此可再設(shè)計(jì)一個(gè)堆棧，以之來暫時(shí)存放為出站汽車暫時(shí)讓道的汽車。當(dāng)停車場(chǎng)滿后，繼續(xù)進(jìn)來的汽車需要停放在停車場(chǎng)旁邊的便道上等候，若停車場(chǎng)有汽車開走，則按排隊(duì)的先后順序依次進(jìn)站，最先進(jìn)入便道的汽車將會(huì)最先進(jìn)入停車場(chǎng)，這完全是一個(gè)先進(jìn)先出模型，因此可設(shè)計(jì)一個(gè)隊(duì)列來模擬便道，隊(duì)列中的數(shù)據(jù)元素設(shè)計(jì)成汽車的車牌號(hào)，并以鏈表的形式存儲(chǔ)。另外，停車場(chǎng)根據(jù)汽車在停車場(chǎng)內(nèi)停放的總時(shí)長(zhǎng)來收費(fèi)的，在便道上的時(shí)間不計(jì)費(fèi)，因此必需記錄車輛進(jìn)入停車場(chǎng)時(shí)的時(shí)間和車輛離開停車場(chǎng)時(shí)的時(shí)間，然后計(jì)算、顯示費(fèi)用狀況。

2.5概要設(shè)計(jì)

2.5.1棧的抽象數(shù)據(jù)類型

ADTstack{

數(shù)據(jù)對(duì)象：D={aiai∈charset,I=1,2,??，n,n=0}數(shù)據(jù)關(guān)系：R1={ai-1,aiai-1,ai∈D,I=2??,n}基本操作：Initstack(StructQnodenext;}Qnode,QueuePtr;

-14-

第2章停車場(chǎng)管理問typedefstruct{

QueuePtrfront;隊(duì)頭指針QueuePtrrear;隊(duì)尾指針ADTQueue{

數(shù)據(jù)對(duì)象：D={aiai∈ElemSet,i=1,2,??,n,n=0}數(shù)據(jù)關(guān)系：R1={ai-1,aiai-1,ai∈D,i=2,??,n}約定中端為隊(duì)列頭，后端為隊(duì)列尾?；静僮鳎篒nitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q)

初始條件：隊(duì)列Q已經(jīng)存在。

操作結(jié)果：隊(duì)列Q被銷毀，不再存在。ClearQueue(&Q)

初始條件：隊(duì)列Q已經(jīng)存在。操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(Q)

初始條件：隊(duì)列Q已經(jīng)存在。

操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則FALSE。QueueLength(Q)

初始條件：隊(duì)列Q已經(jīng)存在。

操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回的e隊(duì)頭元素。EnQueue(&Q,e)

初始條件：隊(duì)列Q已經(jīng)存在。

操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。QueueTraverse(Q,visit())初始條件：Q已經(jīng)存在且非空。

-15-

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對(duì)Q的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。}ADTQueue

2.6模塊劃分

2.6.1主程序模塊

main(){

初始化

while(重復(fù)條件){接受命令；

switch(調(diào)用條件){

Case調(diào)用條件’A’到達(dá)處理；break；Case調(diào)用條件’D’離開處理；break；Case調(diào)用條件’E’退出處理；}

}}

2.6.2兩個(gè)棧模塊

實(shí)現(xiàn)棧抽象數(shù)據(jù)類型:

數(shù)據(jù)對(duì)象：D={aiai∈charset,I=1,2,??，n,n=0}

數(shù)據(jù)關(guān)系：R1={ai-1,aiai-1,ai∈D,I=2??,n}

-16-

第2章停車場(chǎng)管理問2.6.3隊(duì)列模塊

實(shí)現(xiàn)隊(duì)列抽象數(shù)據(jù)類型

數(shù)據(jù)對(duì)象：D={aiai∈ElemSet,i=1,2,??,n,n=0}

數(shù)據(jù)關(guān)系：R1={ai-1,aiai-1,ai∈D,i=2,??,n}約定中端為隊(duì)列頭，后端為隊(duì)列尾。

2.6.4模塊調(diào)用關(guān)系

主程序模塊

棧模塊1

隊(duì)列模塊

棧模塊2

圖2-2模塊調(diào)用關(guān)系

棧模塊1模擬停車場(chǎng)棧模塊2模擬倒車場(chǎng)隊(duì)列模塊模擬車道

2.7詳細(xì)設(shè)計(jì)與源程序

2.7.1詳細(xì)設(shè)計(jì)

以棧模擬停車場(chǎng),以隊(duì)列模擬停車場(chǎng)外的便道,依照從終端讀入的輸入數(shù)據(jù)序

-17-

經(jīng)濟(jì)管理學(xué)院本科課程設(shè)計(jì)論文列進(jìn)行模擬管理。另設(shè)一個(gè)棧，臨時(shí)停放為離去的汽車讓路而從停車場(chǎng)退出來的汽車。棧以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。

停車場(chǎng)棧park模擬停車場(chǎng)。臨時(shí)棧Aux-park模擬倒車場(chǎng)。便道隊(duì)列Road模擬停車場(chǎng)外便道。

程序運(yùn)行后，先設(shè)定停車時(shí)間單位和計(jì)費(fèi)單位，再設(shè)定停車場(chǎng)容量（測(cè)試數(shù)據(jù)設(shè)定停車場(chǎng)容量n=2）。繼續(xù)輸入車輛數(shù)據(jù)：車輛屬性（到達(dá)’A’或離開’D’）、車牌號(hào)、時(shí)間（到達(dá)時(shí)間或離開時(shí)間）。程序根據(jù)輸入數(shù)據(jù)中的“車輛屬性〞進(jìn)入該屬性程序模塊。輸出車輛停放位置或離開時(shí)的收據(jù)。然后循環(huán)，繼續(xù)輸入車輛數(shù)據(jù)。當(dāng)輸入車輛數(shù)據(jù)為’E’時(shí)，程序自動(dòng)退出。

2.7.2部分源程序

停車場(chǎng)問題管理程序代碼如下：

#include//定義輸入／輸出函數(shù)

#include//數(shù)據(jù)流輸入／輸出#include//字符串處理

#include//定義數(shù)學(xué)函數(shù)

#include//定義雜項(xiàng)函數(shù)及內(nèi)存分派函數(shù)#definesize2//停車場(chǎng)位置數(shù)//模擬停車場(chǎng)的堆棧的性質(zhì)typedefstructzanlind{intnumber;//汽車車號(hào)

intar_time;//汽車到達(dá)時(shí)間}zanInode;

typedefstruct{

zanInode*base;//停車場(chǎng)的堆棧底zanInode*top;//停車場(chǎng)的堆棧頂

intstacksize_curren;}stackhead;

//堆棧的基本操作；

voidinitstack(stackheadif(!L.base)exit(0);//存儲(chǔ)分派失敗L.top=L.base;

-18-

第2章停車場(chǎng)管理問L.stacksize_curren=0;}

voidpush(stackhead

L.stacksize_curren++;

}

voidpop(stackhead}

e=*(--L.top);

L.stacksize_curren--;}

//模擬便道的隊(duì)列的性質(zhì)

typedefstructduilie{intnumber;//汽車車號(hào)

intar_time;//汽車到達(dá)時(shí)間structduilie*next;}*queueptr;

Typedefstruct{

queueptrfront;//便道的隊(duì)列的隊(duì)頭queueptrrear;//便道的隊(duì)列的隊(duì)尾intlength;}