数据结构课程设计任务书结构设计.doc

数据结构课程设计任务书数据结构课程设计任务书结构设计一、设计目的数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读数据结构课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在2周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题选题说明：本次任务共提供若干个不同难易程度的题目，其中前面5个为必做题，满分100分（系统功能完善、人机交互界面简单、直观、便捷，否则逐项减分）；后面为选做题，题目难度层度不等，完成部分选做题目者可以适当给予加分；同学们在选题时，要结合个人实际情况，确保及格，力争多做。1、 单位员工通讯录管理系统（线性表的应用）问题描述为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号、及电子邮箱。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。实现提示可以采用单链表的存储结构，如可定义如下的存储结构：typedef struct /*员工通讯信息的结构类型定义*/ char num5; /*员工编号*/ char name10; /*员工姓名*/ char phone15; /*办公室电话号码*/char call15; /*手机号码*/char mail25; /*邮箱*/DataType;/*通讯录单链表的结点类型*/typedef struct node DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ListNode,*LinkList;typedef struct /*员工通讯信息的结构类型定义*/ char num5; /*员工编号*/ char name10; /*员工姓名*/ char phone15; /*办公室电话号码*/char call15; /*手机号码*/char mail25; /*邮箱*/DataType;/*通讯录单链表的结点类型*/typedef struct node DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ListNode,*LinkList;#includeiostreamusing namespace std;struct contaxt char name10; char sex5; char Adrre50; char Class20; char Mobi20; char qq10;struct contaxt *next; ;/声明函数typedef struct contaxt CONT;CONT *InsertCon(CONT *head);/插入联系人的基本信息CONT *AddContaxt(int n); /初始化联系人的基本信息CONT *FindCon(CONT *head); /查找联系人的基本信息CONT *AmendMessage(CONT *head);/修改联系人的基本信息CONT *DeleteMessage(CONT *head);/删除联系人的基本信息void showmessage(CONT *head); /显示联系人的基本信息int menu(CONT *head); /主菜单CONT *saveFileCONT(CONT *head );/保存联系人的基本信息CONT *readFileCONT(CONT *head);/读取联系人的基本信息int choose;/系统入口void main()CONT *head;head = NULL;menu(head);/系统主菜单int menu(CONT *head)cout 请选择操作菜单! endl ;docout -欢迎进入员工管理系统- -操作菜单-; cout - *1 添加联系人信息 * endl *2 插入联系人信息* endl *3 查找联系人信息* endl *4 修改联系人信息 * endl *5 删除联系人信息 * endl *6 显示联系人信息 * endl *7 退出本系统 * endl *8 保存文件 * endl *9 读取文件 * endl - endl; cout 请选择操作菜单! choose;if(choose != 1& choose != 2 & choose != 3 & choose !=4 & choose != 5 & choose !=6 & choose !=7&choose != 8)cout 输入错误：endl;elseswitch(choose)case 1:int n;dofflush(stdin);cout n;while(n = 0);head = AddContaxt(n);break;case 2:system(CLS);head = InsertCon(head);break;case 3:head = FindCon(head);break;case 6:system(CLS); showmessage(head);break;case 7:exit(0);break;case 4:system(CLS);AmendMessage(head);break;case 5:system(CLS);DeleteMessage(head);break;case 8:system(CLS);head = saveFileCONT(head );break;case 9:/head = readFileCONT(head);default:system(CLS);cout 你输入错误,请重新选择！ endl;break;while(choose != 1& choose != 2 & choose != 3 & choose !=4 & choose != 5 & choose !=6 & choose !=7);return choose;/初始化联系人的基本信息CONT *AddContaxt(int n)CONT *p,*q,*head;int i;system(CLS);p = (CONT *)malloc(sizeof(CONT);cout 开始添加联系人信息： endl;cout p-name;cout p-sex ;cout p-Class ;cout p-Adrre ;cout p-Mobi ;cout p-qq ;head = p;for(i = 2;i next = q ; p = q; system(CLS); cout 总共需要输入 n 个联系人的信息,现在你已输入 i-1 个联系人信息. endl 请继续输入第i 个人的信息！ endl; cout p-name; cout p-sex ; cout p-Class ; cout p-Adrre ; cout p-Mobi ; cout p-qq ;p-next = NULL;return head;/按照不同的要求插入联系人的基本信息CONT *InsertCon(CONT *head)CONT *pc,*p,*q;int choose ;char name10;if(head =NULL)cout 还没有添加任何联系人，请先添加联系人！ endl;return head;pc = (CONT *)malloc(sizeof(CONT);cout 请依次输入被插入人的信息：姓名 /性别/班级/住址/手机号/qq号 pc-name pc-sex pc-Class pc-Adrre pc-Mobi pc-qq ;pc -next = NULL;cout 请选择自己喜欢的插入方式： endl 1 插入在自己喜欢的人之前 endl 2 插入在最后 endl 3 插入在开头 choose;switch(choose)case 1:cout name ;if(strcmp(head-name ,name)=0)pc-next = head;head = pc;return head;else q = head;p = head-next ;while(strcmp(p-name,name)!=0 & p-next !=NULL)q = p;p = p-next ;if(strcmp(p-name ,name)=0)pc-next = p ;q = pc;return head;elsep-next = pc;return head;break;case 2:/cout name ;p = head;while(p-next != NULL)p = p-next ;p-next = pc;return head;break;case 3:/cout name ;pc-next = head;head = pc;return head;break;default :couterror endl;break;while(choose!=1 &choose != 2 & choose != 3);/查找联系人的基本信息CONT *FindCon(CONT *head)system(CLS);char na20;CONT *p,*q;if(head = NULL)cout 没有任何信息可查找，请先添加信息！ endl;return head;cout 请您输入要查找人的姓名： na;p = head;while(p!= NULL)if(strcmp(p-name ,na)=0)q = p;cout 找到联系人,信息如下! endl;cout 姓名: name 性别: sex Class 住址: Adrre 手机号: Mobi qq号: qq next ; return head;/修改联系人的基本信息CONT *AmendMessage(CONT *head)CONT *p;char nam10;char sex5;char Adrre50;char Class20;char Mobi20;char qq10;if(head = NULL)cout 没有任何信息，请返回添加信息！ endl;return head;else p = head;cout nam;while(p != NULL & p-name != nam)if(strcmp(p-name ,nam)=0)strcpy(p-name ,nam);int choose;docout 请选择要修改哪一项的信息！ endl;cout 1 修改性别 2 修改班别 3 修改地址 4 修改手机号码 5 修改qq号 choose;switch(choose)case 1:cout sex;strcpy(p-sex , sex);cout 修改成功! endl;system(CLS);return head;break;case 2:cout Class;strcpy(p-Class ,Class);system(CLS);cout 修改成功! endl;return head;break;case 3:cout Adrre;strcpy(p-Adrre ,Adrre);system(CLS);cout 修改成功! endl;return head;break;case 4:cout Mobi;strcpy(p-Mobi ,Mobi);system(CLS);cout 修改成功! endl;return head;break;case 5:cout qq;strcpy(p-qq ,qq);system(CLS);cout 修改成功! endl;return head;break;default:cout 输入错误，重新选择！ next != NULL & p-name != nam)p = p-next ;elsecout 输入名字错误，请重新选择4修改！ endl;return head;/return head;/删除联系人的基本信息CONT *DeleteMessage(CONT *head)CONT *p,*q,*t;char name20;char elem10;cout name;if(head = NULL)cout 没有任何信息可删除，请添加信息！name,name)=0 )t = head;head = head-next ;return head;else p = head-next ;q = head;while(p !=NULL & p-name != name)q = p;p = p-next ;if(strcmp(p-name ,name)=0)q-next = p-next ;free(p); /t = p;else cout 表中无该元素！ name ; free(t); return head;/保存文件CONT *saveFileCONT(CONT *head )char *fileName;FILE *fp;CONT *p;p = (CONT *)malloc(sizeof(CONT);if(p=NULL)cout 分配内存失败 endl; / exit(0);if(head =NULL)cout 没有任何信息，请先添加信息！ endl;return head;elsep = head;fileName = (char *)malloc(sizeof(char);cout 请输入文件名： fileName;fileName = strcat(fileName,.txt);if( (fp = fopen(fileName,a) = NULL)cout cant open file name,p-sex,p-Class,p-Adrre,p-Mobi,p-qq );fprintf(fp, 姓名:);fprintf(fp, p-name );fprintf(fp, 性别：);fprintf(fp, p-sex);fprintf(fp, 班别：);fprintf(fp, p-Class);fprintf(fp, 地址：);fprintf(fp, p-Adrre);fprintf(fp, 手机号：);fprintf(fp, p-Mobi);fprintf(fp, qq号：);fprintf(fp, p-qq);fprintf(fp,n);cout endl; cout -; cout 姓名: name 性别: sex 班别： Class 住址: Adrre 手机号: Mobi qq号: qq endl; cout next ;while(p!=NULL);fclose(fp);return head;/读取文件内容CONT *readFileCONT(CONT *head)char *fileName;CONT *p;FILE *fp;fileName = (char *)malloc(sizeof(char);cout fileName;fileName = strcat(fileName,.txt);fp = fopen(fileName,r);if(fp = NULL)cout 文件没有任何信息,请先输入信息！ endl;else while(!feof(fp)p = (CONT *)malloc(sizeof(CONT); if(p = NULL) cout 分配内存失败！name ); fscanf(fp,p-sex ); fscanf(fp,p-Class ); fscanf(fp,p-Adrre ); fscanf(fp,p-Mobi ); fscanf(fp,p-qq ); cout -; cout 姓名: name 性别: sex 班别： Class 住址: Adrre 手机号: Mobi qq号: qq endl; cout next = head; head = p; p = p-next ;fclose(fp);cout 读取信息成功！ endl;fclose(fp);return head;/显示信息void showmessage(CONT *head) CONT *p; int i=0; if(head = NULL ) cout 没有任何信息可输出，请添加信息!！ endl; else p = head; cout *联系表如下*; do i+; cout -; cout i 姓名: name 性别: sex 班别： Class 住址: Adrre 手机号: Mobi qq号: qq endl; cout next ;while(p!=NULL); cout *联系表*; cout endl; 2、停车场管理（栈和队列的应用）问题描述设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次有北向南排列（大门在最南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。实现提示以栈模拟停车场，以队列模拟车场外的便道。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停车不收费）。栈以顺序存储结构实现，队列以链表结构实现。#include using namespace std;const int size = 5; /停车场停放车上限int enterTop;int tmpTop; /我搞不懂 top 为何不能放入private中struct shortcutLinked /便道停车char carNumber10; /车牌号shortcutLinked *next;class Parkingpublic: void setParking();void enterPot(Parking enter); /进入停车场 , 停车场可放车数 栈1void showEnterPot(Parking enter); /查看停车场void exitPot(Parking exit); /离开停车场void shortcut(); /便道 链表void showShortcut(); /查看便道void exitShortcut(); /离开便道void charge(int ihour, int iminute, int ohour,int ominute); / 收费private:int inhour, inminute; /就默认可停一天int outhour, outminute; /离开时间int port, order; /停车场车位号, 便道排号char carNumberPot10; /车牌号shortcutLinked *front, *rear;void Parking:setParking()order = 0;enterTop = -1;tmpTop = -1;shortcutLinked *s;s = new shortcutLinked;s-next = NULL;front = rear = s;void Parking:enterPot(Parking enter) if (enterTopsize-2)cout停车场已满, 车辆需放在便道上!n;shortcut();elsecout车位号 enterTop+2 尚空, 可停放!n;coutenter+enterTop.carNumberPot;coutenterenterTop.inhourenterenterTop.inminute;cout车牌号: enterenterTop.carNumberPot 已停放进enterTop+1号车位!n; void Parking:showEnterPot(Parking enter)if (enterTop = -1)cout停车场内无车!n;elsefor (int i = 0;ienterTop+1;i+)couti+1号车位停放车牌为 enteri.carNumberPotnn;cout停车场剩余车位:size - enterTop -1endl; void Parking:shortcut()cout你的车将停放在便道第+order号车位上n;shortcutLinked *p;p = new shortcutLinked;coutp-carNumber;p-next = NULL;rear-next = p;rear = p;cout车牌号: carNumber 已经进入便道第order号车位上n;cout请等待!;void Parking:showShortcut()if (front = rear)cout停车场内无车!n;elsecoutnext != NULL)cout便道上, 第+i号车位为: next-carNumbernext;void Parking:charge(int ihour, int iminute, int ohour,int ominute)cout停车场按 0.5元/10min 收费, 不足10min, 收1元n;int min = ominute-iminute; int hour = ohour-ihour;int time; / 时间double fee; /车费if (hour = 0) & (min 10)cout车费为:1元n;elseif (hour 0)cout车辆已停放超过一天, 需特殊处理!n;else if (min0)time = (hour-1)*60-min;else time = hour*60+min;fee = (time/10)*0.5;cout停车时间为: time分钟n;cout车费为:fee元nn; void Parking:exitPot(Parking enter)coutcar;int i = enterTop;int j = 0; /判断有无此车while(i != -1)if (strcmp(car, enteri.carNumberPot) = 0)j = 1;break;i-;if (j=1)cout此车进入停车场的时间为今日 enteri.inhour:enteri.inminuteendl;coutouthouroutminute;charge(enteri.inhour, enteri.inminute, outhour, outminute);cout车号:enteri.carNumberPot于今日 outhour:outminutei; enterTop-)strcpy(tmp+tmpTop.carNumberPot,enterenterTop.carNumberPot); enterTop-; /已清理此车for (tmpTop; tmpTop-1; tmpTop-) /回到停车场strcpy(enter+enterTop.carNumberPot, tmptmpTop.carNumberPot);if (front != rear)cout便道上的占第一车位号的next-carNumber进入停车场!n;coutenter+enterTop.inhourenterenterTop.inminute;cout车牌号: next-carNumbernext-carNumber);shortcutLinked *p;p = front-next;front = front-next;/delete p;order-;elsecout停车场内没有此车!n;void Parking:exitShortcut()if (front = rear)cout便道上无车!n;elsecoutcar;int j=0; /判断有无此车shortcutLinked *p;p = front;while(p-next != NULL)if (strcmp(car, p-next-carNumber) = 0)j =1;break;p = p-next;if (j = 1)shortcutLinked *q;q = p-next;cout车牌号: carNumbernext = p-next-next;delete q;order-;else cout便道上没有这辆车!n;void main()Parking Carsize;Carsize.setParking();while(1)coutn- -欢迎来到停车场!- -nn;cout1, 将车停放在停车场n;cout2, 将车驶离停车场n;cout3, 将车驶离便道n;cout4, 查看停车场情况n;cout5, 查看便道情况n;cout6, 关闭程序nn;