"《算法导论》之‘线性表’"：基于数组实现的单链表
2024-10-10 22:04:49
对于单链表，我们大多时候会用指针来实现（可参考基于指针实现的单链表）。现在我们就来看看怎么用数组来实现单链表。
1. 定义单链表中结点的数据结构
typedef int ElementType;
class NodeType
{
public:
ElementType data;
int next;
};
该结点包括了两个元素，其一是数据，另一个是指向下一个结点的“指针”（在这篇文章中实际上是指用于实现单链表的数组的下标。）
2. 定义一个的数组
const int CAPACITY = ;
NodeType node[CAPACITY];
在内存中该数组的结构如下图：
3. 定义指向单链表第1个结点的“指针”
int head;
4. 一个简单的单链表例子
我们假设单链表只有3个结点，并且3个结点从左到右分别位于数组node中第0、1、2位置，如下图：
head指向链表中的第1个结点。该结点存储于数组node的第0位置，data为111，next指向下一结点。其他以此类推。
需要注意的是链表的中最后一个结点（即上图中的第3个结点）的next被置为-1，表示不指向任何结点。
更为重要的是，这三个结点是可以位于数组node中的任一位置的，只要他们之间保持这种链接的关系。
5. 实际程序实现
在实际程序实现中，为了便于判断数组中哪一个元素已经被使用，我在原单链表的结点数据结构中又添加了一个判断位，如下：
typedef int ElementType;
class NodeType
{
public:
NodeType() { data = ; next = NULL_VALUE; isFree = true; };
~NodeType() {};
ElementType data;
int next;
bool isFree; // 标志位，为true表示该结点可用，反之不可用
};
其余的程序摘录如下：
#ifndef SINGLELINKEDLIST
#define SINGLELINKEDLIST #include <iostream>
#include <cassert>
using namespace std; const int CAPACITY = ;
const int NULL_VALUE = -; typedef int ElementType;
class NodeType
{
public:
NodeType() { data = ; next = NULL_VALUE; isFree = true; };
~NodeType() {};
ElementType data;
int next;
bool isFree; // 标志位，为true表示该结点可用，反之不可用
}; class LinkedList
{
public:
LinkedList();
virtual ~LinkedList();
void initList(ElementType * arr, int len);
bool isEmpty();
int findFreeNode();
bool addNode(const int pos, const ElementType val);
bool deleteNode(const int pos);
void displayNodes();
NodeType getNode(const int pos);
int getLenOfList(); private:
NodeType node[CAPACITY];
int head; }; #endif;
linkedlist.h
#include "linkedlist.h" LinkedList::LinkedList()
{
head = NULL_VALUE;
} LinkedList::~LinkedList()
{
for (int i = ; i < CAPACITY; i++)
{
node[i].data = ;
node[i].next = NULL_VALUE;
node[i].isFree = true;
}
} void LinkedList::initList(ElementType * arr, int len)
{
for (int i = ; i < len; i++)
{
int tmp = arr[i];
addNode(i, tmp);
}
} bool LinkedList::isEmpty()
{
return head == NULL_VALUE;
} int LinkedList::findFreeNode()
{
int i = ;
while (node[i].isFree == false)
{
i++;
if (i == CAPACITY) // 如果找不到可用的结点，返回NULL_VALUE
{
return NULL_VALUE;
}
}
return i;
} bool LinkedList::addNode(const int pos, const ElementType val)
{
bool success = true;
int len = getLenOfList();
if (len == CAPACITY)
{
cerr << "There is no space in the list." << endl;
success = false;
}
else
{
// assert(0 <= pos <= CAPACITY);
if (pos < || pos > len)
{
cerr << "The node at position " << pos << " you want to add is less than zero or larger than "
<< "the capacity of list ." << endl;
success = false;
throw out_of_range("out_of_range");
}
else
{
int freeNode = findFreeNode();
node[freeNode].data = val;
node[freeNode].isFree = false;
if (pos == ) // 如果添加的元素在第1个
{
node[freeNode].next = head;
head = freeNode;
}
else // 其他
{
int ptr = head;
int count = ;
while (ptr != NULL_VALUE && count < pos - )
{
ptr = node[ptr].next;
count++;
}
node[freeNode].next = node[ptr].next;
node[ptr].next = freeNode;
}
}
}
return success;
} bool LinkedList::deleteNode(const int pos)
{
bool success = true;
int len = getLenOfList();
if (len == )
{
cerr << "There is no element in the list." << endl;
success = false;
}
else
{
int ptr = head, tmpPtr;
int count = ;
// assert(0 <= pos <= len);
if (pos < || pos > len - )
{
cerr << "The node at position " << pos << " you want to delete is less than zero or larger than "
<< "the length of list ." << endl;
success = false;
throw out_of_range("out_of_range");
}
else if (pos == ) // 在链表第一个位置
{
head = node[head].next;
node[ptr].data = ;
node[ptr].next = NULL_VALUE;
node[ptr].isFree = true;
}
else if (pos == len - ) // 在链表最后一个位置
{
while (ptr != NULL && count < pos - )
{
ptr = node[ptr].next;
count++;
}
tmpPtr = node[ptr].next;
node[ptr].next = NULL_VALUE;
// reset the deleted one
node[tmpPtr].data = ;
node[tmpPtr].next = NULL_VALUE;
node[tmpPtr].isFree = true;
}
else // 其他
{
while (ptr != NULL && count < pos - )
{
ptr = node[ptr].next;
count++;
}
tmpPtr = node[ptr].next;
node[ptr].next = node[tmpPtr].next;
// reset the deleted one
node[tmpPtr].data = ;
node[tmpPtr].next = NULL_VALUE;
node[tmpPtr].isFree = true;
}
}
return success;
} void LinkedList::displayNodes()
{
int ptr = head;
int sequence = ;
while (ptr != NULL_VALUE)
{
cout << "Seq: " << sequence << "; Data: " << node[ptr].data << endl;
ptr = node[ptr].next;
sequence++;
}
} NodeType LinkedList::getNode(const int pos)
{
NodeType tmpNode;
int len = getLenOfList();
if (len == )
{
cerr << "There is no element in the list." << endl;
}
else
{
// assert(0 <= pos <= len);
if (pos < || pos > len - )
{
cerr << "The item at position " << pos << " you want to get is less than zero or "
<< "larger than the length of list." << endl;
throw out_of_range("out_of_range");
// return tmpNode;
}
else
{
int ptr = head;
int count = ;
while (ptr != NULL_VALUE && count < pos)
{
ptr = node[ptr].next;
count++;
}
tmpNode.data = node[ptr].data;
tmpNode.next = node[ptr].next;
tmpNode.isFree = node[ptr].isFree;
}
} return tmpNode;
} int LinkedList::getLenOfList()
{
int ptr = head;
int len = ;
while (ptr != NULL_VALUE)
{
ptr = node[ptr].next;
len++;
} return len;
}
linkedlist.cpp
Boost单元测试代码测试如下：
#define BOOST_TEST_MODULE LinkedList_Test_Module #include "stdafx.h"
#include "D:\VSProject\Algorithm\List\LinkedList\SingleLinkedList_BasedOnArray\SingleLinkedList\SingleLinkedList\linkedlist.h" struct LinkedList_Fixture
{
public:
LinkedList_Fixture()
{
testLinkedList = new LinkedList();
}
~LinkedList_Fixture()
{
delete testLinkedList;
} LinkedList * testLinkedList;
}; BOOST_FIXTURE_TEST_SUITE(LinkedList_Test_Suite, LinkedList_Fixture) BOOST_AUTO_TEST_CASE( LinkedList_Normal_Test )
{
// isEmpty -------------------------------------------
BOOST_REQUIRE(testLinkedList->isEmpty() == true); // getLenOfList --------------------------------------
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); // findFreeNode --------------------------------------
BOOST_REQUIRE(testLinkedList->findFreeNode() == ); // addNode & getNode ---------------------------------
BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE((testLinkedList->getNode()).next == NULL_VALUE);
BOOST_REQUIRE((testLinkedList->getNode()).isFree == false);
BOOST_REQUIRE(testLinkedList->isEmpty() == false);
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE((testLinkedList->getNode()).next == NULL_VALUE);
BOOST_REQUIRE((testLinkedList->getNode()).isFree == false);
BOOST_REQUIRE(testLinkedList->isEmpty() == false);
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); BOOST_REQUIRE(testLinkedList->addNode(, ) == true);
BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE((testLinkedList->getNode()).next != NULL_VALUE);
BOOST_REQUIRE((testLinkedList->getNode()).isFree == false);
BOOST_REQUIRE((testLinkedList->getNode()).next == NULL_VALUE);
BOOST_REQUIRE(testLinkedList->isEmpty() == false);
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); // deleteNode -----------------------------------------
BOOST_REQUIRE(testLinkedList->deleteNode() == true);
BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); BOOST_REQUIRE(testLinkedList->deleteNode() == true);
BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); BOOST_REQUIRE(testLinkedList->deleteNode() == true);
BOOST_REQUIRE(testLinkedList->getLenOfList() == ); // initList -------------------------------------------
int arr[] = { , , };
int len = sizeof(arr) / sizeof(int);
testLinkedList->initList(arr, len);
BOOST_REQUIRE(testLinkedList->getLenOfList() == );
BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE((testLinkedList->getNode()).next == ); BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE((testLinkedList->getNode()).next == ); BOOST_REQUIRE((testLinkedList->getNode()).data == );
BOOST_REQUIRE((testLinkedList->getNode()).next == NULL_VALUE);
} BOOST_AUTO_TEST_CASE(LinkedList_Abnormal_Test)
{
int arr[] = { , , };
int len = sizeof(arr) / sizeof(int);
testLinkedList->initList(arr, len); // addNode -------------------------------------------
BOOST_REQUIRE_THROW(testLinkedList->addNode(-, ), out_of_range);
BOOST_REQUIRE_THROW(testLinkedList->addNode(, ), out_of_range); // deleteNode ----------------------------------------
BOOST_REQUIRE_THROW(testLinkedList->deleteNode(-), out_of_range);
BOOST_REQUIRE_THROW(testLinkedList->deleteNode(), out_of_range); // getNode --------------------------------------------
BOOST_REQUIRE_THROW(testLinkedList->getNode(-), out_of_range);
BOOST_REQUIRE_THROW(testLinkedList->getNode(), out_of_range); } BOOST_AUTO_TEST_SUITE_END()
BoostUnitTest.cpp
本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.
最新文章
- UML
- js 控制文本只能输入数字
- mvc+webapi 项目架构
- MySQL Replication需要注意的问题
- QT信号槽机制
- 1022. D进制的A+B (20)
- phpweb成品网站最新版(注入、上传、写shell)
- CPU tick counter
- 递归，动态规划，找最短路径，Help Jimmy
- hdoj-2023
- B.xml
- P3381: [Usaco2004 Open]Cave Cows 2 洞穴里的牛之二
- Makefile.am讲解
- Android Wear开发 - 数据通讯 - 第二节 : 数据的发送与接收
- USACO 1.4 ariprog 解题报告
- C#中反射的概念及其使用（转）
- loadrunner 录制TCP协议脚本操作
- 第一节：ASP.NET开发环境配置
- [CQOI2018]异或序列
- Linux网络那点事（CentOS、Ubuntu、Kali）