本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对数据结构知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！
关于对 “线性表” 章节知识点总结的十分全面，涵括了《王道数据结构》课程里的全部要点（本人来来回回过了三遍视频），其中还陆陆续续补充了许多内容，所以读者可以相信本篇博客对于考研数据结构“线性表”章节知识点的正确性与全面性；但如果还有自主命题的学校，还需额外读者自行再观看对应学校的自主命题材料。

精准控时：
如果不实际操作代码，只是粗略过一下知识点，需花费 40 分钟左右过一遍
这个40分钟是我在后期冲刺复习多次尝试的时间，可以让我很好的在后期时间紧张的阶段下，合理分配复习时间；
但是刚开始看这份博客的读者也许会因为知识点陌生、笔记结构不太了解，花费许多时间，这都是正常的。
重点！！！学习一定要多总结多复习！重复、重复、再重复！！！

食用说明书：
第一遍学习王道课程时，我的笔记只有标题和截图，后来复习发现看只看图片，并不能很快的了解截图中要重点表达的知识点。
所以再第二遍复习中，我给每一张截图中标记了重点，以及每张图片上方总结了该图片对应的知识点以及自己的思考。
最后第三遍，查漏补缺。
所以，我把目录放在博客的前面，就是希望读者可以结合目录结构去更好的学习知识点，之后冲刺复习阶段脑海里可以浮现出该知识结构，做到对每一个知识点熟稔于心！
请读者放心！目录展示的知识点结构是十分合理的，可以放心使用该结构去记忆学习！
注意(⊙o⊙)！，每张图片上面的文字，都是该图对应的知识点总结，方便读者更快理解图片内容。

第2章线性表

文章目录

第2章线性表
- 2.1 线性表的定义和基本操作
- - 1.定义
  - 2.基本操作
  - 3.小结
- 2.2 线性表的顺序表示和实现
- - 1.顺序表示
  - - 1）存储结构
    - 2）静态分配
    - 3）动态分配
    - 4）小结
  - 2.基本操作实现
  - - 1）插入
    - 2）删除
    - 3）查找
    - 4）小结
- 2.3 线性表的链式表示和实现
- - 1.链式表示
  - - 1）存储结构
    - 2）代码定义
    - 3）不带头结点
    - 4）带头结点
    - 5）小结
  - 2.基本操作
  - - 1）插入
    - 2）删除
    - 3）查找
    - 4）单链表的建立
  - 3.双链表
  - - 1）初始化
    - 2）插入
    - 3）删除
    - 4）遍历
    - 5）小结
  - 4.循环链表
  - - 1）循环单链表
    - 2）循环双链表
    - 3）小结
  - 5.静态链表
  - - 1）概念
    - 2）定义
    - 3）实现
    - 4）小结
- 2.4 顺序表和链表的比较
- - 1.逻辑结构
  - 2.存储结构
  - 3.基本操作
  - 4.小结
- 2.5 线性表的应用

2.1 线性表的定义和基本操作

在这里插入图片描述

1.定义

线性表的定义(2-1)：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MUwhL5wg- 在这里插入图片描述

注意，线性表是一种逻辑结构，它只有(2-1)这句定义，表示元素之间一对一的相邻关系
之后我们学习的顺序表和链表才指存储结构，所以线性表只考虑逻辑方面的关系

2.基本操作

在这里插入图片描述

3.小结

在这里插入图片描述

2.2 线性表的顺序表示和实现

在这里插入图片描述

1.顺序表示

1）存储结构

顺序表就是用一组地址连续的存储单元依次存储线性表中的数据元素
① 线性表 + 顺序存储 = 顺序表
- 数据元素现在不仅是逻辑上按序且 前后相邻，而且物理上也是按序且前后相邻，顺序表用一块连续的存储空间顺序****实现线性表
② 线性表的顺序存储 + 元素类型相同 = 随机存取

在这里插入图片描述

③ 存储空间分配方式
顺序表在高级语言中是使用数组来实现的，根据对顺序表存储空间分配方式的不同，分成静态分配和动态分配
静态分配时，数组的大小在一开始是固定的，空间满了数据就会溢出；
动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，不够在扩充。
这里就有一处很重要的地方需要注意，当动态分配的数组空间不够用的时候，想再扩充L个存储空间（数组N个存储空间），这时候程序是在内存开辟一个N+L大小的空间，而不是L大小。因为顺序表就得占用着一块连续的内存空间

2）静态分配

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

#define MAXSIZE 100
typedef int ElemType;

typedef struct
{
    ElemType data[MAXSIZE];
    int length;
} SqList;

void InitList(SqList &list)
{
    for (int i = 0; i < MAXSIZE; i++)
    {
        list.data[i] = 0;
    }
    list.length = 0;
}

int main()
{
    SqList l;
    InitList(l);
    int val, i = 0;
    while (cin >> val)
    {
        l.data[i] = val;
        l.length++;
        i++;
    }
    for (i = 0; i < l.length; i++)
    {
        cout << "data[" << i << "] = " << l.data[i] << endl;
    }
}

3）动态分配

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

#define INITSIZE 10
typedef struct
{
    int val;
} ElemType;

typedef struct
{
    ElemType *data;
    int length;
    int maxSize;
} SqList;

void InitList(SqList &list)
{
    list.data = (ElemType *)malloc(INITSIZE * sizeof(ElemType));
    list.length = 0;
    list.maxSize = INITSIZE;
}

int main()
{
    SqList l;
    InitList(l);
    int elem, i = 0;
    while (cin >> elem)
    {
        l.data[i].val = elem;
        l.length++;
        i++;
    }
    for (i = 0; i < l.length; i++)
    {
        cout << "data[" << i << "] = " << l.data[i].val << endl;
    }
}