#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 4 //标签个数
#define N 3 //标签位数
//定义单链队列结构体
typedef struct QNode{
char *qelem;
struct QNode *next;
}QNode,*QueuePtr;//定义了一个结点数据类型QNode和一个指针数据类型QueuePtr(指向QNode)
typedef struct
QueuePtr front;//头指针，指向头结点
QueuePtr rear;//尾指针，指向尾结点
}LinkQueue;//定义了一个链队列数据类型LinkQueue
//初始化队列
void InitQueue(LinkQueue *Q){
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)+N+1);
(*Q).front->next=NULL;
}
//入队
void EnQueue(LinkQueue *Q,char *elem){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode)+N+1);
p->qelem=(char *)p+sizeof(QNode);
strcpy(p->qelem,elem);
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
}
//出队
QNode* DeQueue(LinkQueue *Q){
QueuePtr p;
p=(*Q).front->next;
(*Q).front->next=p->next;
p->next=NULL;
return(p);
}
//判断队列是否为空
int IsEmpty(LinkQueue Q){
if(Q.front->next==NULL) return(1);//队列为空，返回1
else return(0);
}
//前缀检索函数
int Prefix(char *q1,char *q2){
int flag=0;
for(;*q1!='\0';){
if(*q1==*q2) {q1++;q2++;}
else {flag=1;break;}
}
if(flag==0) return(1);//q1是q2的前缀
else return(0);
}
//打印队列的当前值
void PrintQueue(LinkQueue *Q){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode)+N+1);
p=(*Q).front->next;
printf("Q=< ");
for(;p!=NULL;p=p->next){
printf("%s ",p->qelem);
}
printf(">\n");
}
void main(){
LinkQueue Q;
InitQueue(&Q);
char *a="0";
char *b="1";
EnQueue(&Q,a);
EnQueue(&Q,b);
while(!IsEmpty(Q)){
PrintQueue(&Q);
//pointer指向标签ID组成的字符串：
//这里的标签ID个数、位数要分别与宏定义中的M、N保持一致。
char *pointer="000,001,101,110";
int count=0;
int i=0;
printf("发送请求%s\n",Q.front->next->qelem);
for(;i<M;i++,pointer+=(N+1)*sizeof(char)){
if(Prefix(Q. front->next->qelem,pointer)) count++;
}
QNode *pp=DeQueue(&Q);
printf("Update Q:");
PrintQueue(&Q);
char s[N+1];
strcpy(s,pp->qelem);
printf("响应的标签数count=%d\n",count);
if(count==0) {printf("没有标签响应\n");printf("\n");}
else if(count>=2){
EnQueue(&Q,strcat(pp->qelem,"0"));
EnQueue(&Q,strcat(s,"1"));
printf("冲突，重置Q：");
PrintQueue(&Q);
printf("\n");
}
else {printf("读标签\n");printf("\n");}
}
}