数据结构，哈希表hash设计实验

• 2020 年 12 月 12 日
• 笔记
• C/C++, 数据结构

• 数据结构实验，hash表
• 采用链地址法处理hash冲突
• 代码全部自己写，转载请留本文连接，
• 附上代码

  #include<stdlib.h>
  #include<stdio.h>
  #include<string.h>
  #include<conio.h>
  
  #define NAMESIZE 20//姓名长度
  #define NULLKEY -32768//hash表空值
  #define HASHSIZE 30//定义hash表长度
  
  typedef struct student
  {
      char name[NAMESIZE];
      int Snum;
      int Tnum;
      student *next=NULL;
  }stu;
  
  typedef struct
  {
      stu ** list;
      int count;
  }HashTable;
  
  int InitHashtable(HashTable *hash)
  {
      hash->count=0;
      hash->list=(stu **)malloc(HASHSIZE *sizeof(stu *));
      if(!hash->list)
          return -1;
      for(int i=0;i<HASHSIZE;i++)
      {
          hash->list[i]=NULL;
      }
      return 1;
  }
  int hash(stu stu)
  {
      int hashseed=0;
      for(int a=0;stu.name[a]!='\0';a++)
      {
          hashseed=hashseed*7+(int)stu.name[a];
      }
      int hashvalue=NULLKEY;
      srand(hashseed);
      hashvalue=rand()%HASHSIZE;
      return hashvalue;
  }
  int intohashtable(HashTable *htable,student *stu)
  {
      int H1=hash(*stu);
      if(htable->list[H1]!=NULL)//hash冲突
      {
          student *p;
          p=(student *)malloc(sizeof(student));
          p=stu;
          p->next=htable->list[H1];
          htable->list[H1]=p;
  
      }
      else
          htable->list[H1]=stu;
      htable->count++;
      return 1;
  }
  int addstudent(HashTable *htable)
  {
      char name[NAMESIZE];
      int snum,tnum;
      stu *stu1;
      stu1=(student *)malloc(sizeof(student));
      printf("请输入姓名：\t");fflush(stdin);
      scanf("%s",name);
      printf("请输入学号：\t");
      scanf("%d",&snum);
      printf("请输入电话号：\t");
      scanf("%d",&tnum);
      if(!name)
      {
          printf("addstudent__error");
          return 0;
      }
      strcpy(stu1->name,name);
      stu1->Snum=snum;
      stu1->Tnum=tnum;
      stu1->next=NULL;
      if(intohashtable(htable,stu1))
          return 1;
      else
      {
          printf("into_error");
          return 0;
      }
  }
  int findhashtable(HashTable *htable)
  {
      printf("\t2-查找\n");
      char name[NAMESIZE];
      printf("请输入要查找的姓名:");
      scanf("%s",name);
      stu stu0;
      strcpy(stu0.name,name);
      stu0.next=NULL;
      stu0.Snum=0;
      stu0.Tnum=0;
      int hashkey;
      hashkey=hash(stu0);
      if(htable->list[hashkey]==NULL)
          printf("查找的值不存在\n");
      if(htable->list[hashkey!=NULL])
      {
          stu *p;
          p=htable->list[hashkey];
          while(p)
          {
              if(name==p->name)
      printf("你找的信息为：\n姓名：%s\t学号：%d\t电话号码%d\n",htable->list[hashkey]->name,htable->list[hashkey]->Snum,htable->list[hashkey]->Tnum);
              if(p->next==NULL)
                  break;
              p=p->next;
          }
      }
      printf("你找的信息为：\n姓名：%s\t学号：%d\t电话号码%d\n",htable->list[hashkey]->name,htable->list[hashkey]->Snum,htable->list[hashkey]->Tnum);
      getch();
  }
  int main()
  {
      HashTable *htable;
      htable =(HashTable *)malloc(sizeof(HashTable));
      InitHashtable(htable);
      int T=1;
      for(int a=1;T;a++)
      {
          system("cls");
          printf("\t哈希表设计实验\n");
          printf("1-添加\n2-查找\n3-输出hash表\n0-退出\n");
          scanf("%d",&T);
          if(T==1)
          for(char c;1;1)
          {
              if(!addstudent(htable))
                  printf("addstudent返回error\n");
              printf("是否继续输入如 y/n:\t");
              fflush(stdin);
              c=getchar();
              if(c=='n'||c=='N')
                  break;
          }
          if(T==2)
              findhashtable(htable);
          if(T==3)
          {
              student *p;
              printf("储存的数据个数为%d个\n",htable->count);
              for(int a=0;a<HASHSIZE;a++)
              {
                  printf("%d\t",a);
                  p=htable->list[a];
                  int t=0;
                  while(p)
                  {
                      t=1;
                      printf("%s\t",p->name);
                     // if(p->next==NULL)
                       //   break;
                      p=p->next;
                  }
                  if(t==0)
                      printf("0");
                  printf("\n");
              }
              getch();
          }
      }
  }