qfy4.c

rfid修剪枝二进制搜索算法

/* Note:Your choice is C IDE */
#include "stdio.h"
#include <stdlib.h>
#include <fcntl.h>
#include <time.h> 
struct node{
    int  d;
    int   level;
    struct node *l;
    struct node *r;
};
struct node *root=NULL;
FILE *fd;
static int r=1;
static int idle=0,collision=0,effect=0;
int create_tree( struct node **root ,int n,int level);
int call(int  EPC,int m);
int del_zero(int *EPC,int *n);
int set_HighNovalidBitToZero(int *pEPC,int *pn);
int increase(int *pEPC,int *pbitnum);
int totalnode=520;

int myrandom(int n) 
{ 
   int i; 
   time_t t; 
   srand((unsigned) time(&t)); 
   return rand()%n;
}

int create_tree( struct node **pr ,int n,int level)
{
    int *p,ld,rd;
    int  leveltemp;
    leveltemp=level;
    totalnode--;
    /*
    if(level>7)
      return -1;*/
    *pr=(struct node *)malloc(sizeof(struct node));
    if(*pr==NULL)
    	{
         printf("can't malloc*****\n");
         exit(-1);
    	}
   (*pr)->d=n;
   (*pr)->level=level;
   (*pr)->r=(*pr)->l=NULL;
   leveltemp++;
   if(leveltemp>8)
   	return;
    do{ld=myrandom(n);rd=n-ld;}while(ld>(1<<(8-leveltemp))||rd>(1<<(8-leveltemp)));
    fprintf(fd,"ld=%d\n",ld);
    rd=n-ld;
    fprintf(fd,"rd=%d\n",rd);
    fprintf(fd,"level=%d\n",(*pr)->level);
    if(ld>0)
      create_tree(&((*pr)->l),ld,leveltemp);
    if(rd>0)
    create_tree(&((*pr)->r),rd,leveltemp);
    /*return 0;*/
}

int call(int  EPC,int m)
{
    int len;
    struct node *p;
    p=root;
    /*printf("in call fun \n");*/
    if(!m)
        {
         /*printf("coll\n");	*/
         return p->d;
    	}

    len=1;
    while(len<=m)
    	{
    	 /*printf("in while of call\n");	*/
         if(EPC&(1<<(8-len)))
            {  
            	p=p->r;
            }	
         else
            p=p->l;
         len++;   
    	}
   /* printf("p***->d=%d\n",p->d);	
    if(p->d==1)
       effect++;
    else if(p->d==0)
        idle++;
    else if(p->d >1)
        collision++;*/
    return p->d;
}

int del_zero(int *EPC,int *n)
{   int epctemp;
    int m;
    m=*n;
    epctemp=*EPC;
    epctemp>>=(8-m);
   /* printf("ad=%x\n",epctemp);*/
    while(!(epctemp%2))
        {epctemp>>=1;
         m--;
        }
    printf("del_zero  epctemp=%x\n",epctemp);  
    epctemp<<=(8-m);  
    *EPC=epctemp;
  /*  printf("m=%d\n",m);*/
    *n=m;
    return 0;
}

int set_HighNovalidBitToZero(int *pEPC,int *pn)
{
    int EPC,n;
    EPC=*pEPC;
    n=*pn;
    EPC>>=(8-n-1);
    EPC=EPC&0xfe;
    EPC<<=(8-n-1);
    *pEPC=EPC;
    n++;
    *pn=n;
   printf("set_HighNovalidBitToZero EPC=%x\n",EPC);
    printf("set_HighNovalidBitToZero *pn=%d\n",*pn);
}

int increase(int *pEPC,int *pbitnum)
{
    int epctemp,bittemp;
    epctemp=*pEPC;
    bittemp=*pbitnum;
    epctemp>>=(8-bittemp);
    epctemp++;
    epctemp<<=(8-bittemp);
    printf("increase epctemp=%x\n",epctemp);
    *pEPC=epctemp;
    printf("increase *pEPC=%x\n",*pEPC);
    return 0;
}
 /*
main()
{int temp1=0xff,temp2=4;
    set_HighNovalidBitToZero(&temp1,&temp2);
   increase(&temp1,&temp2);
    del_zero(&temp1,&temp2);
    printf("temp1=%x  %d\n",temp1,temp2);
}
*/


main()
{
    int tagnu;
    int EPC=0xff,bitnum=0;
    int flag;
    int level0=0;
    fd=fopen("e:\\re.txt","a");
    if(fd==NULL)
      {printf("can't open file\n");
       exit(-1);
      }   
    
    printf("input the total tag numbers\n");
    scanf("%d",&tagnu);
    create_tree(&root,tagnu,level0);
	 do
        {
            flag=call(EPC,bitnum);
            fprintf(fd,"flag=%d\n",flag);
            if(flag >=2)
        		{
        		collision++;	
        		fprintf(fd,"1EPC=%x  bitnum=%d\n",EPC,bitnum);
                set_HighNovalidBitToZero(&EPC,&bitnum);
            	continue;
        		}
            else if(!flag)
        		{
        		idle++;	
        		fprintf(fd,"2EPC=%x bitnum=%d\n",EPC,bitnum);
                increase(&EPC,&bitnum);
                continue;
        		}
                 else if(flag==1)
                 	{
                 	fprintf(fd,"3EPC=%x bitnum=%d\n",EPC,bitnum);
                 	effect++;	
                	increase(&EPC,&bitnum);
                	del_zero(&EPC,&bitnum);
                	if(effect==tagnu)
                     {
                     	break;
                     }	
                     continue;                   
                 	}
        }while(1) ;
       
       /* fprintf(fd,"co=%d idle=%d effect=%d \n",collision,idle,effect);*/
       printf("co=%d idle=%d effect=%d \n",collision,idle,effect);


}