专栏首页深度学习与计算机视觉数据结构-静态链表及其插入删除操作

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

什么是静态链表

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

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

相关文章

  • 学习SVM(二) 如何理解支持向量机的最大分类间隔

    学习SVM(一) SVM模型训练与分类的OpenCV实现 学习SVM(二) 如何理解支持向量机的最大分类间隔 学习SVM(三)理解SVM中的对偶问题 ...

    chaibubble
  • 理解深层神经网络中的迁移学习及TensorFlow实现

    什么是迁移学习 在深度学习中,所谓的迁移学习是将一个问题A上训练好的模型通过简单的调整使其适应一个新的问题B。在实际使用中,往往是完成问题A的训练出的模型有更完...

    chaibubble
  • 目标检测(object detection)系列(十一) RetinaNet:one-stage检测器巅峰之作

    在RetinaNet之前,目标检测领域一个普遍的现象就是two-stage的方法有更高的准确率,但是耗时也更严重,比如经典的Faster R-CNN,R-FCN...

    chaibubble
  • 暴力搜索------回溯法

    回溯法(backtracking)是深度优先搜索(DFS)的一种,按照深度优先的顺序便利解答树。应用范围很广,只要能把待求解的问题分成不太多的步骤,每个步骤又...

    刘开心_1266679
  • python之MySQLdb库的使用

     在开发的过程中避免不了和数据库的交互,在实际环境中用的最多的Mysql数据库,那python是怎么和Mysql进行交互的呢,python使用一个叫MySQL...

    用户2398817
  • web.xml文件的作用及基本配置

    Java的web工程中的web.xml文件有什么作用呢?它是每个web工程都必须的吗?

    bear_fish
  • 圆圈中最后剩余的数字

    0,1,2,3 ,. . . ,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求这个圆圈里剩余的最后一个数字。

    大学里的混子
  • AngularJS

    scope:单个controller的作用域。可以直接在某controller下的页面引用scope下的变量 rootScope:多个controller作...

    城市中的游牧民族
  • 小数据福音!BERT 在极小数据下带来显著提升的开源实现

    本文授权转载自学术平台 PaperWeekly,公众号ID:paperweekly

    崔庆才
  • web.xml详解

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.or...

    河岸飞流

扫码关注云+社区

领取腾讯云代金券