利用链表ADT学习C++面向对象(1) - 基础知识

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

template <typename T>
class LinkedList
{
protected:
    void init() {}      //私有初始化函数
    struct Node{}       //链节点
    int ListSize;       //链长度
    Node* head;         //头指针
    Node* locate(int index);                      //简易迭代器
    Node* begin_itr() {return locate(0);}         //返回头节点指针, 内联
    Node* end_itr() {return locate(ListSize - 1);}//返回尾节点指针, 内联
public:
    LinkedList() {}                                   //构造函数
    LinkedList(const LinkedList & rhs) {}             //拷贝构造函数
    ~LinkedList()                                     //析构函数
    LinkedList& operator=(LinkedList& rhs);           //操作符重载

    int size() const {return ListSize;}               //链长度, 内联
    T& index(int index) {return locate(index)->data;} //索引函数, 内联
    T& begin() {return begin_itr()->next->data;}      //取头元素, 内联
    T& end() {return end_itr()->data;}                //取尾元素, 内联
    void insert(int index, const T& rhs);      //插入
    void erase(int index);                     //删除
    bool isempty() const {}                    //判空
    void clear() {}                            //清空
};

1
2
3
4
5
6
7

struct Node
{
    T data;
    Node* next;
    Node(const T& d=T(), Node* n=NULL)
        :data(d), next(n) {}
};

1
2
3
4
5
6

void init()
{
    head = new Node;
    head->next = NULL;
    ListSize = 1;
}

1
2
3
4
5
6
7
8
9

explicit LinkedList() {init();}
LinkedList(LinkedList& rhs);
~LinkedList()
{
    cout << "LinkedList:Destructor...";
    clear();
    delete head;
}
LinkedList& operator=(LinkedList& rhs);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//一个暴露默认构造函数缺陷的例子
class IntCell
{
public:
    explicit IntCell(int initialValue = 0)
        {storedValue = new int(initialValue);}
    int read() const {return *storedValue;}
    void write(int x) {*storedValue = x;}
private:
    int* storedValue;
};


int f()
{
    IntCell a(2);
    IntCell b = a;
    IntCell c;

    c = b;
    a.write(4);
    cout << a.read( ) << endl << b.read( ) << endl << c.read( ) << endl;

    return 0;
}

1
2
3
4
5
6
7
8

//改进默认构造函数的手段
explicit IntCell(const IntCell& rhs) //对应IntCell b = a或IntCell b(a)
   {storedValue = new int(*rhs.storedValue);}
IntCell & operator= ( const IntCell & rhs )  // 对应 b = a
{
   if (this != &rhs) {*storedValue = *rhs.storedValue;}
   return *this;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//deep copy, discard explicit or assignment upon initializion is unable
LinkedList(LinkedList& rhs) 
{
   init();
   for (int i = 0; i < rhs.size() - 1; ++i) {insert(i, rhs.index(i+1));}
}

LinkedList& operator=(LinkedList& rhs)
{
   if (this != &rhs)
   {
       for (int i = 0; i < rhs.size() - 1; ++i)
           {insert(i, rhs.index(i+1));}
   }
   return *this;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

template <typename T>
typename LinkedList<T>::Node*
LinkedList<T>::locate(int index)
{	
    if (index < 0) {cout << "error:index < 0" <<endl; return locate(0);}
if (index > ListSize - 1) {cout << "error:index overflow" <<endl; return locate(ListSize - 1    );}
    Node* itr = head;
    for (int i = 0; i < index; ++i) {itr = itr->next;}
    return itr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

//从index后插入一个节点
template <typename T>
void LinkedList<T>::insert(int index, const T& rhs) 
{
    Node *p = locate(index); 
    Node *newNode = new Node(rhs, p->next);
    p->next = newNode;
    ListSize++;
}
//删除index后一个节点
template <typename T>
void LinkedList<T>::erase(int index) 
{
    Node *p = locate(index);
    locate(index - 1)->next = p->next;
    delete p;
    ListSize--;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

//这是一个类实例
#include <string>
#define CLASS_EXAMPLE_H
#ifdef CLASS_EXAMPLE_H
using namespace std;

class Player
{
private:
    int rank;
    string name;
public:
    Player(int r = 0, const string & n = "#name") : rank(r), name(n) {}
    int getrank() const {return rank;}
    string getname() const {return name;}
};
#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

//测试文件
#include <iostream>
#include "../Class_Example.h"
#include "LinkedList_simplified.h"
using namespace std;

int main(int argc, char const *argv[])
{
   const int listcap = 5;
   Player playerlist[listcap] = 
   {
       Player(1, "Cookiezi"),
       Player(2, "WhiteWolf"),
       Player(3, "rrtyui"),
       Player(4, "powergame"),
       Player(5, "SiLviA"),
   };

   LinkedList<Player> players;
   cout << "-----------insert test-----------" <<endl;
   for (int i = 0; i < listcap; ++i)
   {
       players.insert(players.size() - 1, playerlist[i]);
   }
   for (int i = 0; i < listcap; ++i)
   {
       cout << players.index(i+1).getname() << ", " << endl;
   }
   cout << "-----------copy test-----------" <<endl;
   LinkedList<Player> players_copy_1 = players;
   for (int i = 0; i < listcap; ++i)
   {
       cout << players_copy_1.index(i+1).getname() << ", " << endl;
   }
   cout << "-----------operator= test-----------" <<endl;
   LinkedList<Player> players_copy_2;
   players_copy_2 = players_copy_1;
   for (int i = 0; i < listcap; ++i)
   {
       cout << players_copy_2.index(i+1).getname() << ", " << endl;
   }
   return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

-----------insert test-----------
Cookiezi,
WhiteWolf,
rrtyui,
powergame,
SiLviA,
-----------copy test-----------
Cookiezi,
WhiteWolf,
rrtyui,
powergame,
SiLviA,
-----------operator= test-----------
Cookiezi,
WhiteWolf,
rrtyui,
powergame,
SiLviA,
LinkedList:Destructor...LinkedList:Destructor...LinkedList:Destructor...
Process finished with exit code 0