: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 ^_^
