Ha sh таблица с указателем вектора - PullRequest
0 голосов
/ 27 апреля 2020

У меня возникли проблемы с заданием, которое требует создания таблицы ha sh с использованием вектора Entry (ADT, созданного профессором). Программа успешно компилируется, но GDB выдает мне сообщение об ошибке «Нет стека». когда я пытаюсь отладить. Я проследил ошибку до вызова моей функции search() в моей функции insert().

Я не уверен, откуда возникла проблема, но я думаю, что это либо связано с тем, как я получаю доступ к вектор или как я пытался инициализировать его в конструкторе.

Мой исходный код ниже, мой профессор написал структуру Entry и класс HT, а также функции main() и hashing(), которые нельзя редактировать, хотя новые функции могут быть добавлены в класс. Несмотря на то, что эти части не могут быть отредактированы, я включил их сюда для справки.

Вот мой заголовочный файл assignment8.h:

#ifndef ASSIGNMENT8_H
#define ASSIGNMENT8_H
#include <vector>
#include <string>

struct Entry {
    std::string key;
    std::string description;
    Entry() { key = "---"; }
};

class HT {
    private:
        std::vector<Entry>* hTable;
        int table_size=11;
        int item_count;
        int hashing(const std::string&);
    public:
        HT();
        HT(int size);
        ~HT();
        bool insert(const Entry& e);
        int search(const std::string& key);
        bool remove(const std::string& s);
        void print();
        //Student-made member fucntions
        void setsize(int size){table_size = size;}
        void setItemCount(int ic){ic = item_count;}
        int getItemCount(){return item_count;}
};

#endif

и мое cc назначение файла8. cc:

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include "assignment8.h"

using namespace std;

Entry* get_entry(const string& line)
{
  //Holder for string fragments
  string strArr[3];
  int index = 0;
  //Split the string
  for(unsigned int i = 0; i < line.length(); i++)
  {
    if(line[i] != ':')
      strArr[index] += line[i];
    else
      index++;
  }

  Entry* newEntry = new Entry;
  //Pass strings to newEntry
  (*newEntry).key = strArr[1];
  (*newEntry).description = strArr[2];

  return newEntry;
}

string get_key(const string& line)
{
  //Holder for string fragments
  string strArr[2];
  int index = 0;

  //Split string
  for(unsigned int i = 0; i < line.length(); i++)
  {
    if(line[i] != ':')
      strArr[index] += line[i];
    else
      index++;
  }

  //Return item-key
  return strArr[1];
}

//----HT----//
// key is in form of letter-letter-digit
// compute sum <-- ascii(pos1)+ascii(pos2)+ascii(pos3)
// compute sum%htable_size
int HT::hashing(const string& key) {
   return ((int)key[0] + (int)key[1] + (int)key[2])%table_size;
}

//--Constructors
//Default Constructor
HT::HT(){}
//Constructor
HT::HT(int size)
{
  //Initializations
  if(!size)
    size = 11;
  setsize(size);
  hTable = new vector<Entry>[table_size];
}

HT::~HT()
{
  delete[] hTable;
}

int HT::search(const std::string& key)
{
  //Look for unused slot
  for(int i = 0; i < table_size; i++)
  {
    if((*hTable)[i].key == key)
      return hashing(key);
  }
  return -1;
}

bool HT::insert(const Entry& e)
{
  //Get e's key
  string eKey = e.key;
  //If it's full, print error message and return false
  if(getItemCount() == table_size)
  {
    cout << "Hash table is full\n";
    return false;
  }
  //Checks to see if key already exists
  if(search(eKey) != -1)
  {
    cout << "Key already exists in table\n";
    return false;
  }
  //If it does not already exist,
  for(int i = 0; i < table_size; i++)
  {
    string iKey = (*hTable)[i].key;
    cout << i << "iteration(s)"<< endl;
    if(iKey == "---" || iKey == "+++")
    {
      //Compute hash key value and insert into position
      (*hTable)[i] = e;
      setItemCount(++item_count);
      return true;
    }
  }
  return false;
}

bool HT::remove(const std::string& s)
{
  for(int i = 0; i < table_size; i++)
  {
    string iKey = (*hTable)[i].key;
    if(iKey == s)
    {
      iKey = "+++";
      setItemCount(--item_count);
      return true;
    }
  }

  return false;
}

void HT::print()
{
  cout << "----Hash Table----" << endl;
  for(int i = 0; i < table_size; i++)
  {
      cout << (*hTable)[i].key << " " << (*hTable)[i].description << endl;
  }
  cout << endl << "------------------" << endl;
}

int main(int argc, char** argv ) {
    if ( argc < 2 ) {
        cerr << "argument: file-name\n";
        return 1;
    }

    HT ht;
    ifstream infile(argv[1], ios::in);
    string line;
    infile >> line;
    while ( !infile.eof() ) {
        if ( line[0] == 'A' ) {
            Entry* e = get_entry( line );
            ht.insert( *e );
            delete e;
        }
        else {
            string key = get_key(line);
            if ( line[0] == 'D' ) {
                cout << "Removing " << key << "...\n";
                bool removed = ht.remove( key );
                if ( removed )
                    cout << key << " is removed successfully...\n\n";
                else
                    cout << key << " does not exist, no key is removed...\n\n";
            }
            else if ( line[0] == 'S' ) {
                int found = ht.search( key );
                if ( found < 0 )
                    cout << key << " does not exist in the hash table ..." << endl << endl;
                else
                   cout << key << " is found at table position " << found << endl << endl;
            }
            else if ( line[0] == 'P' ) {
                cout << "\nDisplaying the table: " << endl;
                ht.print();
            }
            else
                cerr << "wrong input: " << line << endl;
        }
        infile >> line;
    }

    infile.close();
    return 0;
}

Спасибо за любую помощь или совет! :)

...