数据结构(6)--静态链表的基本操作

标签: 数据结构  链表  指针  数据结构  单链表

前言

博主最近时间紧张,所以最近的博客只贴整理好后的代码,部分方法会有代码注释,也尽量保证编码规范,有问题欢迎留言!

问题分析

在这里插入图片描述

在这里插入图片描述
赶时间“MAXSIZE”写成了“MAIXSIZE”,就说怎么怪怪的

程序实现

存储结构

typedef struct
{
    ElemType data;
    int cur;
} SLinkList[MAXSIZE];

操作方法

int Malloc_SL(SLinkList SL);       //静态链表自实现的malloc函数
void Free_SL(SLinkList SL, int k); //静态链表自实现的free函数
void Destroy_SL();                 //静态链表不可被销毁
void InitSpace_SL(SLinkList SL);
Status ClearSpace_SL(SLinkList SL);
Status SpaceEmpty(SLinkList SL);
int SpaceLength(SLinkList SL);
Status GetElem_SL(SLinkList SL, int location, ElemType &e);
int LocateElem_SL(SLinkList SL, ElemType e);
Status PriorElem_SL(SLinkList SL, ElemType cur_e, ElemType &pre_e);
Status NextElem_SL(SLinkList SL, ElemType cur_e, ElemType &next_e);
Status InsertSpace_SL(SLinkList SL, int location, ElemType e);
Status DeleteSpace_SL(SLinkList SL, int location, ElemType &e);
Status TraverseSpace_SL(SLinkList SL, void (*visit)(ElemType));
void vis(ElemType e);          //结点数据输出
Status Traverse(SLinkList SL); //临时加入的遍历备用链表的方法

代码汇总

main.h

/*
 * Copyright (c) 2020 WUST
 *
 * 文件名 : main.h
 *
 * Author: Mr.Killer
 * Date  : 2020-01-02 16:13:51
 */

#include <iostream>

typedef int Status;
typedef int ElemType;

const int OK = 1;
const int ERROR = 0;
const int TRUE = 1;
const int FALSE = 0;
const int MAXSIZE = 100;

using namespace std;

methods.h

/*
 * Copyright (c) 2020 WUST
 *
 * 文件名 : methods.h
 *
 * Author: Mr.Killer
 * Date  : 2020-01-02 16:14:00
 */

typedef struct
{
    ElemType data;
    int cur;
} SLinkList[MAXSIZE];

methods.cpp

/*
 * Copyright (c) 2020 WUST
 *
 * 文件名 : methods.cpp
 *
 * Author: Mr.Killer
 * Date  : 2020-01-02 16:13:34
 */

int Malloc_SL(SLinkList SL);       //静态链表自实现的malloc函数
void Free_SL(SLinkList SL, int k); //静态链表自实现的free函数
void Destroy_SL();                 //静态链表不可被销毁
void InitSpace_SL(SLinkList SL);
Status ClearSpace_SL(SLinkList SL);
Status SpaceEmpty(SLinkList SL);
int SpaceLength(SLinkList SL);
Status GetElem_SL(SLinkList SL, int location, ElemType &e);
int LocateElem_SL(SLinkList SL, ElemType e);
Status PriorElem_SL(SLinkList SL, ElemType cur_e, ElemType &pre_e);
Status NextElem_SL(SLinkList SL, ElemType cur_e, ElemType &next_e);
Status InsertSpace_SL(SLinkList SL, int location, ElemType e);
Status DeleteSpace_SL(SLinkList SL, int location, ElemType &e);
Status TraverseSpace_SL(SLinkList SL, void (*visit)(ElemType));
void vis(ElemType e);          //结点数据输出
Status Traverse(SLinkList SL); //临时加入的遍历备用链表的方法

int Malloc_SL(SLinkList SL)
{
    int i = SL[0].cur;
    if (i)
        SL[0].cur = SL[i].cur; //把备用链表中将要取出的结点(SL[i])的下一个结点与头结点连接
    return i;
}

void Free_SL(SLinkList SL, int k)
{
    SL[k].cur = SL[0].cur; //把要释放的结点连接到备用链表中
    SL[0].cur = k;
}

void Destroy_SL()
{ // 静态链表不能被销毁
}

void InitSpace_SL(SLinkList SL)
{
    int i;
    SL[MAXSIZE - 1].cur = 0;          // SL的最后一个单元为空链表的表头
    for (i = 0; i < MAXSIZE - 2; i++) // 将其余单元链接成以SL[0]为表头的备用链表
        SL[i].cur = i + 1;
    SL[MAXSIZE - 2].cur = 0;
}

Status ClearSpace_SL(SLinkList SL)
{
    int i, j, k;
    i = SL[MAXSIZE - 1].cur;
    SL[MAXSIZE - 1].cur = 0;
    k = SL[0].cur;
    SL[0].cur = i;
    while (i)  // 通过对初始化和插入的分析,可知链表的最后一个结点的“指针域”(cur)的值为零,
    {          // 一直读取到最后一个结点
        j = i; //因为是把链表整块的连接到备用链表中,所以备用链表中结点的位序会发生改变
        i = SL[i].cur;
    }
    SL[j].cur = k;

    return OK;
}

Status SpaceEmpty(SLinkList SL)
{
    if (SL[MAXSIZE - 1].cur == 0) // 空表
        return TRUE;
    else
        return FALSE;
}

int SpaceLength(SLinkList SL)
{
    int count = 0, i;
    i = SL[MAXSIZE - 1].cur; // i指向第一个元素
    while (i)                // 没到静态链表尾
    {
        i = SL[i].cur; // 指向下一个元素
        count++;
    }
    return count;
}

Status GetElem_SL(SLinkList SL, int location, ElemType &e)
{
    int k = MAXSIZE - 1; // k指向表头序号
    if (location < 1 || location > SpaceLength(SL))
        return ERROR;
    for (int i = 1; i <= location; i++) // 移动到第i个元素处
        k = SL[k].cur;
    e = SL[k].data;
    return OK;
}

int LocateElem_SL(SLinkList SL, ElemType e)
{                                // 位序,与其它LocateElem()的定义不同,这里的位序指的是保存e的结点的数组下标,并不是在链表中第几个位置
    int i = SL[MAXSIZE - 1].cur; // i指示表中第一个结点
    while (i && SL[i].data != e) // 在表中顺链查找(e不能是字符串)
        i = SL[i].cur;
    return i;
}

Status PriorElem_SL(SLinkList SL, ElemType cur_e, ElemType &pre_e)
{
    int j, i = SL[MAXSIZE - 1].cur; // i指示链表第一个结点的位置
    do
    { // 向后移动结点,用j表示i的前一个结点,用i结点保存的数据来匹配数据
        j = i;
        i = SL[i].cur;
    } while (i && cur_e != SL[i].data);
    if (i) // 找到该元素
    {
        pre_e = SL[j].data;
        return OK;
    }
    return ERROR;
}

/* 查找数据的前驱和后继的方法不同,
 * 原因在于结点的“指针域”只保存了下一个结点的序号,
 * 不能通过定位到要找前驱的数据来得到它的前驱,
 * 但是可以通过定位要找后继的数据来得到它的后继 
 * 找后继当然可以使用找前驱的方法
 */

Status NextElem_SL(SLinkList SL, ElemType cur_e, ElemType &next_e)
{
    int j, i = LocateElem_SL(SL, cur_e); // 在SL中查找第一个值为cur_e的元素的位置
    if (i)                               //SL中存在元素cur_e
    {
        j = SL[i].cur; // cur_e的后继的位置
        if (j)         // cur_e有后继
        {
            next_e = SL[j].data;
            return OK; // cur_e元素有后继
        }
    }
    return ERROR; // SL不存在cur_e元素,cur_e元素无后继
}

Status InsertSpace_SL(SLinkList SL, int location, ElemType e)
{
    int l, j, k = MAXSIZE - 1; // k指向表头
    if (location < 1 || location > SpaceLength(SL) + 1)
        return ERROR;
    j = Malloc_SL(SL); // 申请新单元
    if (j)             // 申请成功
    {
        SL[j].data = e;                // 赋值给新单元
        for (l = 1; l < location; l++) // 移动i-1个元素
            k = SL[k].cur;
        SL[j].cur = SL[k].cur;
        SL[k].cur = j;
        return OK;
    }
    return ERROR;
}

/* 
 * 结点删除包含两个步骤:
 * 1.把要删除的结点的后一个结点与前一个结点连接
 * 2.把要删除的结点放入备用链表,即 Free
 */
Status DeleteSpace_SL(SLinkList SL, int location, ElemType &e)
{
    int j, k = MAXSIZE - 1; // k指向表头
    if (location < 1 || location > SpaceLength(SL))
        return ERROR;
    for (j = 1; j < location; j++) // 移动i-1个元素
        k = SL[k].cur;
    j = SL[k].cur;
    SL[k].cur = SL[j].cur;
    e = SL[j].data;
    Free_SL(SL, j);
    return OK;
}

Status TraverseSpace_SL(SLinkList SL, void (*visit)(ElemType))
{
    int i = SL[MAXSIZE - 1].cur; // 指向第一个元素
    while (i)                    // 没到静态链表尾
    {
        visit(SL[i].data); // 调用vis()
        i = SL[i].cur;     // 指向下一个元素
    }
    cout << endl;
    return OK;
}

void vis(ElemType c)
{
    printf("%d ", c);
}

Status Traverse(SLinkList SL)
{
    int i = SL[0].cur;
    while (i)
    {
        cout << i << endl;
        i = SL[i].cur;
    }
    return OK;
}

main.cpp

/*
 * Copyright (c) 2020 WUST
 *
 * 文件名 : main.cpp
 *
 * Author: Mr.Killer
 * Date  : 2020-01-02 16:13:42
 */

#include "main.h"
#include "methods.h"
#include "methods.cpp"

int main()
{
    int j, k;
    Status i;
    ElemType e, e0;
    SLinkList SL;
    InitSpace_SL(SL);
    for (j = 1; j <= 5; j++)
        i = InsertSpace_SL(SL, 1, j);
    printf("在L的表头依次插入1〜5后:L=");
    TraverseSpace_SL(SL, vis);
    i = SpaceEmpty(SL);
    printf("L是否空:i=%d(1:是 0:否)表L的长度=%d\n", i, SpaceLength(SL));
    i = ClearSpace_SL(SL);
    printf("清空L后:L=");
    TraverseSpace_SL(SL, vis);
    printf("清空L后,备用链表的位续:");
    cout << endl;
    Traverse(SL);
    cout << endl;
    TraverseSpace_SL(SL, vis);
    i = SpaceEmpty(SL);
    printf("L是否空:i=%d(1:是 0:否)表L的长度=%d\n", i, SpaceLength(SL));
    for (j = 1; j <= 10; j++)
        InsertSpace_SL(SL, j, j);
    printf("在L的表尾依次插入1〜10后:L=");
    TraverseSpace_SL(SL, vis);
    GetElem_SL(SL, 5, e);
    printf("第5个元素的值为:%d\n", e);
    for (j = 0; j <= 1; j++)
    {
        k = LocateElem_SL(SL, j);
        if (k)
            printf("值为%d的元素在静态链表中的位序为%d\n", j, k);
        else
            printf("没有值为%d的元素\n", j);
    }
    for (j = 1; j <= 2; j++) // 测试头两个数据
    {
        GetElem_SL(SL, j, e0);       // 把第j个数据赋给e0
        i = PriorElem_SL(SL, e0, e); // 求e0的前驱
        if (!i)
            printf("元素%d无前驱\n", e0);
        else
            printf("元素%d的前驱为:%d\n", e0, e);
    }
    for (j = SpaceLength(SL) - 1; j <= SpaceLength(SL); j++) // 最后两个数据
    {
        GetElem_SL(SL, j, e0);      // 把第j个数据赋给e0
        i = NextElem_SL(SL, e0, e); // 求e0的后继
        if (!i)
            printf("元素%d无后继\n", e0);
        else
            printf("元素%d的后继为:%d\n", e0, e);
    }
    k = SpaceLength(SL); // k为表长
    for (j = k + 1; j >= k; j--)
    {
        i = DeleteSpace_SL(SL, j, e); // 删除第j个数据
        if (i)
            printf("删除的元素为:%d\n", e);
        else
            printf("删除第%d个数据失败\n", j);
    }
    printf("依次输出L的元素:");
    TraverseSpace_SL(SL, vis); // 依次对元素调用visit(),输出元素的值
    printf("备用链表的位续:");
    cout << endl;
    Traverse(SL);
}

重中之重

有任何疑问可以留言,然后求赞求关注🙏🙏🙏

原文链接:加载失败,请重新获取