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 

相关文章： 制作网站外包平台,自动化接单网站有哪些？  上海制作企业网站有哪些,上海有哪些网站可以让企业免费发布招聘信息？  小程序网站制作需要准备什么资料,如何制作小程序？  巅云智能建站系统：可视化拖拽+多端适配+免费模板一键生成  网站专业制作公司,网站编辑是做什么的？好做吗？工作前景如何？  制作证书网站有哪些,全国城建培训中心证书查询官网？  如何在万网主机上快速搭建网站？  如何在建站之星网店版论坛获取技术支持？  C++如何使用std::optional？（处理可选值）  制作网站的基本流程,设计网站的软件是什么？  如何选择PHP开源工具快速搭建网站？  电商网站制作价格怎么算,网上拍卖流程以及规则？  如何快速上传建站程序避免常见错误？  实例解析angularjs的filter过滤器  c++怎么使用类型萃取type_traits_c++ 模板元编程类型判断【方法】  如何选择建站程序？包含哪些必备功能与类型？  网站制作费用多少钱,一个网站的运营，需要哪些费用？  江苏网站制作公司有哪些,江苏书法考级官方网站？  个人网站制作流程图片大全,个人网站如何注销？  公司网站建设制作费用,想建设一个属于自己的企业网站，该如何去做？  定制建站价位费用解析与套餐推荐全攻略  网站网页制作专业公司,怎样制作自己的网页？  小自动建站系统：AI智能生成+拖拽模板，多端适配一键搭建  香港服务器网站生成指南：免费资源整合与高速稳定配置方案  品牌网站制作公司有哪些,买正品品牌一般去哪个网站买？  高防服务器租用首荐平台，企业级优惠套餐快速部署  专业型网站制作公司有哪些,我设计专业的，谁给推荐几个设计师兼职类的网站？  如何自定义建站之星模板颜色并下载新样式？  股票网站制作软件,网上股票怎么开户？  怀化网站制作公司,怀化新生儿上户网上办理流程？  微信小程序 input输入框控件详解及实例（多种示例）  如何快速搭建个人网站并优化SEO？  如何选择适配移动端的WAP自助建站平台？  弹幕视频网站制作教程下载,弹幕视频网站是什么意思？  网站广告牌制作方法,街上的广告牌，横幅，用PS还是其他软件做的？  网站制作网站,深圳做网站哪家比较好？  小米网站链接制作教程,请问miui新增网页链接调用服务有什么用啊？  如何通过IIS搭建网站并配置访问权限？  网站制作公司,橙子建站是合法的吗？  移动端手机网站制作软件,掌上时代，移动端网站的谷歌SEO该如何做？  制作农业网站的软件,比较好的农业网站推荐一下？  建站之星后台管理如何实现高效配置？  如何在Golang中指定模块版本_使用go.mod控制版本号  大型企业网站制作流程,做网站需要注册公司吗？  C#如何使用XPathNavigator高效查询XML  如何在七牛云存储上搭建网站并设置自定义域名？  深圳企业网站制作设计,在深圳如何网上全流程注册公司？  独立制作一个网站多少钱,建立网站需要花多少钱？  建站之星伪静态规则如何正确配置？  高端建站如何打造兼具美学与转化的品牌官网？