基于散列表的單片機(jī)快速查找算法

1、1.（1912）基于散列表的單片機(jī)快速查找算法源程序代碼如下：. /*在IC卡計(jì)時(shí)收費(fèi)系統(tǒng)的查找算法中用到了如下數(shù)據(jù)結(jié)構(gòu)*/struct f/*刷卡記錄的數(shù)據(jù)結(jié)構(gòu)*/ unsigned char MemBNum; /*下1條記錄的存儲(chǔ)塊號(hào)*/ unsigned char CardID4; /*4個(gè)字節(jié)的IC卡號(hào)*/ unsigned char CardType; /*1個(gè)字節(jié)的卡類型*/ unsigned char FirstTime2; /*首次刷卡時(shí)間*/ ;/*為了訪問的方便，定義如下聯(lián)合*/union h unsigned char Data8; /*8個(gè)字節(jié)的數(shù)組*/ struct

2、f Record; /*記錄占8個(gè)字節(jié)*/ ;/*DataRec為聯(lián)合類型變量*/ union h idata DataRec;/*為了實(shí)現(xiàn)存儲(chǔ)空間的管理，定義如下全局變量*/unsigned char MemManage28;/*用于存儲(chǔ)空間管理的28個(gè)內(nèi)存單元*/unsigned char NowPoint=0; /*用于存儲(chǔ)空間管理的數(shù)組指針*/*在散列表查找算法中用到了下列函數(shù)*/*下4個(gè)函數(shù)為采用I2C總線訪問24LC16的函數(shù)，由于篇幅原因在本文中未提供原碼，讀者可參考其它文獻(xiàn)*/*下4個(gè)函數(shù)中參數(shù)addr為訪問24LC16時(shí)用到的11位存儲(chǔ)地址，返回值指示讀寫訪問是否成功*/un

3、signed char wrbyte(unsigned int addr,unsigned char odata); /*向24LC16中寫一個(gè)字節(jié)，該字節(jié)在odata中。*/unsigned char rdbyte(unsigned int addr,unsigned char odata); /*從24LC16中讀一個(gè)字節(jié)，讀到字節(jié)在odata中。*/unsigned char wr8byte(unsigned int addr,unsigned char *mtd); /*向24LC16中寫8個(gè)字節(jié)，mtd為寫緩沖區(qū)首址。*/unsigned char rd8byte(unsigned

4、int addr,unsigned char *mrd); /*從24LC16中讀8個(gè)字節(jié)，mrd為讀緩沖區(qū)首址。*/unsigned char hash(unsigned char *ID); /*鏈地址法的散列表查找算法程序*/unsigned char hash_search(union h NowRec);/*哈希(hash)函數(shù)*/unsigned char compare(unsigned char *ID1,unsigned char *ID2); /*關(guān)鍵字比較函數(shù)*/unsigned char req_mem(void); /*存儲(chǔ)塊分配函數(shù)*/void free_mem(u

5、nsigned char MemBNum);/*釋放存儲(chǔ)塊函數(shù)*/unsigned char account(union h OutRec,union h InRec); /*計(jì)時(shí)消費(fèi)結(jié)帳處理函數(shù)，可根據(jù)實(shí)際情況實(shí)現(xiàn)*/*功能：采用鏈地址法的散列表查找算法，包含記錄的添加與刪除入口參數(shù)(NowRec)：待查找的記錄返回值：為0表示無相同關(guān)鍵字記錄，將輸入記錄添加到表尾，為1表示查找成功，結(jié)帳并刪除該記錄*/unsigned char hash_search(union h NowRec) unsigned char i,result; /*result為返回的查找結(jié)果，result=0查找失敗

6、，result=1查找成功*/ unsigned char NowMemBNum; /*當(dāng)前訪問記錄的存儲(chǔ)塊號(hào)*/ unsigned char NextMemBNum; /*下1條記錄的存儲(chǔ)塊號(hào)*/ unsigned int LastRecAddr; /*鏈表中上1條已訪問記錄的首地址或鏈表首地址*/ unsigned int NowRecAddr; /*鏈表中當(dāng)前訪問記錄的首地址*/ union h ReadRec; /*從24LC16中讀到的記錄*/ result=0; NowRecAddr=hash(NowRec.Record.CardID); /*調(diào)用哈希函數(shù)得到哈希地址*/ Last

7、RecAddr=NowRecAddr; /*初始化LastRecAddr*/ rdbyte(NowRecAddr,NowMemBNum); /*讀得鏈表的首存儲(chǔ)塊號(hào)*/ NextMemBNum=NowMemBNum; /*初始化NextMemBNum*/ if(NextMemBNum=0xff) result=0; /*鏈表為空，無相同關(guān)鍵字記錄*/ /*由存儲(chǔ)塊號(hào)計(jì)算得到記錄的存儲(chǔ)首地址，添加新記錄時(shí)用到*/ NowRecAddr=(unsigned int)NowMemBNum*8+0x100; else while(1) NowMemBNum=NextMemBNum; /*保存當(dāng)前要訪問

8、記錄的存儲(chǔ)塊號(hào)*/ LastRecAddr=NowRecAddr; /*保存上1條已訪問記錄的首地址或鏈表首地址*/ /*計(jì)算得到當(dāng)前要訪問記錄的存儲(chǔ)首地址*/ NowRecAddr=(unsigned int)NowMemBNum*8+0x100; rd8byte(NowRecAddr,ReadRec.Data); /*從鏈表中讀取1條記錄，共8個(gè)字節(jié)*/ NextMemBNum=ReadRec.Record.MemBNum; /*下1條記錄的存儲(chǔ)塊號(hào)*/ if(compare(NowRec.Record.CardID,ReadRec.Record.CardID) /*比較卡號(hào)是否相等*/

9、result=1; /*相等，查找成功*/ break; if(NextMemBNum=0xff) result=0; /*已到表尾，無相同關(guān)鍵字記錄*/ break; if(result=0) /*查找失敗，添加新記錄*/ i=req_mem(); /*請(qǐng)求分配存儲(chǔ)塊，返回空閑存儲(chǔ)塊號(hào)，并更新存儲(chǔ)空間利用表*/ wrbyte(NowRecAddr,i); /*新記錄插入表尾，更新表尾記錄的"下一條記錄存儲(chǔ)塊號(hào)"字段*/ NowRecAddr=i*8+0x100; /*由存儲(chǔ)塊號(hào)計(jì)算存儲(chǔ)首地址*/ wr8byte(NowRecAddr,NowRec.Data); /*將新記

10、錄寫入分配的存儲(chǔ)塊中*/ if(result=1) /*查找成功，結(jié)帳并刪除記錄*/ account(NowRec,ReadRec); /*根據(jù)消費(fèi)時(shí)間，計(jì)算消費(fèi)費(fèi)用并結(jié)帳*/ /*從鏈表中刪除該記錄，即將下1條記錄的存儲(chǔ)塊號(hào)寫入上1條記錄的相應(yīng)字段中*/ wrbyte(LastRecAddr,NextMemBNum); free_mem(NowMemBNum); /*更新存儲(chǔ)空間利用表，釋放該記錄所占用的存儲(chǔ)塊*/ return result; /*返回查找結(jié)果*/ /*hash函數(shù)，入口參數(shù)為4字節(jié)卡號(hào)，返回值為計(jì)算所得哈希地址*/unsigned char hash(unsigned c

11、har *ID) unsigned char HashAddr; /*保存計(jì)算所得哈希地址*/ unsigned int Sum; /*將構(gòu)成卡號(hào)的4個(gè)字節(jié)按字節(jié)累加所得累加和*/ Sum=0; Sum+=ID0; Sum+=ID1; Sum+=ID2; Sum+=ID3; HashAddr=Sum%224; return HashAddr; /*比較兩個(gè)卡號(hào)是否相同，相同返回值為1，不同返回值為0*/unsigned char compare(unsigned char *ID1,unsigned char *ID2) unsigned char i; unsigned char CompR

12、esult; /*保存卡號(hào)比較結(jié)果*/ for(i=0;i<4;i+) if(ID1i!=ID2i) break; if(i=4) CompResult=1; /*卡號(hào)相同，返回值為1*/ else CompResult=0; /*卡號(hào)不同，返回值為0*/ return CompResult; /*存儲(chǔ)塊分配程序，調(diào)用該程序返回空閑存儲(chǔ)塊號(hào)*/unsigned char req_mem(void) unsigned char i,temp; while(1) if(MemManageNowPoint=0xff) NowPoint+; /*無空閑存儲(chǔ)塊，繼續(xù)搜索*/ if(NowPoint=28) NowPoint=0; /*用于存儲(chǔ)空間管理的內(nèi)存單元為28個(gè)*/ else /*有空閑存儲(chǔ)塊，查找存儲(chǔ)塊號(hào)*/ temp=0x01; for(i=0;i<8;i+) if(MemManageNowPoint & temp)=0) break; temp=temp<<1; break; MemManageNowPoint|=temp; /* 該存儲(chǔ)塊已分配，置標(biāo)志位*/ temp=NowPoint*8+i; /*