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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈希表實(shí)現(xiàn)電話號(hào)碼查詢系統(tǒng)一目的利用數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí)完成一個(gè)具有一定難度的綜合設(shè)計(jì)題目，利用C/C+語言進(jìn)行程序設(shè)計(jì)，并規(guī)范地完成課程設(shè)計(jì)報(bào)告。通過課程設(shè)計(jì)，鞏固和加深對(duì)線性表、棧、隊(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ù)電話號(hào)碼查詢用戶信息。 根據(jù)姓名查詢用戶信息。3) 存儲(chǔ)信息查詢無記錄的

2、結(jié)果存入記錄文檔。2、 輸出形式1) 數(shù)據(jù)文件“old.txt”存放原始電話號(hào)碼數(shù)據(jù)。2) 數(shù)據(jù)文件“new.txt”存放有系統(tǒng)隨機(jī)生成的電話號(hào)碼文件。3) 數(shù)據(jù)文件“out.txt”存放未查找到的電話信息。4) 查找到相關(guān)信息時(shí)顯示姓名、地址、電話號(hào)碼。3、 初步測(cè)試計(jì)劃1) 從數(shù)據(jù)文件“old.txt”中讀入各項(xiàng)記錄，或由系統(tǒng)隨機(jī)產(chǎn)生各記錄，并且把記錄保存到“new.txt”中 。2) 分別采用偽隨機(jī)探測(cè)再散列法和再哈希法解決沖突。3) 根據(jù)姓名查找時(shí)顯示給定姓名用戶的記錄。4) 根據(jù)電話號(hào)碼查找時(shí)顯示給定電話號(hào)碼的用戶記錄。5) 將沒有查找的結(jié)果保存到結(jié)果文件Out.txt中。6) 系統(tǒng)

3、以菜單界面工作，運(yùn)行界面友好，演示程序以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。三概要設(shè)計(jì)1、 子函數(shù)功能int Collision_Random(int key,int i) /偽隨機(jī)數(shù)探量觀測(cè)再散列法處理沖突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)

4、/以電話號(hào)碼為關(guān)鍵字建立哈希表void Outfile(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ù)電話號(hào)碼查找哈希表中的記錄2、 函數(shù)調(diào)用圖四詳

5、細(xì)設(shè)計(jì)1、 主函數(shù)流程圖2、 “偽隨機(jī)探測(cè)再散列處理沖突”偽代碼若對(duì)應(yīng)位置上已經(jīng)存在其他數(shù)據(jù)，則新的關(guān)鍵字=（原關(guān)鍵字+偽隨機(jī)數(shù)）%哈希表長(zhǎng)。若新的位置上也存在其他數(shù)據(jù)，則用偽隨機(jī)序列的下一個(gè)數(shù)求新的關(guān)鍵字，直到找到合適的位置。3、 “再哈希法處理沖突”偽代碼用“折疊法”將電話號(hào)碼的ASCII碼值定義為關(guān)鍵字，分別為前四位、中四位、后三位。再用“除留余數(shù)法”求的新的關(guān)鍵字=原關(guān)鍵字%哈希表長(zhǎng)。4、 “以姓名為關(guān)鍵字建立哈希表”偽代碼用“除留余數(shù)法”將姓名的ASCII碼值定義為關(guān)鍵字。若對(duì)應(yīng)位置上存在其他數(shù)據(jù)，則調(diào)用偽隨機(jī)處理沖突，然后將數(shù)據(jù)存入哈希表。5、 “以電話號(hào)碼為關(guān)鍵字建立哈希表”偽代

6、碼用“除留余數(shù)法”將電話號(hào)碼的ASCII碼值定義為關(guān)鍵字。若對(duì)應(yīng)位置上存在其他數(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)容覺得很難懂，看了很久參考書才有所了解

7、六測(cè)試結(jié)果1、 根據(jù)姓名查找1) 姓名查找成功2) 姓名查找失敗3) 哈希表2、 根據(jù)電話號(hào)碼查找1) 電話號(hào)碼輸入錯(cuò)誤2) 電話號(hào)碼查詢成功3) 電話號(hào)碼查詢失敗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ù)電話號(hào)碼查找”兩種查找方式。 3、 選擇功能根據(jù)提示信息進(jìn)行操作，選擇輸入已知信息或查看哈希表。4、 顯示結(jié)果5、 查看文件八課程設(shè)計(jì)總結(jié)1、 收獲學(xué)會(huì)了C+的跟蹤。更進(jìn)一步了解和熟悉了關(guān)于哈希表的運(yùn)用和文件的讀取與

8、寫入操作。同時(shí)鍛煉了對(duì)話形式的菜單的創(chuàng)建和熟練運(yùn)用。2、 心得體會(huì)在這次數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)中遇到了很多實(shí)際性的問題，在實(shí)際設(shè)計(jì)中才發(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í)際中。雖然自己對(duì)于這門課懂的并不多，很多基礎(chǔ)的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學(xué)習(xí)，漸漸對(duì)這

9、門課逐漸產(chǎn)生了些許的興趣，自己開始主動(dòng)學(xué)習(xí)并逐步從基礎(chǔ)慢慢開始弄懂它。附錄：源程序#include <fstream>#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;/哈希表的長(zhǎng)度char *sign;/沖突的標(biāo)志struct Datastring name;string phon

10、e;string address; Data *intermediate_data;int Collision_Random(int key,int i)/偽隨機(jī)數(shù)探量觀測(cè)再散列法處理沖突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,

11、p=&name0;*p;p+)key=key+*p;key=key%42;while(signkey='1')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)/

12、再哈希法處理沖突int Re_key;int num1=(str0-'0')*1000+(str1-'0')*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+n

13、um2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;void Init_HashTable_by_phone(string name,string phone,string address)/以電話號(hào)碼為關(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;

14、intermediate_datakey.address=address;intermediate_datakey.phone=phone;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"&l

15、t;<endl;exit(1);out_file<<name<<endl;out_file.close();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_datakey

16、.namei;for(i=0;i<8;i+)cout<<" "cout<<intermediate_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

17、"<<"文件打開失敗!n"<<endl;exit(1);for(j=0;j<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<<" "s

18、tring address=""for(i=0;i<29;i+)address+=rand()%26+'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

19、 i,j;in_file.open(fname);if(in_file.fail()cout<<"n"<<"文件打開失敗!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(

20、stri<=97|stri>=122)i+;for(;stri!=' 'i+)name+=stri;while(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,phon

21、e,address);/以電話號(hào)碼為關(guān)鍵字delete str;in_file.close();int Search_by_name(string 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;ret

22、urn key;int Search_by_phone(string phone)/根據(jù)電話號(hào)碼查找哈希表中的記錄int key;char*p;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;

23、int i,k;int ch;char *Fname;sign=new charsizeindex;intermediate_data=new 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<<&qu

24、ot;§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請(qǐng)選擇用于查找的數(shù)據(jù)來源 *§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 1 . old.TXT *§"<<endl;cout<<"§* 2 . 隨

25、機(jī) 生 成 *§"<<endl;cout<<"§* 0 . 退 出 程 序 *§"<<endl; cout<<"§*§"<<endl; docout<<"n"<< " 請(qǐng)輸入選擇 : n" cin>>k;switch(k)case 0:return;case 1:Fname="old.txt"break;case 2:Rafile();Fna

26、me="new.txt"break; default:cout<<"輸入序號(hào)有誤，請(qǐng)重新輸入!n"<<endl;while(k!=1)&&(k!=2)&&(k!=0); /system("cls"); cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請(qǐng) 選 擇 查 找 方 式

27、 *§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 1 . 根 據(jù) 姓 名 查 找 *§"<<endl;cout<<"§* 2 . 根 據(jù) 電 話 號(hào) 查 找 *§"<<endl;cout<<"§* *§"<<endl; cout<<"§*§

28、;"<<endl;docout<<"n"<< " 請(qǐng)輸入選擇 : n" cin>>ch;if(ch!=1&&ch!=2)cout<<" 輸入序號(hào)有誤，請(qǐng)重新輸入!n"<<endl;while(ch!=1)&&(ch!=2); /system("cls");Init_HashTable(Fname,ch);while(ch=1)int choice;cout<<"§*

29、67;"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請(qǐng) 選 擇 功 能 *§"<<endl; cout<<"§* *§"<<endl;cout<<"§* 1 . 輸 入 姓 名 查 找 數(shù) 據(jù) *§"<<endl;cout<<"§* 2 . 顯 示 哈 希 表

30、 *§"<<endl;cout<<"§* 0 . 退 出 程 序! *§"<<endl;cout<<"§* *§"<<endl; cout<<"§*§"<<endl;docout<<"n"<< " 請(qǐng)輸入選擇 : n"cin>>choice; switch(choice) case 1:int ke

31、y1;string name;cout<<"n"<<" 請(qǐng)輸入姓名: n"cin>>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<

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