插队买票的设计

数据结构课程设计报告

插队买票的设计

散列表的应用：插队买票的设计

目 录

1 设计内容 ................................................................................................................. 1 2 设计分析 ................................................................................................................. 1 2.1 ******设计 .......................................................................................................... 1 2.2 ******设计 .......................................................................................................... 2 3设计实践 ................................................................................................................. 2 3.1****** ................................................................................................................... 2 3.2****** ................................................................................................................... 3 4测试方法 ................................................................................................................. 4 5 程序运行效果 ......................................................................................................... 6 6 设计心得 ................................................................................................................. 8

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

散列表的应用：插队买票的设计 1 设计内容 春节前夕，一年一度的运输高潮也开始了，成千上万的外出人员都往家赶。火车站售票窗前买票队伍一眼望不到头。运气好的，碰到一个已经在排队的朋友，直接走过去，排他后面，这就叫“插队”，但对队伍里的其他人来说是不公平的。本课程设计的任务是写一个程序模种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。

2 设计分析

本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。

用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图所示。散列函数是根据Honer法则计算一个以64为阶的多项式 2.1 存放查找设计

用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图所示。散列函数是根据Honer法则计算一个以64为阶的多项式。

1

散列表的应用：插队买票的设计

2.2 操作命令设计

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

3设计实践

3.1存放查找设计

#define TabSize 2000003 /*散列表大小TabSize typedef struct hashtab *PtrToHash; struct hashtab /*散列表数据结构*/ { }; 3.11 数据结构：散列表 Int Hash(char *key,int TableSize) { int HashVal=0; while(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal %TableSize; } long int Find(PtrToHash hash,char *c) /*查找在散列表中的位置*/ { char *key; long int CurrentPos,CollisionNum; key=c; for(CurrentPos=0;*key;++key) /*散列函数，计算散列值*/ char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ 2

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

} CurrentPos=(CurrentPos<<6)+*key; CurrentPos%=TabSize; /*散列值*/ CollisionNum=0; /*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探测法*/ } hashedx=1; CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize; 法解决冲突； */ if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) else /*元素不在散列表里*/ hashedx=0; return CurrentPos;/*返回在散列表中的位置*/ 3.12 平方探测法 3.2 操作命令设计 While(读测试文件) { if(输入“ENQUEUE”) {读入名字； 插入散列表； 插入队列； } else if(输入“DEQUEUE”) {删除队列第一个名字； 将该名字输出到文件； } Else stop; } 3.21 入队和出对操作

3

散列表的应用：插队买票的设计

4测试方法

为了每个队伍都允许插队，如果你在排队，有一个以上的朋友要求插队，

则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插到朋友后面，当队伍中的朋友不止一个得时候，这个人会排在最后一个朋友的后面，如果队伍中没有朋友，则他只能排在最后面，每一个人的人都先进行上述的判断。

测试图：

图4.1 测试输入图1

图4.1 测试输入图2

4

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

最终输入图： 图4.1 测试输入图3

图4.1 测试输入图4

5

散列表的应用：插队买票的设计

5 程序运行效果

下图是我四次程序运行输出的结果：

6

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

图5.1 运行结果

图5.2 第一次输出结果

图5.3 第二次输出结果

图5.4 第三次输出结果

7

散列表的应用：插队买票的设计

图5.5 第四次输出结果

图5.6 正式输出结果

6 设计心得

以上方法测试了四种特殊情况，期间出现不少情况，但逐一解决了，成功的出了正确的结果。

在这次课程设计中,总的感觉是我遇到了很多困难,这主要是由于我编写代码的经验不足,有时虽然是一个很小的问题,但解决起来却花费了我不少的时间,值得欣慰的是,当自己苦思冥想或者和其它同学一起探讨,把问题解决的时候我还是觉得获益非浅,这就是在摸索中寻求到的知识。

8

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

附录：代码

#include #include #include

#define TabSize 2000003 #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);

9

散列表的应用：插队买票的设计

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(\ return -1; } if(!(fpout=fopen(\ { 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

if(n<1||n>1000) { fprintf(fpout,\ return -1; } num++; if(num!=1) fprintf(fpout,\ for(i=0;i1000) { fprintf(fpout,\ return -1; } for(;j;--j) { fscanf(fpin,\

for(ii=0;ii

10

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

if(tempc[ii]<'A'||('Z''z'||ii>4) { fprintf(fpout,\ return -1; } ii++; } key=Find(hash,c); if(hashedx==1) { fprintf(fpout,\ return -1; } strcpy(hash[key].name,c); hash[key].info=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;

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; }

11

散列表的应用：插队买票的设计

}

} else if(*c=='D') { if(last==0) { fprintf(fpout,\ return -1; } fprintf(fpout,\ temp=head; head=queue[temp].Index; queue[temp].Index=queue[0].Index; 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 break; } }

fprintf(fpout,\fclose(fpin); fclose(fpout); return 1;

12

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