首页 > 代码库 > 基于数组实现的单链表（兼具Boost单元测试）
基于数组实现的单链表（兼具Boost单元测试）
对于单链表，我们大多时候会用指针来实现（可参考基于指针实现的单链表）。现在我们就来看看怎么用数组来实现单链表。
1. 定义单链表中结点的数据结构
1 typedef int ElementType;2 class NodeType3 {4 public:5 ElementType data;6 int next;7 };
该结点包括了两个元素，其一是数据，另一个是指向下一个结点的“指针”（在这篇文章中实际上是指用于实现单链表的数组的下标。）
2. 定义一个的数组
1 const int CAPACITY = 1024;2 NodeType node[CAPACITY];
在内存中该数组的结构如下图：
3. 定义指向单链表第1个结点的“指针”
1 int head;
4. 一个简单的单链表例子
我们假设单链表只有3个结点，并且3个结点从左到右分别位于数组node中第0、1、2位置，如下图：
head指向链表中的第1个结点。该结点存储于数组node的第0位置，data为111，next指向下一结点。其他以此类推。
需要注意的是链表的中最后一个结点（即上图中的第3个结点）的next被置为-1，表示不指向任何结点。
更为重要的是，这三个结点是可以位于数组node中的任一位置的，只要他们之间保持这种链接的关系。
5. 实际程序实现
在实际程序实现中，为了便于判断数组中哪一个元素已经被使用，我在原单链表的结点数据结构中又添加了一个判断位，如下：
1 typedef int ElementType; 2 class NodeType 3 { 4 public: 5 NodeType() { data = http://www.mamicode.com/0; next = NULL_VALUE; isFree = true; }; 6 ~NodeType() {}; 7 ElementType data; 8 int next; 9 bool isFree; // 标志位，为true表示该结点可用，反之不可用10 };
其余的程序摘录如下：
1 #ifndef SINGLELINKEDLIST 2 #define SINGLELINKEDLIST 3 4 #include <iostream> 5 #include <cassert> 6 using namespace std; 7 8 const int CAPACITY = 1024; 9 const int NULL_VALUE = http://www.mamicode.com/-1;10 11 typedef int ElementType;12 class NodeType13 {14 public:15 NodeType() { data = http://www.mamicode.com/0; next = NULL_VALUE; isFree = true; };16 ~NodeType() {};17 ElementType data;18 int next;19 bool isFree; // 标志位，为true表示该结点可用，反之不可用20 };21 22 class LinkedList23 {24 public:25 LinkedList();26 virtual ~LinkedList();27 void initList(ElementType * arr, int len);28 bool isEmpty();29 int findFreeNode();30 bool addNode(const int pos, const ElementType val);31 bool deleteNode(const int pos);32 void displayNodes();33 NodeType getNode(const int pos);34 int getLenOfList();35 36 private:37 NodeType node[CAPACITY];38 int head;39 40 };41 42 43 #endif;
1 #include "linkedlist.h" 2 3 LinkedList::LinkedList() 4 { 5 head = NULL_VALUE; 6 } 7 8 LinkedList::~LinkedList() 9 { 10 for (int i = 0; i < CAPACITY; i++) 11 { 12 node[i].data = http://www.mamicode.com/0; 13 node[i].next = NULL_VALUE; 14 node[i].isFree = true; 15 } 16 } 17 18 void LinkedList::initList(ElementType * arr, int len) 19 { 20 for (int i = 0; i < len; i++) 21 { 22 int tmp = arr[i]; 23 addNode(i, tmp); 24 } 25 } 26 27 bool LinkedList::isEmpty() 28 { 29 return head == NULL_VALUE; 30 } 31 32 int LinkedList::findFreeNode() 33 { 34 int i = 0; 35 while (node[i].isFree == false) 36 { 37 i++; 38 if (i == CAPACITY) // 如果找不到可用的结点，返回NULL_VALUE 39 { 40 return NULL_VALUE; 41 } 42 } 43 return i; 44 } 45 46 bool LinkedList::addNode(const int pos, const ElementType val) 47 { 48 bool success = true; 49 int len = getLenOfList(); 50 if (len == CAPACITY) 51 { 52 cerr << "There is no space in the list." << endl; 53 success = false; 54 } 55 else 56 { 57 // assert(0 <= pos <= CAPACITY); 58 if (pos < 0 || pos > len) 59 { 60 cerr << "The node at position " << pos << " you want to add is less than zero or larger than " 61 << "the capacity of list ." << endl; 62 success = false; 63 throw out_of_range("out_of_range"); 64 } 65 else 66 { 67 int freeNode = findFreeNode(); 68 node[freeNode].data =http://www.mamicode.com/ val; 69 node[freeNode].isFree = false; 70 if (pos == 0) // 如果添加的元素在第1个 71 { 72 node[freeNode].next = head; 73 head = freeNode; 74 } 75 else // 其他 76 { 77 int ptr = head; 78 int count = 0; 79 while (ptr != NULL_VALUE && count < pos - 1) 80 { 81 ptr = node[ptr].next; 82 count++; 83 } 84 node[freeNode].next = node[ptr].next; 85 node[ptr].next = freeNode; 86 } 87 } 88 } 89 return success; 90 } 91 92 bool LinkedList::deleteNode(const int pos) 93 { 94 bool success = true; 95 int len = getLenOfList(); 96 if (len == 0) 97 { 98 cerr << "There is no element in the list." << endl; 99 success = false;100 }101 else102 {103 int ptr = head, tmpPtr;104 int count = 0;105 // assert(0 <= pos <= len);106 if (pos < 0 || pos > len - 1)107 {108 cerr << "The node at position " << pos << " you want to delete is less than zero or larger than "109 << "the length of list ." << endl;110 success = false;111 throw out_of_range("out_of_range");112 }113 else if (pos == 0) // 在链表第一个位置114 {115 head = node[head].next;116 node[ptr].data = http://www.mamicode.com/0;117 node[ptr].next = NULL_VALUE;118 node[ptr].isFree = true;119 }120 else if (pos == len - 1) // 在链表最后一个位置121 {122 while (ptr != NULL && count < pos - 1)123 {124 ptr = node[ptr].next;125 count++;126 }127 tmpPtr = node[ptr].next;128 node[ptr].next = NULL_VALUE;129 // reset the deleted one130 node[tmpPtr].data = http://www.mamicode.com/0;131 node[tmpPtr].next = NULL_VALUE;132 node[tmpPtr].isFree = true;133 }134 else // 其他135 {136 while (ptr != NULL && count < pos - 1)137 {138 ptr = node[ptr].next;139 count++;140 }141 tmpPtr = node[ptr].next;142 node[ptr].next = node[tmpPtr].next;143 // reset the deleted one144 node[tmpPtr].data = http://www.mamicode.com/0;145 node[tmpPtr].next = NULL_VALUE;146 node[tmpPtr].isFree = true;147 }148 }149 return success;150 }151 152 void LinkedList::displayNodes()153 {154 int ptr = head;155 int sequence = 0;156 while (ptr != NULL_VALUE)157 {158 cout << "Seq: " << sequence << "; Data: " << node[ptr].data << endl;159 ptr = node[ptr].next;160 sequence++;161 }162 }163 164 NodeType LinkedList::getNode(const int pos)165 {166 NodeType tmpNode;167 int len = getLenOfList();168 if (len == 0)169 {170 cerr << "There is no element in the list." << endl;171 }172 else173 {174 // assert(0 <= pos <= len);175 if (pos < 0 || pos > len - 1)176 {177 cerr << "The item at position " << pos << " you want to get is less than zero or "178 << "larger than the length of list." << endl;179 throw out_of_range("out_of_range");180 // return tmpNode;181 }182 else183 {184 int ptr = head;185 int count = 0;186 while (ptr != NULL_VALUE && count < pos)187 {188 ptr = node[ptr].next;189 count++;190 }191 tmpNode.data =http://www.mamicode.com/ node[ptr].data;192 tmpNode.next = node[ptr].next;193 tmpNode.isFree = node[ptr].isFree;194 }195 }196 197 return tmpNode;198 }199 200 int LinkedList::getLenOfList()201 {202 int ptr = head;203 int len = 0;204 while (ptr != NULL_VALUE)205 {206 ptr = node[ptr].next;207 len++;208 }209 210 return len;211 }
Boost单元测试代码测试如下：
1 #define BOOST_TEST_MODULE LinkedList_Test_Module 2 3 #include "stdafx.h" 4 #include "D:\VSProject\Algorithm\List\LinkedList\SingleLinkedList_BasedOnArray\SingleLinkedList\SingleLinkedList\linkedlist.h" 5 6 struct LinkedList_Fixture 7 { 8 public: 9 LinkedList_Fixture() 10 { 11 testLinkedList = new LinkedList(); 12 } 13 ~LinkedList_Fixture() 14 { 15 delete testLinkedList; 16 } 17 18 LinkedList * testLinkedList; 19 }; 20 21 BOOST_FIXTURE_TEST_SUITE(LinkedList_Test_Suite, LinkedList_Fixture) 22 23 24 BOOST_AUTO_TEST_CASE( LinkedList_Normal_Test ) 25 { 26 // isEmpty ------------------------------------------- 27 BOOST_REQUIRE(testLinkedList->isEmpty() == true); 28 29 // getLenOfList -------------------------------------- 30 BOOST_REQUIRE(testLinkedList->getLenOfList() == 0); 31 32 // findFreeNode -------------------------------------- 33 BOOST_REQUIRE(testLinkedList->findFreeNode() == 0); 34 35 // addNode & getNode --------------------------------- 36 BOOST_REQUIRE(testLinkedList->addNode(0, 0) == true); 37 BOOST_REQUIRE((testLinkedList->getNode(0)).data =http://www.mamicode.com/= 0); 38 BOOST_REQUIRE((testLinkedList->getNode(0)).next == NULL_VALUE); 39 BOOST_REQUIRE((testLinkedList->getNode(0)).isFree == false); 40 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 41 BOOST_REQUIRE(testLinkedList->getLenOfList() == 1); 42 43 BOOST_REQUIRE(testLinkedList->addNode(1, 2) == true); 44 BOOST_REQUIRE((testLinkedList->getNode(1)).data =http://www.mamicode.com/= 2); 45 BOOST_REQUIRE((testLinkedList->getNode(1)).next == NULL_VALUE); 46 BOOST_REQUIRE((testLinkedList->getNode(1)).isFree == false); 47 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 48 BOOST_REQUIRE(testLinkedList->getLenOfList() == 2); 49 50 BOOST_REQUIRE(testLinkedList->addNode(1, 1) == true); 51 BOOST_REQUIRE((testLinkedList->getNode(1)).data =http://www.mamicode.com/= 1); 52 BOOST_REQUIRE((testLinkedList->getNode(1)).next != NULL_VALUE); 53 BOOST_REQUIRE((testLinkedList->getNode(1)).isFree == false); 54 BOOST_REQUIRE((testLinkedList->getNode(2)).next == NULL_VALUE); 55 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 56 BOOST_REQUIRE(testLinkedList->getLenOfList() == 3); 57 58 // deleteNode ----------------------------------------- 59 BOOST_REQUIRE(testLinkedList->deleteNode(0) == true); 60 BOOST_REQUIRE((testLinkedList->getNode(0)).data =http://www.mamicode.com/= 1); 61 BOOST_REQUIRE(testLinkedList->getLenOfList() == 2); 62 63 BOOST_REQUIRE(testLinkedList->deleteNode(1) == true); 64 BOOST_REQUIRE((testLinkedList->getNode(0)).data =http://www.mamicode.com/= 1); 65 BOOST_REQUIRE(testLinkedList->getLenOfList() == 1); 66 67 BOOST_REQUIRE(testLinkedList->deleteNode(0) == true); 68 BOOST_REQUIRE(testLinkedList->getLenOfList() == 0); 69 70 // initList ------------------------------------------- 71 int arr[] = { 0, 1, 2 }; 72 int len = sizeof(arr) / sizeof(int); 73 testLinkedList->initList(arr, len); 74 BOOST_REQUIRE(testLinkedList->getLenOfList() == 3); 75 BOOST_REQUIRE((testLinkedList->getNode(0)).data =http://www.mamicode.com/= 0); 76 BOOST_REQUIRE((testLinkedList->getNode(0)).next == 1); 77 78 BOOST_REQUIRE((testLinkedList->getNode(1)).data =http://www.mamicode.com/= 1); 79 BOOST_REQUIRE((testLinkedList->getNode(1)).next == 2); 80 81 BOOST_REQUIRE((testLinkedList->getNode(2)).data =http://www.mamicode.com/= 2); 82 BOOST_REQUIRE((testLinkedList->getNode(2)).next == NULL_VALUE); 83 } 84 85 BOOST_AUTO_TEST_CASE(LinkedList_Abnormal_Test) 86 { 87 int arr[] = { 0, 1, 2 }; 88 int len = sizeof(arr) / sizeof(int); 89 testLinkedList->initList(arr, len); 90 91 // addNode ------------------------------------------- 92 BOOST_REQUIRE_THROW(testLinkedList->addNode(-1, 100), out_of_range); 93 BOOST_REQUIRE_THROW(testLinkedList->addNode(10, 100), out_of_range); 94 95 // deleteNode ---------------------------------------- 96 BOOST_REQUIRE_THROW(testLinkedList->deleteNode(-1), out_of_range); 97 BOOST_REQUIRE_THROW(testLinkedList->deleteNode(10), out_of_range); 98 99 // getNode --------------------------------------------100 BOOST_REQUIRE_THROW(testLinkedList->getNode(-1), out_of_range);101 BOOST_REQUIRE_THROW(testLinkedList->getNode(10), out_of_range);102 103 }104 105 106 BOOST_AUTO_TEST_SUITE_END()
个人“数据结构与算法”系列博文：
线性表：
顺序表：
基于静态分配的数组的顺序表（兼具Boost单元测试）
基于动态分配的数组的顺序表（兼具Boost单元测试）
链表：
基于指针实现的单链表（兼具Boost单元测试）
基于数组实现的单链表（兼具Boost单元测试）
基于数组实现的单链表（兼具Boost单元测试）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。