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

1.（1912）《基于散列表的单片机快速查找算法》 源程序代码如下： . /*在IC卡计时收费系统的查找算法中用到了如下数据结构*/ struct f　　　/*刷卡记录的数据结构*/ { unsigned char MemBNum; /*下1条记录的存储块号*/ unsigned char CardID[4]; /*4个字节的IC卡号*/ unsigned char CardType; /*1个字节的卡类型*/ unsigned char FirstTime[2]; /*首次刷卡时间*/ }; /*为了访问的方便，定义如下联合*/ union h { unsigned char Data[8]; /*8个字节的数组*/ struct f Record; /*记录占8个字节*/ }; /*DataRec为联合类型变量*/ union h idata DataRec; /*为了实现存储空间的管理，定义如下全局变量*/ unsigned char MemManage[28];　　/*用于存储空间管理的28个内存单元*/ unsigned char NowPoint=0;　　　 /*用于存储空间管理的数组指针*/ /*在散列表查找算法中用到了下列函数*/ /*下4个函数为采用I2C总线访问24LC16的函数，由于篇幅原因在本文中未提供原码，读者可参考其它文献*/ /*下4个函数中参数addr为访问24LC16时用到的11位存储地址，返回值指示读写访问是否成功*/ unsigned 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 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(unsigned 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查找失败，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); /*调用哈希函数得到哈希地址*/ LastRecAddr=NowRecAddr; /*初始化LastRecAddr*/ rdbyte(NowRecAddr,NowMemBNum); /