插队买票
置*/
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' { 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)在线全文阅读。
相关推荐: