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

下面是测试截图:

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

(0)

相关推荐

  • C语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • C#如何自定义线性节点链表集合

    本例子实现了如何自定义线性节点集合,具体代码如下: using System; using System.Collections; using System.Collections.Generic; namespace LineNodeDemo { class Program { static void Main(string[] args) { LineNodeCollection lineNodes = new LineNodeCollection(); lineNodes.Add(new

  • 面试题快慢链表和快慢指针

    腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点.算法复杂度是:O(3*n/2).而更快的方法就是利用快慢指针的原理. 快慢链表:利用标尺的思想,设置两个指针(一快一慢)*serach和*mid,刚开始都指向单链表的头结点.但是*search指针的移动速度是*mid的两倍.当*search到尾结点的时候,mid刚好到了中间.算法复杂度是:O(n/2) int GetMidNode(LinkList *L,int elem){ Li

  • C语言 数据结构链表的实例(十九种操作)

    C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

  • C++ 实现双向链表的实例

    双向链表C++ 的实现 本文是通过C++ 的知识实现数据结构中的双向链表,这里不多说 了,代码注释很清楚, 实现代码: //double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virt

  • C语言之复杂链表的复制详解

    什么是复杂链表? 复杂链表指的是一个链表有若干个结点,每个结点有一个数据域用于存放数据,还有两个指针域,其中一个指向下一个节点,还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点.今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表. 复杂链表的数据结构如下: typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // 数据 struct Complex

  • C++ 中循环链表和约瑟夫环

    循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表.当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head. 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node *temp,*target; cout<<"输入0完成初始化"&

  • C语言中双向链表和双向循环链表详解

    双向链表和双向循环链表 和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作 新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =

  • C语言数据结构实现链表去重的实例

    C语言数据结构实现链表去重的实例 题目及分析 链表去重 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入

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

    C++ 实现静态链表的简单实例 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标cur. 这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点. 下图表示了静态链表的一中存储结构: 图中用彩色途上的是两个头结点,不存放数据,分别用来记录第一个备用节点和第一个数据节点的下标. 下面给出静态链表的C++实现代码: 首先给出头文件:StaticList.

  • JS控制静态页面之间传递参数获取参数并应用的简单实例

    在项目中遇到这也一个问题: 有a.html和b.html. 1.a页面已经打开,b页面尚未打开,我希望在a页面设置好一些列参数,比如背景色,宽度等参数,传递给b页面,好让b页面在打开就能应用. 2.a页面已经打开,b页面无论是否打开.在a页面需要获取到b页面的一些元素甚至变量,以便于应用到a页面. 注意:不涉及跨域问题. 想了很久,终于想到了解决方案. 第一个问题,我们可以利用html页面锚点的特性,将参数通过url传递给b页面 这是a页面代码: <button>跳转设置</button

  • 利用反射获取Java类中的静态变量名及变量值的简单实例

    JAVA可以通过反射获取成员变量和静态变量的名称,局部变量就不太可能拿到了. public class Test { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub //获取所有变量的值 Class clazz = Class.forName("com.qianmingxs.ScoreTable"); Field[] fields = clazz.g

  • Java反射之静态加载和动态加载的简单实例

    静态加载: package com.imooc.加载类; public class Office_Static { public static void main(String[] args) { //new 创建对象,是静态加载类,在编译时刻就需要加载所有的可能使用到的类 if("Word".equals(args[0])){ Word w = new Word(); w.start(); } if("Excel".equals(args[0])){ Excel

  • Java 链表的定义与简单实例

     Java 链表的定义与简单实例 Java实现链表主要依靠引用传递,引用可以理解为地址,链表的遍历多使用递归,这里我存在一个疑问同一个类的不同对象的的相同方法的方法内调用算不算递归. 这里我写的是单向链表; package com.example.java; public class MyLink { public static void main(String [] args){ Link l=new Link(); mytype[] la; mytype dsome=new mytype("

  • Android 中自定义ContentProvider与ContentObserver的使用简单实例

    Android 中自定义ContentProvider与ContentObserver的使用简单实例 示例说明: 该示例中一共包含两个工程.其中一个工程完成了自定义ContentProvider,另外一个工程用于测试该自定义ContentProvider且在该工程中使用了ContentObserver监听自定义ContentProvider的数据变化 以下代码为工程TestContentProvider ContentProviderTest如下: package cn.testcontentp

  • C语言静态链表和动态链表

    1. 静态链表 结构体中的成员可以是各种类型的指针变量,当一个结构体中有一个或多个成员的基类型是本结构体类型时,则称这种结构体为"引用自身的结构体".如: struct link { char ch; struct link *p; } a; p是一个可以指向 struct link 类型变量的指针成员.因此,a.p = &a 是合法的表达式,由此构成的存储结构如图1所示. 图1 引用自身的结构体 例1 一个简单的链表 #include <stdio.h> stru

  • Python单链表的简单实现方法

    本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.

  • Node.js+jade抓取博客所有文章生成静态html文件的实例

    这篇文章,我们就把上文中采集到的所有文章列表的信息整理一下,开始采集文章并且生成静态html文件了.先看下我的采集效果,我的博客目前77篇文章,1分钟不到就全部采集生成完毕了,这里我截了部分的图片,文件名用文章的id生成的,生成的文章,我写了一个简单的静态模板,所有的文章都是根据这个模板生成的. 项目结构: 好了,接下来,我们就来讲解下,这篇文章主要实现的功能: 1,抓取文章,主要抓取文章的标题,内容,超链接,文章id(用于生成静态html文件) 2,根据jade模板生成html文件 一.抓取文

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

随机推荐