第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
《數(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ì)，并規(guī)范地完成課程設(shè)計(jì)報(bào)告。通過課程設(shè)計(jì)，鞏固和加深對線性表、棧、隊(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、輸出形式
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、初步測試計(jì)劃
1)從數(shù)據(jù)文件“old.txt”中讀入各項(xiàng)記錄，或由系統(tǒng)隨機(jī)產(chǎn)生各記錄，并且把記錄保存到“new.txt”中。
2)分別采用偽隨機(jī)探測再散列法和再哈希法解決沖突。3)根據(jù)姓名查找時(shí)顯示給定姓名用戶的記錄。4)根據(jù)電話號碼查找時(shí)顯示給定電話號碼的用戶記錄。
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 1
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
5)將沒有查找的結(jié)果保存到結(jié)果文件Out.txt中。
6)系統(tǒng)以菜單界面工作，運(yùn)行界面友好，演示程序以用戶和計(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 Outfile(string name,int key)//在沒有找到時(shí)輸出未找到的記錄，打開文件out.txt并將記錄儲(chǔ)存在文檔中 void Outhash(int key)//輸出哈希表中的記錄 void Rafile()//隨機(jī)生成數(shù)據(jù)，并將數(shù)據(jù)保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表
int Search_by_name(string name)//根據(jù)姓名查找哈希表中的記錄 int Search_by_phone(string phone)//根據(jù)電話號碼查找哈希表中的記錄
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 2
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
2、函數(shù)調(diào)用圖
main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 3
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
四詳細(xì)設(shè)計(jì)
1、主函數(shù)流程圖
開始選擇數(shù)據(jù)來源21建“new.txt”選擇查找方式12姓名查找電話號碼查找12021輸入姓名顯示哈希表0顯示哈希表輸入電話號碼無此記錄顯示信息無此記錄顯示信息0寫入“out.txt”寫入“out.txt”結(jié)束
2、“偽隨機(jī)探測再散列處理沖突”偽代碼
若對應(yīng)位置上已經(jīng)存在其他數(shù)據(jù)，則新的關(guān)鍵字=（原關(guān)鍵字+偽隨機(jī)數(shù)）%哈希表長。若新的位置上也存在其他數(shù)據(jù)，則用偽隨機(jī)序列的下一個(gè)數(shù)求新的關(guān)鍵字，直到找到合適的位置。
3、“再哈希法處理沖突”偽代碼
用“折疊法”將電話號碼的ASCII碼值定義為關(guān)鍵字，分別為前四位、中四位、后三位。
再用“除留余數(shù)法”求的新的關(guān)鍵字=原關(guān)鍵字%哈希表長。
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
4、“以姓名為關(guān)鍵字建立哈希表”偽代碼
用“除留余數(shù)法”將姓名的ASCII碼值定義為關(guān)鍵字。
若對應(yīng)位置上存在其他數(shù)據(jù)，則調(diào)用偽隨機(jī)處理沖突，然后將數(shù)據(jù)存入哈希表。
5、“以電話號碼為關(guān)鍵字建立哈希表”偽代碼
用“除留余數(shù)法”將電話號碼的ASCII碼值定義為關(guān)鍵字。若對應(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)容覺得很難懂，看了很久參考書才有所了解
六測試結(jié)果
1、根據(jù)姓名查找
1)姓名查找成功
2)姓名查找失敗
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 5
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
3)哈希表
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 6
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
2、根據(jù)電話號碼查找
1)電話號碼輸入錯(cuò)誤
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 7
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
2)電話號碼查詢成功
3)電話號碼查詢失敗
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 8
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
4)哈希表
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 9
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
七用戶使用說明
1、選擇數(shù)據(jù)來源
根據(jù)提示信息進(jìn)行操作，選擇已存在的“old.txt”文件中的數(shù)據(jù)或系統(tǒng)當(dāng)前自動(dòng)生成的“new.txt”文件。
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 10
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
2、選擇查找方式
根據(jù)提示信息進(jìn)行操作，選擇“根據(jù)姓名查找”或“根據(jù)電話號碼查找”兩種查找方式。
3、選擇功能
根據(jù)提示信息進(jìn)行操作，選擇輸入已知信息或查看哈希表。
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 11
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
4、顯示結(jié)果
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 13
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 14
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
5、查看文件
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 15
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
八課程設(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ì)中才發(fā)現(xiàn)，書本上理論性的東西與在實(shí)際運(yùn)用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯(cuò)誤思維。通過這次設(shè)計(jì)，我懂得了學(xué)習(xí)的重要性，了解到理論知識(shí)與實(shí)踐相結(jié)合的重要意義，xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 16
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
學(xué)會(huì)了堅(jiān)持、耐心和努力，這將為自己今后的學(xué)習(xí)和工作做出了最好的榜樣。我覺得作為一名計(jì)科專業(yè)的學(xué)生，這次課程設(shè)計(jì)是很有意義的。更重要的是如何把自己平時(shí)所學(xué)的東西應(yīng)用到實(shí)際中。雖然自己對于這門課懂的并不多，很多基礎(chǔ)的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學(xué)習(xí)，漸漸對這門課逐漸產(chǎn)生了些許的興趣，自己開始主動(dòng)學(xué)習(xí)并逐步從基礎(chǔ)慢慢開始弄懂它。
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
附錄：源程序
#include
using namespace std;
ifstream in_file;ofstream out_file;
int D[10]={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 Data { string name;string phone;string address;};Data *intermediate_data;
int Collision_Random(int key,int i)//偽隨機(jī)數(shù)探量觀測再散列法處理沖突{ int Re_key;if(sign[key]=='1'){ xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 18
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
} Re_key=(key+D[i])%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=&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;//將數(shù)據(jù)存入哈希表
intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//設(shè)置沖突標(biāo)志 }
xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 19
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
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)//以電話號碼為關(guān)鍵字建立哈希表
{ 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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 20
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)
sign[key]='1';}
void Outfile(string name,int key)//在沒有找到時(shí)輸出未找到的記錄，打開文件out.txt并將記錄儲(chǔ)存在文檔中
{ 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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 21 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) { for(i=0;i cout< for(i=0;i<8;i++) cout<<“ ”; cout< for(i=0;i<8;i++) cout<<“ ”; cout< void Rafile()//隨機(jī)生成數(shù)據(jù)，并將數(shù)據(jù)保存在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< 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) 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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 23 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) 字 鍵字 } char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行讀入數(shù)據(jù) if(str[0]=='*')//判斷數(shù)據(jù)結(jié)束 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);//以姓名為關(guān)鍵else Init_HashTable_by_phone(name,phone,address);//以電話號碼為關(guān)delete str;in_file.close();} xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) int Search_by_name(string name)//根據(jù)姓名查找哈希表中的記錄 { 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)//根據(jù)電話號碼查找哈希表中的記錄{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 25 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì) 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