Назначение связанного списка в C ++: проблемы со вставкой и удалением - PullRequest
Новая
       0

Назначение связанного списка в C ++: проблемы со вставкой и удалением

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

Я работаю над реализацией связанного списка в C ++. Я делаю успехи, но у меня возникают проблемы с правильной работой функций вставки и удаления. Ниже приведен список объектов в заголовочном файле C ++: 

#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
{
    Node() : sentinel(0) {}

    int number;
    Node* next;
    Node* prev;
    Node* sentinel;
};


//
// 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 and inserting a new node to the linked list, 
    // retrieving and deleting a specified node in the list
    //
    void  addNode(int num);
    void  insertNode(Node* current);
    void  deleteNode(Node* current);

    Node* retrieveNode(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

А вот файл реализации (.cpp): 

#include "linkList.h"
#include <iostream>

using namespace std;


//
// Adds a new node to the linked list
//
void List::addNode(int num)
{
    Node *newNode = new Node;
    newNode->number = num;
    newNode->next = m_listHead;
    m_listHead = newNode;
    ++m_listSize;
}


//
// NOTWORKING: Inserts a node which has already been set to front
// of the list
//
void List::insertNode(Node* current)
{
        // check to see if current node already at
        // head of list
    if(current == m_listHead)
        return;

    current->next = m_listHead;

    if(m_listHead != 0)
        m_listHead->prev = current;

    m_listHead = current;
    current->prev = 0;
}


//
// NOTWORKING: Deletes a node from a specified position in linked list
//
void List::deleteNode(Node* current)
{
    current->prev->next = current->next;
    current->next->prev = current->prev;
}


//
// Retrieves a specified node from the list
//
Node* List::retrieveNode(unsigned position)
{
    if(position > (m_listSize-1) || position < 0)
    {
        cout << "Can't access node; out of list bounds";
        cout << endl;
        cout << endl;

        exit(EXIT_FAILURE);
    }

    Node* current = m_listHead;
    unsigned pos = 0;

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

    return current;
 }

После запуска краткой тестовой программы в клиентском коде C ++, вот результат: 

Number of nodes: 10

Elements in each node:
9 8 7 6 5 4 3 2 1 0

Insertion of node 5 at the list head:
4 9 8 7 6 5 4 9 8 7

Deletion of node 5 from the linked list

Как видите, вставка не просто перемещает узел 5 в начало списка, но перезаписывает другие узлы, начиная с третьей позиции. Псевдокод, который я пытался реализовать, взят из книги алгоритмов MIT: 

LIST-INSERT(L, x)
    next[x] <- head[L]
    if head[L] != NIL
        then prev[head[L]] <- x
    head[L] <- x
    prev[x] <- NIL

Также реализация удаления просто падает при вызове метода. Не уверен почему; но вот соответствующий псевдокод: 

LIST-DELET'
    next[prev[x]] <- next[x]
    prev[next[x]] <- prev[x]

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

(*current).prev 0xcdcdcdcd {number=??? next=??? prev=??? ...}   Node *
    number          CXX0030: Error: expression cannot be evaluated  
    next            CXX0030: Error: expression cannot be evaluated  
    prev            CXX0030: Error: expression cannot be evaluated  
    sentinel    CXX0030: Error: expression cannot be evaluated

Любая помощь будет принята с благодарностью !!

Ответы [ 3 ]

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

В deleteNode вы не обрабатываете случаи, когда current-> next и / или current-> prev равен нулю. Кроме того, вы не обновляете заголовок списка, если текущим является заголовок.

Вы должны сделать что-то вроде этого: 

node* next=current->next;
node* prev=current->prev;

if (next!=null) next->prev=prev;
if (prev!=null) prev->next=next;

if (m_listhead==current) m_list_head=next;

(Внимание: на самом деле я не тестировал приведенный выше код, но думаю, что он достаточно хорошо иллюстрирует мою идею)

Я не уверен, что именно делает ваш метод InsertNode, поэтому я не могу предложить никакой помощи там.

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

OK.

  1. Как указывает @Al Kepp, ваш «узел добавления» содержит ошибки.Посмотрите на код Ала и исправьте его.

  2. Выполняемая вами «вставка» не является обычной вставкой в ​​список.Скорее, это, кажется, операция «переместить на передний план».

  3. Несмотря на это, вам нужно удалить узел из его текущего места в списке, прежде чем добавить его в началосписок.

Обновление

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

См. Приведенный ниже пример простого кода. 

#include <iostream>

// List Node Object
//
struct Node
{
    Node(int n=0);
    int nData;
    Node* pPrev;
    Node* pNext;
};

Node::Node(int n)
: nData(n)
, pPrev(NULL)
, pNext(NULL)
{
}

//
// List object
//
class CList
{
public:

    //
    // Contstructor 
    //
    CList();

    //
    // methods to inspect list
    //
    Node*    Head() const;
    unsigned Size() const;
    Node*    Get(unsigned nPos) const;
    void     Print(std::ostream &os=std::cout) const;

    //
    // methods to modify list
    //
    void Insert(int nData);
    void Insert(Node *pNew);
    void Delete(unsigned nPos);
    void Delete(Node *pDel);

private:
    //
    // Internal data
    //
    Node*    m_pHead;
    unsigned m_nSize;
};
/////////////////////////////////////////////////////////////////////////////////
CList::CList()
: m_pHead(NULL)
, m_nSize(0)
{
}
Node *CList::Head() const 
{ 
    return m_pHead; 
}
unsigned CList::Size() const 
{ 
    return m_nSize; 
}
void CList::Insert(int nData)
{
    Insert(new Node(nData));
}
void CList::Insert(Node *pNew)
{
    pNew->pNext = m_pHead;
    if (m_pHead)
        m_pHead->pPrev = pNew;
    pNew->pPrev = NULL;
    m_pHead     = pNew;
    ++m_nSize;
}
void CList::Delete(unsigned nPos)
{
    Delete(Get(nPos));
}
void CList::Delete(Node *pDel)
{
    if (pDel == m_pHead)
    {
        // delete first
        m_pHead = pDel->pNext;
        if (m_pHead)
            m_pHead->pPrev = NULL;
    }
    else
    {
        // delete subsequent
        pDel->pPrev->pNext = pDel->pNext;
        if (pDel->pNext)
            pDel->pNext->pPrev = pDel->pPrev;
    }
    delete pDel;
    --m_nSize;
}

Node* CList::Get(unsigned nPos) const
{
    unsigned nCount(0);
    for (Node *p=m_pHead; p; p = p->pNext)
        if (nCount++ == nPos)
            return p;
    throw std::out_of_range("No such node");
}

void CList::Print(std::ostream &os) const
{
    const char szArrow[] = " --> ";

    os << szArrow;
    for (Node *p=m_pHead; p; p = p->pNext)
        os << p->nData << szArrow;
    os << "NIL\n";
}

int main()
{
    CList l;

    l.Print();

    for (int i=0; i<10; i++)
        l.Insert((i+1)*10);

    l.Print();

    l.Delete(3);

    l.Delete(7);

    l.Print();

    try
    {
        l.Delete(33);
    }
    catch(std::exception &e)
    {
        std::cerr << "Failed to delete 33: " << e.what() << '\n';
    }

    l.Print();

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

Вы получили ошибку в addNode().Пока вы не исправите это, вы не можете ожидать, что insertNode будет работать.

Кроме того, я думаю, что ваш дизайн довольно глупый.Например, метод с именем «insertNode» должен вставлять новый элемент в произвольную позицию, но ваш метод insertNode делает совсем другое, поэтому вы должны переименовать его.Также addNode должен быть переименован.Кроме того, как писал Световой кодер, почему так много часовых?Я боюсь, что ваш дизайн класса в целом плох.

Фактическая ошибка в том, что вы забыли установить атрибут prev старой головы.Он должен указывать на новую голову. 

void List::addNode(int num)
{
    Node *newNode = new Node;
    newNode->number = num;
    newNode->next = m_listHead;

    if(m_listHead) m_listHead->prev = newNode;

    m_listHead = newNode;
    ++m_listSize;
}

Аналогично, у вас есть другая ошибка в deleteNode().Это не работает при удалении последнего элемента из списка. 

void List::deleteNode(Node* current)
{
    m_listSize--;
    if(current == m_listHead) m_listHead = current->next;
    if(current->prev) current->prev->next = current->next;
    if(current->next) current->next->prev = current->prev;
}

Теперь вы можете исправить так называемый insertNode: 

void List::insertNode(Node* current)
{
    int value = current->number;
    deleteNode(current);
    addNode(value);
}

Обратите внимание, что я написал все здесь без компиляции итестирование в компиляторе C ++.Может быть, есть некоторые ошибки, но все же я надеюсь, что это поможет вам хотя бы немного.

...