数据结构-静态链表及其插入删除操作

什么是静态链表

我们平常提及的链表一般指的是动态链表,是使用指针将一个一个的结点连起来,除了动态链表之外,还有静态链表,这种链表用数组来描述,主要为了解决没有指针或者不用指针的情况下具备链表插入删除操作便捷的特性。 静态链表中有一些专属的概念,先贴上图:

这就是一个静态链表,首先他是一个数组(长度为8),数组的类型显然要根据需要定义,在上图中的类型为:

typedef struct 
{
    ElemType data;
    int cur;  
} Component,StaticLinkList[MAXSIZE];

一般我们定义一个有两个数据区域的结构体数组: 一个区域(data)用来存放实际数据; 另一个区域(cur)用来存放“指向”的下一个数据区域数组的下标(这里的指向并不指的是指针),cur也被称之为游标,它里面存放的是数组的下标(先不管存放的规则如何,存放的就是数组的下标) 数组中的元素(除了第一个和最后一个)按照有没有被使用分类的,可以分为两类(就像上面的红色和绿色),这两类元素可以分别构成链,我们可以把没有使用的那个链叫做被备用链。 数组中的第一个元素(下标0)与最后一个元素(下标n-1)是不存放数据的,第一个元素的cur存放备用链的第一个元素的下标,最后一个元素的cur存放使用的链表的第一个元素的下标。比如上图中最后一个元素中cur放的是1,1是第一个红色框的下标。 至此,静态链表就构建完了。

静态链表的插入操作

从上面的图可以看到,其实数组的最后一个元素的cur存的是一般都是1,因为在使用元素构建链表时从第二个元素开始顺序插入,而插入的位置在哪,其实是由cur决定的,都不是顺序存储中由位置决定。 所以,假设已经有了如上图所示的链表,现在想在第i个元素前插入一个元素,可以这样来做: (1)从备用链里面找出来第一个元素的下标j,让备用链减一; (2)将要插入的值给j的data; (3)i是相对于使用链表的长度来说的,所以要判断使用的链表的长度,判断i是否在范围内; (4)找到i的前一个元素下标k; (5)k的cur先变成j的cur,因为k插入到j后面,j以前的后续要有k链接; (6)k的cur赋值为j,由于j是一个下标,j就是cur。 (5)(6)的思路和动态链表的插入很像,都是要先解决后面的东西,在插前面,如果(5)(6)对调,链表断开后,k的cur原来的数被j覆盖,链表将无法重新连接。

#define MAXSIZE 1000
typedef int Status;          
typedef char ElemType; 
//定义数组的类型  
typedef struct 
{
    ElemType data;
    int cur;  
} Component,StaticLinkList[MAXSIZE];
//在备用表中找到并返回第一个元素的下标,并改变数组[0]的cur
int Malloc_SSL(StaticLinkList space) 
{ 
    int i = space[0].cur;                                                               
    if (space[0]. cur)         
        space[0]. cur = space[i].cur;                                                                                      
    return i;
}
//获取使用链表的长度
int ListLength(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
} 
//插入操作
Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;
    //判断是否超范围   
    if (i < 1 || i > ListLength(L) + 1)   
        return 0;  
    //返回备用表第一个元素的下标 
    j = Malloc_SSL(L);   

    if (j)   
    {   
        L[j].data = E;
        //找到i前面的元素下标k  
        for(l = 1; l <= i - 1; l++)   
           k = L[k].cur;   
        //j继承k的cur        
        L[j].cur = L[k].cur;
        //给k   
        L[k].cur = j;          
        return 1;   
    }   
    return 0;   
}    

需要说明的是for循环的内容,第一次看到这个for循环时可能觉得很奇怪,用l在控制循环,但是下面的内容没有变量l的参与,这是因为for只控制循环的次数就好了,k从数组的最后一位开始,而数组[MAXSIZE - 1]的cur中存放的就是是用链表第一个元素的下标,第一个元素的cur中放的又是第二个元素的下标,每一次k都会变成链表中下一个元素的下标。

静态链表的删除操作

删除操作是一样的,在插入中,插入一个元素影响了使用链备用链。那么删除一个元素的话也会同时影响这两个链。

首先考虑备用链,由于原链表中一个元素被删除了,在上图中是下标3的元素,那么原备用链中第一个元素就不再是下标5了,而应该是3,也就是说再有插入操作的时候优先插入的位置是3。那么我们就可以写出一个和Malloc_SSL函数功能相反的函数—Free_SSL。

void Free_SSL(StaticLinkList space, int j) 
{  
    space[j].cur = space[0].cur;    
    space[0].cur = j;               
}

看下这个函数,再看下之前插入代码里面的这两行:

        //j继承k的cur        
        L[j].cur = L[k].cur;
        //给k   
        L[k].cur = j;  

你会发现这是一毛一样的操作,这就是在下标0与备用链第一个元素之间插了一个j,而之前的代码是在下标k与k后面的元素之间插了一个j。 其次就是原链表的变化,要删除链表中i位置的元素,同样要找到这个位置的数组的前一个数组的下标k,而k位置的元素的cur存放着要删除的元素的下标j,j的cur里面又放着下一个元素的下标,我们需要做的就是把这个下标给k的cur,这样一来,j对应的元素就从原链表中删除了。

Status ListDelete(StaticLinkList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return ERROR;   
    k = MAXSIZE - 1;   
    for (j = 1; j <= i - 1; j++)   
        k = L[k].cur;   
    j = L[k].cur;   
    L[k].cur = L[j].cur;   
    Free_SSL(L, j);   
    return OK;   
} 

拿上面的图解释一下这个过程,要删除下标为3的元素,通过for循环找到它前面的元素,此时(下面的“=”是数学里面相等的关系,不是赋值!!): k=2; L[2].cur=3=j; L[j].cur=L[3].cur=4; L[2].cur=4; 执行 Free_SSL(L, 3); L[3].cur=5; L[0].cur=3;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小勇DW3

redis中各种数据类型的常用操作方法汇总

string是redis最基本的类型,你可以理解成与Memcached一模一样的类型,一个key对应一个value。 string类型是二进制安全的。意思是re...

673
来自专栏zaking's

用js来实现那些数据结构02(数组篇02-数组方法)

    上一篇文章简单的介绍了一下js的类型,以及数组的增删方法。这一篇文章,我们一起来看看数组还有哪些用法,以及在实际工作中我们可以用这些方法来做些什么。由于...

37211
来自专栏程序生活

Leetcode-Easy 876. Middle of the Linked List

结题思路主要是通过快慢指针来找到中间节点:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。

823
来自专栏前端侠2.0

大白话讲解Promise(一)一文 的学习+新领悟

1、Promise是一个构造函数,自己身上有all、reject、resolve、then、catch。。。。。

1332
来自专栏Java大联盟

Java面试手册:核心基础-4

5.comparable/comparator区别。 用Comparable简单,只要实现Comparable接口的对象直接就成为一个可以比较的对象但...

1002
来自专栏前端知识分享

第205天:面向对象知识点总结

JSON全称为JavaScript对象简单表示法(JavaScript Object Notation)

783
来自专栏数据结构与算法

BZOJ3585: mex(主席树)

Description   有一个长度为n的数组{a1,a2,...,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。 Input   第一行n,m...

4119
来自专栏用户2442861的专栏

Java内存管理(一、内存分配)

关于Java内存分配,很多问题都模模糊糊,不能全面贯通理解。今查阅资料,欲求深入挖掘,彻底理清java内存分配脉络,只因水平有限,没达到预期效果,仅以此文对所...

2692
来自专栏老九学堂

必看 | 新人必看的Java基础知识点大梳理

各位正在认真苦学Java的准大神,在这烈日炎炎的夏季里,老九君准备给大家带来一个超级大的“冰镇西瓜,”给大家清凉一下,压压惊。但这个大西瓜可不是一般的大西瓜,是...

3498
来自专栏闪电gogogo的专栏

Python——正则表达式

此篇文章结合小甲鱼的笔记和视频整理。 1 编译 Python 通过 re 模块为正则表达式引擎提供一个接口,同时允许你将正则表达式编译成模式对象,并用它们来进行...

26310

扫码关注云+社区