數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-3

1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告書

學(xué)校青島科技高校

學(xué)號(hào)

姓名

指導(dǎo)老師劉勇

課程設(shè)計(jì)的名稱：同學(xué)成果管理

1.問題描述：

同學(xué)成果管理是學(xué)校教務(wù)管理的重要組成部分，其處理信息量很大，該題目是對(duì)同學(xué)的成果管理作一個(gè)簡(jiǎn)潔的模擬，其中同學(xué)信息包括：學(xué)號(hào)、姓名與成果。成果分為課程1成果、課程2成果、課程3成果和總成果。要求設(shè)計(jì)一個(gè)簡(jiǎn)易的成果管理系統(tǒng)，輸入各門功課的成果后能自動(dòng)求出總成果，并通過菜單選擇操作方式完成下列功能：

①登記同學(xué)成果；

②②查詢同學(xué)成果；

③插入同學(xué)成果；

④④刪除同學(xué)成果；

⑤按總成果降序排序。

2.基本要求：

該題目涉及到單鏈表的各種操作，包括單鏈表的建立、結(jié)點(diǎn)的查找、插入、刪除等基本運(yùn)算。首先建立同學(xué)成果單鏈表，鏈表中每個(gè)結(jié)點(diǎn)由4個(gè)域組成，分別為：學(xué)號(hào)、姓名、成果、存放下一個(gè)結(jié)點(diǎn)地址的next域。然后將要求完成的四項(xiàng)功能寫成四個(gè)函數(shù)，登記同學(xué)成果對(duì)應(yīng)建立同學(xué)單鏈表的功能，后三個(gè)功能分別對(duì)應(yīng)單鏈表的查詢、插入與刪除三大基本操作。

3.算法思想：

Creat函數(shù)算法思想：從0至n循環(huán)輸入n個(gè)同學(xué)的三科成果，并且計(jì)算總成果。

Inquiry函數(shù)算法思想：將學(xué)號(hào)與已輸入的全部學(xué)號(hào)做比較，一旦相同則輸出該學(xué)號(hào)信息，否則顯示沒有該同學(xué)信息。

Insert函數(shù)算法思想：生成一個(gè)新節(jié)點(diǎn)，然后將其接到原有鏈表尾部。

Delete函數(shù)算法思想：通過ID找到該節(jié)點(diǎn)，并刪去該節(jié)點(diǎn)。

Sort(函數(shù)算法思想：利用排序算法對(duì)每一個(gè)節(jié)點(diǎn)作比較并更換其在鏈表中的位置挨次。

4.模塊劃分

（1）LinkListCreat(LinkListT,intn)其功能是制造節(jié)點(diǎn)，錄入成果。

（2）voidInquiry(LinkListT)其功能是查詢與已知ID全都的同學(xué)信息并展現(xiàn)出來(lái)。（3）voidInsert(LinkListT,intn)其功能是添加若干個(gè)同學(xué)的成果信息。

（4）voidDelete(LinkListT)其功能是刪除若干個(gè)同學(xué)的成果信息。

（5）voidSort(LNode*p)其功能是排序并展現(xiàn)若干個(gè)同學(xué)的成果信息。

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

數(shù)據(jù)類型LNode定義如下：

typedefstructLNode

{

intID;

charname[20];

intscore1;

intscore2;

intscore3;

inttotal;

structLNode*next;

}LNode,*LinkList;

6.源程序：

源代碼

//main.c

#include

#include

typedefstructLNode

{

intID;

charname[20];

intscore1;

intscore2;

intscore3;

inttotal;

structLNode*next;

}LNode,*LinkList;

LinkListCreat(LinkListT,intn);voidDelete(LinkListT);

voidInquiry(LinkListT);

voidInsert(LinkListT,intn);voidSort(LNode*p);

voidInsert(LinkListT,intn){

inti;

LNode*r=T,*p;

while((r->next)!=NULL)

{

r=r->next;

}

for(i=0;iname);

printf("Pleaseenterthestudent'sscore1:");

scanf("%d",

printf("Pleaseenterthestudent'sscore2:");

scanf("%d",

printf("Pleaseenterthestudent'sscore3:");

scanf("%d",

p->total=p->score1+p->score2+p->score3;

printf("Thetotalscoreis%d\n",p->total);

p->next=NULL;

r->next=p;

r=p;

}

printf("\nInsertiscomplete!");

}

voidInquiry(LinkListT)

{

intid;

printf("PleaseenterthestudentIDyouwanttoinquireabout:");

scanf("%d",

LNode*p=T;

p=p->next;

while(p!=NULL)

{

if(p->ID==id)

{

printf("\nThestudentscoresinformationhasbeensuccessfullyinquired!\n");

printf("ID:%d\nName:%s\nScore1:%d\nScore2:%d\nScore

3:%d\n",p->ID,p->name,p->score1,p->score2,p->score3);

break;

}

else

{

p=p->next;

}

}

if(!p)

printf("Sorry!Didnotinquirythestudentscoresinformation!");}

。。。。。。獵取源程序:1135047472

7.測(cè)試狀況：

截圖：

程序輸出為：Num:1

ID:1Name:n1Score1:78Score2:89Score3:84

total:251

Num:2

ID:3

Name:n3

Score1:68

Score2:89

Score3:90

total:247

課程設(shè)計(jì)的名稱：停車場(chǎng)的管理

1.問題描述：

設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后挨次，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛汽車，則后來(lái)的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；

當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必需先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必需按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。

試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。

2.基本要求：

綜合利用棧和隊(duì)列模擬停車場(chǎng)管理，學(xué)習(xí)利用棧和隊(duì)列解決實(shí)際問題。

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

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

3.算法思想：

停車場(chǎng)運(yùn)用棧的算法思想管理車輛信息；便道運(yùn)用隊(duì)列的算法思想管理等待進(jìn)入停車場(chǎng)的車輛信息；臨時(shí)停放讓路的車輛信息也用隊(duì)列算法思想管理。

4.模塊劃分：

voidPRINT(CarNode*p,introom其功能為打印出場(chǎng)車的信息

voidArrive(SeqStackCar*Enter,LinkQueueCar*W)其功能為記錄進(jìn)場(chǎng)車和等待進(jìn)場(chǎng)車信息voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)其功能為記錄出場(chǎng)車信息

voidList1(SeqStackCar*S)其功能為顯示存車信息

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

（1）數(shù)據(jù)類型Time定義如下：

typedefstructtime

{

inthour;

intmin;

}Time;

（2）數(shù)據(jù)類型CarNode定義如下：

typedefstructnode

{

charnum[10];

Timereach;

Timeleave;

}CarNode;

（3）數(shù)據(jù)類型SeqStackCar定義如下：

typedefstructNODE

{

CarNode*stack[MAX+1];

inttop;

}SeqStackCar;

（4）數(shù)據(jù)類型QueueNode定義如下：

typedefstructcar

{

CarNode*data;

structcar*next;

}QueueNode;

（5）數(shù)據(jù)類型LinkQueueCar定義如下：

typedefstructNode

{

QueueNode*head;

QueueNode*rear;

}LinkQueueCar;

6.源程序：

源代碼

獵取源程序請(qǐng)加:11350474727．測(cè)試狀況：

截圖：

程序輸出為：

TheSystemofparking

1.cararrive

2.carleave

3.showcar

0.quitsystem

ParkingLot

place:1arrivedtime:5:45number:2

place:2arrivedtime:9:14number:1

Returnmainmeun(1.return0.quit)

課程設(shè)計(jì)的名稱：二叉樹的基本操作的實(shí)現(xiàn)

1.問題描述：

?在主程序中編寫一個(gè)簡(jiǎn)潔的菜單，將有關(guān)二叉樹的操作?建立一棵二叉樹的存儲(chǔ)結(jié)構(gòu)

?遍歷一棵二叉樹（包括層次遍歷）

?統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)

?求二叉樹的深度

?子樹交換

2.基本要求：

?建立一棵二叉樹的存儲(chǔ)結(jié)構(gòu)

?遍歷一棵二叉樹（包括層次遍歷）

?統(tǒng)計(jì)二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)

?求二叉樹的深度

?子樹交換

3.算法思想：

CreatBiTree運(yùn)用遞歸制造二叉樹的每一個(gè)節(jié)點(diǎn)；

Exchange通過遞歸交換左右子樹；

Depth通過遞歸計(jì)算二叉樹的深度。

InorderTraverse遞歸中序遍歷二叉樹。

PreOrderTraverse遞歸先續(xù)遍歷二叉樹。PostOrderTraverse遞歸后續(xù)遍歷二叉樹。

4.模塊劃分：

（1）BiTreeCreatBiTree(BiTreeT)其功能是制造一顆二叉樹；（2）intDepth(BiTreeT)其功能是計(jì)算一顆二叉樹的深度（3）voidExchange(BiTreeT)其功能是交換左右子樹

（4）voidInorderTraverse(BiTreeT)其功能是中序遍歷（5）voidPreOrderTraverse(BiTreeT)其功能是前序遍歷

（6）voidPostOrderTraverse(BiTreeT)其功能是后序遍歷5.數(shù)據(jù)結(jié)構(gòu)：

（1）數(shù)據(jù)類型BiTNode定義如下：

typedefstructBiTNode

{

chardata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

6.源程序：

源代碼獵取源程序請(qǐng)加:1135047472

7.測(cè)試狀況：

截圖：

程序輸出為：

Pleaseinputthenumofyourchoice:5

LevelOrder:ACBED

Pleaseinputthenumofyourchoice:7

Depthis3

Pleaseinputthenumofyourchoice:6

TheNodeCountis5

課程設(shè)計(jì)的名稱：圖的基本操作的實(shí)現(xiàn)

1.問題描述：

在主程序中建立一個(gè)菜單，實(shí)現(xiàn)圖的基本操作

2.基本要求：

圖的基本操作，包括：

建立圖的存儲(chǔ)結(jié)構(gòu)，

實(shí)現(xiàn)圖的深度優(yōu)先搜尋遍歷，

廣度優(yōu)先搜尋遍歷

利用圖的拓?fù)渑判蝌?yàn)證圖中是否存在環(huán)

3.算法思想：

createGraph通過for循環(huán)利用鏈表結(jié)構(gòu)錄入點(diǎn)和邊的數(shù)據(jù)。

BFS和DFS以及TopologicalSort利用遞歸思想實(shí)現(xiàn)遍歷和排序。

4.模塊劃分：

voidcreateGraph其功能為錄入點(diǎn)和邊以及其關(guān)系的數(shù)據(jù)。voidBFS(ALGraph

intarcs[40][40];

intvexnum,arcnum;

intkind;

}MGRAPH;

（2）數(shù)據(jù)類型LNode定義如下：

typedefstruct

{

intadjvex;

structnode3*next;

}EDGENODE;

（3）數(shù)據(jù)類型LNode定義如下：

typedefstruct

{

intvertex;

EDGENODE*link;

intid;

}VEXNODE;

（4）數(shù)據(jù)類型LNode定義如下：

typedefstruct

{

VEXNODEadjlist[40];

intvexnum,arcnum;

intkind;

}ADJGRAPH;

6.源程序：

源代碼：獵取源請(qǐng)加:1135047472

7.測(cè)試狀況：

截圖：

程序輸出為：

請(qǐng)輸入圖的頂點(diǎn)個(gè)數(shù):4

請(qǐng)輸入邊數(shù):4

第1個(gè)頂點(diǎn)的名稱:a

第2個(gè)頂點(diǎn)的名稱:b

第3個(gè)頂點(diǎn)的名稱:c

第4個(gè)頂點(diǎn)的名稱:d

請(qǐng)輸入第1條邊的起始位置與終止位置:ab

請(qǐng)輸入第2條邊的起始位置與終止位置:ac

請(qǐng)輸入第3條邊的起始位置與終止位置:ad

請(qǐng)輸入第4條邊的起始位置與終止位置:bc

深度遍歷排序：0123

廣度遍歷排序：0123

該有向圖無(wú)回路

課程設(shè)計(jì)的名稱：哈希查找的設(shè)計(jì)與實(shí)現(xiàn)1.問題描述：

編寫一個(gè)程序?qū)崿F(xiàn)哈希表的相關(guān)運(yùn)算。

2.基本要求：

完成如下功能：

（1）建立｛16，74，60，43，54，90。46，31，29，88，77｝哈希表A[0..12]，哈希函數(shù)為H（k）=key%p，并用線性探查法解決沖突；

（2）在上述哈希表中查找關(guān)鍵字為29的記錄；

（3）在上述哈希表中刪除關(guān)鍵字為77的記錄，再將其插入。

3.算法思想：

CreatHT通過m次循環(huán)對(duì)哈希表初始化。

InsertHT通過循環(huán)體將數(shù)組內(nèi)元素放入哈希表中

SearchHT采納線性探查法找下一個(gè)地址

DeleteHT調(diào)用SearchHT找到該關(guān)鍵字并刪除

DispHT利用循環(huán)體輸出哈希表

4.模塊劃分：

voidCreatHT(HashTableha,intx,intn,intm,intp)創(chuàng)建哈希表；

intInsertHT(Ha