静态链表的C++语言描述实现模板

前言

数据结构中静态链表的C++语言描述实现模板，有详细的步骤解析及使用示例。

---

代码仓库

• yezhening/Programming-examples: 编程实例 (github.com)
• Programming-examples: 编程实例 (gitee.com)

---

sLinkList.cpp

//头文件————————————————————
#include <iostream>
using namespace std;

//宏————————————————————
#define MAX_SIZE 100 //最大大小
//为防止插入数据时溢出，通常数组建立得大一些

//自定义数据类型————————————————————
typedef int ELEM_TYPE; //数据的（数据）类型 依据数据的实际类型定义

//结构体
//定义
//静态链表/数组
typedef struct
{
    ELEM_TYPE data;    //数据
    int cur;           //游标 存储直接后继位置的数组下标
} SLinkList[MAX_SIZE]; //结构体数组
//数组中存在未被使用和已使用的位置/结点
//约定：
//数组的第一个和最后一个位置不存数据
//数组的第一个位置（数组下标为0）的游标存储未被使用位置中第一个位置的数组下标
//当数组位置的游标无直接后继位置时，存储数组下标0
//数组的最后一个位置（数组下标为MAX_SIZE-1）存储已被使用位置中第一个位置的数组下标  类比单链表的头结点
//数组为空时，数组的最后一个位置（数组下标为MAX_SIZE-1）存储数组下标0

//函数声明————————————————————
void use_example();                                               //使用示例
void init_list(SLinkList &sLinkList);                             //初始化
int get_length(SLinkList sLinkList);                              //获取表长
int allot(SLinkList &sLinkList);                                  //分配
bool insert_list(SLinkList &sLinkList, int posi, ELEM_TYPE elem); //插入
void release(SLinkList &sLinkList, int del_cur);                  //释放
bool delete_list(SLinkList &sLinkList, int posi);                 //删除
void traverse(SLinkList sLinkList);                               //遍历

//主函数————————————————————
int main()
{
    use_example(); //使用示例

    return 0;
}

//函数定义————————————————————
//使用示例
void use_example()
{
    //创建
    SLinkList sLinkList;

    //初始化
    init_list(sLinkList);

    //插入  默认成功，未接收返回值
    insert_list(sLinkList, 1, 300);
    insert_list(sLinkList, 1, 200);
    insert_list(sLinkList, 1, 100);
    //元素在数组中排列：300，200，100
    //元素在链表中排列：100，200，300

    for (int i = 1; i < 4; i++)
    {
        cout << sLinkList[i].data << endl; //输出：300，200，100
    }

    int move_cur; //移动游标

    move_cur = MAX_SIZE - 1;

    while (1) //遍历
    {
        move_cur = sLinkList[move_cur].cur; //移动移动游标

        cout << sLinkList[move_cur].data << endl; //输出：100，200，300

        if (sLinkList[move_cur].cur == 0) //移动游标到数组的最后一个位置，输出数据后退出
        {
            break;
        }
    }

    //获取表长
    int length; //表长

    length = get_length(sLinkList); //获取表长

    cout << length << endl; //输出：3

    //删除  默认成功，未接收返回值
    delete_list(sLinkList, 2); //删除

    //注意：
    //删除只是修改元素删除位置的前一个位置的游标存储的数组下标，并将元素删除位置置为未被使用位置
    //是在逻辑上删除，但在物理上元素删除位置仍存储原数据
    //元素在数组中排列：300，200，100
    //元素在链表中排列：100，300

    for (int i = 1; i < 4; i++)
    {
        cout << sLinkList[i].data << endl; //输出：300，200，100
    }

    //遍历
    traverse(sLinkList); //遍历 输出：100，300

    return;
}

//函数定义————————————————————
//初始化
void init_list(SLinkList &sLinkList) //参数：数组（还未形成静态链表）
{
    for (int i = 0; i < MAX_SIZE; i++) //遍历各数组位置
    {
        sLinkList[i].cur = i + 1; //游标存储数组下一位置的数组下标
    }
    //由代码逻辑，初始化后若直接使用插入操作，一般按照数组下标1-MAX_SIZE-1的位置依次插入元素

    sLinkList[MAX_SIZE - 1].cur = 0;
    //遍历后数组最后一个位置的游标存储：sLinkList[MAX_SIZE-1].cur = MAX_SIZE
    //约定：数组为空时，数组的最后一个位置（数组下标为MAX_SIZE-1）存储数组下标0
    //修改数组最后一个位置的游标存储

    return;
}

//获取表长
int get_length(SLinkList sLinkList) //参数：数组    返回值：表长
{
    int length = 0; //表长
    int move_cur;   //移动游标   当前数组位置的数组下标

    move_cur = sLinkList[MAX_SIZE - 1].cur; //初始化移动游标    存储数组已被使用位置中第一个位置的数组下标
    //约定：数组的最后一个位置（数组下标为MAX_SIZE-1）存储已被使用位置中第一个位置的数组下标  类比单链表的头结点

    while (move_cur != 0) //遍历
    {
        move_cur = sLinkList[move_cur].cur; //更新移动游标   存储数组已被使用位置中下一个位置的数组下标

        length++; //表长+1
    }

    return length; //返回表长
}

//静态链表需要模拟动态链表的存储空间分配，需要时申请
//思路：将数组中未被使用的位置链成链表，需要时取第一个位置，记录游标存储下一个未被使用的位置
//分配
int allot(SLinkList &sLinkList) //参数：数组    返回值：数组未被使用位置中第一个位置的数组下标
{
    int posi; //数组未被使用位置中第一个位置的数组下标

    posi = sLinkList[0].cur; //获取数组未被使用位置中第一个位置的数组下标

    //约定：数组的第一个位置（数组下标为0）的游标存储未被使用位置中第一个位置的数组下标
    //约定：当数组位置的游标无直接后继位置时，存储数组下标0
    //从数组的第一个位置（数组下标为0）的游标获取未被使用位置中第一个位置的数组下标
    //若存在数组未被使用位置中第一个位置，值>0，不存在，值==0

    //数组未被使用位置中第一个位置的游标存储数组未被使用位置中第二个位置或者0（已不存在数组未被使用位置）
    //修改数组的第一个位置（数组下标为0）的游标存储下一个数组未被使用位置的数组下标
    if (sLinkList[0].cur != 0)
    {
        sLinkList[0].cur = sLinkList[posi].cur;
    }

    return posi; //返回数组未被使用位置中第一个位置的数组下标
}

//插入
//参数：数组，元素插入的位置，元素 返回值：操作失败返回false，成功返回true
bool insert_list(SLinkList &sLinkList, int posi, ELEM_TYPE elem)
{
    int length; //表长

    length = get_length(sLinkList); //获取表长

    if (posi < 1 || posi > length + 1) //元素插入的位置不合法
    {
        return false;
    }
    //元素的合法插入位置为数组已被使用位置的第一个位置到最后一个位置的后一个位置

    int unused_cur; //数组未被使用位置中第一个位置的数组下标

    unused_cur = allot(sLinkList); //获取数组未被使用位置中第一个位置的数组下标

    //约定：数组的第一个位置（数组下标为0）的游标存储未被使用位置中第一个位置的数组下标
    //约定：当数组位置的游标无直接后继位置时，存储数组下标0
    // allot()从数组的第一个位置（数组下标为0）的游标获取未被使用位置中第一个位置的数组下标
    //若存在数组未被使用位置中第一个位置，值>0，不存在，值==0
    if (unused_cur != 0)
    {
        sLinkList[unused_cur].data = elem; //赋值数据域

        //插入需要修改数组位置的游标域  类比链表的插入
        int move_cur; //移动游标    当前数组位置的数组下标

        //需要查找当前元素插入位置的前一个位置和后一个位置
        //约定：数组的最后一个位置（数组下标为MAX_SIZE-1）存储已被使用位置中第一个位置的数组下标  类比单链表的头结点
        //从数组的最后一个位置（数组下标为MAX_SIZE-1）按照游标存储的数组下标依次遍历1-posi-1个位置
        move_cur = MAX_SIZE - 1;

        for (int i = 1; i <= posi - 1; i++) //遍历  查找当前元素插入位置的前一个位置
        {
            move_cur = sLinkList[move_cur].cur; //移动移动游标
        }
        //遍历后，move_cur是元素插入位置的前一个位置的数组下标

        sLinkList[unused_cur].cur = sLinkList[move_cur].cur;
        // 1.链接当前元素插入位置的后一个位置
        //当前元素插入位置的游标存储的是当前元素插入位置的前一个位置的游标存储的数组下标
        //类比s->next=p->next;

        sLinkList[move_cur].cur = unused_cur;
        // 2.链接当前元素插入位置的前一个位置
        //当前元素插入位置的前一个位置的游标存储的是当前元素插入位置的的数组下标
        //类比p->next=s;

        return true;
    }

    return false;
}

//释放
void release(SLinkList &sLinkList, int del_cur) //参数：数组，元素删除的位置
{
    //约定：数组的第一个位置（数组下标为0）的游标存储未被使用位置中第一个位置的数组下标
    //思路：头插法
    sLinkList[del_cur].cur = sLinkList[0].cur; //元素删除位置的游标记录数组未使用位置中第一个位置的数组下标

    sLinkList[0].cur = del_cur; //数组的第一个位置（数组下标为0）的游标记录元素删除位置的数组下标

    return;
}

//删除
//注意：
//删除只是修改元素删除位置的前一个位置的游标存储的数组下标，并将元素删除位置置为未被使用位置
//是在逻辑上删除，但在物理上元素删除位置仍存储原数据
//参数：数组，元素删除的位置    返回值：操作失败返回false，成功返回true
bool delete_list(SLinkList &sLinkList, int posi)
{
    int length; //表长

    length = get_length(sLinkList); //获取表长

    if (posi < 1 || posi > length) //元素删除的位置不合法
    {
        return false;
    }
    //元素的合法删除位置为数组已被使用位置的第一个位置到最后一个位置

    //删除需要修改数组位置的游标域  类比链表的删除
    int move_cur; //移动游标    当前数组位置的数组下标

    //需要查找元素删除位置的前一个位置和后一个位置
    //约定：数组的最后一个位置（数组下标为MAX_SIZE-1）存储已被使用位置中第一个位置的数组下标  类比单链表的头结点
    //从数组的最后一个位置（数组下标为MAX_SIZE-1）按照游标存储的数组下标依次遍历1-posi-1个位置
    move_cur = MAX_SIZE - 1;

    for (int i = 1; i <= posi - 1; i++) //遍历  查找元素删除位置的前一个位置
    {
        move_cur = sLinkList[move_cur].cur; //移动移动游标
    }
    //遍历后，move_cur是元素删除位置的前一个位置的数组下标

    int del_cur; //元素删除位置的数组下标

    del_cur = sLinkList[move_cur].cur;
    //使用元素删除位置的前一个位置的数组下标定位元素删除位置的前一个位置
    //使用元素删除位置的游标定位元素删除位置的数组下标

    sLinkList[move_cur].cur = sLinkList[del_cur].cur;
    //链接当前元素删除位置的前一个位置和后一个位置
    //使用元素删除位置的前一个位置的数组下标定位元素删除位置的前一个位置
    //使用元素删除位置的的数组下标定位元素删除位置
    //使用元素删除位置的的游标定位元素删除位置的后一个位置
    //使用元素删除位置的前一个位置的游标记录元素删除位置的后一个位置
    //类比：p->next=p->next->next;

    release(sLinkList, del_cur); //释放空间

    return true;
}

//遍历
void traverse(SLinkList sLinkList) //参数：数组
{
    int move_cur; //移动游标

    move_cur = MAX_SIZE - 1;

    while (1) //遍历
    {
        move_cur = sLinkList[move_cur].cur; //移动移动游标

        cout << sLinkList[move_cur].data << endl; //输出：100，200，300

        if (sLinkList[move_cur].cur == 0) //移动游标到数组的最后一个位置，输出数据后退出
        {
            break;
        }
    }

    return;
}

---

总结

• 静态链表是为给没有指针的高级语言设计的一种实现单链表的方法
• 静态链表的操作在链表的基础上多了一层抽象、不易理解。作者也极难选择用词，以能够将其含义通俗易懂的表述出来，还望理解
• 许多参考资料中往往只有对静态链表定义的代码示例，少有对操作的代码示例。静态链表少有使用，但其设计思想是巧妙的。我们需理解学习，扩展思维的同时也以备不时之需
• 作者使用规范的变量命名、提供详细的步骤解析及使用示例，应用C++语言将其整合成模板，以帮助理解记忆。

---

作者的话

• 作者：夜悊
• 版权所有，转载请注明出处，谢谢~
• 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
• 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
• 文章在认识上有错误的地方, 敬请批评指正
• 望读者们都能有所收获

---

参考资料

《大话数据结构》作者：程杰