Siddharth
Siddharth

Reputation: 373

Runtime error while executing simple hashing program

I am creating a simple hashing program with chaining, the compiler didn't give me any error, but the program itself is crashing at the time of execution. The program logs the time difference taken by search function to a file(The dataset is x% of 1000 randomly generated numbers hashed)(I don't know if it something with the logic itself, or some technical error. I am using pocketcpp as, err..ide). Code :

#include <fstream>
#include <iostream>
#include <chrono>
#include <ctime>
#include <cstdlib>
#include <cstring>

/*Code by RN:121503 * Date: 04-11-2014*/

using namespace std;

typedef struct storagelist
{
    int value;
    storagelist *next;
};

storagelist *startArray[100];

int simplehash(int n)
{
    int index;
    index=n%1000;
    return index;
}

int simplesearch(int n)
{
    int index;
    int i=0;
    storagelist *tempPointer=startArray[n]->next;
    index=simplehash(n);
    //Base address of array, i.e. array index will be null.
    if(startArray[n]->next==NULL)
    {
        //cout<<"No such key/value exist \n";
    }
    else
    {
        do
        {
            if(tempPointer->value==n)
            {
                //cout<<"Key found \n";
                break;
            }
            else
            {
                tempPointer=tempPointer->next;
            }
        }while(tempPointer->next!=NULL);
    }
}

void simpleinsert(int n)
{
    int tempIndex;
    storagelist *tempPointer;
    storagelist *tempPointertwo;
    tempIndex=simplehash(n);
    if(startArray[tempIndex]->next==NULL)
    {
        tempPointer=new storagelist;
        tempPointer->value=n;
        startArray[tempIndex]->next=tempPointer;
        tempPointer->next=NULL;
    }
    else
    {
        while(tempPointer->next!=NULL)
        {
            tempPointer=tempPointer->next;
        }
        tempPointertwo=new storagelist;
        tempPointertwo->value=n;
        tempPointer->next=tempPointertwo;
        tempPointertwo->next=NULL;
    }
}

int main()
{
    int tempRandom;
    int loopHelp;
    int randomBackup[100];
    //File handeling
    ofstream myfile;
    //Clock elements
    clock_t start, end;
    //Populating starting indices with NULL
    for(int i=0;i<100;i++)
    {
        startArray[i]->next=NULL;
    }
    /*generating 1000 random numbers between 1 to 10000
    and storing+hashing them*/
    srand (time(NULL));
    for (int k=0;k<100;k++)
    {
        tempRandom=rand()%10000+1;
        randomBackup[k]=tempRandom;
        simpleinsert(tempRandom);
    }
    //following are search cases with time logging
    for(int m=1;m<10;m++)
    {
        switch(m)
        {
        case 1:
            myfile.open ("10per.txt");
            for(loopHelp=0;loopHelp<(100*(10/100));loopHelp++)
            {
                start = clock();
                simplesearch(randomBackup[loopHelp]);
                end = clock();
                myfile<<loopHelp<<"\t"<<(double)(end-start)<<"\n";
            }
            break;
        case 2:
            myfile.open ("20per.txt");
            for(loopHelp=0;loopHelp<(100*(20/100));loopHelp++)
            {
                start = clock();
                simplesearch(randomBackup[loopHelp]);
                end = clock();
                myfile<<loopHelp<<"\t"<<(double)(end-start)<<"\n";
            }
            break;
        case 3:
            myfile.open ("30per.txt");
            for(loopHelp=0;loopHelp<(100*(30/100));loopHelp++)
            {   
                start = clock();
                simplesearch(randomBackup[loopHelp]);
                end = clock();
                myfile<<loopHelp<<"\t"<<(double)(end-start)<<"\n";
            }
            break;
        case 4:
            myfile.open ("40per.txt");
            for(loopHelp=0;loopHelp<(100*(40/100));loopHelp++)
            {
                start = clock();
                simplesearch(randomBackup[loopHelp]);
                end = clock();
                myfile<<loopHelp<<"\t"<<(double)(end-start)<<"\n";
            }
            break;
        case 5:
            myfile.open ("50per.txt");
            for(loopHelp=0;loopHelp<(100*(50/100));loopHelp++)
            {
                start = clock();
                simplesearch(randomBackup[loopHelp]);
                end = clock();
                myfile<<loopHelp<<"\t"<<(double)(end-start)<<"\n";
            }
            break;
        case 6:
            myfile.open ("60per.txt");
            for(loopHelp=0;loopHelp<(100*(60/100));loopHelp++)
            {
                start = clock();
                simplesearch(randomBackup[loopHelp]);
                end = clock();
                myfile<<loopHelp<<"\t"<<(double)(end-start)<<"\n";
            }
            break;
        }
    }
    return 0;
}

Upvotes: 0

Views: 159

Answers (1)

Sorin Totuarez
Sorin Totuarez

Reputation: 114

storagelist *startArray[1000];
[...]
int main()
{
[...]
    for(inti=0;i<1000;i++)
    {
        startArray[i]->next=NULL;

The runtime error results from the uninitialized startArray[i], which contains only NULL-Pointers. I guess the NULL-Pointer has no member 'next' you can access at runtime, which results in a Segmentation fault.

So what you miss is creating the actual items and store them in your startArray:

    for(inti=0;i<1000;i++)
    {
        storagelist *item = new storagelist;
        item->value = 0;
        item->next = NULL;
        //startArray[i]->next=NULL;

Upvotes: 1

Related Questions