首页 > 代码库 > 基于动态分配的数组的顺序表（兼具Boost单元测试）
基于动态分配的数组的顺序表（兼具Boost单元测试）
我们利用静态分配的数组来实现的顺序表的局限还是挺大的，主要在于它的容量是预先定好的，用户不能根据自己的需要来改变。如果为了后续用户能够自己调整顺序表的大小，动态地分配数组空间还是很有必要的。基于动态分配的数组的顺序表绝大部分跟基于静态分配的数组的顺序表是一样的，只需在后者程序上改动一小部分即可。
第一，我们不需定义一个容量常量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 SeqList14 {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 else102 {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 else131 {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() const145 {146 cout << "***Start Displaying***" << endl;147 if (lenOfList == 0)148 {149 cerr << "There is no element in the the list!" << endl;150 }151 else152 {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 else175 {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() const183 {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 else196 {197 return seqList[pos];198 }199 }200 201 ElementType * SeqList::getSeqList()202 {203 return seqList;204 }
Boost单元测试程序为：
1 // BoostUnitTest.cpp 2 #define BOOST_TEST_MODULE ArrayList_Test_Module 3 4 #include "stdafx.h" 5 #include "D:\VSProject\Algorithm\List\SeqList\SeqList_BsedOnDynamicArray\SeqList\seqlist.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 list110 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 constructor116 SeqList * copySeqList(testArrayList);117 118 // Method getItem-----------------------------------------------119 BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);120 121 122 // Method empty-------------------------------------------------123 expected = false;124 actual = copySeqList->empty();125 BOOST_REQUIRE(expected == actual);126 127 128 // Method insert-------------------------------------------------129 expected = true;130 actual = copySeqList->insert(1, 10);131 BOOST_REQUIRE(expected == actual);132 BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList + 1);133 BOOST_REQUIRE(copySeqList->getItem(1) == 10);134 135 136 // Method erase-------------------------------------------------137 expected = true;138 actual = copySeqList->erase(1);139 BOOST_REQUIRE(expected, actual);140 BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList);141 BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);142 }143 144 BOOST_AUTO_TEST_CASE(ArrayList_EqualOperator_Test)145 {146 bool expected;147 bool actual;148 // Set values to the array list149 int testArray[] = { 1, 2, 3, 4, 5 }; // 5 个元素150 int testLenOfList = sizeof(testArray) / sizeof(int);151 testArrayList->setSeqList(testArray, testLenOfList);152 // BOOST_REQUIRE_THROW(testArrayList->setArrayList(testArray, testLenOfList), out_of_range);153 154 // Copy constructor155 SeqList * copySeqList = new SeqList(2048);156 copySeqList = testArrayList;157 158 // Method getItem-----------------------------------------------159 BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);160 161 162 // Method empty-------------------------------------------------163 expected = false;164 actual = copySeqList->empty();165 BOOST_REQUIRE(expected == actual);166 167 168 // Method insert-------------------------------------------------169 expected = true;170 actual = copySeqList->insert(1, 10);171 BOOST_REQUIRE(expected == actual);172 BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList + 1);173 BOOST_REQUIRE(copySeqList->getItem(1) == 10);174 175 176 // Method erase-------------------------------------------------177 expected = true;178 actual = copySeqList->erase(1);179 BOOST_REQUIRE(expected, actual);180 BOOST_REQUIRE(copySeqList->getLenOfList() == testLenOfList);181 BOOST_REQUIRE(copySeqList->getItem(1) == testArray[1]);182 }183 184 BOOST_AUTO_TEST_SUITE_END();
基于动态分配的数组的顺序表（兼具Boost单元测试）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。