本文將通過(15 C++ Homework) D&A 5 Collection with Inheritance來講解一些重要的排序與零散的知識。對抽象類中析構函數的調用情況進行了分類討論並一一試驗，最終得出了“抽象類最好要定義純虛析構函數”的結論。
![類關系圖](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012112091393.png "\")
其實出題人的意思很簡單，就是希望你用代碼實現這張圖中部分的內容(有方框的)。
現在我來簡單的分析一下這張圖(只介紹帶有大方框的)。
1.直線加圓圈對應的方框是指提供接口的類，換句話說就是抽象類。
由圖可知，Collection 與 List 是抽象類。
2.直線加空心三角形表達的是繼承關系。
由圖可知，List繼承Collection，ArrayList與Linked List繼承List。
3.直線加實心菱形代表的是被包含於。
由圖可知，結構體node在Linked List中定義。
本題考查的知識點清單如下：
繼承、成員函數的純虛函數、析構函數的純虛函數、抽象類、接口、預處理指令在頭文件中的應用、數據結構(數組與鏈表)的各種操作、快速排序、歸並排序、動態內存的分配與釋放、多態等。
這裡再重復一下C++中很重要的三個部分：
1.encapsulation(封裝)；2.inheritance(繼承)； 3.polymorphism(多態)。
（1）接口：
接口方便了基類的指針訪問派生類的成員函數。成員函數一般都要定義成純虛函數(除了構造函數)，因此它們一般都是抽象類。而且接口類一般只提供接口，不提供實現，所以定義純虛析構函數時不能用virtual 函數原型 ＝ 0;的格式，而要用virtual ~類名 {}。但這並不意味著析構函數就不能用virtual 函數原型 ＝ 0;的格式，當類包含實現時，如若在類的定義裡用virtual ~類名 ＝ 0;的格式，那麼在實現中要重新定義析構函數。對於其他成員函數(除構造函數)，用virtual 函數原型 ＝ 0;的格式就行了。因為這些成員函數只提供接口，並不會調用，而抽象類雖然沒有實例化對象，但是仍然會在刪除子對象時調用抽象類的析構函數。
（2）純虛析構函數
注：正如上面所說，抽象類的析構函數一定需要實現。所以我認為虛析構函數與純虛析構函數應該是同一個概念，沒什麼區別。
對於一個抽象類，最好要定義純虛析構函數(這個觀點網上有爭議，不過我個人更傾向於定義純虛析構函數)，雖然並不是必要的，但定義了肯定是最好的了。我的理由如下：
定義一個抽象類，一般是用於提供接口，以方便基類指針訪問派生類中的成員。好，現在我分成兩種情況來生成派生類對象，並用一些小代碼來展現它們各自的析構函數的調用情況。
I.通過基類指針動態分配內存生成派生類對象；
———————————————-實例一————————————————–
# include
using namespace std;
class Base {
public:
virtual void funA() = 0;
~Base() {
cout << "Calling for Base's destruction!\n";
}
};
class Derived : public Base {
public:
void funA() {}
~Derived() {
cout << "Calling for Derived's destruction\n";
}
};
int main(void) {
Base *p1 = new Derived;
delete p1;
// Derived A;
return 0;
}
輸出結果：
Calling for Base's destruction!
從代碼的輸出結果不難發現，如果通過基類指針動態分配內存生成派生類對象，當刪去對象時，只會調用基類也就是抽象類的析構函數。
如果將析構函數變成純虛析構函數呢？
———————————————-實例二————————————————–
# include
using namespace std;
class Base {
public:
virtual void funA() = 0;
virtual ~Base() {
cout << "Calling for Base's destruction!\n";
}
};
class Derived : public Base {
public:
void funA() {}
~Derived() {
cout << "Calling for Derived's destruction\n";
}
};
int main(void) {
Base *p1 = new Derived;
delete p1;
// Derived A;
return 0;
}
輸出結果：
Calling for Derived's destruction
Calling for Base's destruction!
從輸出結果可以得出結論：
通過基類指針動態分配內存生成派生類對象時，如若沒有定義純虛析構函數，那麼只會調用基類的析構函數；如若定義了純虛析構函數，不僅會調用派生類的析構函數，還會調用基類的析構函數(所以析構函數需要實現，否則會編譯出錯)。
那麼對於積累是非抽象類的呢？情況如何？讀者可以試一下～
而我實驗的結果是無論基類是抽象類還是普通類，都滿足上面的結論。
II.通過數據類型＋變量名的方式生成派生類對象。
———————————————-實例三————————————————–
# include
using namespace std;
class Base {
public:
virtual void funA() = 0;
~Base() {
cout << "Calling for Base's destruction!\n";
}
};
class Derived : public Base {
public:
void funA() {}
~Derived() {
cout << "Calling for Derived's destruction\n";
}
};
int main(void) {
// Base *p1 = new Derived;
// delete p1;
Derived A;
return 0;
}
輸出結果：
Calling for Derived's destruction
Calling for Base's destruction!
改成純虛析構函數試試～
———————————————-實例四————————————————–
# include
using namespace std;
class Base {
public:
virtual void funA() = 0;
virtual ~Base() {
cout << "Calling for Base's destruction!\n";
}
};
class Derived : public Base {
public:
void funA() {}
~Derived() {
cout << "Calling for Derived's destruction\n";
}
};
int main(void) {
// Base *p1 = new Derived;
// delete p1;
Derived A;
return 0;
}
輸出結果：
Calling for Derived's destruction
Calling for Base's destruction!
從輸出結果可以得出結論：
如果通過數據類型＋變量名的方式生成派生類對象，那麼此時有無定義純虛析構函數就沒有太大的關系了（也許這就是網上的人認為抽象類不用定義純虛析構函數的原因)。
總而言之，由上面的試驗可知，定義純虛構造函數還是比較好的，比較適用於兩種生成對象的方法。
（3）重定義問題
在一項比較大的工程內，或者是比較復雜的代碼題內，可能會出現多個文件調用同一個頭文件的情況，這便會導致代碼重定義問題。為了解決這一問題，我們需要在頭文件中加入一些預編譯指令來防止此類情況的發生。
如頭文件List.hpp:
#ifndef LIST_H_
#define LIST_H_
class List : public Collection {
(content)
};
#endif
在該頭文件中，我加入了以下語句：
#ifndef LIST_H_
#define LIST_H_
#endif
如果這個頭文件還沒有被include，那麼也就沒有定義LIST_H_常量。
於是便會執行#ifndef與#endif之間的代碼，其中便定義了LIST_H_常量。
假如這個這個頭文件已經被include了，那麼就一定定義了LIST_H_ 常量，那麼也就不會執行#ifndef與#endif之間的代碼，也就不會造成重定義的情況。
於是，為保險起見，最好頭文件都加上這三句預編譯指令。
（4）要自己實現快排，鏈表，數組，不能調用STL。
(1)對於快排的實現，我就不細講了，挺簡單的。可以看我以前的一篇文章學習：快速排序
(2)對於歸並，只要了解了它的算法，我們自己就能實現！
![歸並排序](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012112091353.png "\")
推薦一篇博文：
遞歸算法學習系列二：歸並排序
這篇博文我只推薦他對歸並排序算法的講解，但我並不推薦他的代碼。畢竟他用的是數組的歸並排序，顯然就沒快排快了。我們所要做的就是根據歸並排序的算法用鏈表加以實現！
用鏈表實現歸並排序的代碼我會在後文給出。
題目已給出main.cpp, ArrayList.hpp,LinkedList.hpp,要求我們實現Collection.hpp, List.hpp, ArrayList.cpp, LinkedList.cpp。
// main.cpp
#include
#include
#include "Collection.hpp"
#include "List.hpp"
#include "LinkedList.hpp"
#include "ArrayList.hpp"
#include
using std::cin;
using std::cout;
using std::endl;
using std::exception;
class AlgorithmnForbidden : public exception {
virtual const char *what() const throw() {
return "Please do not use std::sort or std::list or std::vector .....";
}
};
class TEST {
private:
int *testData;
int data_size;
public:
TEST() {
#if defined(_GLIBCXX_ALGORITHM) || defined(_GLIBCXX_LIST) || \
defined(_GLIBCXX_VECTOR)
//throw AlgorithmnForbidden();
cout << "please do not use algorithm" << endl;
#endif
cin >> data_size;
cout << "test data size:" << data_size << endl;
testData = new int[data_size];
for (int i = 0; i < data_size; i++) {
cin >> testData[i];
}
}
~TEST() { delete[] testData; }
void test_List(Collection *c) {
cout << (c->isEmpty() ? "true" : "false") << endl;
int n = data_size;
for (int i = 0; i < n; i++) {
c->add(testData[i]);
}
reinterpret_cast(c)->sort();
for (int i = 0; i < n; i++) {
cout << (*reinterpret_cast(c))[i] << " ";
}
cout << endl;
// not empty
cout << (c->isEmpty() ? "true" : "false") << endl;
for (int i = 0; i < n / 2; i++) {
cout << "(" << (c->contain(i) ? "true" : "false");
cout << ","
<< (reinterpret_cast(c)->indexOf(i) != -1 ? "true" : "false")
<< ") ";
c->remove(i);
}
cout << endl;
for (int i = 0; i < c->size(); i++) {
cout << (*reinterpret_cast(c))[i] << " ";
}
cout << endl;
}
void test_ArrayList() {
Collection *c = new ArrayList();
test_List(c);
delete c;
}
void test_LinkedList() {
Collection *c = new LinkedList();
test_List(c);
delete c;
}
void runAllTests() {
cout << "Testing ArrayList:" << endl;
test_ArrayList();
cout << endl;
cout << "Testing LinkedList:" << endl;
test_LinkedList();
}
};
int main() {
TEST t;
t.runAllTests();
return 0;
}
// ArrayList.hpp
#ifndef ARRAYLIST_H_
#define ARRAYLIST_H_
#include "List.hpp"
class ArrayList : public List {
public:
ArrayList();
~ArrayList();
virtual void add(E e);
virtual void clear(void);
virtual bool contain(E e);
virtual bool isEmpty(void);
virtual void remove(E e);
virtual E& operator[](int index);
virtual E& get(int index);
virtual int indexOf(E element);
virtual void sort(void);
virtual int size(void);
private:
E* storage;
int _size;
int _maxsize;
static const int extend_factor = 2;
void extend(void);
};
#endif
// LinkList.hpp
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "List.hpp"
#include
class LinkedList : public List {
public:
typedef struct node {
E data;
struct node* next;
struct node* prev;
node(E data, struct node* next = NULL, struct node* prev = NULL)
: data(data), next(next), prev(prev) {}
} node;
LinkedList();
~LinkedList();
virtual void add(E e);
virtual void clear(void);
virtual bool contain(E e);
virtual bool isEmpty(void);
virtual void remove(E e);
virtual E& operator[](int index);
virtual E& get(int index);
virtual int indexOf(E element);
virtual void sort(void);
virtual int size(void);
private:
node* head;
node* tail;
int _size;
};
#endif
對於Collection.hpp，根據最開始給出的那個圖中對應方框內的內容進行定義。
#ifndef COLLECTION_H_
#define COLLECTION_H_
class Collection {
protected:
typedef int E;
public:
virtual ~Collection() {} // 一定要加上virtual
virtual void add(E e) = 0;
virtual void clear(void) = 0;
virtual bool contain(E e) = 0;
virtual bool isEmpty(void) = 0;
virtual void remove(E e) = 0;
virtual int size(void) = 0;
};
#endif
對於List.hpp，也是如圖中對應方框的內容進行定義。
#ifndef LIST_H_
#define LIST_H_
# include "Collection.hpp"
class List : public Collection {
public:
virtual ~List() {} // 一定要加上virtual
virtual E& operator[](int index) = 0;
virtual E& get(int index) = 0;
virtual int indexOf(E element) = 0;
virtual void sort(void) = 0;
};
#endif
（1）ArrayList.cpp
對於ArrayList.cpp的實現，其實類似於實現vector類，因為這個array有extend的功能。
除了排序，我覺得需要有點小思維的就是remove函數。不難想到最普通的方法就是從頭到尾遍歷數組，除去相同元素，並且實現相同元素後面元素的前移。
但是我有一個更快，更巧的方法。由main.cpp可知, 在調用remove()函數之前，數組內的元素已經排完序，並且remove的數字是從小到大的。不難想到，它只會在數組的一端刪去相同元素。所以我先將整個數組給倒過來，然後從後往前遍歷。如果遍歷到要刪除的元素，直接_size–即可，因為只會從尾端刪除元素，故不用考慮刪除中間元素的情況。我的ArrayList::remove()是這樣實現的。其實我的代碼還可以改進，先判斷最後一個元素是否是我們要刪除的元素，如果不是，就不執行遍歷，如果是，就執行遍歷。還有再縮短時間的方法，就是加一個循環終止調節，這個條件可以是判斷相鄰元素是否都是我們要刪除的元素。最後要將數組倒回來！！！不必調用quick_sort()函數。
extend()函數也是挺有意思。不過要注意分情況。如果storage為NULL，那就直接分配內存給它；如果不為空，要在分配內存之後將原數組中的數據復制到新內存中，然後把原數組的空間delete，以避免內存洩漏。
// ArrayList.cpp
# include "ArrayList.hpp"
# include
static int a = 0;
void quick_sort(int *pArr, int pbig, int psmall) {
if (pbig >= psmall) return;
int key = pbig;
int len = psmall + 1;
while (pbig != psmall) {
for (; psmall > pbig; psmall--) {
if (pArr[key] > pArr[psmall]) break;
}
for (; pbig < len; pbig++) {
if (pbig == psmall) {
int temp = pArr[key];
pArr[key] = pArr[psmall];
pArr[psmall] = temp;
break;
}
if (pArr[key] < pArr[pbig]) break;
}
if (pbig != psmall) {
int temp = pArr[psmall];
pArr[psmall] = pArr[pbig];
pArr[pbig] = temp;
}
}
quick_sort(pArr, key, pbig-1);
quick_sort(pArr, pbig+1, len-1);
}
ArrayList :: ArrayList() : _size(0), _maxsize(0), storage(NULL) {}
ArrayList :: ~ArrayList() { clear(); }
void ArrayList :: add(ArrayList::E e) {
if (_size == _maxsize) extend();
storage[_size] = e;
_size++;
}
void ArrayList :: clear(void) {
if (storage != NULL) delete[] storage;
storage = NULL;
_size = 0;
_maxsize = 0;
}
bool ArrayList :: contain(ArrayList::E e) {
for (int i = 0; i < _size; i++) {
if (storage[i] == e) return true;
}
return false;
}
bool ArrayList :: isEmpty(void) {
if (_size == 0) return true;
return false;
}
void ArrayList :: remove(ArrayList::E e) {
static int b = _size;
a++;
if (a == 1) {
for (int i = 0, j = _size-1; i < j; i++, j--) {
int temp = storage[i];
storage[i] = storage[j];
storage[j] = temp;
}
}
for (int i = _size-1; i >= 0; i--) {
if (storage[i] == e) _size--;
}
if (a == b/2) {
for (int i = 0, j = _size-1; i < j; i++, j--) {
int temp = storage[i];
storage[i] = storage[j];
storage[j] = temp;
}
}
}
ArrayList::E& ArrayList :: operator[](int index) { return storage[index]; }
ArrayList::E& ArrayList :: get(int index) { return storage[index]; }
int ArrayList :: indexOf(ArrayList::E element) {
for (int i = 0; i < _size; i++) {
if (storage[i] == element) return i;
}
return -1;
}
void ArrayList :: sort(void) {
if (storage != NULL) {
quick_sort(storage, 0, _size-1);
}
}
int ArrayList :: size(void) { return _size;}
void ArrayList :: extend(void) {
_maxsize += extend_factor;
if (storage == NULL) {
storage = new E[_maxsize];
} else {
E* pArr = new E[_maxsize];
pArr[_size] = pArr[_size+1] = 0;
for (int i = 0; i < _size; i++) {
pArr[i] = storage[i];
}
delete[] storage;
storage = pArr;
}
}
(2) Linkedlist.cpp
除了排序，我覺得remove()函數的實現需要點小思維。
不過鏈表的remove()函數實現比數組簡單多了，因為這個鏈表是雙向鏈表，操作起來較為方便。(雙向鏈表的詳細實現詳見：實現雙向鏈表， 單向鏈表的詳細實現相見：16.03.11實驗課總結， 單向鏈表入門：入門：鏈表的基本操作)
因為只會從一端刪除元素，所以我們只需對鏈表進行遍歷。循環中只需判斷第一個結點中的數據是否等於我們要刪除的，如果是，刪除第一個結點，如果不是，直接break來終止循環。此處已經有了循環終止條件，就沒有必要再設置一個新的了。
下面上LinkedList.cpp，重點在歸並排序！
// LinkedList.cpp
# include "LinkedList.hpp"
static int a = 0;
void merge_sort(LinkedList::node** head, int _size) {
if (*head == NULL || (*head)->next == NULL) return;
int count = 1;
LinkedList::node *p1 = *head;
while (p1 != NULL) {
if (count == _size/2) break;
p1 = p1->next;
count++;
}
LinkedList::node *p2 = p1->next;
p1->next = NULL;
p2->prev = NULL;
merge_sort(head, count);
merge_sort(&p2, _size-count);
LinkedList::node *p3 = *head;
LinkedList::node *p4 = p2;
LinkedList::node *merge_list = new LinkedList::node(0);
LinkedList::node *p5 = merge_list;
int size = 1;
while (size < _size) {
p5->next = new LinkedList::node(0);
p5->next->prev = p5;
size++;
p5 = p5->next;
}
p5 = merge_list;
while (p3 != NULL && p4 != NULL) {
if (p3->data > p4->data) {
p5->data = p4->data;
p4 = p4->next;
} else {
p5->data = p3->data;
p3 = p3->next;
}
p5 = p5->next;
}
if (p3 == NULL) {
while (p5 != NULL) {
p5->data = p4->data;
p5 = p5->next;
p4 = p4->next;
}
} else if (p4 == NULL) {
while (p5 != NULL) {
p5->data = p3->data;
p5 = p5->next;
p3 = p3->next;
}
}
while (*head != NULL) {
LinkedList::node *p6 = (*head)->next;
delete (*head);
*head = p6;
}
while (p2 != NULL) {
LinkedList::node *p7 = p2->next;
delete p2;
p2 = p7;
}
*head = merge_list;
}
LinkedList :: LinkedList() : head(NULL), tail(NULL), _size(0) {}
LinkedList :: ~LinkedList() { clear(); }
void LinkedList :: add(LinkedList::E e) {
node *p1 = new node(e);
if (head == NULL) {
head = tail = p1;
} else {
tail->next = p1;
p1->prev = tail;
tail = p1;
}
_size++;
}
void LinkedList :: clear(void) {
if (head != NULL) {
node *p1;
while (head != NULL) {
p1 = head->next;
delete head;
head = p1;
}
}
_size = 0;
head = tail = NULL;
}
bool LinkedList :: contain(LinkedList::E e) {
node *p1 = head;
while (p1 != NULL) {
if (e == p1->data) return true;
p1 = p1->next;
}
return false;
}
bool LinkedList :: isEmpty(void) {
if (_size == 0) return true;
return false;
}
void LinkedList :: remove(LinkedList::E e) {
while (head != NULL) {
if (head->data == e) {
node *temp = head;
head = head->next;
head->prev = NULL;
delete temp;
_size--;
} else {
break;
}
}
}
LinkedList::E& LinkedList :: operator[](int index) {
node *p1 = head;
while (index--) {
p1 = p1->next;
}
return p1->data;
}
LinkedList::E& LinkedList :: get(int index) {
return (*this)[index];
}
int LinkedList :: indexOf(LinkedList::E element) {
node *p1 = head;
int count = 0;
int flag = 0;
while (p1 != NULL) {
if (p1->data == element) {
flag = 1;
break;
}
count++;
p1 = p1->next;
}
if (flag == 1) return count;
else return -1;
}
void LinkedList :: sort(void) {
if (head == NULL) return;
merge_sort(&head, _size);
int count = 1;
node *p1 = head;
while (count < _size) {
p1 = p1->next;
count++;
}
tail = p1;
}
int LinkedList :: size(void) { return _size; }
True object-orient programming requires objects to support three qualities: encapsulation, inheritance, and polymorphism.Polymorphism enables one common interface for many implementations, and for objects to act differently under different circumstances.
C++ supports several kinds of static (compile-time) and dynamic (run-time) polymorphisms, supported by the language features described above. Compile-time polymorphism does not allow for certain run-time decisions, while run-time polymorphism typically incurs a performance penalty.
Static polymorphism is not true polymorphism including function overloading, operator overloading and templates which is not what we are going to work on(in this question).
Dynamic polymorphism:
Variable pointers (and references) to a base class type in C++ can refer to objects of any derived classes of that type in addition to objects exactly matching the variable type. This allows arrays and other kinds of containers to hold pointers to objects of differing types. Because assignment of values to variables usually occurs at run-time, this is necessarily a run-time phenomenon.
C++ also provides a dynamic_cast operator, which allows the program to safely attempt conversion of an object into an object of a more specific object type (as opposed to conversion to a more general type, which is always allowed). This feature relies on run-time type information (RTTI). Objects known to be of a certain specific type can also be cast to that type with static_cast, a purely compile-time construct that has no runtime overhead and does not require RTTI.
Ordinarily, when a function in a derived class overrides a function in a base class, the function to call is determined by the type of the object. A given function is overridden when there exists no difference in the number or type of parameters between two or more definitions of that function. Hence, at compile time, it may not be possible to determine the type of the object and therefore the correct function to call, given only a base class pointer; the decision is therefore put off until runtime. This is called dynamic dispatch. Virtual member functions or methods[43] allow the most specific implementation of the function to be called, according to the actual run-time type of the object. In C++ implementations, this is commonly done using virtual function tables. If the object type is known, this may be bypassed by prepending a fully qualified class name before the function call, but in general calls to virtual functions are resolved at run time.
In addition to standard member functions, operator overloads and destructors can be virtual. As a rule of thumb, if any function in the class is virtual, the destructor should be as well. (此處表示應該使用虛析構函數，沒有強制)As the type of an object at its creation is known at compile time, constructors, and by extension copy constructors, cannot be virtual. Nonetheless a situation may arise where a copy of an object needs to be created when a pointer to a derived object is passed as a pointer to a base object. In such a case, a common solution is to create a clone() (or similar) virtual function that creates and returns a copy of the derived class when called.
A member function can also be made “pure virtual” by appending it with = 0 after the closing parenthesis and before the semicolon. A class containing a pure virtual function is called an abstract data type. Objects cannot be created from abstract data types; they can only be derived from. Any derived class inherits the virtual function as pure and must provide a non-pure definition of it (and all other pure virtual functions) before objects of the derived class can be created. A program that attempts to create an object of a class with a pure virtual member function or inherited pure virtual member function is ill-formed.
