c++ - 尝试制作哈希表,无法映射所有键,还程序崩溃
问题描述
我必须制作一个带有哈希表的程序,将单个随机字符映射到表中。该程序可以正常工作,但有时会崩溃,也不会映射每个元素。他们中的一些人只是不会进入桌子,桌子上总是有多余的空间。我不知道该怎么做才能解决这两个问题。我使用了 3 个版本的开放寻址,每个版本都会导致相同的 2 个问题。对不起,我的英语不好。先感谢您。
已编辑。当然,我忘记了动态分配。但问题并没有解决。
#include <time.h>
#include <string>
#include <cstdlib>
using namespace std;
int Liniowo(int i, int proby, int rozmiar) // (open adressing, Linear probing)
{
if(i+proby<rozmiar)
return i+proby;
else
{
return -1;
}
}
int Kwadratowo(int i, int proby, int rozmiar) // (open adressing, Quadratic probing)
{
if (i+proby*proby<rozmiar)
return i+proby*proby;
else
{
return -1;
}
}
int Podwojnie(int i, int proby, int rozmiar, char klucz) // (open adressing, Double hashing)
{
if (i*(klucz*(701%klucz)-klucz%13)<rozmiar&&i*(klucz*(701%klucz)-klucz%13)>0)
return i*(klucz*(701%klucz)-klucz%13);
else
{
return -1;
}
}
int modularnie(char c,int rozmiar) // modular
{
return c%rozmiar;
}
void dodaj(char *tab,int max, char c) // add an element
{
int i=modularnie(c, max);
if (tab[i]== '\0')
tab[i]=c;
else
{
int u=0;
int h;
while (tab[i]!= '\0'&&h!=-1)
{
u++;
// h=Kwadratowo(i, u, max);
h=Podwojnie(i,u,max,c);
}
if (h!=-1)
tab[h]=c;
else
cout << "no niestety, nie udalo sie wstawic " <<endl; //"I couldn't map the element"
}
}
int wyszukaj(char *tab,int max, char c) // search an element
{
int i=modularnie(c, max);
int j=i;
if (tab[i]== '\0')
return -1;
while (tab[i]==c)
{
i=(i+1)%max;
if((i==j)||(tab[i]== '\0'))
return -1;
}
return i;
}
int usun(char *tab,int max, char c) // remove an element
{
int r,j,i=wyszukaj(tab,max,c);
j=i;
if (i==-1)
return -1;
tab[i]= '\0';
while (tab[(++i)%max]!= '\0')
{
i%=max;
r=modularnie(tab[i],max);
if (((i<r)&&(r<=j)) || ((r<=j)&&(j<i)) || ((j<i)&&(i<r)))
{
tab[j]=tab[i];
tab[i]= '\0';
j=i;
continue;
}
}
return 0;
}
int main()
{
srand( time( NULL ) );
int ile;
cout << "podaj wielkosc tablicy: "; //"Type the size of the table"
cin >> ile;
char* tab; // EDITED
tab=new char(ile);
for (int n=0; n<ile; n++)
{
tab[n]= '\0';
}
char e;
for (int i=0; i<ile; i++)
{
e='!'+rand()%127;
dodaj(tab, ile, e);
}
for(int j=0; j<ile; j++)
{
cout << j << ", " << tab[j] << endl;
}
return 0;
}
解决方案
推荐阅读
- batch-file - 我将如何编写一个批处理文件来在整个目录上运行 ffmpeg 命令?
- jquery - Jquery 插件,如 dataable,但根据需要具有 ajax 分页和服务器端搜索
- postman - 邮差多张图片
- python - UnicodeDecodeError 错误charmap'编解码器无法解码位置 250 中的字节 0x81:
- javascript - 儿童糖果 Hackerrank 挑战:优化解决方案
- redis - 如果一个主节点只有一个从节点,是否有替代方案可以跳过 Redis 集群中从节点的选举过程?
- html - SVG路径中的工具提示在纯html中工作时不起作用
- java - 在调用操作 api 时获得 403-PERMISSION_DENIED
- spring - 如何访问 org.quartz.Job 类中的应用程序属性?
- android - 使用 Retrofit 获取 Json 中的数据