第一篇:C语言与数据结构课程设计报告要求
C语言与数据结构课程设计报告
学 号 2014014083 姓 名 汪明 课程设计题目 通讯录的制作
2016 年 1
月
目 录 需求分析 1.1 功能与数据需求 1.1.1 题目要求的功能 1.1.2 扩展功能 1.2 界面需求 1.3 开发环境与运行需求 2 概要设计 2.1主要数据结构 2.2程序总体结构 2.3各模块函数说明 3 详细设计
3.1算法分析与设计 3.2主要程序段设计 4 测试 5 使用说明
5.1应用程序功能的详细说明 5.2应用程序运行环境要求 5.5输入数据类型、格式和内容限制 6 总结提高
6.1课程设计总结
6.2开发中遇到的问题和解决方法 6.3 对自己完成课设完成情况的评价
6.4《C语言与数据结构课程设计》课程的意见与建议 附录:程序源代码
需求分析 1.1 功能与数据需求
1)输入信息--enter();2)显示信息---display();3)查找以姓名作为关键字---search();4)删除信息---delete();5)存盘---save();6)装入---load();
1.2 界面需求
1)每条信息至包含 :姓名(NAME)街道(STREET)城市(CITY)邮编(EIP)国家(STATE)几项;电话号码(TEL); 2)作为一个完整的系统,应具有友好的界面和较强的容错能力; 3)需要链表实现;
4)上机能正常运行。
1.3 开发环境
开发环境:
测试系统:Windows7,开发工具:Dev-C++ 概要设计 2.1主要数据结构
//构建链表的结构体 typedef struct CLUB { char NAME[20];//姓名 char STREET[20];//街道 char CITY[20];//城市 char STATE[20];//国家 char PHONE[20];//电话号码 char EIP[10];//邮编 struct CLUB *next;}CLUB;CLUB *headLink;
2.2程序总体结构 //主要函数
void Enter(CLUB *t);//录入 void Search(void);//查找
void Display(void);//输出输入的所有信息 void Delete(void);//删除信息 void Save(void);//保存
void Load(void);//从文件中的内容 //界面函数
void Menu(void);//显示菜单
2.2各模块函数说明
void CreateHeadLink(void);//创建 void Load(void);//从文件中的内容 void Menu(void);//显示菜单
void InsertOneNode(CLUB *t);//增加新结点
CLUB *MallocNode(void);//申请一个新结点,并将其初始化 void Enter(CLUB *t);//输入
void InsertOneNode(CLUB *t);//在链表的结尾处增加一个结点 void Search(void);//查找
void DesplayOneNode(CLUB *t);//输出一个结点的信息 void Display(void);//输出输入的所有信息 void Delete(void);//删除信息
void ChangeInforByName(void);//修改信息 void Save(void);//保存 详细设计
3.1算法分析与设计
Enter函数:从键盘中获得数据,通过scanf将各数据放入对应的链表中 Display函数:将链表中的数据输出 3.2主要程序段设计测试 使用说明
5.1应用程序功能的详细说明
先输入联系人的基本信息,可以显示录入的所有联系人的信息,可以将联系人的信息保存到CLUB.txt,当第二次运行时可以直接从CLUB.txt文件中调用 5.2应用程序运行环境要求 5.5输入数据类型、格式和内容限制 6 总结提高
6.1课程设计总结
6.2开发中遇到的问题和解决方法 6.3 对自己课程设计完成情况的评价 附录:程序源代码
#include
char STREET[20];//街道
char CITY[20];//城市
char STATE[20];//国家
char PHONE[20];//电话号码
char EIP[10];//邮编 struct CLUB *next;}CLUB;CLUB *headLink;//链表表头指针 void CreateHeadLink(void);//创建 void Load(void);//从文件中的内容 void Menu(void);//显示菜单
void InsertOneNode(CLUB *t);//增加新结点
CLUB *MallocNode(void);//申请一个新结点,并将其初始化 void Enter(CLUB *t);//输入
void InsertOneNode(CLUB *t);//在链表的结尾处增加一个结点 void Search(void);//查找
void DesplayOneNode(CLUB *t);//输出一个结点的信息 void Display(void);//输出输入的所有信息 void Delete(void);//删除信息
void ChangeInforByName(void);//修改信息 void Save(void);//保存
int choose;//用于接收用户的选择 //主函数 int main(){ int j;system(“color 3E”);printf(“nnnnnnnnnn”);printf(“ttt %c ”,1);printf(“欢迎进入通信录!nn”);printf(“正在进入,请等候”);for(j=0;j<6;j++){ Sleep(300);printf(“.”);} system(“cls”);
CreateHeadLink();Menu();} //函数功能:从文件中读信息 void Load(void){ FILE *fp;CLUB *p;p=(CLUB *)malloc(sizeof(CLUB));headLink=p;p->next=NULL;fp=fopen(“CLUB.txt”,“r”);if(!fp){ printf(“文件不存在n”);return;} p=MallocNode();while(fscanf(fp,“%s%s%s%s%s%sn”,p->NAME,p->STREET,p-> CITY,p->STATE,p->PHONE ,p->EIP)>0){ InsertOneNode(p);p=MallocNode();} fclose(fp);}
//函数功能:显示菜单,根据用户的输入完成相应的功能 void Menu(void){ CLUB *p;printf(“nt|***********欢迎使用通信录信息管理系统****************|n”);printf(“t提示:为保证您的操作得到保存,请按正常顺序退出系统^_^n”);printf(“tt+------------主菜单---------------+n”);printf(“tt+ [1]******显示电话簿信息 +n”);printf(“tt+ [2]按姓名查找电话簿信息 +n”);printf(“tt+ [3]******录入电话簿信息 +n”);printf(“tt+ [4]******删除电话簿信息 +n”);printf(“tt+ [5]按姓名修改电话簿信息 +n”);printf(“tt+ [6]**保存所有电话簿信息 +n”);printf(“tt+ [7]装入文件中电话簿信息 +n”);printf(“tt+ [0]****************退出 +nn”);printf(“请输入指令:”);scanf(“%d”,&choose);//取得用户的选择
switch(choose){
case 1: Display();//显示所有电话簿的信息 Sleep(2000);system(“cls”);break;case 2: Search();//按姓名查找信息 Sleep(2000);system(“cls”);break;case 3: //录入新信息
p=MallocNode();//先申请一个新结点 Enter(p);//要求用户输入信息到新结点中 InsertOneNode(p);//将新结点加到链表中 Sleep(2000);system(“cls”);break;case 4: Delete();//删除电话簿信息
Sleep(2000);system(“cls”);break;case 5:
ChangeInforByName();//按姓名修改电话簿信息 Sleep(2000);system(“cls”);break;case 6: Save();//保存 Sleep(2000);system(“cls”);break;case 7:
Load();//装入 Display();Sleep(2000);system(“cls”);break;case 0: Save();//保存数据后再退出 free(headLink);exit(1);break;default:
} break;} Menu();//递归调用
// 函数功能:建立链表表头 void CreateHeadLink(void){ CLUB *p;p=(CLUB *)malloc(sizeof(CLUB));headLink=p;p->next=NULL;} // 函数功能:增加新结点 void InsertOneNode(CLUB *t){ CLUB *p;p=headLink;while(p->next){ p=p->next;} p->next=t;} //函数功能:申请一个新结点,并将其初始化 CLUB *MallocNode(void){ CLUB *p;int i;p=(CLUB*)malloc(sizeof(CLUB));if(p==NULL)return NULL;for(i=0;i<20;i++)p->NAME[i]=' ';
for(i=0;i<20;i++)p->STREET[i]=' ';
for(i=0;i<10;i++)p->CITY[i]=' ';
for(i=0;i<20;i++)p->STATE[i]=' ';
for(i=0;i<20;i++)p->PHONE[i]=' ';
for(i=0;i<20;i++)p->EIP[i]=' ';
p->next=NULL;} return p;//函数功能:录入电话簿信息 void Enter(CLUB *t){
} printf(“请输入姓名: n”);scanf(“%s”,t->NAME);printf(“请输入街道信息:n”);scanf(“%s”,t->STREET);printf(“请输入城市信息:n”);scanf(“%s”,t->CITY);printf(“请输入国家信息:n”);scanf(“%s”,t->STATE);printf(“请输入电话号码:n”);scanf(“%s”,t->PHONE);printf(“请输入邮编信息:n”);scanf(“%s”,t->EIP);//函数功能:在链表的结尾处增加一个结点 void InsertOneNode(void){ CLUB *p;p=headLink;while(p->next){ p=p->next;} p->next=p;} //函数功能:根据用户输入的姓名显示电话簿的信息 void Search(void){ CLUB *p;char NAME[20];char flag=0;p=headLink->next;printf(“请输入要查询的姓名信息:n”);scanf(“%s”,NAME);while(p){ if(strcmp(p->NAME,NAME)==0){ printf(“n 姓名t街道t城市t国家t电话号码t邮编n”);DesplayOneNode(p);flag=1;break;} p=p->next;} if(!flag)} printf(“对不起,不存在姓名为 %s 的电话簿信息n”,NAME);//函数功能:输出一个结点的信息 void DesplayOneNode(CLUB *t){ printf(“%st”,t->NAME);printf(“%st”,t->STREET);printf(“%st”,t->CITY);printf(“%st”,t->STATE);printf(“%st”,t->PHONE);printf(“%st”,t->EIP);printf(“nt”);} //函数功能:显示所有电话簿的信息 void Display(void){ CLUB *p;p=headLink->next;if(p==NULL){ printf(“现在没有电话簿信息,请先输入电话簿信息nn”);return;} printf(“n”);printf(“nt姓名t街道t城市t国家t电话号码t邮编ntnt”);while(p){ DesplayOneNode(p);p=p->next;} p=NULL;} //函数功能:根据用户输入的姓名删除 void Delete(void){ char NAME[20];CLUB *p,*q;char flag=0;printf(“请输入要删除的姓名信息:”);scanf(“%s”,NAME);p=headLink;q=headLink->next;while(q){ if(strcmp(q->NAME,NAME)==0){ p->next=q->next;free(q);flag=1;break;} p=p->next;q=q->next;} if(!flag){
} printf(“不存在该姓名的信息n”);return;} printf(“成功删除n”);//函数功能:根据输入的姓名修改电话簿信息 void ChangeInforByName(void){ CLUB *p;char NAME[20];char flag=0;p=headLink->next;printf(“请输入姓名:n”);scanf(“%s”,NAME);while(p){ if(strcmp(p->NAME,NAME)==0){
printf(“请输入新的街道信息:n”);scanf(“%s”,&p->STREET);printf(“请输入新的电话号码:n”);scanf(“%s”,&p->PHONE);printf(“修改成功n”);break;}
} p=p->next;} // 函数功能:保存链表数据到文件中 void Save(void){ CLUB *p;FILE *fp;p=headLink->next;if(p==NULL){
} printf(“现在没有电话簿信息,请先输入电话簿信息nn”);return;} fp=fopen(“CLUB.txt”,“w+”);if(!fp){ printf(“文件不存在n”);return;} while(p){ fprintf(fp,“%st%st%st%st%st%sn”,p->NAME,p->STREET,p-> CITY,p->STATE,p->PHONE,p->EIP);p=p->next;} fclose(fp);
第二篇:数据结构课程设计要求
《数据结构》课程设计要求
一、课程设计的目的及要求
1.课程设计目的
课程设计是《数据结构》课程教学必不可缺的一个重要环节,它可加深学生对该课程所学内容的进一步的理解与巩固,是将计算机课程与实际问题相联接的关键步骤。通过课程设计,能够提高学生分析问题、解决问题,从而运用所学知识解决实际问题的能力,因而必须给予足够的重视。2.课程设计要求
1)明确课设任务,复习与查阅有关资料
2)按要求完成课设内容,课设报告要求文字和图工整、思路清楚、正确。3)每人完成一个项目。
4)应用程序应具有一定的可用性:
5)凡等候用户输入时,给出足够的提示信息,如“Please Select(1—3):”提示用户选择。
6)格式明显易懂,配上适当的颜色、声音等辅助效果,能方便地改正输入时的错误,使用户感到方便、好用。
7)有联机求助功能。用户能直接从系统得到必要的提示,不查手册也能解决一些疑难。8)程序具有一定的健壮性,不会因为用户的输入错误引起程序运行错误而中断执行: 9)对输入值的类型、大小范围、字符串的长度等,进行正确性检查,对不合法的输入值给出出错信息,指出错误类型,等待重新输入。
10)当可能的回答有多种时,应允许输入任何一种回答。11)对删除数据应给出警告。
二、课程设计任务、内容及时间安排
1.课程设计任务、内容
课程设计的题目可由教师指定,如可在下列选题中选择,或由教师另外选择,也可由学生自行选择。但选题内容、难度要适当,要有一定的实际意义,并能达到进一步巩固和强化本课程所学知识的效果。
选题1.停车场管理问题。
问题描述:设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排以便道上的第一辆车就进入停车场。停车场内如有某辆车要开走,在它之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些辆再依原来的次序进场。每辆车在离开停车场时,都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场时,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。
基本要求:要求程序输出每辆车到达后的停车位置(停车场或便道上),以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。
实现提示:汽车的模拟输入信息格式可以是:(到达/离去,汽车牌照号码,到达/离去的时刻)。例如,(„A‟,1,5)表示1号牌照车在5这个时刻到达,而(„D‟,5,20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(„E‟,0,0)时结束。本题可用栈和队列来实现。
选题2.一元多项式简单计算
问题描述:设计一个一元多项式简单的计算器。基本要求:一元多项式简单计算器的基本功能为:(1)输入并建立多项式;(2)输出多项式:
(3)两个多项式相加减、相乘,建立并输出多项式。
实现提示:可选择带头结点的单向循环链表或单链表存储多项式,头结点可存放多项式的参数(如项数等)。
选题3.迷宫问题。
问题描述:迷宫实验是取自心理学的一个古典的实验。在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形成了多处阻拦。盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步。老鼠经多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
基本要求:要求程序输出:
(1)一条通路的二元组(i,j)数据序列,(i,j)表示通路上某一点的坐标。
(2)用一种标志(如数字8)在二维数组中标出该条通路,并在屏幕上输出二维数组。
实现提示:可以利用一个二维数组maze[i][j]表示迷宫,其中1≦i≦m,1≦j≦n。数组元素值为1表示该位置是墙壁,不能通行;元素值为0表示该位置是通路。假定从maze[1][1]出发,出口位于maze[m][n],移动方向可以是8个方向(东、东南、南、西南、西、西北、北和东北)。
选题4.算术表达式求值演示。选题5.哈夫曼编/译码器。选题6.简单行编辑程序。选题7.各种图的算法的演示。选题8.汉诺塔的演示。2.时间安排
课程设计,安排在本课程的最后部分,时间一周。周1上午:设计动员,分组,布置课程设计任务。周1下午:查阅资料。
周2全天:进行程序总体设计和详细设计。周3~4全天:详细设计, 系统调试。
周5上午:系统调试,整理,撰写设计(或调研)报告。周5下午:验收,答辩,提交设计(或调研)报告,评定成绩。
四、报告内容及要求
课程设计报告应不少于1000字。报告中应包括需求分析、概要设计、详细设计、调试分析、用户手册、测试结果、附录等,具体地:
(1)设计报告中应首先包括设计题目、班级、姓名、学号、完成日期。
(2)概要设计中应包括设计思想、实现方法、系统中主要模块及各模块间的关系的描述。
(3)用户手册应详细、具体,使具有程序设计语言基础的人在阅读用户手册后能使用和退出应用程序。
(4)附录中包括源程序、设计体会等。源程序中应有注解,说明每个模块的功能,使别人能比较容易地读懂源程序;设计体会中应包括本系统的不足之处以及可改进的地方,还应说明系统的特色、新的发明、创造等等。
第三篇:数据结构课程设计要求
光盘内容说明
本光盘有8个目录,对应于课程设计教材中第2至5章的8个案例。每个目录以ch0x0y命名,代表第x章第y节的案例,内容包含该案例的源程序及教材中描述的测试数据。除“文件目录结构的显示”案例为.C++源程序外,其他均为C源程序。
各目录中的内容及说明:
1.ch0201:表达式求值,在VC++6.0环境下测试通过
文件main.c:案例源程序;
文件input.txt:案例测试输入数据文件;
文件output.txt:案例测试输出结果文件;
2.ch0202:文件目录结构的显示,在VC++6.0环境下测试通过
文件main.c:案例源程序;
文件input.txt:案例测试输入数据文件;
文件bad_input_cases.txt:案例容错测试输入数据文件;
文件output.txt:案例测试输入input.txt的输出结果文件;
3.ch0301:拯救007,在VC++6.0环境下测试通过
文件main.c、graph.c、deque.c、error.c、graph.h、deque.h、error.h:案例源程序。编译时需通过应用工程文件(console project)。
文件input.txt:案例测试输入数据文件;
文件output.txt:案例测试输出结果文件;
4.ch0302:迷宫问题,在TC2.0环境下测试通过
文件main.c:案例源程序;
说明:测试时可选择自动生成测试数据,读者也可按照教材中提供的数据进行测试;
5.ch0401:快速排序详析,在VC++6.0环境下测试通过
文件main.c:案例源程序;
文件input.txt:案例测试输入数据文件,包含顺序、逆序和随机等三种类型的测试数据;
文件output.txt:案例测试输出结果文件;
6.ch0402:插队买票,在VC++6.0环境下测试通过
文件main.c:案例源程序;
文件input.txt:案例测试输入数据文件;
文件output.txt:案例测试输出结果文件;
7.ch0501:搜索算法效率比较,在VC++6.0环境下测试通过
文件main.c:案例源程序;
说明:读者可按照教材中提供的数据进行测试;
8.ch0502:任务调度问题,在VC++6.0环境下测试通过
文件main.c:案例源程序;
说明:读者可按照教材中提供的数据进行测试;
第四篇:数据结构课程设计报告
数据结构课程设计
散列表的应用:插队买票
专业 计算机科学与技术(网络技术)
金玲 计算机131 1310704114 张静林 2015年1月23日 学生姓名 班学级 号
指导教师 完成日期
目录概述……………………………………………………………………………………1 1.1 课程设计目的……………………………………………………………………….1 1.2 课程设计内容……………………………………………………………………….1 2 系统需求分析……………………………………………………………………….1 2.1 主体功能…………………………………………………………………………....2 3系统概要设计…………………………………………………………………………2 3.1 系统流程图………………………………………………………………………….2 4 系统详细设计…………………………………………………………………………3 5 测试……………………………………………………………………………………5 5.1 测试方案…………………………………………………………………………….5 5.2 测试结果…………………………………………………………………………….5 6 小结……………………………………………………………………………………5 参考文献…………………………………………………………………………………5 附录………………………………………………………………………………………7 附录1 源程序清单……………………………………………………………………...7 概述
1.1 课程设计目的
数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识,加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的:
1.要求学生达到熟练掌握C语言的基本知识和技能。
2.了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力。3.提高程序设计和调试能力。学生通过上机实习,验证自己设计的算法的正确性。学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。
4.培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平。
5.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
1.2课程设计内容
本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队,有一个以上的朋友要求插队,则你可以安排他们的次序。每次一个人入队,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后,依次出队。系统需求分析
2.1 主体功能
程序从“input.txt”文件读入测试用例,一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n(1<=n<=1000)。对于一个朋友组以朋友的数目j(1<=j<=1000)开始,由朋友的个数以及他们的名字组成,一个空格后接该组朋友的名字,以空格分开,并且每个人的名字都不同。每个名字不超过四个字母,由{A,B,...,Z,a,b,...,z}组成。一个朋友组最多有1000个人,每个人只属于一个朋友组。n=0时,测试数据结束。
下面是一些具体命令:.ENQUEUE——X入队;.DEQUEUE——排队头的人买票,离开队伍,即出队;.STOP——一个测试用例结束。
测试结果输出到“output.txt”文件中。每个测试用例第一行输出“Scenario#k”,k是测试用例的序号(从1开始)。对每一个出队命令,输出刚买票离开队伍的人名。两个测试试用例 之间隔一空行,最后一个用例结束不输出空行。系统概要设计
3.1 系统流程图 系统详细设计
本题目主要解决两个问题:一是怎么存放和查找大量数据(主要是姓名);二是怎么操作“ENQUEUE”和“DEQUEUE”命令。
用散列表来存放和查找数据。由于最多有1000个朋友组,每组最多有1000人,使用平方探测法解决冲突,则表的大小是2*(1000*1000),所以选择TableSize=2000003(2000003是大于2000000的最小素数)。同一个组内的都是朋友,所以每个人除了记录他的名字name,还要记录他属于哪个组group,另外用info来表示该单元是否被占用,数据结构如图4.1所示。散列函数是根据Honer法则计算一个以64为阶的多项式,如图4.2所示。冲突解决方法采用平方探测法,如图4.3所示。
#define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab
/*散列表数据结构*/ { char name[5];
/*名字*/ int group;
/*属于哪个朋友组*/ char info;
/*标志位,该单元是否被占用*/ };图4.1数据结构:散列表
Int Hash(char *key,int TableSize){
Int HashVal=0;
While(key!=NULL)
HashVal=(HashVal<<6)+*key;
Return HashVal%TableSize;} 图4.2散列函数
Long int Find(PtrToHash hash,char *c){
key=c;
CurrentPos=Hash(key,TableSize);
CollisionNum=0;
While((单元被占用)and(单元内的名字与查找的名字不同))
{
CurrentPos+=2*(++CollisionNum)-1;
If(CurrentPos>=TabSize)
CurrentPos=TabSize;
}
Return CurrentPos;} 图4.3用平方探测法解决冲突
第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在,不能单纯的用一个数组来表示队列,因为这样的话,插入一个朋友,则他后面的人都要往后移一个单位,删除一个人,则他后面的人都要前移一个,会降低效率。所以,采用一个Index标记来表示当前元素的后继元素,最后一个单元的后继元素是第0个,形成环,数据结构如图4.4所示。不用链表是因为链表存放指针也需要空间,并且链表插入、删除的效率没有数组高。
typedef struct Que *PtrToQue;struct Que
/*队列数据结构*/ { long int HashVal;
/*散列值*/ long int Index;
/*在中的队列序号*/ };图4.4数据结构:队列
输入ENQUEUE命令,如果队伍里有朋友,则排在朋友后面;如果没有朋友,则排在队尾。入队时,用一个数组记录每个朋友组的最后一位,以便下一个朋友到来时排到他后面,这个数组被称为“插队数组”。
输入DEQUEUE命令,则根据“先进先出”,按照各个元素和它后继元素的先后顺序,每次删除队列重的第一个。程序结构如图4.5所示。
While(读测试文件){
if(输入”ENQUEUE”)
{
读入名字;
插入散列表;
插入队列;
}
else if(输入”DEQUEUE”)
{
删除队列第一个名字;
将该名字输出到文件;
}
else stop;} 图4.5入队、出队操作 测试
5.1 测试方案 按输入要求输入正常测试数据,测试程序是否能正确解决问题,得到正确答案。应注意边界测试。例如,将n,j分别取为1的用例和n为1000的用例。n,j比较大时需写程序生成测试用例。
不按输入要求输入数据,测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如,将n或j取为小于1或大于1000的数,名字超过4个字母等情况下的测试用例。5.2 测试结果 小结
在前面的学习过程中我们学到了很多知识而这次课程设计又是对我们所学的 一次总结,刚开始,可以说是没有头绪,于是就去图书馆找资料,找到了一些关于程序方面的,可这远远不够,这只是小小的开始。我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中,总的感觉是我遇到了很多困难这主要是由于我编写代码的经验不足,有时虽然是一个很小的问题但解决起来却花费了我不少的时间,值得欣慰的是,当自己苦思冥想或者和其它同学一起探讨把问题解决的时候我还是觉得获益非浅,这就是在摸索中寻求到的知识。在设计时也免不了存在着些不足,所以在今后的学习中我会努力取得更大的进步。虽然对着电脑做程序,有些累,可当看到劳动成果时,却有另一番滋味。
参考文献
[1]范策,周世平,胡晓琨.《算法与数据结构(C语言版)》[M].北京:机械工业出版社,2004 [2]严蔚敏.《数据结构(C语言版)》.北京:清华大学出版社,2004 [3]许卓群,杨冬青,唐世渭,张铭.《数据结构与算法》.北京:高等教育出版社,2004 [4]徐孝凯.《数据结构实用教程(第二版)》.北京:清华大学出版社,2006
附录
附录1 源程序清单
#include
/*散列表大小TabSize 是大于表最大空间的素数*/ #define Max 1000001
/*队列空间最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab
/*散列表数据结构*/ { char name[5];
/*名字*/ int group;
/*属于哪个朋友组*/ char info;
/*标志位,该单元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que
/*队列数据结构*/ { long int HashVal;
/*散列值*/ long int Index;
/*在中的队列序号*/ };
int hashedx=0;
/*标记元素是否已经在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum;
key=c;for(CurrentPos=0;*key;++key)
/*散列函数,计算散列值*/
CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize;
/*散列值*/ CollisionNum=0;/*如果当前单元被占用:单元内的元素与当前操作的名字不同,使用平方探测法解决冲突;与当前操作的名字相同,则直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)))
{
/*平方探测法*/
CurrentPos+=2*(++CollisionNum)-1;
if(CurrentPos>=TabSize)
CurrentPos-=TabSize;}
if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))
/*元素已经在散列表里*/
hashedx=1;else /*元素不在散列表里*/
hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ }
int main(){ long int Find(PtrToHash hash,char *c);
/*查找在散列表中的位置*/
PtrToHash hash;
/*散列表*/ PtrToQue queue;
/*队列*/ int *grouppos;
/*记录每个朋友组的最后一位,即插队数组*/ int n;
/*测试用例数目*/ int num;
/*当前测试用例序号*/ long int i,ii,j,key,temp;long int head,last;
/*队列的头和尾*/ char c[8],tempc[8];
/*名字*/ FILE *fpin,*fpout;
/*输入、输出文件指针*/
if(!(fpin=fopen(“input.txt”,“r”)))
/*打开测试文件*/ {
printf(“fopen error!”);
/*文件打开错误*/
return-1;} if(!(fpout=fopen(“output.txt”,“w”)))
/*打开输出文件*/ {
printf(“fopen error!”);
return-1;}
hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*为散列表申请空间*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*为队列申请空间*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申请空间记录每个朋友组的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一个单元的后继单元是第0个,形成环*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*输入当前测试用例的朋友组数*/ { if(n<1||n>1000) /*处理异常输入n*/ { fprintf(fpout,“n is out of rangen”); return-1; } num++; if(num!=1) /*两个测试用例间输入一空行*/ fprintf(fpout,“n”); for(i=0;i hash[i++].info=0; /*初始化散列表,标记位置0*/ for(i=0;i /*对每一组朋友*/ { fscanf(fpin,“%d”,&j); /*当前组里的人数*/ if(j<1||j>1000) /*处理异常输入j*/ { fprintf(fpout,“j is out of rangen”); return-1; } for(;j;--j) { fscanf(fpin,“%s”,c); /*输入名字*/ for(ii=0;ii tempc[ii]=' '; strcpy(tempc,c); ii=0; while(tempc[ii]!=' ') /* 是否由四个以内字母组成*/ { if(tempc[ii]<'A'||('Z' { fprintf(fpout,“Group %d: Nonstandard namen ”,i); return-1; } ii++; } key=Find(hash,c); /*找到在散列表中的位置*/ if(hashedx==1)/*重名*/ { fprintf(fpout,“repeated name %sn”,c); return-1; } strcpy(hash[key].name,c);/*插入散列表*/ hash[key].info=1; /*标记置1,该单元被占用*/ hash[key].group=i; /*记录他属于哪个组*/ } } for(i=0;i<1000;) grouppos[i++]=0;/*初始化插队数组*/ head=0; /*初始化队列头、尾标记*/ last=0;fprintf(fpout,“Scenario #%dn”,num);/*输出当前用例序号到文件*/ for(fscanf(fpin,“%s”,c);;fscanf(fpin,“%s”,c))/*输入命令*/ { if(*c=='E') /*入队命令*/ { fscanf(fpin,“%s”,c); /*输入名字*/ key=Find(hash,c); /*查找在散列表中的位置*/ if(hashedx==0)/*散列表里没这个人*/ { fprintf(fpout,“no %sn”,c); return-1;} temp=queue[0].Index; /*队列第0个位置记录队尾的后继单元*/ queue[0].Index=queue[temp].Index; /*在队列中申请一个新单元,队尾标记后移一个位置 */ queue[temp].HashVal=key;/*入队*/ if(!head)/*如果是队列里的第一个元素 */ last=head=temp;/*队头、队尾标记指向第一个元素*/ if(!grouppos[hash[key].group])/*如果队列里没朋友*/ { queue[temp].Index=0;/*队尾指向对头,形成环*/ queue[last].Index=temp;/*前一次队尾的后继元素是当前元素*/ last=temp; /*队尾标记指向当前元素*/ grouppos[hash[key].group]=temp;/*插队数组记录该朋友组里已入队的最后一位*/ } else/*如果队列中已经有他的朋友*/ { queue[temp].Index=queue[grouppos[hash[key].group]].Index; /*插队到朋友的后面*/ queue[grouppos[hash[key].group]].Index=temp; /*插队到朋友后面一位的前面*/ grouppos[hash[key].group]=temp; /*替换插队数组里该组的元素为当前元素*/ if(hash[queue[last].HashVal].group==hash[key].group) /*如果当前元素和前一元素是朋友,队尾标志指向当前元素*/ last=temp; } } else if(*c=='D')/*出队命令*/ { if(last==0) /*不能对空队列执行出队命令*/ { fprintf(fpout,“Empty queue!nCan't execute DEQUEUE!n”); return-1; } fprintf(fpout,“%sn”,hash[queue[head].HashVal].name); /*输出队头元素到文件*/ temp=head; head=queue[temp].Index; /*队列第一位出队,队头标记后移一位*/ queue[temp].Index=queue[0].Index; /*队列第0个元素后移一位*/ queue[0].Index=temp; /*释放空间*/ if(grouppos[hash[queue[temp].HashVal].group]==temp) /*当前删除的元素是该朋友组在队列里的最后一位*/ grouppos[hash[queue[temp].HashVal].group]=0; if(last==temp) /*出队后,队列为空*/ last=0; } else /*输入 “STOP”*/ break; /*测试结束*/ } } fprintf(fpout,“b”);fclose(fpin);fclose(fpout);return 1;} 正文要求:对每一个题目,正文必须包括以下几个方面 知识点回顾: 实验要求: 实验过程:包括设计思路,算法描述,程序清单,调试等等; 实验小结: 注意:(1)正文中字体用小四号宋体,行间距1.25倍行距; (2)页码居中; (3)A4纸双面打印,在纸的左侧装订。 (4)上交的课程设计报告控制在10页以内。 齐鲁工业大学 理学院 信计11-1 郑桥 一、提示:对于单窗口的服务系统知识点回顾如下: 1、什么是负指数分布? 又称指数分布。泊松事件流的等待时间(相继两次出现之间的间隔)服从指数分布。用于描述非老化性元件的寿命(元件不老化,仅由于突然故障而毁坏)。常假定排队系统中服务器的服务时间和Petri网中变迁的实施速率符合指数分布。 2、用C语言如何产生随机序列? double rd_MN1(double m,double n){ double r;if(m>n){r=n;n=m;m=r;};r =((double)rand()/((double)(RAND_MAX)+(double)(1)));r = m+ r*(n-m);return r;} 3、用C语言如何产生负指数分布的时间序列? double expntl(double x){ double z;do { z =((double)rand()/ RAND_MAX);} while((z == 0)||(z == 1));return(-x * log(z));//z相当于1-x,而x相当于1/lamda。} 其中的x相当于1/λ 4、排队论简单叙述; 排队系统主要有:X/Y/Z,其中X表示到达时间间隔的分布,Y表示服务时间的分布,Z表示并列的服务设备的数目。表示相继到达的时间间隔或服务时间的分布的符号是: M——负指数分布,D——确定性,Ek——k阶Erlang,GI——相互独立的一般随机分布,G——一般的随机分布。 例如:M/M/1表示达到时间间隔为负指数分布,服务时间为负指数分布,单服务设备的排队系统。 这里我们用静态仿真的思想来实现M/M/1仿真。在排队系统中的每一个动态实体的状态可以有三个量来反映:与前一个实体到达的时间间隔,在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布,不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下: 即:如果某个实体到达以后,发现处在它前面的动态实体已经结束服务,所以这个实体就不用等待,直接接受服务;反之,处在它前面的动态实体如果没有结束服务(包括没有开始服务),则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。 5、如何得到每个顾客的到达时刻,服务时间,等待时间和离开时刻; 到达时间=前面各个到达时间之和; 服务时间就是负指数随机生成的时间; 等待时刻:如果前一个人的离开时间小于这个人的到达时间,等待时间=0; 如果不是,则等待时间=该人的离开时间-他的到达时间-服务时间 6、如何排队,排队的主要算法思想? 排队就是来到的人数多于离开的人数; 如果下一个人到达时前一个人依旧在接受服务,则此人就要排队。 7、如何求队长?以及最大的队长? 假设以5分钟为一个时间段,则在第5分钟时用这5分钟内来到的人数减去这5分钟内离开的人数即是排队人数 8、如何求平均等待时间? 求平均等待时间首先要求出总的等待时间与接受服务的人数; 总的等待时间=每个人的等待时间之和;接受服务的人数由时间540分钟来控制,如果在540分钟之后才到达的人则不再算入接受服务的人数之内。 9、用C语言如何将得到的数据输出到文件? 在C语言中用fopen函数打开文件,然后把数据输出比如用fprintf函数,最后fclose。 利用ofstream fcout(“d:arr_time.txt”);语句来实现C++中的输出文件 10、如何用已学的数学语言程序(如:Mathematica, Matlab)把C语言得到的数据文件画出其相应的图像? 11、如果是两个窗口的服务系统,则该怎么修改程序? 12、如果到达时间间隔,服务时间服从泊松分布或者其他分布,该程序该如何改进? 二、数据结构课程设计题目 单窗口的排队模型的数值仿真(参考课本上第四章的离散事件模拟)要求如下:(1)要求相邻两个顾客的到达时间间隔服从负指数分布;且每个顾客接受服务的时间也服从负指数分布; (2)求出各个时刻的队长(以五分钟为一时间单位,即求零时刻的队长,五分钟时的队长,十分钟时的队长,依次类推); (3)一个工作日内的顾客总数,约定8:30上班,17:30下班,中午不休息;(4)求平均等待时间(顾客总等待时间除以总人数); (5)画出顾客的到达,离开图像(横坐标是顾客图,纵坐标是到达时刻,和离开时刻); (6)画出队长变换图像(横坐标是时刻图,纵坐标是队长个数);(7)求出一个工作日内的最大队长; 三、设计思路: 1)把8::30记做第0分钟,17:30记做第540分钟。 2)首先利用C++随机生成200个服从负指数分布的到达时间与200个服务时间 然后根据随机生成的数计算到达的时刻,即到达时间的逐步加和,然后计算离开的时刻; 3)根据到达时刻与离开时刻来计算等待时刻,于是便可得到平均等待时间; 同时根据这两个时刻求出每5分钟到达人数与离开的人数,于是便得出每5分钟的队长,同时也可求出最大队长。4)再利用MATLAB画出相应的图像。 四、算法描述: 1)首先将8:30这个时刻化为0时刻,17:30化为第540分钟这个时刻,全体单位为分钟。 2)定义到达时间间隔arr_time[200],服务时间ser_time[200],到达时刻arr_time1[200],离开时间lea_time[200],等待时间sta_time[200],离开人数lea_num[200],到达人数arr_num[200]等变量。3)根据负指数函数 来利用C++程序生成随机到达时间间隔与服务时间。 4)利用到达时刻与离开时刻之间的关系来求出等待时间。同时将这540分钟划分为5分钟间隔的108个时间段来求出在每个时间段到达人数与离开人数,再求出队长。 5)利用已知的服务人数,平均到达时间与平均离开时间来做出图像。(借助MATLAB软件。) 五、总结 (1)求出各个时刻的队长(以五分钟为一时间单位,即求零时刻的队长,五分钟时的队长,十分钟时的队长,依次类推);见程序清单中数据部分对长。(2)求平均等待时间(顾客总等待时间除以总人数);根据程序可得,平均等待时间为21.6分钟。 (3)画出顾客的到达,离开图像(横坐标是顾客图,纵坐标是到达时刻,和离开时刻); ***0100806040200 0Arrive curveleave curve***600 (6)画出队长变换图像(横坐标是时刻图,纵坐标是队长个数); 25Queue Length Curve 20151050 ***0600 (7)求出一个工作日内的最大队长: 最大对长为16个人在排队。 六、程序清单: 求随机产生负指数 #include #include void main(){ long int i,k;double m,n;//m,n控制时间间隔 double r;double a,s,sum;//arr为到达时间,ser为服务时间 double LAM=1.2; //f(x)=LAM*exp(-LAM*x);double arr_time[200];double ser_time[200];ofstream fcout(“d:arr_time.txt”);ofstream fscout(“d:ser_time.txt”);m=2.0;n=5.0;srand((unsigned)time(NULL)); k=0;loop: r=((double)rand()/((double)(RAND_MAX)+(double)(1))); a =-log(r)/LAM;if(a >= m && a <= n){ arr_time[k]=a; k++;};if(k < 200)goto loop; // 产生200个指数分布随机数 for(i=0;i<200;i++){ fcout< //cout< if(i!=0 && i%5==0) //cout< fcout< s =-log(r)/LAM;if(s >= m && s <= n){ ser_time[k]=s;k++;};if(k < 100)goto loop1; // 产生200个指数分布随机数 m=3.0;n=5.5; srand((unsigned)time(NULL));k=100;loop2: r=((double)rand()/((double)(RAND_MAX)+(double)(1))); s =-log(r)/LAM;if(s >= m && s <= n){ ser_time[k]=s;k++;};if(k < 200)goto loop2; // 产生200个指数分布随机数 for(i=0;i<200;i++){ fscout< //cout< if(i!=0 && i%5==0) //cout< fscout< #include double sta_time[200];//等待时间 double arr_time[200];//随机生成到达时间 double ser_time[200];//随机生成服务时间 double arr_time1[200];//到达时间 ifstream fcin(“d:arr_time.txt”);ifstream fscin(“d:ser_time.txt”);ofstream fcout(“d:arr_time1.txt”);ofstream flcout(“d:lea_time.txt”);ofstream fscout(“d:sta_time.txt”); //求到达的时间 for(i=0;i<200;i++){ fcin>>arr_time[i]; arr_time1[i]=arr_time[i];} double sum=0.0;for(i=0;i<200;i++){ sum+=arr_time1[i]; arr_time1[i]=sum;} for(i=0;i<200;i++){ fcout< if(i!=0 && i%5==0) fcout< //求离开时间 fscin>>ser_time[0];lea_time[0]=arr_time1[0]+ser_time[0];for(i=1;i<200;i++){ fscin>>ser_time[i]; if(lea_time[i-1]>arr_time1[i]) {lea_time[i]=lea_time[i-1]+ser_time[i];} else {lea_time[i]=arr_time1[i]+ser_time[i];} } for(i=0;i<200;i++){ flcout< if(i!=0 && i%5==0) flcout< sta_time[i]=lea_time[i]-arr_time1[i]-ser_time[i];// if(sta_time[i]<0) { sta_time[i]=0; } } for(i=0;i<200;i++){ fscout< if(i!=0 && i%5==0) fscout< sta_sum+=sta_time[i];} //求平均等待时间 double ave;int peo_sum;for(i=0;i<200;i++){ if(lea_time[i]<540) peo_sum=i;} cout<<“总的服务人数为:”< 求离开人数和到达人数 #include #include int i,j; int arr_num[200];//到达人数arr int lea_num[200];//lea离开人数 int arr_jian=0;//时间间隔 double arr_time1[200];double lea_time[200];int peo_sum;int count=0;int count1=0;ifstream fcin(“d:arr_time1.txt”);ifstream flcin(“d:lea_time.txt”);ofstream fcout(“d:arr_num.txt”);ofstream flcout(“d:lea_num.txt”);for(i=0;i<200;i++){ fcin>>arr_time1[i]; flcin>>lea_time[i];} for(i=0;i<200;i++){ if(lea_time[i]<540) peo_sum=i;} while(arr_jian<540){ for(i=0;i { if(arr_time1[i]>arr_jian) { arr_num[count]=i; count++;第五篇:数据结构课程设计报告