大话数据结构第三章线性表

本文最后更新于：2020年2月19日晚上

线性表：零个或多个数据元素的有限序列。

3.1-3.2线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

若将线性表记为（a_1，…，a_(i−1)，a_i，a_(i+1)，…，a_n），则表中a_(i−1) 领先于a_i，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 有且仅有一个直接前驱。
如图3-2-1所示。
3-2-1

所以线性表元素的个数n（n>0）定义为线性表的长度，当n=0时，称为空表。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

3.3线性表的抽象数据类型

线性表的抽象数据类型定义如下：

ADT线性表（List）
Data
    线性表的数据对象集合为{a1，a2…，an），每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
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.3.1两个线性表集合的并集操作

要使得集合A=AUB。说白了，就是把存在集合B中但并不存在A中的数据元素插入到A中即可。
仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容易想到的。
我们假设La表示集合A，Lb表示集合B，则实现的代码如下：

/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void unionL(SqList *La, SqList Lb)
{
    int La_len, Lb_len, i;
    ElemType e;                          /*声明与La和Lb相同的数据元素e*/
    La_len = ListLength(*La);                /*求线性表的长度*/
    Lb_len = ListLength(Lb);
    for (i = 1; i <= Lb_len; i++)
    {
        GetElem(Lb, i, &e);           /*取Lb中第i个数据元素赋给e*/
        if (!LocateElem(*La, e))           /*La中不存在和e相同数据元素*/
            ListInsert(La, ++La_len, e);          /*插入*/
    }
}

3.4线性表的顺序存储结构

3.4.1顺序存储定义

线性表的两种物理结构的第一种——顺序存储结构。
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

3.4.2顺序存储方式

可以用C语言（其他语言也相同）的一维数组来实现顺序存储结构。
线性表的顺序存储的结构代码如下

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

这里，我们就发现描述顺序存储结构需要三个属性：
• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量：数组长度MaxSize。
• 线性表的当前长度：length。

3.4.3数据长度与线性表长度区别

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

3.4.4地址计算方法

存储器中的每个存储单元都有自己的编号，这个编号称为地址。
假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。
LOC（a_(i+1)）=LOC（a_i）+c
所以对于第i个数据元素ai的存储位置可以由a1推算得出：
LOC（a_i）=LOC（a_1）+（i-1）*c

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

3.5.1获得元素操作

我们要实现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个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L, int i, ElemType *e)
{
    if (L.length == 0 || i<1 || i>L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

3.5.2插入操作

插入算法的思路：
• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置i处；
• 表长加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<1 || i>L->length + 1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
        return ERROR;
    if (i <= L->length)        /* 若插入数据位置不在表尾 */
    {
        for (k = L->length - 1; k >= i - 1; k--)  /* 将要插入位置之后的数据元素向后移动一位 */
            L->data[k + 1] = L->data[k];
    }
    L->data[i - 1] = e;          /* 将新元素插入 */
    L->length++;
    return OK;
}

3.5.3删除操作

删除算法的思路：
• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
• 表长减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<1 || i>L->length)         /* 删除位置不正确 */
        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;
}

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O（1）；而插入或删除时，时间复杂度都是O（n）。

3.5.4线性表顺序存储结构的优缺点

线性表的顺序存储结构的优缺点如图3-5-3所示。
3-5-3

3.6线性表的链式存储结构

3.6.2线性表链式存储结构定义

为了表示每个数据元素a_i 与其直接后继数据元素a_(i+1) 之间的逻辑关系，对数据元素a1来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素a_i 的存储映像，称为结点（Node）。
n个结点（a_i 的存储映像）链结成一个链表，即为线性表（a_1，a_2，…，a_n）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
我们把链表中第一个结点的存储位置叫做头指针,线性链表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。
有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息。

3.6.3头指针与头结点的异同

3-6-3

3.6.4线性表链式存储结构代码描述

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

节点Node是由存放数据元素的数据域和存放后继节点地址的指针域组成。

3.7单链表的读取

获得链表第i个的数据的算法思路：

声明一个结点p指向链表第一个结点，初始化j从1开始;
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
若到链表末尾p为空，则说明第i个元素不存在;
否则查找成功，返回结点p的数据。

实现代码算法如下：

/* 初始条件：顺序线性表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;
}

这个算法的最坏情况时间复杂度为O(n)。

3.8 单链表的插入和删除

3.8.1 单链表的插入

图3-8-1
假设上一个结点是p，下一个结点是p->next,现在要把结点s插入这两个结点中去。只需要2行代码：
s->next=p->next;//先让s的指针域指向p->next
p->next=s;//把s的地址赋给p的指针域

ps:这两句顺序不能交换。
如果先p->next=s;再s->next=p->next;就等于s->next=s;
所以这2句如论如何都不能反，这点初学者一定要注意。

单链表第i个数据插入结点的算法思路：

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

实现代码算法如下:

/* 初始条件：顺序线性表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));  /*  生成新结点(C语言标准函数) */
    s->data = e;  
    s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
    p->next = s;          /* 将s赋值给p的后继 */
    return OK;
}

3.8.2 单链表的删除

3-8-5
要删除节点q，其实就是要让p->next=q->next;
单链表第i个数据删除结点的算法思路：

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

实现代码算法如下：

/* 初始条件：顺序线性表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;              //q结点指向要删除的结点（即要删除的结点地址赋值给q）
    p->next = q->next;            /* 将q的后继(第三个结点)赋值给p的后继 */
    *e = q->data;               /* 将q结点中的数据给e */
    free(q);                    /* 让系统回收此结点，释放内存 */
    return OK;
}

分析一下刚才我们讲解的单链表插入和删除算法，我们很容易推导出：它们的时间复杂度都是O（n）。
显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

3.9单链表的整表创建

单链表整表创建的算法思路：

声明一结点p和计数器变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
- 生成一新结点赋值给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)); /* L为整个线性表 */
    r=*L;                                /* r为指向尾部的结点 */
    for (i=0; i<n; i++)
    {
        p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
        p->data = rand()%100+1;           /*  随机生成100以内的数字 */
        r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
        r = p;                            /* 将当前的新结点定义为表尾终端结点 */
    }
    r->next = NULL;                       /* 表示当前链表结束 */
}

PS：这里需解释一下，r->next=p的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，如图3-9-2所示，当中①位置的连线就是表示这个意思。
3-9-2
r=p的意思请看图3-9-3，就是本来r是a_(i-1)元素的结点，现在它已经不是最后的结点了，现在最后的结点是a_i，所以应该将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。
3-9-3

循环结束后，那么应该让这个链表的指针域置空，因此有了r->next=NULL，以便以后遍历时可以确认其是尾部。

3.10单链表的整表删除

单链表整表删除的算法思路如下：

声明一结点p和q；
将第一个结点赋值给p；
循环：
- 将下一结点赋值给q；
- 释放p；将q赋值给p。

实现代码算法如下：

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;   //下一个结点地址赋值给临时结点q
        free(p);     //释放p结点内存
        p=q;         //临时结点q的地址赋值给p，使p能够指向继续指向下一个结点
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}

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

简单地对单链表结构和顺序存储结构做对比,如图3-11-1：
3-11-1

通过上面的对比，我们可以得出一些经验性的结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。

总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。

3.12静态链表

静态链表是由数组组成。
我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next 指针，存放该元素的后继在数组中的下标。
我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。
静态链表的结构定义如下：

/* 线性表的静态链表存储结构 */
typedef struct
{
    ElemType data;
    int cur;  /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];

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

初始化数组状态，代码如下：

/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space)
{
    int i;
    for (i=0; i<MAXSIZE-1; i++)  
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
    return OK;
}

3.12.1静态链表的插入操作

在静态链表中，需要我们自己实现结点的申请和释放这2个函数，才可以做插入和删除的操作。
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

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

这段代码有意思，它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标,同时把这个空闲的下标给space[0].cur，之后就可以继续分配新的空闲分量，实现类似mallbc（）函数的作用。
插入操作的实现代码如下：

/*  在L中第i个元素之前插入新的数据元素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_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个元素之前元素的ur */
        return OK;
    }
    return ERROR;
}

3.12.2静态链表的删除操作

删除元素时，实现的代码如下：

/*  删除在L中第i个数据元素   */
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;
}

释放结点的函数代码如下：

/*  将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k)
{  
    space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
}

返回静态链表长度的代码实现如下：

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

3.12.3静态链表优缺点

总结一下静态链表的优缺点（见图3-12-5）：
3-12-5
总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

3.13循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）。
其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。
在单链表中，我们有了头结点时，我们可以用O（1）的时间访问第一个结点，但如果想要用O（1）的时间访问到最后一个结点，则需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表（如图3-13-5）。
3-13-5
从上图可以看出，终端结点用尾指针rear指示，则查找终端结点是O（1），而开始结点，其实就是rear->next->next，其时间复杂也为O（1）。
举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB，如图3-13-6所示。
3-13-6
要想把它们合并，只需要如下的操作即可，如图3-13-7所示。
3-13-7
具体代码如下：

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

3.14双向链表

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

/*线性表的双向链表存储结构*/
typedef struct DulNode
{
    ElemType data；
    struct DuLNode *prior；/*直接前驱指针*/
    struct DuLNode *next；/*直接后继指针*/
}DulNode，*DuLinkList；

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。
双向链表的循环带头结点的空链表如图3-14-3所示。
3-14-3
非空的循环的带头结点的双向链表如图3-14-4所示。
3-14-4
PS：双向链表在插入和删除时，需要更改两个指针变量。
插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。
我们现在假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间需要下面几步，如图3-14-5所示。
3-14-5

s->prior=p;/*把p赋值给s的前驱，如图中①*/
s->next=p->next;/*把p->next赋值给s的后继，如图中②*/
p->next->prior=s;/*把s赋值给p->next的前驱，如图中③*/
p->next=s;/*把s赋值给p的后继，如图中④*/

关键在于它们的顺序，由于第2步和第3步都用到了p->next。如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

若要删除结点p，只需要下面两步骤，如图3-14-6所示。
3-14-6

p->prior->next=p->next；/*把p->next赋值给p->prior的后继，如图中①*/
p->next->prior=p->prior；/*把p->prior 赋值给p->next的前驱，如图中②*/
free（p）；/*释放结点*/

3.15总结回顾

这一章，主要讲的是线性表。
先谈了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型，如它的一些基本操作。
之后我们就线性表的两大结构做了讲述，先讲的是比较容易的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。通常我们都是用数组来实现这一结构。
后来是我们的重点，由顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式，如单链表、循环链表和双向链表做了讲解，另外我们还讲了若不使用指针如何处理链表结构的静态链表方法。
总的来说，线性表的这两种结构（如图3-15-1所示）是后面其他数据结构的基础，把它们学明白了，对后面的学习有着至关重要的作用。
3-15-1

读书笔记大话数据结构

读书笔记数据结构线性表

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

大话数据结构第四章栈与队列上一篇

大话数据结构第三章 线性表

3.1-3.2线性表的定义

3.3线性表的抽象数据类型

3.3.1两个线性表集合的并集操作

3.4线性表的顺序存储结构

3.4.1顺序存储定义

3.4.2顺序存储方式

3.4.3数据长度与线性表长度区别

3.4.4地址计算方法

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

3.5.1获得元素操作

3.5.2插入操作

3.5.3删除操作

3.5.4线性表顺序存储结构的优缺点

3.6线性表的链式存储结构

3.6.2线性表链式存储结构定义

3.6.3头指针与头结点的异同

3.6.4线性表链式存储结构代码描述

3.7单链表的读取

3.8 单链表的插入和删除

3.8.1 单链表的插入

3.8.2 单链表的删除

3.9单链表的整表创建

3.10单链表的整表删除

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

3.12静态链表

3.12.1静态链表的插入操作

3.12.2静态链表的删除操作

3.12.3静态链表优缺点

3.13循环链表

3.14双向链表

3.15总结回顾

大话数据结构第三章线性表