大话数据机构_线性表

欢迎关注我的微信公众号【万能的小江江】

线性表的定义

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

​ 第一个元素没有前驱节点，最后一个元素没有后继节点，其他每一个元素都只有一个前驱节点和后续节点

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

线性表的抽象数据类型

ADT 线性表（List）
Data
    线性表的数据对象集合（a1,a2,...,an），每个元素的类型均为DataType
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

​ 假设La表示集合A，Lb表示集合B。现在要实现两个线性表集合A和B的并集操作（把存在B但不在A中的数据元素插入到A中）

/*
将所有在线性表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))
            ListInsert(La,++La_Len,e);//插入
    }
}

​ 复杂的个性化操作，其实就是把基本操作组合起来实现的

线性表的顺序存储结构

顺序存储定义

​ 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

顺序存储方式

​ 长度固定，数据多了会溢出，数据不够会浪费

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

顺序存储结构需要三个属性

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
• 线性表的最大存储容量：数组长度MaxSize
• 线性表的当前长度：length

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

​ 数组的长度是存放线性表存储空间的长度，存储分配后这个量一般是不变的（虽然可以动态分配数组，不过会带来性能上的损耗）

​ 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的

​ 在任意时刻，线性表的长度应该小于等于数组的长度

地址计算方法

​ 分配的数组空间要大于等于当前线性表的长度

​ 存储器中每个存储单元都有自己的编号，这个编号称为地址

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

获得元素操作

​ 实现GetElem操作，就将线性表L中的第i个位置元素值返回就可

#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;
}

​ 这里的返回类型Status是一个整型，返回OK代表1，ERROR代表0

插入操作

​ 我们现在要实现ListInsert(*L,i,e)操作，在线性表L中的第i个位置插入新元素e

插入算法的思路

• 如果插入位置不合理，抛出异常
• 如果线性表长度大于等于数组长度，抛出异常或动态增加容量
• 从最后一个元素开始向前遍历到第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;
}

删除操作

删除算法的思路

• 如果删除位置不合理，抛出异常
• 取出删除元素
• 从删除元素位置开始遍历到最后一个元素位置，分别把它们都向前移动一个位置
• 表长减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)

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

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间（不用设置专门的指针域）
• 可以快速地存取表中任一位置的元素（感觉也不是很快hhh）

缺点

• 插入和删除操作需要移动大量的元素（对！好麻烦的说）
• 当线性表长度变化较大时，难以确定存储空间的容量（要是很长，就很难确定辣）
• 造成存储空间的“碎片”（看不懂…）

什么是存储空间碎片

​ 采用分区式存储管理的系统，在储存分配过程中产生的、不能供用户作业使用的主存里的小分区称成“内存碎片”。内存碎片分为内部碎片和外部碎片

​ 动态分配内存都会造成内存碎片

为什么会有内存碎片

​ 内部碎片的产生是因为所有的内存分配必须起始于可被4、8、16整除的地址（视处理器架构而不同），或者因为MMU的分页机制限制。比如某客户机请求43字节内存块，没有合适大小的内存块，就会分配44字节或者48字节这样大些的内存块。因为所需大小四舍五入而产生的多余空间，就叫做内存碎片

​ 外部碎片的产生是因为频繁的分配与回收物理页面，而导致大量连续且小的页面块夹杂在已分配的页面中间。比如有个100个单位的连续空闲内存空间，范围是0-99。从中申请10个单位的内存，那么申请的内存块就是0-9区间，如果在申请一个内存大小为5个单位，之后分配的内存块就是10-14区间。如果把第一块内存块释放，在申请一块20个的单位的内存块，之前释放的内存块无法满足新内存块的要求，就只能从15开始再去分配。如果10-14一直被占用，之后申请的都大于10个单位，那么0-9就永远用不上，变成了外部碎片

内部碎片定义

​ 已经被分配出去，却不能被利用的内存空间

外部碎片定义

​ 还没被分配出去（不属于任何进程），但是由于太小了，无法分配给申请内存空间的新进程的内存空闲区域

减少内存碎片方法

• 确保被分割的内存块尽可能大

• 将相邻的空闲内存块连接起来

• 用一些避免内存碎片的工具：

  专为分布式高可用性容错系统开发的 OSE 实时操作系统可提供三种运行时内存分配程序：

  1. 内核 alloc()，它根据系统或内存块池来分配；（速度快、产生的内存碎片少，有判定功能）
  2. 堆 malloc()，根据程序堆来分配； （内存开销比alloc小，内部碎片比alloc少，外部碎片比alloc多）
  3. OSE 内存管理程序 alloc_region，它根据内存管理程序内存来分配（需要大块内存的时候用）

线性表的链式存储结构

顺序存储结构不足的解决办法

​ 顺序存储结构在插入和删除时需要移动大量的元素，这是它的缺点。解决办法就是让每个元素随机排放，哪里有空位放哪里，再单独分别告诉每个元素它下一个元素的地址（指针域），这就是链表

线性表链式存储结构定义

​ 线性表的链式存储结构得到特点是用任意一组存储单元存取线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这些数据元素可以存在内存未被占有的任意位置

​ 就是现在每个存储元素除了要存储数据元素信息外，还要存储它的后续元素的存储地址。两部分信息组成数据元素ai的存储映像，称为结点Node

头指针与头节点的异同

头指针

• 头指针是链表指向第一个结点的指针，如果链表有头结点，就是指向头结点的指针
• 头指针有标识的作用，所有经常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入节点和删除第一节点，它的操作和其他节点的操作就统一了
• 头节点不一定是链表的必要元素

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

​ 若线性表为空表，头节点的指针域就为“空”

​ 链表数据元素之间的关系是逻辑关系，不是空间关系

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

​ 节点由存放数据元素的数据域存放后继节点地址的指针域组成

单链表的读取

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

1. 声明一个节点p指向链表第一个节点，初始化j从1开始
2. 当j<1时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1
3. 知道链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，返回节点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 < 1) //p不为空或者计数器j还没有等于i时，循环继续
    {
        p = p -> next; //让p指向下一个节点
        ++j;
    }
    if (!p || j>1)
        return ERROR; //第i个元素不存在
    *e = p -> data; //取第i个元素的数据
    return OK;
}

​ 这个算法的时间复杂度取决于i的位置，当i=1时，不需要遍历，当i=n时要遍历n-1次，所以最坏情况的时间复杂度是O(n)

​ 因为链表没有定义表长，不知道要循环多少次，所以不方便用for来控制循环。主要核心思想是“工作指针后移”

单链表的插入与删除

单链表的插入

​ 单链表的插入，要插入的节点是s，要实现p，p->next和s之间的逻辑关系变化

​ 我们只需要让s->next和p->next的指针做一些改变

s -> next = p ->next;
p -> next = s; //这两句不能交换顺序！！

​ 让p的后继节点变成s的后继节点，再把s变成p的后继节点

代码交换顺序的结果

​ 如果先p -> next = s；再s -> next = p -> next

​ 第一句会使p -> next 覆盖成s的地址，这时候再s -> next = p -> next，就等于s -> next = s（自己等于自己）

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

1. 声明一节点p指向链表的第1个节点，初始化j从1开始
2. 当j<1时，遍历链表，让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 < 1) //寻找第i个节点
    {
        p = p -> next;
        ++j;
    }
    if (!p || j > 1)
        return ERROR; //第i个元素不存在
    s = (LinkList)malloc(sizeof(Node));//生成新的节点
    s -> data = e;
    s -> next = p -> next; //把p的后继节点赋值给s的后继
    p -> next = s; //把s赋值给p的后继
    return OK;
}

malloc函数的作用

​ 按照给定的数据类型，分配相应的空间，生成一个新的节点

单链表的删除

​ 实际就是 p -> next = p -> next -> next，用q来取代p -> next就是

q =  p -> next;
p ->next =q -> next;

单链表第i个数据删除节点的算法思路：

1. 声明一节点p指向链表第一个节点，初始化j从1开始
2. 当j<1时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，把想要删除的节点p->next赋值给q
5. 单链表的删除标准语句p->next = q->next
6. 把q节点中的数据赋值给e作为返回
7. 释放q节点（free(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 < 1) //遍历寻找第i个元素
    {
        p = p -> next;
        ++j;
    }
    if (!(p -> next) || j > 1)
        return ERROR; //第i个元素不存在
    q = p -> next;
    p - next = q -> next; //把q的后继赋值给p的后继
    *e = q -> data; //把q节点中的数据给e
    free(q); //让系统回收此节点，释放内存
    return OK;
}

比较单链表的插入和删除

​ 其实它们都是由两部分组成，第一部分是遍历查找第i个元素，第二部分是插入和删除元素

​ 它们的时间复杂度都是O(n)

​ 如果一次要在第i个位置插入10个元素，链表找到第i个位置的是按复杂度是O(n)，接下来的几次就是简单地通过赋值移动指针，时间复杂度都是O(1)。如果是顺序存储结构的线性表，则每次插入时间复杂度都是O(n)

​ 所以，在进行插入或删除频繁的操作时，单链表的效率优势越发明显

单链表整表的创建

​ 单链表创建的过程其实就是一个动态生成链表的过程，即从“空表”的初始状态开始，一次建立各元素节点，并逐个插入链表

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

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 CreateListHead(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; //表示当前链表结束
}

​ 循环结束后，应该让整个链表的指针域置空，所以有一个r->next = NULL;，以便以后遍历的时候可以确认它是尾部

单链表的整表删除

​ 不打算使用这个单链表时，需要销毁它，在内存中将它释放掉，以便留出空间给其他程序或软件使用

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

1. 声明一节点p和q

2. 将第一个节点赋值给p

3. 循环：

   • 将下一节点赋值给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 = q; //把q赋值给p
       }
       (*L) -> next = NULL; //头节点指针域为空
       return OK;
   }

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

存储分配方式：

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能：

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

空间性能：

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了容易发生溢出
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

总结：

• 如果线性表需要频繁查找，很少进行插入和删除操作，适合用顺序存储结构（因为顺序存储结构可以用二分法查找，时间复杂度为log2(n)）
• 如果需要频繁插入和删除，适合用单链表结构
• 当线性表中元素的个数变化较大或者根本不知道有多大的适合，最好用单链表结构，这样可以不用考虑存储空间大小的问题
• 如果事先知道线性表的大致长度，用顺序存储结构效率就会高很多

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

为什么二分法查找的时间复杂度是log2(n)

​ 二分查找在最坏的情况下依次是n/2,n/4,n/8。。。。 一直到1为止，由题意可得

n(1/2)x = 1

参考自：https://www.cnblogs.com/yellowgg/p/11272908.html

静态链表

​ 我们都知道数组的元素都是由两个域组成的，data域和cur域。数据域data用来存放数据元素，游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标

​ 我们把这种用数组描述的链表叫做静态链表，或者叫游标实现法

​ 为了方便插入数据，可以把数组建立的大一些，以便有一些空闲空间便于插入的时候不容易溢出

/*线性表的静态链表存储结构*/
#define MAXSIZE 1000 /*假设链表的最大长度是1000*/
typedef struct
{
    ElemType data;
    int cur; //游标（Cursor），为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

第一个元素和最后一个元素

​ 第一个元素和最后一个元素要作为特殊元素处理，不存数据

​ 备用链表就是未被使用的数组元素

​ 数组的第一个元素的cur用来存放备用链表第一个节点的下标

​ 数组的最后一个元素的cur存放第一个有效数值元素的下标，相当于单链表中头节点的作用

​ 初始化的数组状态如下：

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

静态链表的插入操作

需要解决的问题

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

动态链表中是怎么做的

​ 动态链表中节点的申请和释放分别用malloc()和free()两个函数来实现

静态链表中要怎么做

​ 静态链表中，操作的是数组，不存在像动态链表的结点申请和释放的问题

​ 将所有未被使用过及已被删除的分量用游标链成一个备用的链表，每次插入时，便可以从备用链表上取得第一个结点作为待插入的新节点

/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur; //i就是第一个备用元素的下标
    if (space[0].cur)
        space[0].cur = space[i].cur; //把第一个备用元素的cur（也就是第二个备用元素）赋值给头元素
    return i;
}

​ 这段代码的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标，从前面的例子来看，就是返回7

​ 既然下标为7的分量准备要被使用了，就必须有接替者，所以就把分量7的cur值赋值给头元素，就是把8给space[0].cur，之后就可以继续分配新的空闲分量了，实现类似于malloc()函数的作用（这样就好理解了）

开始插入元素了

​ 其实过程很简单，先把插入那个元素放到第一个备用元素，再把要插入那个位置前面一个元素cur改成插入的那个元素，再把插入那个元素的cur改成插入位置后面一个元素。这样就插入完成了

​ 代码如下：

/*线性表的静态链表存储结构*/
#define MAXSIZE 1000 /*假设链表的最大长度是1000*/
typedef struct
{
    ElemType data;
    int cur; //游标（Cursor），为0时表示无指向
}Component,StaticLinkList[MAXSIZE];
/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur; //i就是第一个备用元素的下标
    if (space[0].cur)
        space[0].cur = space[i].cur; //把第一个备用元素的cur（也就是第二个备用元素）赋值给头元素
    return i;
}
/*在L中第i个元素之前插入新的数据元素e*/
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()，现在我们尝试自己实现它：

/*删除在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)

/*把下标为k的空闲节点回收到备用链表*/
void Free_SSL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur; //把第一个元素的cur（第一个备用元素）赋给要删除的分量的cur
    space[0].cur = k; //把要删除分量的下标赋值给i的第一个元素的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;
}

静态链表的优缺点

优点

• 在插入和删除操作时，只需要移动游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点

缺点

• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了顺序存储结构随机存储的特性

总结

​ 总的来说，静态链表其实是为了给没有指针的高级语言设计的的一种能够实现单链表能力的方法。尽管可能用不上，但是这样的思考方式十分巧妙，应该理解其思想，以备不时之需

循环链表

​ 在单链表中，每个节点只存储了向后的指针，到了尾节点停止向后链接。所以每个节点不能找到它的前驱节点，不能回到之前

​ 把单链表中终端节点的指针域由空指针改为指向头节点，就可以使整个单链表形成一个环。这样头尾相接的单链表称为单循环链表，简称：循环链表（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

双向链表

​ 单链表中只有next指针，所以只能往一个方向查找，所以我们要查找下一节点的时间复杂度为O(1)，可查找上一节点的时间复杂度最坏情况下有可能是O(n)，因为每次都要从头开始遍历查找

​ 双向链表(double linked list)就是为了克服单向性这一缺点而产生的，在单链表的每个节点中，我们再设置一个指向其前驱节点的指针域。因此，双向链表中的节点都有两个指针域，一个指向后继，另外一个指向前驱

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

双向链表也可以是循环链表

​ 双向链表中，对于某节点p，它后继的前驱是它自己，它前驱的后继也是它自己

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

双向链表和单链表的区别

​ 双向链表是单链表中扩展出来的结构，很多操作和单链表相同。比如求长度的ListLength，查找元素的GetElem，获得元素位置的LocateElem（当然，这些操作都只需要设计一个方向的指针）

双向链表插入和删除

​ 双向链表插入和删除时，需要更改两个指针变量

插入示例

​ 我们现在要把一个节点s插入到p和p->next之间

s -> prior = p; //把s的前驱换为p 1
s -> next = p -> next; //把s的后继换为p -> next 2
p -> next -> prior = s; //把p -> next的前驱换为s 3
p -> next = s; //把p的后继换为s 4

删除示例

​ 删除p节点

p -> prior -> next = p -> next; //p -> prior的后继换为p -> next 1
p -> next -> prior = p -> p -> prior; //p -> next的前驱换位p -> prior 2
free(p); //释放节点p

需要注意的

​ 插入和删除的时候顺序千万不要弄错！！

总结回顾

​ 本章我们主要学习了线性表

• 线性表的定义：是零个或多个具有相同类型的数据元素的有限序列

• 线性表的抽象数据类型：

• 线性表的基本操作：

• 线性表的两大结构：

  ​ 顺序存储结构（地址连续的存储单元，一般我们用数组来实现）

  ​ 链式存储结构

• 引入链式存储结构的原因：顺序存储结构的插入和删除操作不方便

• 链式存储结构的优点：不受固定的存储空间限制，可以比较快捷的插入和删除操作

• 链式存储结构又分为：

  • 单链表
  • 循环链表
  • 双向链表
  • 静态链表（不使用指针，了解这个思想）

  

//第三章完，最后更新时间：2021年4月22日 21:48