当前位置:   article > 正文

【Dev-c++】C语言数据结构实验——哈希表的建立和查找_希表的开放地址法解决冲突:设有一个数据元素的关键字为key,其在哈希表中的存

希表的开放地址法解决冲突:设有一个数据元素的关键字为key,其在哈希表中的存

一、实验目的

1、掌握哈希表的构造的方法及其解决冲突的机制(开放地址法)

2、掌握常见的查找方法,如折半查找等。

二、实验要求

    1、认真阅读程序,见参考程序7.1。

2、用哈希法建立哈希表并对其进行查找、删除操作的源程序。请将他们输入计算机,编译、连接并运行。

3、保存和截图程序的运行结果,并结合程序进行分析。

三、实验内容和基本原理

    1、哈希表的开放地址法解决冲突:设有一个数据元素的关键字为key,其在哈希表中的存储位置为D=Hkey),此时在哈希表中的存储位置非空,则发生了冲突。那么关键字为key的数据元素在哈希表中的下一个存储位置应该是:

    ND=D+di%m I=1,2,3…,K(K小于等于 m-1)

    这里:m是哈希表的表长;di是增量序列。

                        

参考程序1

  1. //* * * * * * * * * * * * * * * * * * * * * * * *
  2. //*PROGRAM          :哈希表的综合操作           *
  3. //*CONTENT          :Insert,Search,Deltet       *
  4. //* * * * * * * * * * * * * * * * * * * * * * * *
  5. #include <dos.h>
  6. #include <conio.h>
  7. #include <math.h>
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #define MAXSIZE 12 //哈希表的最大容量,与所采//用的哈希函数有关
  11. enum BOOL{False,True};
  12. enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY};
  13.     //哈希表元素的三种状态,没有记录、有记录、//有过记录但已被删除
  14. typedef struct         //定义哈希表的结构
  15. {int  elem[MAXSIZE];   //数据元素体
  16.  HAVEORNOT elemflag[MAXSIZE]; //元素状态标//志,没有记录、有记录、有过记录但已被删除
  17.  int count//哈希表中当前元素的个数
  18. }HashTable;
  19. typedef struct
  20. {int keynum;     //记录的数据域,只有关键字一项
  21. }Record;
  22. void InitialHash(HashTable&); //初始化哈希表
  23. void PrintHash(HashTable);    //显示哈希表中的所//有元素
  24. BOOL SearchHash(HashTable,int,int&); //在哈希表 //中查找元素
  25. BOOL InsertHash(HashTable&,Record);     //在哈//希表中插入元素
  26. BOOL DeleteHash(HashTable&,Record);     //在哈//希表中删除元素
  27. int  Hash(int);  //哈希函数
  28. void main()
  29. {HashTable H;  //声明哈希表H
  30.  char ch,j='y';
  31.  int position;
  32.  Record R;
  33.  BOOL temp;
  34.  textbackground(3);  //设定屏幕颜色
  35.  textcolor(15);
  36.  clrscr();
  37.  //-------------------------程序说明-------------------------------
  38.  printf("This program will show how to operate to a HashTable.\n");
  39.  printf("You can display all elems,search a elem,\ninsert a elem,delete a elem.\n");
  40.  //----------------------------------------------------------------
  41.  InitialHash(H);
  42.  while(j!='n')
  43.     {printf("1.display\n");
  44.      printf("2.search\n");
  45.      printf("3.insert\n");
  46.      printf("4.delete\n");
  47.      printf("5.exit\n");
  48.      scanf(" %c",&ch); //输入操作选项
  49.      switch(ch)
  50.       {case '1':if(H.count) PrintHash(H);  //哈希表//不空
  51.               else printf("The HashTable has no elem!\n");
  52.               break;
  53.        case '2':if(!H.count) printf("The HashTable has no elem!\n"); //哈希表空
  54.               else
  55.                  {printf("Please input the keynum(int) of the elem to search:");
  56.                   scanf("%d",&R.keynum); //输入待查//记录的关键字
  57.                   temp=SearchHash(H,R.keynum,position);
  58.           //temp=True:记录查找成功, //temp=False:没有找到待查记录
  59.                   if(temp) printf("The position of the elem is %d\n",position);
  60.                   else printf("The elem isn't exist!\n"); 
  61.                  }
  62.               break;
  63.        case '3':if(H.count==MAXSIZE)   //哈希表//已满
  64.                  {printf("The HashTable is full!\n");
  65.                   break;
  66.                  }
  67.               printf("Please input the elem(int) to insert:");
  68.               scanf("%d",&R.keynum);  //输入要插入//的记录
  69.               temp=InsertHash(H,R);
  70.                   //temp=True:记录插入成功;//temp=False:已存在关键字相同的记录
  71.               if(temp) printf("Sucess to insert the elem!\n");
  72.               else printf("Fail to insert the elem.The same elem has been exist!\n");
  73.               break;
  74.        case '4':printf("Please input the keynum of the elem(int) to delet:");
  75.               scanf("%d",&R.keynum); //输入要删除记//录的关键字
  76.               temp=DeleteHash(H,R);
  77.                    //temp=True:记录删除成功;//temp=False:待删记录不存在
  78.               if(temp) printf("Sucess to delete the elem!\n");
  79.               else printf("The elem isn't exist in the HashTable!\n");
  80.               break;
  81.        default: j='n';
  82.     }
  83.  }
  84.  printf("The program is over!\nPress any key to shut off the window!\n");
  85.  getchar();getchar();
  86. }
  87. void InitialHash(HashTable &H)
  88. {//哈希表初始化
  89.  int i;
  90.  H.count=0;
  91.  for(i=0;i<MAXSIZE;i++) H.elemflag[i]=NULLKEY;
  92. }
  93. void PrintHash(HashTable H)
  94. {//显示哈希表所有元素及其所在位置
  95.  int i;
  96.  for(i=0;i<MAXSIZE;i++) //显示哈希表中记录所在//位置
  97.     if(H.elemflag[i]==HAVEKEY) //只显示标志为HAVEKEY(存放有记录)的元素
  98.        printf("%-4d",i);
  99.  printf("\n");
  100.  for(i=0;i<MAXSIZE;i++) //显示哈希表中记录值
  101.     if(H.elemflag[i]==HAVEKEY)
  102.        printf("%-4d",H.elem[i]);
  103.  printf("\ncount:%d\n",H.count); //显示哈希表当前 //记录数
  104. }
  105. BOOL SearchHash(HashTable H,int k,int &p)
  106. {//在开放定址哈希表H中查找关键字为k的数据元//素,若查找成功,以p指示
  107.  //待查数据元素在表中的位置,并返回True;否则,//以p指示插入位置,并返回False
  108.  int p1;
  109.  p1=p=Hash(k); //求得哈希地址
  110.  while(H.elemflag[p]==HAVEKEY&&k!=H.elem[p]) 
  111.       //该位置中填有记录并且关键字不相等
  112.    {p++//冲突处理方法:线性探测再散列
  113.     if(p>=MAXSIZE) p=p%MAXSIZE; //循环搜索
  114.     if(p==p1) return False//整个表已搜索完,没//有找到待查元素
  115.    }
  116.  if(k==H.elem[p]&&H.elemflag[p]==HAVEKEY)  //查找成功,p指示待查元素位置
  117.     return True;
  118.  else return False; //查找不成功
  119. }
  120. BOOL InsertHash(HashTable &H,Record e)
  121. {//查找不成功时插入元素e到开放定址哈希表H  //中,并返回True,否则返回False
  122.  int p;
  123.  if(SearchHash(H,e.keynum,p)) //表中已有与e有相//同关键字的元素
  124.     return False;
  125.  else
  126.    {H.elemflag[p]=HAVEKEY;  //设置标志为HAVEKEY,表示该位置已有记录
  127.     H.elem[p]=e.keynum;     //插入记录
  128.     H.count++;          //哈希表当前长度加一
  129.     return True;
  130.    }
  131. }
  132. BOOL DeleteHash(HashTable &H,Record e)
  133. {//在查找成功时删除待删元素e,并返回True,否//则返回False
  134.  int p;
  135.  if(!SearchHash(H,e.keynum,p)) //表中不存在待删 //元素
  136.    return False;
  137.  else
  138.    {H.elemflag[p]=DELKEY; //设置标志为//DELKEY,表明该元素已被删除
  139.     H.count--;    //哈希表当前长度减一
  140.     return True;
  141.    }
  142. }
  143. int Hash(int kn)
  144. {//哈希函数:H(key)=key MOD 11
  145.  return (kn%11);
  146. }

2、对有序表进行非递归折半查找。

  1. int BinSearch1(Seqlist A[],int n,KeyType k)
  2. int low=0,high=n-1,mid;
  3. while(low<=high)
  4. {
  5.        mid=(low+high)/2;
  6.        if(high==k)
  7.        {
  8.               printf("所找的元素%d下标为%d\n",k,mid);
  9.               return mid;
  10.        }
  11.        else if(A[mid].key>k)
  12.        {
  13.               high=mid-1;
  14.        }
  15.        else
  16.        {
  17.               low=mid+1;/*将未完成的代码补全,提示:此处添加一条语句*/
  18.        }
  19.        return -1;
  20. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/500040
推荐阅读
相关标签
  

闽ICP备14008679号