链式存储结构之双向链表与跳表

链式存储结构之双向链表与跳表-五分钟学算法

只要大家坐过火车，对于双向链表的理解就相当简单。双向链表就是在单链表的基础之上，为每一个结点增加了它的前继结点。双向链表的定义如下：

typedef struct DaulNode
{
    ElemType data;
    struct DaulNode *prior;  //前驱结点
    struct DaulNode *next;   //后继结点
}DaulNode, *DuLinkList;

下图可以更直观地反映双向链表的形式：

单链表存在循环链表，双向链表也有循环链表：01.
双向链表的重要操作

双向链表的插入操作

插入操作其实并不复杂，不过顺序很重要，千万不要写反了。

双向链表的删除操作

程序员永远都知道，删除一个元素更加容易，你说呢？

双向链表相对于单链表来说，是更复杂一些，每个结点多了一个prior指针，对于插入和删除操作的顺序一定要格外小心，就像你的 “求生欲”。

双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间。

02.

双向链表的两个实例

凯撒密码

题目描述：

–要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，输出结果：

–DEFGHIJKLMNOPQRSTUVWXYZABC

–同时需要支持负数，例如用户输入-3，输出结果：

–XYZABCDEFGHIJKLMNOPQRSTUVW

双向循环链表初始化操作（InitList()函数）执行流程：

左右滑动查看双向链表的初始化过程，InitList()函数的执行过程

Caesar()函数的执行过程：

左右滑动查看Caesar()函数的执行过程

维吉尼亚加密

Vigenere（维吉尼亚）加密：

当输入明文，自动生成随机密匙匹配明文中每个字母并移位加密。

维吉尼亚加密与凯撒加密最大的区别就是，凯撒加密的秘钥是固定的，而维吉尼亚加密的秘钥随机生成，下面给出该加密方法实现的主要函数，完整的工程代码后台回复 「Vigenere」 即可获得。

维吉尼亚加密算法的加密流程：

左右滑动查看维吉尼亚加密算法的执行流程

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

typedef struct DaulNode
{
    ElemType data;
    struct DaulNode *prior;
    struct DaulNode *next;
}DaulNode, *DuLinkList;

Status InitList(DuLinkList *L)
{
    DaulNode *p, *q;
    int i;

    *L = (DuLinkList)malloc(sizeof(DaulNode));
    if(!(*L))
    {
        return ERROR;
    }

    (*L)->next = (*L)->prior = NULL;
    p = (*L);

    for( i = 0; i < 26; i++)
    {
        q = (DaulNode *)malloc(sizeof(DaulNode));
        if( !q )
            return ERROR;

        q->data = 'A'+i;
        q->prior = p;
        q->next = p->next;
        p->next = q;

        p = q;
    }

    p->next = (*L)->next;
    (*L)->next->prior = p;

    return OK;
}

void Caesar(DuLinkList *L, int i)
{
    if( i > 0 )
    {
        do
        {
            (*L) = (*L)->next;
        }while(--i);
        printf("%d", i);
    }

    if(i < 0)
    {
        (*L) = (*L)->next->prior;
        do
        {
            (*L) = (*L)->prior;
        }while( ++i );
    }

}

int main()
{
    DuLinkList L;
    int i, n;

    InitList(&L);

    printf("Please input n :");
    scanf("%d",&n);
    printf("n");
    Caesar(&L, n);

    for( i=0; i < 26; i++)
    {
        L = L->next;
        printf("%c",L->data);
    }
}

03.

跳表(Skip List)

在解释跳表之前，先看一个简单的有序单链表：

对于上面这个有序单链表，我们查找一个元素的平均时间复杂度为O(n)，那么是否有一种更快的方式查找元素呢？

答案是肯定的啦！我们可以通过在原始链表的基础之上，为其增加索引来解决这个问题，如下图：

我们以查找元素 6 为例，当我们在原始链表（Normal Line）上进行查找，将需要从头结点开始依次遍历直至找到值为6的结点；当我们在一级索引（Express Lane）上进行查找，将只需要从1->3->5->6，就可以找到元素6。相当于之前查找步数的一半，速度提升了一倍，那我们是否可以更快呢，当然可以，我想你已经想到啦！

通过上图可以发现，从二级索引开始，我们仅需要1->5->6，进一步的提升了查找的效率。

注意：跳表只能用于元素有序的情况

所以跳表对标的是平衡树和二分查找，是一种 插入/删除/搜索 都是O(log n) 的数据结构。1989年实现。

它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此，在一些热门的项目里用来代替平衡树，如Redis、LevelDB 等。

跳表查找的时间复杂度分析：

跳表查找的空间复杂度分析：

总结：跳表的查询时间复杂度为O(log(n))，空间复杂度为O(n)。

END

作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。