C++ 实现静态单链表的实例
发布时间:2020-12-16 05:08:38 所属栏目:百科 来源:网络整理
导读:C++ 实现静态单链表的实例 利用数组实现的静态单链表,与严蔚敏书实现略有不同,不另设回收空间。有任何BUG或错误,希望各位朋友多多反馈~~感激不尽 /* Author : Moyiii * Mail: lc09@vip.qq.com * 静态链表实现,仅作学习之用,当然如果 * 你想拿去用,随你
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; } 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- ruby-on-rails – 是否可以在Ruby on Rails 3中登录到两个不
- 正则表达式 – 优雅R功能:混合大小写,以句点分隔,以分隔小
- Flash务实主义(五)——AS3的垃圾回收
- objective-c – 在copyWithZone中为可变子类返回[self reta
- ruby-on-rails-3 – 如何在Prawn表中创建粗体标题
- swift:使用协议protocol设置颜色,UIImage的切圆角ImageWit
- ruby-on-rails-3 – 现有列的change_column_null
- ruby-on-rails – 用Ransack一次搜索多个模型
- AJAX请求 $.ajax方法的使用
- ORACLE数据库环境故障数据恢复方案