帮别人改的DS课设1

/*设计哈希表实现电话号码查询系统。
基本要求：
1、设每个记录有下列数据项：电话号码、用户名、地址；
2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；
3、采用再哈希法解决冲突；(采用再哈希法解决冲突,已知一个哈希数为:H(k)=(key)mod13,
产生冲突,采用再哈希法hi=(h(k)+i*h1(k))modm,h1=(k)=kmod11+1
采用再哈希法解决冲突的做法是当待存入散列表的某个元素k在原散列函数H(k)的映射下
与其它数据发生碰撞时,采用另外一个Hash函数Hi(k)(i=1,2,…,n)计算k的存储地址
(Hi均是不同的Hash函数),这种计算直到冲突不再发生为止. )
4、查找并显示给定电话号码的记录；
5、查找并显示给定用户名的记录。*/
/* 针对某个集体（比如所在班级）中的人名设计一个哈希表，
使的平均查找的长度不超过2完成相应的建表和查表的程序

题目要求：

       假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，
    取平均查找长度的上限为2。哈希函数用除留余数法构造，
    用伪随机探测再散列法处理冲突。
       测试数据
       自定义。
*/

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define HASH_LEN 50                      //哈希表的长度        
#define M 47                            //随机数
#define NAME_NO 30                      //人名的个数       

typedef struct
{
 char address[20];
 char telnum[20];
 char py[20];    //名字的拼音
    int k;       //拼音所对应的整数
 int k_tel;
}NAME;

NAME NameList[HASH_LEN];    //全局变量  
      

typedef struct    //哈希表
{
 char *address;
 char *telnum;
 char *py;   //名字的拼音
    int k;      //拼音所对应的整数
 int k_tel;
    int si;     //查找长度
}HASH;

HASH HashList[HASH_LEN];        //用户名为关键字建立哈希表全局变量HASH                    
HASH HashList2[HASH_LEN];        //电话号码为关键字建立哈希表全局变量
int all=0;
void InitNameList() //姓名（结构体数组）初始化         

{
    FILE *fp;
    int r,s0,s1,i,j=0;
 char *f;
 char place1[20],place2[20],place3[20],c;
 if((fp=fopen("123.txt","r"))==NULL)
 {
  printf("不能打开文件%s/n",fp);
  system("pause");
  exit(0);
 }
 c=fgetc(fp);
 while(c!=EOF)
 {
  //逐个读取文件中的字符
  while(c==' ' || c=='/n')
   c=fgetc(fp);
  i=0;
  while(c!=' ' && c!='/n' && c!=EOF)
  {
   //将第一个用户名保存在place1数组中
   *(place1+i)=c;
   c=fgetc(fp);
   i++;
  }
  *(place1+i)='/0';//添加结束符
  while(c==' ' || c=='/n')
   c=fgetc(fp);
  i=0;
  while(c!=' ' && c!='/n' && c!=EOF)
  {
   //将第二个地名保存在place2数组中
   *(place2+i)=c;
   c=fgetc(fp);
   i++;
  }
  *(place2+i)='/0';//添加结束符
  while(c==' ' || c=='/n')
   c=fgetc(fp);
  i=0;
  while(c!=' ' && c!='/n' && c!=EOF)
  {
   //将第二个地名保存在place2数组中
   *(place3+i)=c;
   c=fgetc(fp);
   i++;
  }
  *(place3+i)='/0';//添加结束符
  while(c==' ' || c=='/n')
   c=fgetc(fp);
  strcpy(NameList[j].py,place1);
  strcpy(NameList[j].telnum,place2);
  strcpy(NameList[j].address,place3);
  j++;
 }
 fclose(fp);

  for (i=0;i<NAME_NO;i++)
  {
     s0=0;
     f=NameList[i].py;//printf("%s/n",f);
//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
     for (r=0;*(f+r)!='/0';r++)
         s0=*(f+r)+s0;
     NameList[i].k=s0;
  }
  for (i=0;i<NAME_NO;i++)
  {
     s1=0;
     f=NameList[i].telnum;//printf("%s/n",f);
//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
     for (r=0;*(f+r)!='/0';r++)
         s1=*(f+r)+s1;
     NameList[i].k_tel=s1;
  }
}
void Insert() //姓名（结构体数组）初始化         

{
    int r,s0,s1;
 char *f;
 printf("输入姓名：/n");
 scanf("%s",NameList[all].py);
    printf("输入电话：/n");
 scanf("%s",NameList[all].telnum);
 printf("输入地址：/n");
 scanf("%s",NameList[all].address);

     s0=0;
     f=NameList[all].py;//printf("%s/n",f);
//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
     for (r=0;*(f+r)!='/0';r++)
         s0=*(f+r)+s0;
     NameList[all].k=s0;

     s1=0;
     f=NameList[all].telnum;//printf("%s/n",f);
//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
     for (r=0;*(f+r)!='/0';r++)
         s1=*(f+r)+s1;
     NameList[all].k_tel=s1;

     all++;
}

void CreateHashList() //建立哈希表
{
 int i;
    for (i=0; i<HASH_LEN;i++)
    {
     HashList[i].py="";
  HashList[i].telnum="";
  HashList[i].address="";
     HashList[i].k=0;
  HashList[i].k_tel=0;
     HashList[i].si=0;
    }
    for (i=0;i<HASH_LEN;i++)
    {
     int sum=0;
     int adr=(NameList[i].k)%M;  //哈希函数
     int d=adr;
     if(HashList[adr].si==0)     //如果不冲突
     {
       HashList[adr].k=NameList[i].k;
       HashList[adr].py=NameList[i].py;
       HashList[adr].telnum=NameList[i].telnum;
    HashList[adr].address=NameList[i].address;
       HashList[adr].si=1;
     }
     else   //冲突 
     {
          do
          {
           d=(d+NameList[i].k%10+1)%M;   //伪随机探测再散列法处理冲突   
           sum=sum+1;   //查找次数加1   
         }while (HashList[d].k!=0);

         HashList[d].k=NameList[i].k;
         HashList[d].py=NameList[i].py;
         HashList[d].telnum=NameList[i].telnum;
   HashList[d].address=NameList[i].address;
         HashList[d].si=sum+1;

     }//end if
    }//end for
}
void CreateHashList2() //建立哈希表
{
 int i;
    for (i=0; i<HASH_LEN;i++)
    {
     HashList2[i].py="";
  HashList2[i].telnum="";
  HashList2[i].address="";
     HashList2[i].k=0;
  HashList2[i].k_tel=0;
     HashList2[i].si=0;
    }
    for (i=0;i<HASH_LEN;i++)
    {
     int sum=0;
     int adr=(NameList[i].k_tel)%M;  //哈希函数
     int d=adr;
     if(HashList2[adr].si==0)     //如果不冲突
     {
       HashList2[adr].k_tel=NameList[i].k_tel;
       HashList2[adr].py=NameList[i].py;
       HashList2[adr].telnum=NameList[i].telnum;
    HashList2[adr].address=NameList[i].address;
       HashList2[adr].si=1;
     }
     else   //冲突 
     {
          do
          {
           d=(d+NameList[i].k_tel%10+1)%M;   //伪随机探测再散列法处理冲突   
           sum=sum+1;   //查找次数加1   
         }while (HashList2[d].k_tel!=0);

         HashList2[d].k_tel=NameList[i].k_tel;
         HashList2[d].py=NameList[i].py;
         HashList2[d].telnum=NameList[i].telnum;
   HashList2[d].address=NameList[i].address;
         HashList2[d].si=sum+1;

     }//end if
    }//end for
}
void   FindList() //查找   
{ 
    char name[20]={0};
    int s0=0,r,sum=1,adr,d;
    printf("/n请输入用户名的拼音:");
    scanf("%s",name);
    for(r=0;r<20;r++)   //求出姓名的拼音所对应的整数(关键字)
        s0+=name[r];
    adr=s0%M;   //使用哈希函数
    d=adr;
if(HashList2[d].k==0)printf("无此记录! ");
while(HashList[adr].k==s0 && HashList[d].k!=0)          //分3种情况进行判断
{
 printf("/n姓名:%s   电话号码:%s   地址:%s   关键字:%d   查找长度为: 1",HashList[d].py,HashList[d].telnum,HashList[d].address,s0);
    d=(d+s0%10+1)%M;       //伪随机探测再散列法处理冲突
    sum=sum+1;
   
}

}
void   FindList_tel() //查找   
{ 
    char telnum[20]={0};
    int s1=0,r,sum=1,adr,d;
    printf("/n请输入用户的电话号码:");
    scanf("%s",telnum);
    for(r=0;r<20;r++)   //求出姓名的拼音所对应的整数(关键字)
        s1+=telnum[r];
    adr=s1%M;   //使用哈希函数
    d=adr;
if(HashList2[d].k_tel==0)printf("无此记录! ");
while(HashList2[adr].k_tel==s1 && HashList2[d].k_tel!=0)          //分3种情况进行判断
{
 printf("/n姓名:%s   电话号码:%s   地址:%s   关键字:%d   查找长度为: 1",HashList2[d].py,HashList2[d].telnum,HashList2[d].address,s1);
    d=(d+s1%10+1)%M;       //伪随机探测再散列法处理冲突
    sum=sum+1;
}

}

void   Display() // 显示哈希表      

{
 int i;
    float average=0;
    printf("/n/n地址/t关键字/t搜索长度 H(key)  用户名/t/t电话号码/t地址/n"); //显示的格式
    for(i=0; i<50; i++)
 {
         printf("%d ",i);
         printf("/t%d ",HashList[i].k);
         printf("/t%d ",HashList[i].si);
         printf("/t%d ",HashList[i].k%M);
         printf("/t %s ",HashList[i].py);
   printf("/t%s",HashList[i].telnum);
   printf("/t%s",HashList[i].address);
         printf("/n");
 }
    for (i=0;i<HASH_LEN;i++)
        average+=HashList[i].si;
    average/=NAME_NO;
    printf("/n/n平均查找长度：ASL(%d)=%f /n/n",NAME_NO,average);
}
void menu()
{
 printf("/n                  电话号码查询系统(哈希表)的建立和查找/n");
    printf("               *-------------------------------------------*/n");
 printf("               |              A. 从文件输入用户信息        |/n");
    printf("               |              S. 从键盘输入用户信息        |/n");
 printf("               |              F. 查找用户名                |/n");
    printf("               |              T. 查找电话号码              |/n");
 printf("               |              D. 显示哈希表                |/n");
    printf("               |              Q. 退出                      |/n");
    printf("               *-------------------------------------------*/n");
}

void scan()
{
 int quit=0,d;
 while(!quit)
 {
        printf("1.插入用户信息:/n");
  printf("0.退出.../n");
  scanf("%d",&d);
     if(d==1)
        Insert();
     else if(d==0)
     quit=1;
  else
   continue;
 }
}
void main()
{
 char ch;  
    while(1)
 {
    menu();
       printf("/n       请选择操作:");
       fflush(stdin);//键盘输入清屏
       ch=getchar();
       if (ch=='D'||ch=='d') Display();
    else if (ch=='A'||ch=='a') InitNameList();
    else if (ch=='S'||ch=='s') scan();
       else if (ch=='F'||ch=='f') FindList();
    else if (ch=='T'||ch=='t') FindList_tel();
       else if (ch=='Q'||ch=='q') return;
       else printf("/n请输入正确的选择!");
 CreateHashList();
 CreateHashList2();
 }
}