Сбой реализации связанного списка в C ++ - PullRequest
Новая
       0

Сбой реализации связанного списка в C ++

2 голосов
/ 10 октября 2011

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

Ниже приведен код ошибки, который я пытался реализовать, следуя инструкциямпсевдокод во введении MIT к тексту алгоритмов: 

//
// Method searches and retrieves a specified node from the list
//
Node* List::getNode(unsigned position)
{
    Node* current = m_listHead;

    for(unsigned i = m_listSize-1; (current != 0) && (i != position); --i)
            current = current->next;

    return current;
}

Голова в этой точке программы - это 4-й узел, который содержит значение int 5. Проблема, по-видимому, в телецикл for, где указатель на объект узла назначается следующему узлу.Но это выходит за пределы заголовка узла, поэтому он по существу указывает на какое-то случайное место в памяти (это имеет смысл).

Не должен ли алгоритм в этом случае переходить на предыдущий узел вместо следующего узла?Ниже приведен псевдокод: 

LIST-SEARCH(L, k)
    x <- head
    while x != NIL and key != k
        do x <- next[x]
    return x

Кроме того, здесь находится файл заголовка для моей реализации связанного списка.Я еще не пытался реализовать его в форме шаблона, просто чтобы все было просто: 

#ifndef linkList_H
#define linkList_h


//
// Create an object to represent a Node in the linked list object
// (For now, the objects to be put in the list will be integers)
//
struct Node
{
    // nodes of list will be integers
    int number;
    // pointer to the next node in the linked list
    Node* next;
};


//
// Create an object to keep track of all parts in the list
//
class List
{
public:

    // Contstructor intializes all member data
    List() : m_listSize(0), m_listHead(0) {}

    // methods to return size of list and list head
    Node* getListHead() const { return m_listHead; }
    unsigned getListSize() const { return m_listSize; }

    // method for adding a new node to the linked list, 
    // retrieving and deleting a specified node in the list
    void addNode(Node* newNode);
    Node* getNode(unsigned position);

private:

    // member data consists of an unsigned integer representing
    // the list size and a pointer to a Node object representing head
    Node* m_listHead;
    unsigned m_listSize;
};

#endif

Реализация метода addNode: 

//
// Method adds a new node to the linked list
//
void List::addNode(Node* newNode)
{
    Node* theNode = new Node;

    theNode = newNode;
    theNode->next;
    m_listHead = theNode;

    ++m_listSize;
}

Ответы [ 3 ]

1 голос
/ 10 октября 2011

Попробуйте построить список: 

void List::addNode(int number) 
{ 
    newNode = new Node;
    newNode -> number = number;
    newNode -> next = m_listHead ;
    m_listHead = newNode;
    ++m_listSize; 
}

Это добавит узлы к голове.Возможно, вы захотите сохранить указатель на хвост и вставить туда узлы.

0 голосов
/ 10 октября 2011

Ваш список сильно отличается от того, как выглядит обычный список ADT. Вместо того, чтобы возвращать узлы, которые потребовали бы, чтобы клиент знал о реализации списка, вы возвращаете и принимаете тип, из которого вы делаете список.

В этом случае вы составляете список целых чисел, так что вы бы хотели 

public:
    void add(int num); //prepends an Item to the list
    int get(int pos);

Реализации обоих просты. Add создает новый узел и связывает его с; 

void List::add(int num)
{
    Node *newNode = new Node;
    newNode->number  = num;
    newNode->next = m_listHead;
    m_listHead = newNode;
    m_listSize++;
}

Тогда получить тоже легко: 

int List::get(int pos)
{
    if(pos>m_listSize)
        ;//throw an error somehow
    Node *tmp = m_listHead;
    while(pos-->0)
        tmp=tmp->next; 
    return m->number
}
0 голосов
/ 10 октября 2011

К сожалению, ваш код не похож на указанный вами псевдокод.

Псевдокод предназначен для поиска в связанном списке ключа, а не позиции.

Псевдокод читается как: 

Assign head to (node) x.
while x isn't null and the key inside the current node (x) doesn't match k
  assign x->next to x
return x

Возвращаемое значение является либо указателем на узел, который содержит k, либо нулевым

Если вы пытаетесь найтиузел в данной позиции ваш цикл будет (обратите внимание, это предполагает, что вы собираетесь использовать нулевой индекс для доступа к списку): 

Assign head to (node) x
assign 0 to (int) pos
while x isn't null and pos not equal to given position
    assign x->next to x
    increment pos
return x

Результат будет либобыть указателем на узел в данной позиции или нулевым (если вы дойдете до конца списка первым)

Редактировать: Ваш код очень близок к последнему, если это то, что вы 'пытаешься сделать ... ты видишь разницу?

Редактировать, потому что мне нравится домашняя работа, где ОП задает правильные вопросы:) 

Node* List::getNodeContaining(int searchValue)
{
    Node* current = m_listHead;

    while (current != 0 && current->number != searchValue)
    {
        current = current->next;
    }
    return current;
}

Node* List::getNodeAtPos(int position)
{
     Node* current = m_listHead;
     int pos = 0;

     while (current != 0 && pos != position)
     {
        current = current->next;
        pos++;
     }

     return current;
}
...