1.基本概念

1.1 定义

零个或者多个元素的有限排列

PS：元素之间有序，有限

2. 线性表的抽象数据结构

  1. InitList(*L); // 初始化，建立一个空的线性表
  2. ListEmpty(L); // 若线性表为空，返回 true，否则返回 false
  3. ClearList(*L); // 清空线性表
  4. GetElem(L,i,*e); // 将线性表中的第 i 个位置的元素返回给 e
  5. LocateElem(L,e); // 在线性表中查找与 e 值相等的元素，并返回序号
  6. ListInsert(*L,i,e); // 在线性表中的第 i 个位置插入新元素 e
  7. ListDelete(*L,i,*e); // 删除线性表中第 i 个位置的元素，并用 e 返回这个值
  8. ListLength(L); // 返回线性表的元素个数

note：

  1. 线性表是逻辑结构，而顺序表和链表是逻辑结构
  2. 插入默认是前插
  3. 有 * 表示，该对象发生了减少，增加，复制之类结构上的变化
  4. 在 C 语言中 . 用于左操作数为结构体，而 -> 用于左操作数为指向结构体的指针

3. 线性表的顺序存储结构

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

image.png

3.1 顺序存储方式

  1. 通过数组实现
  2. 顺序结构的三个属性
    1. 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置
    2. 最大存储容量：数据长度 MaxSize
    3. 线性表当前的长度：length

PS：线性表长度是指当前数组中元素的个数，随着元素的插入和删除发生变化（动态的），而数组的长度是一开始分配的数组最大长度，这里不考虑动态开辟数组空间的情况（静态的）
**

3.2 地址计算方法

第二章 线性表 - 图2
其中 c 表示占用了 c 个存储单元

3.3 顺序表的优缺点

优点 缺点
快速存取任意位置的元素 插入和删除需要移动大量元素
容易造成空间碎片

3.4 顺序表的实现

链接
顺序表的静态实现
image.png
上面是静态的。

这是动态的：
image.png

note

  1. 顺序表插入和删除的时间复杂度都是 O(n)
  2. 单链表的逆置(转）
  3. 指针与地址image.png

4. 线性表的链式存储结构

4.1 定义

不考虑物理上存储结构的相邻关系，只需要让逻辑上相邻。

4.2 存储结构

image.png
D3UY4O1$O%K]]O9QZF)@N14.png
一个结点由数据域和指针域组成，数据域存放信息，指针域存放下一个结点的信息，尾结点的指针域尾 NULL。


链表第一个结点的存储位置叫做头指针，整个链表的存取也是从头指针开始的
为了方便起见，我们设置头结点，头指针指向头结点，头结点指向链表中第一个结点。
image.png
note

  1. 在没有头结点的时候，**head（头指针）= NULL 时为空（因为此时 head 指向第一个结点，即代表第一个结点；当有头结点的时候，head->next = NULL 表示空，此时 head 指向头结点，所以 head->next 才是指向第一个结点**。

4.3 头结点与头指针的异同

头指针 头结点
头指针指向链表的第一个结点，若链表由头结点，则是指向头结点的指针 头结点是为了操作方便设置的，不是必须的元素
头指针是链表的不要元素

4.4 单链表的基本操作

1. 单链表的数据结构

  1. // typedef struct Node{...}Node;
  2. // 在学习 C 语言的时候，我们直到 struct 后面的 Node 是可以
  3. // 省略的，但是这里必须加上，因为在结构体内部定义了后驱尾
  4. // 该结构，这个时候，在运行代码的时候，最后的末尾的 Node 没有
  5. // 运行到，会报错 
  6. typedef int ElemType; 
  7. typedef struct Node
  8. {
  9.     ElemType data;
  10.     struct Node *next;
  11. }Node;
  13. // 定义一个结构体指针
  14. // 对于初学者来说，结构体指针的目的就是为了构造链表
  15. typedef struct Node *LinkList;

image.png

image.png

4.4.2. 单链表的创建

4.4.2.1. 尾插法建立单链表
  1. 创建单链表的过程就是一个动态生成链表的过程
  2. 算法的思路
    1. 初始化一个空链表 L：*L = (LinkList)malloc(sizeof(Node));
    2. 让 L 指向 NULL：(*L)->next = NULL;
    3. 创建新结点 P：LinkList p;
    4. 循环
      1. 没创建一个新结点 P，就插入到头结点和就的 P 结点之间： p->next = (*L)->next; (*L)->next =p;
  1. // 以下两种插法都是带头结点的
  3. // 头插法
  4. // 头插法是每次把新加入的结点都相比于已经存在的结点
  5. // 往前插入，但是头结点本身始终位于链表最前面的结点
  6. // 这个方法相当于逆序插入
  8. void CreateListHead(LinkList *L,int n)
  9. {
  10.     // 创建一个新结点 p 
  11.     LinkList p;
  12.     int i;
  13.     // 初始化一个空链表 
  14.     // 创建一个新的结点，该节点是头结点
  15.     *L = (LinkList)malloc(sizeof(Node));
  16.     // L 的头结点指针指向 NULL，这是一个带头结点的单链表 
  17.     (*L)->next = NULL;
  18.     for(i=0;i<n;i++)
  19.     {
  20.         p = (LinkList)malloc(sizeof(Node));
  21.         p->data = i;
  22.         // 注意第一次时，新创建的结点指向头结点的下一个结点，此时是指向
  23.         // 的 NULL
  24.         p->next = (*L)->next;
  25.         (*L)->next =p;
  26.     }
  27. } 
  29. // 尾插法
  30. void CreateListTail(LinkList *L,int n)
  31. {
  32.     LinkList p,r;
  33.     int i;
  34.     *L = (LinkList)malloc(sizeof(Node));
  35.     // r 指向当前链表，注意这里的 L 和头插法中的 L
  36.     // 有区别，这里的 L 是指的整个链表 
  37.     // r 是 rear（尾部）的缩写，此时 r 当作尾结点（因为
  38.     // 当前还没有新插入的结点 p ，所以认为 r 是头结点也对） 
  39.     r = *L;
  40.     for(i=0;i<n;i++)
  41.     {
  42.         p=(LinkList)malloc(sizeof(Node));
  43.         p->data = i;
  44.         // 此时 r 为前一个结点，新创建的结点 p
  45.         // 被放在 r 后面（尾插） 
  46.         r->next = p;
  47.         // 然后让 r 变成 p，这样 r 又可以作为尾结点 
  48.         r = p;
  49.     } 
  50.     // 循环结束，让尾结点指空
  51.     r-next = NULL; 
  52. }

这里另起一个关于头插入法的代码，目前这个是我完全掌握的。
image.png

头插法（图片来源）
image.png

r->next = p; 的含义
image.png

r = p; 的含义
image.png

单链表的插入
image.png

3. 单链表的读取

  1. // 单链表的读取
  2. // 依然是带有头结点的形式
  3. Status GetElem(LinkList L,ElemType *e)
  4. {
  5.     int j=1;    // 为计数器 
  6.     LinkList p; // 声明一个额外的指针
  7.     p = L->next; // 将 p 指向链表的第一个结点
  8.     while(p && j<i) // 当 p 不为空，且当前查找到的下标小于要被查找的下标循环继续 
  9.     {
  10.         p = p->next;
  11.         ++j; 
  12.     } 
  14.     if(!p||j>i)
  15.         return 0;
  16.     else
  17.     {
  18.         *e = p->data;
  19.         printf("要查找的数值是：%d\n",e);
  20.     }
  22.     return 1;
  23. }

4. 单链表的插入与删除

插入
image.png

  1. // 插入的核心代码
  2. s->next = p->next;
  3. p->next = s;

对于头尾特殊位置的插入
image.png

前插，且没有传入链表
image.png

删除
image.png

  1. p->next = q->next

5. 单链表的整表删除

  1. // 单链表的整表删除
  2. Status ClearList(LinkList *L)
  3. {
  4.     LinkList p,q;
  5.     while(p)
  6.     {
  7.         // 声明两个结点 p 和 q，分别赋值 p 为第一个结点
  8.         // q 为第二个结点，当释放 p 所在的结点后，p 又指向
  9.         // q。下一次循环时，q 有移动到当前 p 的下一个结点
  10.         q = p->next;
  11.         free(p);
  12.         p=q;
  13.     }
  15.     // 最终将单链表完全释放掉
  16.     (*L)->next = NULL;
  17.     return 1;
  18. }

6. 单链表的基本操作合集

链接

4.5 单链表的优势

单链表在插入和删除时的时间复杂度都是 O(n)，所以对于插入和删除数据越频繁的操作，单链表的优势就越大。

4.6 单链表与顺序表的对比

存储分配方式 时间性能
顺序表 一段连续的内存地址 查找：O(1)
插入和删除：O(n)
单链表 逻辑上连续，物理上随机 查找：O（n）
插入和删除：O(1)

5. 静态链表

所谓静态链表，就是用数组来代替指针描述链表的一种方式。
数组元素由两个数据域 data 与 cur 组成。其中 data 存放数据元素，cur（游标）起到指针的作用。
之所以这么做，是因为在早期的编程语言中还没有引入指针的概念。

5.1 静态链表的抽象结构

  1. #define MAXSIZE 1000
  2. typedef int ElemType;
  3. typedef struct
  4. {
  5.     ElemType data;
  6.     int cur;
  8. }Component,StaticLinkList[MAXSIZE];

在已经划分的数组空间中，未被使用的数组元素称为备用链表。
其中，数组的第一个（下标为 0 ）和最后一个元素另作他用，不存储数据。
下标为 0 的元素 cur 存放备用链表（未被使用的数组元素）的第一个结点的下标，最后一个元素 cur 存放已使用的第一个元素的下标（相当于头结点）。

PS：

  1. 初始化静态链表的时候，除了首尾两个元素，其他都是空的，即都是备用链表。
  2. 静态链表初始化时没有任何元素，则其 cur 为 0。
  3. 指针域指出下一个结点的位置

image.png

5.2 静态链表的初始化

  1. // 初始化
  2. Status InitList(StaticLinkList space)
  3. {
  4.     int i;
  5.     for(i=0;i<MAXSIZE-1;i++)
  6.         space[i].cur = i+1;
  7.     space[MAXSIZE-1].cur=0; // 当前初始化链表为空 
  8.     return 1;
  9. }

5.3 静态链表的插入

在单链表中我们使用 malloc 和 free 函数作为实现插入和删除的必备步骤。但是静态链表不具备这样的函数，所以需要我们手动实现。

思想
未使用（包括之前删除的）的每个数组空间构成备用链表（就是之前的讲的那个），当插入时从备用链表上取一个结点作为被插入的新结点。

  1. // 自定义具有 malloc 功能的函数
  2. int mallocSll(StaticLinkList space)
  3. {
  4.     // 当前第一个备用链表的下标
  5.     // 也就是上图中下标为 1 的元素空间
  6.     // i 的值时这个下标为 1 的元素空间的下一个元素空间
  7.     // 即下标为 2
  8.     int i=space[0].cur;
  10.     if(space[0].cur)
  11.         space[0].cur = space[i].cur; // 将第二个备用链表升级成第一个
  13.     // 返回空闲下标
  14.     return i;     
  15. }

插入

  1. // 插入操作
  2. Status ListInsert(StaticLinkList L,int i,ElemType e)
  3. {
  4.     int j,k,l;
  5.     k = MAXSIZE-1; // k 是最后一个元素的下标
  6.     if(i<1 || i>ListLength(L)+1)
  7.         return 0;
  8.     j =  mallocSll(L); // 获得空闲下标 
  9.     if(j)
  10.     {
  11.         L[j].data = e; // 将数据赋给 data 
  12.         for(l=1;l<=i-1;l++)
  13.             k=L[k].cur;
  14.         // 最后一个元素的 cur 是用来存放已使用的
  15.         // 第一个元素的下标    
  16.         L[j].cur=L[k].cur;  
  17.         // 前一个元素的下标指向新元素的下标 
  18.         L[k].cur=j;
  19.         return 1;
  20.     }
  21.     return 0;
  22. }

5.4 静态链表的删除

自定义的 free 函数

  1. // 自定义 free 函数
  2. void FreeSll(StaticLinkList space,int k)
  3. {
  4.     // 把原来的一个备用链表的下标给现在被删除的空位的下标
  5.     // 即后面如果还有数值插入，就优先插入现在被删除的位置 
  6.     space[k].cur = space[0].cur;
  7.     // 更新第一个备用链表下标为 k 
  8.     space[0].cur = k;
  9. }

删除

  1. // 删除操作
  2. Status ListDelete(StaticLinkList L,int i)
  3. {
  4.     int j,k;
  5.     if(i<1 || i>ListLength(L))
  6.         return 0;
  7.     k = MAXSIZE -1 ;
  8.     for(j=1;j<=i-1;j++)
  9.         k=L[k].cur;
  10.     j=L[k].cur;
  11.     L[k].cur=L[j].cur;
  12.     FreeSll(L,j);
  13.     return 1;
  14. }

5.5 静态链表的操作合集

链接

6. 循环链表

  1. 将终端结点的指针由空指针（即指向 NULL）改为指向头结点，使链表形成了一个环，这就是循环链表。
  2. 循环链表解决了如何从任意一个结点出发就可以访问全部结点的问题。
  3. 和单链表不同的是，循环链表使用尾指针。其开始结点可以这样表示：rear->next->next
  4. 带头结点的循环单链表的尾指针指向头结点

image.png

7. 双向链表

7.1 双向链表的抽象结构

  1. typedef struct DulNode
  2. {
  3.     ElemType data;
  4.     struct DuLNode *prior;
  5.     struct DuLNode *next;
  6. } DulNode,*DuLinkList;

循环双向链表
image.png

循环双向链表的前驱的后继和后继的前驱都是自己

  1. p->next->prior = p = p->prior->next

单向循环链表的判空是 p==L

7.2 插入和删除操作

插入
image.png

s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

删除
image.png

p->prior->next=p->next;
p->next->prior=p->prior;
free(p);

7 总结与回顾

  1. image.png
  2. 时间复杂度中的第二章 线性表 - 图26怎么理解