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

1. 🥬 第一章 绪论(无)
2. 🥕 第二章 线性表 ⇦当前位置🪂
3. 🥪 第三章 栈和队列
4. 🍊 第四章 串-KMP(看毛片算法)
5. 🍒 第五章 树和二叉树
6. 🍀 第六章 图
7. 🍚 第七章 查找(B树、散列表)
8. 🧄 第八章 排序 (内部排序：八大排序动图演示与实现 + 外部排序)
9. 🍔 数据结构与算法 复试精简笔记 (未完成)
10. 🎨 408 全套初复试笔记汇总 传送门 🏃‍🏃‍🏃‍
     

如果本篇文章对大家起到帮助的话，跪求各位帅哥美女们，求赞👍 、求收藏 👏、求关注！👀
你必考上研究生！我说的，耶稣来了也拦不住！😀😀😀

 

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

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

 

---

第2章 线性表

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

---

4）小结

---

2.基本操作实现

1）插入

---

2）删除

---

3）查找

• ① 按位查找

• ② 按值查找

---

4）小结

---

2.3 线性表的链式表示和实现

1.链式表示

1）存储结构

---

2）代码定义

---

3）不带头结点

---

4）带头结点

---

5）小结

---

2.基本操作

• 对于不带头结点的情况，虽然考查较少，当也有可能考
• 除了插入操作有带头、不带头情况，其它操作默认带头结点

1）插入

• ① 带头结点

• ② 不带头结点

• ③ 指定后插

• ④ 指定前插

• 该方法虽然间接实现了指定结点的前插操作，但是无法获得前驱结点的指针

---

2）删除

• ① 带头结点

• ② 指定删除
• 无法删除最后一个结点

---

3）查找

• ① 按位查找

• ② 优化插入操作代码

• ③ 按值查找

• ④ 求表长度

• ⑤ 小结

---

4）单链表的建立

• ① 尾插法
• 下面时间复杂度是O(n)，但是如果题目说明每次都重头开始遍历进行尾插，就是O(n^2)

• ② 头插法

---

3.双链表

1）初始化

• 带头结点情况

---

2）插入

---

3）删除

---

4）遍历

---

5）小结

---

4.循环链表

1）循环单链表

---

2）循环双链表

• ① 初始化

• ② 插入

• ③ 删除

---

3）小结

---

5.静态链表

1）概念

---

2）定义

---

3）实现

---

4）小结

---

2.4 顺序表和链表的比较

1.逻辑结构

---

2.存储结构

---

3.基本操作

---

4.小结

---

2.5 线性表的应用

必定不考，放在这里主要是为了知识结构的完整性

---

加油考验人！！！