数据结构与算法——第四讲：静态链表及双向链表

前言

C/Cpp系列具有指针，使他可以非常容易地操作内存中的地址和数据，虽然如Java，C#等不使用指针，但启用了对象引用机制，某种程度上来说也间接实现了指针的某些作用。但对于一些基层的语言，如更早期的Basic、Fortran等早期高级语言，没有指针的概念，链表如果按照我们之前的说法并没有办法实现。

这就是我们接下来三分之一的篇章——静态链表。它解决了在没有指针存在的情况下对静态链表的实现，为什么叫静态？因为其大小是固定的，跟我们最开始定义数组的情况一样，我们一定是int a[100];这样来定义int[100]类型数组名为a的数组，他比较死板，不能灵活扩容，也不能灵活减容，故而称之为静态。

在此之前，我们学习了这两种线性结构，但我们会发现这在解决形如12个月问题，一周7天的链表表示中还并不能很完美展现，这就需要我们在本章另外的篇章，来引入双向链表以及循环链表。

双向链表允许我们在链表中向前和向后遍历，这在某些情况下非常有用。循环链表则是一种特殊的链表，它的最后一个节点指向链表的第一个节点，形成一个循环。这两种链表结构都可以更好地解决一些特定的问题，并且在实际编程中有着广泛的应用。

回眸数组——静态链表

回顾数组，我们发现，数组的元素都是由两个数据域组成的，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据：而cur相当于单链表种的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。

我们把这种数组描述的链表叫做静态链表。静态链表是比较死板的，雷打不动，说自己有多少他就只有多少，多了数据会溢出，空间用少了他的空闲空间又会闲置，导致占用过多的内存空间（内存管理在C/Cpp中是比较重要的，特别是Cpp，为了及时释放空间在类中引入了"析构"的概念），这是我们无法避免的事情。

#define MAXSIZE 1000

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

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个由数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，其cur数值则为0。

静态链表的初始化

Status InitList(StaticLinkList space){
    for(int i=0;i<MAXSIZE-1;i++){
        space[i].cur=i+1;
    }
    space[MAXSIZE-1].cur=0;//目前静态链表为空，最后一个元素的cur为0
    return OK;
}

我们可以发现，除了头结点的cur指向的是5外，其他的指针域都是从2再到5依次递增，此时"A"这里的cur存有下一元素"B"的下标**1**，"B"的cur存有下一元素"C"的下标**2**，……，直到"E"的cur存储的数值是0，意思是指向数组下标为0的数值，而我们会发现其指向的就是头结点，而第一个元素因空闲空间的第一个元素下标为5，所以它的cur存有5。

为了求这个静态链表中数据元素的个数，我们可以通过下列自定义的函数方法来确定：

/*静态链表L已存在。其结果为返回L中数据元素的个数*/
int ListLength(StaticLinkList L){
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i){
        i=L[i].cur;
        j++;
    }
    return j;
}

静态链表的插入操作

既然我们有静态链表的定义，我们对数据的增删改查也应运而生，我们该如何将某些元素/数据插入到其中？

在动态链表中，我们对节点的申请和释放分别使用malloc(),free()两个函数来实现，可我们要操作的是一个数组，我们应该如何处理这种迥异？既然没有条件，我们就创造条件，我们要把类似于这两个函数给模拟出来，才可以做到插入以及删除操作。

这时候我们就要分析，哪个分量是被使用的，哪些个并没有被使用？解决方法是通过将**所有未被使用过的以及被删除的分量用游标链成一个备用**的链表，每当进行插入的时候，可以从备用链表取得第一个结点作为待插入的新结点。

/*链表若为空，则返回0，反之返回分配的结点下标*/
int Malloc_SLL(StaticLinkList space){			//实际上这个东西就是一个数组的类型
    int i=space[0].cur;							//根据定义，这里存储的是目前拥有的元素个数
    
    if(space[0].cur){
        space[0].cur=space[i].cur;				//判断是否为0，非零就将sapce[0]
    }											//的cur赋值为space[i].cur,
    											//把这个数值当作下一个分量的"备胎"
    return i;
}

那我们到底如何去插入一个数值？

注意到我们如果添加了一个元素"E"，告诉元素"C"说，我要排在你的后面，那不就是把各自的cur，但是对下家元素"D"一点都不理睬，因为插队本身就是这样子即荒诞又好笑，只要旁边的人同意了，也便不顾及其他人，这时候只要元素"C"给"E"，只需要"D"将cur更改成6，将"E"的下标的cur改成4，而"E"的也就完成了所谓的"插队"

以下是其实现代码：

Status ListInsert(StaticLinkList L,int i,ElemType e){
    int j,k,l;
    k=MAXSIZE-1;					//k首先是最后一个元素的下标
    if(i<1||i>LIstLength(L)+1)
        return ERROR;
    j=Malloc_SLL(L);				//获得该静态链表空闲分量的下标
    if(j){
        L[j].data=e;				//将数据赋值给此份量的data
        for(l-1;l<=i-1;l++){		//找到第i元元素之前的位置
            k=L[k].cur;
        }
        L[j].cur=L[k].cur;			//把第i个元素之前的cur赋值给新元素的cur
        L[k].cur=j;					//把新元素的下标赋值给第i个元素之前的cur
        return OK;
    }
    return ERROR;
}

静态链表的删除操作

突然前面在最前面排队的人接了电话后应了几声，也就走了，看上去有急事，这部就意味着我们所有的元素会往前排1位，在静态链表中我们如何实现？

同理，我们没有malloc()，定义了Malloc()，我们也没有free()，自然Free()也就是千呼万唤始出来的结果：

void Free(StaticLinkList L,int k){
    space[k].cur=space[0].cur;				//把第一个元素的cur赋值给要删除的分量cur
    space[0].cur=k;							//把要删除的分量下标赋值给第一个元素的cur
}
    //当一个节点不再被使用时，将其标记为空闲，并将其插入到空闲链表的头部，以便后续可以被重新分配和使用。

Free()函数的存在就是为了执行元素"A"要走，这个位置就空出来了，也就是未来来的人排在这，但是其序号并没有继承下去，这一方针。

实际上更像我们排队点麻辣烫，麻辣香锅，有的人是酱香口味，有人是微辣口味，有人是麻辣口味…（更多的我说不出来），虽然说你的酱香口味拿的牌子是72，但是不妨碍微辣口味的同学在你前面点了，其牌子虽然是108（我在玩72地煞36天罡的梗，希望有人理解看水浒传人士的精神状态），但是他就是比你先点，理应也先做好，可以理解为，元素"A"走了，实际上是该同学(元素)拿到餐了，甚至说退出了。

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);
}

静态链表的优缺点

值得反复提一嘴的是，静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法，不到万不得已可以考虑用这种方法来写题目。

循环链表

循环链表是一种特殊的链表，它的最后一个节点的指针指向链表的头节点，形成一个环形结构。这样，链表中的任何一个节点都可以作为起始节点，并且可以通过遍历回到起始节点。

循环链表的定义

循环链表的操作与普通链表类似，但需要注意的是，在进行插入和删除操作时，需要考虑循环的特性。例如，在插入节点时，需要确保新节点的指针正确地指向链表中的其他节点；在删除节点时，需要更新被删除节点的前一个节点的指针，使其指向被删除节点的下一个节点。

循环链表在实际应用中非常有用，例如在操作系统中，进程调度通常使用循环链表来实现。此外，循环链表还可以用于实现循环队列、约瑟夫问题等。

双向链表

双向链表是一种特殊的链表，**它的每个节点都包含两个指针，一个指向前一个节点，另一个指向后一个节点。**这样，链表中的每个节点都可以向前和向后遍历，从而提高了链表的操作效率。

双向链表的定义

双向链表的操作与普通链表类似，但需要注意的是，**在进行插入和删除操作时，需要同时更新前一个节点和后一个节点的指针。**例如，在插入节点时，需要确保新节点的前一个节点的后指针和后一个节点的前指针都正确地指向新节点；在删除节点时，需要更新被删除节点的前一个节点的后指针和后一个节点的前指针，使其指向彼此。

双向链表在实际应用中非常有用，例如在浏览器的历史记录中，每个页面都可以通过双向链表来表示，用户可以方便地向前和向后浏览历史记录。此外，双向链表还可以用于实现LRU缓存、二叉搜索树等。

总结

循环链表和双向链表都是链表的特殊形式，它们分别通过循环和双向指针的方式提高了链表的操作效率和灵活性。在实际应用中，应根据具体需求选择合适的链表形式。

回眸链表

链表是一种非常重要的数据结构，它通过指针将多个节点连接在一起，形成一个线性的数据结构。链表的优点是可以动态地分配内存，并且插入和删除操作非常高效。然而，链表的缺点是访问特定位置的元素需要从头开始遍历，因此查找操作的效率较低。

在实际应用中，链表通常用于实现栈、队列、哈希表等数据结构。此外，链表还可以用于实现文件系统、内存管理等操作系统中的重要功能。

随着计算机技术的不断发展，链表的实现方式也在不断改进。例如，循环链表和双向链表的出现，使得链表的操作更加灵活和高效。未来，随着硬件和软件技术的进一步发展，链表可能会在更多的领域得到应用。

关于下一篇，我们将讲述栈是如何实现的，以及我们如何用生活的例子来讲述栈。