這一周的實驗題比較水，我就不總結了，而作業題中最有意思的就是實現雙向鏈表這一道題。
這道題和我們之前做的單向鏈表是同一種類型的，只是這一次是雙向鏈表，需要實現的操作較多，可能產生的bug也比之前多。我個人覺得，打出這道題的代碼不難，難是難在調試。
(入門鏈表的可以參照我以前的一篇文檔入門：鏈表的基本操作)
題目如下：(Author: 葉嘉祺(TA))
Introduction
Well, this time we will be a little difficult for you to do. We are going to design a link list class in c++. Again, the knowledge of pointer in c++ in widely used this time and you have to focus when you are coding. List is not easy for you.
Knowledge
This time, you are going to finish a advanced list which is known as doubly linked list. Each node of the list have three members: data which is use as the real storage, next pointer which is used to linked the next node of the list, prev pointer which is use to linked the previous node.
Requirements
Finish the member functions below.
Notice that for output functions, the format is as below:
toString() [1,2,3,4,5]
NULL<-1<->2<->3<->4<->5->NULL
toString() []
NULL
toString() [1]
NULL<-1->NULL
No new line is needed;
void split(int position, list* des1, list* dest2) 2 [1,2,3,4]
[1,2] [3,4]
list& merge(const list& src1, const list& src2) [1,2,3,4] [5,6,7,8]
[1,2,3,4,5,6,7,8]
list& remove_if(bool (*condition)(listPointer)); [1,2,3,4,5,6] condition = odd number
[2,4,6]
list& unique(void) [1,2,2,3,4,4,5,6]
[1,2,3,4,5,6]
list& reverse(void) [1,2,3,4,5,6]
[6,5,4,3,2,1]
下面是雙向鏈表的簡要模型：
![雙向鏈表](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012112161962.png "\")
題目的main.cpp 與 List.hpp 已經給出。
// main.cpp
#include "List.hpp"
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::string;
bool condition1(list::listPointer p) { return true; }
bool condition2(list::listPointer p) {
if (p->data % 2 == 0) {
return false;
}
return true;
}
bool condition3(list::listPointer p) {
if (p->data > 5) {
return false;
}
return true;
}
void outputList(const list& li) {
cout << li << " size:" << li.size();
if (&li.front() == NULL) {
cout << " front:NULL";
} else {
cout << " front:" << li.front();
}
if (&li.back() == NULL) {
cout << " back:NULL";
} else {
cout << " back:" << li.back();
}
cout << endl;
}
int main() {
int n, m;
cin >> n >> m;
int* a = new int[n]();
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (true) {
list li1(a, n);
li1.insert(2, 111);
li1.push_front(150);
list li2(li1);
outputList(li1);
outputList(li2);
}
cout << endl;
if (true) {
list li1;
for (int i = 0; i < n; i++) {
li1.insert(i, a[i]);
}
for (int i = 0; i < m; i++) {
li1.erase(i);
}
outputList(li1);
}
cout << endl;
if (true) {
list li1(a, n), li2, li3;
li1 = li2 = li3 = li1;
outputList(li1);
li1.split(0, &li2, &li3);
outputList(li1);
outputList(li2);
outputList(li3);
li1.split(li1.size(), &li2, &li3);
outputList(li1);
outputList(li2);
outputList(li3);
li1.split(li1.size() / 2, &li2, &li3);
cout << li2.toString() << endl;
cout << li3.toString() << endl;
li1 += (li2 += li1).merge(li1, li1);
outputList(li1);
li1 += li3;
li2.merge(li1, li3);
for (int i = 0; i < li1.size(); i++) {
cout << li1[i] << " ";
}
cout << endl;
outputList(li2);
}
cout << endl;
cout << endl;
if (true) {
list li1(a, n);
li1.remove_if(condition1);
cout << li1 << " " << endl;
li1.assign(a, n);
li1.remove_if(condition2);
cout << li1 << endl;
li1.assign(a, n);
li1.remove_if(condition3);
outputList(li1);
}
cout << endl;
if (true) {
list li(a, n);
li.merge(li, li).merge(li, li).unique();
outputList(li);
}
delete[] a;
return 0;
}
// list.hpp
#ifndef LIST
#define LIST
#include
#include
class list {
public:
typedef int data_type;
struct node {
public:
data_type data;
node* next;
node* prev;
node(data_type data = 0, node* next = NULL, node* prev = NULL)
: data(data), next(next), prev(prev){};
};
typedef node listNode;
typedef node* listPointer;
typedef unsigned int size_type;
private:
listPointer head;
listPointer tail;
size_type _size;
inline listPointer at(int index) {
if (index >= 0 && index < this->_size) {
if (index <= this->_size / 2) {
int counter = 0;
listPointer p = this->head;
while (counter != index) {
counter++;
p = p->next;
}
return p;
} else {
int counter = 0;
listPointer p = this->tail;
while (counter != this->_size - 1 - index) {
counter++;
p = p->prev;
}
return p;
}
}
return NULL;
}
public:
list();
// construct a list from an exist array
list(const data_type[], int length);
list(const list&);
list& operator=(const list&);
~list();
// Capacity
bool empty(void) const;
size_type size(void) const;
// Element access
data_type& front(void) const;
data_type& back(void) const;
public:
// output
std::string toString(void) const;
// Modifiers
void assign(const list&);
void assign(const data_type datas[], int length);
void push_front(const data_type&);
void push_back(const data_type&);
void pop_front(void);
void pop_back(void);
void insert(int position, const data_type& data);
void erase(int position);
void clear(void);
// Operations
// split this list into to lists at the given position
void split(int position, list* des1, list* dest2);
// merge two list to this list from src1 and src2
list& merge(const list& src1, const list& src2);
// remove the elements who satisfy the condition
list& remove_if(bool (*condition)(listPointer));
// remove duplicate elements
list& unique(void);
// reverse the list
list& reverse(void);
// operators
data_type& operator[](int index);
list& operator+=(const list&);
friend std::ostream& operator<<(std::ostream& os, const list& li);
};
#endif
因為實現這些操作不難，況且有些操作在16.03.04實驗課總結是類似的，我就不詳細一一介紹了。下面就簡單地介紹split, merge, remove_if, unique, reverse操作.
split操作指將鏈表根據輸入的position拆成兩段，這個很簡單，就用一個外層的while循環對原鏈表進行遍歷，然後在內部弄兩個小的while循環形成兩段目標鏈表。
merge操作指將兩段鏈表連接在一起，這個很簡單，就將其中一個鏈表復制給原鏈表，然後再通過push_back操作將第二個鏈表的內容壓入。
remove_if這個有點小難度，很容易導致內存錯誤。傳入remove_if的參數是一個函數指針，如bool (*condition)(listPointer)就是定義一個函數指針，其中bool是函數的返回類型，condition是指針的名字，listPointer是指傳入參數的類型。那麼通過函數指針來調用函數的操作如下：
// listPointer是用typedef定義的指向鏈表結點的指針類型
listPointer p1;
if ((*condition)(p1)) {}
也就是說，在(*condition)()的括號裡加入我們傳入的參數就可以調用這個函數了。
remove_if是對鏈表中各個結點進行檢測的，如若不滿足條件就刪去。因此在遍歷時，要用一個“中介”指針去存儲遍歷指針指向的對象的下一個結點，然後在執行完if ((*condition)(p1)) 後再將“中介”指針裡的內容賦給遍歷指針。原因是遍歷指針指向的對象可能已經被刪除了，因此不能訪問。
unique操作也是要注意的，你的程序會不會超時取決於這個操作的實現。我起初想到的方法是將鏈表裡的內容存到數組裡，然後對數組進行操作(畢竟對數組的操作比較熟悉)，後來發現有一組測試樣例超時了，於是我就改進了我的代碼，把數組去了，然後直接對鏈表進行操作。其實很簡單，就是用一個外層的while循環遍歷數組裡的內容，然後在弄一個內層的while循環遍歷之前的內容，如果沒有重復，就將遍歷到的對象儲存在一個新的鏈表裡。
最後是reverse操作,我發現標程寫的挺麻煩的，直接把head與tail的內容交換不久可以了麼。
好的，下面開始講解我debug的內容。
1.構造函數
我此處強調的是帶有參數的構造函數，這類函數往往很容易忘記給類成員進行初始化。
例子1:
list :: list(const data_type a[], int length);
這是一個帶有參數的構造函數。在實現將數組內容輸入鏈表之前，最好對類的成員進行初始化。如這個函數沒有先對成員函數size置0，那麼用size++就會造成內存非法訪問。再如沒有在一開始對頭指針與尾指針置空，那麼當輸入數組的長度為0時，將不執行數組內容輸入鏈表的操作，便會導致類成員沒有被初始化，在接下來的代碼中將有可能會引發錯誤。
例子2:
list :: list(const list& list) {
head = tail = NULL;
_size = 0;
*this = list;
}
list& list :: operator=(const list& list) {
clear();
head = tail = NULL;
_size = 0;
if (list.head != NULL) {
head = new listNode(list.head->data);
_size++;
listPointer p1 = head;
listPointer p2 = list.head->next;
tail = head;
while (_size < list._size) {
p1->next = new listNode(p2->data);
p1->next->prev = p1;
p1 = p1->next;
p2 = p2->next;
_size++;
if (_size == list._size) {
tail = p1;
}
}
}
return *this;
}
void list :: clear(void) {
if (head != NULL) {
listPointer p1;
while (head != NULL) {
p1 = head->next;
delete head;
head = p1;
}
}
}
這是一個復制構造函數，根據重載的”=”實現類的對象的復制。但是這裡也是要注意要在一開始給類的成員初始化。我們可以看重載”=”的代碼，在我上一篇寫鏈表的文章裡我有提到，實現賦值之前要將原鏈表指向的內存清空。好的，那我們現在來看clear()函數。不難發現clear不會對頭指針為空的鏈表進行內存釋放，也就是說如若在復制構造函數中沒有提前初始化成員，會導致head不為NULL，會執行clear()操作，而顯然這個鏈表對象中並沒有動態內存可以釋放，所以會引發錯誤。
2.尾指針的問題
對於初學者來說，接觸到的鏈表大多數是單向鏈表，所以在寫雙向鏈表時很容易采用單向鏈表的思想從而忽略了一些小細節。如尾指針的復制。在單向鏈表中，我們只給頭指針復制，而在雙向鏈表中，我們不僅要考慮頭指針，還要考慮尾指針。也就是說，當鏈表建立完畢以後，不要忘了將最後一個結點的地址賦給尾指針。如果沒有給尾指針賦值，會導致鏈表長度計算錯誤以及棧溢出等後果。
3.push_back操作要考慮鏈表為空的情況
push_back操作是指在鏈表末端增加結點。這個操作比較容易忽略的就是沒有考慮鏈表為空的情況。這個情況很重要，因為我們可以通過不斷調用push_back來實現數據輸入鏈表，所以一定要記得考慮鏈表為空的情況。
與此同時，push_front,pop_front, pop_back也要記得考慮鏈表為空的情況，雖然有些操作不考慮鏈表為空的操作不會出錯，但是為了使代碼更加“天衣無縫”，還是要把一些可能使程序崩潰的情況考慮下去。
4.插入與刪除操作
插入與刪除操作都有傳入一個代表位置的參數，我們要先對這個參數進行判斷，判斷其是否合法。對於插入操作，其插入的位置參數必須大於等於0且小於等於鏈表的大小。而對於刪除操作，其刪除的位置參數必須大於等於0且小於鏈表的大小(注意一個是小於等於一個是小於)。
5.merge操作
對於merge操作有一點要注意，其傳入的參數可以是自己。一般來說，調用成員函數將兩個鏈表連接起來賦值到該成員之前要先清空原成員鏈表中的內容以避免內存洩漏，但是此處不同，因為傳入的參數是本身，倘若先清空，便會導致傳入的兩個參數也變成空鏈表，最終連接的結果就是一個空鏈表，這顯然是錯誤的。因此在這裡應該再定義一個list對象來存儲鏈表連接的結果，然後再用”＝”賦值給原成員的鏈表(“=”會先清空原成員的鏈表裡的內容)。
6.if_remove操作
這個在前文我已經講解過了，所以就這樣代過了。
7.unique操作超時
這個在前文我已經講解過了，所以就這樣代過了。
我的代碼還有可以簡化的地方：
1.重載[]運算符時可以用已經定義的at函數，沒有必要自己去定義；
2.重載+=運算符時可以用merge函數，沒有必要自己去定義。
3._size置0與頭指針尾指針置空可以放到clear函數裡。
以上三點就是我覺得我的代碼裡還可以簡化的地方。
至於我的代碼，等到harddue過了我再放上來吧，免得被抄襲然後就完蛋了…
以上內容皆為本人觀點，歡迎大家提出批評和指導，我們一起探討！
