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); /*读得链表的首存储块号*/NextMemBNum=NowMemBNum; /*初始化NextMemBNum*/if(NextMemBNum==0xff){result=0; /*链表为空，无相同关键字记录*//*由存储块号计算得到记录的存储首地址，添加新记录时用到*/NowRecAddr=(unsigned int)NowMemBNum*8+0x100;}else{while(1){NowMemBNum=NextMemBNum; /*保存当前要访问记录的存储块号*/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)) /*比较卡号是否相等*/{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); /*将新记录写入分配的存储块中*/}if(result==1) /*查找成功，结帐并删除记录*/{account(NowRec,ReadRec); /*根据消费时间，计算消费费用并结帐*//*从链表中删除该记录，即将下1条记录的存储块号写入上1条记录的相应字段中*/wrbyte(LastRecAddr,NextMemBNum);free_mem(NowMemBNum); /*更新存储空间利用表，释放该记录所占用的存储块*/}return result; /*返回查找结果*/}/*hash函数，入口参数为4字节卡号，返回值为计算所得哈希地址*/unsigned char hash(unsigned char *ID){unsigned char HashAddr; /*保存计算所得哈希地址*/unsigned int Sum; /*将构成卡号的4个字节按字节累加所得累加和*/Sum=0;Sum+=ID[0]; Sum+=ID[1];Sum+=ID[2]; Sum+=ID[3];HashAddr=Sum%224;return HashAddr;}/*比较两个卡号是否相同，相同返回值为1，不同返回值为0*/unsigned char compare(unsigned char *ID1,unsigned char *ID2){unsigned char i;unsigned char CompResult; /*保存卡号比较结果*/for(i=0;i<4;i++) if(ID1[i]!=ID2[i]) 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(MemManage[NowPoint]==0xff){NowPoint++; /*无空闲存储块，继续搜索*/if(NowPoint==28) NowPoint=0; /*用于存储空间管理的内存单元为28个*/ }else{/*有空闲存储块，查找存储块号*/temp=0x01;for(i=0;i<8;i++){if((MemManage[NowPoint] & temp)==0) break;temp=temp<<1;}break;}}MemManage[NowPoint]|=temp; /* 该存储块已分配，置标志位*/temp=NowPoint*8+i; /* 计算得到存储块号*/return temp; /* 返回存储块号*/}/*存储块释放程序，清除标志位，释放指定存储块*/void free_mem(unsigned char MemBNum){unsigned char i,j;i=MemBNum/8; MemBNum%=8;j=0x01; j<<=MemBNum;MemManage[i]^=j; /*清除标志位，释放指定存储块*/}.。