C++ указатели/Списки реализации

Question

Написать класс ListNode, который имеет следующие свойства:

• INT значение;
• ListNode * next;

обеспечивают следующие функции:

• ListNode (Int V, ListNode * L)
• INT GetValue();
• ListNode * getNext();
• void insert (int i);
• bool listcontains (int j);

Напишите программу, которая просит пользователя ввести некоторые целые и сохраняет их в качестве ListNodes, а затем запрашивает номер, который он должен искать в списке.

Вот мой код:

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

Где мы можем улучшить это?

Answer 1

Что скажите, пожалуйста, и 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;

Answer 2

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

Answer 3

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

Я бы советовал не ставить несколько команд на одном Ligne, как это:

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

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

Answer 4

Часть задания следующим образом:

обеспечивают следующие функции:

• ListNode (Int V, ListNode * L)
• INT GetValue();
• ListNode * getNext();
• void insert (int i);
• bool listcontains (int j);

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

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

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

Answer 5

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

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

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; 

Answer 6

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

Answer 7

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

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 doContain без лишнего префикса «bool». Во-вторых, поскольку я пытался сделать редактируемый код, создавайте переменные только тогда, когда они вам понадобятся. C используется для запроса переменных, которые должны быть объявлены в верхней части блока, но C++ так и не сделал. В-третьих, вам не нужно «вернуть 0» в конце основной функции. Main - это особый случай, когда, если он достигает конца функции, он автоматически возвращает 0.

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

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

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

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

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

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

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

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

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

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

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