我的链表方法有什么改进吗?

首先,对于一般用途,您应该使用标准库: 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 设置为null是毫无意义的——它是一个即将超出范围的局部变量。你回来了 write 阅读 ,已被删除。

此外,在代码中几乎没有使用C++和对象OrristEng编程的特性:如果忽略CUT,它基本上只是通过新的和AMP分配内存的C代码;删除。正如我所指出的,它可以从构造函数中获益匪浅。一个析构函数可能也很有用,再加上一个List类,它将保存head节点,并将所有函数作为成员。

看看你的“推送”功能,这里有一些建议:

• 为清楚起见,第一个参数应命名为“head”,而不是“read”

• “if(read==NULL)”测试的两个分支之间有很多重复。找出公共代码(例如,使用@James建议的构造函数)

• 将您正在执行的步骤分解为“创建一个值为'val'的节点”、“查找列表的结尾”、“如果列表为空,则head=new;其他尾部->下一个=新“

如果您正在创建一个C样式的链表类,那么应该使用 void * 对于数据项,允许您将链表与其他类型一起使用:

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

另一方面,如果您想使用C++设备,可以扩展使用 template 对于数据类型。A 模板 实例化 模板(模具)的类型:

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

列表 阶级或结构。这将帮助用户区分实例化。在C样式中,这个结构将被传递给list方法(因此list方法知道对哪个list进行操作)。

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

然后,这里和那里有相当多的错误。我没有复习所有的代码,但我可以给你一些提示:

• 总是检查边界,覆盖所有情况。如果我给出了一个无效的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这样的构造->下一步->其次,因为它们很容易出错。

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