鏈接列表練習，我做錯了什麼？

Question

嘿，所有。我正在做一個鏈接列表練習，涉及動態內存分配，指針，類和異常。有人願意對它進行批評並告訴我我做錯了什麼，以及在風格和我上面列出的那些主題方面我應該做得更好？

/* 

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

Answer 1

沒有必要將數據作爲指針。

使用構造函數初始化程序列表，它是常量，正確性和異常安全更好。你的構造函數都不需要在內部有任何代碼。

你LinkedList的構造函數沒有初始化nodeCount。

您沒有使用您的列表的尾指針的任何東西。如果您保持最新狀態，這將節省您在非空案例中掃描整個列表。

索引（運營商[]）是一個不尋常的事情，以支持一個鏈表上。 OTOH你還沒有做過刪除功能。

運算符[]不應該通過引用取其參數。只有大型結構需要通過const引用傳遞，像int這樣的小型應該只是通過值傳遞。

現在，如果添加失敗，則指向新節點（）泄漏。 （但我沒有真正看到了添加到失敗，除非列表裏的鏈接被損壞了的方式。）

你應該節點，以防止雙免費的數據定義的私人拷貝構造函數。每當你定義operator =和析構函數時，你也應該定義或刪除拷貝構造函數（三條規則）。您還應該在linkedList上定義私有拷貝構造函數和賦值運算符，以防止雙免費。

變量string集合打印功能不被使用。 print（）中的變量t應該是一個指向const的指針。打印本身應該是一個const成員函數。

Answer 2

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 
} 

Answer 3

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

2）你已經創建了一個操作符[] if ((i >= 0) && (i < nodeCount))一個錯誤的情況下，它應該被反轉，像if ((i < 0) || (i >= nodeCount))

Answer 4

/* 
Linked List exercise 
*/ 

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

data並不真正需要的是一個指針（除非你的課堂作業說它必須）。您可以將其更改爲int，然後將您的參考文獻從*(t->data)更改爲t->data。同樣，您不需要在ctor/dtor中使用new和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; 

這看起來像一個錯誤。你需要總是分配head = t，即使當t是NULL，否則你的循環將不會終止（但多次刪除同一個節點可能會導致異常）。

 } 
    } 

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

我覺得這整個if聲明是不必要的。鏈接列表爲空時，兩個分支都執行相同的操作，因此您可以始終使用第二個分支（，其他分支爲）。

另外，在末尾設置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) { 

A小調挑剔，但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); 

像上面的其他條件，我認爲上面的分支是不必要的。第二個（其他）分支應該處理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 & again ...

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