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

什么是静态链表

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

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

相关文章

来自专栏静默虚空的博客

[spring]03_装配Bean

3.1 JavaBean 3.1.1 JavaBean 是什么 JavaBean 是一种JAVA语言写成的可重用组件。 为写成JavaBean,类必须是具体的和...

1789
来自专栏cs

c++那些事儿10.0 STL--Vector

知识点综述: ---- vector:动态数组,是序列式容器。 这里只介绍vector使用,其实现可以参考数据结构,其函数可以查看stl的源码。 优点...

34711
来自专栏小灰灰

Java 反射简单实例

反射 什么是反射,反射有什么用,反射该怎么用? 一些概念性的东西,这里就不细说了,下面主要给出一个非常简单的反射的调用工具类; 后续会提供一个基于Spring...

1935
来自专栏用户2442861的专栏

Java中finalize()用法

public class Book { boolean checkout = false; Book(boolean checkout){ this....

833
来自专栏Python爬虫与数据挖掘

Python正则表达式初识(五)

正则表达式的内容很丰富,今天小编继续给大家分享Python正则表达式的基础知识。今天要给大家的讲的特殊字符是竖线“|”。竖线“|”实质上是一个或的关系。

784
来自专栏Jack-Cui

155.Min Stack(Stack-Easy)

    Design a stack that supports push, pop, top, and retrieving the minimum elem...

1925
来自专栏Nian糕的私人厨房

JavaScript 分支/循环语句

if...else 语句,在条件为 true 时执行代码,在条件为 false 时执行其他代码

694
来自专栏Laoqi's Linux运维专列

多类型传值和冗余参数+递归调用

947
来自专栏编程坑太多

Python 字典

784
来自专栏架构说

题目:判断一个单链表是否回文链表

题目:判断一个单链表是否回文链表 Given a singly linked list, determine if it is a palindrome. C...

3168

扫码关注云+社区