Dictionary ADT

[Dani]

Attached is a small C++ program I wrote for an Algorithms and Data Structures class (CSC120 at Hofstra University).

It takes grocery items from a text file and puts them into a hash table. The user can add, delete, and edit items in the hash table. Upon exiting the program, the text file is updated.

[laoli]

it seems that you know everything , how cuold you do that ? is your major computer science?

[Dani]

As in my signature, CSCGAL stands for Computer SCience gal. I just finished my junior year at Hofstra University for a B.S. in Computer Science and a minor in BCIS (Business Computer Info Systems)

BTW thank you for the compliment!!

[samaru]

Computer Science sucks. ;)

[big_k105]

No way computer sceince is the only way to go. :D

[laoli]

I like playing computer ,but my majoy is electric engineering

[Tekmaven]

Dani's my role model :oops:

[Dani]

aww hehe

[samaru]

I think all of you like Dani a little too much.

[samaru]

I just don't like computer science. I know it's useful and it has a purpose. I just don't like it. The same way I don't like broccoli. I know it's healthy and good for me, but I just don't like it.

Oh by the way, I'm majoring in computer science and minoring in BCIS (Business Computer Info Systems) and Psychology. ;)

[Bob]

In something like the following, you'd want to write your code in such a way as to avoid buffer overflow. The user prompt itself won't be enough:

char* Input::name(){     // get the product name
  char *name;
  name = new char[20];
  if (flag_)
    cout << "   Product name (max 20 characters, no spaces!): ";
  cin >> name;
  return name;
}

I notice that you use float almost everywhere rather than double, and as a general rule I'd say you should use double for all of your floating point variables unless you have good reason to prefer float.

> int stop=0; // stop when stop = 1

I'd probably use a Boolean rather than integer for stop, with true and false values.

> int key; // the key

An example of an unnecessary comment ;)

Some good stuff there though.

[samaru]

Computer Science sucks. ;)

I was just looking over this thread and I still think computer science sucks.

[Asif_NSU]

I was just looking over this thread and I still think computer science sucks.

It seems like Popeye hates Spinach.
Incissor,

Define Computer Science the way u know it/think it is------will you?:rolleyes:

Make that short (2/3 lines at best).

[DragoTJ]

hi do anyone know how to write A Hash Table Implementation of the Dictionary ADT. I wrote using binary Search and as well as Linked list. But i just can't get hang of hash tables.
I did a little research and came out with an algorithm on how to begin, but can anyone or do anyone already have the code written out using this layout? Thnx it would be a lot of help. My final is coming around the corner and I'm trying to understand how hash tables work and it seems that this is the best way to go about understanding it.

/*
* DictionaryRef
* Exported reference type which points to a Dictionary struct
*/
typedef struct Dictionary* DictionaryRef;

/*
* newDictionary
* Allocates and initializes a struct representing an empty Dictionary. Returns a
* pointer to new memory if successful, terminates if not successful.
*/
DictionaryRef newDictionary(void);

/*
* freeDictionary
* Frees all heap memory associated with *pD and sets the reference *pD to NULL
*/
void freeDictionary(DictionaryRef* pD);

/*
* isEmpty
* pre: none
* post: returns 1 (true) if D is empty, 0 (false) otherwise
*/
int isEmpty(DictionaryRef D);

/*
* size
* pre: none
* post: returns the number of entries in D
*/
int size(DictionaryRef D);

/*
* lookup
* pre: none
* post: returns value associated key k, or UNDEF if no such key exists
*/
int lookup(DictionaryRef D, int k);

/*
* insert
* inserts new (key,value) pair into D
* pre: key k currently does not exist in D, i.e. lookup(D, k)==UNDEF
* post: !isEmpty(D), size(D) is increased by one
*/
void insert(DictionaryRef D, int k, int v);

/*
* delete
* deletes pair with the key k
* pre: key k currently exists in D, i.e. lookup(D, k)!=UNDEF
* post: size(D) is decreased by one
*/
void delete(DictionaryRef D, int k);

/*
* makeEmpty
* pre: none
* post: isEmpty(D)
*/
void makeEmpty(DictionaryRef D);

/*
* printDictionary
* pre: none
* post: prints a text representation of D to file pointed to by out.
*/
void printDictionary(DictionaryRef D, FILE* out);

#endif

[Dogtree]

typedef struct Dictionary* DictionaryRef;
I don't like hiding pointers with typedef. It's confusing to readers and maintenance programmers. You would be better off just using Dictionary *.

void delete(DictionaryRef D, int k);
Deletion in a hash table isn't trivial unless you use separate chaining. However, your comment suggests that you're supposed to use some variation of linear probing, so I'll assume that's what you want and show you deletion using a DELETED status.

lookup is just taking a hash of the key and checking that location to see if it's empty. If not, you go to the next location and do the same test. Repeat until you get back to where you started, in which case the key isn't found:

int lookup(Dictionary *dict, int key)
{
  unsigned start = hash(key);

  if (dict->dict[start].status == FULL && key == dict->dict[start].key)
    return dict->dict[start].value;
  else {
    /* Linear probe until found or back at start */
    unsigned probe = start == DICT_SIZE - 1 ? 0 : start + 1;

    while (probe != start) {
      if (dict->dict[probe].status == FULL && key == dict->dict[probe].key)
        return dict->dict[probe].value;
      if (++probe == DICT_SIZE) probe = 0;
    }

    return UNDEF;
  }
}

The tricky part is making sure that you don't go around and around in an infinite loop. Deletion is just a variant of lookup where instead of returning the value, you mark the status as DELETED so that it won't effect future insertions, but still won't be treated as an existing item:

void delete(Dictionary *dict, int key)
{
  unsigned start = hash(key);

  if (dict->dict[start].status == FULL && key == dict->dict[start].key) {
    dict->dict[start].status = DELETED;
    --dict->size;
  } else {
    /* Linear probe until found or back at start */
    unsigned probe = start == DICT_SIZE - 1 ? 0 : start + 1;

    while (probe != start) {
      if (dict->dict[probe].status == FULL && key == dict->dict[probe].key) {
        dict->dict[probe].status = DELETED;
        --dict->size;
      }
      if (++probe == DICT_SIZE) probe = 0;
    }
  }
}

Insertion is, oddly enough, yet another variant of lookup, where if the item doesn't exist in the dictionary, the first empty location is filled using the hashed key as a starting point:

void insert(Dictionary *dict, int key, int value)
{
  if (lookup(dict, key) == UNDEF) {
    unsigned start = hash(key);
    unsigned probe = start;

    if (dict->dict[start].status != EMPTY) {
      while (++probe != start) {
        if (probe == DICT_SIZE) probe = 0;
        if (dict->dict[probe].status == EMPTY)
          break;
      }

      if (probe == start)
        return;
    }

    dict->dict[probe].key = key;
    dict->dict[probe].value = value;
    dict->dict[probe].status = FULL;
    ++dict->size;
  }
}

Those functions are the heart of a hash table. Once they're implemented, the rest of the interface just falls into place. Of course, you also need to come up with a hash function, but that's another topic entirely. ;) After all that, remember that any form of linear probing is a pain in the butt to implement correctly. In fact, I wouldn't be surprised if the code I gave you had bugs because I wrote it in a hurry and didn't test it thoroughly. The same can't be said about separate chaining, which is much easier to get right the first time.

[mohsin]

thnx for sharing lot of info admin

[samsathish]

As in my signature, CSCGAL stands for Computer SCience gal. I just finished my junior year at Hofstra University for a B.S. in Computer Science and a minor in BCIS (Business Computer Info Systems)

BTW thank you for the compliment!!

show me the link for Dictionary project

[Ezzaral]

show me the link for Dictionary project

Her code is attached to the first post. Did you bother to read anything at all before posting this question on a thread that is years old? Additionally, your vocabulary could be improved with the addition of some terms of common courtesy such as "Please".

[aves]

cscgal, thank you very much for the dictionary, I was really desperate about this project I have to give tomorrow. ;)