数据结构课程设计报告.docx

数据结构课程设计报告专业：网络工程班级： 学号： 姓名： 指导老师: 日期： 年 月 日目 录一、 设计题目二、 需求分析三、 概要设计四、 详细设计五、 调试分析与结果六、 源 代 码、停车场管理系统一、设计题目设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。二、 需求分析1根据车辆到达停车场离开停车场所停留的时间差进行计费2当有车辆从停车场离开时，等待的车辆按顺序进入停车场存放。实现停车场的调度功能。3程序执行的命令为：汽车到达汽车离开显示停车场情况显示候车室情况。4（用顺序栈S来表示停车场，另一个栈S1用来表示临时便道）Tmax 作为车辆能够容纳的车辆数，no作为车牌号，Price 0.2 单位时间价格。5用户根据系统规定并提示要输出的有关内容，车辆进出时间由收费人员来确定。该程序是简单的用于运用栈与队列的基本知识的工具，其特点是“先进后出、后进先出”。三、 概要设计1设定储存类型：typedef structSqstack；typedef structCarType;用来存储车辆的相关信息。2基本操作：ADT stack InitStack(Sqstack &S) 操作结果：构造一个顺序空栈S。StackFull(Sqstack S) 操作结果：判断栈是否为满。StackEmpty(Sqstack S)操作结果：判断栈是否为空。Push(Sqstack &S,CarType e) 操作结果：在栈S的栈顶插入新的元素e。Pop(Sqstack &S,CarType &e)操作结果：删除S的栈顶元素，并用e返回其值。Length(Sqstack S) 操作结果： 求栈长。DisStack(Sqstack S) 操作结果：显示栈中信息。 ADT stack主函数3流程图：到达停车场离开停车场InitStack InitQueuePushDeQueuePopEnQueuePush离开停车场到达停车场主函数四、 详细设计1.数据存储结构设计采用链式线性表示2.函数功能（1）、int InitStack(Sqstack &S) /初始化停车场S.base=(CarType *)malloc(Tmax*sizeof(CarType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=Tmax;return OK;功能：构造一个栈，并置为空栈。（2）、int Push(Sqstack &S,CarType e) /汽车到达停车场if(StackFull(S)return ERROR;(*S.top).no=e.no;(*S.top).time.year=e.time.year;(*S.top).time.mouth=e.time.mouth;(*S.top).time.day=e.time.day;(*S.top).time.hour=e.time.hour;(*S.top).time.min=e.time.min;S.top+;return OK;功能：定义入栈函数Push。（3）、int Pop(Sqstack &S,CarType &e) /汽车离开停车场if(StackEmpty(S)return ERROR;S.top-;e.no=(*S.top).no;e.time.year=(*S.top).time.year;e.time.mouth=(*S.top).time.mouth;e.time.day=(*S.top).time.day;e.time.hour=(*S.top).time.hour;e.time.min=(*S.top).time.min;return OK;功能：定义出栈函数Pop。（4）、int InitQueue(LinkQueue &Q) /初始化便道Q.front=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.rear=Q.front;Q.front-next=NULL;return OK;功能：构造一个队列，并置为空队列。（5）、int EnQueue(LinkQueue &Q,int e) /汽车进入便道 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-no=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;功能：定义入队函数EnQueue。（6）、int DeQueue(LinkQueue &Q,int &e) /汽车离开便道if(Q.front=Q.rear) /队空return ERROR;QueuePtr p;p=Q.front-next;e=p-no;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;功能：定义出队函数DeQueue。（7）、void DisStack(Sqstack S) /显示停车场中的车辆信息 if(StackEmpty(S)cout停车场中暂无车辆endl;else for(int i=0;iLength(S);i+)couti+1 S.basei.no S.basei.time.year-S.basei.time.mouth-S.basei.time.day-S.basei.time.hour-S.basei.time.minnext;int i=0;if(!p)cout候车室中暂无车辆endl;elsewhile(p)i+;couti nonext;coutendl;功能：定义候车室显示函数五、调试分析与测试结果函数界面：停车场为空：汽车到达停车场：停车场未满，候车室暂时没有汽车：停车场已满，候车室有车：查询的汽车不存在：汽车离开停车场，在候车室中的汽车进入停车场，候车室无车：六、源代码#include#include#define Tmax 3 /栈的最大长度#define Price 0.2 /单位时间价格#define OK 1#define ERROR 0#define OVERFLOW 0typedef structint year;int mouth;int day;int hour;int min;Time;/车的相关信息/typedef structint no; /车牌号Time time; /进入或离开时间CarType;/栈结构定义/typedef structCarType *base;CarType *top;int stacksize;Sqstack;int InitStack(Sqstack &S) /构造顺序栈栈S.base=(CarType *)malloc(Tmax*sizeof(CarType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=Tmax;return OK;int StackFull(Sqstack S) /判断栈是否为满if(S.top-S.base=S.stacksize)return OK;elsereturn ERROR;int StackEmpty(Sqstack S) /判断栈是否为空if(S.top=S.base)return OK;elsereturn ERROR;int Push(Sqstack &S,CarType e) /入栈操作if(StackFull(S)return ERROR;(*S.top).no=e.no;(*S.top).time.year=e.time.year;(*S.top).time.mouth=e.time.mouth;(*S.top).time.day=e.time.day;(*S.top).time.hour=e.time.hour;(*S.top).time.min=e.time.min;S.top+;return OK;int Pop(Sqstack &S,CarType &e) /出栈操作if(StackEmpty(S)return ERROR;S.top-;e.no=(*S.top).no;e.time.year=(*S.top).time.year;e.time.mouth=(*S.top).time.mouth;e.time.day=(*S.top).time.day;e.time.hour=(*S.top).time.hour;e.time.min=(*S.top).time.min;return OK;int Length(Sqstack S) /求栈长return (S.top-S.base);void DisStack1(Sqstack S,int no)for(int i=0;i=Length(S)cout无该车辆信息endl;elsecouti+1 S.basei.no S.basei.time.year-S.basei.time.mouth-S.basei.time.day-S.basei.time.hour-S.basei.time.minendl;void DisStack(Sqstack S) /显示栈中信息if(StackEmpty(S)cout停车场中暂无车辆endl;elsefor(int i=0;iLength(S);i+)couti+1 S.basei.no S.basei.time.year-S.basei.time.mouth-S.basei.time.day-S.basei.time.hour-S.basei.time.minnext=NULL;return OK;int QueueEmpty(LinkQueue Q) /判断队列是否为空if(Q.front=Q.rear)return OK;elsereturn ERROR;int DestoryQueue(LinkQueue &Q) /销毁队列while(Q.front) Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;int LengthQueue(LinkQueue Q) /求队列长度int i=0;QueuePtr p;p=Q.front-next;while(p)i+;p=p-next;return i;int EnQueue(LinkQueue &Q,int e) /入队操作QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-no=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,int &e) /出队操作if(Q.front=Q.rear) /队空return ERROR;QueuePtr p;p=Q.front-next;e=p-no;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;void DisQueue1(LinkQueue Q,int no) /显示队列相关信息QueuePtr p;p=Q.front-next;int i=0;while(p&no!=p-no)i+;p=p-next;if(p)couti+1 noendl;elsecout无该车辆信息endl;coutnext;int i=0;if(!p)cout候车室中暂无车辆endl;elsewhile(p)i+;couti nonext;coutendl;void main()int mark,i,j,k;CarType car,car1;Sqstack S,S1;LinkQueue Q;InitStack(S);InitStack(S1);InitQueue(Q);cout1：汽车到达 2：汽车离开 3：显示停车场情况 4：显示候车室情况 endl;for(;)cout请输入指令：mark;switch(mark)case 1:cout依次输入汽车车号、到达时间：car.nocar.time.yearcar.time.mouthcar.time.daycar.time.hourcar.time.min;if(!StackFull(S) /若停车场不满，则车进入停车场 Push(S,car);cout在停车场中的位置：S.top-S.baseendl;DisStack1(S,car.no);else /停车场满，则车进入候车室 EnQueue(Q,car.no);cout在候车室的的位置：LengthQueue(Q)endl;DisQueue1(Q,car.no);break;case 2:cout输入离开汽车的车牌号：car.no; k=S.top-S.base;for(i=0;i=S.top-S.base)cout未找到该车牌号的汽车endl;elsecout输入离去时间：car.time.yearcar.time.mincar.time.daycar.time.hourcar.time.min;for(j=i;jk-1;j+) Pop(S,car1); /将S中的数据进入栈S1中 Push(S1,car1);Pop(S,car1);int t=(car.time.year-car1.time.year)*365*24*60+(car.time.mouth-car1.time.mouth)*30*24*60+(car.time.day-car1.time.day)*24*60+(car.time.hour-car1.time.hour)*60+(car.time.min-car1.time.min);cout汽车停留时间为：tendl;cout费用为：t*Priceendl;while(!StackEmpty(S1) Pop(S1,car1);/将S1中的数据再次进入栈S中Push(S,car1);if(!QueueEmpty(Q)/如候车室中有车，则第一辆进入停车场 DeQueue(Q,car1.no);car.no=car1.no;Push(S,car); break;case 3:DisStack(S);break;case 4:DisQueue(Q);break;default:cout输入有误endl; 、文章编辑一、 设计题目输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；二、 需求分析功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；三、 概要设计1 文章输入：包含中英文，空格和各种字符。用write()函数来实现。2 文章读取：包含中英文，空格，数字和各种字符。用read()函数来实现3 文章的统计：包含中英文字母、空格数、数字和文章总字数的统计。用cal()函数来实现。4 统计特定字符：用calchar()函数实现。5 文章字符删除：包含中英文字母、空格数、数字，用del()函数实现。四、 设计函数功能（1）、void read(char *c) / 定义文章读取函数（2）void write(char*c) /定义文章输入函数（3）void calchar(char *c) /定义统计函数（4） void del(char *c) /定义删除函数五、调试分析与测试结果 主界面：文章读取：统计字符：统计特定字符：删除字符：六、源代码#include #include #includeusing namespace std;void read(char *c)cout你输入的字符串为：endl;ifstream is(content.txt);while(1)is.getline(c,80);if(is.eof()break;coutcendl;is.close();void write(char*c)ofstream os(content.txt);int count;cout请输入要储存的行数count;cout请输入要储存的字符串endl;cin.getline(c,80);for(int i=1;i=count;i+)cin.getline(c,80);oscendl;os.close();void cal(char *c)ifstream is(content.txt);int spacecount=0,blackcount=0,count=0,countnum=0;char *s;while(1)is.getline(c,80);s=c;if(is.eof()break;while(*s!=0)if(*s=32)spacecount+;else if(*s=97|*s=65)blackcount+;else if(*s=48)countnum+;count+;s+;cout数字总数：countnumendl;cout空格数：spacecountendl;cout字母个数：blackcountendl;cout字符总数：countendl;is.close();void calchar(char *c)ifstream is(content.txt);char d;cout请输入要统计的字符d;int count=0;char *s;while(1)is.getline(c,80);s=c;if(is.eof()break;while(*s!=0)if(*s=d)count+;s+;coutd字符总数：countendl;is.close();void del(char *c)char t20;bool flag=false;cout请输入要删除的字符串t;ifstream is(content.txt);ofstream os(tem.txt);while(1)is.getline(c,80);if(is.eof()break;for(;)int i=0,j=0;while(istrlen(c)&jstrlen(t)-1)flag=true;i=i-j;do ci=ci+j;i+; while(ci+j!=0);ci=0;elsebreak;oscendl;if(flag=false)cout字符串不存在endl;elsecout操作成功endl;is.close();os.close();ifstream inf(tem.txt);ofstream outf(content.txt);for (;)inf.getline(c,80);if(inf.eof()break;outfcendl;void main() char c100;int i;for (;)cout 请选择服务endl;cout1.输入n2.读取n3.统计n4.统计特定字符n5.删除字符串i;if(i=1)write(c);else if(i=2)read(c);else if(i=3)cal(c);else if(i=4)calchar(c);else if(i=5)del(c);elsecout输入有误，请重新输入endl; 、宿舍管理系统一、 设计题目为宿舍管理人员编写一个宿舍管理查询软件二、 需求分析（1）采用交互工作方式（2）可以增加、删除、修改信息（3）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(选择、快速排序、堆排序等任选一种)(4) 查询 : a.按姓名查询 ;b.按学号查询 ;c按房号查询(5) 打印任一查询结果（可以连续操作）要求：上述查询功能中，学号、房号用折半查找，姓名查找用哈希查找。三、 概要设计1数据存储结构typedef char keytype;typedef int keytype1;typedef struct Nodekeytype name10;keytype1 id;keytype1 roomno;Sqlist;2.本系统的功能有：用户登录（分学生和管理员两个级别），用Administrate()函数实现管理员登陆；用Student()函数实现学生登陆；Quit()函数实现退出系统。四、 详细设计Add() /管理员添加学生信息Delete() /管理员删除显示信息Idinquiry() /查询信息Inquiry() /查询学生信息Modify() /管理员修改学生信息Order() /管理员排序（冒泡排序法）Skip() /浏览学生信息各函数功能的结构层次可以用下面的图简明表示：学生信息链表的建立 插入学生信息按学号查询管理员登陆 学生 登陆查询学生信息主菜单模块按姓名查询 用户登陆删除学生信息 修 改姓 名修改学生信息修 改学 号输出所有学生信息退出管理系统1.登陆主要进行打开主系统的操作，只有管理员才能登陆进行工本操作，学生只能进行非工本操作。2.学生信息链表的建立该部分通过尾插法建立一个新的链表来存储信息，包括学生的姓名学号宿舍号等。3.插入学生信息该部分构建了Add()函数，并利用for循环和while语句来实现信息的插入操作。4.查询学生信息该部分构建了Inquiry ()函数，并利用switch语句实现选择按何种查询操作。5.删除显示信息该部分构建了Delete()函数，文件打开的方式进行删除，用while循环诸葛删除。6.修改学生信息该部分构建了Modify()函数，通过while语句和if查找要删除的学生信息。五、 调试分析与结果1.登陆主界面并添加信息2浏览信息3.删除信息 4.修改信息 修改成功： 5.信息查询6.排序7.切换用户就会返回主登陆界面了8.学生登陆系统只能看不能修改六、源代码远#include#include#include#define M 100static int m=0;typedef char keytype;typedef int keytype1;typedef struct Nodekeytype name10;keytype1 id;keytype1 roomno;Sqlist;Sqlist StuM;void Login();void Administrate();void Student();void Add();void Skip();void Delete();void Modify();void Inquiry();void Idinquiry();void Noinquiry();void Nameinquiry();void Order();void Idorder();void Noorder();void Quit();int c;/主函数void main()Login();/登录界面void Login()cout * endl;cout * * endl;cout * 宿舍管理系统 * endl;cout * * endl;cout * endl;cout 请选择登陆界面 endl;cout 1.Administrate 2.Student 3.Quit c;while(c!=1&c!=2&c!=3)cout输入错误，重新输入c;switch(c)case 1:Administrate();break;case 2:Student();break;case 3:Quit();break;default:break;/管理员登录void Administrate()int a;cout 请选择一下操作 endl;cout 1.添加信息 endl;cout 2.浏览信息 endl;cout 3.删除信息 endl;cout 4.修改信息 endl;cout 5.信息查询 endl;cout 6.信息排序 endl;cout 7.退出 endl;cout 8.切换用户 a;while(a!=1&a!=2&a!=3&a!=4&a!=5&a!=6&a!=7&a!=8)cout输入错误，重新输入a;switch(a)case 1:Add();break;case 2:Skip();break;case 3:Delete();break;case 4:Modify();break;case 5:Inquiry();break;case 6:Order();break;case 7:Quit();break;case 8:Login();break;default:break;/学生登录界面void Student()int a;cout 请选择一下操作 endl;cout 1.浏览信息 endl;cout 2.信息查询 endl;cout 3.信息排序 endl;cout 4.退出 endl;cout 5.切换用户 a;while(a!=1&a!=2&a!=3&a!=4&a!=5)cout输入错误，重新输入a;switch(a)case 1:Skip();break;case 2:Inquiry();break;case 3:Order();break;case 4:Quit();break;case 5:Login();break;default:break;/添加信息void Add()fstream iofile(student.dat,ios:in|ios:out|ios:binary|ios:app);if(!iofile)cout打开失败endl;return;static int i;char ch;m+;for(i=m-1;im;i+)cout请输入学生的信息:endl; cout请输入学号Stui.id;cout请输入姓名Stui.name; cout请输入房间号Stui.roomno; iofile.write(char*)&Stui,sizeof(Stui);iofile.close();cout是否继续添加(继续输入y，否则输入n)ch;while(ch!=Y&ch!=y&ch!=N&ch!=n) cout输入错误，重新输入ch;if(ch=y|ch=Y)Add();if(ch=N|ch=n)cout添加结束endl;fstream o(data.dat,ios:out|ios:binary);if(!o)cout打开失败endl;return; o.write(char*)&m,sizeof(m);o.close();if(c=1)Administrate();if(c=2)Student();/浏览信息void Skip()fstream ifile(data.dat,ios:in|ios:binary);if(!ifile)cout打开失败endl;return;ifile.read(char*)&m,sizeof(m);ifile.close();fstream iofile(student.dat,ios:out|ios:in|ios:binary);if(!iofile)cout打开失败endl;return;for(int i=0;im;i+)iofile.read(char*)&Stui,sizeof(Stui);cout学号:Stui.id 姓名:Stui.name 房间号:Stui.roomnoendl;iofile.close();if(c=1)Administrate();return;if(c=2)Student();/删除信息void Delete()fstream ifile(data.dat,ios:in|ios:binary);if(!ifile)cout打开失败endl;return;ifile.read(char*)&m,sizeof(m);ifile.close();fstream iofile(student.dat,ios:out|ios:in|ios:binary);if(!iofile)cout打开失败endl;return;for(int i=0;im;i+)iofile.read(char*)&Stui,sizeof(Stui);int b;int mid;int low=0;int high=m-1;cout请输入要删除的学号b;while(low=high)mid=(low+high)/2;if(Stumid.id=b)cout此人信息如下：endl;cout学号:Stumid.id 姓名:Stumid.name 房间号:Stumid.roomnoendl;if(mid=m)m-;fstream o(data.dat,ios:out|ios:binary);if(!o)cout打开失败endl; return; o.write(char*)&m,sizeof(m); o.close();iofile.close();goto step;elsefor(int i=mid;im-1;i+)iofile.read(char*)&Stui+1,sizeof(Stui+1);Stui=Stui+1;iofile.seekp(i*sizeof(Stui),ios:beg);iofile.write(char*)&Stui,sizeof(Stui);m-;fstream o(data.dat,ios:out|ios:binary);if(!o)cout打开失败b) high=mid-1;