Member Avatar for Daria Shmaria

I'm writing a spellchecking program using a hash table. The hash table (a char * array) serves as the dictionary, storing words inputted from a file. However, a segmentation fault occurs before I can get through reading, hashing, and inserting all 60,389 words (the words are in alphabetical order, and the fault occurs after "reloads"). Any suggestions on how to figure out where the segmentation fault is coming from would be greatly appreciated.

The attached files:

1. spellcheck.cpp contains the main function, calling the Dictionary class member function "add" on every word in the file wordlist.txt.
2. hashTable.cpp contains definitions for functions in the Dictionary class. The "add" and "getIndex" functions are the only ones that are functional right now.
3. hashTable.h contains declarations.
4. wordlist.txt contains all the words that need to go in the dictionary.
5. input.txt is the input to the program, but isn't actually being used for anything yet.

#include "hashTable.h"
#include "string.h"
#include <iostream>

using namespace std;

Dictionary::Dictionary()
{
  char*  htl[139079];
  int status[139079];
  for (int i = 0; i < 139079; i++){
    status[i] = 0;
  }

}

Dictionary::~Dictionary()
{
  // deallocate memory of ht and status arrays
  // delete[] ht;
  // delete[] status;
}

// assignemnt operator overloading 
/*
Dictionary& Dictionary::operator=(Dictionary& obj)
{

}
*/

unsigned int Dictionary::add(char* item)
{

  int r = 139067; 
  int m = 139079;

  int length;
  length = strlen(item); // determine length of item
  unsigned int myIndex; 
  myIndex = Dictionary::getIndex(item, length); 
  //cout << "myIndex = " << myIndex << endl;
  // check if the hash table at that index is available
  if((status[myIndex] == 0) || (status[myIndex] == 1)) // if the location is empty or deleted
    {  
      ht[myIndex] = item;
      cout << "word inserted. ht[" << myIndex << "] = " << ht[myIndex] << endl;
      status[myIndex] = 2;
    }
  else // if the location is already taken
    {
      int i = 1; // index of how many times you've attempted hashing the table
      // double hashing until the hash table location is empty
      //cout << "ht[myIndex] = " << ht[myIndex] << endl << "item = " << item << endl;
      while(status[myIndex] == 2)
	{
	  if(strcmp(ht[myIndex], item) == 0) // if the word has already been added, exit
	    {
	      //cout << "The item has already been inserted." << endl;
	      return 1;
	    }
	  else 
	    {
	      // rehash
	      //cout << "status = " << status[myIndex] << endl;
	      int originalIndex = myIndex;
	      myIndex = (originalIndex + (i * (r - (originalIndex % r))) ) % m;
	      i++;
	      //cout << "i incremented. i = " << i << endl;
	    }
	}
      ht[myIndex] = item;
      cout << "word inserted. ht[" << myIndex << "] = " << ht[myIndex] << endl;
      status[myIndex] = 2;      
    }
 
  //cout << "last line of add function." << endl;

 return 0;
}

int Dictionary::returnStatus(int index)
{
  cout << "Status[" << index << "] = " <<  status[index] << endl;
  return 0;
}

bool Dictionary::lookup(char* item) 
{
  // hash item
  int length;
  length = strlen(item); 
  unsigned int myIndex; 
  myIndex = Dictionary::getIndex(item, length); 
  cout << "Initial myIndex = " << myIndex << endl;
  
  if(status[myIndex] == 0) // if the hash table is empty at that location
    {
      cout << "Item " << item << " does not exist." << endl;
      return false; // item does not exist
    }
  else if(status[myIndex] == 1) // if the entry at the location was deleted
    {
      //  keep looping until you find the item or you've reached the original index
      cout << "Item at location was deleted, keep looping." << endl;
      int originalIndex = myIndex;
      int i = 1; // index of immediately following hash
      myIndex = Dictionary::getIndex(item, length);
      while(myIndex != originalIndex)
	{
	  // stuff goes here
	}
      
      
      /*
      

      while(myIndex != originalIndex)
	{
	  getIndex(item, length);
	  // stuff about i++
	}
      */
    }
  else if(status[myIndex] == 2)
    {
      cout << "Location taken at myIndex = " << myIndex << endl;
      cout << "ht[myIndex] = " << ht[myIndex] << endl << "item = " << item << endl;
      if(strcmp(ht[myIndex], item) == 0)
	{
	  cout << "The item " << item << " exists. yay!" << endl;
	}
      else 
	{
	  cout << "Other item at location, have to keep looping."<< endl;
	  // keep looping until you find it or you've reached the original index
	}
    }

  cout << "End of lookup function." << endl;
  return true;
}

int Dictionary::remove(char* item)
{
  cout << "Remove function called." << endl;
  return 0;
}

unsigned int Dictionary::getIndex(char * p, int len) // hash the item using a cyclic shift hash code
{
  unsigned int h = 0;
  for(int i = 0; i < len; i++)
    {
      h = (h<<5)|(h>>27);
      h += (unsigned int)p[i]; 
    }
  
  //cout << "getIndex function called." << endl;
  //cout << "h = " << h << endl;
  h = (h % 69539); // make sure the index is possible given the size of the hash table
  //cout << "h after modding = " << h << endl;
  return h; 
}
#ifndef _HASHTABLE_H
#define _HASHTABLE_H

class Dictionary
{
 public:
  Dictionary(); // constructor
  ~Dictionary(); // destructor
  // Dictionary& operator=(Dictionary& obj); // assignment operator overloading
  unsigned int add(char* item); // add an item
  int remove(char * item); // remove an item
  bool lookup(char * item); // find an item
  unsigned int getIndex(char * p, int len); // hash an item
  int returnStatus(int index);

 private:
  char* ht[139079];
  int status[139079];
  int m; // size of hash table for add formula
  int r; // prime number less than m in double hash function
};

#endif
In computer science, a data stucture is a wayof storing datta in a computur so that it can be used efficeintly.  Often a careffully chosen data structure willallow the moste efficient algorthm to be used.
#include "iostream"
#include "fstream"
#include "string.h"

#include "hashTable.h"

using namespace std;

int main(int argc, char** argv)
{
  if(argc != 2)
    {
      cerr << "Incorrect number of inputs." << endl;
      return -1;
    }

  // Read the input file

  ifstream myInput(argv[1]);
  
  if(myInput)
    {
      cout << "The input file was opened. Yay!" << endl;
      char firstInputLetter;
      myInput >> firstInputLetter;
      cout << "The first letter of the input file: " << firstInputLetter << "." << endl;
    }
  else if(!myInput)
    {
      cerr << "The input file could not be opened. Try again!" << endl;
      exit(1);
    }

  // Read the wordlist file

  ifstream wordlist("./wordlist.txt");


  Dictionary* htl;
  htl =new Dictionary();
  if(wordlist)
    {
      cout << "The wordlist file was opened." << endl;
      string line;
      cout << "made a string called line" << endl;
      wordlist.ignore(7, '\n');  // ignore the first entry (the number of words in the wordlist)
      cout << "ignored the first 7 chars" << endl;
      while(getline(wordlist, line, '\n'))
	{
	  //cout << "in the while loop" << endl;
	  char * convline = new char[line.size() + 1];
	  //cout << "made char * convline" << endl;
	  strcpy(convline, line.c_str());
	  //cout << "strcpy'd" << endl;
	  htl->add(convline);
	  //cout << "added " << convline << endl;

	  // delete convline; // caused segmentation fault
	}
    }
  else if(!wordlist)
    {
      cerr << "The wordlist could not be read." << endl;
      exit(2);
    }

  /*

  cout << "Checking if the item pikachu exists" << endl;
  htl.lookup("pikachu");

  cout << "Checking if the item beedril exists" << endl;
  htl.lookup("beedril");
  // call destructor 

  */
  delete htl;
  return 0;
}

// at the end, go through entire hash table and delete memory pointed to by hash table
// OR allocate the memory in the hash table
60389
a
aah
aardvark
aardvarks
abacus
abacuses
abalone
abalones
abandon
abandoned
abandoning
abandonment
abandons
abase
abased
abasement
abases
abashed
abasing
abate
abated
abatement
abates
abating
abattoir
abattoirs
abbess
abbesses
abbey
abbeys
abbot
abbots
abbreviate
abbreviated
abbreviates
abbreviating
abbreviation
abbreviations
abdicate
abdicated
abdicates
abdicating
abdication
abdications
abdomen
abdomens
abdominal
abduct
abducted
abducting
abduction
abductions
abductor
abductors
abducts
abed
aberrant
aberration
aberrations
abet
abets
abetted
abetting
abhor
abhorred
abhorrence
abhorrent
abhorring
abhors
abide
abided
abides
abiding
abilities
ability
abject
abjectly
abjure
abjured
abjures
abjuring
ablaze
able
abler
ablest
ablutions
ably
abnegation
abnormal
abnormalities
abnormality
abnormally
aboard
abode
abodes
abolish
abolished
abolishes
abolishing
abolition
abolitionist
abolitionists
abominable
abominably
abominate
abominated
abominates
abominating
abomination
abominations
aboriginal
aboriginals
aborigine
aborigines
abort
aborted
aborting
abortion
abortionist
abortionists
abortions
abortive
aborts
abound
abounded
abounding
abounds
about
above
aboveboard
abracadabra
abrade
abraded
abrades
abrading
abrasion
abrasions
abrasive
abrasively
abrasiveness
abrasives
abreast
abridge
abridged
abridgement
abridgements
abridges
abridging
abridgment
abridgments
abroad
abrogate
abrogated
abrogates
abrogating
abrogation
abrupt
abruptly
abruptness
abscess
abscesses
abscond
absconded
absconding
absconds
abseil
abseiled
abseiling
abseils
absence
absences
absent
absented
absentee
absenteeism
absentees
absenting
absently
absents
absinth
absinthe
absolute
absolutely
absolutes
absolution
absolutism
absolutist
absolutists
absolve
absolved
absolves
absolving
absorb
absorbed
absorbency
absorbent
absorbing
absorbs
absorption
abstain
abstained
abstainer
abstainers
abstaining
abstains
abstemious
abstention
abstentions
abstinence
abstinent
abstract
abstracted
abstractedly
abstracting
abstraction
abstractions
abstracts
abstruse
absurd
absurdities
absurdity
absurdly
abundance
abundant
abundantly
abuse
abused
abuser
abusers
abuses
abusing
abusive
abusively
abut
abuts
abutted
abutting
abuzz
abysmal
abysmally
abyss
abysses
acacia
acacias
academe
academia
academic
academically
academician
academicians
academics
academies
academy
accede
acceded
accedes
acceding
accelerate
accelerated
accelerates
accelerating
acceleration
accelerator
accelerators
accent
accented
accenting
accents
accentuate
accentuated
accentuates
accentuating
accentuation
accept
acceptability
acceptable
acceptably
acceptance
acceptances
accepted
accepting
accepts
access
accessed
accesses
accessibility
accessible
accessing
accession
accessions
accessories
accessorise
accessorised
accessorises
accessorising
accessorize
accessorized
accessorizes
accessorizing
accessory
accident
accidental
accidentally
accidents
acclaim
acclaimed
acclaiming
acclaims
acclamation
acclimate
acclimated
acclimates
acclimating
acclimatisation
acclimatise
acclimatised
acclimatises
acclimatising
acclimatization
acclimatize
acclimatized
acclimatizes
acclimatizing
accolade
accolades
accommodate
accommodated
accommodates
accommodating
accommodation
accommodations
accompanied
accompanies
accompaniment
accompaniments
accompanist
accompanists
accompany
accompanying
accomplice
accomplices
accomplish
accomplished
accomplishes
accomplishing
accomplishment
accomplishments
accord
accorded
according
accordingly
accordion
accordions
accords
accost
accosted
accosting
accosts
account
accountability
accountable
accountancy
accountant
accountants
accounted
accounting
accounts
accouterments
accoutrements
accredit
accreditation
accredited
accrediting
accredits
accretion
accretions
accrual
accruals
accrue
accrued
accrues
accruing
accumulate
accumulated
accumulates
accumulating
accumulation
accumulations
accumulative
accumulator
accumulators
accuracy
accurate
accurately
accursed
accusation
accusations
accusative
accusatives
accusatory
accuse
accused
accuser
accusers
accuses
accusing
accusingly
accustom
accustomed
accustoming
accustoms
ace
acerbic
acerbity
aces
acetaminophen
acetate
acetone
acetylene
ache
ached
aches
achievable
achieve
achieved
achievement
achievements
achiever
achievers
achieves
achieving
aching
achingly
achy
acid
acidic
acidified
acidifies
acidify
acidifying
acidity
acidly
acids
acknowledge
acknowledged
acknowledgement
acknowledgements
acknowledges
acknowledging
acknowledgment
acknowledgments
acme
acne
acolyte
acolytes
acorn
acorns
acoustic
acoustically
acoustics
acquaint
acquaintance
acquaintances
acquaintanceship
acquainted
acquainting
acquaints
acquiesce
acquiesced
acquiescence
acquiescent
acquiesces
acquiescing
acquire
acquired
acquirer
acquirers
acquires
acquiring
acquisition
acquisitions
acquisitive
acquisitiveness
acquit
acquits
acquittal
acquittals
acquitted
acquitting
acre
acreage
acreages
acres
acrid
acrimonious
acrimoniously
acrimony
acrobat
acrobatic
acrobatics
acrobats
acronym
acronyms
across
acrostic
acrostics
acrylic
acrylics
act
acted
acting
action
actionable
actions
activate
activated
activates
activating
activation
active
actively
activism
activist
activists
activities
activity
actor
actors
actress
actresses
acts
actual
actualities
actuality
actualize
actualized
actualizes
actualizing
actually
actuarial
actuaries
actuary
actuate
actuated
actuates
actuating
acuity
acumen
acupressure
acupuncture
acupuncturist
acupuncturists
acute
acutely
acuteness
ad
adage
adages
adagio
adagios
adamant
adamantly
adapt
adaptability
adaptable
adaptation
adaptations
adapted
adapter
adapters
adapting
adaption
adaptions
adaptive
adaptor
adaptors
adapts
add
added
addenda
addendum
adder
adders
addict
addicted
addiction
addictions
addictive
addicts
adding
addition
additional
additionally
additions
additive
additives
addle
addled
addles
addling
address
addressed
addressee
addressees
addresses
addressing
adds
adduce
adduced
adduces
adducing
adenoidal
adenoids
adept
adeptly
adepts
adequacy
adequate
adequately
adhere
adhered
adherence
adherent
adherents
adheres
adhering
adhesion
adhesive
adhesives
adieu
adieus
adieux
adios
adipose
adjacent
adjectival
adjectivally
adjective
adjectives
adjoin
adjoined
adjoining
adjoins
adjourn
adjourned
adjourning
adjournment
adjournments
adjourns
adjudge
adjudged
adjudges
adjudging
adjudicate
adjudicated
adjudicates
adjudicating
adjudication
adjudications
adjudicator
adjudicators
adjunct
adjuncts
adjure
adjured
adjures
adjuring
adjust
adjustable
adjusted
adjuster
adjusters
adjusting
adjustment
adjustments
adjusts
adjutant
adjutants
adman
admen
admin
administer
administered
administering
administers
administration
administrations
administrative
administratively
administrator
administrators
admirable
admirably
admiral
admirals
admiration
admire
admired
admirer
admirers
admires
admiring
admiringly
admissibility
admissible
admission
admissions
admit
admits
admittance
admitted
admittedly
admitting
admixture
admixtures
admonish
admonished
admonishes
admonishing
admonishment
admonishments
admonition
admonitions
admonitory
adobe
adolescence
adolescent
adolescents
adopt
adopted
adopting
adoption
adoptions
adoptive
adopts
adorable
adoration
adore
adored
adores
adoring
adoringly
adorn
adorned
adorning
adornment
adornments
adorns
adrenal
adrenalin
adrenaline
adrift
adroit
adroitly
adroitness
ads
adulation
adulatory
adult
adulterate
adulterated
adulterates
adulterating
adulteration
adulterer
adulterers
adulteress
adulteresses
adulterous
adultery
adulthood
adults
adumbrate
adumbrated
adumbrates
adumbrating
adumbration
advance
advanced
advancement
advancements
advances
advancing
advantage
advantaged
advantageous
advantageously
advantages
advent
adventitious
adventitiously
adventure
adventurer
adventurers
adventures
adventuresome
adventurism
adventurist
adventurists
adventurous
adventurously
adverb
adverbial
adverbs
adversarial
adversaries
adversary
adverse
adversely
adversities
adversity
advert
advertise
advertised
advertisement
advertisements
advertiser
advertisers
advertises
advertising
advertorial
advertorials
adverts
advice
advisability
advisable
advise
advised
advisedly
adviser
advisers
advises
advising
advisor
advisories
advisors
advisory
advocacy
advocate
advocated
advocates
advocating
adz
adze
adzes
aeon
aeons
aerate
aerated
aerates
aerating
aeration
aerial
aerials
aerie
aeries
aerobatic
aerobatics
aerobic
aerobics
aerodrome
aerodromes
aerodynamic
aerodynamically
aerodynamics
aerogram
aerogramme
aerogrammes
aerograms
aeronautic
aeronautical
aeronautics
aeroplane
aeroplanes
aerosol
aerosols
aerospace
aesthete
aesthetes
aesthetic
aesthetically
aesthetics
aetiology
afar
affability
affable
affably
affair
affairs
affect
affectation
affectations
affected
affectedly
affecting
affection
affectionate
affectionately
affections
affects
affidavit
affidavits
affiliate
affiliated
affiliates
affiliating
affiliation
affiliations
affinities
affinity
affirm
affirmation
affirmations
affirmative
affirmatively
affirmatives
affirmed
affirming
affirms
affix
affixed
affixes
affixing
afflict
afflicted
afflicting
affliction
afflictions
afflicts
affluence
affluent
afford
affordability
affordable
afforded
affording
affords
afforest
afforestation
afforested
afforesting
afforests
affray
affrays
affront
affronted
affronting
aff
  • 1 Contributor
  • 1 Reply
  • 160 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Daria Shmaria
Member Avatar for Daria Shmaria

Er, never mind. I'm not entirely sure what I did that fixed it, but I'm able to read in the whole file now. Sorry for the inconvenience.

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.