什么是静态链表
就是用数组来描述链表，数组中的元素由两个数据域组成，data和cur，你可以把数组的元素设想成有两个元素的结构体。数据域data用来存放数据元素，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。这种用数组描述的链表叫做静态链表，也叫游标实现法。为了便于数据的插入，这个静态数组，我们通常会建的大一些。
另外数组的第一个元素和最后一个元素作为特殊元素处理，不存数据。通常把未被使用的数组元素称为备用链表。而数组的第一个元素，即下标为0的的元素的cur就存放第一个空闲结点的下标，最后一个元素的cur则存放这第一个有数值的元素的下标（相当于首元结点），相当于单链表的头结点作用，当整个链表为空是，存放0。尾结点的cur的值也为0。
静态链表的C++实现
代码示例如下：
#ifndef STATICLINKLIST_H_
#define STATICLINKLIST_H_
template
struct StaticNode
{
T data;
int iCur{ 0 };
};
/************************************************************************/
/* 静态链表通过数组实现，数组中第一个位置不存数据元素，它的cur指向数组中第一个不存数据的*/
/*位置，数组最后一个位置，数据域不存值，cur（游标）部分存放数组中第一个有数据元素的位置，*/
/*如果静态链表为空，则cur的值为0，尾结点的cur也为0 */
/************************************************************************/
template
class StaticLinkList
{
public:
StaticLinkList(unsigned int iMaxSize);
//获取指定位置上的元素
bool getValue(const int iPosition,T &value);
unsigned int size()
{
return m_iCurrLen;
}
bool empty()
{
if (0 == m_pStaticList[m_iMaxSize-1].iCur)
{
return true;
}
return false;
}
void clear();
unsigned int maxSize()
{
return m_iRealMaxSize;
}
bool full()
{
if (m_iRealMaxSize == m_iCurrLen)
{
return true;
}
return false;
}
//寻找可以插入的位置
int findInsertSpace();
//回收指定位置的空间（就是把将要删除的元素，添加到备用链表中）
void callBackSpace(int iPosition);
//在指定位置插入元素
bool insert(int iPosition, const T value);
//删除指定位置的元素
bool remove(int iPosition);
~StaticLinkList();
private:
int m_iMaxSize; //静态链表最大的最大度
unsigned int m_iRealMaxSize; //在构造函数中赋值，m_iRealMaxSize = m_iMaxSize -3;
int m_iCurrLen{ 0 }; //目前已容纳的数据元素的数量
StaticNode * m_pStaticList{ nullptr }; //静态链表存放数据元素的地方
};
#endif
template
StaticLinkList::StaticLinkList(unsigned int iMaxSize):m_iMaxSize(iMaxSize)
{
m_iMaxSize = m_iMaxSize + 2; //为了防止参数误传为0，确保有三个位置
m_iRealMaxSize = m_iMaxSize - 2; //在判断是否还有空闲空间以供插入时使用
m_pStaticList = new StaticNode[m_iMaxSize];
//数组0位置存放的内容：要求数据域不存储数据，游标存储数组中第一个空闲位置的下标
for (int iLoopVariable =0;iLoopVariable < m_iMaxSize -1;++iLoopVariable)
{
m_pStaticList[iLoopVariable].iCur = iLoopVariable + 1;
}
//数组最后一个位置存放的内容：相当于单链表的头结点，当静态链表为空时，其游标值为0，不为空时，游标值为第一个有元素的结点，数据域不存值
m_pStaticList[m_iMaxSize - 1].iCur = 0;
}
template
bool StaticLinkList::getValue(const int iPosition,T &value)
{
if (1> iPosition || iPosition > m_iCurrLen +1)
{
std::cout << "Invaild Index!" << std::endl;
return false;
}
int k = m_pStaticList[m_iMaxSize - 1].iCur;
for (int i =1; i<=m_iCurrLen;++i)
{
if (k == iPosition)
{
value = m_pStaticList[k].data;
return true;
}
k = m_pStaticList[k].iCur;
}
return false;
}
template
void StaticLinkList::clear()
{
for (int iLoopVariable = 0; iLoopVariable < m_iMaxSize - 1; ++iLoopVariable)
{
m_pStaticList[iLoopVariable].iCur = iLoopVariable + 1;
}
//数组最后一个位置存放的内容：相当于单链表的头结点，当静态链表为空时，其游标值为0，不为空时，游标值为第一个有元素的结点，数据域不存值
m_pStaticList[m_iMaxSize - 1].iCur = 0;
m_iCurrLen = 0;
}
template
//为了在数组中找到一个可以插入的位置，我们把未插入数据的位置和已经删除的位置视为一个备用链表
int StaticLinkList::findInsertSpace()
{
int i = m_pStaticList[0].iCur;
if (m_pStaticList[0].iCur)
{
m_pStaticList[0].iCur = m_pStaticList[i].iCur;
}
//根据构造函数中给每个游标的赋值可以看出，当游标为0号位置的游标为0时，链表已经满了
return i;
}
template
void StaticLinkList::callBackSpace(int iPosition)
{
//这个结点要删除意味着它将成为空闲结点，在整个静态链表中，我们唯一知道的空闲单元就是0位置的游标所指向的位置
m_pStaticList[iPosition].iCur = m_pStaticList[0].iCur;
m_pStaticList[0].iCur = iPosition;
}
template
bool StaticLinkList::insert(int iPosition, const T value)
{
//注意，由于静态链表设计的特殊性，它实际存储数据元素的位置是从下标为1的位置开始的，而最后一个位置不存储数据元素
//根据这个规则，要对插入位置的合法性做个判断，插入位置必须是在链表之中或者紧邻着尾结点的位置，
//这里蕴含一个编程假设，数据长度一定是小于最大长度的
if (iPosition <1 || iPosition > m_iCurrLen+1)
{
std::cout << "Invaild Index!" << std::endl;
return false;
}
int k = m_iMaxSize - 1;
int i = findInsertSpace();
if (i)
{
//这里相当于是new出了一个元素
m_pStaticList[i].data = value;
//接下来找到目标位置的前驱
for (int l = 1;l<=i-1;l++)
{
k = m_pStaticList[k].iCur;
}
//考虑下这里的亮点，当插入位置为1时，下面这行代码实际上使得新插入的结点成为尾结点，当插入位置大于1时，尾结点的情况是适用的
m_pStaticList[i].iCur = m_pStaticList[k].iCur;
m_pStaticList[k].iCur = i;
++m_iCurrLen;
return true;
}
return false;
}
template
bool StaticLinkList::remove(int iPosition)
{
//同样先验证删除位置的合法性
if (1> iPosition || iPosition > m_iCurrLen+1)
{
return false;
}
int k = m_iMaxSize - 1;
//找到指定位置的前驱
for (int l =1; l<= iPosition-1;++l)
{
k = m_pStaticList[k].iCur;
}
//令i的前驱节点的游标指向i的后继结点
m_pStaticList[k].iCur = m_pStaticList[iPosition].iCur;
//回收iPositon结点
callBackSpace(iPosition);
--m_iCurrLen;
return true;
}
template
StaticLinkList::~StaticLinkList()
{
if (nullptr != m_pStaticList)
{
delete[] m_pStaticList;
m_pStaticList = nullptr;
}
}
静态链表的优缺点
- 在插入和删除操作时，只需要修改游标，不要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
- 没有解决连续存储分配带来的表长难以确定的问题
- 失去了顺序存储结构的随机存储特性
循环链表
循环链表：将单链表中尾节点的指针域由空指针改为指向头结点，就使整个单链表形成了一个环。这种头尾相连的单链表称为单循环链表，简称循环链表。
循环链表的优势在可以从任意一个结点出发，访问到这个链表中的所有结点。
循环链表和单链表的主要差异是循环条件的判断，原来是判断尾结点的指针域是否为空，来检查是否达到尾结点，现在检查尾结点的指针域是否指向头结点，如果指向头结点，则到达链表的尾部。循环链表的判空条件是，检查头结点的指针域是否指向它自己，其它操作，与单链表完全一样。
在单链表中，我们使用头指针来表示一个链表，此时查找首元结点的时间复杂度是O(n)，查找尾结点的时间复杂度是O(n)，现在我们用尾指针rear来表示一个链表，尾指针指向链表的尾结点，加上循环链表的特性，可以使得访问首元结点和尾结点的时间复杂度都是O(1)，这在链表的具体实现上需要有一点不同，我们将保存一个尾指针，使其总是指向尾结点。（就是在前面的单链表实现上多一个成员变量罢了，注意它的更新）
双向链表
单向链表的一个问题是，查找前驱节点，需要的时间复杂度是O(n)。为了解决这个问题，出现了双向链表。双向链表是在单链表的每个结点中，再设置一个指向其前驱节点的指针。所以，双向链表的结点包含两个指针域和一个数据域。一个指针域直接指向直接后继，另一个指针域直接指向其直接前驱。
双向循环链表：
判空条件是：前驱指针后后继指针都指向头结点自己。
判断到达尾部的条件是，后继指针指向了头结点。
双向链表的查找、获取元素位置、求长度都和单向链表一致，但是它可以反向遍历数据结构，因为它有两个指针，所以在插入或者删除的时候需要改变两个指针变量。
双向链表对某个结点的前后结点的操作带来了方便。
转载请注明出处 静态链表
