Abo

数据结构-线性表

发表于 | 分类于 | 热度 ℃
字数统计 6.2k | 阅读时长 24


数据结构与算法-线性表部分,线性表较为基础，其中对链表的操作需要熟悉，之后我会补上链表操作练习

链表练习

fade

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

  • 线性表元素的个数n（n≥0）定义为线性表的长度，当n=0时，称为空表。
  • 在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
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

实现两个线性表集合A跟B的并集操作！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*将所有的在线性表Lb但不在La的数据元素插入到La中*/
void union(List *La,List 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,equal)) /*La中不存在和e相同数据元素*/
        ListInsert(La, ++La_len, e); /*插入*/
    }
}

线性表的顺序存储结构

  • 定义:指的是用一段地址连续的存储单元以此存储线性表的数据元素。

    以下是线性表的顺序存储的结构代码

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

  • 数组长度和线性表长度的区别：

  1. 数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的
  2. 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是会变化的
  3. 在任意时刻，线性表的长度应该小于等于数组的长度。
  • 地址计算方法
  1. 线性表的第i个元素是要存储在数组下标为i-1的位置，即线性表从1开始
  2. 用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，由此分配的数组空间要大于等于当前线性表的长度
  3. 存储器中的每个存储单元都有自己的编号，这个编号称为地址

LOC(a(i+1))=LOC(ai)+c

LOC(ai)=LOC(a1)+(i-1)*c

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

  • GetElem:将线性表L中的第i个位置元素值返回，就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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==0 || i<1 || i>L.length)
   return ERROR;
   *e=L.data[i-1];
   return OK;
}

==疑问：为什么是*e？==

  • ListInsert(*L,i,e):在线性表L中的第i个位置插入新元素e
  • 插入算法的思路：
  1. 如果插入位置不合理，抛出异常
  2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
  3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
  4. 将要插入元素填入位置i处
  5. 表长加一
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /*初始条件:顺序线性表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;
    }
  • ListDelete
  • 删除算法的思路:
  1. 如果删除位置不合理，抛出异常
  2. 取出删除元素
  3. 从删除元素位置开始遍历到最后一个元素，分别将它们都往前移动一个位置
  4. 表长减1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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;
    }

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

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

线性表的链式存储结构

  • 为了表示每个数据元素a1与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置).我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)
  • n个结点(ai的存储映像)链结成一个链表，即为线性表(a1，a2，…an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做==单链表==
  • 我们把链表中第一个结点的存储位置叫做头指针，规定最后一个结点指针为“空”(通常用NULL或^符号表)；有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个节点，称为头结点，头结点的指针域存储指向第一个结点的指针。
    头指针与头结点的异同
  • 头指针
  1. 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
  2. 头指针具有标识作用，所以常用头指针冠以链表的名字
  3. 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
  • 头结点
  1. 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)
  2. 有了头结点，对在第一元素结点前插入节点和删除第一结点，其操作与其它节点的操作就==统一==了
  3. 头结点不一定是链表必要元素
  • 线性表链式存储结构代码描述
  1. 若线性表为空表，则头结点的指针域为“空”

    单链表中，我们在C语言可用结构指针来描述

    1
    2
    3
    4
    5
    6
    7
    /*线性表的单链表存储结构*/
    typedef struct Node
    {
        ElemType data;
        struct Node *next;
    } Node;
    typedef struct Node *LinkList;/*定义LinkList*/

这波操作事后==了解==一下,翻一下结构体

  1. 结点由存放数据元素的数据域,存放后继结点地址的指针域组成

单链表的读取

  • 获得链表第i个数据的算法思路：
  1. 声明一个结点p指向链表第一个结点，初始化j从1开始
  2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
  3. 若到链表末尾p为空，则说明第i个元素不存在
  4. 否则查找成功，返回结点p的数据
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /*初始条件:顺序线性表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;
    }

单链表的插入与删除

s->next=p->next; p->next=s
这两句的顺序==不可交换==，自己想

  • 单链表第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. 返回成功
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /*初始条件:顺序线性表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;
    }

单链表的删除实质：p->next=p->next->next

用q来取代p->next,就是q=p->next;p->next=q->next;

  • 单链表第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. 返回成功
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /*初始条件:顺序线性表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;
    }

单链表的整表创建

  • 创建单链表的过程就是一个动态生成链表的过程，即从”空表”的初始状态起，依次建立各元素结点，并逐个插入链表
  • 单链表整表创建的算法思路:
  1. 声明一结点p和计数器变量i
  2. 初始化一空链表L
  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
  4. 循环:
    生成一新结点赋值给p；随机生成一数字赋值给p的数据域p->data;将p插入到头结点与前一新结点之间
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    /*随机生成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; /*插入到表头*/
        }
    }

求问L,L,(L)的区别？ 如果要改变变量的值就用指针，不改变就用变量本身
LinkList等同于Node ，所以L要加

函数rand()跟srand()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*随机生成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=(Node*)malloc(sizeof(Node));/*生成新结点*/
        p->data=rand()%100+1;/*随机生成100以内的数字*/
        r->next = p;/*将表尾终端结点的指针指向新结点*/
        r=p;
    }
    r->next=NULL;/*表示当前链表结束*/
}

单链表的整表删除

  • 单链表整表删除的算法思路如下:
  1. 声明一结点p和q；
  2. 将第一个结点赋值给p
  3. 循环：将下一结点赋值给q；释放p；将q赋值给p。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /*初始条件：顺序线性表L已存在，操作结果：将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;
    }

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

简单地对单链表结构和顺序存储结构做对比：

  • 存储分配方式
  1. 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  2. 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
  • 时间性能
  1. 查找：①顺序存储结构O(1)；②单链表O(n)
  2. 插入与删除：①顺序存储结构需要平均移动表长一半的元素，时间为O(n)； ②单链表在线出某位置的指针后，插入和删除时间仅为O(1)
  • 空间性能
  1. 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
  2. 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
    通过上面对比，我们可以得出一些经验性的结论
  3. 若线性表需要频繁查找，很少进行插入或删除时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如游戏开发，对于用户注册的个人信息，出来注册时插入数据外，绝大多数情况都是读取，所以应该考虑顺序存储结构。而游戏装备道具就用单链表结构。
  4. 当线性表元素个数变化很大或者不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，则用顺序存储结构效率会高很多。

静态链表

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

    为了方便插入数据，通常会把数组建立得大一些，以便有一些空闲空间插入不至于溢出

    1
    2
    3
    4
    5
    6
    7
    8
    /*线性表的静态链表存储结构*/
    #define MAXSIZE 1000 /*假设链表的最大长度是1000*/
    typedef struct
    {
        ElemType data;
        int cur; /*游标(cursor),为0
        时表示无指向*/
    }Component,StaticLinkList[MAXSIZE];

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据，把未被使用的数组元素称为备用链表。

数组第一个元素，即下标为0的元素的cur存放备用链表的第一个结点的下标;而数组的最后一个元素的cur则存放第一个有数值的元素的下表，相当于单链表中的头结点，当整个链表为空时，则为0

1
2
3
4
5
6
7
8
9
10
/*将一维数组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;
}

  • 静态链表的插入操作

    静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放

    动态链表，结点的申请和释放分别借用malloc()和free()两个函数来实现，而静态链表操作的是数组，我们需要自己实现这两个函数

    为了辨明数组中哪些分量未被使用，解决方法是将所有未被使用过的及被删除的分量用游标链成一个备用的链表，每当插入时，可以从备用链表上取得第一个结点作为待插入的新结点

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

需要找到接替者才能继续分配新的空闲分量

现在我们如果需要在乙丁之间插入丙，我们只需要让丙在7号备用位待着，把乙的cur改为7，再让丙的cur改为3即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status ListInsert(StaticLinkList L,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；
}

  • 静态链表的删除操作

    和前面一样，删除元素时，原来是需要释放结点的函数free().现在我们也得自己实现它:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /*删除在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;
    }

而关于Free_SSL(L,j)

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

当然，静态链表也有相应的其他操作的相关实现，比如代码中的ListLength

1
2
3
4
5
6
7
8
9
10
11
12
/*初始条件：静态链表L已存在，操作结果：返回L中的数据个数*/
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE-1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

回顾：sizeof()和strlen

静态链表优缺点

  • 优点
  1. 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
  • 缺点
  1. 没有解决连续存储分配带来的表长难以确定的问题
  2. 失去了顺序存储结构随机存取的特性

    总的来说，静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

循环链表

  • 定义:将单链表中终端结点的指针端由空指针改为指向头结点就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list)
  • 循环链表和单链表的主要差异在判断条件上：原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束

    在单链表中，我们有了头结点，可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描一遍

    如用O(1)的时间由链表指针访问到最后一个结点,则需改造一下循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表，这样查找开始结点和终端结点都很方便

    终端结点用尾指针rear指示，则查找终端结点是O(1),而开始结点，其实就是rear->next->next，其时间复杂也为O(1)

  • 举个程序的例子，要将两个循环链表合成一个表时，有了尾指针就非常简单
    1
    2
    3
    4
    p = rearA->next;/*保存A表的头结点*/
    rearA->next=rearB->next->next;/*将本是指向B表的第一个结点(不是头结点)赋值给rearA->next*/
    rearB->next=p;/*将原A表的头结点赋值给rearB->next*/
    free(p);/*释放p*/

双向链表

  • 定义：双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。
    1
    2
    3
    4
    5
    6
    7
    /*线性表的双向链表存储结构*/
    typedef struct DuLNode
    {
        ElemType data;
        struct DuLNode *prior;/*直接前驱指针*/
        struct DuLNode *next;/*直接后继指针*/
    }DulNode,*DuLinkList;

既然单链表有循环链表，那么双向链表也可以是循环链表

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

  • 双向链表的插入
    将结点s插入到结点p和p->next之间

顺序很重要，不能写反

1
2
3
4
s->prior = p;/*将p赋值给s的前驱*/
s->next = p->next;/*把p->next赋值给s的后继*/
p->next->prior = s;/*把s赋值给p->next的前驱*/
p->next = s;/*把s赋值给p的后继*/

顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继

  • 双向链表的删除
    1
    2
    3
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);

多结合图形记忆

总结回顾

  • 线性表
  1. 顺序存储结构
  2. 链式存储结构
  • 单链表
  • 静态链表
  • 循环链表
  • 双向链表