山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

虚心求教

楼主happy_cser（菜鸟也编程）2005-06-01 16:38:30 在 C/C++ / C语言提问

我写了个采用连表法解决哈希冲突的程序,不过调试总出错误报告..
请高手帮看一下,给小弟一点意见,谢谢!
#include "stdio.h"
#include "stdlib.h"
typedef int KeyType;

typedef struct
{
KeyType key;
}DataType;

typedef struct Node
{
DataType data;
struct Node *next;
}HashNode;

typedef struct
{
HashNode *ho[100];
int tablesize;
int currentsize;
}HashTable;

int Initiate(HashTable *hash,int mSize)
{
int i;
hash->tablesize=mSize;
for(i=0;i<mSize;i++)
{
hash->ho[i]->data.key=0;
hash->ho[i]->next=NULL;
}
hash->currentsize=0;
return 1;
}

int Findpos(HashTable *hash,DataType x)
{
int i,j;
i=x.key%hash->tablesize;
j=i;
HashNode *p;
p=hash->ho[j]->next;
while(p!=NULL)
if(x.key==p->data.key)
return j;
else
p=p->next;
return -j;
}

int Insert(HashTable *hash,DataType x)
{
int i=Findpos(hash,x);
if(i>0)
{
printf("The key has been in the hashtable!\n");
return 0;
}
else
{
HashNode *p;
p=(HashNode *)malloc(sizeof(HashNode));
if(p==NULL)
return 0;
else
{
p->data=x;
p->next=hash->ho[i]->next;
hash->ho[i]->next=p;
hash->currentsize++;
return 1;
}
}
}

int main(void)
{
int i,j,mSize;
DataType data[100];
HashNode *p;
HashTable *hash;
printf("Input the value of mSzie:");
scanf("%d",&mSize);
Initiate(hash,mSize);
printf("%d",hash->tablesize);
for(i=0;i<mSize;i++)
{
scanf("%d",&data[i].key);
j=Findpos(hash,data[i]);
if(Insert(hash,data[i])==0)
return 1;
}
for(i=0;i<11;i++)
{
p=hash->ho[i]->next;
while(p)
{
printf("%d",p->data.key);
p=p->next;
}
}
}
问题点数：100、回复次数：10Top

1 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-06-01 16:50:31 得分 10

HashTable *hash;
-----------
hash没有分配内存，就在Initiate里用了。Top

2 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-06-01 16:52:04 得分 10

hash = (HashTable *)malloc(sizeof(HashTable));Top

3 楼happy_cser（菜鸟也编程）回复于 2005-06-01 17:44:01 得分 0

加上这条语句还是出现同样的错误!郁闷中!Top

4 楼herryhuang（Herry）回复于 2005-06-01 22:09:08 得分 25

你把楼上说的这一句加到哪里了，要加到主函数中

hash->ho[i]->data.key=0;

这里也没有申请内存，建议先看看指针的用法，内存使用前要申请的。

Top

5 楼mostideal（三甲）回复于 2005-06-02 00:14:21 得分 10

先顶。。Top

6 楼nasi00（莫傲·逍遥）回复于 2005-06-02 01:58:32 得分 5

建议先用STL中的list让hash跑起来，然后确定了hash没写错以后，在单独写list，当然，如果没要求自己写list的话，用STL当然更好了

或者你改成用线性探测的方法，就不用list了，呵呵Top

7 楼happy_cser（菜鸟也编程）回复于 2005-06-03 09:32:48 得分 0

我根据上面的意见做一些修改,不过还是报错,程序只执行到插入函数那里.....
WHY??????

#include "stdio.h"
#include "stdlib.h"
typedef int KeyType;

typedef struct
{
KeyType key;
}DataType;

typedef struct Node
{
DataType data;
struct Node *next;
}HashNode;

typedef struct
{
HashNode *ho[100];
int tablesize;
int currentsize;
}HashTable;

int Initiate(HashTable *hash,int mSize)
{
int i;
hash->tablesize=mSize;
for(i=0;i<mSize;i++)
{
if(hash->ho[i]=(HashNode*)malloc(sizeof(HashNode)))
{
hash->ho[i]->data.key=0;
hash->ho[i]->next=NULL;
}
else
return 0;
}
hash->currentsize=0;
return 1;
}

int Findpos(HashTable *hash,DataType x)
{
int i,j;
i=x.key%hash->tablesize;
printf("%d",hash->tablesize);
j=i;
HashNode *p;
p=hash->ho[j]->next;
while(p!=NULL)
if(x.key==p->data.key)
return j;
else
p=p->next;
return -j;
}

int Insert(HashTable *hash,DataType x)
{
int i=Findpos(hash,x);
if(i>0)
{
printf("The key has been in the hashtable!\n");
return 0;
}
else
{
HashNode *q;
q=(HashNode *)malloc(sizeof(HashNode));
if(q==NULL)
return 0;
else
{
q->data=x;
q->next=hash->ho[i]->next;
hash->ho[i]->next=q;
hash->currentsize++;
return 1;
}
}
}

int main(void)
{
int i,j,mSize;
DataType data[100];
HashNode *r;
HashTable *hash;
hash=(HashTable*)malloc(sizeof(HashTable));
printf("Input the value of mSzie:");
scanf("%d",&mSize);
Initiate(hash,mSize);
for(i=0;i<mSize;i++)
{
scanf("%d",&data[i].key);
j=Findpos(hash,data[i]);
printf("\nj=%d",j);
if(Insert(hash,data[i])==0)
return;
}
for(i=0;i<11;i++)
{
r=hash->ho[i]->next;
while(r)
{
printf("%d",r->data.key);
r=r->next;
}
}
}Top

8 楼happy_cser（菜鸟也编程）回复于 2005-06-03 09:59:30 得分 0

100分哦--!
呵呵 ,大家来看看啊--很容易得的!Top

9 楼foochow（无聊,灌水......）回复于 2005-06-03 10:26:33 得分 20

else
{
q->data=x;
q->next=hash->ho[i]->next;//这里
hash->ho[i]->next=q;//这里有问题,自己检查下
hash->currentsize++;
return 1;
}Top

10 楼nasi00（莫傲·逍遥）回复于 2005-06-07 06:03:47 得分 20

你先不要自己写链表了，先用STL吧，方法如下：

代码是随便写的，假设数据类型是int的

#include <list>
#define MAX 100

std::list<int> h[MAX];

初始化：

for(int i = 0; i < MAX; i++) h[i].clear();

然后比如你的hash函数是hash(x)的话

int k = hash(data); // data是数据
h[k].push_back(data);

这样就可以插入了

然后对每个链表，通过迭代器访问一下就可以遍历了，或者用find()也可以

然后，再自己写一个链表的类，确定能用以后，再替换掉STL的list，如果不是非要自己写链表的话，用STL就好了Top