C++ 实现静态单链表的实例

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; 
} 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C++  # 实现静态单链表  # 静态单链表  # C++实现LeetCode(141.单链表中的环)  # C++实现LeetCode(142.单链表中的环之二)  # C++单链表实现大数加法  # C++实现单链表的构造  # C++使用模板实现单链表（类外实现）  # C++使用模板实现单链表  # 利用C++简单实现顺序表和单链表的示例代码  # C++中单链表的建立与基本操作  # C++编程语言实现单链表详情  # 链表  # 不可以  # 你想  # 感激不尽  # 希望能  # 几点  # 谢谢大家  # 之用  # 好啦  # 拿去  # 仅作  # 随你  # 请参考  # 中取  # 有任何  # 最初  # 测试数据  # namespace  # std  # bool 

相关文章： 如何访问已购建站主机并解决登录问题？  宁波自助建站系统如何快速打造专业企业网站？  如何在Golang中处理模块冲突_解决依赖版本不兼容问题  如何制作公司的网站链接,公司想做一个网站，一般需要花多少钱？  如何通过VPS搭建网站快速盈利？  如何挑选最适合建站的高性能VPS主机？  制作无缝贴图网站有哪些,3dmax无缝贴图怎么调？  html制作网站的步骤有哪些,iapp如何添加网页？  建站VPS配置与SEO优化指南：关键词排名提升策略  网站建设制作需要多少钱费用,自己做一个网站要多少钱，模板一般多少钱？  网站制作知乎推荐,想做自己的网站用什么工具比较好？  如何高效完成独享虚拟主机建站？  高防服务器租用首荐平台，企业级优惠套餐快速部署  成都品牌网站制作公司,成都营业执照年报网上怎么办理？  哈尔滨网站建设策划,哈尔滨电工证查询网站？  建站主机是否等同于虚拟主机？  建站之星安装后界面空白如何解决？  网站制作大概多少钱一个,做一个平台网站大概多少钱？  建站之星如何优化SEO以实现高效排名？  阿里云网站搭建费用解析：服务器价格与建站成本优化指南  Android使用GridView实现日历的简单功能  nginx修改上传文件大小限制的方法  清单制作人网站有哪些,近日“兴风作浪的姑奶奶”引起很多人的关注这是什么事情？  建站之星各版本价格是多少？  建站之星安装提示数据库无法连接如何解决？  免费制作小说封面的网站有哪些,怎么接网站批量的封面单？  美食网站链接制作教程视频,哪个教做美食的网站比较专业点？  如何批量查询域名的建站时间记录？  学生网站制作软件,一个12岁的学生写小说，应该去什么样的网站？  定制建站平台哪家好？企业官网搭建与快速建站方案推荐  微信小程序 input输入框控件详解及实例（多种示例）  宝华建站服务条款解析：五站合一功能与SEO优化设置指南  详解ASP.NET 生成二维码实例（采用ThoughtWorks.QRCode和QrCode.Net两种方式）  建站之星代理如何获取技术支持？  建设网站制作价格,怎样建立自己的公司网站？  建站之星如何防范黑客攻击与数据泄露？  天津个人网站制作公司,天津网约车驾驶员从业资格证官网？  如何通过智能用户系统一键生成高效建站方案？  JS中使用new Date(str)创建时间对象不兼容firefox和ie的解决方法(两种)  制作网站的公司有哪些,做一个公司网站要多少钱？  如何选择PHP开源工具快速搭建网站？  小型网站制作HTML,*游戏网站怎么搭建？  家庭服务器如何搭建个人网站？  如何用美橙互联一键搭建多站合一网站？  零服务器AI建站解决方案：快速部署与云端平台低成本实践  如何在七牛云存储上搭建网站并设置自定义域名？  浅析上传头像示例及其注意事项  手机钓鱼网站怎么制作视频,怎样拦截钓鱼网站。怎么办？  如何确保西部建站助手FTP传输的安全性？  高端云建站费用究竟需要多少预算？