"《算法导论》之‘线性表’"：基于动态分配的数组的顺序表

　　我们利用静态分配的数组来实现的顺序表的局限还是挺大的，主要在于它的容量是预先定好的，用户不能根据自己的需要来改变。如果为了后续用户能够自己调整顺序表的大小，动态地分配数组空间还是很有必要的。基于动态分配的数组的顺序表绝大部分跟基于静态分配的数组的顺序表是一样的，只需在后者程序上改动一小部分即可。

　　第一，我们不需定义一个容量常量CAPACITY，而是定义一个私有变量myCapacity。

　　第二，类的构造函数需要改进一下。我们需要类在被实例化时自动申请内存，即需添加下边程序：

ElementType * seqList = new ElementType(myCapacity);
assert(seqList != NULL);

　　第三，类的析构函数需要添加下边一句：

delete [] seqList;

　　上面三点说的还有所欠缺。Larry Nyhoff在《数据结构与算法分析》第253页中提到设计类时要记住的一条规则：

　　如果类在运行时使用new分配内存，则它应该提供：

把动态分配的内存还给堆的析构函数。
编译器用来创建不同副本的复制构造函数。
程序员用来创建不同副本的赋值运算符。

　　基于动态分配的数组的顺序表设计的类如下：

 1 // seqlist.h
 2 #ifndef SEQLIST
 3 #define SEQLIST
 4 
 5 #include <iostream>
 6 #include <cassert>
 7 #include <algorithm>
 8 
 9 using namespace std;
10 
11 typedef int ElementType;
12 
13 class SeqList
14 {
15 public:
16     SeqList(const int maxsize = 1024);
17     virtual ~SeqList();
18     SeqList(const SeqList& origList);    　　　　　　　　　　　　　　 // 拷贝构造函数，记得防止浅拷贝
19     const SeqList& operator=(const SeqList& rightHandSide);      // 重载赋值运算符，记得防止浅拷贝
20     bool empty() const;
21     void clear();
22     bool insert(const int pos, const ElementType val);
23     bool erase(const int pos);
24     void display() const;
25     bool setSeqList(const ElementType *tmpList, const int len);
26     int getLenOfList() const;
27     ElementType getItem(const int pos);
28     ElementType * getSeqList();    　　　　　　　　　　　　　　　　　　// 保留，不推荐使用，因为在使用过程中无法进行越界检查
29 
30 private:
31     int myCapacity;    　　　　　　　　　　　　　　　　　　　　　　　　　// 自定义顺序表容量
32     int lenOfList;    　　　　　　　　　　　　　　　　　　　　　　　　　 // 顺序表长度
33     ElementType * seqList;
34 
35 };
36 
37 #endif

　　实现程序为：

  1 // seqlist.cpp
  2 #include <iostream>
  3 #include <cassert>
  4 #include "seqlist.h"
  5 
  6 using namespace std;
  7 
  8 SeqList::SeqList(const int maxsize)
  9 {
 10     // initialization
 11     lenOfList = 0;
 12     myCapacity = maxsize;
 13     seqList = new ElementType[myCapacity];
 14     // assert(seqList != NULL);
 15     if (seqList == NULL)
 16     {
 17         cerr << "Inadequate memory to allocate stack." << endl;
 18         throw bad_alloc();
 19     }
 20 }
 21 
 22 SeqList::~SeqList()
 23 {
 24     delete[] seqList;
 25 }
 26 
 27 SeqList::SeqList(const SeqList& origList)
 28 {
 29     myCapacity = origList.myCapacity;
 30     lenOfList = origList.lenOfList;
 31     seqList = new ElementType[myCapacity];
 32     // assert(seqList != NULL);
 33     if (seqList == NULL)
 34     {
 35         cerr << "Inadequate memory to allocate stack." << endl;
 36         throw bad_alloc();
 37     }
 38     else
 39     {
 40         for (int i = 0; i < lenOfList; i++)
 41         {
 42             seqList[i] = origList.seqList[i];
 43         }
 44     }
 45 }
 46 
 47 const SeqList& SeqList::operator=(const SeqList& rightHandSide)
 48 {
 49     // 确保不是自我赋值
 50     if (this != &rightHandSide)
 51     {
 52         // 如果需要，分配一个新数组
 53         if (myCapacity != rightHandSide.myCapacity)
 54         {
 55             delete[] seqList;
 56             myCapacity = rightHandSide.myCapacity;
 57             seqList = new ElementType[myCapacity];
 58             // assert(seqList != NULL);
 59             if (seqList == NULL)
 60             { 
 61                 cerr << "Inadequate memory to allocate stack." << endl;
 62                 throw bad_alloc();
 63             }
 64         }
 65 
 66         lenOfList = rightHandSide.lenOfList;
 67         for (int i = 0; i < lenOfList; i++)
 68         {
 69             seqList[i] = rightHandSide.seqList[i];
 70         }
 71     }
 72     return *this;
 73 }
 74 
 75 bool SeqList::empty() const
 76 {
 77     return lenOfList == 0;
 78 }
 79 
 80 void SeqList::clear()
 81 {
 82     lenOfList = 0;
 83     fill(seqList, seqList + myCapacity - 1, 0);
 84 }
 85 
 86 bool SeqList::insert(const int pos, const ElementType val)
 87 {
 88     bool success = false;
 89     // assert(lenOfList != CAPACITY);    // 这里的assert分成两行写，是为了方便定位错误发生的地方
 90     // assert(0 <= pos <= lenOfList);
 91     if (lenOfList == myCapacity)
 92     {
 93         cerr << "No space for insertion!" << endl;
 94     }
 95     else if (pos < 0 || pos > lenOfList)
 96     {
 97         cerr << "The position " << pos << 
 98             " you want to insert is less than zero or exceeds the length of the list!" << endl;
 99         throw out_of_range("throw out_of_range");    // 抛出一个越界异常
100     }
101     else
102     {
103         int tmpCount = lenOfList - pos;
104         for (int i = 0; i < tmpCount; i++)
105         {
106             seqList[lenOfList - i] = seqList[lenOfList - i - 1];
107         }
108         seqList[pos] = val;
109         lenOfList++;
110         success = true;
111     }
112     return success;
113 }
114 
115 bool SeqList::erase(const int pos)
116 {
117     bool success = false;
118     // assert(lenOfList != 0);
119     // assert(0 <= pos <= lenOfList);
120     if (lenOfList == 0)
121     {
122         cerr << "There is no elements in the list!" << endl;
123     }
124     else if (pos < 0 || pos > lenOfList)
125     {
126         cerr << "The position " << pos << 
127             " you want to erase is less than zero or exceeds the length of the list!" << endl;
128         throw out_of_range("throw out_of_range");    // 抛出一个越界异常
129     }
130     else
131     {
132         int tmp = lenOfList - pos;
133         for (int i = 0; i < tmp - 1; i++)
134         {
135             seqList[pos + i] = seqList[pos + i + 1];
136         }
137         seqList[lenOfList - 1] = 0;
138         lenOfList--;
139         success = true;
140     }
141     return success;
142 }
143 
144 void SeqList::display() const
145 {
146     cout << "***Start Displaying***" << endl;
147     if (lenOfList == 0)
148     {
149         cerr << "There is no element in the the list!" << endl;
150     }
151     else
152     {
153         for (int i = 0; i < lenOfList; i++)
154         {
155             cout << i << " : " << seqList[i] << endl;
156         }
157         cout << "***End Displaying***" << endl;
158     }
159 }
160 
161 bool SeqList::setSeqList(const ElementType *tmpList, const int len)
162 {
163     // assert(len <= CAPACITY);
164     bool success = false;
165     if (len <= myCapacity)
166     {
167         for (int i = 0; i < len; i++)
168         {
169             seqList[i] = *(tmpList++);
170         }
171         lenOfList = len;
172         success = true;
173     }
174     else
175     {
176         cerr << "The length of the array you set exceeds the CAPACITY." << endl;
177         throw out_of_range("throw out_of_range");    // 抛出一个越界异常
178     }
179     return success;
180 }
181 
182 int SeqList::getLenOfList() const
183 {
184     return lenOfList;
185 }
186 
187 ElementType SeqList::getItem(const int pos)
188 {
189     // assert(0 <= pos <= lenOfList);
190     if (pos < 0 || pos > lenOfList)
191     {
192         cerr << "The item at " << pos << " you want to get does not exist!" << endl;
193         throw out_of_range("throw out_of_range");    // 抛出一个越界异常
194     }
195     else
196     {
197         return seqList[pos];
198     }
199 }
200 
201 ElementType * SeqList::getSeqList()
202 {
203     return seqList;
204 }

seqlist.cpp

　　Boost单元测试程序为：

  1 // BoostUnitTest.cpp
  2 #define  BOOST_TEST_MODULE ArrayList_Test_Module
  3 
  4 #include "stdafx.h"
  5 #include "D:VSProjectAlgorithmListSeqListSeqList_BsedOnDynamicArraySeqListseqlist.h"
  6 
  7 struct ArrayList_Fixture
  8 {
  9     ArrayList_Fixture()
 10     {
 11         BOOST_TEST_MESSAGE("Setup fixture");
 12         testArrayList = new SeqList(1024);
 13     }
 14     ~ArrayList_Fixture()
 15     {
 16         BOOST_TEST_MESSAGE("Teardown fixture");
 17         delete testArrayList;
 18     }
 19 
 20     SeqList * testArrayList;
 21 };
 22 
 23 // BOOST_AUTO_TEST_SUITE(ArrayList_Test_Suite)
 24 BOOST_FIXTURE_TEST_SUITE(ArrayList_Test_Suite, ArrayList_Fixture)
 25 
 26 BOOST_AUTO_TEST_CASE(ArrayList_Abnormal_Test)
 27 {
 28     // Set values to the array list
 29     int testArray[] = { 1, 2, 3, 4, 5 };    // 5 个元素
 30     int testLenOfList = sizeof(testArray) / sizeof(int);
 31     testArrayList->setSeqList(testArray, testLenOfList);
 32     // BOOST_REQUIRE_THROW(testArrayList->setArrayList(testArray, testLenOfList), out_of_range);
 33 
 34 
 35     // Method getItem-----------------------------------------------
 36     // If the position of the item you want to get is less than zero
 37     BOOST_REQUIRE_THROW(testArrayList->getItem(-1), out_of_range);
 38     // If the position of the item you want to get is larger than the length of the list
 39     BOOST_REQUIRE_THROW(testArrayList->getItem(10), out_of_range);
 40 
 41 
 42     // Method insert-------------------------------------------------
 43     // If the inserting position is less than zero
 44     BOOST_REQUIRE_THROW(testArrayList->insert(-1, 10), out_of_range);
 45     BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList);
 46 
 47     // If the inserting position is larger than the length of the list
 48     BOOST_REQUIRE_THROW(testArrayList->insert(10, 10), out_of_range);
 49     BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList);
 50 
 51 
 52     // Method erase-------------------------------------------------
 53     // If the erasing position is less than zero
 54     BOOST_REQUIRE_THROW(testArrayList->erase(-1), out_of_range);
 55     BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList);
 56 
 57     // If the erasing position is larger than the length of the list
 58     BOOST_REQUIRE_THROW(testArrayList->erase(10), out_of_range);
 59     BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList);
 60 
 61 }
 62 
 63 BOOST_AUTO_TEST_CASE(ArrayList_Normal_Test)
 64 {
 65     bool expected;
 66     bool actual;
 67     // Method empty-------------------------------------------------
 68     expected = true;
 69     actual = testArrayList->empty();
 70     BOOST_REQUIRE(expected == actual);
 71 
 72     // Set values to the array list
 73     int testArray[] = { 1, 2, 3, 4, 5 };    // 5 个元素
 74     int testLenOfList = sizeof(testArray) / sizeof(int);
 75     testArrayList->setSeqList(testArray, testLenOfList);
 76     // BOOST_REQUIRE_THROW(testArrayList->setArrayList(testArray, testLenOfList), out_of_range);
 77 
 78     // Method getItem-----------------------------------------------
 79     BOOST_REQUIRE(testArrayList->getItem(1) == testArray[1]);
 80 
 81 
 82     // Method empty-------------------------------------------------
 83     expected = false;
 84     actual = testArrayList->empty();
 85     BOOST_REQUIRE(expected == actual);
 86 
 87 
 88     // Method insert-------------------------------------------------
 89     expected = true;
 90     actual = testArrayList->insert(1, 10);
 91     BOOST_REQUIRE(expected == actual);
 92     BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList + 1);
 93     BOOST_REQUIRE(testArrayList->getItem(1) == 10);
 94 
 95 
 96     // Method erase-------------------------------------------------
 97     expected = true;
 98     actual = testArrayList->erase(1);
 99     BOOST_REQUIRE(expected, actual);
100     BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList);
101     BOOST_REQUIRE(testArrayList->getItem(1) == testArray[1]);
102 
103 }
104 
105 BOOST_AUTO_TEST_CASE(ArrayList_CopyConstructor_Test)
106 {
107     bool expected;
108     bool actual;
109     // Set values to the array list
110     int testArray[] = { 1, 2, 3, 4, 5 };    // 5 个元素
111     int testLenOfList = sizeof(testArray) / sizeof(int);
112     testArrayList->setSeqList(testArray, testLenOfList);
113     // BOOST_REQUIRE_THROW(testArrayList->setArrayList(testArray, testLenOfList), out_of_range);
114 
115     // Copy constructor
116     //SeqList * copySeqList(testArrayList);        // 极容易写成这样子。错误。
117                                                 // 需要给copySeqList分配内存
118     SeqList * copySeqList = new SeqList(*testArrayList);
119 
120     // Method getItem-----------------------------------------------
121     BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);
122 
123 
124     // Method empty-------------------------------------------------
125     expected = false;
126     actual = copySeqList->empty();
127     BOOST_REQUIRE(expected == actual);
128 
129 
130     // Method insert-------------------------------------------------
131     expected = true;
132     actual = copySeqList->insert(1, 10);
133     BOOST_REQUIRE(expected == actual);
134     BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList + 1);
135     BOOST_REQUIRE(copySeqList->getItem(1) == 10);
136 
137 
138     // Method erase-------------------------------------------------
139     expected = true;
140     actual = copySeqList->erase(1);
141     BOOST_REQUIRE(expected, actual);
142     BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList);
143     BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);
144 }
145 
146 BOOST_AUTO_TEST_CASE(ArrayList_EqualOperator_Test)
147 {
148     bool expected;
149     bool actual;
150     // Set values to the array list
151     int testArray[] = { 1, 2, 3, 4, 5 };    // 5 个元素
152     int testLenOfList = sizeof(testArray) / sizeof(int);
153     testArrayList->setSeqList(testArray, testLenOfList);
154     // BOOST_REQUIRE_THROW(testArrayList->setArrayList(testArray, testLenOfList), out_of_range);
155 
156     // Copy constructor
157     SeqList * copySeqList = new SeqList(2048);
158     // copySeqList = testArrayList;        // 极易犯的一个低级错误
159     *copySeqList = *testArrayList;
160 
161     // Method getItem-----------------------------------------------
162     BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);
163 
164 
165     // Method empty-------------------------------------------------
166     expected = false;
167     actual = copySeqList->empty();
168     BOOST_REQUIRE(expected == actual);
169 
170 
171     // Method insert-------------------------------------------------
172     expected = true;
173     actual = copySeqList->insert(1, 10);
174     BOOST_REQUIRE(expected == actual);
175     BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList + 1);
176     BOOST_REQUIRE(copySeqList->getItem(1) == 10);
177 
178 
179     // Method erase-------------------------------------------------
180     expected = true;
181     actual = copySeqList->erase(1);
182     BOOST_REQUIRE(expected, actual);
183     BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList);
184     BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);
185 }
186 
187 BOOST_AUTO_TEST_SUITE_END();

BoostUnitTest.cpp

　　本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.