:idea: :idea: hey, guys & experts :D
i'm havin' a big pro now~~i can't past the test 3 now...
i know i may hav a bug but seems too hard for me to find it out
can anyone help me???seg fault... i hav asked many ppl but....plzzzz


====the file====

dict.cc
#include "dict.h"
#include <iostream>
#include <cmath>
using namespace std;

dict_t::dict_t() {
n=0;
m = 5;
table = new record_t[m];
for(int i=0;i<m;i++)
{table.key="";
table.value=0;
}

}

int dict_t::hash(const string &key) const {
float e=0;
long long code=0;
int j;
int k;
j=key.length();

while(j>0){
code=code+int(key[j-1])* pow(128,e);
j--;
e++;
}
k=code%m;
if(table[k].key==""||table[k].key=="DEL")
return k;

else
for(int i=1;i+k<m;i++){
if(table[k+i].key==""||table[k+i].key=="DEL")
return k+i;}
int t;
for(t=0;t<k;t++)
if(table[t].key==""||table[t].key=="DEL")
return t;
return -1;}


int dict_t::get(const string &key) const {
// do the search
for(int i=0;i<m;i++)
{
if(table.key==key)
return table.value;}
return -1;
}

void dict_t::set(const string &key, int value) {
int i;
i=dict_t::hash(key);

table.key=key;
table.value=value;
n++;
double a=n/m;
if(a<=0.3&&m>=10)rehash(m/2);
if(a>=0.8&&m>=5)rehash(m*2);

}

void dict_t::remove(const string &key) {
for(int i=0;i<m;i++)
{
if(table.key==key)//search first
{table.key="DEL";
table.value=0;
n--;
double a=n/m;
if(a<=0.3&&m>=10)rehash(m/2);
if(a>=0.8&&m>=5)rehash(m*2);
return;}
}}

void dict_t::rehash(int new_size) {

p=table;

table=new record_t[new_size];
for(int s=0;s<new_size;s++)
{table[s].key="";
table[s].value=0;
}
int original_size=m;
m=new_size;

for(int i=0;i<original_size;i++)
{
if(p.key!=""&&p.key!="DEL"){
int g;
g=dict_t::hash(p.key);
table[g].key=p.key;
table[g].value=p.value;
}
}
p=NULL;
delete p;

}
head==>
#ifndef __DICT_H // to prevent multiple definition
#define __DICT_H

#include <string>
using std::string; // import the symbol 'string' from 'std::string'

// a dictionary from string to positive integer
class dict_t {
public:
dict_t();

// return the hash table size
unsigned int slots() const { return m; }

// return the number of elements stored
unsigned int size() const { return n; }

// return a non-negative integer hash value of a key
int hash(const string &key) const;

// return the value associated with the key
// return -1 if the key has no associated value
int get(const string &key) const;

// set a new value for the key
// overwrite the old value, if any
void set(const string &key, int value);

// remove the key and its associated value
// do nothing if the key does not exist
void remove(const string &key);

private:
// resize the hash table to a new size
void rehash(int new_size);

int m; // number of slots
int n; // number of elements stored

// a table of m records, n of which storing real data
struct record_t {
string key;
int value;
record_t() : key(""), value(0) {} // default values
} *table,*p;

// extra variables here, if any
};

#endif
test 3(>0<!!)
#include "dict.h"
#include <iostream>
#include <cstdlib>
#include <map>
using namespace std;

// Generating collission
int main(int argc, char *argv[]) {
dict_t d;

// Generate a pair of collission v1 and v2
typedef map<int, string> seen_t;
seen_t seen;
srand(time(0)); // seed prng by current time
string v1, v2;
while (true) {
string s = "";
for (int i = 0; i < 6; ++i) {
s += 'A' + rand() % 26; // random alphabet
}
int h = d.hash(s);

if (seen.find(h) != seen.end()) { // found
v1 = seen.find(h)->second;
v2 = s;
break;
}
seen[h] = s;

d.set(s, 10 + seen.size());
assert(d.size() == seen.size());
assert(d.slots() < 10 || d.slots() < d.size() * 4);
}

d.set(v1, 8);

d.set(v2, 9);
d.remove(v1);
assert(d.get(v1) == -1);

assert(d.get(v2) == 9);
assert(d.size() == seen.size());

for (seen_t::const_iterator it = seen.begin(); it != seen.end(); ++it) {
if (it->second != v2) d.remove(it->second);
}
assert(d.get(v1) == -1);
assert(d.get(v2) == 9);
assert(d.size() == 1);
assert(d.slots() < 10 || d.slots() < d.size() * 4);

cout << argv[0] << ": Test case passed." << endl;
}
i'm using Dev-C++ latest version
really appreciate it if you can help me~~
thx ^_^

First, format your code so that it's readable. Then post the code using code tags so that the formatting isn't lost. Finally, give way more information than "it doesn't work" and "seg fault". Despite how it may seem, we're not here to be your testers and debuggers. Please consider that many of us are professionals that are busy with our own problems, and you need to help us to help you.

That said, a segmentation fault is caused by accessing memory outside of your address space. With a hash table, and it looks like you aren't using separate chaining, that means you've got an invalid index somewhere.

sorry....but still thx all the same
it's done

>it's done
And what was the problem?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.