Какие-либо улучшения по сравнению с моим методом связанных списков?

Question

Я постоянно пишу программу, чтобы улучшить мои знания о связанных списках и о том, как они функционируют.Мне было интересно, могут ли некоторые из вас просмотреть мой код и заметить какие-либо ошибки, с которыми вы, возможно, знакомы, или какие-либо ошибки вообще.Функции работают для моих тестовых функций, но, очевидно, я не проверял все возможные сценарии.

    // LinkedList.cpp : Defines the entry point for the console application.
//

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

using std::cout;
using std::cin;
using std::endl;

struct node
{
    int value;
    node* next;
};

node* push(node*, int);
node* pop(node*);
node* pop(node*, int);
node* insert(node*, int, int);
void printList(const node*);

int _tmain(int argc, _TCHAR* argv[])
{
    node* head = NULL;

    for(int i = 1; i <= 15; ++i)
    {
        head = push(head, i);
    }

    for(int j = 14; j >= 0; j = j - 2)
    {
        head = pop(head, j);
        printList(head);
    }

    head = pop(head);
    head = insert(head, 4, 27);
    printList(head);
    cin.ignore();
}

node* push(node* read, int val)
{
    node* write = read;
    if(read == NULL)
    {
        read = new node;
        read->next = NULL;
        read->value = val;
        cout << "Node Head: " << read->value << endl;
        return read;
    }
    else
    {
        while(read->next != NULL)
        {
            read = read->next;
        }
        read->next = new node;
        read->next->next = NULL;
        read->next->value = val;
        read = read->next;
        cout << "Node Link: " << read->value << endl;
        return write;
    }
}

node* pop(node* read)
{
    node* write = read;
    if(read->next == NULL)
    {
        delete read;
        read = NULL;
        return write;
    }
    else
    {
        while(read->next != NULL)
        {
            if(read->next->next == NULL)
            {
                cout << "Pop: " << read->next->value << endl;
                delete read->next;
                read->next = NULL;
            }
            else
            {
                read = read->next;
            }
        }
        return write;
    }
}

node* pop(node* read, int pos)
{
    node* write = read;
    if(read->next == NULL)
    {
        delete read;
        return write;
    }
    else
    {   
        if(pos == 0)
        {
            node* old = read;
            cout << "Pop: " << read->value << endl;
            read = read->next;
            delete old;
            return read;
        }
        else
        {
            for(int i = 0; i < (pos - 1); i++)
            {
                read = read->next;
            }
            node* old = read->next;
            cout << "Pop: " << old->value << endl;
            read->next = read->next->next;
            delete old;
            return write;
        }
    }
}

node* insert(node* read, int pos, int val)
{
    node* write = read;
    for(int i = 0; i < (pos - 1); i++)
    {
        read = read->next;
    }
    node* ins = new node;
    ins->value = val;
    cout << "Insert: " << ins->value << endl;
    ins->next = read->next;
    read->next = ins;
    return write;
}

void printList(const node* read)
{
    if(read != NULL)
    {
        cout << "List Item: " << read->value << endl;
        printList(read->next);
    }
}

/****************OUTPUT*********************
Node Head: 1
Node Link: 2
Node Link: 3
Node Link: 4
Node Link: 5
Node Link: 6
Node Link: 7
Node Link: 8
Node Link: 9
Node Link: 10
Node Link: 11
Node Link: 12
Node Link: 13
Node Link: 14
Node Link: 15
Pop: 15
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 11
List Item: 12
List Item: 13
List Item: 14
Pop: 13
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 11
List Item: 12
List Item: 14
Pop: 11
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 12
List Item: 14
Pop: 9
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 7
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 5
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 3
List Item: 1
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 1
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 14
Insert: 27
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 27
List Item: 10
List Item: 12
*******************************************/

Answer 1

Ну, во-первых, для общего использования вы должны использовать Стандартную библиотеку: std:vector, или, если вам действительно нужен связанный список, std::list<>. Но, поскольку это упражнение самообучения, мы пропустим это.

Что приводит нас к следующей проблеме: как учебное упражнение, на самом деле это не рабочий код, на что нам жаловаться? Кут в середине функций ??

Одна конкретная проблема, которую я увидел, была такая:

    read = new node;    
    read->next = NULL;    
    read->value = val; 

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

    read = new node(val);

Еще одна проблема: в pop () у вас есть:

node* write = read; 
if(read->next == NULL) 
{ 
    delete read; 
    read = NULL; 
    return write; 
} 

Установка read на ноль - бессмысленна - это локальная переменная, которая вот-вот выйдет из области видимости. И вы возвращаете write, что равно read, который был удален.

Кроме того, вы почти не используете в коде функции C ++ и объектно-ориентированного программирования: если мы игнорируем cout, то в основном это просто код C, который выделяет память через new & delete. Как я уже отметил, это может принести пользу конструктору. Также может быть полезен деструктор плюс класс List, который будет содержать головной узел и будет иметь все ваши функции в качестве членов.

Answer 2

Если пользователь может удалить узел в определенной позиции, я не думаю, что его можно назвать «поп»Pop обычно означает удаление только верхнего узла, как в стеке."удалить", вероятно, будет лучшим именем.

Answer 3

Если вы создаете класс связанного списка в стиле C, вы должны использовать void * для элемента данных, что позволит вам использовать связанный список с другими типами:

struct Node
{
    void * p_data;
    struct Node * next;
};

НаС другой стороны, если вы хотите использовать средства C ++, вы можете расширить для использования template для типа данных.A template позволит вам использовать один и тот же код для разных типов.Компилятор разрешит тип данных во время создания шаблона (трафарета):

template <class Data_Type>
struct Node
{
    Data_Type data;
    Node *    next;
};

Как уже говорили другие, у вас должен быть класс List ,или структура.Это поможет пользователям различать экземпляры.В стиле C эта структура будет передаваться методам списка (поэтому методы списка знают, с каким списком работать).

struct List_Header
{
    struct Node * head;
    struct Node * tail;
    unsigned int  size; // Quantity of nodes
};

void List_Push(List_Header * p_header, void * data)
{
  if (p_header)
  {
    // Create a node, prepend to list, etc.
  }
  return;
}

Для использования списка:

List_Header    my_list;
unsigned int *   my_data(new int(1));
List_Push(&my_list, my_data);

Answer 4

Вы делаете список в стиле C.В C ++ вы бы использовали класс для узла и другой класс для списка.Класс для списка должен иметь член для первого элемента в списке.Тогда здесь и там есть некоторые ошибки.Мне не удалось просмотреть весь код, но я могу дать вам несколько советов:

• всегда проверяйте границы, охватывайте все случаи.Что произойдет, если я дам недопустимый pos (> размер)?:

   node* insert(node* read, int pos, int val)
    {
       node* write = read;
       for(int i = 0; i < (pos - 1), read <> NULL; i++) 
       {// you should make the for stop if it hits the bottom of the list
           read = read->next; 
       }
       if (read == NULL) return NULL
       node* ins = new node;
       ins->value = val;
       cout << "Insert: " << ins->value << endl;
       ins->next = read->next;
       read->next = ins;
       return write;
   }
  

• Будьте осторожны с памятью и тем, как вы ее используете.Постарайтесь как можно больше избегать таких конструкций, как node-> next-> next, поскольку они очень подвержены ошибкам.

    node* pop(node* read)
    {
        node* write = read;
        if(read->next == NULL)
        {
            delete read;
            read = NULL;
            return write;
        }
        else
        {
            while(read->next != NULL)
            {
                if(read->next->next == NULL)
                {
                    cout << "Pop: " << read->next->value << endl;
                    delete read->next;
                    read->next = NULL;
                }
                else
                {
                    read = read->next;
                }
            }
            return write;
        }
    }
  

Можно просто написать так:

     node* pop(node* head)
     {
        if (head == NULL) return;

        node* previous = NULL;
        node* returnVal = head;

        while (head->next != NULL)
        {
            previous = head;
            head = head->next;
        }
        if (previous != NULL)
        {
            previous->next = NULL;
            delete head;
        }
        else //we need to pop out the head :)
        {
            delete head;
            returnVal = null;
        }
        return returnVal;
     }

Немного смущает отсутствие глобального члена класса, указывающего на заголовок списка.Я к этому не привык .. Функция удаления списка в стиле C ++ будет написана так:

void SingleLinkedList::RemoveElement(TInfo value)
{
    Node* cursor = mHead;
    Node* lastCursor = NULL;

    if (cursor != NULL) while (cursor->GetNext() != NULL && cursor->GetInfo() != value) 
    {
        lastCursor = cursor;
        cursor = cursor->GetNext();
    }
    if (cursor->GetInfo() == value)
    {
        lastCursor->SetNext(cursor->GetNext());
        delete cursor;
    }
}

И определение классов выглядит так:

#define NULL 0
typedef int TInfo;

class Node
{
private:
    TInfo info;
    Node* next;
public:

    Node()                          {info = 0; next = NULL;}
    Node(TInfo iInfo, Node* iNode)  {info = iInfo; next = iNode;}
    ~Node()                         {info = 0; next = NULL;}

    TInfo GetInfo() const           {return info;}
    Node* GetNext() const           {return next;}

    void SetInfo(TInfo value)       {info = value;}
    void SetNext(Node* pValue)      {next = pValue;}
};

class SingleLinkedList
{
private:
    Node* mHead;
    int mCount;

    void RecursiveRemove(Node* iNode);

public:
    SingleLinkedList();
    ~SingleLinkedList() {mHead = NULL;};

    int Count() const               {return mCount;}
    Node* const GetHead() const     {return mHead;}

    void ClearList();
    void AddHeadElement(TInfo value);
    void AddTailElement(TInfo value);
    void RemoveElement(TInfo value);
    bool SearchElement(TInfo value, int &pos);
};

void PrintList (SingleLinkedList const& list);

ТамЕсть много улучшений, которые вы можете внести в свой код.Думай просто:)

Answer 5

Если посмотреть только на вашу функцию «push», вот несколько предложений:

• 1-й параметр должен называться «head», а не «read», для ясности

• между двумя ветвями теста "if (read == NULL)" много дублирования.Вычеркните общий код (например, используя конструктор, предложенный @James)

• разбейте шаги, которые вы делаете, на что-то вроде «создайте узел со значением« val »"," найти конец списка "," если список пуст, head = new; иначе tail-> next = new "