哈希表實(shí)現(xiàn)電話號碼查詢系統(tǒng)

1、?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計(jì)哈希表實(shí)現(xiàn) 號碼查詢系統(tǒng)一目的利用?數(shù)據(jù)結(jié)構(gòu)?課程的相關(guān)知識(shí)完成一個(gè)具有一定難度的綜合設(shè)計(jì)題目，利用C/C+語言進(jìn)行程序設(shè)計(jì)，并標(biāo)準(zhǔn)地完成課程設(shè)計(jì)報(bào)告。通過課程設(shè)計(jì)，穩(wěn)固和加深對線性表、棧、隊(duì)列、字符串、樹、圖、查找、排序等理論知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問題的分析建模和解決方法包括問題描述、系統(tǒng)分析、設(shè)計(jì)建模、代碼實(shí)現(xiàn)、結(jié)果分析等；提高利用計(jì)算機(jī)分析解決綜合性實(shí)際問題的根本能力。二需求分析1、 程序的功能1) 讀取數(shù)據(jù) 讀取原 本存儲(chǔ)的 信息。 讀取系統(tǒng)隨機(jī)新建 本存儲(chǔ)的 信息。2) 查找信息 根據(jù) 號碼查詢用戶信息。 根據(jù)查詢用戶信息。3) 存儲(chǔ)信息查詢無記錄的結(jié)果存入記錄

2、文檔。2、 輸出形式1) 數(shù)據(jù)文件“old.txt存放原始 號碼數(shù)據(jù)。2) 數(shù)據(jù)文件“new.txt存放有系統(tǒng)隨機(jī)生成的 號碼文件。3) 數(shù)據(jù)文件“out.txt存放未查找到的 信息。4) 查找到相關(guān)信息時(shí)顯示、地址、 號碼。3、 初步測試方案1) 從數(shù)據(jù)文件“old.txt中讀入各項(xiàng)記錄，或由系統(tǒng)隨機(jī)產(chǎn)生各記錄，并且把記錄保存到“new.txt中 。2) 分別采用偽隨機(jī)探測再散列法和再哈希法解決沖突。3) 根據(jù)查找時(shí)顯示給定用戶的記錄。4) 根據(jù) 號碼查找時(shí)顯示給定 號碼的用戶記錄。5) 將沒有查找的結(jié)果保存到結(jié)果文件Out.txt中。6) 系統(tǒng)以菜單界面工作，運(yùn)行界面友好，演示程序以用戶和

3、計(jì)算機(jī)的對話方式進(jìn)行。三概要設(shè)計(jì)1、 子函數(shù)功能int Collision_Random(int key,int i) /偽隨機(jī)數(shù)探量觀測再散列法處理沖突void Init_HashTable_by_name(string name,string phone,string address)/以為關(guān)鍵字建立哈希表int Collision_Rehash(int key,string str) /再哈希法處理沖突void Init_HashTable_by_phone(string name,string phone,string address)/以 號碼為關(guān)鍵字建立哈希表void Outfil

4、e(string name,int key) /在沒有找到時(shí)輸出未找到的記錄，翻開文件out.txt并將記錄儲(chǔ)存在文檔中void Outhash(int key) /輸出哈希表中的記錄void Rafile()/隨機(jī)生成數(shù)據(jù)，并將數(shù)據(jù)保存在new.txtvoid Init_HashTable(char*fname,int n)/建立哈希表int Search_by_name(string name)/根據(jù)查找哈希表中的記錄int Search_by_phone(string phone)/根據(jù) 號碼查找哈希表中的記錄2、 函數(shù)調(diào)用圖四詳細(xì)設(shè)計(jì)1、 主函數(shù)流程圖2、 “偽隨機(jī)探測再散列處理沖突偽

5、代碼假設(shè)對應(yīng)位置上已經(jīng)存在其他數(shù)據(jù)，那么新的關(guān)鍵字=原關(guān)鍵字+偽隨機(jī)數(shù)%哈希表長。假設(shè)新的位置上也存在其他數(shù)據(jù)，那么用偽隨機(jī)序列的下一個(gè)數(shù)求新的關(guān)鍵字，直到找到適宜的位置。3、 “再哈希法處理沖突偽代碼用“折疊法將 號碼的ASCII碼值定義為關(guān)鍵字，分別為前四位、中四位、后三位。再用“除留余數(shù)法求的新的關(guān)鍵字=原關(guān)鍵字%哈希表長。4、 “以為關(guān)鍵字建立哈希表偽代碼用“除留余數(shù)法將的ASCII碼值定義為關(guān)鍵字。假設(shè)對應(yīng)位置上存在其他數(shù)據(jù)，那么調(diào)用偽隨機(jī)處理沖突，然后將數(shù)據(jù)存入哈希表。5、 “以 號碼為關(guān)鍵字建立哈希表偽代碼用“除留余數(shù)法將 號碼的ASCII碼值定義為關(guān)鍵字。假設(shè)對應(yīng)位置上存在其他

6、數(shù)據(jù)，那么調(diào)用再哈希處理沖突。然后將數(shù)據(jù)存入哈希表。五調(diào)試分析1、程序的關(guān)鍵是掌握文件的相關(guān)操作、哈希函數(shù)的創(chuàng)立和運(yùn)用、偽隨機(jī)法處理沖突、再哈希法處理沖突等。在編程的過程中，出現(xiàn)了很多問題，如文件無法正常翻開、程序進(jìn)入死循環(huán)、無法實(shí)現(xiàn)文件的寫入操作、忘了添加頭文件等錯(cuò)誤。修改后程序運(yùn)行正確。2、創(chuàng)立“new.txt內(nèi)容用子函數(shù)來實(shí)現(xiàn)，但是原數(shù)據(jù)是從“old.txt文件中讀取的，剛開始不知道怎樣實(shí)現(xiàn)二者之間的選擇，在同學(xué)和參考書的幫助下終于得到解決。3、關(guān)于偽隨機(jī)和再哈希的相關(guān)內(nèi)容覺得很難懂，看了很久參考書才有所了解六測試結(jié)果1、 根據(jù)查找1) 查找成功2) 查找失敗3) 哈希表2、 根據(jù) 號碼

7、查找1) 號碼輸入錯(cuò)誤2) 號碼查詢成功3) 號碼查詢失敗4) 哈希表七用戶使用說明1、 選擇數(shù)據(jù)來源根據(jù)提示信息進(jìn)行操作，選擇已存在的“old.txt文件中的數(shù)據(jù)或系統(tǒng)當(dāng)前自動(dòng)生成的“new.txt文件。2、 選擇查找方式根據(jù)提示信息進(jìn)行操作，選擇“根據(jù)查找或“根據(jù) 號碼查找兩種查找方式。 3、 選擇功能根據(jù)提示信息進(jìn)行操作，選擇輸入信息或查看哈希表。4、 顯示結(jié)果5、 查看文件八課程設(shè)計(jì)總結(jié)1、 收獲學(xué)會(huì)了C+的跟蹤。更進(jìn)一步了解和熟悉了關(guān)于哈希表的運(yùn)用和文件的讀取與寫入操作。同時(shí)鍛煉了對話形式的菜單的創(chuàng)立和熟練運(yùn)用。2、 心得體會(huì)在這次數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中遇到了很多實(shí)際性的問題，在實(shí)際設(shè)計(jì)中才

8、發(fā)現(xiàn)，書本上理論性的東西與在實(shí)際運(yùn)用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯(cuò)誤思維。通過這次設(shè)計(jì)，我懂得了學(xué)習(xí)的重要性，了解到理論知識(shí)與實(shí)踐相結(jié)合的重要意義，學(xué)會(huì)了堅(jiān)持、耐心和努力，這將為自己今后的學(xué)習(xí)和工作做出了最好的典范。我覺得作為一名計(jì)科專業(yè)的學(xué)生，這次課程設(shè)計(jì)是很有意義的。更重要的是如何把自己平時(shí)所學(xué)的東西應(yīng)用到實(shí)際中。雖然自己對于這門課懂的并不多，很多根底的東西都還沒有很好的掌握，覺得很難，也沒有很有效的方法通過自身去理解，但是靠著學(xué)習(xí)，漸漸對這門課逐漸產(chǎn)生了些許的興趣，自己開始主動(dòng)學(xué)習(xí)并逐步從根底慢慢開始弄懂它。附錄：源程序#include <fstream&

9、gt;#include <iostream>#include <string>using namespace std;ifstream in_file;ofstream out_file;int D10=1,3,5,8,13,15,17,21,27,34;/偽隨機(jī)數(shù)序列int count;/當(dāng)前數(shù)據(jù)元素個(gè)數(shù)int sizeindex;/哈希表的長度char *sign;/沖突的標(biāo)志struct Datastring name;string phone;string address; Data *intermediate_data;int Collision_Random

10、(int key,int i)/偽隨機(jī)數(shù)探量觀測再散列法處理沖突int Re_key;if(signkey='1')Re_key=(key+Di)%sizeindex;return Re_key;/歸回新的要害碼return -1;void Init_HashTable_by_name(string name,string phone,string address)/以為關(guān)鍵字建立哈希表int i=0;int key;char*p;for(key=0,p=&name0;*p;p+)key=key+*p;key=key%42;while(signkey='1

11、9;)key=Collision_Random(key,i+1);if(key=-1) exit(1);count+;intermediate_=name;/將數(shù)據(jù)存入哈希表intermediate_datakey.address=address;intermediate_datakey.phone=phone;signkey='1'/設(shè)置沖突標(biāo)志int Collision_Rehash(int key,string str)/再哈希法處理沖突int Re_key;int num1=(str0-'0')*1000+(str1-'0

12、')*100+(str2-'0')*10+(str3-'0');int num2=(str4-'0')*1000+(str5-'0')*100+(str6-'0')*10+(str7-'0');int num3=(str8-'0')*100+(str9-'0')*10+(str10-'0');Re_key=num1+num2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;void Init_H

13、ashTable_by_phone(string name,string phone,string address)/以 號碼為關(guān)鍵字建立哈希表int key;char*p;for(key=0,p=&phone0;*p;p+)key=key+*p;key=key%42;while(signkey='1')key=Collision_Rehash(key,phone);count+;intermediate_=name;intermediate_datakey.address=address;intermediate_datakey.phone=p

14、hone;signkey='1'void Outfile(string name,int key)/在沒有找到時(shí)輸出未找到的記錄，翻開文件out.txt并將記錄儲(chǔ)存在文檔中if(key=-1)|(signkey='0')out_file.open("out.txt");if(out_file.fail() cout<<"n"<<"文件翻開失敗!n"<<endl;exit(1);out_file<<name<<endl;out_file.clos

15、e();void Outhash(int key)/輸出哈希表中的記錄unsigned i;if(key=-1)|(signkey='0')cout<<"n"<<"無此記錄!n"<<endl;elsefor(i=0;i<strlen(&(intermediate_0);i+)cout<<intermediate_i;for(i=0;i<8;i+)cout<<" "cout<<int

16、ermediate_datakey.phone;for(i=0;i<8;i+)cout<<" "cout<<intermediate_datakey.address<<endl;void Rafile()/隨機(jī)生成數(shù)據(jù)，并將數(shù)據(jù)保存在new.txtint i,j;out_file.open("new.txt");if(out_file.fail()cout<<"n"<<"文件翻開失敗!n"<<endl;exit(1);for(j=0;j&

17、lt;30;j+)string name=""for(i=0;i<20;i+)name+=rand()%26+'a'out_file<<name<<" "string phone=""for(i=0;i<11;i+)phone+=rand()%10+'0'out_file<<phone<<" "string address=""for(i=0;i<29;i+)address+=rand()%26+&

18、#39;a'address+=','out_file<<address<<endl; out_file<<"*"out_file.close();void Init_HashTable(char*fname,int n)/建立哈希表string name=""string phone=""string address=""int i,j;in_file.open(fname);if(in_file.fail()cout<<"n&quo

19、t;<<"文件翻開失敗!n"<<endl;exit(1);while(!in_file.eof()char* str=new char100;name=""phone=""address=""in_file.getline(str,100,'n');/按行讀入數(shù)據(jù)if(str0='*')/判斷數(shù)據(jù)結(jié)束break;i=0;while(stri<=97|stri>=122)i+;for(;stri!=' 'i+)name+=stri;w

20、hile(stri=' ')i+;for(j=0;stri!=' 'j+,i+)phone+=stri;while(stri=' ')i+;for(j=0;stri!=','j+,i+)address+=stri;if(n=1)Init_HashTable_by_name(name,phone,address);/以為關(guān)鍵字else Init_HashTable_by_phone(name,phone,address);/以 號碼為關(guān)鍵字delete str;in_file.close();int Search_by_name(s

21、tring name)/根據(jù)查找哈希表中的記錄int i=0;int j=1;int key;char*p;for(key=0,p=&name0;*p;p+)key=key+*p;key=key%42;while(signkey='1'&&(intermediate_!=name)key=Collision_Random(key,i+1);j+;if(j=count)return -1;return key;int Search_by_phone(string phone)/根據(jù) 號碼查找哈希表中的記錄int key;char*p

22、;for(key=0,p=&phone0;*p;p+)key=key+*p;key=key%42;int j=1;while(signkey='1'&&(intermediate_datakey.phone!=phone)key=Collision_Rehash(key,phone);j+;if(j=count)return-1;return key;void main()count=0;sizeindex=50;int i,k;int ch;char *Fname;sign=new charsizeindex;intermediate_data=new

23、 Datasizeindex;for(i=0;i<sizeindex;i+)signi='0'signi='0'for(i=0;i<sizeindex;i+)intermediate_=""intermediate_datai.phone=""intermediate_datai.address="" cout<<"§*§"<<endl;cout<<"§* *§&qu

24、ot;<<endl;cout<<"§* 請選擇用于查找的數(shù)據(jù)來源 *§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 1 . old.TXT *§"<<endl;cout<<"§* 2 . 隨 機(jī) 生 成 *§"<<endl;cout<<"§* 0 . 退 出 程 序 *

25、§"<<endl; cout<<"§*§"<<endl; docout<<"n"<< " 請輸入選擇 : n" cin>>k;switch(k)case 0:return;case 1:Fname="old.txt"break;case 2:Rafile();Fname="new.txt"break; default:cout<<"輸入序號有誤，請重新輸入!n&q

26、uot;<<endl;while(k!=1)&&(k!=2)&&(k!=0); /system("cls"); cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請 選 擇 查 找 方 式 *§"<<endl;cout<<"§* *§"<&

27、lt;endl;cout<<"§* 1 . 根 據(jù) 姓 名 查 找 *§"<<endl;cout<<"§* 2 . 根 據(jù) 電 話 號 查 找 *§"<<endl;cout<<"§* *§"<<endl; cout<<"§*§"<<endl;docout<<"n"<< " 請輸入選擇 :

28、n" cin>>ch;if(ch!=1&&ch!=2)cout<<" 輸入序號有誤，請重新輸入!n"<<endl;while(ch!=1)&&(ch!=2); /system("cls");Init_HashTable(Fname,ch);while(ch=1)int choice;cout<<"§*§"<<endl;cout<<"§* *§"<<en

29、dl;cout<<"§* 請 選 擇 功 能 *§"<<endl; cout<<"§* *§"<<endl;cout<<"§* 1 . 輸 入 姓 名 查 找 數(shù) 據(jù) *§"<<endl;cout<<"§* 2 . 顯 示 哈 希 表 *§"<<endl;cout<<"§* 0 . 退 出 程 序! *

30、7;"<<endl;cout<<"§* *§"<<endl; cout<<"§*§"<<endl;docout<<"n"<< " 請輸入選擇 : n"cin>>choice; switch(choice) case 1:int key1;string name;cout<<"n"<<" 請輸入: n"cin&

31、gt;>name;key1=Search_by_name(name);Outfile(name,key1); cout<<"n"<<"查找結(jié)果:n"<<endl;Outhash(key1);break;case 2: cout<<"n"<<" 哈希表: n"<<endl;for(i=0;i<sizeindex;i+)if(signi!='0')cout<<"* " Outhash(i)

32、; cout<<"* *"<<endl;break;case 0:return; default:cout<<" 輸入序號有誤，請重新輸入!n"<<endl; while(choice!=1)&&(choice!=2)&&(choice!=0);while(ch=2)int choice;cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請 選 擇 功 能 *§"<<endl;cout<<"§* 1 . 輸 入 電 話 查 找 數(shù) 據(jù) *§"<<endl;cout<&l