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

什么是静态链表

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

这就是一个静态链表,首先他是一个数组(长度为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 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

一文入门Python 3

Python 是一种高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。Python 由 Guido van Rossum 于 1989 年底在荷兰国家数...

972
来自专栏跟着阿笨一起玩NET

SQL Server数据库获取TEXT字段的内容长度的方法

SQL Server数据库如何获取TEXT字段的内容长度呢?本文我们就来介绍一下SQL Server数据库如何获取TEXT字段的内容长度的方法,是通过DATA...

583
来自专栏java一日一条

(转)Java中的System类

System类代表系统,系统级的很多属性和控制方法都放置在该类的内部。该类位于java.lang包。

552
来自专栏Golang语言社区

Go语言语法汇总

最近看了看GoLang,把Go语言的语法总结了一下,做个快速参考 数据类型 ---- var varName type,var var1,var2… type,...

4188
来自专栏haifeiWu与他朋友们的专栏

Kotlin委托

Kotlin中有委托,这个C#中也有,不过对于学Java的童鞋来说,这是什么鬼啊,到底是干什么用的… 在委托模式中,当有两个对象参与处理同一个请求是,接受请求的...

693
来自专栏西枫里博客

单数据和批量数据的删除操作

通常对某条数据的删除和某一批数据的删除分别采用两个成员方法。这样太累赘了一些,为了使用批量删除的成员方法,就需要构造单数据的结构。这里以ID为数组作为例子

823
来自专栏钟绍威的专栏

装配bean

spring有三种装配bean的方式:隐式装配、java代码装配、xml装配 隐式装配最为省事方便,也称为自动化装配 这三种装配方式可以混搭着来用 在这里通...

1659
来自专栏Golang语言社区

转--Golang语言语法汇总

最近看了看GoLang,把Go语言的语法总结了一下,做个快速参考 数据类型 ---- var varName type,var var1,var2… type,...

34816
来自专栏web前端教室

【学习笔记】先行者课程0109-rotate3d_变量、堆、栈

一,通过一个小例子,来学习一下css3 3d变换; 二,开始讲js,先从js变量开始说起, 说一下js的变量与内存中的栈的关系, 还有数据的“值传递”、“引...

1756
来自专栏木子昭的博客

<导图>Mysql入门基础语法及示例

数据库操作 查看所有数据库 show database; 创建数据库 语法 create database 数据库名 charset=utf8; 示例 ...

2849

扫码关注云+社区