程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> (15 C++ Lab) D&A Simple Linked List

(15 C++ Lab) D&A Simple Linked List

編輯：關於C++

description

Knowledge points: (copy) constructor, deep copy, pointers, dynamic allocation, linked list algorithms, debug methods(GDB or IDE or output debug), memory leak.

In this Lab, you are going to implement a class named list which is a simple version for the list in stl. You are going to use dynamic memory allocation and pointer operations to finish this project.

I recommend you to:

Learn the knowledge points mentioned above.
Use local compilers to test you program rather than submit your answer to the system time after time.
Use local debug tools(GDB is recommended) to debug your code, especially for the memory leak problem. I can tell you that you will meet runtime error problem if you don’t use local debug tools.
Make use of your paper and pen to have some sketches because it’s a good way when you meet list.

Requirements:

Finish all the functions which have been declared inside the hpp file.

Details:

string toString(void) const

Return a visible list using ‘->’ to show the linked relation which is a string like:

1->2->3->4->5->NULL

void insert(int position, const int& data)

Add an element at the given position:

example0:

1->3->4->5->NULL

instert(1, 2);

1->2->3->4->5->NULL

example1:

NULL

insert(0, 1)

1->NULL

void list::erase(int position)

Erase the element at the given position

1->2->3->4->5->NULL

erase(0)

2->3->4->5->NULL

Happy coding…

Hint:

建議使用調試工具，注意內存洩露問題，注意在鏈表頭部插入數據的問題，注意.

請大家使用本地編譯器(VS或DEV CPP或MinG)編程調試，不要直接在系統上編寫代碼！

=============================================================================

請大家相信，這道題是一道很重要的題目，c++裡面重要的知識點都在裡面體現，特別是c++獨有的指針。請不要放棄治療。

你們罵我也好，吐槽也好，請大家靜下心來好好做這道題目，你會有很大收獲。

我知道肯定會遇到很多很多問題，希望大家能夠平心靜氣去解決這些問題，比如：

編譯錯誤，很大一部分同學兩節實驗課都沒能使得程序通過編譯，原因就是第一對c++語法很不熟悉，域作用符號與命名空間，函數原型等知識理解有偏差，第二對編譯器的報錯非常陌生，或者不會看編譯器的錯誤信息，關鍵是要理解。

淺拷貝很深拷貝，有同學直接對指針進行賦值，卻忽略了指針指向的整個鏈表。打個比方，淺拷貝就是“創建快捷方式”，深拷貝就是真正的“復制粘貼”，淺拷貝中兩個指針指向同一塊內容，深拷貝則是兩個指針有兩塊數據相同的內存空間。

3.new delete運算符不會使用，這個可以參考老師課件。

賦值運算符重載問題，重載時候沒有考慮要將當前(this)對象清除導致內存洩露。或者在拷貝構造函數裡面調用賦值運算符時候，沒有先初始化head和_size。

鏈表算法不熟悉，重要的是畫圖，一定要畫圖！指針之間怎麼解出鏈接，怎麼重新鏈接的，一定要通過草稿來理解。還有在鏈表頭部操作和空鏈表是特殊情況，必須特殊處理。

內存洩露控制，這是一個很關鍵的知識。解決內存洩露問題：1. 養成良好的編程習慣，在對原指針賦值的時候，時刻想著會不會出現內存塊丟失的問題。 2. 可以維護一個容器，通過重載new和delete運算符來記錄堆內存的申請 3. 通過eden系統的提示，慢慢尋找內存錯誤的源頭（需要耐心和細心）

如果有問題請找ta，我們很樂意回答你們問題。

請大家多點耐心和細心，靜下心來，慢慢調試程序，你所遇到的所有問題都是學習c++路上很珍貴的經驗，只有一個一個地解決問題，才能真正提高自己的編程能力。

建議寫一個經驗總結：

深拷貝的知識。

賦值運算符為什麼要返回 this對象？

內存洩露怎麼處理？

編程風格怎麼注意？

鏈表。

TA出題不易，越難的題目花的時間越多，通常需要寫大家3倍的代碼（頭文件，源文件，測試文件，隨機輸入），真正能提高你們的編程能力需要你的耐心和細心。

無心虐大家。。。。

harddue改到周日，大家加油。

file provided

main.cpp

#include 
#include 
#include "list.hpp"

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

int main() {
  list li;

  int n;
  cin >> n;

  for (int i = 0, data, pos; i < n; i++) {
    cin >> pos >> data;
    li.insert(pos, data);
  }

  cout << li.toString() << " size: " << li.size() << endl;

  list li2(li);
  list li3;

  li = li3 = li2 = li;

  cout << li.toString() << " size: " << li.size() << endl;
  cout << li2.toString() << " size: " << li2.size() << endl;
  cout << li3.toString() << " size: " << li3.size() << endl;

  int m;
  cin >> m;

  for (int i = 0, pos; i < m; i++) {
    cin >> pos;
    li.erase(pos);
  }

  cout << li.toString() << endl;

  cout << li.sort().toString() << endl;
  cout << li2.sort().toString() << endl;
  cout << li3.sort().toString() << endl;

  return 0;
}

list.hpp

#ifndef LIST
#define LIST

#include 
#include 

typedef struct node {
  int data;
  struct node* next;
  node(int data = 0, struct node* next = NULL) : data(data), next(next) {}
} node;

class list {
 private:
  node* head;
  int _size;

 public:
  list();
  list(const list&);
  list& operator=(const list&);
  ~list();

  // Capacity
  bool empty(void) const;
  int size(void) const;

 public:
  // output
  // list: [1,2,3,4,5]
  // output: 1->2->3->4->5->NULL
  std::string toString(void) const;

  void insert(int position, const int& data);
  void erase(int position);
  void clear(void) {
    if (this->head != NULL) {
      node* p = this->head;
      while (p != NULL) {
        node* temp = p;
        p = p->next;
        delete temp;
      }
      this->head = NULL;
    }
    this->_size = 0;
  }
  list& sort(void);
};

#endif

understanding

重要理解問題:鏈表每個元素的序號:0 1 2 3 …

my answer

#include"list.hpp"
#include
#include
#include 

using namespace std;

list::list() {
    head = NULL;
    _size = 0;
}

list::list(const list& other) {
    head = NULL;
    _size = 0;
    node* otherp = other.head;
    for (int i = 0; i < other._size; i++) {
        insert(i, otherp->data);
        otherp = otherp->next;
    }
}

list& list::operator=(const list& other) {
    clear();
    if (other._size != 0) {
        node* otherp = other.head;
        for (int i = 0; i < other._size; i++) {
            insert(i, otherp->data);
            otherp = otherp->next;
        }
    }
    return *this;
}

list::~list() {
    clear();
}

// Capacity
bool list::empty(void) const {
    return (head == NULL);
}

int list::size(void) const {
    return _size;
}


std::string list::toString(void) const {
    stringstream st;
    node* temp = head;
    while (temp != NULL) {
        st << temp->data;  // some problems
        st << "->";
        temp = temp->next;
    }
    st << "NULL";
    return st.str();
}

void list::insert(int position, const int& data) {
    if (position > _size) return;
    if (position == 0) {
        if (head == NULL) {
            head = new node(data, NULL);
        } else {
             node* NewNode = new node(data, head);
             head = NewNode;
        }
        _size++;
        return;
    }
    node* temp = head;
    for (int i = 0; i < position - 1; i++) {
         temp = temp->next;
    }
    node* NewNode = new node;
    NewNode->data = data;
    NewNode->next = temp->next;
    temp->next = NewNode;
    _size++;
}

void list::erase(int position) {
    if (_size == 0 || position > _size - 1) return;

    node* temp = head;
    if (position == 0) {
        head = head->next;
        delete temp;
        temp = NULL;
        _size--;
        return;
    }
    for (int i = 0; i < position - 1; i++) {
         temp = temp->next;
    }
    node* targetnode = temp->next;
    temp->next = targetnode->next;
    delete targetnode;
    targetnode = NULL;
    _size--;
    return;
}

list& list::sort(void) {
    if (head == NULL) return *this;
    node* temp = head;
    int* a = new int[_size];
    for (int i = 0; i < _size; i++) {
        *(a + i) = temp->data;
        temp = temp->next;
    }
    for (int i = 0; i < _size - 1; i++) {
        for (int j = i + 1; j < _size; j++) {
            if (*(a + i) > *(a + j)) {
                int t =  *(a + i);
                *(a + i) = *(a + j);
                *(a + j) = t;
            }
        }
    }
    temp = head;
    for (int i = 0; i < _size; i++) {
        temp->data = *(a + i);
        temp = temp->next;
    }
    delete []a;
    return *this;
}

the standard answer

#include "list.hpp"
#include 
#include 

list::list() {
  this->head = NULL;
  this->_size = 0;
}

list::list(const list& another) {
  this->head = NULL;
  this->_size = 0;
  *(this) = another;
}

list& list::operator=(const list& another) {
  if (this != &another) {
    this->clear();
    if (another.head != NULL) {
      this->head = new node(another.head->data);
      node* p = another.head->next;
      node* q = this->head;
      while (p != NULL) {
        q->next = new node(p->data);
        p = p->next;
        q = q->next;
      }
      q->next = NULL;
    }
    this->_size = another._size;
  }
  return *(this);
}

list::~list() { this->clear(); }

bool list::empty(void) const { return this->_size == 0; }

int list::size(void) const { return this->_size; }

std::string list::toString(void) const {
  node* positioner = this->head;
  std::string result;
  std::stringstream ss;
  while (positioner != NULL) {
    ss << positioner->data;
    std::string temp;
    ss >> temp;
    result += temp + "->";
    ss.clear();
    positioner = positioner->next;
  }
  result += "NULL";
  return result;
}

void list::insert(int position, const int& data) {
  if (position > this->_size || position < 0) {
    return;
  } else if (position == 0) {
    node* temp = new node(data, this->head);
    this->head = temp;
  } else {
    node* p = this->head;
    int counter = 1;
    while (counter != position) {
      p = p->next;
      counter++;
    }
    node* temp = new node(data, p->next);
    p->next = temp;
  }
  this->_size++;
}

void list::erase(int position) {
  if (position >= this->_size || position < 0) {
    return;
  } else if (position == 0) {
    node* temp = this->head;
    this->head = this->head->next;
    delete temp;
  } else {
    node* pre = this->head;
    int counter = 0;
    while (counter != position - 1) {
      counter++;
      pre = pre->next;
    }
    node* temp = pre->next;
    pre->next = temp->next;
    delete temp;
  }
  this->_size--;
}

list& list::sort(void) {
  if (this->head != NULL && this->head->next != NULL) {
    node* slow = head;
    node* fast = head->next;
    while (fast != NULL) {
      if (fast->data >= slow->data) {
        fast = fast->next;
        slow = slow->next;
      } else {
        node* pre = this->head;
        if (this->head->data > fast->data) {
          slow->next = fast->next;
          fast->next = this->head;
          this->head = fast;
        } else {
          while (pre->next->data <= fast->data) {
            pre = pre->next;
          }
          slow->next = fast->next;
          fast->next = pre->next;
          pre->next = fast;
        }
        fast = slow->next;
      }
    }
  }
  return *(this);
}