1

大家好。我正在做一个涉及动态内存分配、指针、类和异常的链表练习。有人愿意批评它并告诉我在风格和我上面列出的主题方面我做错了什么以及我应该做得更好吗？

/*

Linked List exercise

*/

#include <iostream>
#include <exception>
#include <string>
using namespace std;

class node{
public:
    node * next;
    int * data;
    node(const int i){
        data = new int;
        *data = i;
    }
    node& operator=(node n){
        *data = *(n.data);
    }
    ~node(){
        delete data;
    }
};

class linkedList{

public:

    node * head;
    node * tail;
    int nodeCount;

    linkedList(){
        head = NULL;
        tail = NULL;
    }

    ~linkedList(){
        while (head){
            node* t = head->next;
            delete head;
            if (t) head = t;
        }
    }

    void add(node * n){
        if (!head) {
            head = n;
            head->next = NULL;
            tail = head;
            nodeCount = 0;
        }else {
            node * t = head;
            while (t->next) t = t->next;
            t->next = n;
            n->next = NULL;
            nodeCount++;
        }
    }

    node * operator[](const int &i){
        if ((i >= 0) && (i < nodeCount)) throw new exception("ERROR:  Invalid index on linked list.", -1);
        node *t = head;
        for (int x = i; x < nodeCount; x++) t = t->next;
        return t;
    }

    void print(){
        if (!head) return;
        node * t = head;
        string collection;
        cout << "[";
        int c = 0;
        if (!t->next) cout << *(t->data);
        else while (t->next){
            cout << *(t->data);
            c++;
            if (t->next) t = t->next;
            if (c < nodeCount) cout << ", ";
        }
        cout << "]" << endl;
    }

};

int main (const int & argc, const char * argv[]){

    try{
        linkedList * myList = new linkedList;
        for (int x = 0; x < 10; x++) myList->add(new node(x));
        myList->print();
    }catch(exception &ex){
        cout << ex.what() << endl;
        return -1;
    }   
    return 0;
}
4

4 回答 4

7

数据不需要是指针。

使用 ctor-initializer 列表，对于 const 正确性和异常安全性更好。您的任何构造函数都不需要在正文中包含任何代码。

您的linkedList 构造函数没有初始化nodeCount。

您没有将列表的尾指针用于任何事情。在添加的非空情况下，它可以节省您扫描整个列表 - 如果您保持它是最新的。

索引 (operator[]) 在链表上是一种不寻常的支持。OTOH，您还没有执行删除功能。

operator[] 不应通过引用获取其参数。只有大型结构需要通过 const 引用传递，像 int 这样的小类型应该只通过值传递。

现在，如果 add 失败，指向 new node() 的指针就会泄漏。（但除非列表链接损坏，否则我实际上并没有看到添加失败的方法。）

您应该在节点上定义一个私有复制构造函数以防止数据双重释放。每当您定义 operator= 和析构函数时，您还应该定义或删除复制构造函数（三规则）。您还应该在linkedList 上定义私有复制构造函数和赋值运算符以防止双重释放。

未使用 print 函数中的变量字符串集合。print() 中的变量 t 应该是指向 const 的指针。print 本身应该是一个 const 成员函数。

于 2010-03-13T19:18:21.927 回答
4 
/*
Linked List exercise
*/

class node {
public:
    node * next;
    int * data;

data并不真的需要成为一个指针（除非你的课堂作业说它必须是）。您可以将其更改为int，然后将您的引用从 更改*(t->data)为 just t->data。同样，您不需要在 ctor/dtor 中使用newand 。delete

    node(const int i) {
        data = new int;
        *data = i;
    } 
    node& operator=(node n) {
        *data = *(n.data);
    } 
    ~node() {
        delete data;
    } 
};

class linkedList {

public:
    node * head;
    node * tail;
    int nodeCount;

    linkedList() {
        head = NULL;
        tail = NULL;

您应该在此处初始化所有数据成员。nodeCount除非您在此处将其设置为零，否则将具有一些随机值。

    } 

    ~linkedList() {
        while (head) {
            node* t = head->next;
            delete head;
            if (t)
                head = t;

这看起来像一个错误。即使 t 是，您也需要始终分配，否则您的循环不会终止（但多次删除同一个节点可能会导致异常）。head = tNULL

        } 
    } 

    void add(node * n) {
        if (!head) {
            head = n;
            head->next = NULL;
            tail = head;
            nodeCount = 0;

我认为这整个if声明是不必要的。当链表为空时，两个分支都做同样的事情，所以你总是可以使用第二个（else）分支。

此外，最后设置nodeCount为0似乎是一个错误。不应该1吗？

        } else {
            node * t = head;

            while (t->next)
                t = t->next;

            t->next = n;
            n->next = NULL;
            nodeCount++;
        } 
    } 

    node * operator[](const int &i) {

一个小问题，但const int &争论并没有任何意义。int仅仅传递一个类型，你并没有获得任何好处。

        if ((i >= 0) && (i < nodeCount))
            throw new exception("ERROR:  Invalid index on linked list.", -1);

上面的情况在我看来是倒退的；您将始终使用有效参数引发异常。

        node *t = head;

        for (int x = i; x < nodeCount; x++)
            t = t->next;

上面的循环对我来说似乎有点可疑。如果i是您想要的节点的从零开始的索引，您的计数器不应该从0到i-1吗？

        return t;
    } 

    void print() {
        if (!head)
            return;

同样，您应该使此方法有效，而不必防范空列表。我希望一个空列表可以打印类似的东西[]，但是使用上面的保护代码，你什么都不会打印。

        node * t = head;
        string collection;
        int c = 0;

        cout << "[";

        if (!t->next) {
            cout << *(t->data);

像上面的其他条件一样，我认为上面的分支是不必要的。第二个（else）分支应该NULL可以很好地处理这个案例。

        } else {
            while (t->next) {

我想你想要while (t)上面而不是while (t->next)

                cout << *(t->data);
                c++;

                if (t->next)
                    t = t->next;

我认为这是一个类似于之前的错误。你应该总是指定`t = t->next'，否则你的循环不会终止。

                if (c < nodeCount)
                    cout << ", ";
            } 
        } 

        cout << "]" << endl;
    } 
};

int main (const int & argc, const char * argv[]) { // const int& ?

const int &再次...

    try {
        linkedList * myList = new linkedList;
        for (int x = 0; x < 10; x++)
            myList->add(new node(x));
        myList->print();
    } catch(exception &ex) {
        cout << ex.what() << endl;
        return -1;
    }

对于家庭作业来说可能没问题，但是捕获所有可能的异常（正如您在上面所做的那样）可能不会在这里增加太多价值，并且通常被认为是不好的做法。

如果您忽略上面的 try/catch 内容，我怀疑每当您的程序以异常终止时，编译器提供的默认顶级异常处理程序无论如何都会转储异常和堆栈跟踪信息（取决于您的编译器）。

    return 0;
}
于 2010-03-13T20:02:26.930 回答
0 
if ((i >= 0) && (i < nodeCount)) throw new exception("ERROR:  Invalid index on linked list.", -1);

该行应为：

if( i < 0 || i >= nodeCount ) throw...

add 方法也有问题：

void add(node * n){
    if (!head) {
        head = n;
        head->next = NULL;
        tail = head;
        nodeCount = 0;
    }else {
        node * t = head;
        while (t->next) t = t->next;
        t->next = n;
        n->next = NULL;
        nodeCount++;
    }
}

对于一个在添加第一个节点后的计数将为 0，对于另一个您正在搜索以插入到链表中......人们期望的操作是 O(1)。

更典型的实现是：

void add( node* n ) {
   node* old_head = head;
   head = n;
   head->next = old_head;
   ++nodeCount;
   if( old_head == NULL )
      tail = head
}
于 2010-03-13T19:19:59.087 回答
0

1）您可以使用data = new int(i)初始化字段。

2）您在 operator[] 中创建了错误的条件if ((i >= 0) && (i < nodeCount))，它应该被反转，比如if ((i < 0) || (i >= nodeCount))

于 2010-03-13T19:20:47.667 回答