第一篇：數據結構課程設計報告
《數據結構》課程設計
哈希表實現電話號碼查詢系統一目的
利用《數據結構》課程的相關知識完成一個具有一定難度的綜合設計題目，利用C/C++語言進行程序設計，并規范地完成課程設計報告。通過課程設計，鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現實復雜問題的分析建模和解決方法（包括問題描述、系統分析、設計建模、代碼實現、結果分析等）；提高利用計算機分析解決綜合性實際問題的基本能力。
二需求分析
1、程序的功能
1)讀取數據
① 讀取原電話本存儲的電話信息。
② 讀取系統隨機新建電話本存儲的電話信息。2)查找信息
① 根據電話號碼查詢用戶信息。② 根據姓名查詢用戶信息。3)存儲信息
查詢無記錄的結果存入記錄文檔。
2、輸出形式
1)數據文件“old.txt”存放原始電話號碼數據。
2)數據文件“new.txt”存放有系統隨機生成的電話號碼文件。3)數據文件“out.txt”存放未查找到的電話信息。4)查找到相關信息時顯示姓名、地址、電話號碼。
3、初步測試計劃
1)從數據文件“old.txt”中讀入各項記錄，或由系統隨機產生各記錄，并且把記錄保存到“new.txt”中。
2)分別采用偽隨機探測再散列法和再哈希法解決沖突。3)根據姓名查找時顯示給定姓名用戶的記錄。4)根據電話號碼查找時顯示給定電話號碼的用戶記錄。
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 1
《數據結構》課程設計
5)將沒有查找的結果保存到結果文件Out.txt中。
6)系統以菜單界面工作，運行界面友好，演示程序以用戶和計算機的對話方式進行。
三概要設計
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)//以電話號碼為關鍵字建立哈希表 void Outfile(string name,int key)//在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中 void Outhash(int key)//輸出哈希表中的記錄 void Rafile()//隨機生成數據，并將數據保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表
int Search_by_name(string name)//根據姓名查找哈希表中的記錄 int Search_by_phone(string phone)//根據電話號碼查找哈希表中的記錄
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 2
《數據結構》課程設計
2、函數調用圖
main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 3
《數據結構》課程設計
四詳細設計
1、主函數流程圖
開始選擇數據來源21建“new.txt”選擇查找方式12姓名查找電話號碼查找12021輸入姓名顯示哈希表0顯示哈希表輸入電話號碼無此記錄顯示信息無此記錄顯示信息0寫入“out.txt”寫入“out.txt”結束
2、“偽隨機探測再散列處理沖突”偽代碼
若對應位置上已經存在其他數據，則新的關鍵字=（原關鍵字+偽隨機數）%哈希表長。若新的位置上也存在其他數據，則用偽隨機序列的下一個數求新的關鍵字，直到找到合適的位置。
3、“再哈希法處理沖突”偽代碼
用“折疊法”將電話號碼的ASCII碼值定義為關鍵字，分別為前四位、中四位、后三位。
再用“除留余數法”求的新的關鍵字=原關鍵字%哈希表長。
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6
《數據結構》課程設計
4、“以姓名為關鍵字建立哈希表”偽代碼
用“除留余數法”將姓名的ASCII碼值定義為關鍵字。
若對應位置上存在其他數據，則調用偽隨機處理沖突，然后將數據存入哈希表。
5、“以電話號碼為關鍵字建立哈希表”偽代碼
用“除留余數法”將電話號碼的ASCII碼值定義為關鍵字。若對應位置上存在其他數據，則調用再哈希處理沖突。然后將數據存入哈希表。
五調試分析
1、程序的關鍵是掌握文件的相關操作、哈希函數的創建和運用、偽隨機法處理沖突、再哈希法處理沖突等。在編程的過程中，出現了很多問題，如文件無法正常打開、程序進入死循環、無法實現文件的寫入操作、忘了添加頭文件等錯誤。修改后程序運行正確。
2、創建“new.txt”內容用子函數來實現，但是原數據是從“old.txt”文件中讀取的，剛開始不知道怎樣實現二者之間的選擇，在同學和參考書的幫助下終于得到解決。
3、關于偽隨機和再哈希的相關內容覺得很難懂，看了很久參考書才有所了解
六測試結果
1、根據姓名查找
1)姓名查找成功
2)姓名查找失敗
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 5
《數據結構》課程設計
3)哈希表
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 6
《數據結構》課程設計
2、根據電話號碼查找
1)電話號碼輸入錯誤
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 7
《數據結構》課程設計
2)電話號碼查詢成功
3)電話號碼查詢失敗
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 8
《數據結構》課程設計
4)哈希表
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 9
《數據結構》課程設計
七用戶使用說明
1、選擇數據來源
根據提示信息進行操作，選擇已存在的“old.txt”文件中的數據或系統當前自動生成的“new.txt”文件。
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 10
《數據結構》課程設計
2、選擇查找方式
根據提示信息進行操作，選擇“根據姓名查找”或“根據電話號碼查找”兩種查找方式。
3、選擇功能
根據提示信息進行操作，選擇輸入已知信息或查看哈希表。
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 11
《數據結構》課程設計
4、顯示結果
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6
《數據結構》課程設計
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 13
《數據結構》課程設計
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 14
《數據結構》課程設計
5、查看文件
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 15
《數據結構》課程設計
八課程設計總結
1、收獲
學會了C++的跟蹤。更進一步了解和熟悉了關于哈希表的運用和文件的讀取與寫入操作。同時鍛煉了對話形式的菜單的創建和熟練運用。
2、心得體會
在這次數據結構設計中遇到了很多實際性的問題，在實際設計中才發現，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯誤思維。通過這次設計，我懂得了學習的重要性，了解到理論知識與實踐相結合的重要意義，xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 16
《數據結構》課程設計
學會了堅持、耐心和努力，這將為自己今后的學習和工作做出了最好的榜樣。我覺得作為一名計科專業的學生，這次課程設計是很有意義的。更重要的是如何把自己平時所學的東西應用到實際中。雖然自己對于這門課懂的并不多，很多基礎的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學習，漸漸對這門課逐漸產生了些許的興趣，自己開始主動學習并逐步從基礎慢慢開始弄懂它。
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6
《數據結構》課程設計
附錄：源程序
#include
using namespace std;
ifstream in_file;ofstream out_file;
int D[10]={1,3,5,8,13,15,17,21,27,34};//偽隨機數序列 int count;//當前數據元素個數 int sizeindex;//哈希表的長度 char *sign;//沖突的標志
struct Data { string name;string phone;string address;};Data *intermediate_data;
int Collision_Random(int key,int i)//偽隨機數探量觀測再散列法處理沖突{ int Re_key;if(sign[key]=='1'){ xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 18
《數據結構》課程設計
} Re_key=(key+D[i])%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,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){
} if(key==-1)exit(1);key=Collision_Random(key,i+1);count++;intermediate_data[key].name=name;//將數據存入哈希表
intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//設置沖突標志 }
xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 19
《數據結構》課程設計
int Collision_Rehash(int key,string str)//再哈希法處理沖突 { int Re_key;int num1=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0');int num2=(str[4]-'0')*1000+(str[5]-'0')*100+(str[6]-'0')*10+(str[7]-'0');int num3=(str[8]-'0')*100+(str[9]-'0')*10+(str[10]-'0');Re_key=num1+num2+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=&phone[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){
} count++;intermediate_data[key].name=name;intermediate_data[key].address=address;intermediate_data[key].phone=phone;key=Collision_Rehash(key,phone);xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 20
《數據結構》課程設計
sign[key]='1';}
void Outfile(string name,int key)//在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中
{ if((key==-1)||(sign[key]=='0')){
out_file.open(“out.txt”);
if(out_file.fail())
{
cout<<“n”<<“文件打開失??！!n”< exit(1); } out_file< out_file.close();} } void Outhash(int key)//輸出哈希表中的記錄 { unsigned i;if((key==-1)||(sign[key]=='0')){ cout<<“n”<<“無此記錄！!n”< } else xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 21 《數據結構》課程設計 { for(i=0;i cout< for(i=0;i<8;i++) cout<<“ ”; cout< for(i=0;i<8;i++) cout<<“ ”; cout< void Rafile()//隨機生成數據，并將數據保存在new.txt { int i,j;out_file.open(“new.txt”);if(out_file.fail()){ cout<<“n”<<“文件打開失?。?n”< exit(1);} for(j=0;j<30;j++){ string name=“"; for(i=0;i<20;i++) name+=rand()%26+'a';out_file< 《數據結構》課程設計 string phone=”“; for(i=0;i<11;i++) phone+=rand()%10+'0'; out_file< string address=”“; for(i=0;i<29;i++) address+=rand()%26+'a'; address+=','; out_file< 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“<<”文件打開失?。?n“< exit(1);} while(!in_file.eof()){ xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 23 《數據結構》課程設計 字 鍵字 } char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行讀入數據 if(str[0]=='*')//判斷數據結束 i=0;while(str[i]<=97||str[i]>=122)i++;break;for(;str[i]!=' ';i++)name+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=' ';j++,i++)phone+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=',';j++,i++)address+=str[i];if(n==1)Init_HashTable_by_name(name,phone,address);//以姓名為關鍵else Init_HashTable_by_phone(name,phone,address);//以電話號碼為關delete str;in_file.close();} xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 《數據結構》課程設計 int Search_by_name(string name)//根據姓名查找哈希表中的記錄 { int i=0;int j=1;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'&&(intermediate_data[key].name!=name)){ key=Collision_Random(key,i+1); j++; if(j=count) return-1;} return key;} int Search_by_phone(string phone)//根據電話號碼查找哈希表中的記錄{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 25 《數據結構》課程設計 while(sign[key]=='1'&&(intermediate_data[key].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 char[sizeindex]; intermediate_data=new Data[sizeindex]; for(i=0;i