77范文网 - 专业文章范例文档资料分享平台

数据结构插队买票(4)

来源:网络收集 时间:2019-03-03 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

插队买票

置*/

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据结构插队买票(4)在线全文阅读。

数据结构插队买票(4).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/492254.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: