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

1、數(shù)據(jù)結(jié)構(gòu)課程設計報告書學校學號姓名指導老師劉勇課程設計的名稱： 學生成績管理1. 問題描述：學生成績管理是學校教務管理的重要組成部分，其處理信息量很大，該題目是對學生的成 績管理作一個簡單的模擬，其中學生信息包括：學號、姓名與成績。成績分為課程 1 成績、 課程 2 成績、課程 3成績和總成績。要求設計一個簡易的成績管理系統(tǒng)，輸入各門功課的 成績后能自動求出總成績，并通過菜單選擇操作方式完成下列功能： 登記學生成績； 查詢學生成績； 插入學生成績； 刪除學生成績； 按總成績降序排序。2. 基本要求：該題目涉及到單鏈表的各種操作，包括單鏈表的建立、結(jié)點的查找、插入、刪除等基本運 算。首先建立學生

2、成績單鏈表，鏈表中每個結(jié)點由 4 個域組成，分別為：學號、姓名、成 績、存放下一個結(jié)點地址的 next 域。然后將要求完成的四項功能寫成四個函數(shù)，登記學生 成績對應建立學生單鏈表的功能，后三個功能分別對應單鏈表的查詢、插入與刪除三大基 本操作。3. 算法思想：Creat() 函數(shù)算法思想：從 0 至 n 循環(huán)輸入 n 個同學的三科成績，并且計算總成績。 Inquiry() 函數(shù)算法思想：將學號與已輸入的所有學號做比較，一旦相同則輸出該學號信息， 否則顯示沒有該學生信息。Insert () 函數(shù)算法思想：生成一個新節(jié)點，然后將其接到原有鏈表尾部。Delete() 函數(shù)算法思想：通過 ID 找到該

3、節(jié)點，并刪去該節(jié)點。Sort( 函數(shù)算法思想：利用排序算法對每一個節(jié)點作比較并更換其在鏈表中的位置順序。4. 模塊劃分1) LinkList Creat(LinkList T,int n) 其功能是創(chuàng)造節(jié)點，錄入成績。2) void Inquiry(LinkList T) 其功能是查詢與已知 ID 一致的學生信息并展示出來。3) void Insert(LinkList T,int n) 其功能是添加若干個學生的成績信息。4) void Delete(LinkList T) 其功能是刪除若干個學生的成績信息。5) void Sort(LNode *p) 其功能是排序并展示若干個學生的成績信息。

4、5. 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)類型LNode定義如下：typedef struct LNode int ID; char name20;int score1;int score2;int score3;int total; struct LNode *next;LNode,*LinkList;6. 源程序：源代碼/main.c#include<stdio.h>#include<stdlib.h>typedefstruct LNodeintID;charname20;intscore1;intscore2;intscore3;inttotal;struct LNode *next;

5、LNode,*LinkList;LinkList Creat(LinkListT,int n);void Delete(LinkListT);void Inquiry(LinkListT);void Insert(LinkListT,int n);void Sort(LNode *p);void Insert(LinkList T,int n) int i;LNode *r=T,*p; while(r->next)!=NULL) r=r->next;for(i=0;i<n;i+)p=(LNode *)malloc(sizeof(LNode);printf("Plea

6、se enter scanf("%d",&p->ID);printf("Please enter scanf("%s",p->name);printf("Please enter scanf("%d",&p->score1); printf("Please enter scanf("%d",&p->score2); printf("Please enterthe student's the student's t

7、he student's the student's the student'sstudent ID:");name: ");score 1: ");score 2: ");score 3: ");scanf("%d",&p->score3);p->total=p->score1+p->score2+p->score3; printf("The total score is %dn",p->total); p->next=NULL;

8、r->next=p;r=p;printf("nInsert is complete!");void Inquiry(LinkList T) int id;printf("Pleaseenter the studentID you want to inquireabout:");scanf("%d",&id);LNode *p=T;p=p->next; while(p!=NULL)if(p->ID=id)printf("nThestudent scores information has beensu

9、ccessfullyinquired!n");printf("ID:%dnName: %snScore 1: %dnScore 2: %dnScore 3:%dn",p->ID,p->name,p->score1,p->score2,p->score3);break;else p=p->next;if(!p)printf("Sorry!Did not inquiry the student scores information!");void Delete(LinkList T)int id,flag=1;I

10、D you want to delete about: ");scores information has been successfullyprintf("Please enter the student scanf("%d",&id);LNode *p=T;/LNode *q; while(p->next)!=NULL)if(p->next->ID=id)/q=p->next; p->next=p->next->next;/ delete q;printf("nThe student del

11、eted!n");flag=0;break;elsep=p->next;if(flag)printf("Sorry!Did not delete the student scores information you want to delete!");void Sort(LNode *p)LNode *r,*qian,*hou; qian=p->next; hou=qian->next;while(hou) if(qian->total>=hou->total)qian=hou; hou=hou->next;/ifelse

12、r=p; while(r->next->total>hou->total)r=r->next; qian->next=hou->next; hou->next=r->next; r->next=hou; hou=qian->next;/elsep=p->next;int i=1;while(p)%dnScore 3:printf("Num: %dnID: %dnName: %snScore 1: %dnScore 2: %dntotal: %dnn",i,p->ID,p->name,p-&g

13、t;score1,p->score2,p->score3,p->total); p=p->next;i+;LinkList Creat(LinkList T,int n)LNode *p,*r;int i;T=(LNode *)malloc(sizeof(LNode);T->next=NULL;r=T;for(i=0;i<n;i+)p=(LNode *)malloc(sizeof(LNode);printf("Please enter scanf("%d",&p->ID);printf("Please e

14、nter scanf("%s",p->name);printf("Please enter scanf("%d",&p->score1); printf("Please enter scanf("%d",&p->score2); printf("Please enterthe student's the student's the student's the student's the student'sstudent ID:&qu

15、ot;);name: ");score 1: ");score 2: ");score 3: ");scanf("%d",&p->score3);p->total=p->score1+p->score2+p->score3; printf("The total score is %dn",p->total);p->next=NULL;r->next=p; r=p;return T;int main()LNode *p;int n;while(1) system

16、("cls");printf(" Student Scores Managementnn");printf("1-Enterthestudent'sscoren");printf("2-Querythestudent'sscoren");printf("3-Insertthestudent'sscoren");printf("4-Deletethestudent'sscoren");printf("5-Sortthe student&

17、#39;sscoren");printf("0-Exitsystemnn");printf("Please enter a number selection(0-5):"); int choice;scanf("%d",&choice);system("cls");if(choice=0)exit(0);switch(choice)case 1:printf("Pleaseenter the number of students you want toenter your student

18、's scores:”);seanf("%d",&n);p=Creat(p, n);pri ntf("nnPlease choice(1):");pri ntf("1-Esc");sca nf("%d",&n );if( n)break;case 2:printf("Pleaseenterthe numberquery your student's scores:");sca nf("%d",&n);int i=0;while(i<

19、; n)I nquiry(p);i+;prin tf("nPleaseen ter yourEsc");sca nf("%d", &n );break;case 3:pri ntf("Pleaseen terthe nu mberinsertyour student'sscores:");sca nf("%d",&n );I nsert(p ,n);prin tf("nPleaseen ter yourEsc");sca nf("%d", &n

20、 );break;case 4:pri ntf("Pleaseen terthe nu mberdelete your student'sscores:");sca nf("%d",&n);i=0;while(i< n)Delete(p);i+;prin tf("nPleaseen ter yourEsc");sca nf("%d", &n );break;case 5:Sort(p);prin tf("nPleaseen ter yourEsc");sca nf(

21、"%d", &n );break;default:break;return 0;7.測試情況：截圖：en teryourstudentsyou want tochoice(1):");pri ntf("1-studentsyou want tochoice(1):");pri ntf("1- studentsyou want tochoice(1):");pri ntf("1-choice(1):");pri ntf("1-S tudent Scozes X ana genie el t

22、1- Enter the student1 s ecote2- Query the student1 s score3- Insert the student1 e score4- Delete the student g scors5- Sort thes scareOExit systemPlease enter a nturibeT seiseti.onCO-5):Pl 匕dStJAlltel"iiuiiLtjr o£s ludfcjutsYou want tnqut 5 ludy： it s scores: 2Pleasewritertlies tudyi it，s

23、studentib：iPleaseenterthes tudei 11 snaLie:nlPl啓耳enterthes tudent ssore78Pleaseenterthestudent sscoreS9Pleaseenterthestudent'sscore34Tlie total score i,s 251 ,Pl easeenterthestudent'sstudentID:2J1 caseenterthestudent* snoire：n2Pl caseenterthestudent'sscore72Pleaseenterthestudent'ssco

24、re99Plcaocenterthestuctot' core76rho total ccoro is 253Please enter your choice(1):1-EscPlease ar-tei wanber of stadaits you vant to aurv zoui student s scoies: 1Please onter *he student II) you want to inquire about: 2The student scotgs ir.fcrnaxion has keen successfully LnqtiirGd!W： 2Nine： n2S

25、core 1: 7£Score 2: 99Score 3： 76PleasR atit.ft your GhricR'h 'l:PLeaseeitertheriunLer ofStiJClfeiitSyou vaiit to insert ycui smi9nt> s scores:Pi ”朋enterThsstudentJ sstudentD:2Pl mmenterthsgtiidpnt, gname:n3PLeaseentprthestudent'sscore1：68enterthestuccnt1 sscore一：89Pl 0133enterths

26、studentJ ssc'Dre3;90Ihe total s«oze is 247Insert is corlete!PLease enter vour chcice il):1-EscPlvase oritur the number jf students yuu 旳mt to delate zoax* student s scjrss; 1Pl ease Enter U.e s ：ude:it ID ycu vant to delete about; 2Thet scores infDrziatior: has been successfulIv deleted!Ple

27、ase enter vcur choice(l)：lEsc:247Jame ；lease enter your choice Cl):1-Escante ；nl;2514um： 18 9 06 8 9urn：D: 3n31;2:3:78陰S4程序輸出為:Num: 1ID: 1Name: n1Score 1: 78Score 2: 89Score 3: 84total: 251Num: 2ID: 3Name: n3Score 1: 68Score 2: 89Score 3: 90total: 247課程設計的名稱：停車場的管理1. 問題描述：設停車場內(nèi)只有一個可停放 n輛汽車的狹長通道，且只有一

28、個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先 到達的第一輛車停放在車場的最北端) ，若車場內(nèi)已停滿 n 輛汽車，則后來的汽車只能 在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入； 當停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛 車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場 時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。2. 基本要求：綜合利用棧和隊列模擬停車場管理，學習利用棧和隊列解決實際問題。 以棧模擬停車場，以隊列模擬車場外的便道，

29、按照從終端讀入的輸入數(shù)據(jù)序列進行模 擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照 號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到 達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場 內(nèi)停留的時間和應交納的費用(在便道上停留的時間不收費) 。棧以順序結(jié)構(gòu)實現(xiàn)，隊 列以鏈表實現(xiàn)。需另設一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序 存儲結(jié)構(gòu)實現(xiàn)。輸入數(shù)據(jù)按到達或離去的時刻有序。棧中每個元素表示一輛汽車，包 含兩個數(shù)據(jù)項：汽車的牌照號碼和進入停車場的時刻。3. 算法思想： 停車場運用棧的算法思想管

30、理車輛信息；便道運用隊列的算法思想管理等待進入停車場的 車輛信息；臨時停放讓路的車輛信息也用隊列算法思想管理。4. 模塊劃分：void PRINT(CarNode *p,int room 其功能為打印出場車的信息void Arrive(SeqStackCar *Enter,LinkQueueCar *W) 其功能為記錄進場車和等待進場車信息 void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) 其功能為記錄出場車 信息void List1(SeqStackCar *S) 其功能為顯示存車信息5. 數(shù)據(jù)結(jié)構(gòu)：( 1)數(shù)據(jù)

31、類型 Time 定義如下：typedefintstructtimehour;intmin;Time;(2)數(shù)據(jù)類型CarNode定義如下typedefstructnodechar num10;Time reach;Time leave;CarNode;( 3)數(shù)據(jù)類型 SeqStackCar 定義如下： typedef struct NODECarNode *stackMAX+1;int top;SeqStackCar;(4)數(shù)據(jù)類型 QueueNode定義如下：typedef struct carCarNode *data; struct car *next;QueueNode;( 5)數(shù)據(jù)

32、類型 LinkQueueCar 定義如下：typedef struct NodeQueueNode*head; QueueNode*rear;LinkQueueCar;6. 源程序：源代碼#include <stdio.h>#include <stdlib.h>#include <windows.h>#define price 0.15#define max 2/= int flag;/= typedef struct timeint hour;int min;Time;typedef struct nodelong num;Time reach;Time

33、leave;CarNode; /車輛信息結(jié)點typedef struct NODECarNode *stack10; int top;SeqStackCar; /模擬車場typedef struct carCarNode *data; struct car *next;QueueNode;typedef struct NodeQueueNode *head;QueueNode *rear;LinkQueueCar;/模擬通道/= void InitStack(SeqStackCar *s) /初始化棧int i; s->top=0;for(i=0;i<=max;i+) s->

34、stacks->top=NULL;void InitQueue(LinkQueueCar *Q) / 初始化便道Q- >head=(QueueNode *)malloc(sizeof(QueueNode); if(Q ->head!=NULL)Q->head->next=NULL;Q->rear=Q->head;return (1);elsereturn (- 1);void PRINT(CarNode *p,int room)/ 打印出場車的信息int A1,A2,B1,B2;printf("n 請輸入離開的時間 :/*:*/")

35、; scanf("%d:%d",&p ->leave.hour,&p ->leave.min); printf(" 離開車輛的車牌號為 :%ldn",p ->num);printf(" 其到達時間為 : %d:%dn",p ->reach.hour,p->reach.min);printf(" 離開時間為 : %d:%dn",p ->leave.hour,p->leave.min);A1=p ->reach.hour;A2=p ->reach.m

36、in;B1=p ->leave.hour;B2=p ->leave.min;printf(" 應交費用為 :%2.1f RMBn",(B1 -A1)*60+(B2 -A2)*price); free(p);/= =arrivevoid Arrive(SeqStackCar *Enter,LinkQueueCar *W)CarNode *p;QueueNode *t;p=(CarNode *)malloc(sizeof(CarNode);/flushall();printf("請輸入車牌號(例:12345):n");scanf("%l

37、d",&p ->num); if(Enter->top<max)/車輛未滿，車進場Enter->top+;printf(" 車輛請停在第 %d 位置 .n",Enter->top); printf(" 請輸入到達時間 :n");scanf("%d:%d",&p ->reach.hour,&p->reach.min);Enter->stackEnter->top=p;else/車輛已滿printf(" 該車須在便道等待！ .n")

38、;t=(QueueNode *)malloc(sizeof(QueueNode); t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;printf("Return main meun(1.return 0.quit)n");scanf("%d",&flag);switch(flag)case0:system("cls");printf("Thanks,Welcome to usenextn");exit(0);case1:syst

39、em("cls");/= =leavevoid Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) int i,room;CarNode *p,*t;QueueNode *q;if(Enter ->top>0)/盼斷車場內(nèi)是否有車while(1)/請輸入車在車場的printf(" 請輸入車在車場的位置 /1-%d/:n",Enter ->top);scanf("%d",&room);if(room>=1&&room<

40、;=Enter ->top)break;while(Enter ->top>room) /車輛離開Temp->top+;Temp->stackTemp->top=Enter ->stackEnter - >top;Enter->stackEnter ->top=NULL;Enter->top-;p=Enter ->stackEnter ->top;Enter->stackEnter ->top=NULL;Enter->top-; while(Temp - >top>=1)Enter-&g

41、t;top+;Enter ->stackEnter ->top=Temp ->stackTemp->top; Temp->stackTemp->top=NULL;Temp->top-;PRINT(p,room); /判斷通道上是否有車及車場是否已滿if(W ->head!=W ->rear)&&Enter ->top<max)/便道的車輛進場q=W - >head->next;t=q->data;Enter->top+;printf(" 便道的 %s 號車進入車場第 %d 位置

42、.n",t ->num,Enter ->top); printf(" 請輸入現(xiàn)在的時間 /*:*/:n");scanf("%d:%d",&t ->reach.hour,&t ->reach.min);W - >head->next=q ->next; if(q=W - >rear)W ->rear=W ->head;Enter->stackEnter ->top=t;free(q);elseprintf(" 便道；里沒有車 .n");el

43、seprintf(" 車場里沒有車 .n"); /車場里沒有車 printf("Return main meun(1.return 0.quit)n"); scanf("%d",&flag);switch(flag)case0:system("cls");printf("Thanks,Welcome to usenextn"); exit(0);case1:system("cls");/= =show void List1(SeqStackCar *S)/顯示存車信息

44、int i;if(S ->top>0) /判斷車場內(nèi)是否有車printf(" 車場 n");for(i=1;i<=S ->top;i+)printf(" 位置 到達時間 :%d:%dt 號碼 :%ldn",i,S ->stacki ->reach.hour,S- >stacki ->reach.min,S->stacki - >num);elseprintf(" 車場里沒有車 .n");printf("Return main meun(1.return 0.quit

45、)n"); scanf("%d",&flag);switch(flag)case0: system("cls"); printf("Thanks,Welcome to usenextn");exit(0);case1: system("cls");void List2(LinkQueueCar *W)QueueNode *p;p=W ->head->next;if(W ->head!=W ->rear)printf(" 等待車輛的號碼為 :");whil

46、e(p!=NULL)printf("%ldn",p ->data->num);p=p->next;elseprintf(" 便道里沒有車 .n");printf("Return main meun(1.return 0.quit)n");scanf("%d",&flag);switch(flag)case0: system("cls"); printf("Thanks,Welcome to usenextn"); exit(0);case1:syst

47、em("cls");void List(SeqStackCar S,LinkQueueCar W)int tag;printf("1. 車場 n");printf("2. 便道 n");printf("0. 返回 n");scanf("%d",&tag);system("cls");switch(tag)case0:break;case1:List1(&S);break;case2:List2(&W);break;/= =mainint main()S

48、eqStackCar Enter,Temp;LinkQueueCar Wait;int ch;InitStack(&Enter);InitStack(&Temp);InitQueue(&Wait);AA:printf(" 停車場 n");printf("n1. 車輛到達 n");printf("2. 車輛離開 n");printf("3. 列表顯示 n");printf("0. 退出系統(tǒng) n");scanf("%d",&flag);system

49、("cls");switch(flag)case0:printf("Thanks,Welcome to usenextn");return 0;case 1:Arrive(&Enter,& Wait);goto AA;case2:Leave(&En ter, &Temp,&Wait);goto AA;case3:List(E nter,Wait);goto AA;return 0;/=7.測試情況:截圖:I. -.r：J. 'i"iT；J.Ar- . L-_rPlease input the nu

50、iriber of car :tt.Thecaris in the N02 placePlease input the arrive tiiM of car: 9:14Return main meun(l.return 0. quit)lease input ths ear is in the 2 place: *lese input the time of leave:he number of car:2he csr arrived: &:34he ear left! 7:14Please pay the fee：6. 0 RMB there is n口 car in the roa

51、dReturn main msun(l. return 0, quit)Parking Lotplac: 1 ax'xiv-ed time:i5number:2pl qq ; 2 arrived time: 9; L4nuinber: 1Return main 陰皿(1 return 0 quit)程序輸出為:The System of parking1. car arrive2. car leave3. show car0.quit systemParking Lotplace:1 arrived time:5:45place:2 arrived time:9:14number:2n

52、umber:1Return main meun(1.return 0.quit)課程設計的名稱： 二叉樹的基本操作的實現(xiàn)1. 問題描述：? 在主程序中編寫一個簡單的菜單，將有關(guān)二叉樹的操作? 建立一棵二叉樹的存儲結(jié)構(gòu)? 遍歷一棵二叉樹(包括層次遍歷)? 統(tǒng)計二叉樹葉子結(jié)點的個數(shù)? 求二叉樹的深度? 子樹交換2. 基本要求：? 建立一棵二叉樹的存儲結(jié)構(gòu)? 遍歷一棵二叉樹(包括層次遍歷)? 統(tǒng)計二叉樹葉子結(jié)點的個數(shù)? 求二叉樹的深度? 子樹交換3. 算法思想：CreatBiTree() 運用遞歸創(chuàng)造二叉樹的每一個節(jié)點；Exchange() 通過遞歸交換左右子樹；Depth() 通過遞歸計算二叉樹的

53、深度。InorderTraverse() 遞歸中序遍歷二叉樹。PreOrderTraverse() 遞歸先續(xù)遍歷二叉樹。PostOrderTraverse() 遞歸后續(xù)遍歷二叉樹。4. 模塊劃分：1) BiTree CreatBiTree(BiTree T) 其功能是創(chuàng)造一顆二叉樹；2) int Depth(BiTree T) 其功能是計算一顆二叉樹的深度3) void Exchange(BiTree T) 其功能是交換左右子樹4) void InorderTraverse(BiTree T) 其功能是中序遍歷5) void PreOrderTraverse(BiTree T) 其功能是前序遍

54、歷6) void PostOrderTraverse(BiTree T) 其功能是后序遍歷5. 數(shù)據(jù)結(jié)構(gòu)：(1)數(shù)據(jù)類型 BiTNode 定義如下： typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;6. 源程序： 源代碼/main.c#include <stdio.h>#include <stdlib.h> #include <malloc.h> typedef struct BiTNodechar data;struct BiTNode *lch

55、ild,*rchild; BiTNode,*BiTree;void LevelOrder(BiTree T);void InorderTraverse(BiTree T); BiTree CreatBiTree(BiTree T);int Depth(BiTree T);void Exchange(BiTree T);int NodeCount(BiTree Ti);void PostOrderTraverse(BiTree T); void PreOrderTraverse(BiTree T);BiTree CreatBiTree(BiTree T)char ch;scanf("%

56、c",&ch);if(ch='#')T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode); if(!T)exit(0);printf("error");T->data=ch;T->lchild=CreatBiTree(T->lchild);T->rchild=CreatBiTree(T->rchild);return T;int Depth(BiTree T)int LNum,RNum;if(T=NULL)return 0;elseLNum=Depth(T->lchi

57、ld);RNum=Depth(T->rchild);if(LNum>RNum)return (LNum+1);elsereturn (RNum+1);void Exchange(BiTree T)BiTNode* p;if(T) p=T->lchild; T->lchild=T->rchild;T->rchild=p;Exchange(T->lchild);Exchange(T->rchild); void InorderTraverse(BiTree T)if(T)InorderTraverse(T->lchild);printf(&qu

58、ot;%c ",T->data);InorderTraverse(T->rchild);void LevelOrder(BiTree T)BiTree Queue20,b;int front,rear; front=rear=0;if(T)printf("LevelOrder:");Queuerear+=T; while(front!=rear) b=Queuefront+; printf("%2c",b->data); if(b->lchild!=NULL)Queuerear+=b->lchild; if(b->rchild!=N