静态链表的C++实现数据结构和算法

静态链表是使用数组实现的可以快速插入和删除数据的链表，静态链表和链式单链表比的缺点在于链表的长度只能初始化设置好，而相对应普通的顺序存储的链表，静态链表不能实现快速的读写任意的元素。
当然静态链表给了我们一种思考方式，当我们在特定状态下，不能使用指针操作时，我们可以使用一种替代指针的方法，静态链表使用的cur来表示当前节点的下一个节点的下标。
【静态链表的C++实现】

#pragma once #define MAXSIZE 1000template class StaticList { public: typedef struct { EleType data; int cur; }Node; StaticList(); ~StaticList(); bool Insert(const EleType& e, int index = 1); bool Delete( EleType& e, int index = 1); void Show()const; private: int NewSpace(); //返回list中一个可以用的空间下标 void DeleteSpace(int index); //删除list中的index元素 bool Empty()const; bool Full()const; Node StList[MAXSIZE]; int Length; };

#include "StaticList.h" #include using namespace std; template StaticList::StaticList() :Length(0) { for (int i = 0; i < MAXSIZE - 1; ++i) { StList[i].cur = i + 1; } StList[MAXSIZE - 1].cur = 0; }template StaticList::~StaticList() {}template bool StaticList::Insert(const EleType& e, int index /*= 1*/) { if (Full())//如果为满，则不插入数据 { cout << "Can't insert element to a full List!\n"; return false; } if (index<1||index>Length+1)//如果插入点的下标不合法，返回false { cout << "The invalid index!\n"; return false; } int k = NewSpace(); //返回一个可以插入的节点的下标 int j = MAXSIZE - 1; if (k)//如果返回下标不为0 { StList[k].data = https://www.it610.com/article/e; //将返回位置的数据设置成e for (int i = 1; i <= index - 1; ++i)//找到插入节点的前一个节点的下标 { j = StList[j].cur; } StList[k].cur = StList[j].cur; //将插入节点的cur设置成插入位置前一个节点的cur StList[j].cur = k; //将插入位置的前一个节点的cur设置成k，实现把第k个节点插入到index-1个节点后，实现把第K个节点插入到第index个位置 ++Length; //链表长度加一 return true; } return false; }template bool StaticList::Delete(EleType& e, int index /*= 1*/) { if (Empty())//如果链表为空，不执行删除操作 { cout << "Can't delete element in a empty list!\n"; return false; } if (index<1 || index>Length )//如果删除的位置不合法，返回false { cout << "The invalid index!\n"; return false; } int k = MAXSIZE - 1; int i = 1; for (; i <= index - 1; ++i)//找到第index-1个节点k { k = StList[k].cur; } i = StList[k].cur; //i为第index个节点的下标 StList[k].cur = StList[i].cur; //将第index-1个节点的cur设置成第index个节点的cur，实现了把第index个节点排除在链表之外 e = StList[i].data; //返回第index个节点的data给e DeleteSpace(i); //回收第index个节点的空间 --Length; //链表长度减一 return true; }template void StaticList::Show() const { if (Empty()) { cout << "The List is Empty!\n"; return; } int k = StList[MAXSIZE - 1].cur; cout << "The list is :\n"; for (int i = 1; i <= Length; ++i) { cout << StList[k].data << " "; k = StList[k].cur; } cout << endl; }template bool StaticList::Full() const { if (Length > MAXSIZE - 2)//保证StList[0]和StList[MAXSIZE-1]不被插入数据覆盖 { return true; } return false; }template bool StaticList::Empty() const { return(Length == 0); }template void StaticList::DeleteSpace(int index) { StList[index].cur = StList[0].cur; //将要删除的节点加入到空闲节点最前 StList[0].cur = index; //把该节点设置成第一个可用的空闲节点 }template int StaticList::NewSpace() { int i = StList[0].cur; //第一个可用的空闲姐弟那 if (StList[0].cur)//如果该空闲节点可用 { StList[0].cur = StList[i].cur; //设置下一次第一个可用的空闲节点为返回节点的下一个节点 } return i; //返回可用节点的下标 }

#include "StaticList.cpp"int main() { StaticList TestList; TestList.Insert(12); TestList.Insert(12); TestList.Insert(34); TestList.Insert(23); TestList.Insert(12); TestList.Insert(99,4); TestList.Show(); int m = 0; TestList.Delete(m,7); cout << "____________" << m << "_______________\n"; TestList.Show(); return 0; }