天天看點
傳回

C++：單向連結清單實作C++：單向連結清單實作

C++：單向連結清單實作

标簽： C++

by 小威威

概況：

本次實驗課的代碼題難度較大(對于剛剛入門C++的人來說)，對于解答者有一定的要求：1.了解連結清單的基本操作；2.對于淺複制與深複制有一定的了解并能加以區分；3.要有較強的gdb調試能力。(沒有對程式進行調試一般情況下是得不到滿分的，不排除你是超級大大神，第一次就寫出了沒有記憶體洩漏的代碼)

這道題涉及到的知識點：

複制構造函數中的深複制，以及指針，動态記憶體配置設定，連結清單的建立，插入，删除，輸出，排序，和删除連結清單，而且還要求通過gdb調試來解決runtime error 以及 記憶體洩漏等問題。

題目如下：

(15 C++ Lab) D&A Simple Linked List(Author: 葉嘉祺(TA))

Introduction

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…

題目已給出main.cpp與list.hpp

// main.cpp
#include <iostream>
#include <string>
#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 = , 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 = , 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 ;
}


// list.hpp
#ifndef LIST
#define LIST

#include <string>
#include <iostream>

typedef struct node {
  int data;
  struct node* next;
  node(int data = , 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 = ;
  }
  list& sort(void);
};

#endif

現要求我們完成list.cpp來實作類list。

list.cpp需要完成類的構造函數、複制構造函數，”=”運算符的重載，析構函數，連結清單結點插入函數，連結清單結點删除函數，連結清單的輸出函數(按照格式)，檢查連結清單是否為空的函數，傳回連結清單結點數目的函數以及連結清單的排序函數的定義。

1.涉及到連結清單的題目，要區分一下題目建立的是何種連結清單。

(1)含頭結點的連結清單(頭結點不用來存儲資料)；

(1)不含頭結點的連結清單(也就是第一個結點就用來存儲資料)。

我是根據list.hpp中的clear函數的定義推斷出是不含頭結點的連結清單。因為在clear函數的定義中，有一個if條件是用來判斷head是否為空。為什麼我們要對連結清單的類型加以确定，原因是：對于連結清單的插入與删除操作，二者是不同的，若含有頭結點，插入資料、删除資料都無需考慮特殊情況，因為插入後的操作都是相同的。但是對于沒有頭結點的連結清單來說，插入、删除第一個位置的操作是特殊的，需要單獨拿出來定義。是以需要區分連結清單的類型。

2.複制構造函數與重載”=”的函數同時出現

當類的成員出現指針，一般都要進行深拷貝。若要進行深拷貝，一般都要定義自己複制構造函數。有時題目要求重載”=”，為了提高代碼的重用性，我們可以在複制構造函數中使用我們重載的”=”進行複制。

3.重載”=”運算符可能引起的記憶體洩漏

在重載的過程中我們不僅要考慮深拷貝，更需要考慮是否會出現記憶體洩漏的情況。在進行複制之前，要先把等号左邊的對象的連結清單進行記憶體釋放。

假設我們沒有在複制前進行記憶體釋放(已考慮了深拷貝)如：

例如這個語句，我們将list2複制給list1, list1中的head指向一塊新的記憶體，這樣它就不再指向原有的那塊記憶體，而head又是這段記憶體的唯一指向，這樣一來就會導緻head原來指向的這塊記憶體無法再通路，這也就導緻了記憶體洩漏。(記憶體洩漏可以正常通過編譯，要用專門的工具才能檢測出來)是以在複制前清空的操作是很重要的！！！

是以，要養成一個良好的程式設計習慣：在給指針指派的時候，要考慮是否會導緻原有指針指向的記憶體洩漏！

4.stringstream的問題 

std::stringstream ss;

ss.clear()與ss.str(“”)

ss.clear()起到重置的作用，ss.str(“”)起到清空的作用。注意，clear不是清空的意思!!!

(1)當進行多次轉化時(<<與>>成對使用時)，在每次轉化之後都要用ss.clear()進行重置；

(2)但是如果在多進行多次轉化時，<<與>>不成對使用，而是用ss.str()等函數直接進行類型轉化時，在每次轉化後都要用ss.str(“”)進行清空。

我的代碼如下：

5.連結清單的插入與删除

這部分知識可以看我以前寫的博文：連結清單的入門

但是那個畢竟是我剛入門時寫的，方法可能比較麻煩，但是還是很容易了解的。而我在最後展示的代碼裡采用了更為精簡的方法來實作插入與删除操作，如果有興趣可以看一下。

6.連結清單的排序

在沒有時間的限制下，我們可以将連結清單内的資料存儲到數組中，再對數組進行排序，然後再将數組内的值重新複制到連結清單中即可。這種方法思維量較小，可以節省不少時間。

以下便是我這道題的代碼：

# include "list.hpp"
# include <string>
# include <sstream>

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

list :: list(const list& list1) {
    head = NULL;
    _size = ;
    *this = list1;
}

list& list :: operator=(const list& list1) {
    clear();   // 十分重要！！！
    _size = list1._size;
    if (list1.head == NULL) {
        head = NULL;
        _size = ;
    } else {
        head = new node(list1.head->data);
        node *p1 = head;
        node *p2 = list1.head->next;
        int num = ;
        while (num < list1._size) {
            p1->next = new node(p2->data); // 此處調用了node的構造函數而不是起到指派的作用 
            p2 = p2->next;
            p1 = p1->next;
            num++;
        }
        p1->next = NULL;
    }
    return *this;
}

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

bool list :: empty(void) const {
    return _size ? false : true;
}

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

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

void list :: insert(int position, const int& data) {
    if (position >=  && position <= _size) {  // 注意排除不符合情況的position
        if (position == ) {
            node *p1 = new node(data);
            p1->next = head;
            head = p1;
            _size++;
        } else {
            node *p1 = head;
            position--;
            while (position--) {
                p1 = p1->next;
            }
            node *p2 = new node(data);
            p2->next = p1->next;
            p1->next = p2;
            _size++;
        }
    }
}

void list :: erase(int position) {
    if (position >=  && position < _size) {
        if (position == ) {
            node *p1 = head->next;
            delete head;
            head = p1;
            _size--;
        } else {
            position--;
            node *p1 = head;
            while (position--) {
                p1 = p1->next;
            }
            node *p2 = p1->next;
            p1->next = p2->next;
            delete p2;
            _size--;
        }
    }
}

list& list :: sort(void) {  // 這裡用了冒泡排序
    node *p1 = head;
    int *arr = new int[_size];
    int i = ;
    while (p1 != NULL) {
        arr[i] = p1->data;
        i++;
        p1 = p1->next;
    }
    for (int j = ; j < _size-; j++) {
        for (int k = ; k < _size--j; k++) {
            int temp;
            if (arr[k] > arr[k+]) {
                temp = arr[k];
                arr[k] = arr[k+];
                arr[k+] = temp;
            }
        }
    }
    p1 = head;
    i = ;
    while (p1 != NULL) {
        p1->data = arr[i];
        p1 = p1->next;
        i++;
    }
    delete[] arr;
    return *this;
}

以上内容皆為本人觀點，歡迎大家提出批評和指導，我們一起探讨！

c++ gdb 連結清單 記憶體洩漏 深複制
上一篇: 單向連結清單的實作C++
下一篇: C++ 單向連結清單

繼續閱讀