C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old November 17th, 2012, 01:51 PM
unbreakable unbreakable is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Nov 2012
Posts: 1 unbreakable User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 m 26 sec
Reputation Power: 0
Memory & arrays - How to check if an index within a string array is empty?

Hey, I'm using linear probing and quadratic probing to make 2 different hash tables of the state names given.

On the table, if there is a state, it should be Statename collisions. If there is not a state at that position on the table, it should be just underscrolls.

Right now, even for positons where state names exist, I have statename____collisions. I need to get rid of the ____, so I want to know how to check when there is a string within that array.

Here is the code that I have so far:

Code:
#include <iostream>
#include <string>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

class HashEntry
{
private:
    int keyInserted;
    int amount;

public:
    HashEntry(int keyInserted, int amount)
    {
        this->keyInserted = keyInserted;
        this->amount = amount;
    }

    int obtainKey()
    {
        return keyInserted;
    }

    int getValue()
    {
        return amount;
    }
};

const int TableSize = 100;

class HashMap
{
private:
    HashEntry **HashTable;

public:
    HashMap()
    {
        HashTable = new HashEntry*[TableSize];
        for (int i = 0; i < TableSize; i++)
            HashTable[i] = NULL;
    }

    int findPosition(int keyInserted)
    {
        int hash = (keyInserted % TableSize);
        int counter = 0;
        while (HashTable[hash] != NULL && HashTable[hash]->obtainKey() != keyInserted)
        {
            hash = (hash + 1) % TableSize;
            counter++;
        }
        if (HashTable[hash] == NULL) //if empty
            return -1;
        else
            return hash;
    }
    int Insert2(int keyInserted, int amount) //inserts a keyInserted and amount
    {
        int counter = 0;
        int quadratic = 1;
        int hash = (keyInserted % TableSize);
        int initial = hash;
        while (HashTable[hash] != NULL && HashTable[hash]->obtainKey() != keyInserted)
        {
            hash = (initial + ((quadratic * quadratic))) % TableSize;
            quadratic++;
            counter++;
        }
        if (HashTable[hash] != NULL)
            delete HashTable[hash];
        HashTable[hash] = new HashEntry(keyInserted, amount);
        return counter;
    }
    int searchState(int keyInserted)
    {
        int hash = (keyInserted % TableSize);
        int counter = 0;
        while (HashTable[hash] != NULL && HashTable[hash]->obtainKey() != keyInserted)
        {
            hash = (hash + 1) % TableSize;
            counter++;
        }
        if (HashTable[hash] == NULL) //if empty
            return -1;
        else
            return counter;
    }

    int Insert(int keyInserted, int amount)
    {
        int counter = 0;
        int hash = (keyInserted % TableSize);
        while (HashTable[hash] != NULL && HashTable[hash]->obtainKey() != keyInserted)
        {
            hash = (hash + 1) % TableSize;
            counter++;
        }
        if (HashTable[hash] != NULL)
            delete HashTable[hash];
        HashTable[hash] = new HashEntry(keyInserted, amount);
        return counter;
    }

    int searchState2(int keyInserted)
    {
        int hash = (keyInserted % TableSize);
        int counter = 0;
        int quadratic = 1;
        int initial = hash;
        while (HashTable[hash] != NULL && HashTable[hash]->obtainKey() != keyInserted)
        {
            hash = (initial + ((quadratic * quadratic))) % TableSize;
            quadratic++;
            counter++;
        }
        if (HashTable[hash] == NULL)
            return -1;
        else
            return counter;
    }

    int findPosition2(int keyInserted)
    {
        int hash = (keyInserted % TableSize);
        int counter = 0;
        int quadratic = 1;
        int initial = hash;

        while (HashTable[hash] != NULL && HashTable[hash]->obtainKey() != keyInserted)
        {
            hash = (initial + ((quadratic * quadratic))) % TableSize;
            quadratic++;
            counter++;
        }
        if (HashTable[hash] == NULL)
            return -1;
        else
            return hash;
    }

    ~HashMap()
    {
        for (int i = 0; i < TableSize; i++)
            if (HashTable[i] != NULL)
                delete HashTable[i];
        delete[] HashTable;
    }
};

int main()
{
    HashMap Hash;
    HashMap myHash2;
    string* temporary = new string[50] {};
    string* print = new string[100] {};
    string* print2 = new string[100] {};
    int clsn[100] = {0}, clsn2[100] = {0};
    int numCompare[100] = {0},numCompare2[100] = {0};
    int keyInserted[50] = {0}, i = 0, x = 0, y = 0;
    int ComparisonsAmount = 0, ComparisonsAmount2 = 0;
    int ComparisonsCount = 0, ComparisonsCount2 = 0;
    ifstream infile;
    infile.open ("a4.txt");
    if (infile.good())
    {
        while(infile.peek() != EOF)
        {
            infile >> temporary[i];
            for(y=0; y < temporary[i].length(); y++)
            {
                keyInserted[i] = keyInserted[i] + temporary[i][y];
            }
            Hash.Insert(keyInserted[i],i);
            myHash2.Insert2(keyInserted[i],i);
            Hash.findPosition(keyInserted[i]);
            myHash2.findPosition2(keyInserted[i]);
            print[Hash.findPosition(keyInserted[i])] = temporary[i];
            print2[myHash2.findPosition2(keyInserted[i])] = temporary[i];
            clsn[Hash.findPosition(keyInserted[i])] = Hash.Insert(keyInserted[i],i);
            clsn2[myHash2.findPosition2(keyInserted[i])] = myHash2.Insert2(keyInserted[i],i);
            numCompare[Hash.findPosition(keyInserted[i])] = Hash.searchState(keyInserted[i]);
            numCompare2[myHash2.findPosition2(keyInserted[i])] = myHash2.searchState2(keyInserted[i]);
            i++;
        }
    }
    else
    {
        cout << "a4.txt not found!";
        return -1;
    }
    infile.close();
    cout << "Linear Probing Hash Table: \n";
    for(x=0; x<100; x++)
    {
        if (x%4 == 0)
        {
            if(x < 10)
                cout << "\n" << "0" << x+1 << "|";
            else
                cout << "\n" << x+1 << "|";
        }
        print[x].resize(15,'_');
        cout << print[x] << clsn[x] << "|";
        if (clsn[x] > 0)
            ComparisonsCount++;
        ComparisonsAmount = numCompare[x] + ComparisonsAmount;
    }
    cout << endl;
    cout << "\nNumber of comparisons: " << ComparisonsAmount + ComparisonsCount << "\n";
    cout << endl;
    cout << "\nQuadratic Probing Hash Table: \n";
    for(x=0; x<100; x++)
    {
        if (x%4 == 0)
        {
            if(x < 10)
                cout << "\n" << "0" << x+1 << "|";
            else
                cout << "\n" << x+1 << "|";
        }
        print2[x].resize(15,'_');
        cout << print2[x] << clsn2[x] << "|";
        if (clsn2[x] > 0)
            ComparisonsCount2++;
        ComparisonsAmount2 = numCompare2[x] + ComparisonsAmount2;
    }
    cout << endl;
    cout << "\nNumber of comparisons: " << ComparisonsAmount2 + ComparisonsCount2;
    cout << endl;
    return 0;
}


Here is the assignment given by the professor if you would like to know exactly what the assignment is:
Code:
http://www.filedropper.com/370-f12-a4update

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > Memory & arrays - How to check if an index within a string array is empty?


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.

© 2003-2014 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap