数据结构课程设计

淮 海 工 学 院 计算机工程学院

课程设计报告

设计名称： 数据结构课程设计 选题名称： 姓 名： 学 号： 专业班级： 计算机科学与技术 系 （院）： 计算机工程学院 设计时间： 2014.12.22~2015.1.4 设计地点： 计算机实验室、教室 指导教师评语： 签名： 年 月 日 教育资料 成绩： .

1．课程设计目的 1、训练学生灵活应用所学数据结构知识，完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3、提高综合运用所学的理论知识和方法分析和解决问题的能力； 4、训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 2．课程设计任务与要求： 任务 根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 设计题目从任务书所列选题表中选取，每班每题不得超过2人。 学生自选课题。 学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可运行的程序； 5、每位同学需提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）； 6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 教育资料

. 3．课程设计说明书 一 需求分析 停车场管理系统 （1）根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时计费。 （2）当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放，实现停车场的调度功能。 （3）用要求以顺序栈模拟停车场，以链队列模拟便道。 （4） 从终端读入汽车到达或离去的数据，每组数据包括三项： ①是“到达”还是“离去”； ②汽车牌照号码； ③“到达”或“离去”的时刻。 （5）每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。 二 概要设计 停车场管理系统 1、系统用到的抽象数据类型定义： typedef struct node { char num[10]; //车牌号码 Time reach; //到站时间 Time leave; //离开时间 }CarNode; typedef struct time 教育资料 . { int hour; int min; }Time; typedef struct NODE { CarNode *stack[MAX+1]; //栈用顺序表示 int top; }SeqStackCar; typedef struct car { CarNode *data; // 便道上的车用链表表示 struct car *next; }QueueNode; typedef struct Node { QueueNode *head; // 设置头指针、尾指针。 QueueNode *rear; }LinkQueueCar; 2、 系统中的子程序和功能说明： （1）void InitStack(SeqStackCar *); //车辆节点进栈 当栈未满时，就把到达的车辆进栈。 （2）int InitQueue(LinkQueueCar *); //车辆节点进队列 当栈满了时，车辆就进入便道上的队列中 （3）int Arrival(SeqStackCar *,LinkQueueCar *); //车辆到达登记 车辆到达时，先登记车辆车牌号码。然后再判断停车场有没有停满，没停满就进栈，停满了就停在便道上，即进队列。。 （4） void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); //车辆离开处理 通过输入离开车辆的位置处理，然后调用PRINT(CarNode *p,int room);函数进行收费。。然后再判断便道上有没有车，如果有，就把便道上的车进停车场内。 （5）void List(SeqStackCar,LinkQueueCar); //显示车场内和便道上的车辆情况 用个switch();函数选择显示车场内或是便道上的车辆情况。 包括对下面两个子函数的调用: void List1(SeqStackCar *S); void List2(LinkQueueCar *W); //分别为显示车场和便道上的车辆情况 （6）void PRINT(CarNode *p,int room); // 车辆离开是的收费 这个函数由车辆离开的函数调用，以分钟计时算费，但只能计算当天之内的费用，如果第二天的话会导致计费为负或减少。即只能当天停，当天开走。 教育资料

. 3、 系统程序功能结构图 停车场管理系统 车辆到达 车辆离开 列表显示 车牌号码 到达时间 离开时间 收费情况 车场信息 便道信息 三 详细设计 停车场管理系统 算法的设计思想及流程图 主要模块算法描述： 本程序最主要的算法就是车辆到达登记的和车辆离开的。 1车辆到达：int Arrival(SeqStackCar *Enter,LinkQueueCar *W) ○首先定义一个栈和队列的结构体指针为：*p , *t , 然后申请一个车辆信息的内存空间，并把它赋给栈指针.车辆到达时就输入车牌号，并通过if(Enter->toptop>0) 确保栈不空，然后用个while(1) 确保输入的车辆离开位置的合法性。如果不和法，显示输入有误，要重新输入。 通过while(Enter->top>room) 判断离开车辆的位置，如果是中间位置，就要再用一个栈前面临时开出来的车，等要开出的车开出后，再把临时栈的车看进 车场内，并要调用PRINT(p,room); 这个函数计算显示费用.然后还要用 if((W->head!=W->rear)&&Enter->topnum); if(Enter->toptop++; printf(\"\\n车辆在车场第%d位置.\ printf(\"\\n车辆到达时间:\"); 教育资料

. scanf(\"%d:%d\ Enter->stack[Enter->top]=p; return(1); } else { printf(\"\\n该车须在便道等待!有车位时进入车场\"); t=(QueueNode *)malloc(sizeof(QueueNode)); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); } } 图1.2源代码： void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W)//车辆的离开 { int room; CarNode *p,*t; QueueNode *q; if(Enter->top>0) // 判断车场是否为空 { while(1) { printf(\"\\n请输入车在车场的位置/1--%d/：\ scanf(\"%d\ if(room>=1&&room<=Enter->top) break; else printf(\"\\n 输入有误,请重输: \"); } while(Enter->top>room) // 把要删除的车辆的前面的车开出来，进临时栈。 { Temp->top++; Temp->stack[Temp->top]=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; } p=Enter->stack[Enter->top]; // 把要删除的车辆节点赋给p。 Enter->stack[Enter->top]=NULL; Enter->top--; while(Temp->top>=1) // 再把临时栈里德车辆进停车场 教育资料

. { Enter->top++; Enter->stack[Enter->top]=Temp->stack[Temp->top]; Temp->stack[Temp->top]=NULL; Temp->top--; } PRINT(p,room); // 调用计费函数计费。。 if((W->head!=W->rear)&&Enter->tophead->next; t=q->data; Enter->top++; printf(\"\\n便道的%s号车进入车场第%d位置.\ printf(\"\\n请输入%s号车进入车场的时间:\ scanf(\"%d:%d\ W->head->next=q->next; if(q==W->rear) W->rear=W->head; Enter->stack[Enter->top]=t; free(q); } else printf(\"\\n便道里没有车.\\n\"); } else printf(\"\\n车场里没有车.\"); } 显示车场里的车辆情况源程序： void List1(SeqStackCar *S) //显示车场里的车辆情况 { int i; if(S->top>0) { printf(\"\\n车场:\"); 教育资料

. printf(\"\\n 位置 到达时间 车牌号\\n\"); for(i=1;i<=S->top;i++) { printf(\" %d \ printf(\" %d:%d \ puts(S->stack[i]->num); } } else printf(\"\\n车场里没有车\"); } 显示便道上的车辆情况源代码： void List2(LinkQueueCar *W) //显示便道上的车辆情况 { QueueNode *p; int i; p=W->head->next; if(W->head!=W->rear) { printf(\"\\n等待车辆的号码为:\"); for(i=1; (p!=NULL); i++) { printf(\"\\n第 %d 车辆.\ puts(p->data->num); p=p->next ; } } else printf(\"\\n便道里没有车.\"); printf(\"\\n\"); } 教育资料

. 开始 初始化两个栈Enter和Temp及一个队列Wait。 进入主菜单 车到达 车离开 列表显示 退出 是 车场是否为空 否 车场内信息 便道车信息 退出列表显示 Room前车辆进临时栈 对room计费 否 判便道是否有车 是 判断栈是否为满 否 元素进栈Enter 是 元素进队列Wait 便道车进车场 栈Enter元素出栈 队列Wait中元素出队 结束 队列中元素进栈 图1.3：停车场管理系统主流程图. 教育资料

. 四 程序设计与调试分析 停车场管理系统 测试数据： 每个测试的数据都是以字符串的形式存储的，输入数据是严格按照提示的信息执行。 调试遇到的问题与解决方法： 在调试的过程中，输出员工信息的时候格式老是错位，调试了很多次才得以调整；在从文件中读出数据时老是显示不出数据，最后才发现原来是忘了写输出语句，但是在添加上去之后，能输出信息却有很多的乱码，仔细检查了一遍又一遍后终于发现了，原来是自己定义的指针在循环的过程中次序混乱了。在调试的过程中我还发现我的提示语句不多，导致让别人不知道下一步要做些什么，所以就适当的添加了一些提示的信息。 五 用户手册 停车场管理系统 【 使用说明 】 （1）进入程序的界面，出现命令的帮助信息(停车场的最大容量为三辆车，多了则进入便道中等待其他车离开车场)。 （2）输入1：车辆到达登记；输入2：车辆离开登记；输入3：车辆列表显示；输入4：退出系统（首先得进行车辆登记，否则停车场里没有车） （3）车辆登记时，到达的时间与离开的时间一定要严格按照时间的模式，如：8:00 （4）显示车辆列表时，有相应的信息提示，看自己的意愿执行程序。 （5）在觉得操作完毕时输入4：退出系统。 【 程序中的头文件 】 #include #include #include #define MAX 3 // 停车场最大容量为3辆，便于观察 #define price 0.05 教育资料

. 六 测试成果 停车场管理系统 教育资料

. 教育资料 . 教育资料

. 教育资料

. 教育资料 . 一 需求分析 简单的员工管理系统 （1）该程序可用于对企业员工情况基本信息的存储、更新、查询、输出等操作,以实现对企业员工的管理。 （2） 其中更新功能包括：添加信息、删除信息、修改信息、可根据需要添加一个或多个员工信息,也可对个别员工信息进行适当的删除或修改。以便随时更新员工信息。 （3） 程序中设计的查询功能可根据需要从若干数据中查询某个员工信息，并且可根据两种不同的方法查询：按工作证号查询和按姓名查询。以满足不同的需要。 二 概要设计 简单的员工管理系统 1、 系统用到的抽象数据类型定义： struct wokers //定义结构体 { }; typedef struct node { struct wokers data; struct node *next;//建立一个链表 char num[10]; //员工工号 char name[15]; //员工姓名 char sex[15]; //员工性别 char birthday[15];//员工出生年月 char degree[10]; //员工学历 char position[10];//员工职位 char salary[10]; //员工工资 char address[20];//员工地址 char telephone[20];//员工电话 }Node; 2、 系统中的子程序和功能说明： 教育资料

. （1）菜单模块：显示员工管理系统的主菜单，供用户选择所需的功能，通过主函数来实现。 （2）添加模块：添加员工的工号、姓名以及其它的一些职工的相关信息，通过自己定义的void Add(Node *woker)函数来实现。 （3）修改模块：可以修改需要修改的员工的相关信息，通过自己定义的void change(Node *woker)函数 来实现。 （4）浏览模块：浏览所有员工的相关信息，通过自己定义的void Disp(Node *woker)函数来实现。 （5）删除模块：删除需要删除的员工的所有信息，通过自己定义的void delet(Node *woker)函数来实现。 （6）查询模块：可以按员工号和员工姓名来查询职工的相关信息，通过自己定义的void search(Node *woker)函数来实现。 （7）保存模块：将内存中员工的信息输出到磁盘文件中，可以通过自己定义的void save(Node *woker)函数来实现。 （8）读取模块：将磁盘文件中员工的信息输出到屏幕中，可以通过自己定义的void load(Node *woker)函数来实现。 3、 系统程序功能结构图 教育资料 简单员工管理系统 添加员工信息 修改 员工信息 浏览员工信息 保存员工信息 删除员工信息 读取员工信息 查找员工信息 按员工工号查找 按员工姓名查找 . 三 详细设计 算法的设计思想及流程图 简单的员工管理系统 主要模块算法描述 本程序的主要算法就是对于员工信息的添加、浏览、查找、删除模块 为了方便起见本程序定义的结构体中，员工的信息都是以字符串来存储的。 ①在对员工信息的添加中，本程序利用的是链表将每个员工的信息都顺序的录入链表中。 ②同样的利用此方法浏览员工的信息，利用while（）循环，直到指针p到链表的末尾。 ③在查找模块利用函数void search()实现，里面包括两个子模块，第一个是以员工的工号来查找员工的相应的信息，第二个则是以员工的姓名来查找员工的相应的信息。 ④删除模块则是利用void delet()函数来实现。输入想删除的员工的工号，然后把相应的员工的信息都删除。 教育资料

. 开始 Y Y 链表为空 Y 输入要删除的员工的工号 N 找到要删除的员工与否 Y 删除相应的员工信息 结束 图2.2：删除模块流程图 图2.1：查找模块流程图 教育资料

. 图2.1源代码： void search(Node *woker)//按条件查找员工信息 { Node *p; int sel,flag2; char find[20]; p=woker->next; if(!woker->next)//若链表为空 { printf(\"没有资料可以查找！\\n\"); return; } printf(\"\\\*************************************\\n\"); printf(\"\\\*\1：按员工工号查找\ *\\n\"); printf(\"\\\*\2：按员工姓名查找\ *\\n\"); printf(\"\\\*************************************\\n\"); scanf(\"%d\ if(sel==1) { flag2=0; printf(\"请输入你要查找的员工工号：\"); scanf(\"%s\ while(p) { if(strcmp(p->data.num,find)==0) { flag2=1; printf(\"工号 姓名 性别 生日 学历 职位 工资 住址 电话\\n\"); } if(flag2==1) printf(\"%-9s%-11s%-8s%-8s%-10s%-9s%-9s%-7s%-7s\\na.birthday,p->data.degree,p->data.position,p->data.salary,p->data.address,p->data.telephone); p=p->next; } if(flag2==0) printf(\"所要查找的员工不存在！\\n\"); 教育资料

. } else if(sel==2) { flag2=0; printf(\"请输入你要查找的员工姓名：\"); scanf(\"%s\ while(p) { if(strcmp(p->data.name,find)==0) { flag2=1; printf(\"工号 姓名 性别 生日 学历 职位 工资 住址 电话\\n\"); if(flag2==1) printf(\"%-9s%-11s%-8s%-8s%-10s%-9s%-9s%-7s%-7s\\nhday,p->data.degree,p->data.position,p->data.salary,p->data.address,p->data.telephone); p=p->next; } } if(flag2==0) printf(\"所要查找的员工不存在！\\n\"); } } 图2.2源代码： void delet(Node *woker)//删除员工信息 { Node *p,*r,*s; char find[10]; if(!woker->next) { printf(\"没有资料可以显示！\\n\"); return; } printf(\"请输入您要删除的员工工号！\\n\"); scanf(\"%s\ p=woker->next; while(p!=NULL) { if(strcmp(p->data.num,find)==0)//如果找到的话返回的是符合要求 break; p=p->next; 教育资料

. } } if(!p) printf(\"找不到您要删除的员工工号！\\n\"); else { r=woker; while(r->next!=p) r=r->next; s=r->next; r->next=r->next->next; } 员工信息保存源代码： void save(Node *woker)//将员工信息保存到文件 { int n; Node *p; FILE *fp;//指向文件的指针 printf(\"需要保存吗？（1-保存 0-不保存）\"); scanf(\"%d\ if(n) { if(woker->next==NULL) printf(\"无记录\"); else p=woker->next; if((fp=fopen(\"员工管理系统.txt\打开文件，并判断打开是否正常 printf(\"can not open file\\n\");//打开文件失败 while(p!=NULL) { fprintf(fp,\"%-9s%-11s%-8s%-8s%-10s%-9s%-9s%-7s%-7s\\n\>data.birthday,p->data.degree,p->data.position,p->data.salary,p->data.address,p->data.telephone); p=p->next; } fclose(fp);//关闭文件 } } 教育资料

教育资料 . .

教育资料