數據結構課程設計------c實現散列表（二次探測再哈希）電話簿（文件存儲）

題目二：散列表的設計與實現

2.1問題描述

設計散列表實現電話號碼查找系統，使得平均查找長度不超過2

基本要求
（1）設每個記錄有下列數據項：電話號碼、用戶名、地址；
（2）從鍵盤輸入各記錄，以電話號碼為關鍵字建立散列表；
（3）采用一定的方法解決沖突；
（4）查找并顯示給定電話號碼的記錄；

2.2.算法設計與分析

2.2.1設計思路分析
基本思路
1構建哈希表（需要構造一個哈希函數，確定一個合適的處理沖突的方法）
2按照電話號碼查找并輸出
3將哈希表按序存進文件中
基本思想
1 哈希表是根據關鍵碼而直接進行訪問的數據結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表
2給定表M，存在函數f（key），對任意給定的關鍵子值key，代入函數后能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希表，函數f（key）為哈希函數。
3 二次探測再散列法:若發生沖突，則按照+12，-12，+22，-22……方式進行探測再散列的方法。

2.2.2設計程序流程圖
在這里插入圖片描述
進入程序，進行功能選擇，選擇1進行存入電話號碼，構建哈希表，如果存在沖突解決沖突再錄入，不存在直接錄入信息。選擇0查找電話號碼，怎么解決沖突，就按相應的方法查找。所有功能執行完后返回，選擇0退出程序，程序結束。
2.2.3數據結構定義

typedef struct record				//定義一條記錄的結構體
{char Number[20];				char Name[20];char Address[20];
}Record;typedef struct Hash					//定義一個散列表
{Record *data;					//存訪多條記錄的數組int cnt;						int size;						//數組大小
}*HashTable, HashElem;

2.2.4算法的時間復雜度分析
整個程序的時間復雜度看哈希表在解決沖突時的時間復雜度
解決沖突
最差的時間復雜度O(n),當所有數據被填滿時
最好的時間復雜度O(1)沒有沖突的時候.

2.3源程序清單

hash.h文件

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>#define MAXSIZE 50using namespace std;				typedef struct record				//定義一條記錄的結構體
{char Number[20];				char Name[20];char Address[20];
}Record;typedef struct Hash					//定義一個散列表
{Record *data;					//存訪多條記錄的數組int cnt;						int size;						//數組大小
}*HashTable, HashElem;void savenumb(HashTable numbertable, Record record[]);		//存訪函數
void findnumb(HashTable numbertable);						//查詢函數

function.cpp文件

#define _CRT_SECURE_NO_WARNINGS
#include"hash.h"int Czy = 1;
//哈希函數，將電話號碼每一位求和 
int GetHashKey(char ar[])
{int len = strlen(ar);						//計算電話號碼的長度int key = 0;for (int i = 0; i<len; i++){					key += ar[i] - '0';						//key=總和，數字字符減'0'就是數字}return key%MAXSIZE;//必須取模，否則下標越界		//返回得到的地址
}//沖突處理，二次探測再散列 
int HandleCollision(HashTable table, int key)
{Czy = 1; //從2,3,4,5,....... while (1){Czy++; //從2,3,4,5,....... if (Czy % 2 == 0) {										//偶數和偶數下一個數奇數除二的值相等if (table->data[(key + (Czy / 2)*(Czy / 2)) % MAXSIZE].Name[0] == 0)	//這個位置上沒有數據	return (key + (Czy / 2)*(Czy / 2)) % MAXSIZE;						//返回這個位置上的地址}else if (Czy % 2 != 0) {if ((key - (Czy / 2)*(Czy / 2))<0) continue;                             //由于是減法，要注意負數不能取模 if (table->data[(key - (Czy / 2)*(Czy / 2)) % MAXSIZE].Name[0] == 0)	//如果這個位置上沒有數據return (key - (Czy / 2)*(Czy / 2)) % MAXSIZE;}}//return -1;
}//構建哈希表 
void CreateHashTable(HashTable &table, Record *record, int n)
{int key;for (int i = 0; i<n; i++){key = GetHashKey(record[i].Number);				//接受每個電話返回來的地址if (table->data[key].Name[0] != 0)				//當這個地址里的名字不為空時，也就是有沖突了key = HandleCollision(table, key);			//進行沖突處理  傳沖突的地址//如果不沖突，則進行賦值strcpy(table->data[key].Number, record[i].Number);	strcpy(table->data[key].Name, record[i].Name);strcpy(table->data[key].Address, record[i].Address);}
}//按照電話號碼尋找 
int SerchKey(HashTable table, char PhoneNumber[])
{int key = GetHashKey(PhoneNumber);						//得到該元素的最初地址位置if (strcmp(table->data[key].Number, PhoneNumber)){		//如果該位置上的數與給定的數不相等，則考慮沖突尋址for (Czy = 1; Czy < MAXSIZE; Czy++){if (Czy % 2 == 0) {//strcmp（str1，str2）//當str1的字典序大于str2時返回一個一個正數 小于負數，等于0if (!strcmp(PhoneNumber, table->data[(key + (Czy / 2)*(Czy / 2)) % MAXSIZE].Number)){//如果相等則地址就等于沖突處理后的值key = (key + (Czy / 2)*(Czy / 2)) % MAXSIZE;break;}}else if (Czy % 2 != 0) {if ((key - (Czy / 2)*(Czy / 2)) < 0) continue;//由于是減法，要注意負數不能取模			//如果取差后為負數，則不做處理，Czy+1//不是負數，判斷值是否與當前地址值相等if (!strcmp(PhoneNumber, table->data[(key - (Czy / 2)*(Czy / 2)) % MAXSIZE].Number)){key = (key - (Czy / 2)*(Czy / 2)) % MAXSIZE;break;}}}}return key;
}
//將哈希表存入文件中 void GoToFile(HashTable table)
{FILE *fp = fopen("Output.txt", "w");				//打開文件Output.txtfor (int i = 0; i <= MAXSIZE; i++)					//遍歷整個散列表if (table->data[i].Name[0] != 0)					//如果名字不為空，則寫入文件fprintf(fp, "%s %s %s\n", table->data[i].Name, table->data[i].Number, table->data[i].Address);//printf("%s %s %s\n",table->data[i].Name,table->data[i].Number,table->data[i].Address);	fclose(fp);											//關閉文件
}void findnumb(HashTable numbertable){				//查詢函數int key = 0;//輸入并尋找PhoneNumber（必須存在表中） char PhoneNumber[20];printf("請輸入你想找的電話:\n");cin >> PhoneNumber;cout << "給定電話號碼為：" << endl << PhoneNumber << endl;key= SerchKey(numbertable, PhoneNumber);if (!strcmp(numbertable->data[key].Number, PhoneNumber)){printf("找到的電話信息為:\n");}else{printf("\n沒有該電話號碼\n");return;}cout << numbertable->data[key].Name << " " << numbertable->data[key].Number << " " << numbertable->data[key].Address << endl;}void savenumb(HashTable numbertable,Record record[]){			//保存函數int k;//輸入數據 組數及 各個數據 //freopen("Data.txt","r",stdin);printf("你想要存入幾個人的電話\n");cin >> k;while(k > 10){printf("一次至多只能存放10人\n");printf("請重新輸入:\n");cin >> k;}for (int i = 0; i < k; i++){printf("請輸入電話\n");cin >> record[i].Number;printf("請輸入姓名\n");cin >> record[i].Name;printf("請輸入住址\n");cin >> record[i].Address;}//創建哈希表 CreateHashTable(numbertable, record, k);//存入文件中 GoToFile(numbertable);printf("保存成功\n");}

Main.cpp文件

#include"hash.h"
void menu2(){printf("****************************\n");printf("*歡迎使用電話簿(散列表版本)*\n");printf("****** 1存入電話號碼 *******\n");printf("****** 2查找電話號碼 *******\n");printf("****** 0 退出程序    *******\n");printf("****************************\n");
}void menu(){//定義及初始化 Record record[50];			//定義結構體數組，可以存放50個元素的信息HashElem table;				//散列表結構體變量HashTable numbertable;		//散列表結構體指針numbertable = &table;		//給結構體指針賦初值numbertable->data = (Record*)malloc(sizeof(record[0])*MAXSIZE);memset(numbertable->data, 0, sizeof(record[0])*MAXSIZE);numbertable->size = MAXSIZE;numbertable->cnt = 0;int input;do{menu2();printf("請輸入你想要執行的操作\n");scanf("%d", &input);switch (input){case 1:savenumb(numbertable, record);break;case 2:findnumb(numbertable);break;case 0:printf("再見\n");break;default:printf("你的輸入有誤請重新輸入\n");break;}} while (input);}int main(){menu();system("pause");return 0;
}