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

时间:2021-11-18 19:30:11

  首先,我们来搞明白几个概念吧(参考自网站数据结构及百度百科)。

  线性表

  线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。在实现线性表数据元素的存储方面,一般可用顺序存储结构链式存储结构两种方法。

  顺序表

  用顺序存储方法存储的线性表简称为顺序表(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 }
seqlist.cpp

  单元测试所用到的代码如下:

"《算法导论》之‘线性表’":基于静态分配的数组的顺序表"《算法导论》之‘线性表’":基于静态分配的数组的顺序表
  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();
BoostUnitTest.cpp

  我在单元测试中偏向于使用REQUIRE型的判断,这样方便我检测出问题出现在哪。另外,我在单元测试中偏向于按“正常测试”和“不正常测试”两类进行测试。

 

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