第一篇：C语言与数据结构课程设计报告要求
C语言与数据结构课程设计报告
学 号 2014014083 姓 名 汪明 课程设计题目 通讯录的制作
202_ 年 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(202_);system(“cls”);break;case 2: Search();//按姓名查找信息 Sleep(202_);system(“cls”);break;case 3: //录入新信息
p=MallocNode();//先申请一个新结点 Enter(p);//要求用户输入信息到新结点中 InsertOneNode(p);//将新结点加到链表中 Sleep(202_);system(“cls”);break;case 4: Delete();//删除电话簿信息
Sleep(202_);system(“cls”);break;case 5:
ChangeInforByName();//按姓名修改电话簿信息 Sleep(202_);system(“cls”);break;case 6: Save();//保存 Sleep(202_);system(“cls”);break;case 7:
Load();//装入 Display();Sleep(202_);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.时间安排
课程设计，安排在本课程的最后部分，时间一周。周１上午：设计动员，分组，布置课程设计任务。周１下午：查阅资料。
周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：案例源程序；
说明：读者可按照教材中提供的数据进行测试；
第四篇：数据结构课程设计报告
青岛理工大学
数据结构课程设计报告
题目：宿舍管理查询软件
院（系）：计算机工程学院
学生姓名:谢茂盛
班级：网络121学号: 201207131
起迄日期:202_.07.07-202_.07.20
指导教师:张艳
一、需求分析（所有大标题宋体加粗四号，下同）（小标题宋体加粗小四，下同）
1.问题描述：
以无歧义的陈述详细说明对自己所选题目的解释性描述，可以补充说明该设计中要做的具体任务。强调的是程序要做什么？
2.基本功能
要求分别列出该设计要实现的功能，（每个功能要尽量和概要设计中的模块函数对应起来）。
二、概要设计
1.设计思路：
解决问题的思路概述，拟采用的算法的简介。
2.数据结构设计：
要求分别列出拟采用的数据结构及其定义，分为逻辑结构（线性？树状？图状？）和存储结构（顺序？链式？）。采用该结构的原因，如果有定义的抽象数据类型，可以列出其定义及各种操作。如下为抽象数据类型定义的模板。
定义程序中用到的抽象数据类型；
设计中所用到的数据结构或抽象数据类型的说明，以及在程序中的作用
抽象数据类型线性表的定义如下：
ADT List{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
数据关系：R1={| ai-1,ai ∈D,i=1,2,3,……，n}
基本操作：
Insert(&L,i,j)
初始条件：线性表L已存在，1≤i≤n+1。
操作结果：在L中第i个位置之前插入新的数据元素j,L的长度加1。
Del(&L,i,j)
初始条件：线性表L已存在，1≤i≤n。
操作结果：删除L的第i个数据元素,L的长度减1
Xg(&L,i,j)
初始条件：线性表L已存在。
操作结果：用新的输入数据项j代替原有的指定要修改的数据项i。
Search(&L,i,e)
初始条件：线性表L已存在。
操作结果：查找指定的某元素i，并将值赋给e,用e 输出。
}
3.软件结构设计：
按需求分析中的功能进行模块划分，建立模块的层次结构及调用关系。
三、详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画
出函数和过程的调用关系图。
实现设计中主程序和其他子模块的算法，以流程图的形式表示，需画出函数和过程的调用关系图。
本小节内所有的图均要求用Visio或Word进行绘制，不允许用bmp或其他格式的图片。绘图内文字均采用宋体五号（如果图比较大，排版不好看的话，可以根据需要缩小字体），单倍行间距，段前段后均设置为0行。
1.定义程序中所有用到的数据及其数据结构，及其基本操作的实现；
2．主函数和其他函数的伪码算法；
3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。
4.画出函数之间的调用关系图。
四、调试分析
内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析。
1.实际完成的情况说明（完成的功能，支持的数据类型等）；
2.程序的性能分析，包括时空分析；
3.上机过程中出现的问题及其解决方案；
4.程序中可以改进的地方说明；
5.程序中可以扩充的功能及设计实现假想。
五、测试结果
列出你的测试结果，包括输入和输出。注意测试数据应该完整和严格，至少给出2组测试结果（含合法数据与非法数据）。
六、用户手册
说明如何使用你编写的程序，详细列出每一步的具体操作步骤。这里可以有适当的运行结果抓图。用户手册与开发过程无关，只与使用有关，必须是Step by Step的。
所有运行结果截图均要求有实际数据的内容，截图尺寸要求按页宽排版两张大小，且要求有每张图下面有规范的标题说明如何使用你编写的程序，详细列出每一步的操作步骤。
七、体会与自我评价
写出本设计的总结思考，收获心得体会，要求不少于600字，不得摘抄网上资料，只能参考。
正文（各标题除外），均采用宋体和Times New Roman字体，小四号字，1.25倍行距。
八、参考文献（列出你参考的书，格式按照下面的例子来写）例如：
[1]严蔚敏．数据结构(C语言)．清华大学出版社，202_
第五篇：数据结构课程设计报告
数据结构课程设计
散列表的应用:插队买票
专业 计算机科学与技术（网络技术）
金玲 计算机131 1310704114 张静林 202_年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].北京：机械工业出版社，202_ [2]严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社，202_ [3]许卓群，杨冬青，唐世渭，张铭.《数据结构与算法》.北京：高等教育出版社，202_ [4]徐孝凯.《数据结构实用教程（第二版）》.北京：清华大学出版社，202_
附录
附录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;}
鲁公网安备37028302000876号