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

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

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

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

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

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

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

Provide the following functions:

• ListNode(int v, ListNode *l)
• int getValue();
• ListNode* getNext();
• void insert(int i);
• bool listcontains(int j);

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

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

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

Что говорят раскрученные и ckarmann. Вот подсказка, я реализую listcontains для вас, чтобы вы поняли, как может означать назначение:

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);
    }
};

Итак, у вас есть только заголовок списка, который по очереди ссылается на следующий узел. Хвост будет иметь next == 0;

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

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

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;

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

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

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. Вызовите свою переменную типа bool doesContain без ненужного префикса 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);

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

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