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

只要大家坐过火车,对于双向链表的理解就相当简单。双向链表就是在单链表的基础之上,为每一个结点增加了它的前继结点。双向链表的定义如下:
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

作者:景禹,一个追求极致的共享主义者,想带你一起拥有更美好的生活,化作你的一把伞。
链式存储结构之双向链表与跳表