首页 > 代码库 > 单链表（兼具Boost单元测试）
单链表（兼具Boost单元测试）
这是“线性表系列”中的“链表系列”文章之一——单链表。关于“线性表系列”中的“顺序表系列”请转到：基于静态分配的数组的顺序表（兼具Boost单元测试），基于动态分配的数组的顺序表（兼具Boost单元测试）。
对于单链表的介绍请参考网页。
对于单链表，我定义了一个这样的类LinkedList：
1 // linkedlist.h 2 #ifndef LINKEDLIST 3 #define LINKEDLIST 4 5 #include <iostream> 6 #include <cassert> 7 8 using namespace std; 9 10 typedef int ElementType;11 12 class Node13 {14 public:15 ElementType data;16 Node * next;17 };18 typedef Node * NodePointer;19 20 21 class LinkedList22 {23 public:24 LinkedList();25 virtual ~LinkedList();26 LinkedList(const LinkedList& origlist); // 拷贝构造函数27 LinkedList& operator=(const LinkedList& origlist); // 赋值运算符重载28 void initList(ElementType * arr, int len);29 bool isEmpty();30 bool addNode(const int pos, const ElementType val);31 bool deleteNode(const int pos);32 void displayNodes();33 NodePointer getNode(const int pos);34 int getLenOfList();35 36 private:37 NodePointer head;38 39 };40 41 #endif // LINKEDLIST
实现代码如下：
1 // linkedlist.cpp 2 #include "linkedlist.h" 3 4 LinkedList::LinkedList() 5 { 6 head = NULL; 7 } 8 9 LinkedList::~LinkedList() 10 { 11 NodePointer ptr = head, tmpPtr; 12 while (ptr != NULL) 13 { 14 tmpPtr = ptr; 15 ptr = ptr->next; 16 delete tmpPtr; 17 } 18 } 19 20 LinkedList::LinkedList(const LinkedList& origlist) 21 { 22 head = origlist.head; 23 } 24 25 LinkedList& LinkedList::operator=(const LinkedList& origlist) 26 { 27 head = origlist.head; 28 return *this; 29 } 30 31 void LinkedList::initList(ElementType * arr, int len) 32 { 33 for (int i = 0; i < len; i++) 34 { 35 addNode(i, arr[i]); 36 } 37 } 38 39 bool LinkedList::isEmpty() 40 { 41 return head == NULL; 42 } 43 44 bool LinkedList::addNode(const int pos, const ElementType val) 45 { 46 bool success = true; 47 int len = getLenOfList(); 48 // assert(0 <= pos <= len); 49 if (pos < 0 || pos > len) 50 { 51 cerr << "The node at position " << pos << " you want to add is less than zero or larger than " 52 << "the length of list ." << endl; 53 success = false; 54 throw out_of_range("out_of_range"); 55 } 56 else 57 { 58 NodePointer ptr = new Node(); 59 ptr->data =http://www.mamicode.com/ val; 60 if (pos == 0) // 如果添加的元素在第1个 61 { 62 ptr->next = head; 63 head = ptr; 64 } 65 else // 其他 66 { 67 NodePointer tmpPtr = head; 68 int count = 0; 69 while (tmpPtr != NULL && count < pos - 1) 70 { 71 tmpPtr = tmpPtr->next; 72 count++; 73 } 74 ptr->next = tmpPtr->next; 75 tmpPtr->next = ptr; 76 } 77 78 } 79 80 return success; 81 } 82 83 bool LinkedList::deleteNode(const int pos) 84 { 85 bool success = true; 86 int len = getLenOfList(); 87 if (len == 0) 88 { 89 cerr << "There is no element in the list." << endl; 90 success = false; 91 } 92 else 93 { 94 NodePointer ptr = head, tmpPtr; 95 int count = 0; 96 // assert(0 <= pos <= len); 97 if (pos < 0 || pos > len - 1) 98 { 99 cerr << "The node at position " << pos << " you want to delete is less than zero or larger than "100 << "the length of list ." << endl;101 success = false;102 throw out_of_range("out_of_range");103 }104 else if (len == 1 && pos == 0) // 特殊情况，后边两个条件程序均不能处理，因为head105 // 是要置为NULL的106 {107 head = NULL;108 delete ptr;109 }110 else if (pos == len - 1) // 在链表最后一个元素111 {112 while (ptr != NULL && count < pos - 1)113 {114 ptr = ptr->next;115 count++;116 }117 tmpPtr = ptr->next;118 ptr->next = NULL;119 delete tmpPtr;120 }121 else // 其他122 {123 while (ptr != NULL && count < pos - 1)124 {125 ptr = ptr->next;126 count++;127 }128 tmpPtr = ptr->next;129 ptr->next = tmpPtr->next;130 delete tmpPtr;131 }132 }133 return success;134 }135 136 void LinkedList::displayNodes()137 {138 int len = getLenOfList();139 if (len == 0)140 {141 cerr << "There is no element in the list." << endl;142 }143 else144 {145 NodePointer ptr = head;146 int sequence = 0;147 while (ptr != NULL)148 {149 cout << "Seq: " << sequence << "; Data: " << ptr->data << "."<< endl;;150 ptr = ptr->next;151 sequence++;152 }153 }154 155 }156 157 NodePointer LinkedList::getNode(const int pos)158 {159 int len = getLenOfList();160 if (len == 0)161 {162 cerr << "There is no element in the list." << endl;163 return NULL;164 }165 else166 {167 // assert(0 <= pos <= len);168 if (pos < 0 || pos > len - 1)169 {170 cerr << "The item at position " << pos << " you want to get is less than zero or "171 << "larger than the length of list." << endl;172 throw out_of_range("out_of_range");173 // return NULL;174 }175 else176 {177 NodePointer ptr = head;178 int count = 0;179 while (ptr != NULL && count < pos)180 {181 ptr = ptr->next;182 count++;183 }184 return ptr;185 }186 }187 }188 189 int LinkedList::getLenOfList()190 {191 int len = 0;192 NodePointer ptr = head;193 while (ptr != NULL)194 {195 len++;196 ptr = ptr->next;197 }198 return len;199 }
Boost单元测试代码如下：
1 // BoostUnitTest.cpp 2 #define BOOST_TEST_MODULE LinkedList_Test_Module 3 4 #include "stdafx.h" 5 #include "D:\VSProject\Algorithm\List\LinkedList\SingleLinkedList\SingleLinkedList\SingleLinkedList\linkedlist.h" 6 7 struct LinkedList_Fixture 8 { 9 public: 10 LinkedList_Fixture() 11 { 12 testLinkedList = new LinkedList(); 13 } 14 ~LinkedList_Fixture() 15 { 16 delete testLinkedList; 17 } 18 19 LinkedList * testLinkedList; 20 21 }; 22 23 BOOST_FIXTURE_TEST_SUITE(LinkedList_Test_Suite, LinkedList_Fixture) 24 25 26 BOOST_AUTO_TEST_CASE( LinkedList_Normal_Test ) 27 { 28 // isEmpty -------------------------------------------- 29 BOOST_REQUIRE(testLinkedList->isEmpty() == true); 30 31 // getLenOfList --------------------------------------- 32 BOOST_REQUIRE(testLinkedList->getLenOfList() == 0); 33 34 // addNode & getNode --------------------------------- 35 BOOST_REQUIRE(testLinkedList->addNode(0, 0) == true); 36 BOOST_REQUIRE((testLinkedList->getNode(0))->data =http://www.mamicode.com/= 0); 37 BOOST_REQUIRE((testLinkedList->getNode(0))->next == NULL); 38 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 39 BOOST_REQUIRE(testLinkedList->getLenOfList() == 1); 40 41 BOOST_REQUIRE(testLinkedList->addNode(1, 2) == true); 42 BOOST_REQUIRE((testLinkedList->getNode(1))->data =http://www.mamicode.com/= 2); 43 BOOST_REQUIRE((testLinkedList->getNode(1))->next == NULL); 44 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 45 BOOST_REQUIRE(testLinkedList->getLenOfList() == 2); 46 47 BOOST_REQUIRE(testLinkedList->addNode(1, 1) == true); 48 BOOST_REQUIRE((testLinkedList->getNode(1))->data =http://www.mamicode.com/= 1); 49 BOOST_REQUIRE((testLinkedList->getNode(1))->next != NULL); 50 BOOST_REQUIRE(testLinkedList->isEmpty() == false); 51 BOOST_REQUIRE(testLinkedList->getLenOfList() == 3); 52 53 54 // deleteNode ----------------------------------------- 55 BOOST_REQUIRE(testLinkedList->deleteNode(0) == true); 56 BOOST_REQUIRE(testLinkedList->getLenOfList() == 2); 57 58 BOOST_REQUIRE(testLinkedList->deleteNode(0) == true); 59 BOOST_REQUIRE(testLinkedList->getLenOfList() == 1); 60 61 BOOST_REQUIRE(testLinkedList->deleteNode(0) == true); 62 BOOST_REQUIRE(testLinkedList->getLenOfList() == 0); 63 64 65 // initList ------------------------------------------- 66 int arr[] = { 0, 1, 2 }; 67 int len = sizeof(arr) / sizeof(int); 68 testLinkedList->initList(arr, len); 69 BOOST_REQUIRE(testLinkedList->getLenOfList() == 3); 70 BOOST_REQUIRE((testLinkedList->getNode(0))->data =http://www.mamicode.com/= 0); 71 BOOST_REQUIRE((testLinkedList->getNode(1))->data =http://www.mamicode.com/= 1); 72 BOOST_REQUIRE((testLinkedList->getNode(2))->data =http://www.mamicode.com/= 2); 73 BOOST_REQUIRE((testLinkedList->getNode(2))->next == NULL); 74 75 76 } 77 78 BOOST_AUTO_TEST_CASE(LinkedList_Abnormal_Test) 79 { 80 int arr[] = { 0, 1, 2 }; 81 int len = sizeof(arr) / sizeof(int); 82 testLinkedList->initList(arr, len); 83 84 // addNode ------------------------------------------- 85 BOOST_REQUIRE_THROW(testLinkedList->addNode(-1, 100), out_of_range); 86 BOOST_REQUIRE_THROW(testLinkedList->addNode(10, 100), out_of_range); 87 88 // deleteNode ---------------------------------------- 89 BOOST_REQUIRE_THROW(testLinkedList->deleteNode(-1), out_of_range); 90 BOOST_REQUIRE_THROW(testLinkedList->deleteNode(10), out_of_range); 91 92 // getNode -------------------------------------------- 93 BOOST_REQUIRE_THROW(testLinkedList->getNode(-1), out_of_range); 94 BOOST_REQUIRE_THROW(testLinkedList->getNode(10), out_of_range); 95 96 } 97 98 BOOST_AUTO_TEST_CASE(LinkedList_CopyConstuctor_Test) 99 {100 int arr[] = { 0, 1, 2 };101 int len = sizeof(arr) / sizeof(int);102 testLinkedList->initList(arr, len);103 104 LinkedList * testLinkedList2(testLinkedList);105 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 3);106 BOOST_REQUIRE((testLinkedList2->getNode(0))->data =http://www.mamicode.com/= 0);107 BOOST_REQUIRE((testLinkedList2->getNode(1))->data =http://www.mamicode.com/= 1);108 BOOST_REQUIRE((testLinkedList2->getNode(2))->data =http://www.mamicode.com/= 2);109 BOOST_REQUIRE((testLinkedList2->getNode(2))->next == NULL);110 }111 112 BOOST_AUTO_TEST_CASE(LinkedList_EqualOperator_Test)113 {114 int arr[] = { 0, 1, 2 };115 int len = sizeof(arr) / sizeof(int);116 testLinkedList->initList(arr, len);117 118 LinkedList * testLinkedList2 = testLinkedList;119 BOOST_REQUIRE(testLinkedList2->getLenOfList() == 3);120 BOOST_REQUIRE((testLinkedList2->getNode(0))->data =http://www.mamicode.com/= 0);121 BOOST_REQUIRE((testLinkedList2->getNode(1))->data =http://www.mamicode.com/= 1);122 BOOST_REQUIRE((testLinkedList2->getNode(2))->data =http://www.mamicode.com/= 2);123 BOOST_REQUIRE((testLinkedList2->getNode(2))->next == NULL);124 }125 126 BOOST_AUTO_TEST_SUITE_END()
下一篇：双链表。
单链表（兼具Boost单元测试）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。