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

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<>.但是,因为这是一个自学教练,我们将跳过它.

这引出了下一个问题:作为一种教学练习,它实际上不是生产代码,所以我们应该抱怨什么？cout在函数中间？

我看到的一个特殊问题是这样的代码:

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

节点对象的构造函数应该处理将其next成员设置为null.就此而言,它应该处理设置值,所以这段代码应该是:

    read = new node(val);

另一个问题:在pop()中,你有:

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

设置read为null是没有意义的 - 它是一个超出范围的本地变量.并且你正在返回write,read这已经被删除了.

此外,您在代码中几乎不使用C++和Object-oreitned编程的功能:如果我们忽略cout,它基本上只是通过new&delete分配内存的C代码.正如我所指出的,它可以从构造函数中获益匪浅.析构函数也可能是有用的,加上一个List类,它将保存头节点,并将所有函数作为成员.

Answer 2

如果用户可以删除某个位置的节点,我认为它不能正确地称为"pop".Pop通常指的是仅移除顶部节点,就像在堆栈中一样."删除"可能是一个更好的名字.