登录
当前位置： 首页 > 编程笔记 >

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

谷翰飞
2023-03-14
本文向大家介绍C++ 实现静态链表的简单实例，包括了C++ 实现静态链表的简单实例的使用技巧和注意事项，需要的朋友参考一下

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

用数组描述的链表，即称为静态链表。

在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。

这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

下图表示了静态链表的一中存储结构：

图中用彩色途上的是两个头结点，不存放数据，分别用来记录第一个备用节点和第一个数据节点的下标。
下面给出静态链表的C++实现代码：

首先给出头文件：StaticList.h:

#include<iostream>
#include<assert.h>
using namespace std;

#define MAXSIZE 20    // 静态链表（数组）默认长度
#define ElemType int   // 值类型

class StaticList;

//节点类
typedef class StaticListNode  // 静态链表的节点类型（数组元素类型）
{
  friend class StaticList;
private:
  ElemType data;       // 值域
  int   cur;        // 游标 （指示当前节点的下一个元素下标）
}StaticListNode;


// 静态链表类</strong></span>
class StaticList
{
public:
  StaticList()
  {
    for(int i = 2; i<MAXSIZE-1; ++i)
      space[i].cur = i+1;
    space[i].cur = 0;    //整个链表结束
    space[0].cur = 2;
    space[1].cur = 0;    //数据节点头的游标为空，没有数据
  }

  ~StaticList()
  {}

// 尾部插入法
  void push_back(const ElemType &x)
  {
    int i = Malloc_SL();
    if(0 == i)       // 空间申请失败
    {
      cout<<"已满！"<<x<<"不能插入"<<endl;  
      return ;
    }
    space[i].data = x;
    space[i].cur = 0;

    int k = 1;
    while(0!=k && 0!=space[k].cur) // 找到最后一个节点
      k = space[k].cur;

    space[k].cur = i;       // 把刚申请的下标为i的节点链到最后一个节点后面       
  }

// 头部插入法
  void push_front(const ElemType &x)
  {
    int i = Malloc_SL();
    if(0 == i)      // 同上，空间申请失败
    {
      cout<<"已满！"<<x<<"不能插入"<<endl;
      return ;
    }
    space[i].data = x;  // 把x放入刚申请的节点中

    space[i].cur = space[1].cur;  // 此时刚申请的节点i的游标指向第一个数据节点，称为第一个结点
    space[1].cur = i;       // 使头结点指向第一个数据节点
  }

// 尾部删除
  void pop_back()
  {
    int i = space[1].cur;
    int j = 0;
    for(; 0!=space[i].cur; j = i, i = space[i].cur)
    {}  // 找到最后一个节点以及倒数第二个节点

    space[j].cur = 0;   // 倒数第二个节点的游标赋空
    Free_SL(i);      // 最后一个节点被释放
  }

// 头部删除
  void pop_front()
  {
    int i = space[1].cur;  // i是第一个数据节点的下标
    space[1].cur = space[i].cur; // 头结点指向第二个数据节点的下标
    Free_SL(i);       // i 节点被释放
  }

  void show_list()
  {
    for(int i = space[1].cur; i!=0; i = space[i].cur)
      cout<<space[i].data<<" ";
    cout<<"Over"<<endl;
  }

  /* 静态链表从小到大排序的前提下，插入x */
  void insert_val(const ElemType &x)
  {
    int k = 1;
    while(0!=k && 0!=space[k].cur && space[space[k].cur].data<x)
      k = space[k].cur;    //在下标k之后插入

    if(0 == space[k].cur)  // 如果k指向最后一个节点，执行尾插
      push_back(x);
    else if(k == 1)     // 如果k指向第一个节点，执行头插
      push_front(x);
    else           // 在中间任意位置插入x
    {  
      int i = Malloc_SL();
      assert(0 != i);
      space[i].data = x;
      space[i].cur = space[k].cur;  // i节点的游标指向k节点后面的一个节点
      space[k].cur = i;       // k节点的游标指向新开辟的i节点
    }
  }

  /* 返回key的前一个节点下标*/
  int find(const ElemType &key)    
  {
    int i = 1;
    while(0!=i && space[space[i].cur].data!=key)
      i = space[i].cur;
    if(0 == i)
    {
      cout<<"没找到 "<<key<<endl;
      return -1;
    }
    return i;
  }

  /* 删除给定的值key所在节点，若没找到则返回 */
  void delete_val(const ElemType &key)
  {
    int i = find(key);
    if(-1 == i)   // 说明静态链表中没有元素key
      return ;
    else if(1 == i) // key 处于下标为2的节点(第一个数据节点)
      pop_front();
    else if(0 == space[i].cur) // key处于最后一个节点
      pop_back();
    else       // key 处于中间任意位置
    {
      int k = space[i].cur;  // 记录要删除位置的下标
      space[i].cur = space[k].cur; // 脱离出要删除节点
      Free_SL(k); // 删除key所在节点
    }
  }

  /* sl1 和 sl2已存在，把它们糅合到另一个链表，使之按非递减排列 */
  void merge(StaticList &sl1, StaticList &sl2)
  {
    sl1.sort();  
    sl2.sort();
    if(0==sl1.length() || 0==sl2.length())
      return ;
    int p = sl1.space[1].cur;
    int q = sl2.space[1].cur;

    while(0!=p && 0!=q)
    {    
      // 哪个数据较小，就把该数据尾插到新链表中，并使游标指向下一个
      if(sl1.space[p].data < sl2.space[q].data)
      {      
        push_back(sl1.space[p].data);
        p = sl1.space[p].cur;
      }
      else
      {
        push_back(sl2.space[q].data);
        q = sl2.space[q].cur;
      }
    }
    while(0!=p)
    {    // 因为sl1已经有序，如果sl1还没有全部插入新链表，就把剩下的全部插入
      push_back(sl1.space[p].data);
      p = sl1.space[p].cur;
    }
    while(0!=q)
    {    // 因为sl2已经有序，如果sl2还没有全部插入新链表，就把剩下的全部插入
      push_back(sl2.space[q].data);
      q = sl2.space[q].cur;
    }
  }

  /* 如果静态链表无序，使其按非递减顺序排列 */
  void sort()
  {
    int s = space[1].cur;
    int p = space[s].cur;
    if(0 == p)
      return ;
    space[s].cur = 0;

    int k = 1;
    int k1 = 0;
    while(0 != p)
    {
      s = p;
      p = space[p].cur;

      k = 1;   // 找到一个位置k, 在k后插入s所指节点的数据
      while(0!=k && space[space[k].cur].data < space[s].data)
      {
        k1 = k;         //如果k==0,用k1记录最后一个数据节点
        k = space[k].cur;    //在下标k之后插入
      }
      if(0 == k)  //尾插
      {
        space[k1].cur = s;
        space[s].cur = 0;
      }
      else     //头插和中间插
      {
        space[s].cur = space[k].cur;
        space[k].cur = s;
      }
    }
  }

  /* 逆置静态链表 */
  void reserve()
  {
    int s = space[1].cur;
    int p = space[s].cur;
    if( 0==p )
      return ;
    space[s].cur = 0;
    while(0 != p)
    {
      s = p;
      p = space[p].cur;

      space[s].cur = space[1].cur;  // 把s所指节点 头插进原有链表
      space[1].cur = s;       // s成为第一个数据节点
    }
  }

  /* 清空静态链表 */
  void clear()
  {
    for(int i = 2; i<MAXSIZE-1; ++i)
      space[i].cur = i+1;
    space[i].cur = 0;

    space[0].cur = 2;   // 下标2成为第一个备用节点
    space[1].cur = 0;   // 第一个数据节点为空
  }

  /* 返回表长 */
  int length()
  {
    if(0 == space[1].cur)
      return 0;
    int i = 1;
    int count = -1;
    do
    {
      ++count;
      i = space[i].cur;
    }while(0 != i);

    return count;
  }

  /* 返回下标为k的节点的下一个节点下标 在静态链表中用处不大*/
  int next(const int k)
  {
    if(0==k || 1==k)
      return -1;
    return space[k].cur;
  }
  /* 返回下标为k的节点的上一个节点下标 */
  int prio(const int k)
  {
    if(0==k || 1==k)
      return -1;
    int p = 1;
    while(0!=p && space[p].cur!=k)
      p = space[p].cur;
    return p;
  }

protected:
  /* 用来申请一个空间，返回该节点的下标 */
  int Malloc_SL()  
  {
    int i = space[0].cur;  // 0下标的游标指向第一个备用节点
    if(space[0].cur) space[0].cur = space[i].cur; // 修改头结点保存的第一个备用节点下标 
    return i;
  }
  /* 释放下标为k的节点 */
  void Free_SL(int k)  
  {
    space[k].cur = space[0].cur;  // 该节点的游标指向第一个备用节点
    space[0].cur = k;        // 该节点称为第一个备用节点
  }

private:
  StaticListNode space[MAXSIZE];
};

下面是测试代码：Main.cpp

#include"StaticList.h"

void main()
{
  StaticList SL;

  StaticList SL1;  //测试merge()
  StaticList SL2;

  SL1.push_back(1);
  SL1.push_back(9);
  SL1.push_back(0);
  SL1.push_back(6);
  SL1.push_back(999);

  SL2.push_back(5);
  SL2.push_back(8);
  SL2.push_back(100);

  ElemType Item = 0;
  int select = 1;
  while(select)
  {
    cout<<"********************************************"<<endl;
    cout<<"*[1] push_back      [2] push_front  *"<<endl;
    cout<<"*[3] show_list      [4] pop_back   *"<<endl;
    cout<<"*[5] pop_front      [6] insert_val  *"<<endl;
    cout<<"*[7] length       [8] find     *"<<endl;
    cout<<"*[9] merge        [10] delete_val  *"<<endl;
    cout<<"*[11] sort        [12] reserve   *"<<endl;
    cout<<"*[13] next        [14] prio     *"<<endl;
    cout<<"*[15] clear       [16] destroy   *"<<endl;
    cout<<"*[0] quit_sys               *"<<endl;
    cout<<"********************************************"<<endl;
    cout<<"请选择：》";
    cin>>select;
    switch(select)
    {
    case 1:
      cout<<"输入要尾插的数据:(-1结束)>";
      while(cin>>Item && -1 != Item)
        SL.push_back(Item);
      break;

    case 2:
      cout<<"输入要头插的数据:(-1结束)>";
      while(cin>>Item && -1 != Item)
        SL.push_front(Item);
      break;

    case 3:
      SL.show_list();
      break;
    case 4:
      SL.pop_back();
      break;

    case 5:
      SL.pop_front();
      break;

    case 6:
      cout<<"输入要插入的数据:>";
      cin>>Item;
      SL.insert_val(Item);
      break;

    case 7:
      cout<<"链表长度为："<<SL.length()<<endl;
      break;

    case 8:
      cout<<"输入要查找的数据:>";
      cin>>Item;
      SL.find(Item);
      break;

    case 9:
      SL.merge(SL1, SL2);
      break;

    case 10:
      cout<<"输入要删除的数据:>";
      cin>>Item;
      SL.delete_val(Item);
      break;

    case 11:
      SL.sort();
      break;

    case 12:
      SL.reserve();
      break;

    case 13:
      SL.next(0);
      break;

    case 14:
      SL.prio(0);
      break;

    case 15:
      SL.clear();
      break;

    case 16:
      SL.~StaticList();
      break;

    default:
      break;
    }
  }
}

下面是测试截图：

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

 类似资料：
  • C#单链表实现

    在试图理解如何在C#中实现单个列表时，我遇到了下面的链接： 创建一个非常简单的链表。 然而，由于我是C#的新手，我被上面讨论的第一部分中列出的语法弄糊涂了。正在声明一个名为节点的类，并且在声明为“公共节点下一个”的类中还有另一个语句。这个语句称为构造函数吗？请帮忙。

  • C语言单链表的实现

    本文向大家介绍C语言单链表的实现，包括了C语言单链表的实现的使用技巧和注意事项，需要的朋友参考一下 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。 链表结构： SList.h SList.cpp Test.cpp 以上内容是小编给大家介绍的C语言单链表的实现代码，希望对大家有所帮助！

  • C++实现的链表类实例

    本文向大家介绍C++实现的链表类实例，包括了C++实现的链表类实例的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了C++实现的链表类。分享给大家供大家参考。具体如下： 希望本文所述对大家的C++程序设计有所帮助。

  • C语言实现单链表实现方法

    本文向大家介绍C语言实现单链表实现方法，包括了C语言实现单链表实现方法的使用技巧和注意事项，需要的朋友参考一下 C语言实现单链表实现方法 链表和我们之前实现过的顺序表一样，都是简单的数据结构，链表分为单向链表、双向链表、循环链表。而单向链表又分为两种实现方法，一种为带头节点的单链表，一种为不带头节点的单链表。我们来具体看看不带头节点的单链表的实现 单链表：它是一种链式存储的线性表，用一组地址任意的

  • 单链表实现

    C语言面向对象编程（五）：单链表实现 前面我们介绍了如何在 C 语言中引入面向对象语言的一些特性来进行面向对象编程，从本篇开始，我们使用前面提到的技巧，陆续实现几个例子，最后呢，会提供一个基本的 http server 实现（使用 libevent ）。在这篇文章里，我们实现一个通用的数据结构：单链表。 这里实现的单链表，可以存储任意数据类型，支持增、删、改、查找、插入等基本操作。（本文提供的是完

  • C#中的IEnumerable简介及简单实现实例

    本文向大家介绍C#中的IEnumerable简介及简单实现实例，包括了C#中的IEnumerable简介及简单实现实例的使用技巧和注意事项，需要的朋友参考一下 IEnumerable这个接口在MSDN上是这么说的，它是一个公开枚举数，该枚举数支持在非泛型集合上进行简单的迭代。换句话说，对于所有数组的遍历，都来自IEnumerable，那么我们就可以利用这个特性，来定义一个能够遍历字符串的通用方法.

相关阅读

C语言实现单链表反转C#实现简单的Http请求实例C#实现简单的Login窗口实例C语言单向链表的表示与实现实例详解js实现简单模态框实例

相关文章

C#静态成员2.4.5 ListView简单实用GCC使用静态链接库和动态链接库C++静态成员函数C++静态成员变量

相关问答

用类实现C++中的链表队列C++中静态和动态绑定的实例Java迭代器中单链表的实现链表中队列的实现实现一个简单的Dagger2示例

相关工具

最简单代码实现九宫格静态blog简单UITableViewDemo简单CMS简单的广告栏

相关文档

Android 实战简易教程Markdown 简单的世界通过实例学习 C 语言如何实现自己的 jQueryRedis 设计与实现
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.