生活随笔
收集整理的這篇文章主要介紹了
课设题目:哈希表实现电话号码查找系统
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
?開發工具:VS 2017
?演示效果:呃,我也忘了成功沒有了
// MyHashTable.cpp : 定義控制臺應用程序的入口點。
設計哈希表實現電話號碼查詢系統
//說明:一是從文件old.txt中讀取的數據自己在程序運行前建立,
// 二是由系統隨機生成數據,在程序運行由隨機數產生器生成,并且將產生的記錄保存到 new.txt文件。 //存在的問題:使用隨機產生的文件,在顯示時出現亂碼 #include "stdafx.h"
#include<fstream>//文件流
#include<iostream>
#include <string>
using namespace std; const int D[] = {3,5,8,11,13,14,19,21};//預定再隨機數
const int HASH_MAXSIZE = 50;//哈希表長度 //記錄信息類型
class DataInfo
{
public: DataInfo();//默認構造函數 friend ostream& operator<<(ostream& out, const DataInfo& dataInfo); //重載輸出操作符 //friend class HashTable; //private: string name;//姓名 string phone;//電話號碼 string address;//地址 char sign;//沖突的標志位,'1'表示沖突,'0'表示無沖突
}; DataInfo::DataInfo():name(""), phone(""), address(""), sign('0')
{ } ostream& operator<<(ostream& out, const DataInfo& dataInfo) //重載輸出操作符
{ cout << "姓名:" << dataInfo.name << " 電話:" << dataInfo.phone << " 地址:" << dataInfo.address << endl; return out;
} //存放記錄的哈希表類型
class HashTable
{
public: HashTable();//默認構造函數 ~HashTable();//析構函數 int Random(int key, int i);// 偽隨機數探測再散列法處理沖突 void Hashname(DataInfo *dataInfo);//以名字為關鍵字建立哈希表 int Rehash(int key, string str);// 再哈希法處理沖突 注意處理沖突還有鏈地址法等 void Hashphone(DataInfo *dataInfo);//以電話為關鍵字建立哈希表 void Hash(char *fname, int n);// 建立哈希表 //fname 是數據儲存的文件的名稱,用于輸入數據,n是用戶選擇的查找方式 int Findname(string name);// 根據姓名查找哈希表中的記錄對應的關鍵碼 int Findphone(string phone);// 根據電話查找哈希表中的記錄對應的關鍵碼 void Outhash(int key);// 輸出哈希表中關鍵字碼對應的一條記錄 void Outfile(string name, int key);// 在沒有找到時輸出未找到的記錄 void Rafile();// 隨機生成文件,并將文件保存在 new.txt文檔中 void WriteToOldTxt();//在運行前先寫入數據 //private: DataInfo *value[HASH_MAXSIZE]; int length;//哈希表長度
}; HashTable::HashTable():length(0)//默認構造函數
{ //memset(value, NULL, HASH_MAXSIZE*sizeof(DataInfo*)); for (int i=0; i<HASH_MAXSIZE; i++) { value[i] = new DataInfo(); }
} HashTable::~HashTable()//析構函數
{ delete[] *value;
} void HashTable::WriteToOldTxt()
{ ofstream openfile("old.txt"); if (openfile.fail()) { cout << "文件打開錯誤!" << endl; exit(1); } string oldname; string oldphone; string oldaddress; for (int i=0; i<30; i++) { cout << "請輸入第" << i+1 << "條記錄:" << endl; cin >> oldname ; cin >> oldphone; cin >> oldaddress; openfile << oldname << " " << oldphone << " " << oldaddress << "," << endl; } openfile.close();
} int HashTable::Random(int key, int i)// 偽隨機數探測再散列法處理沖突
{//key是沖突時的哈希表關鍵碼,i是沖突的次數,N是哈希表長度 //成功處理沖突返回新的關鍵碼,未進行沖突處理則返回-1 int h; if(value[key]->sign == '1')//有沖突 { h = (key + D[i]) % HASH_MAXSIZE; return h; } return -1;
} void HashTable::Hashname(DataInfo *dataInfo)//以名字為關鍵字建立哈希表
{//利用除留取余法建立以名字為關鍵字建立的哈希函數,在發生沖突時調用Random函數處理沖突 int i = 0; int key = 0; for (int t=0; dataInfo->name[t]!='\0'; t++) { key = key + dataInfo->name[t]; } key = key % 42; while(value[key]->sign == '1')//有沖突 { key = Random(key, i++);//處理沖突 } if(key == -1) exit(1);//無沖突 length++;//當前數據個數加 value[key]->name = dataInfo->name; value[key]->address = dataInfo->address; value[key]->phone = dataInfo->phone; value[key]->sign = '1';//表示該位置有值 //cout << value[key]->name << " " << value[key]->phone << " " << value[key]->address << endl;
} int HashTable::Rehash(int key, string str)// 再哈希法處理沖突
{//再哈希時使用的是折疊法建立哈希函數 int h; 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'); h = num1 + num2 + num3; h = (h + key) % HASH_MAXSIZE; return h;
} void HashTable::Hashphone(DataInfo *dataInfo)//以電話為關鍵字建立哈希表
{//利用除留取余法建立以電話為關鍵字建立的哈希函數,在發生沖突時調用Rehash函數處理沖突 int key = 0; int t; for(t=0; dataInfo->phone[t] != '\0'; t++) { key = key + dataInfo->phone[t]; } key = key % 42; while(value[key]->sign == '1')//有沖突 { key = Rehash(key, dataInfo->phone); } length++;//當前數據個數加 value[key]->name = dataInfo->name; value[key]->address = dataInfo->address; value[key]->phone = dataInfo->phone; value[key]->sign = '1';//表示該位置有值
} void HashTable::Outfile(string name, int key)//在沒有找到時輸出未找到的記錄
{ ofstream fout; if((key == -1)||(value[key]->sign == '0'))//判斷哈希表中沒有記錄 { fout.open("out.txt",ios::app);//打開文件 if(fout.fail()) { cout << "文件打開失敗!" << endl; exit(1); } fout << name << endl;//將名字寫入文件,有個問題,每次寫入的時候總是將原來的內容替換了 fout.close(); }
} void HashTable::Outhash(int key)//輸出哈希表中關鍵字碼對應的記錄
{ if((key==-1)||(value[key]->sign=='0')) cout << "沒有找到這條記錄!" << endl; else { for(unsigned int i=0; value[key]->name[i]!='\0'; i++) { cout << value[key]->name[i]; } for(unsigned int i=0; i<10; i++) { cout << " "; } cout << value[key]->phone; for(int i=0; i<10; i++) { cout << " "; } cout << value[key]->address << endl; }
} void HashTable::Rafile()//隨機生成文件,并將文件保存在new.txt文檔中
{ ofstream fout; fout.open("new.txt");//打開文件,等待寫入 if(fout.fail()) { cout << "文件打開失敗!" << endl; exit(1); } for(int j=0; j<30; j++) { string name = ""; for(int i=0; i<20; i++)//隨機生成長個字的名字 { name += rand() % 26 + 'a';//名字是由個字母組成 } fout << name << " ";//將名字寫入文件 string phone = ""; for(int i=0; i<11; i++)//隨機生成長位的電話號碼 { phone += rand() % 10 + '0';//電話號碼是純數字 } fout << phone << " ";//將電話號碼寫入文件 string address = ""; for(int i=0; i<29; i++)//隨機生成長個字的名字 { address += rand() % 26 + 'a';//地址是由個字母組成 } address += ','; fout << address << endl;//將地址寫入文件 } fout.close();
} void HashTable::Hash(char *fname, int n)//建立哈希表
//fname是數據儲存的文件的名稱,用于輸入數據,n是用戶選擇的查找方式
//函數輸入數據,并根據選擇調用Hashname或Hashphone函數進行哈希表的建立
{ ifstream fin; int i; fin.open(fname);//讀文件流對象 if(fin.fail()) { cout << "文件打開失敗!" << endl; exit(1); } while(!fin.eof())//按行讀入數據 { DataInfo *dataInfo = new DataInfo(); char* str = new char[100]; fin.getline(str, 100, '\n');//讀取一行數據 if(str[0] == '*')//判斷數據結束 { break; } i = 0;//記錄字符串數組的下標 //a-z:97-122 A-Z:65-90 //本程序的姓名和地址都使用小寫字母 while((str[i] < 97) || (str[i] > 122))//讀入名字 { i++; } for(; str[i]!=' '; i++) { dataInfo->name += str[i]; } while(str[i] == ' ') { i++; } for(int j=0; str[i]!=' '; j++,i++)//讀入電話號碼 { dataInfo->phone += str[i]; } while(str[i] == ' ') { i++; } for(int j=0; str[i]!=','; j++,i++)//讀入地址 { dataInfo->address += str[i]; } if(n == 1) { Hashname(dataInfo); } else { Hashphone(dataInfo);//以電話為關鍵字 } delete []str; delete dataInfo; } fin.close();
} int HashTable::Findname(string name)//根據姓名查找哈希表中的記錄對應的關鍵碼
{ int i = 0; int j = 1; int t; int key = 0; for(key=0, t=0; name[t] != '\0'; t++) { key = key + name[t]; } key = key % 42; while((value[key]->sign == '1') && (value[key]->name != name)) { key = Random(key, i++); j++; if(j >= length) return -1; } return key;
} int HashTable::Findphone(string phone)//根據電話查找哈希表中的記錄對應的關鍵碼
{ int key = 0; int t; for(t=0; phone[t] != '\0' ; t++) { key = key + phone[t]; } key = key % 42; int j = 1; while((value[key]->sign == '1') && (value[key]->phone != phone)) { key = Rehash(key, phone); j++; if(j >= length) { return -1; } } return key;
} void main()
{ //WriteToOldTxt(); int k; int ch; char *Fname; HashTable *ht = new HashTable; while(1) { system("cls");//cls命令清除屏幕上所有的文字 cout << "歡迎使用本系統!" << endl << endl; cout << "請選擇數據" << endl; cout << "1.使用已有數據文件" << endl; cout << "2.隨機生成數據文件" << endl; cout << "0.結束" << endl; cout << "輸入相應序號選擇功能:"; cin >> k; switch(k) { case 0: return; case 1: Fname = "old.txt";//從數據文件old.txt(自己現行建好)中讀入各項記錄 break; case 2: ht->Rafile(); Fname = "new.txt";//由系統隨機產生各記錄,并且把記錄保存到new.txt文件中 break; default: cout << "輸入序號有誤,退出程序。" << endl; return; } do { system("cls"); cout << " 請選擇查找方式" << endl; cout << "1.通過姓名查找" << endl; cout << "2.通過電話查找" << endl; cout << "輸入相應序號選擇功能:"; cin >> ch; if((ch != 1) && (ch != 2)) cout << "輸入序號有誤!" << endl; }while((ch != 1) && (ch != 2)); ht->Hash(Fname, ch); while(ch == 1) { int choice; cout << endl << "請選擇功能" << endl; cout << "1.輸入姓名查找數據" << endl; cout << "2.顯示哈希表" << endl; cout << "0.退出"<<endl; cout << "輸入相應序號選擇功能:"; cin >> choice; switch(choice) { case 1: {//注意此處應該加上大括號 int key1; string name; cout << "請輸入姓名:"; cin >> name; key1 = ht->Findname(name); ht->Outfile(name, key1); ht->Outhash(key1); } break; case 2: { for(int i=0; i<HASH_MAXSIZE; i++) { if(ht->value[i]->sign!='0') { ht->Outhash(i); } } } break; default: cout << endl << "您的輸入有誤!" << endl; } if(choice == 0) { return; } } while(ch == 2) { int choice; cout << endl << "請選擇功能" << endl; cout << "1.輸入電話查找數據" << endl; cout << "2.顯示哈希表"<<endl; cout << "0.退出"<<endl; cout << "輸入相應序號選擇功能:"; cin >> choice; switch(choice) { case 1: { int key2; string phone; cout << "請輸入11位的電話號碼:"; do { cin >> phone; if(phone.length() != 11) { cout << "電話號碼應為11位!\n請重新輸入:"; } }while(phone.length() != 11); key2 = ht->Findphone(phone); ht->Outfile(phone, key2); ht->Outhash(key2); } break; case 2: { for(int i=0; i<HASH_MAXSIZE; i++) { if(ht->value[i]->sign != '0') { ht->Outhash(i); } } } break; default: cout << endl << "您的輸入有誤!" << endl; } if(choice == 0) { return; } } while((ch != 1) && (ch != 2)) { cout << "您的輸入有誤!請輸入相應需要選擇功能:"; } } system("pause");
} ?這是我的課設題目,應該沒有太大問題:
課題概述
設計散列表實現電話號碼查找系統。
要求能以姓名或是電話號碼的形式查出對應的記錄。
?
程序分析設計部分
??? 程序的功能
每個記錄有下列數據項:用戶名、電話號碼、地址;
從鍵盤輸入各記錄,以用戶名(漢語拼音形式)為關鍵字建立散列表;
要求給定一個電話號碼,能查找出相關記錄;
??? 需求分析
??? 首先要通過鍵盤輸入相關的信息,一邊輸入一邊往表里面添加相關的記錄。
?? 以姓名為關鍵字(姓名是拼音的,取一個首字母),建立散列表。
?? 以電話號碼為關鍵字建立第二個散列表,
能夠根據姓名或者電話號碼為關鍵字查找到相應的記錄
系統操作演示部分
#include "stdafx.h"#include <stdio.h>#include<stdlib.h>#include<string.h>#define size 100#define n 13typedef struct node {int number;char address[size];char name[size];struct node *next;}newnode, *anode;void HashLink(newnode **p) {for (int i = 0; i < n;i++) {//n為最多查詢的記錄13p[i] = NULL;}printf("散列表初始化完畢!");}void HashAddName(newnode **p) {//添加記錄,以姓名為關鍵字int i, v; printf("請輸入電話號碼:(若無更多記錄請輸入-1)\n");scanf("%d", &v);while (v != -1) {anode e = (anode)malloc(sizeof(newnode));e->number = v;printf("請輸入地址:\n");scanf("%s", e->address);printf("請輸入姓名:(以拼音形式)\n");scanf("%s", e->name);i = e->name[0];//取名字的首字母i = i%n;e->next = p[i];//p[i] = e;printf("請輸入電話號碼:(若無更多記錄請輸入-1)\n");scanf("%d", &v);}}void SearchHash(newnode **p) {//查詢記錄,也用鏈地址法char a[size];//定義一個char數組anode t;int i;printf("請輸入要查詢用戶名:\n");scanf("%s", a);i = (int)a[0];i = i%n;t = p[i];while (t&&strcmp(t->name, a) != 0) {t = t->next;}if (t == NULL) {printf("您所查詢的用戶不存在!\n");}else {printf("------------------------------------------\n");printf("姓名:%s\n",t->name);printf("電話:%d\n",t->number);printf("地址:%s\n",t->address);printf("------------------------------------------\n");}}void hashinput2(newnode **p) {//添加記錄(以號碼為關鍵字)int t, v;printf("請輸入電話號碼:(若無更多記錄請輸入- 1) \n");scanf("%d", &v);while (v != -1) {anode e = (anode)malloc(sizeof(newnode));e->number = v;printf("請輸入地址\n");scanf("%s", e->address);printf("請輸入姓名:(以拼音形式)\n");scanf("%s", e->name);t = e->number%n;e->next = p[t];p[t] = e;printf("請輸入電話號碼:(若無更多記錄請輸入- 1) \n"); scanf("%d", &v);}}void SearchPhone(newnode **p){//查詢記錄(以號碼為關鍵字)鏈地址法int d, h;anode t;printf("請輸入所要查詢的電話號碼:\n");scanf("%d", &d);h = d%n;t = p[h];while (t&&t->number != d) {t = t->next;}if (t == NULL) {printf("不好意思您所要查詢的號碼不存在哦~\n"); }else {printf("------------------------------------------\n");printf("姓名:%s\n",t->name);printf("電話:%d\n",t->number);printf("地址:%s\n",t->address);printf("------------------------------------------\n");}}int main() {int j1;node *p[n];HashLink(p);//散列表初始化printf("歡迎進入~~!\n");printf("step1:添加記錄\n");printf("step2:查詢記錄\n");printf("------------------------------------------\n");printf("請添加記錄(以用戶名為關鍵字)\n");HashAddName(p);printf("請添加記錄(以電話號碼為關鍵字)\n");hashinput2(p);printf("------------------------------------------\n");printf("請選擇功能\n");printf("1.以用戶名為關鍵字查詢記錄\n");printf("2.以電話號碼為關鍵字查詢記錄\n");scanf("%d", &j1);switch (j1){case 1:SearchHash(p);printf("請輸入電話號碼查詢記錄:\n");case 2:SearchPhone(p); break;}return 0;}
?
?
代碼演示部分
測試數據:
1、8870774 四川省成都市 TanMin
2、8475257 江西省贛州市 YangDan
3、8754455 北京市朝陽區 YanyiYin
?
?
??? 系統小結
????? 程序設計過程中遇到的問題及解決過程
?????? 建立散列表時要建立相應的哈希函數,選用直接取余法:f(x):= x mod maxM ;對一個素數取模。這里maxM 為長度n=13。
?????? 在設計關鍵字的時候原本想用中文姓名直接存,后來涉及到字符的存取比較麻煩。因此改用題目給出的用中文拼音形式。
?????? 用電話號碼查找時還是建立了第二張散列表,以電話號碼為關鍵字。
?????? 有多種方法解決沖突,如開放地址法等,最后選用鏈地址法解決沖突。
?????? 涉及到要結束循環的問題,所以說需要先輸入電話號碼,以電話號碼作為結束的條件。
?
總結
以上是生活随笔為你收集整理的课设题目:哈希表实现电话号码查找系统的全部內容,希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯,歡迎將生活随笔推薦給好友。