C++ 实现静态单链表的实例
利用数组实现的静态单链表，与严蔚敏书实现略有不同，不另设回收空间。有任何BUG或错误，希望各位朋友多多反馈~~感激不尽
/* Author : Moyiii * Mail: lc09@vip.qq.com * 静态链表实现，仅作学习之用，当然如果 * 你想拿去用，随你好啦。 */ #include <iostream> using namespace std; #define MAX_LIST_SIZE 100 class Node { public: int data; int cur; }; class SLinkList { public: SLinkList(); //和普通的线性链表区别不是很大。除了两个分配 //和回收节点空间的函数，具体算法请参考课本或 //网络资料 int newNode(); bool deleteNode(int pos); bool insertElem(int pos, int elem); bool deleteElem(int pos); int& getElem(int pos); int getLength(); bool isEmpty(); void print(); void clear(); private: int head;//这个可以不要，默认等于0 int space; int length; Node *elems; }; SLinkList :: SLinkList() { // 0号位置为头几点，不可以更改，初始指向自己 // 从1~MAXLENGTH为可分配节点，最初由space管理 elems = new Node[MAX_LIST_SIZE]; if(!elems) { cout << "Malloc failed!" << endl; } head = space = length = 0; for(int i = 0; i < MAX_LIST_SIZE; ++i) { elems[i].data = i; elems[i].cur = i + 1; } elems[MAX_LIST_SIZE - 1].cur = 0; elems[0].cur = 0; space = 1; } //从space指向的备用节点链表中取下一个节点 int SLinkList :: newNode() { if(space == 0) { cout << "Space is full!" << endl; return 0; } int pos = space; space = elems[space].cur; elems[pos].cur = 0; return pos; } //回收节点空间 bool SLinkList :: deleteNode(int pos) { if(pos == 0) { cout << "Free space Error!" << endl; return false; } elems[pos].cur = space; space = pos; return true; } //插入节点，思路类似，找到被删除节点的前一个节点 //然后更改指向 bool SLinkList :: insertElem(int pos, int elem) { if(length == MAX_LIST_SIZE) { cout << "Space is Full" << endl; return false; } if(pos < 1 || pos > length + 1) { cout << "Insert Over Bound" << endl; return false; } int index = head; for(int i = 1; i <= pos - 1; ++i) { index = elems[index].cur; } int node = newNode(); if(node == 0) { cout << "Space malloc failed" << endl; return false; } elems[node].data = elem; elems[node].cur = elems[index].cur; elems[index].cur = node; length++; return true; } //一回事，注意把删除的节点回收给space bool SLinkList :: deleteElem(int pos) { if(pos < 1 || pos > length) { cout << "Delete Node over Bound!" << endl; return false; } int index = head; for(int i = 1; i <= pos - 1; ++i) { index = elems[index].cur; } int node = elems[index].cur; elems[index].cur = elems[node].cur; deleteNode(node); length--; return true; } void SLinkList :: print() { int index = elems[head].cur; while(index != 0) { cout << elems[index].data << " "; index = elems[index].cur; } cout << endl; return; } int SLinkList :: getLength() { return length; } bool SLinkList :: isEmpty() { if(length == 0) { return true; } else { return false; } } int& SLinkList :: getElem(int pos) { int index = head; for(int i = 1; i <= pos; ++i) { index = elems[index].cur; } return elems[index].data; } void SLinkList :: clear() { for(int i = 0; i < MAX_LIST_SIZE; ++i) { elems[i].data = i; elems[i].cur = i + 1; } elems[MAX_LIST_SIZE - 1].cur = 0; elems[0].cur = 0; space = 1; } int main() { //测试数据，测试插入删除空间是否溢出 SLinkList myList; for(int i = 1; i <= 105; ++i) { myList.insertElem(1,i); } //myList.print(); for(int i = 1; i <= 105; ++i) { myList.deleteElem(1); } //myList.print(); //普通测试 for(int i = 1; i <= 10; ++i) { myList.insertElem(1,i); } myList.print(); cout << "Length= " << myList.getLength() <<endl; myList.deleteElem(5); myList.print(); cout << "Length= " << myList.getLength() <<endl; cout << myList.isEmpty() << endl; int &elem = myList.getElem(3); elem = 99; myList.print(); myList.clear(); myList.print(); return 0; }
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
年岁有加，并非垂老，理想丢弃，方堕暮年。
