开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 大话数据结构（三） -> 正文阅读

[数据结构与算法]大话数据结构（三）

大话数据结构

第三章线性表

3.1线性表的相关概念

定义：线性表( List ) : 零个或多个数据元素的有限序列。
1）首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
2）然后，线性表强调是有限的。
3）数学语言：若将线性表记为( ${a}_1$ ，···， ${a}_{i-1}$ ， ${a}_{i}$ ， ${a}_{i+1}$ ，…， ${a}_{n}$ ), 则表中 ${a}_{i-1}$ 领先于 ${a}_1$ ， ${a}_{i}$ 引领先于 ${a}_{i+1}$ ，称 ${a}_{i-1}$ 是 ${a}_{i}$ 的直接前驱元素， ${a}_{i+1}$ 是 ${a}_{i}$ 的直接后继元素。当 i=1，2 ，… ，n-1 时， ${a}_{i}$ 有且仅有一个直接后继，当i = 2，3，···，n 时， ${a}_{i}$ 有且仅有一个直接前驱。
4）线性表元素的个数n ( n > 0 ) 定义为线性表的长度，当n=0时，称为空表。i 为数据元素 ${a}_{i}$ 在线性表中的位序。
5）在较复杂的线性表中，一个数据元素可以由若干个数据项组成。
线性表的抽象数据类型
ADT线性表（List）
Data
　　线性表的数据对象集合为{ ${a}_1$ ， ${a}_{2}$ ， ${a}_{n}$ }, 每个元素的类型均为DataType。其中．除第一个元素 ${a}_1$ 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 ${a}_{n}$ 外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
　　InitList(* L): 初始化操作，建立一个空的线性表L。
　　ListEmpty(L): 若线性表为空，返回true，否则返回false 。
　　ClearList(* L)：将线性表清空。
　　GetElem(L, i, * e)：将线性表L中的第i个位置元素值返回给e。
　　LocateElem (L, e) : 在线性表L中查找与给定值e相等的元素，如果查找成功，
　　　　　　　　　　　返回该元素在表中序号表示成功；否则，返回0表示失败。
　　ListInsert ( * L, i , e) : 在线性表L中的第i个位置插入新元素e。
　　ListDelete (* L, i, *,e) : 删除线性表L中第i个位置元素，并用e返回其值。
　　ListLength(L) : 返回线性表L的元素个数。
endADT

3.2线性表的顺序存储结构

顺序存储定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
顺序存储方式（通常用一维数组实现顺序存储结构）

顺序存储的结构代码

#define MAXSIZE 20            /*存储空间初始分配量*/
typedef int ElemType;         /*ElemType类型根据实际情况而定,这里假设为int*/
typedef struct
{
    ElemType data[MAXSIZE];   /*数组存储数据元素．最大值为MAXSIZE*/
    int length;               /*线性表当前长度*/
}SqList;

描述顺序存储结构三个属性：
存储空间的起始位置：数组data, 它的存储位嚣就是存储空间的存储位置。
线性表的最大存储容量：数组长度MaxSize。
线性表的当前长度：length 。

数据长度与线性表长度区别
数组的长度是存放线性表的存储空间的长度，存储分配后这个最是一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
地址计算方法

线性表的第i个元索是要存储在数组下标为i - 1的位置，下图即数据元素的序号和存放它的数组下标之间存在对应关系。
存储器中的每个存储单元都有自己的编号，这个编号称为地址。那么线性表中第i + 1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系( LOC 表示获得存储位置的函数）。

$LOC({a}_{i})= LOC({a}_{1})+(i-1)*c$
通过这个公式可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用时间复杂度的概念来说，它的存取时间性能为O(1) 。通常把具有这一特点的存储结构称为随机存取结构。

3.3顺序存储结构的插入与删除

获得元素操作
如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。只要i的数值在数组下标范围内，就是把数组第i - 1下标的值返回即可。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码，如OK等*/
/*初始条件：顺序线性表L已存在，1=<i=<ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem(SqList L,int i,ElemType *e)
{
    if (L.length == O || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i - 1] ;
    return OK;
}

插入操作
插入算法的思路：
? 如果插入位置不合理，抛出异常；
? 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
? 从最后一个元素开始向前遍历到第1个位置，分别将它们都向后移动一个位置；
? 将要插入元素填入位置1处；
? 表长加1。

/*初始条件：顺序线性表L已存在，1=<i=<ListLength(L)*/
/*操作结果：在L中第i个位置之前插入新的数据元素e, L的长度加1*/
Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;
    if (L->length == MAXSIZE)         /*顺序线性表已经满*/
        return ERROR;
    if (i < l || i > L->length+l)     /*当i不在范围内时*/
        return ERROR;
    if (i <= L->length)               /*若插入数据位置不在表尾*/
    {
        for (k = L->length-l;k > i-l; k--)/*将要插入位置后数据元素向后移动一位*/
            L->data[k+1] = L->data[k];
     }
    L->data[i-1] = e;                 /*将新元素插入*/
    L->length++;
    return OK;
}

删除操作
删除算法的思路：
? 如果删除位置不合理，抛出异常；
? 取出删除元素；
? 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
? 表长减1。

/*初始条件：顺序线性表L已存在，1=<i=<ListLength(L)*/
/*操作结果：删除L的第i个数据元素．并用e返回其值,L的长度减1*/
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;
    if (L->length == 0)                /*线性表为空*/
        return ERROR;
    if (i < l || i > L->length+l)      /*删除位置不正确*/
        return ERROR;
    *e = L->data[i-1];
    if (i <= L->length)                /*若删除不是最后位置*/
    {
        for (k = i;k < L->length;k++)  /*将删除位置后继元素前移*/
            L->data[k-1] = L->data[k];
     }
    L->length--;
    return OK;
}

插入和删除的时间复杂度
1）最好的情况，如果元索要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1) , 因为不需要移动元素。
2）最坏的情况，如果元素要插入到第一个位置或者删除第一个元素，那就意味着要移动所有的元素向后或者向前，所以这个时间复杂度为O(n) 。
3）平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要移动n - i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，最终平均移动次数和最中间的那个元素的移动次数相等，为 $\frac{n-1}{2}$ 。故平均时间复杂度还是O(n)。
4）线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1) ; 而插入或删除时，时间复杂度都是O(n) 。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。
线性表顺序存储结构的优缺点

优点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间；
可以快速地存取表中任一位置的元素。
缺点
插入和删除操作需要移动大量元素；
当线性表长度变化较大时，难以确定存储空间的容量；
造成存储空间的＂碎片”。

3.4线性表的链式存储结构

线性表链式存储结构定义
　　线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。
　　为了表示每个数据元素 ${a}_{i}$ 与其直接后继数据元素 ${a}_{i+1}$ 之间的逻辑关系，对数据元素 ${a}_{i}$ 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 ${a}_{i}$ 的存储映像，称为结点( Node) 。
　　n 个结点( ${a}_{i}$ 的存储映像）连接成一个链表，即为线性表( ${a}_{1}，{a}_{2}，……，{a}_{n}$ ) 的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

　　把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每—个结点，其实就是上一个的后继指针指向的位置。同时我们规定，线性链表的最后一个结点指针为“空”（通常用NULL或"^" 符号表示）。

　　为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。
头指针与头结点的异同

头指针
1）头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
2）头指针具有标识作用，所以常用头指针冠以链表的名字。
3）无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
头节点
1）头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）。
2）有了头结点，对在第一元素节点前插入结点和删除第一结点，其操作与其它结点的操作就统一了。
3）头结点不一定是链表必须要素。

线性表链式存储结构代码描述
结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点 ${a}_{i}$ 的数据域我们可以用p->data来表示， p ->data的值是一个数据元素，结点 ${a}_{i}$ 的指针域可以用p->next来表示， p->next的值是一个指针，指向第i + 1个元索，即指向 ${a}_{i+1}$ 的指针。

/*线性表的单链表存储结构*/
typedef struct Node
{
    ElemType data;
    struct Node *next ;
} Node;
typedef struct Node *LinkList; /*定义LinkLi st*/

3.5单链表及其相关操作

读取
获得链表第i个数据的算法思路（主要核心思想就是”工作指针后移“）：
1）声明一个结点p指向链表第一个结点，初始化j从1开始；
2）当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点， j累加1;
3）若到链表末尾p为空，则说明第i个元素不存在；
4）否则查找成功，返回结点p的数据；
5）最坏情况的时间复杂度是O(n)。

/*初始条件：顺序线性表L已存在，1=<i=<ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem(LinkList L, int i , ElemType *e)
{
    int j;
    LinkList p;    /*声明一结点p*/
    p = L->next；  /*让p指向链表L的第一个结点*/
    j = 1;         /*j 为计数器*/
    while (p && j < i) /*p不为空或者计数器j还没有等于i时，循环继续*/
    {
        p = p -> next; /*让p指向下一个结点*/
        ++j ;
    }
    if(!p || j > i)
        return ERROR; /*第i个元素不存在*/
    *e = p->data;     /*取第i个元素的数据*/
    return OK;

插入
单链表第i个数据插入结点的算法思路：
1）声明一结点p指向链表第一个结点，初始化j从1开始；
2）当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点， j累加1;
3）若到链表末尾p为空，则说明第i个元素不存在；
4）否则查找成功，在系统中生成一个空结点s;
5）将数据元素e赋值给s -> data ;
6）单链表的插入标准语句s->next = p->next; p->next = s ;
7）返回成功。

/*初始条件：顺序线性表L已存在，1=<i=<ListLength(L)*/
/*操作结果：在L中第i个位置之前插入新的数据元素e, L的长度加1*/
Status ListInsert(LinkList *L, int i , ElemType e)
{
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while (p && j < i) /*寻找第i个结点*/
    {
        p = p -> next;
        ++j ;
    }
    if(!p || j > i)
        return ERROR; /*第i个元素不存在*/
    s = (LinkList) malloc (sizeof(Node));/*生成新结点*/
    s -> data = e;
    s -> next = p -> next;/*将p的后继结点赋值给s的后继*/
    p -> next = s;/*将s赋值给p的后继*/
    return OK;

删除
单链表第i个数据删除结点的算法思路：
1）声明一结点p指向链表第一个结点，初始化j从1开始；
2）当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一个结点， j累加1;
3）若到链表末尾p为空，则说明第i个元素不存在；
4）否则查找成功，将欲删除的结点p->next 赋值给q ;
5）单链表的删除标准语旬p->next=q->next ;
6）将q结点中的数据赋值给e , 作为返回；
7）释放q结点；
8）返回成功。

/*初始条件：顺序线性表L已存在，1=<i=<ListLength(L)*/
/*操作结果：删除L的第i个数据元素．并用e返回其值,L的长度减1*/
Status ListDelete(LinkList *L, int i , ElemType *e)
{
    int j;
    LinkList p,q;
    p = *L；
    j = 1;
    while (p -> next && j < i) /*遍历寻找第i个元素*/
    {
        p = p -> next;
        ++j ;
    }
    if(!(p -> next) || j > i)
        return ERROR;         /*第i个元素不存在*/
    q = p -> next;
    p -> next = q -> next;    /*将q的后继赋值给p的后继*/
    *e = q -> data;           /*将q结点中的数据给e*/
    free(q);                  /*让系统回收此结点，释放内存*/
    return OK;

插入和删除的时间复杂度
　　时间复杂度都是O(n) 。如果在我们不知道第1个元素的指针位萱，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第1个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n - i个元素，每次都是O(n) 。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n), 接下来只是简单地通过赋值移动指针而巳，时间复杂度都是O(1) 。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。
　　### 3.6单链表的整表创建
创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。
头插法
1）声明一结点p和计数器变量i;
2）初始化一空链表L;
3）让L的头结点的指针指向NULL, 即建立一个带头结点的单链表；
4）循环：
　　? 生成一新结点赋值给p;
　　? 随机生成一数字赋值给p的数据域p->data;
　　? 将p插入到头结点与前一新结点之间。

/*随机产生n个元素的值，建立带表头结点的单链线性表L(头插法）*/
void CreateListHead (LinkList *L, int n)
{
    LinkList p;
    int i ;
    srand (time (0)) ;                        /*初始化随机数种子*/
    *L = (LinkList) malloc (sizeof (Node)) ;
    (*L) -> next = NULL;                      /*先建立一个带头结点的单链表*/
    for (i = 0;i < n;i++)
    {
        p = (LinkList) malloc (sizeof (Node));/*生成新结点*/
        p->data = rand () %100 + 1 ;          /*随机生成100以内的数字*/
        p->next = (*L) -> next；
        (*L)->next = p ;                      /*插入到表头*/
        }
}

尾插法

/*随机产生n个元素的值，建立带表头结点的单链线性表L(尾插法）*/
void CreateListTail (LinkList *L, int n)
{
    LinkList p,r;
    int i ;
    srand (time (0)) ;                        /*初始化随机数种子*/
    *L = (LinkList) malloc (sizeof (Node)) ;  /*为整个链表*/
    r = *L;                                   /*r为指向尾部的结点*/
    for (i = 0;i < n;i++)
    {
        p = (LinkList) malloc (sizeof (Node));/*生成新结点*/
        p->data = rand () %100 + 1 ;          /*随机生成100以内的数字*/
        r->next = p ;                         /*将表尾终端结点的指针指向新结点*/
        r = p;                                /*将当前的新结点定义为表尾终端结点*/
        }
    r->next = NULL;                           /*表示当前链表结束*/
}

3.7单链表的整表删除

单链表整表删除的算法思路如下：
1）声明一结点p和q ;
2）将第一个结点赋值给p;
3）循环：
　　? 将下一结点赋值给q;
　　? 释放p;
　　? 将q 赋值给p。

/*初始条件：顺序线性表已存在，操作结果：将L重置为空表*/
Status ClearList (LinkList *L)
{
    LinkList p,q;
    p = (*L) -> next;       /*p指向第一个结点*/
    while(p)                /*没有到表尾*/
    {
        q = p -> next;
        free(p);
        p = q;
        }
    (*L)->next = NULL;      /*头结点指针域为空*/
    return OK;
}

3.8单链表结构与顺序存储结构优缺点

存储分配方式
? 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
? 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能

查找
? 顺序存储结构O(1)
? 单链表O(n)
插入和删除
? 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
? 单链表在找出某位置的指针后，插入和删除时间仅为O(1)

空间性能
? 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
? 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
小结
1）若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
2）当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多。

3.9静态链表

定义
　　用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。
　　让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data, 用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。
　　为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。
　　另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0。

eg：
静态链表的插入操作
静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。在动态链表中，结点的申请和释放分别借用malloc ()和free（）两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以需要自己实现这两个函数，才可以做插入和删除的操作。为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SLL (StaticLinkLiat space)
{
    int i = space[O].cur;           /*当首数组第一个元素的cur存的值，就是要返回的第一个备用空间的下标*/
    if (space[O].cur)
        space[O].cur = space[i].cur;/*由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用*/
    return i;
}

/*在L中第i个元素之前插入新的数据元素e*/
Status ListInsert (StaticLinkList, int i, ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;        /*注意K首先是最后一个元素的下标*/
    if (i < 1||i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SSL(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;
}

在这里插入图片描述

静态链表的删除操作

/*删除在L中第i个数据元素e*/
Status ListDelete (StaticLinkList L,int i)
{
    int j,k;
    if(i < 1||i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 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;
}
/*将下标为k的空闲结点回收到备用链表*/
void Free_SSL(StaticLinkList space,int k)
{
    space[k].cur = space[0].cur;/*把第一个元素cur值赋给要删除的分量cur*/
    space[O].cur = k;/*把要删除的分量下标赋值给第一个元素的cur*/
}

在这里插入图片描述

静态链表优缺点

优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点：1）没有解决连续存储分配带来的表长难以确定的问题
　　　2）失去了顺序存储结构随机存取的特性
总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

3.10循环链表

定义
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list) 。循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p ->next是否为空，现在则是p -> next 不等于头结点，则循环未结束。
改进
有了头结点时，我们可以用O(1) 的时间访间第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描一遍。为了实现用O(1) 的时间由链表指针访问到最后一个结点，我们设计了指向终端结点的尾指针。

终端结点用尾指针rear指示，则查找终端结点是O(1), 而开始结点，其实就是rear -> next -> next，其时间复杂也为O(1) 。
将两个循环链表合成一个表

    p = rearA -> next; /*保存A表的头结点*/
    rearA -> next = rearB-> next -> next;/*将本是指向B表的第一个结点（不是头结点）赋值给rearA->next*/
    rearB -> next = p;/*将原A表的头结点赋值给rearB->next*/
    free(p);/*释放p*/

3.11双向链表

单链表的双向链表
双向链表（double linked list) 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;/*直接前驱指针*/
    struct DuLNode *next;/*直接后继指针*/
}DulNode, *DuLinkList;

循环链表的双向链表

p -> next -> prior = p = p -> prior ->next

双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength , 查找元素的GetElem , 获得元素位置的LocateElem等，这些橾作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

双向链表的插入操作

s -> prior = p;            /*把p赋值给s的前躯*/
s -> next = p -> next;     /*把p->next 赋值给s的后继*/
p -> next -> prior = s ;   /*把s赋值给p->next的前躯*/
p -> next = s;             /*把s赋值给p的后继*/

双向链表的删除操作

p -> prior -> next = p -> next; /*把p->next赋值给p->prior的后继*/
p -> next -> prior = p -> prior;/*把p->prior赋值给p->next的前躯*/
free (p);                       /*释放结点*/

小结
双向链表相对于单链表来说，要更复杂一些，毕竟它多了prior指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多一些的。不过，由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。