线性表的顺序存储——静态顺序表和动态顺序表的实现

1，本文目标：

　　1，完成 StaticList 类的具体实现；

　　2，完成 DynamicList 类的具体实现；

2，StaticList 设计要点：

1，类模板：

1，使用原生数组作为顺序存储空间；

2，使用模板参数决定数组大小；

3，StaticList 的实现：

 1 #ifndef STATICLIST_H
 2 #define STATICLIST_H
 3 
 4 #include "SeqList.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 template <typename T, int N>
10 class StaticList : public SeqList<T>
11 {
12 protected:
13 　　 T m_space[N];  // 顺序存储空间， N 为模板参数，静态定义的一个顺序存储空间，这就是 Static 的含义；
14 
15 public:
16     StaticList()  // 指定父类成员的具体值；父类先默认初始化，然后子类再初始化继承而来的成员变量,各自初始化各自的成员变量；
17     {
18         this->m_array = m_space;
19         this->m_length = 0;
20 　　 }
21 
22     int capacity() const
23     {
24         return N;
25     }
26 };
27 
28 }

 

4，StaticList 类模板测试代码：

 1 #include <iostream>
 2 #include "StaticList.h"
 3 
 4 using namespace std;
 5 using namespace DTLib;
 6 
 7 int main()
 8 {
 9 　　 StaticList<int, 5> l;
10 
11     for(int i=0; i<l.capacity(); i++)
12     {
13         l.insert(0, i);
14 　　 }
15 
16     for(int i=0; i<l.length(); i++)
17     {
18         cout << l[i] << endl;
19 　　 }
20 
21     l[0] *= l[0];
22     for(int i=0; i<l.length(); i++)
23     {
24         cout << l[i] << endl;
25 　　 }
26 
27     try
28     {
29         l[5] = 5;
30     }
31     catch(const Exception& e)
32     {
33         cout << e.message() << endl;
34         cout << e.location() << endl;
35 　　 }
36 
37     return 0;
38 }

5，DynamicList 设计要点（比 StaticList 复杂的多就是复杂在 Dynamic 上面）：

1，类模板：

1，申请连续堆空间（这里就是 Dynamic 含义）作为顺序存储空间；

2，动态设置（这里就是 Dynamic 含义）顺序存储空间的大小（觉着当前存储空间太大或太小了）；

3，保证重置顺序存储空间时的异常安全性；

1，函数异常安全的概念：

1，不泄漏任何资源；

2，不允许破坏数据；

2，函数异常安全的基本保证：

1，如果一场被抛出：

1，对象内任何成员任然能保持有效状态；

2，没有数据的破坏及资源泄漏；

6，DynamicList 设计要点：

7， DynamicList 的实现：

 1 #ifndef DYNAMICLIST_H
 2 #define DYNAMICLIST_H
 3 
 4 #include "SeqList.h"
 5 #include "Exception.h"
 6 
 7 namespace DTLib
 8 {
 9 template <typename T>
10 class DynamicList : public SeqList<T>
11 {
12 protected:
13 　　 int m_capacity;   //顺序存储空间的大小
14 
15 public:
16     DynamicList(int capacity)    //申请顺序存储空间
17     {
18         this->m_array = new T[capacity];
19         if( this->m_array != NULL )
20         {
21             this->m_length = 0;
22             this->m_capacity = capacity;
23         }
24         else
25         {
26             THROW_EXCEPTION(NoEnoughMemoryException, "No menory to create DynamicList object ...");
27         }
28 　　 }
29 
30     int capacity() const
31     {
32         return m_capacity;
33 　　 }
34 
35     /* 重置顺序存储空间的大小,觉着当前存储空间太大或太小了，要重置 */
36     void resize(int capacity)
37     {
38         if( m_capacity != capacity )
39         {
40             T* array = new T[capacity];    // 不用this->m_array是为了保证 this->m_array 指向原来的空间，以便下面的 for 循环的赋值操作；
41 
42             if( array != NULL )
43             {
44                 int length = (this->m_length < capacity ? this->m_length : capacity);
45 
46                 for( int i=0; i<length; i++ )    // 保证数据结构没有丢失，所以要让 m_array 还是指向原来的堆空间，当然这里数组也可以自己给自己赋值；
47                 {
48                     array[i] = this-> m_array[i];   // 这里可能发生异常，当发生异常的时候，三个成员变量值没有任何改变，线性表依然合法可用，只不过 array 指向的堆空间将会发生泄漏，但是对于 resize() 函数是无法顾全的，因为 array 里面存储的是 T 的泛指类型，这个泛指类型赋值操作符有可能被重载，如果重载里面是有错的，有异常的，这里我们就不能顾全了，如果在这里发生了异常，则就是泛指类型 T 导致的，也就是第三方工程导致的； 因为是泛指类型，这里的赋值可能由第三方工程师发生异常，不在考虑范围；如果发生异常，这里的 resize 保持不更改，但是会造成 array 指向的堆空间内存泄露；
49                 }
50 
51                 T* temp = this->m_array;    // 是为了在下面删除之前的堆空间，如//果直接 delete[] this->m_array 则会发生异常不安全；
52 
53                 this->m_array = array;      //是为了使 resize 函数有效，这里类似//于构造函数，这三条语句不会发生异常；
54                 this->m_length = length;
55                 this->m_capacity = capacity;
56 
57                 delete[] temp;    // 在这里才删除是为了异常安全；因为泛指类型可//能是类类型，在delete[]时候就可能触发析构函数进而由于某种原因发生异常，这样就会发生异常返回了，也就不能保证上面三条语句执行，也就不能保证resize函数的有效了，则当前的线性表不能保证合法可用；则如果发生异常，这个线性表不可用，也就不是异常安全的了；这里这个函数是异常安全的，即便发生了异常，然后异常返回，但是三个成员变量的值已经合法，则当前线性表对象也是合法可用的；
58             }
59             else
60             {
61                 THROW_EXCEPTION(NoEnoughMemoryException, "No enough to resize DynamicList object ...");
62             }
63         }
64 　　 }
65 
66     ~DynamicList()
67     {
68         delete[] this->m_array;
69     }
70 };
71 
72 }
73 
74 #endif // DYNAMICLIST_H

8，DynamicList 实现的测试代码：

 1 #include <iostream>
 2 #include "DynamicList.h"
 3 
 4 using namespace std;
 5 using namespace DTLib;
 6 
 7 int main()
 8 {
 9 　　 DynamicList<int> l(5);
10 
11     for(int i=0; i<l.capacity(); i++)
12     {
13         l.insert(0, i);
14 　　 }
15 
16     for(int i=0; i<l.length(); i++)
17     {
18         cout << l[i] << endl;
19 　　 }
20 
21 　　 l[0] *= l[0];
22 
23     for(int i=0; i<l.length(); i++)
24     {
25         cout << l[i] << endl;
26 　　 }
27 
28     try
29     {
30         l[5] = 5;
31     }
32     catch(const Exception& e)
33     {
34         cout << e.message() << endl;
35         cout << e.location() << endl;
36 
37         l.resize(10);
38         l.insert(5, 50);
39 　　 }
40 
41 　　 l[5] = 5;
42 
43     for(int i=0; i<l.length(); i++)
44     {
45         cout << l[i] << endl;
46 　　 }
47 
48 　　 l.resize(3);
49 
50 　　 for(int i=0; i<l.length(); i++)
51     {
52         cout << l[i] << endl;
53   　}
54 
55     return 0;
56 }

9，是否可以将 DynamicList 作为 StaticList 的子类实现：

1，不可以，反之也不可以；

2，因为这两个类对于顺序存储空间的指定没有任何的关系，所以在类层次中位于同一层；

10，小结：

1，StaticList 通过模板参数定义顺序存储空间；

2，DynamicList 通过动态内存申请定义顺序存储空间；

3，DynamicList 通过动态重置顺序存储空间的大小；

4，DynamicList 中的 resize() 函数实现需要保证异常安全；