基于静态分配的数组的顺序表（兼具Boost单元测试）
浏览数：30 /
时间：2015年06月08日
首先，我们来搞明白几个概念吧（参考自网站数据结构及百度百科）。
线性表
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。
顺序表
用顺序存储方法存储的线性表简称为顺序表（Sequential List）。顺序表的存储方法是把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。
链表
链接方式存储的线性表简称为链表（Linked List）。
顺序表和链表的比较如下：
注：存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即“存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）”。
下文将具体讲述如何实现基于静态分配的数组的顺序表：
具体算法可以参考网页顺序表上实现的基本运算及Larry Nyhoff的《数据结构与算法分析》。我的做法基本跟他们是一样的，只是我又额外多了一部分：Boost单元测试。对于如何进行Boost单元测试可以参考本人之前写过的一篇文章如何在VS2013中进行Boost单元测试。
我设计的顺序表类如下：
// seqlist.h
1 #ifndef SEQLIST 2 #define SEQLIST 3 4 #include <iostream> 5 #include <cassert> 6 #include <algorithm> 7 8 using namespace std; 9 10 const int CAPACITY = 1024; 11 typedef int ElementType; 12 13 class SeqList 14 { 15 public: 16 SeqList(); 17 virtual ~SeqList(); 18 bool empty() const; 19 void clear(); 20 bool insert(const int pos, const ElementType val); 21 bool erase(const int pos); 22 void display() const; 23 bool setSeqList(const ElementType *tmpList, const int len); 24 int getLenOfList() const; 25 ElementType getItem(const int pos); 26 ElementType * getSeqList(); // 保留，不推荐使用，因为在使用过程中无法进行越界检查 27 28 private: 29 int lenOfList; // 线性链表长度 30 ElementType seqList[CAPACITY]; 31 32 }; 33 34 #endif
1 // seqlist.cpp 2 #include "seqlist.h" 3 4 SeqList::SeqList() 5 { 6 // initialization 7 lenOfList = 0; 8 fill(seqList, seqList + CAPACITY - 1, 0); 9 // memset(SeqList, 1, CAPACITY*sizeof(int)); 10 } 11 12 SeqList::~SeqList() 13 { 14 15 } 16 17 bool SeqList::empty() const 18 { 19 return lenOfList == 0; 20 } 21 22 void SeqList::clear() 23 { 24 lenOfList = 0; 25 fill(seqList, seqList + CAPACITY - 1, 0); 26 } 27 28 bool SeqList::insert(const int pos, const ElementType val) 29 { 30 bool success = false; 31 // assert(lenOfList != CAPACITY); // 这里的assert分成两行写，是为了方便定位错误发生的地方 32 // assert(0 <= pos <= lenOfList); 33 if (lenOfList == CAPACITY) 34 { 35 cerr << "No space for insertion!" << endl; 36 } 37 else if (pos < 0 || pos > lenOfList) 38 { 39 cerr << "The position " << pos << 40 " you want to insert is less than zero or exceeds the length of the list!" << endl; 41 throw out_of_range("throw out_of_range"); // 抛出一个越界异常 42 } 43 else 44 { 45 int tmpCount = lenOfList - pos; 46 for (int i = 0; i < tmpCount; i++) 47 { 48 seqList[lenOfList - i] = seqList[lenOfList - i - 1]; 49 } 50 seqList[pos] = val; 51 lenOfList++; 52 success = true; 53 } 54 return success; 55 } 56 57 bool SeqList::erase(const int pos) 58 { 59 bool success = false; 60 // assert(lenOfList != 0); 61 // assert(0 <= pos <= lenOfList); 62 if (lenOfList == 0) 63 { 64 cerr << "There is no elements in the list!" << endl; 65 } 66 else if (pos < 0 || pos > lenOfList) 67 { 68 cerr << "The position " << pos << 69 " you want to erase is less than zero or exceeds the length of the list!" << endl; 70 throw out_of_range("throw out_of_range"); // 抛出一个越界异常 71 } 72 else 73 { 74 int tmp = lenOfList - pos; 75 for (int i = 0; i < tmp - 1; i++) 76 { 77 seqList[pos + i] = seqList[pos + i + 1]; 78 } 79 seqList[lenOfList - 1] = 0; 80 lenOfList--; 81 success = true; 82 } 83 return success; 84 } 85 86 void SeqList::display() const 87 { 88 cout << "***Start Displaying***" << endl; 89 if (lenOfList == 0) 90 { 91 cerr << "There is no element in the the list!" << endl; 92 } 93 else 94 { 95 for (int i = 0; i < lenOfList; i++) 96 { 97 cout << i << " : " << seqList[i] << endl; 98 } 99 cout << "***End Displaying***" << endl; 100 } 101 } 102 103 bool SeqList::setSeqList(const ElementType *tmpList, const int len) 104 { 105 // assert(len <= CAPACITY); 106 bool success = false; 107 if (len <= CAPACITY) 108 { 109 for (int i = 0; i < len; i++) 110 { 111 seqList[i] = *(tmpList++); 112 } 113 lenOfList = len; 114 success = true; 115 } 116 else 117 { 118 cerr << "The length of the array you set exceeds the CAPACITY." << endl; 119 throw out_of_range("throw out_of_range"); // 抛出一个越界异常 120 } 121 return success; 122 } 123 124 int SeqList::getLenOfList() const 125 { 126 return lenOfList; 127 } 128 129 ElementType SeqList::getItem(const int pos) 130 { 131 // assert(0 <= pos <= lenOfList); 132 if (pos < 0 || pos > lenOfList) 133 { 134 cerr << "The item at " << pos << " you want to get does not exist!" << endl; 135 throw out_of_range("throw out_of_range"); // 抛出一个越界异常 136 } 137 else 138 { 139 return seqList[pos]; 140 } 141 } 142 143 ElementType * SeqList::getSeqList() 144 { 145 return seqList; 146 }
单元测试所用到的代码如下：
1 // BoostUnitTest.cpp 2 #define BOOST_TEST_MODULE ArrayList_Test_Module 3 4 #include "stdafx.h" 5 #include "D:\VSProject\Algorithm\List\SeqList\SeqList\SeqList\seqlist.h" 6 7 struct ArrayList_Fixture 8 { 9 ArrayList_Fixture() 10 { 11 BOOST_TEST_MESSAGE("Setup fixture"); 12 testArrayList = new SeqList(); 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 79 // Method getItem----------------------------------------------- 80 BOOST_REQUIRE(testArrayList->getItem(1) == testArray[1]); 81 82 83 // Method empty------------------------------------------------- 84 expected = false; 85 actual = testArrayList->empty(); 86 BOOST_REQUIRE(expected == actual); 87 88 89 // Method insert------------------------------------------------- 90 expected = true; 91 actual = testArrayList->insert(1, 10); 92 BOOST_REQUIRE(expected == actual); 93 BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList + 1); 94 BOOST_REQUIRE(testArrayList->getItem(1) == 10); 95 96 97 // Method erase------------------------------------------------- 98 expected = true; 99 actual = testArrayList->erase(1); 100 BOOST_REQUIRE(expected, actual); 101 BOOST_REQUIRE(testArrayList->getLenOfList() == testLenOfList); 102 BOOST_REQUIRE(testArrayList->getItem(1) == testArray[1]); 103 104 } 105 106 BOOST_AUTO_TEST_SUITE_END();
我在单元测试中偏向于使用REQUIRE型的判断，这样方便我检测出问题出现在哪。另外，我在单元测试中偏向于按“正常测试”和“不正常测试”两类进行测试。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
