1、數據結構課程設計哈希表實現電話號碼查詢系統一目的利用數據結構課程的相關知識完成一個具有一定難度的綜合設計題目，利用C/C+語言進行程序設計，并規范地完成課程設計報告。通過課程設計，鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現實復雜問題的分析建模和解決方法（包括問題描述、系統分析、設計建模、代碼實現、結果分析等）；提高利用計算機分析解決綜合性實際問題的基本能力。二需求分析1、 程序的功能1) 讀取數據 讀取原電話本存儲的電話信息。 讀取系統隨機新建電話本存儲的電話信息。2) 查找信息 根據電話號碼查詢用戶信息。 根據姓名查詢用戶信息。3) 存儲信息查詢無記錄的

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

3、以菜單界面工作，運行界面友好，演示程序以用戶和計算機的對話方式進行。三概要設計1、 子函數功能int Collision_Random(int key,int i) /偽隨機數探量觀測再散列法處理沖突void Init_HashTable_by_name(string name,string phone,string address)/以姓名為關鍵字建立哈希表int Collision_Rehash(int key,string str) /再哈希法處理沖突void Init_HashTable_by_phone(string name,string phone,string address)

4、/以電話號碼為關鍵字建立哈希表void Outfile(string name,int key) /在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中void Outhash(int key) /輸出哈希表中的記錄void Rafile()/隨機生成數據，并將數據保存在new.txtvoid Init_HashTable(char*fname,int n)/建立哈希表int Search_by_name(string name)/根據姓名查找哈希表中的記錄int Search_by_phone(string phone)/根據電話號碼查找哈希表中的記錄2、 函數調用圖四詳

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

6、碼用“除留余數法”將電話號碼的ASCII碼值定義為關鍵字。若對應位置上存在其他數據，則調用再哈希處理沖突。然后將數據存入哈希表。五調試分析1、程序的關鍵是掌握文件的相關操作、哈希函數的創建和運用、偽隨機法處理沖突、再哈希法處理沖突等。在編程的過程中，出現了很多問題，如文件無法正常打開、程序進入死循環、無法實現文件的寫入操作、忘了添加頭文件等錯誤。修改后程序運行正確。2、創建“new.txt”內容用子函數來實現，但是原數據是從“old.txt”文件中讀取的，剛開始不知道怎樣實現二者之間的選擇，在同學和參考書的幫助下終于得到解決。3、關于偽隨機和再哈希的相關內容覺得很難懂，看了很久參考書才有所了解

7、六測試結果1、 根據姓名查找1) 姓名查找成功2) 姓名查找失敗3) 哈希表2、 根據電話號碼查找1) 電話號碼輸入錯誤2) 電話號碼查詢成功3) 電話號碼查詢失敗4) 哈希表七用戶使用說明1、 選擇數據來源根據提示信息進行操作，選擇已存在的“old.txt”文件中的數據或系統當前自動生成的“new.txt”文件。2、 選擇查找方式根據提示信息進行操作，選擇“根據姓名查找”或“根據電話號碼查找”兩種查找方式。 3、 選擇功能根據提示信息進行操作，選擇輸入已知信息或查看哈希表。4、 顯示結果5、 查看文件八課程設計總結1、 收獲學會了C+的跟蹤。更進一步了解和熟悉了關于哈希表的運用和文件的讀取與

8、寫入操作。同時鍛煉了對話形式的菜單的創建和熟練運用。2、 心得體會在這次數據結構設計中遇到了很多實際性的問題，在實際設計中才發現，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯誤思維。通過這次設計，我懂得了學習的重要性，了解到理論知識與實踐相結合的重要意義，學會了堅持、耐心和努力，這將為自己今后的學習和工作做出了最好的榜樣。我覺得作為一名計科專業的學生，這次課程設計是很有意義的。更重要的是如何把自己平時所學的東西應用到實際中。雖然自己對于這門課懂的并不多，很多基礎的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學習，漸漸對這

9、門課逐漸產生了些許的興趣，自己開始主動學習并逐步從基礎慢慢開始弄懂它。附錄：源程序#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;/偽隨機數序列int count;/當前數據元素個數int sizeindex;/哈希表的長度char *sign;/沖突的標志struct Datastring name;string phon

10、e;string address; Data *intermediate_data;int Collision_Random(int key,int i)/偽隨機數探量觀測再散列法處理沖突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)/以姓名為關鍵字建立哈希表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;/將數據存入哈希表intermediate_datakey.address=address;intermediate_datakey.phone=phone;signkey='1'/設置沖突標志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)/以電話號碼為關鍵字建立哈希表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)/在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中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()/隨機生成數據，并將數據保存在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');/按行讀入數據if(str0='*')/判斷數據結束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);/以姓名為關鍵字else Init_HashTable_by_phone(name,phon

21、e,address);/以電話號碼為關鍵字delete str;in_file.close();int Search_by_name(string name)/根據姓名查找哈希表中的記錄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)/根據電話號碼查找哈希表中的記錄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<<"§* 請選擇用于查找的數據來源 *§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 1 . old.TXT *§"<<endl;cout<<"§* 2 . 隨

25、機 生 成 *§"<<endl;cout<<"§* 0 . 退 出 程 序 *§"<<endl; cout<<"§*§"<<endl; docout<<"n"<< " 請輸入選擇 : 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<<"輸入序號有誤，請重新輸入!n"<<endl;while(k!=1)&&(k!=2)&&(k!=0); /system("cls"); cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請 選 擇 查 找 方 式

27、 *§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 1 . 根 據 姓 名 查 找 *§"<<endl;cout<<"§* 2 . 根 據 電 話 號 查 找 *§"<<endl;cout<<"§* *§"<<endl; cout<<"§*§

28、;"<<endl;docout<<"n"<< " 請輸入選擇 : 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<<"§*

29、67;"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請 選 擇 功 能 *§"<<endl; cout<<"§* *§"<<endl;cout<<"§* 1 . 輸 入 姓 名 查 找 數 據 *§"<<endl;cout<<"§* 2 . 顯 示 哈 希 表

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

31、y1;string name;cout<<"n"<<" 請輸入姓名: n"cin>>name;key1=Search_by_name(name);Outfile(name,key1); cout<<"n"<<"查找結果: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<<" 輸入序號有誤，請重新輸入!n"<<endl; while(choice!=1)&&(choice!=2)&&(choice!=0);while(ch=2)int choice;cout<<"§*§"<<endl;cout<<"§* *§"<<endl;cout<<"§* 請 選 擇 功 能 *§"<<endl;cout<<"§* 1 . 輸 入 電 話 查 找 數 據 *§"<<endl;cout&l