数据结构插队买票

数据结构课程设计报告

插队买票

专业 计算机科学与技术

学生姓名 班学

级 号

指导教师 完成日期

插队买票

目 录

1 概 述 ............................................................... 1 1.1 课程设计目的 ................................................ 1 1.2 课程设计内容 ................................................ 1 2 系统需求分析 ........................................................... 1 2.1 系统目标 .................................................... 1 2.2 主体功能 .................................................... 2 2.3 开发环境 .................................................... 2 3 系统概要设计 ........................................................... 2 3.1 系统的功能模块划分 .......................................... 2 3.2 系统流程图 .................................................. 2 4系统详细设计 ............................................................ 3 5 测试 ................................................................... 5 5.1 测试方案 .................................................... 5 5.2 测试结果 .................................................... 5 6 小结 ................................................................... 5 参考文献 ................................................................. 5 附 录 ................................................................. 7 附录1 源程序清单 ....................................................... 7

数据结构课程设计报告（2014）

插队买票 1 概 述 1.1 课程设计目的

数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的：

1．要求学生达到熟练掌握C语言的基本知识和技能。 2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

4．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。

1.2 课程设计内容

本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。

2 系统需求分析 2.1 系统目标

数据结构课程设计用 C/C++编程实现。

1．问题描述与分析：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？

2．数据结构设计：为实现每个功能选择的逻辑结构和存储结构，分析原因及合理性。

3．软件结构设计：设计软件模块之间的结构。

4．算法设计：算法的设计及算法分析。每个部分的算法设计说明，可以用流程图描述算法。

5．程序编码：把详细设计的结果进一步求精为程序设计语言程序。源程序要按照软件工程的规则来编写，要求结构清晰，重要功能部分要加上清晰的程序注释。

1

插队买票

6．调试分析：掌握调试工具的各种功能，设计测试数据，测试输出的结果。并进行算法的时间复杂度和空间复杂度的分析。

7．总结：课程设计过程的收获，遇到问题以及解决问题的思路和方法，程序调试能力的思考，对数据结构这门课程的认识及思考等。

8．编写课程设计报告。 2.2 主体功能

程序从“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开始）。对每一个出队命令，输出刚买票离开队伍的人名。两个测试用例之间隔一空行，最后一个用例结束不输出空行。 2.3 开发环境

Microsoft Visual C++ 6.0

3 系统概要设计

3.1 系统的功能模块划分

主函数模块：是系统的入口，系统的执行需要调用菜单界面，通过菜单界面触发系统的各个功能。系统中通过获取句柄（标准输入、标准输出）来监控程序的执行。调用初始化的菜单界面，然后根据菜单所显示的功能去调用相应的功能模块函数，从而实现系统管理功能。

系统执行模块：包含系统的初始化、清屏、执行以及退出等功能。

文件操作模块：将文件看做一个数据库来进行操作。充分考虑系统执行的时间与空间复杂性，将文件信息归类保存。文件操作模块需要有新建、加载、保存、退出这四项基本内容，还可以增加备份和维护功能。

2

数据结构课程设计报告（2014）

3.2 系统流程图

开始 初始化窗口队列，读入测试用例 用户选择 入队 当前测试用例结束 出队 是否读到文件尾 结束 图4-1 插队买票流程图

4系统详细设计

本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多有1000人，使用平方测探法解决冲突，则表的大小是2*（1000*1000），所以选择TableSize=2000003(2000003是大于2000000的最小素数)。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个组group，另外用info来表示该但愿是否被占用，数据结构如图4-1所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图4-2所示。冲突解决方法采用平方探测法，如图4-3所示。

3

插队买票

#define TabSize 2000003 typedef struct hashtab *PtrToHash; struct hashtab { char name[5]; int group; char info; /*用来表示该单元是否被占用*/ }; 图4-2 数据结构：散列表

int Hash(char *key,int TableSize) { int HashVal=0; while(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize; } 图4-3 散列函数

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-4用平方探测法解决冲突

第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯地用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如图4-4所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。 Typedef struct Que *PtrToQue; Struct Que { long int HashVal; long int Index; }; 图4-5 数据结构：队列

输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有朋友，则

4

数据结构课程设计报告（2014）

排在对尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插队数组”。

输入DEQUEUE命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列中的第一个。程序结构如图4-5所示。 While(读测试文件) { if(输入“ENQUEUE”) { 读入名字； 插入散列表； 插入队列； } else if(输入“DEQUEUE”) { 删除队列第一个名字； 将该名字输出到文件； } else stop; } 图4-6 入队、出对操作

5 测试

5.1 测试方案

1.按输入要求输入正常测试数据，测试程序是否能正确解决问题，得到正确答案。 2.应注意边界测试。例如，将n、j分别取为1的用例和n胃1000的用例。n、j比较大时需写程序生成测试用例。

3.不按输入要求输入数据，测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如，将n或j取为小于1或大于1000的数，名字超过4个字母等情况下的测试用例。 5.2 测试结果 1．无任何输入结果：

当输入的n小于程序所要求的1<=n<=1000时，因为n小于1，所以会报错，调用冲突处理模块，程序输出的结果如图

5

插队买票

图4–7 无任何输入结果

2．正确显示结果：

按照输入要求正确的输入几组数据，根据出入队的顺序，先进的回排在最后一个得后面，所以输出结果如图4 – 8所示

6

数据结构课程设计报告（2014）

图4 – 8 正确显示结果

3.举例说明几种异常结果：

7

插队买票

1．Repeated name

当出现人名重复的时候出现的结果，出现异常，调用异常处理模块中人名重复异常处理模块，所以输出结果如图4 - 9所示

图4 – 9 Repeated name

2

数据结构课程设计报告（2014）

2.No name

当出队的人不存在时候，出现异常，调用异常处理模块中没有这个人不存在的异常处理模块，输出结果如下图4 – 10 所示

图4 – 10 No name

3

插队买票

3.Nonstandard name

当输入的数据不是标准的输入的时候，出现异常，调用异常处理模块中异常输入名字模块，输出结果如图4 – 11 所示

图4 – 11 Nonstandard name

4

数据结构课程设计报告（2014）

6 小结

经过这次的数据结构实践,我个人得到了不少的收获,一方面加深了我对课本理论的认识,另一方面也提高了实验操作能力。现在我总结了以下的体会和经验。

这次的实践跟我们以前做的实验不同，因为我觉得这次我是真真正正的自己亲自去完成。所以是我觉得这次实验最宝贵，最深刻的。就是实践的过程全是我们学生自己动手来完成的，这样，我们就必须要弄懂实验的原理。在这里我深深体会到哲学上理论对实践的指导作用：弄懂实验原理，而且体会到了实践的操作能力是靠自己亲自动手，亲自开动脑筋，亲自去请教别人才能得到提高的。

我们做实践绝对不能人云亦云，要有自己的看法，这样我们就要有充分的准备，若是做了也不知道是个什么实践，那么做了也是白做。在实践过程中，我们应该尽量减少操作的盲目性提高实验效率的保证，有的人一开始就赶着做，结果却越做越忙，主要就是这个原因。我们做实践不要一成不变和墨守成规，应该有改良创新的精神。

在实践的过程中我们要培养自己的独立分析问题，和解决问题的能力。培养这种能力的前题是你对每次实验的态度。如果你在实验这方面很随便，抱着等老师教你怎么做，拿同学的报告去抄，尽管你的成绩会很高，但对将来工作是不利的

最后，通过这次的数据结构实践我不但对理论知识有了更加深的理解，对于实际的操作和也有了质的飞跃。经过这次的实验，我们整体对各个方面都得到了不少的提高，希望以后学校和系里能够开设更多类似的实践，能够让我们得到更好的锻炼。

5

插队买票

参考文献

[1] 许卓群，杨冬青，唐世渭，张铭. 数据结构与算法 .[M] 北京：高等教育出版 [2] 范策，周世平，胡哓琨. 算法与数据结构（C语言版）. [M] 北京：机械工业出版社，2004

[3] 严蔚敏. 数据结构（C语言版）. [M] 北京：清华大学出版社，2004 [4] 徐孝凯. 数据结构实用教程（第二版）. [M] 北京：清华大学出版社，2006 [5] 谭浩强. C程序设计（第四版）. [M] 北京：清华大学出版社，2010 [6] 陈文博，朱青 数据结构与算法. [M] 北京：机械工业出版社，1996年 [7] 李廉治，姜文清，郭福顺数据结构. [M] 大连：大连理工大学出版社，1989年

6

数据结构课程设计报告（2014）

附 录

附录1 源程序清单

#include #include #include

#define TabSize 2000003 /*散列表大小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;/*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测法解决冲突；与当前操作的名字相同，则直接返回在散列中的位

7

插队买票

置*/

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(\打开测试文件*/ {

printf(\ printf(\插队买票 --------\\n\ printf(\

printf(\文件打开错误*/ return -1; }

if(!(fpout=fopen(\打开输出文件*/ {

8

数据结构课程设计报告（2014）

printf(\ printf(\插队买票 --------\\n\ printf(\ printf(\ 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,\输入当前测试用例的朋友组数*/

{

if(n<1||n>1000) /*处理异常输入n*/ {

printf(\ printf(\插队买票 --------\\n\ printf(\ printf(\ fprintf(fpout,\ return -1;

}

num++;

if(num!=1) /*两个测试用例间输入一空行*/ fprintf(fpout,\ for(i=0;i

hash[i++].info=0; /*初始化散列表，标记位置0*/ for(i=0;i

fscanf(fpin,\当前组里的人数*/ if(j<1||j>1000) /*处理异常输入j*/

9

插队买票

{

printf(\ printf(\插队买票 --------\\n\ printf(\ printf(\ fprintf(fpout,\ return -1; }

for(;j;--j) {

fscanf(fpin,\输入名字*/

for(ii=0;ii

tempc[ii]='\\0'; strcpy(tempc,c); ii=0;

while(tempc[ii]!='\\0') /* 是否由四个以内字母组成*/ {

if(tempc[ii]<'A'||('Z''z'||ii>4)

{

printf(\

printf(\插队买票 --------\\n\

printf(\

printf(\ fprintf(fpout,\ return -1;

} ii++; }

key=Find(hash,c); /*找到在散列表中的位置*/ if(hashedx==1) /*重名*/ {

printf(\ printf(\插队买票 --------\\n\

printf(\

10

数据结构课程设计报告（2014）

printf(\ fprintf(fpout,\ 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,\输出当前用例序号到文件*/ for(fscanf(fpin,\输入命令*/ {

if(*c=='E') /*入队命令*/ {

fscanf(fpin,\输入名字*/

key=Find(hash,c); /*查找在散列表中的位置*/ if(hashedx==0) /*散列表里没这个人*/ {

fprintf(fpout,\ 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;

11

素*/

插队买票

/*插队数组记录该朋友组里已入队的最后一位*/ }

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) /*不能对空队列执行出队命令*/

{

printf(\ printf(\插队买票 --------\\n\ printf(\ printf(\

fprintf(fpout,\queue!\\nCan't execute DEQUEUE!\\n\ return -1; }

fprintf(fpout,\/*输出队头元素到文件*/ 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) /*出队后，队列为空*/

12

数据结构课程设计报告（2014）

}

last=0; }

else /*输入 \ break; /*测试结束*/ } }

printf(\printf(\插队买票 --------\\n\printf(\printf(\操作完成\\n\fprintf(fpout,\fclose(fpin); fclose(fpout); return 1;

13

数据结构课程设计报告（2014）

}

last=0; }

else /*输入 \ break; /*测试结束*/ } }

printf(\printf(\插队买票 --------\\n\printf(\printf(\操作完成\\n\fprintf(fpout,\fclose(fpin); fclose(fpout); return 1;

13

本文来源：https://www.bwwdw.com/article/vkt.html