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

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

More

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