Создание массива n со связанным списком целых
Я недавно сделал 26array и попытался смоделировать словарь.
Я не могу понять, как это сделать. Я пытался работать с передачей связанного списка целых вместо строки. Мой текущий код создает 26 узлов (a-z), а затем каждый из этих узлов имеет 26 узлов (a-z). Я хотел бы реализовать способ сделать это с целыми числами, скажем (1-26). Эти int-узлы будут представлять элементы, а связанный список целых, которые я хочу передать, будет содержать набор целых чисел, которые я хочу представить в дереве, похожем на строку.
Пример: передать набор {1, 6, 8} вместо строки, такой как «привет»
#include <iostream>
using namespace std;
class N26
{
private:
struct N26Node
{
bool isEnd;
struct N26Node *children[26];
}*head;
public:
N26();
~N26();
void insert(string word);
bool isExists(string word);
void printPath(char searchKey);
};
N26::N26()
{
head = new N26Node();
head->isEnd = false;
}
N26::~N26()
{
}
void N26::insert(string word)
{
N26Node *current = head;
for(int i = 0; i < word.length(); i++)
{
int letter = (int)word[i] - (int)'a';
if(current->children[letter] == NULL)
{
current->children[letter] = new N26Node();
}
current = current->children[letter];
}
current->isEnd = true;
}
/* Pre: A search key
* Post: True is the search key is found in the tree, otherwise false
* Purpose: To determine if a give data exists in the tree or not
******************************************************************************/
bool N26::isExists(string word)
{
N26Node *current = head;
for(int i=0; i<word.length(); i++)
{
if(current->children[((int)word[i]-(int)'a')] == NULL)
{
return false;
}
current = current->children[((int)word[i]-(int)'a')];
}
return current->isEnd;
}
Решение
class N26
{
private:
N26Node newNode(void);
N26Node *mRootNode;
...
};
N26Node *newNode(void)
{
N26Node *mRootNode = new N26Node;
mRootNode = NULL;
mRootNode->mData = NULL;
for ( int i = 0; i < 26; i++ )
mRootNode->mAlphabet[i] = NULL;
return mRootNode;
}
Ах! Мои глаза!
Серьезно, вы пытаетесь сделать что-то слишком сложное. Ваш код полон ошибок и не может работать как задумано. Повозиться не поможет, нужно вернуться к основам указателей и связанных списков. Изучите основы и не пытайтесь делать что-либо похожее на связанный список связанных списков пока не поймешь, что не так с кодом выше.
Я дам вам несколько советов: «утечка памяти», «висячий указатель», «несоответствие типов», «неопределенное поведение».
Другие решения
Я не совсем использовал связанные списки, но мне удалось заставить его работать, используя массивы.
/* *** Author: Jamie Roland
* Class: CSI 281
* Institute: Champlain College
* Last Update: October 31, 2012
*
* Description:
* This class is to implement an n26 trie. The
* operations
* available for this impementation are:
*
* 1. insert
* 2. isEmpty
* 3. isExists
* 4. remove
* 5. showInOrder
* 6. showPreOrder
* 7. showPostOrder
*
* Certification of Authenticity:
* I certify that this assignment is entirely my own work.
**********************************************************************/
#include <iostream>
using namespace std;
class N26
{
private:
struct N26Node
{
bool isEnd;
struct N26Node *children[26];
}*head;
public:
N26();
~N26();
void insert(int word[]);
bool isExists(int word[]);
void printPath(char searchKey);
};
N26::N26()
{
head = new N26Node();
head->isEnd = false;
}
N26::~N26()
{
}
void N26::insert(int word[])
{
int size = sizeof word/sizeof(int);
N26Node *current = head;
for(int i = 0; i < size; i++)
{
int letter = word[i] - 1;
if(current->children[letter] == NULL)
{
current->children[letter] = new N26Node();
}
current = current->children[letter];
}
current->isEnd = true;
}
/* Pre: A search key
* Post: True is the search key is found in the tree, otherwise false
* Purpose: To determine if a give data exists in the tree or not
******************************************************************************/
bool N26::isExists(int word[])
{
int size = sizeof word/sizeof(int);
N26Node *current = head;
for(int i=0; i<size; i++)
{
if(current->children[(word[i]-1)] == NULL)
{
return false;
}
current = current->children[(word[i]-1)];
}
return current->isEnd;
}