Реализация указателей/списков C++

#include <iostream>
using namespace std;

class ListNode
{
    private:
        struct Node
        {
            int value;
            Node *next;
        } *lnFirst;

    public:
        ListNode();
        int Length();
        void DisplayList();
        void Insert( int num );
        bool Contains( int num );
        int GetValue( int num );
};

ListNode::ListNode()
{
    lnFirst = NULL;
}

int ListNode::Length()
{
    Node *lnTemp;
    int intCount = 0;
    for( lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
    {
        intCount++;
    }
    return intCount;
}

void ListNode::DisplayList()
{
    Node *lnTemp;
    for( lnTemp = lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
        cout<<endl<<lnTemp->value;
}

void ListNode::Insert(int num)
{
    Node *lnCurrent, *lnNew;

    if( lnFirst == NULL )
    {
        lnFirst = new Node;
        lnFirst->value = num;
        lnFirst->next = NULL;
    }
    else
    {
        lnCurrent = lnFirst;
        while( lnCurrent->next != NULL )
            lnCurrent = lnCurrent->next;

        lnNew = new Node;
        lnNew->value = num;
        lnNew->next = NULL;
        lnCurrent->next = lnNew;
    }
}

bool ListNode::Contains(int num)
{
    bool boolDoesContain = false;
    Node *lnTemp,*lnCurrent;
    lnCurrent = lnFirst;
    lnTemp = lnCurrent;
    while( lnCurrent!=NULL )
    {
        if( lnCurrent->value == num )
        {
            boolDoesContain = true;
            return boolDoesContain;
        }
        lnTemp = lnCurrent;
        lnCurrent = lnCurrent->next;
    }
    return boolDoesContain;
}

int ListNode::GetValue(int num)
{
    Node *lnTemp;
    int intCount = 1;
    for( lnTemp=lnFirst; lnTemp != NULL; lnTemp = lnTemp->next )
    {
        if (intCount == num)
        {
            return lnTemp->value;
        }
        intCount++;
    }
}

int main()
{
    cout << "Input integers below. Input the integer -1 to stop inputting.\n\n";

    ListNode lnList;
    int intNode = 1, intInput = 0;
    while (intInput != -1) {
        cout << "Please input integer number " << intNode << ": "; cin >> intInput;
        intNode++;
        if (intInput != -1) { lnList.Insert(intInput); }
    }

    lnList.DisplayList();
    cout << "\n\n";

    int intListLength = lnList.Length();
    cout << "Which value do you wish to recall? (Between 1 and " << intListLength << "): "; cin >> intNode;
    if ( intNode >= 1 && intNode <= intListLength ) {
        cout << "Value at position " << intNode << " is " << lnList.GetValue(intNode) << ".";
    } else {
        cout << "No such position in the list. Positions run from 1 to " << intListLength << ". You asked for " << intNode << ".";
    }

    cout << "\n\nCheck if the following value is in the list: "; cin >> intNode;
    bool IsThere = lnList.Contains(intNode);
    if (IsThere) {
        cout << intNode << " is in the list.";
    } else {
        cout << intNode << " is not in the list.";
    }

    cout << "\n\n";
    system("pause");
    return 0;
}

class ListNode {
private:
    int value;
    ListNode * next;

public:
    bool listcontains(int v) {
        // does this node contain the value?
        if(value == v) return true;

        // was this the last node?
        if(next == 0) return false;

        // return whether nodes after us contain the value
        return next->listcontains(v);
    }
};

Ответ 2 · рейтинг 3 · Cyrille Ka

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

Я бы посоветовал вам не помещать несколько команд в одну строку, например:

cout << "Please input integer number " << intNode << ": "; cin >> intInput;

Это просто сбивает с толку.

Ответ 3 · рейтинг 3 · Pieter

Что касается более общего стиля, объявите указатели ближе к тому месту, где вы их определите, и старайтесь, чтобы их область действия была как можно меньше.
Хотя с технической точки зрения в вашем коде не может быть ошибок, всегда делайте это, чтобы избежать ошибок в гораздо более крупных/старых кодах. кодовые базы по моему опыту.

например вместо

Node *lnTemp;
int intCount = 0;
for( lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
{
}

записывать

int intCount = 0;
for(Node* lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next )
{
}

или, аналогично, вместо

Node *lnTemp,*lnCurrent;
lnCurrent = lnFirst;
lnTemp = lnCurrent;

записывать

Node* lnCurrent = lnFirst;
Node* lnTemp = lnCurrent;

Ответ 4 · рейтинг 2 · unwind

Я думаю, что вы слишком усложняете моделирование узла списка. Класс ListNode IS A узел списка, то есть видно из его названия. Тогда ему не нужна вложенная структура для хранения информации о списке, что очень сбивает с толку.

Ответ 5 · рейтинг 2 · jalf

Более подробный отзыв внизу этого поста, а для начала просто некоторые встроенные комментарии и изменения в коде:

struct Node // Why doesn't this have a constructor initializing the members?
{
        int value;
        Node *next;
} *lnFirst;


ListNode::ListNode() : lnFirst(NULL) {} // Use initializer lists instead of initializing members in the ctor body. It's cleaner, more efficient and may avoid some nasty bugs (because otherwise the member gets default-initialized *first*, and then assigned to in the body)

int ListNode::Length()
{
    int intCount = 0;
    for( Node* lnTemp=lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next ) // Create the loop iteration variable lnTemp here, in the loop, not at the start of the function
    {
        intCount++;
    }
    return intCount;
}

void ListNode::DisplayList()
{
    for(Node* lnTemp = lnFirst ; lnTemp != NULL ; lnTemp = lnTemp->next ) // And again, initialize the loop variable in the loop
        cout<<endl<<lnTemp->value; // Not a huge deal, but endl flushes the stream as well as inserting a newline. That can be needlessly slow. So you might want to just use "\n" in cases where you don't need the flushing behavior.
}

void ListNode::Insert(int num)
{
//    Node *lnCurrent, *lnNew; // Very subjective, but I prefer not declaring multiple variables on the same line, because the syntax if they're pointers can be surprising (You got it right, but a lot of people would write Node* lnCurrent, lnView, which would make lnView not a pointer. I find it clearer to just give ecah variable a separate line:
    if( lnFirst == NULL )
    {
//        lnFirst = new Node;
//        lnFirst->value = num;
//        lnFirst->next = NULL;
        lnFirst = new Node(num); // Make a constructor which initializes next to NULL, and sets value = num. Just like you would in other languages. ;)
    }
    else
    {
        Node* lnCurrent = lnFirst; // Don't declare variables until you need them. Both to improve readability, and because C++ distinguishes between initialization and assignment, so in some cases, default-initialization followed by assigment may not be the same as just initializing with the desired value.
        while( lnCurrent->next != NULL )
                lnCurrent = lnCurrent->next;

        Node* lnNew = new Node(num); // Again, let a constructor do the work.
        lnCurrent->next = lnNew;
    }
}

bool ListNode::Contains(int num)
{
    bool boolDoesContain = false;
//    Node *lnTemp,*lnCurrent; // Again, don't initialize variables at the start of the function if they're not needed
    Node* lnCurrent = lnFirst;
//    lnTemp = lnCurrent;
    while( lnCurrent!=NULL )
    {
        if( lnCurrent->value == num )
        {
//                boolDoesContain = true;
//                return boolDoesContain;
                  return true; // Just return directly, and remove the boolDoesContain variable. Alternatively, set boolDoesContain to true, and then break out of the loop without returning, so you have a single exit point from the function. Both approaches have their merits, but setting a variable you don't need, and then returning is silly. ;)
        }
//        Node* lnTemp = lnCurrent; // you don't actually use lnTemp for anything, it seems
        lnCurrent = lnCurrent->next;
    }
//    return boolDoesContain;
      return false; // just return false. If you get this far, it must be because you haven't found a match, so boolDoesContain can only be false anyway.
}

int ListNode::GetValue(int num)
{
//    Node *lnTemp;
    int intCount = 1; // Wouldn't most people expect this indexing to be zero-based?
    for( Node* lnTemp=lnFirst; lnTemp != NULL; lnTemp = lnTemp->next )
    {
        if (intCount == num)
        {
            return lnTemp->value;
        }
        intCount++;
    }
}

Теперь пара общих замечаний. (Я собираюсь проигнорировать, поняли ли вы задание неправильно, и сосредоточусь на опубликованном вами коде) Во-первых, венгерская нотация: Не делайте этого. Сначала вызовите указатели узлов, temp и все остальное, без префикса "ln". Назовите свою логическую переменную doContain без ненужного префикса 'bool'. Во-вторых, как я пытался сделать в отредактированном коде, создавайте переменные только тогда, когда они вам нужны. C раньше требовал, чтобы переменные объявлялись в начале блока, но C++ никогда этого не делал. В-третьих, вам не нужен "возврат 0" в конце основной функции. Main - это особый случай, когда при достижении конца функции автоматически возвращается 0.

В-четвертых, у нас есть большая неприятная проблема: управление памятью. Вы выделяете память, которая никогда не освобождается. Поскольку у вас нет функции RemoveNode, это может показаться спорным вопросом, но что происходит, когда весь список сам выходит за рамки и удаляется? Ни один из его узлов не удаляется, потому что все, что есть в списке, - это набор указателей, и он не вызывает для них автоматическое удаление. Так что, по крайней мере, вам нужен деструктор в самом классе списка, чтобы при удалении списка он обязательно удалял все его дочерние узлы.

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

Следующая большая проблема, что, если я скопирую список?

int main(){
ListNode list;
list.Insert(1);
list.Insert(2);
list.Insert(3);
}
ListNode list2 = list;

Ваш код взрывается. Оба списка теперь указывают на одни и те же узлы, вместо того, чтобы создавать копии узлов. Добавление узла в один список также заставит его отображаться в другом. И прежде чем утверждать, что "это фича, а не баг" ;), подумайте, что происходит, когда один из списков удаляется сейчас.

Предположим, что list2 удаляется первым. Только что определенный нами деструктор удаляет три узла и возвращает значение. Теперь список указывает на узлы, которые были удалены. Доступ к ним является неопределённым поведением и вполне может привести к сбою. Итак, скажем, мы не обращаемся к ним, вместо этого мы просто быстро удаляем и этот список.

Упс, это означает, что мы пытаемся удалить дочерние узлы, которые уже были удалены. Это определенно похоже на аварию.

Поэтому, чтобы исправить это, ваш класс ListNode должен реализовать две дополнительные функции: конструктор копирования и оператор присваивания:

ListNode(const ListNode& other);
ListNode& operator==(const ListNode& other);

Эти двое должны гарантировать, что при копировании всех данных из "другого". Для каждого узла в "другом" вы должны выделить новый узел в текущем списке, а не просто заставлять оба списка указывать на один и тот же узел. (Это означает, что класс узла, скорее всего, также нуждается как минимум в конструкторе копирования).

Это основной способ управления памятью, и его важно понимать, иначе вы напортачите. ;)

Ответ 6 · рейтинг 1 · Rasmus Faber

Часть задания гласила:

Обеспечьте следующие функции:

• ListNode(int v, ListNode *l)
• int получить значение();
• СписокУзел* getNext();
• пустая вставка (целое я);
• логический список содержит (int j);

Вы не предоставили ни одну из этих функций.

Как указали некоторые другие, вы реализовали List вместо ListNode, поэтому сигнатуры ваших функций разные.

Но также не следует бездумно нарушать правила кодирования задания. У вас есть опыт работы с C#? В соглашениях о кодировании C++ обычно предписываются имена методов в нижнем регистре.

Ответ 7 · Vinko Vrsalovic

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