数据结构课程设计报告

数 据 结 构课程设计报告书学校 青岛科技大学 学号 姓名 指导老师 刘勇 课程设计的名称：学生成绩管理1. 问题描述：学生成绩管理是学校教务管理的重要组成部分，其处理信息量很大，该题目是对学生的成绩管理作一个简单的模拟，其中学生信息包括：学号、姓名与成绩。成绩分为课程1成绩、课程2成绩、课程3成绩和总成绩。要求设计一个简易的成绩管理系统，输入各门功课的成绩后能自动求出总成绩，并通过菜单选择操作方式完成下列功能： 登记学生成绩； 查询学生成绩； 插入学生成绩； 删除学生成绩； 按总成绩降序排序。2. 基本要求：该题目涉及到单链表的各种操作，包括单链表的建立、结点的查找、插入、删除等基本运算。首先建立学生成绩单链表，链表中每个结点由4个域组成，分别为：学号、姓名、成绩、存放下一个结点地址的next域。然后将要求完成的四项功能写成四个函数，登记学生成绩对应建立学生单链表的功能，后三个功能分别对应单链表的查询、插入与删除三大基本操作。3. 算法思想：Creat()函数算法思想：从0至n循环输入n个同学的三科成绩，并且计算总成绩。Inquiry()函数算法思想：将学号与已输入的所有学号做比较，一旦相同则输出该学号信息，否则显示没有该学生信息。Insert ()函数算法思想：生成一个新节点，然后将其接到原有链表尾部。Delete()函数算法思想：通过ID找到该节点，并删去该节点。Sort(函数算法思想：利用排序算法对每一个节点作比较并更换其在链表中的位置顺序。4. 模块划分（1）LinkList Creat(LinkList T,int n)其功能是创造节点，录入成绩。（2）void Inquiry(LinkList T)其功能是查询与已知ID一致的学生信息并展示出来。（3）void Insert(LinkList T,int n) 其功能是添加若干个学生的成绩信息。（4）void Delete(LinkList T) 其功能是删除若干个学生的成绩信息。（5）void Sort(LNode *p) 其功能是排序并展示若干个学生的成绩信息。5. 数据结构：数据类型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 #include typedef struct LNode int ID; char name20; int score1; int score2; int score3; int total; struct LNode *next;LNode,*LinkList;LinkList Creat(LinkList T,int n);void Delete(LinkList T);void Inquiry(LinkList T);void Insert(LinkList T,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;iID); printf(Please enter the students name: ); scanf(%s,p-name); printf(Please enter the students score 1: ); scanf(%d,&p-score1); printf(Please enter the students score 2: ); scanf(%d,&p-score2); printf(Please enter the students 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; printf(nInsert is complete!);void Inquiry(LinkList T) int id; printf(Please enter the student ID you want to inquire about: ); scanf(%d,&id); LNode *p=T; p=p-next; while(p!=NULL) if(p-ID=id) printf(nThe student scores information has been successfully inquired!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; printf(Please enter the student ID you want to delete about: ); 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 scores information has been successfully deleted!n); flag=0; break; else p=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; /if else r=p; while(r-next-totalhou-total) r=r-next; qian-next=hou-next; hou-next=r-next; r-next=hou; hou=qian-next; /else p=p-next; int i=1; while(p) printf(Num: %dnID: %dnName: %snScore 1: %dnScore 2: %dnScore 3: %dntotal: %dnn,i,p-ID,p-name,p-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;iID); printf(Please enter the students name: ); scanf(%s,p-name); printf(Please enter the students score 1: ); scanf(%d,&p-score1); printf(Please enter the students score 2: ); scanf(%d,&p-score2); printf(Please enter the students 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(cls); printf( Student Scores Managementnn); printf( 1-Enter the students scoren); printf( 2-Query the students scoren); printf( 3-Insert the students scoren); printf( 4-Delete the students scoren); printf( 5-Sort the students scoren); printf( 0-Exit systemnn); 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(Please enter the number of students you want to enter your students scores: );scanf(%d,&n); p=Creat(p,n);printf(nnPlease enter your choice(1):);printf(1-Esc);scanf(%d,&n);if(n)break; case 2:printf(Please enter the number of students you want to query your students scores: ); scanf(%d,&n); int i=0;while(in)Inquiry(p);i+; printf(nPlease enter your choice(1):);printf(1-Esc);scanf(%d,&n);break; case 3:printf(Please enter the number of students you want to insert your students scores: ); scanf(%d,&n);Insert(p,n); printf(nPlease enter your choice(1):);printf(1-Esc);scanf(%d,&n);break; case 4:printf(Please enter the number of students you want to delete your students scores: ); scanf(%d,&n); i=0;while(in)Delete(p);i+; printf(nPlease enter your choice(1):);printf(1-Esc);scanf(%d,&n);break; case 5:Sort(p); printf(nPlease enter your choice(1):);printf(1-Esc);scanf(%d,&n);break; default:break; return 0;7. 测试情况：截图： 程序输出为：Num: 1ID: 1Name: n1Score 1: 78Score 2: 89Score 3: 84total: 251Num: 2ID: 3Name: n3Score 1: 68Score 2: 89Score 3: 90total: 247课程设计的名称：停车场的管理1. 问题描述：设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。2. 基本要求：综合利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。3. 算法思想：停车场运用栈的算法思想管理车辆信息；便道运用队列的算法思想管理等待进入停车场的车辆信息；临时停放让路的车辆信息也用队列算法思想管理。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. 数据结构：（1）数据类型Time定义如下：typedef struct time int hour; int min;Time; （2）数据类型CarNode定义如下：typedef struct node char num10; Time reach; Time leave;CarNode; （3）数据类型SeqStackCar定义如下：typedef struct NODE CarNode *stackMAX+1; int top;SeqStackCar; （4）数据类型QueueNode定义如下：typedef struct car CarNode *data; struct car *next;QueueNode;（5）数据类型LinkQueueCar定义如下：typedef struct Node QueueNode *head; QueueNode *rear;LinkQueueCar; 6. 源程序：源代码#include #include #include #define price 0.15#define max 2/=int flag;/=typedef struct time int hour; int min;Time;typedef struct node long num; Time reach; Time leave;CarNode; /车辆信息结点typedef struct NODE CarNode *stack10; int top;SeqStackCar; /模拟车场typedef struct car CarNode *data; struct car *next;QueueNode;typedef struct Node QueueNode *head; QueueNode *rear;LinkQueueCar; /模拟通道/=void InitStack(SeqStackCar *s) /初始化栈 int i; s-top=0; for(i=0;istacks-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); else return (-1);void PRINT(CarNode *p,int room)/打印出场车的信息 int A1,A2,B1,B2; printf(n请输入离开的时间:/*:*/); 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.min; 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(%ld,&p-num); if(Enter-toptop+; printf(车辆请停在第%d位置.n,Enter-top); printf(请输入到达时间:n); scanf(%d:%d,&p-reach.hour,&p-reach.min); Enter-stackEnter-top=p; else /车辆已满 printf(该车须在便道等待！.n); 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) case 0: system(cls); printf(Thanks,Welcome to use nextn); exit(0); case 1: system(cls); /=leavevoid Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) int i,room; CarNode *p,*t; QueueNode *q; if(Enter-top0) /盼断车场内是否有车 while(1) printf(请输入车在车场的位置/1-%d/:n,Enter-top); /请输入车在车场的位置 scanf(%d,&room); if(room=1&roomtop) break; while(Enter-toproom) /车辆离开 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-top+; Enter-stackEnter-top=Temp-stackTemp-top; Temp-stackTemp-top=NULL; Temp-top-; PRINT(p,room); /判断通道上是否有车及车场是否已满 if(W-head!=W-rear)&Enter-tophead-next; t=q-data; Enter-top+; printf(便道的%s号车进入车场第%d位置.n,t-num,Enter-top); printf(请输入现在的时间/*:*/: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); else printf(便道；里没有车.n); else printf(车场里没有车.n); /车场里没有车 printf(Return main meun(1.return 0.quit)n); scanf(%d,&flag); switch(flag) case 0: system(cls); printf(Thanks,Welcome to use nextn); exit(0); case 1: system(cls); /=showvoid List1(SeqStackCar *S) /显示存车信息 int i; if(S-top0) /判断车场内是否有车 printf(车场n); for(i=1;itop;i+) printf(位置%d到达时间:%d:%dt号码:%ldn,i,S-stacki-reach.hour,S-stacki-reach.min,S-stacki-num); else printf(车场里没有车.n); printf(Return main meun(1.return 0.quit)n); scanf(%d,&flag); switch(flag) case 0: system(cls); printf(Thanks,Welcome to use nextn); exit(0); case 1: system(cls); void List2(LinkQueueCar *W) QueueNode *p; p=W-head-next; if(W-head!=W-rear) printf(等待车辆的号码为:); while(p!=NULL) printf(%ldn,p-data-num); p=p-next; else printf(便道里没有车.n); printf(Return main meun(1.return 0.quit)n); scanf(%d,&flag); switch(flag) case 0: system(cls); printf(Thanks,Welcome to use nextn); exit(0); case 1: system(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) case 0: break; case 1: List1(&S); break; case 2: List2(&W); break; /=mainint main() SeqStackCar 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.退出系统n); scanf(%d,&flag); system(cls); switch(flag) case 0: printf(Thanks,Welcome to use nextn); return 0; case 1: Arrive(&Enter,&Wait); goto AA; case 2: Leave(&Enter,&Temp,&Wait); goto AA; case 3: List(Enter,Wait); goto AA; return 0;/=7 测试情况：截图： 程序输出为：The System of parking1.car arrive2.car leave3.show car0.quit systemParking Lotplace:1 arrived time:5:45 number:2place:2 arrived time:9:14 number:1Return main meun(1.return 0.quit)课程设计的名称：二叉树的基本操作的实现1. 问题描述： 在主程序中编写一个简单的菜单，将有关二叉树的操作 建立一棵二叉树的存储结构 遍历一棵二叉树（包括层次遍历） 统计二叉树叶子结点的个数 求二叉树的深度 子树交换2. 基本要求： 建立一棵二叉树的存储结构 遍历一棵二叉树（包括层次遍历） 统计二叉树叶子结点的个数 求二叉树的深度 子树交换3. 算法思想：CreatBiTree()运用递归创造二叉树的每一个节点；Exchange()通过递归交换左右子树；Depth()通过递归计算二叉树的深度。InorderTraverse()递归中序遍历二叉树。PreOrderTraverse()递归先续遍历二叉树。PostOrderTraverse()递归后续遍历二叉树。4. 模块划分：（1）BiTree CreatBiTree(BiTree T)其功能是创造一颗二叉树；（2）int Depth(BiTree T)其功能是计算一颗二叉树的深度（3）void Exchange(BiTree T) 其功能是交换左右子树（4）void InorderTraverse(BiTree T) 其功能是中序遍历（5）void PreOrderTraverse(BiTree T) 其功能是前序遍历（6）void PostOrderTraverse(BiTree T) 其功能是后序遍历5. 数据结构：（1）数据类型BiTNode定义如下：typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;6. 源程序：源代码/main.c#include #include #include typedef struct BiTNode char data; struct BiTNode *lchild,*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(%c,&ch); if(ch=#) T=NULL; else T=(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)