print?#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define Size 11
typedef struct{
char name[30];
char address[20];
//float num;
char num[30];
int c;//統計比較次數
}record;
typedef struct{
record data[Size];
int count;
int size;
}Hashtable;
void init(Hashtable &h)
{
for(int i=0;i<Size;i++)
{h.data[i].num[0]=0;
h.data[i].c=0;}//!
h.size=Size;
h.count=0;
}
int exchange(char str[])
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
int HashSearch1(Hashtable &h,char *str,int &p) //線性探測
{
int i,j,k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
return j;
h.data[j].c++;//!
}//沒有發生沖突，比較一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
h.data[j].c++;//!
i=(j+1)%Size;//第1次解決沖突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[i].num)==0)
{
h.data[j].c++;//!
return i;
}//發生沖突，比較若干次查找成功
i=(i+1)%Size; //向後探測一個位置
}
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功
}
}
}
int HashSearch2(Hashtable &h,char *str,int &p)
{
int i,j,t=1,d=1;
int k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return j;
} //沒有發生沖突，比較一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
i=(j+d)%Size;//第1次解決沖突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[i].num)==0)
{
h.data[j].c++;//!
return i;
}
if(t>0)
t=-1*d*d;
else
{
d=d+1;
t=-1*d*d ;
}
i=(j+t+Size)%Size; //探測一個新的位置
while(i<0)
{
h.data[j].c++;//!
i=(i+Size)%Size;
} }
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功時插入
}
}
}
void disp(Hashtable h)
{
printf("電話簿中所有電話記錄如下:\n");
for(int i=0;i<Size;i++)
{
if(h.data[i].num[0])
printf("-.%7s s %s\n",i,h.data[i].name,h.data[i].address,h.data[i].num);
}
}
//
int compasl(Hashtable h)
{
int sum=0;
for(int i=0;i<Size;i++)
sum+=h.data[i].c;
return sum;
}
int menu()
{
int num;
while(1)
{
system("cls");
printf("\n---------電話管理系統模擬(哈希表實現)---------\n");
printf("\n**********************************************\n");
printf("\n 0.退出電話簿 1.已存在的電話記錄 \n");
printf("\n 2.添加記錄到電話簿1 3.添加記錄到電話簿2 \n");
printf("\n 4.查找電話簿1通訊人 5.查找電話簿2通訊人 \n");
printf("\n 6.電話簿1查找ASL 7.電話簿2查找ASL \n");
printf("\n**********************************************\n");
printf("\n----------------------------------------------\n");
printf("\n請您選擇操作(0--7):\n");
scanf("%d",&num);
if(num<0||num>7)
printf("您的選擇有誤，請重新選擇!\n");
break;
}
return num;
}
void main()
{
Hashtable h1,h2;
int i,j,n,a,m,flag=1;
char num[30];
char name[30],address[50];
init(h1);init(h2);
while(1)
{
j=menu();
switch(j){
case 0:printf("(@ @) 謝謝使用，再見! (^ ^)\n");
exit(0);
getch();
break;
case 1:
if(flag){
FILE *fp;
if((fp=fopen("1234.txt","r+"))==NULL)
{
puts("成功導入電話記錄！");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%s%s%s",name,address,num);
HashSearch1(h1,num,a);
strcpy(h1.data[a].num,num);
strcpy(h1.data[a].address,address);
strcpy(h1.data[a].name,name);
h1.count++;
}
puts("\t成功將電話記錄導入電話簿1!");
disp(h1);
fclose(fp);
if((fp=fopen("1234.txt","r+"))==NULL)
{
puts("導入電話記錄失敗");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%s%s%s",name,address,num);
HashSearch2(h2,num,a);
strcpy(h2.data[a].num,num);
strcpy(h2.data[a].address,address);
strcpy(h2.data[a].name,name);
h2.count++;
}
puts("\t成功將電話記錄導入電話簿2!");
disp(h2);
fclose(fp);
printf("按任意鍵繼續!\n");
getch();}
flag=0;
break;
case 2:
printf("添加電話記錄到電話簿1:\n");
printf("請輸入您要添加電話記錄的數目：\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("請輸入第%d條電話記錄的姓名、地址和電話號碼(用空格隔開)\n",i+1);
scanf("%s%s%s",name,address,num);
if(HashSearch1(h1,num,a))
{
printf("已存在");
i--;
}
else
{
strcpy(h1.data[a].num,num);
strcpy(h1.data[a].address,address);
strcpy(h1.data[a].name,name);
h1.count++;
}
}
disp(h1);
printf("按任意鍵繼續!\n");
getch();
break;
case 3:printf("添加電話記錄到電話簿2:\n");
printf("請輸入您要添加電話記錄的數目\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("請輸入第%d條電話記錄的姓名、地址和電話號碼(用空格隔開)\n",i+1);
scanf("%s%s%s",name,address,num);
if(HashSearch2(h2,num,a))
{
printf("已存在");
i--;
}
else
{
strcpy(h2.data[a].num,num);
strcpy(h2.data[a].address,address);
strcpy(h2.data[a].name,name);
h2.count++;
}
}
disp(h2);
printf("按任意鍵繼續!\n");
getch();
break;
case 4:disp(h1);
printf("請輸入您要在電話簿1中查找的人的電話號碼:\n");
scanf("%s",num);
printf("\n");
if(m=HashSearch1(h1,num,a))
{
printf("查找的結果為:\n");
printf("您要查找的人的姓名、地址和電話號碼分別為:\n%s,%s,%s\n",h1.data[m].name,h1.data[m].address,h1.data[m].num);
}
else
printf("對不起，沒有您要找的人!\n");
printf("按任意鍵繼續!\n");
getch();
break;
case 5:disp(h2);
printf("請輸入您要在電話簿2中查找的人的電話號碼:\n");
scanf("%s",num);
printf("\n");
if(m=HashSearch2(h2,num,a))
{
printf("查找的結果為:\n");
printf("您要查找的人的姓名、地址和電話號碼分別為:\n%s,%s,%s\n",h2.data[m].name,h2.data[m].address,h2.data[m].num);
}
else
printf("對不起，沒有您要找的人!\n");
printf("按任意鍵繼續!\n");
getch();
break;
case 6:printf("在電話簿1中查找的ASL為:\n");
printf("%d %d\n",compasl(h1),h1.count);
printf("按任意鍵繼續!\n");
getch();
break;
case 7:printf("在電話簿2中查找的ASL為:\n");
printf("%d %d\n",compasl(h2),h2.count);
printf("按任意鍵繼續!\n");
getch();
break;
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define Size 11
typedef struct{
char name[30];
char address[20];
//float num;
char num[30];
int c;//統計比較次數
}record;
typedef struct{
record data[Size];
int count;
int size;
}Hashtable;
void init(Hashtable &h)
{
for(int i=0;i<Size;i++)
{h.data[i].num[0]=0;
h.data[i].c=0;}//!
h.size=Size;
h.count=0;
}
int exchange(char str[])
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
int HashSearch1(Hashtable &h,char *str,int &p) //線性探測
{
int i,j,k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
return j;
h.data[j].c++;//!
}//沒有發生沖突，比較一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
h.data[j].c++;//!
i=(j+1)%Size;//第1次解決沖突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[i].num)==0)
{
h.data[j].c++;//!
return i;
}//發生沖突，比較若干次查找成功
i=(i+1)%Size; //向後探測一個位置
}
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功
}
}
}
int HashSearch2(Hashtable &h,char *str,int &p)
{
int i,j,t=1,d=1;
int k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return j;
} //沒有發生沖突，比較一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
i=(j+d)%Size;//第1次解決沖突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[i].num)==0)
{
h.data[j].c++;//!
return i;
}
if(t>0)
t=-1*d*d;
else
{
d=d+1;
t=-1*d*d ;
}
i=(j+t+Size)%Size; //探測一個新的位置
while(i<0)
{
h.data[j].c++;//!
i=(i+Size)%Size;
} }
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功時插入
}
}
}
void disp(Hashtable h)
{
printf("電話簿中所有電話記錄如下:\n");
for(int i=0;i<Size;i++)
{
if(h.data[i].num[0])
printf("-.%7s s %s\n",i,h.data[i].name,h.data[i].address,h.data[i].num);
}
}
//
int compasl(Hashtable h)
{
int sum=0;
for(int i=0;i<Size;i++)
sum+=h.data[i].c;
return sum;
}
int menu()
{
int num;
while(1)
{
system("cls");
printf("\n---------電話管理系統模擬(哈希表實現)---------\n");
printf("\n**********************************************\n");
printf("\n 0.退出電話簿 1.已存在的電話記錄 \n");
printf("\n 2.添加記錄到電話簿1 3.添加記錄到電話簿2 \n");
printf("\n 4.查找電話簿1通訊人 5.查找電話簿2通訊人 \n");
printf("\n 6.電話簿1查找ASL 7.電話簿2查找ASL \n");
printf("\n**********************************************\n");
printf("\n----------------------------------------------\n");
printf("\n請您選擇操作(0--7):\n");
scanf("%d",&num);
if(num<0||num>7)
printf("您的選擇有誤，請重新選擇!\n");
break;
}
return num;
}
void main()
{
Hashtable h1,h2;
int i,j,n,a,m,flag=1;
char num[30];
char name[30],address[50];
init(h1);init(h2);
while(1)
{
j=menu();
switch(j){
case 0:printf("(@ @) 謝謝使用，再見! (^ ^)\n");
exit(0);
getch();
break;
case 1:
if(flag){
FILE *fp;
if((fp=fopen("1234.txt","r+"))==NULL)
{
puts("成功導入電話記錄！");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%s%s%s",name,address,num);
HashSearch1(h1,num,a);
strcpy(h1.data[a].num,num);
strcpy(h1.data[a].address,address);
strcpy(h1.data[a].name,name);
h1.count++;
}
puts("\t成功將電話記錄導入電話簿1!");
disp(h1);
fclose(fp);
if((fp=fopen("1234.txt","r+"))==NULL)
{
puts("導入電話記錄失敗");
exit(0);
}
fscanf(fp,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%s%s%s",name,address,num);
HashSearch2(h2,num,a);
strcpy(h2.data[a].num,num);
strcpy(h2.data[a].address,address);
strcpy(h2.data[a].name,name);
h2.count++;
}
puts("\t成功將電話記錄導入電話簿2!");
disp(h2);
fclose(fp);
printf("按任意鍵繼續!\n");
getch();}
flag=0;
break;
case 2:
printf("添加電話記錄到電話簿1:\n");
printf("請輸入您要添加電話記錄的數目：\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("請輸入第%d條電話記錄的姓名、地址和電話號碼(用空格隔開)\n",i+1);
scanf("%s%s%s",name,address,num);
if(HashSearch1(h1,num,a))
{
printf("已存在");
i--;
}
else
{
strcpy(h1.data[a].num,num);
strcpy(h1.data[a].address,address);
strcpy(h1.data[a].name,name);
h1.count++;
}
}
disp(h1);
printf("按任意鍵繼續!\n");
getch();
break;
case 3:printf("添加電話記錄到電話簿2:\n");
printf("請輸入您要添加電話記錄的數目\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("請輸入第%d條電話記錄的姓名、地址和電話號碼(用空格隔開)\n",i+1);
scanf("%s%s%s",name,address,num);
if(HashSearch2(h2,num,a))
{
printf("已存在");
i--;
}
else
{
strcpy(h2.data[a].num,num);
strcpy(h2.data[a].address,address);
strcpy(h2.data[a].name,name);
h2.count++;
}
}
disp(h2);
printf("按任意鍵繼續!\n");
getch();
break;
case 4:disp(h1);
printf("請輸入您要在電話簿1中查找的人的電話號碼:\n");
scanf("%s",num);
printf("\n");
if(m=HashSearch1(h1,num,a))
{
printf("查找的結果為:\n");
printf("您要查找的人的姓名、地址和電話號碼分別為:\n%s,%s,%s\n",h1.data[m].name,h1.data[m].address,h1.data[m].num);
}
else
printf("對不起，沒有您要找的人!\n");
printf("按任意鍵繼續!\n");
getch();
break;
case 5:disp(h2);
printf("請輸入您要在電話簿2中查找的人的電話號碼:\n");
scanf("%s",num);
printf("\n");
if(m=HashSearch2(h2,num,a))
{
printf("查找的結果為:\n");
printf("您要查找的人的姓名、地址和電話號碼分別為:\n%s,%s,%s\n",h2.data[m].name,h2.data[m].address,h2.data[m].num);
}
else
printf("對不起，沒有您要找的人!\n");
printf("按任意鍵繼續!\n");
getch();
break;
case 6:printf("在電話簿1中查找的ASL為:\n");
printf("%d %d\n",compasl(h1),h1.count);
printf("按任意鍵繼續!\n");
getch();
break;
case 7:printf("在電話簿2中查找的ASL為:\n");
printf("%d %d\n",compasl(h2),h2.count);
printf("按任意鍵繼續!\n");
getch();
break;
}
}
}
下面是課程設計的報告：
一、課程設計的目的與要求
1. 目的: 應用數據結構和算法來設計相應的程序，培養學生問題求解模塊的框架設計和詳細設計、相關程序實現和調試能力，完成創新能力和實踐能力的訓練。
2. 要求: 用高級程序設計語言C編碼，用VC++開發平台調試。
二、設計正文
（一） 課程設計題目
設計哈希表實現電話號碼查詢系統
（二） 需求分析
設每個記錄有下列數據項：電話號碼、用戶名、地址；
(1)數據導入（從文件中讀取各記錄，分別以電話號碼為關鍵字建立哈希表）；
(2)從鍵盤讀記錄，並插入到哈希表中；
(3)查找並顯示給定電話號碼的記錄；
(4)將電話號碼記錄保存在文件中；
(5)嘗試各種不同類型處理沖突的方法,考察平均查找長度的變化。
分析:由於題目要求以電話號碼為關鍵字建表，考慮到電話號碼長短不一，如果直接以表示電話號碼的字符串為關鍵字，可能會造成一定的麻煩。故而，利用一個函數將表示電話號碼的字符串轉換成其相應的數字，然後把這些數字之和作為關鍵字即可將上述麻煩解除。
（三） 概要設計
為了實現上述程序的功能，需要定義下列抽象數據類型：
ADT hashtable {
數據對象：哈希表中存儲的個條電話記錄；
數據關系：表中相鄰元素之間有前去和後繼的關系；
基本操作：
init(Hashtable &h)
操作結果：初始化了哈希表；
int exchange(char str[])
操作結果：球取關鍵字；
int HashSearch1(Hashtable &h,char *str,int &p)
操作結果：在表中線性探測數據，返回數據的插入位置；
int HashSearch2(Hashtable &h,char *str,int &p)
操作結果：在表中二次探測數據，返回數據的插入位置；
void disp(Hashtable h)
操作結果：顯示出哈希表中儲存的電話記錄；
}ADT hashtable
將每個人的信息作為一條記錄，包括電話號碼、用戶名、地址，還有一個整型變量用來記錄沖突的次數，便於計算ASL,然後哈希表由記錄數組、表現存量、容量組成,具體數據類型見下：
typedef struct {
char name[30];
char address[20];
char num[30];
}record;
typedef struct{
record data[Size];
int count;
int size;
}Hashtable;
關鍵字處理-----利用一個函數將表示電話號碼的字符串轉換成其相應的數字，然後把這些數字之和作為關鍵字。具體函數見下：
int exchange(char str[])
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
最後就是用兩種方法建表，分別用線性和二次探測的方法來處理沖突。
本程序所有函數清單：
void init(Hashtable &h)；//哈希表的初始化
int exchange(char str[])；//求取關鍵字
int HashSearch1(Hashtable &h,char *str,int &p)；//線性探測處理沖突
int HashSearch2(Hashtable &h,char *str,int &p)；//二次探測處理沖突
void disp(Hashtable h)；//顯示哈希表
int menu()；//主菜單
void main()；//主函數
各函數之間的調用關系是：
主函數main（）
菜單函數menu（）
線性探測解決沖突hashserch1（）
查找用戶
考察ASL1
二次探測解決沖突hashsearch2（）
查找用戶
考察ASL
顯示電話簿disp（）
（四） 詳細設計
1）為了實現上述程序的功能，需要定義下述數據類型：
typedef struct{
char name[30];
char address[20];
//float num;
char num[30];
int c;//統計比較次數
}record; //記錄
typedef struct{
record data[Size];
int count;
int size;
}Hashtable; //哈希表
2）一些主要的函數：
int exchange(char str[]) //關鍵字處理函數
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
int HashSearch1(Hashtable &h,char *str,int &p) //線性探測
{
int i,j,k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
return j;
h.data[j].c++;//!
}//沒有發生沖突，比較一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
h.data[j].c++;//!
i=(j+1)%Size;//第1次解決沖突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return i;
}//發生沖突，比較若干次查找成功
i=(i+1)%Size; //向後探測一個位置
}
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功
}
}
}
int HashSearch2(Hashtable &h,char *str,int &p) //二次探測
{
int i,j,t=1,d=1;
int k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return j;
} //沒有發生沖突，比較一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
i=(j+d)%Size;//第1次解決沖突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return i;
}
if(t>0)
t=-1*d*d;
else
{
d=d+1;
t=-1*d*d ;
}
i=(j+t+Size)%Size; //探測一個新的位置
while(i<0)
{
h.data[j].c++;//!
i=(i+Size)%Size;
}
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功時插入
}
}
}
}
（五） 調試分析
本實驗的運行環境是VC++。按照要求，應該事先導入一些記錄，以下為本實驗的測試數據：
4
侯進斌 北京 6627584
王璐 太原 6650370
唐磊 天津 6626074
高啟波 太原 6651805
然後按照菜單中的提示操作即可
（六） 使用說明
程序名為hashtable.exe，運行環境為VC++。由於菜單中有詳細的操作提示，您只要按照上面的提示一步一步進行操作即可。
（七）測試數據
程序運行後將會出現以下菜單：
選擇1，立即會顯示下面窗口，顯示已存在的記錄：
再選操作2，可以向電話簿1裡添加記錄，如下：
操作3，向電話簿2中添加記錄，如下：
然後還可以進行查詢操作，選4，可以在電話簿1中查詢您想要的找的人的信息：
同理，選5還可以在電話簿2中作相應的查詢：
如果您想比較著看一下在電話簿1中查找的速度（專業術語：ASL），可以選擇操作6：
同理還可以查看電話簿2的這項功能：
如果您想結束操作，直接選0，即可退出該系統：
以上就是本系統的主要功能。
三、課程設計總結或結論
1．完成的工作
該實驗的所有要求：哈希表的創建，用兩種不同的方法處理沖突，考察各種處理沖突方法的ASL；
2．未完成的工作
無；
3．所需做的改進
應該嘗試更多的處理沖突的方法
一些代碼的效率很低，有待改進
