基于散列表的单片机快速查找算法

1、1.（1912）基于散列表的单片机快速查找算法源程序代码如下：. /*在IC卡计时收费系统的查找算法中用到了如下数据结构*/struct f/*刷卡记录的数据结构*/ unsigned char MemBNum; /*下1条记录的存储块号*/ unsigned char CardID4; /*4个字节的IC卡号*/ unsigned char CardType; /*1个字节的卡类型*/ unsigned char FirstTime2; /*首次刷卡时间*/ ;/*为了访问的方便，定义如下联合*/union h unsigned char Data8; /*8个字节的数组*/ struct

2、f Record; /*记录占8个字节*/ ;/*DataRec为联合类型变量*/ union h idata DataRec;/*为了实现存储空间的管理，定义如下全局变量*/unsigned char MemManage28;/*用于存储空间管理的28个内存单元*/unsigned char NowPoint=0; /*用于存储空间管理的数组指针*/*在散列表查找算法中用到了下列函数*/*下4个函数为采用I2C总线访问24LC16的函数，由于篇幅原因在本文中未提供原码，读者可参考其它文献*/*下4个函数中参数addr为访问24LC16时用到的11位存储地址，返回值指示读写访问是否成功*/un

3、signed char wrbyte(unsigned int addr,unsigned char odata); /*向24LC16中写一个字节，该字节在odata中。*/unsigned char rdbyte(unsigned int addr,unsigned char odata); /*从24LC16中读一个字节，读到字节在odata中。*/unsigned char wr8byte(unsigned int addr,unsigned char *mtd); /*向24LC16中写8个字节，mtd为写缓冲区首址。*/unsigned char rd8byte(unsigned

4、int addr,unsigned char *mrd); /*从24LC16中读8个字节，mrd为读缓冲区首址。*/unsigned char hash(unsigned char *ID); /*链地址法的散列表查找算法程序*/unsigned char hash_search(union h NowRec);/*哈希(hash)函数*/unsigned char compare(unsigned char *ID1,unsigned char *ID2); /*关键字比较函数*/unsigned char req_mem(void); /*存储块分配函数*/void free_mem(u

5、nsigned char MemBNum);/*释放存储块函数*/unsigned char account(union h OutRec,union h InRec); /*计时消费结帐处理函数，可根据实际情况实现*/*功能：采用链地址法的散列表查找算法，包含记录的添加与删除入口参数(NowRec)：待查找的记录返回值：为0表示无相同关键字记录，将输入记录添加到表尾，为1表示查找成功，结帐并删除该记录*/unsigned char hash_search(union h NowRec) unsigned char i,result; /*result为返回的查找结果，result=0查找失败

6、，result=1查找成功*/ unsigned char NowMemBNum; /*当前访问记录的存储块号*/ unsigned char NextMemBNum; /*下1条记录的存储块号*/ unsigned int LastRecAddr; /*链表中上1条已访问记录的首地址或链表首地址*/ unsigned int NowRecAddr; /*链表中当前访问记录的首地址*/ union h ReadRec; /*从24LC16中读到的记录*/ result=0; NowRecAddr=hash(NowRec.Record.CardID); /*调用哈希函数得到哈希地址*/ Last

7、RecAddr=NowRecAddr; /*初始化LastRecAddr*/ rdbyte(NowRecAddr,NowMemBNum); /*读得链表的首存储块号*/ NextMemBNum=NowMemBNum; /*初始化NextMemBNum*/ if(NextMemBNum=0xff) result=0; /*链表为空，无相同关键字记录*/ /*由存储块号计算得到记录的存储首地址，添加新记录时用到*/ NowRecAddr=(unsigned int)NowMemBNum*8+0x100; else while(1) NowMemBNum=NextMemBNum; /*保存当前要访问

8、记录的存储块号*/ LastRecAddr=NowRecAddr; /*保存上1条已访问记录的首地址或链表首地址*/ /*计算得到当前要访问记录的存储首地址*/ NowRecAddr=(unsigned int)NowMemBNum*8+0x100; rd8byte(NowRecAddr,ReadRec.Data); /*从链表中读取1条记录，共8个字节*/ NextMemBNum=ReadRec.Record.MemBNum; /*下1条记录的存储块号*/ if(compare(NowRec.Record.CardID,ReadRec.Record.CardID) /*比较卡号是否相等*/

9、result=1; /*相等，查找成功*/ break; if(NextMemBNum=0xff) result=0; /*已到表尾，无相同关键字记录*/ break; if(result=0) /*查找失败，添加新记录*/ i=req_mem(); /*请求分配存储块，返回空闲存储块号，并更新存储空间利用表*/ wrbyte(NowRecAddr,i); /*新记录插入表尾，更新表尾记录的"下一条记录存储块号"字段*/ NowRecAddr=i*8+0x100; /*由存储块号计算存储首地址*/ wr8byte(NowRecAddr,NowRec.Data); /*将新记

10、录写入分配的存储块中*/ if(result=1) /*查找成功，结帐并删除记录*/ account(NowRec,ReadRec); /*根据消费时间，计算消费费用并结帐*/ /*从链表中删除该记录，即将下1条记录的存储块号写入上1条记录的相应字段中*/ wrbyte(LastRecAddr,NextMemBNum); free_mem(NowMemBNum); /*更新存储空间利用表，释放该记录所占用的存储块*/ return result; /*返回查找结果*/ /*hash函数，入口参数为4字节卡号，返回值为计算所得哈希地址*/unsigned char hash(unsigned c

11、har *ID) unsigned char HashAddr; /*保存计算所得哈希地址*/ unsigned int Sum; /*将构成卡号的4个字节按字节累加所得累加和*/ Sum=0; Sum+=ID0; Sum+=ID1; Sum+=ID2; Sum+=ID3; HashAddr=Sum%224; return HashAddr; /*比较两个卡号是否相同，相同返回值为1，不同返回值为0*/unsigned char compare(unsigned char *ID1,unsigned char *ID2) unsigned char i; unsigned char CompR

12、esult; /*保存卡号比较结果*/ for(i=0;i<4;i+) if(ID1i!=ID2i) break; if(i=4) CompResult=1; /*卡号相同，返回值为1*/ else CompResult=0; /*卡号不同，返回值为0*/ return CompResult; /*存储块分配程序，调用该程序返回空闲存储块号*/unsigned char req_mem(void) unsigned char i,temp; while(1) if(MemManageNowPoint=0xff) NowPoint+; /*无空闲存储块，继续搜索*/ if(NowPoint=28) NowPoint=0; /*用于存储空间管理的内存单元为28个*/ else /*有空闲存储块，查找存储块号*/ temp=0x01; for(i=0;i<8;i+) if(MemManageNowPoint & temp)=0) break; temp=temp<<1; break; MemManageNowPoint|=temp; /* 该存储块已分配，置标志位*/ temp=NowPoint*8+i; /*