关键词：
2022计算机考研408—数据结构—线性表、栈、队列、数组
手把手教学考研大纲范围内的线性表、栈、队列、数组
22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，
如有什么建议或者不足欢迎大佬评论区或者私信指出
Talk is cheap. Show me the code.
理论到处都有，代码加例题自己练习才能真的学会
顺序表
链表
双向循环链表 后面附：顺序表链表区别
栈
栈实现括号问题
循环链栈表
递归斐波那契
递归汉诺塔
循环队列
链队（链式队列）
顺序表
官方含义：一段地址连续的存储单元依次存储线性表的数据元素。
其实就相当于数组，`把顺序表当数组看`最简单了
// 顺序表
#include <iostream>
#define MAXSIZE 1001
using namespace std;
typedef struct //定义学生结构体，包含学号和姓名
char ID[20];
char name[50];
Student;
typedef struct //定义线性表，和长度属性
Student *elem;
int length;
StuList;
bool ListInit(StuList &L) //初始化线性表
L.elem = new Student[MAXSIZE]; //给数组分配空间长度
if (!L.elem) //如果没分配成功，就返回失败
return false;
L.length = 0; //初始化线性表后长度为0
return true;
//插入的时候需要注意把这一位后面的，每个都后移一位，然后把数据放到空出来的那位
bool ListInsert(StuList &L, int i, Student stu) //把Student类型插入到序列为i的位置
if (i < 0 || i > L.length + 1) //判断插入位置是否正确
return false;
if (L.length == MAXSIZE) //如果插入位置到达最大值，无法插入
return false;
for (int j = L.length - 1; j >= i - 1; j--) //把i以后元素都向后移动一位，
L.elem[j + 1] = L.elem[j];
L.elem[i - 1] = stu; //把将要插入的放到指定位置
++L.length; //线性表长度+1
return true;
//也是和插入的时候一样，把i后面的都向前移动一位
bool ListDelete(StuList &L, int i) //删除序列为i的元素
if (i < 1 || i > L.length)
return false;
for (int j = i; j < L.length; j++) //把序列i以后的元素全部前移一位，盖住了序列为i的那位
L.elem[j - 1] = L.elem[j];
--L.length; //线性表长度-1
return true;
bool ListGetStu(StuList &L, int i, Student &s) //返回序列为i的元素
if (i < 1 || i > L.length)
return false;
s = L.elem[i - 1];
return true;
int ListGetIndex(StuList &L, Student s) //找到与s相等的元素的下标
for (int i = 0; i < L.length; i++)
if (L.elem[i].ID == s.ID && L.elem[i].name == s.name)
return i + 1;
return 0;
void ListMerge(StuList &A, StuList B) //把B表中A表没有的元素插入到A表后面
int a = A.length, b = B.length;
for (int i = 0; i < B.length; i++)
if (!ListGetIndex(A, B.elem[i])) //A表中是否存在B.elem[i]
ListInsert(A, ++a,B.elem[i]);
A.length = a; //a代表新线性表的大小，初始为A线性表大小，后面每次插入到A线性表一个值，a++
void ListaddAll (StuList &A, StuList B) //把B线性表插入到A线性表后面
int a = A.length, b = B.length;
for (int i = 0; i < B.length; i++)
ListInsert(A, ++a,B.elem[i]);
A.length = a;
int main()
StuList demo;
ListInit(demo);
Student student = "123", "张三";
Student student2 = "456", "李三";
ListInsert(demo, 1, student);
ListInsert(demo, 2, student2);
ListGetStu(demo, 1, student2);
cout << student2.ID << student2.name << "\\n";
cout << ListGetIndex(demo, student) << "\\n";
ListMerge(demo, demo);
ListaddAll(demo, demo);
cout << demo.length;
return 0;
链表
链表和顺序表其实是差不多的
顺序表在访问下一个的时候是用下标访问
链表访问下一个只能通过结构体中的指针
插入，删除的时候不需要改变其他元素，只需要修改指定元素前后元素的指针即可
//此链表的index为序列号从1开始 ！！！！不是下标
//此链表多处用到new ，建议大家删一个new调试一下，就能了解到new和不用new的区别了
#include "iostream"
#include "vector"
using namespace std;
typedef struct LNode //LNode类型 包含一个int值和一个指针指向下一个地址
int data;
struct LNode *next;
LNode, *LinkList;
bool ListInit(LinkList &L, int val) //初始化链表，要给一个初始值当作链表头节点
L = new LNode;
L->next = NULL;
L->data = val;
return true;
bool ListInsertE(LinkList &L, int val) //添加一个元素到链表尾端
LNode *headL = new LNode; //保存一下链表当前的位置
headL = L;
while (L->next) //循环到L最后面，然后把当前值给L的下一个
L = L->next;
LNode *temp = new LNode; //new一个结点，如果不new可能会使用上一个temp结点
temp->data = val;
temp->next = NULL;
L->next = temp;
L = headL; //链表的头位置给L
bool ListInsert(LinkList &L, int index, int val) //插入到链表的序列index（注意不是下标）位置
LNode *headL = new LNode; //保存头位置的上一个（headL的下一个是头位置）
headL->next = L; //这里不保存头位置， 防止添加第一个位置时，链表会添加到第二个位置
int j = 0;
while (headL && j < (index - 1)) //找到第index个位置
j++;
headL = headL->next;
if (!headL || index < 1)
return false;
LNode *temp = new LNode; //new一个结点，（不new可能会用到上一个结点）
temp->data = val;
temp->next = headL->next; //把headL的下一个结点给temp的下一个结点
headL->next = temp; //把temp给headL的下一个结点 现在temp的下一个就是原headL的下一个结点，相当于把temp插入到了里面
L = headL->next;
return true;
bool ListDelete(LinkList &L, int index) //删除指定序列index的值
LNode *headL = new LNode;
LNode *tempL = new LNode;
tempL->next = L; //tempL的下一个是头节点（防止删除第一个结点出现问题）
headL = tempL; //保存头结点的上一个，就是tempL
int j = 0;
while (tempL && j < (index - 1)) //找到序列index的结点
tempL = tempL->next;
j++;
if (!tempL) //如果tempL为NULL，直接退出，没有要删除的结点
return false;
tempL->next = tempL->next->next; //tempL的下一个的下一个给下一个 相当于下一个会被直接盖住（删除了下一个 ）
L = headL->next; //把头结点给L
bool ListGetElem(LinkList L, int index, int &val) //找到知道序列index的值，传送给val
int j = 0;
while (L && j < (index - 1)) //找到序列为index的值
L = L->next;
j++;
if (!L) //如果L为空，直接退出，没有此节点
return false;
val = L->data;
return true;
int ListGetIndex(LinkList L, int val) //通过值找到指定序列下标
int index = 1;
while (L->data != val)
L = L->next;
index++;
if (!L)
return 0;
return index;
void ListCreateH(LinkList &L, vector<int> num) //前插法创建节点（num数组的值创建链表）
L = new LNode;
L->next = NULL;
for (int i = 0; i < num.size(); i++)
LNode *p = new LNode;
p->data = num[i];
p->next = L->next; //每次把L的下一个给p的下一个
L->next = p; //然后把p给L的下一个 p的下一个是原来L的下一个
L = L->next; //L的下一个才是num数组创建的第一个值
void ListCreateE(LinkList &L, vector<int> num) //前插法创建节点（num数组的值创建链表）
L = new LNode;
LNode *headL = new LNode;
headL = L;
L->next = NULL;
for (int i = 0; i < num.size(); i++)
LNode *p = new LNode;
p->data = num[i];
p->next = NULL;
L->next = p; //当前指针p给L的下一个
L = p; //把p给L p的上一个就是原L
L = headL->next; //头结点的下一个才是num创建的第一个结点
void ListPrint(LinkList L) //输出链表各个的值
while (L)
cout << L->data << " ";
L = L->next;
cout << "\\n";
int main()
vector<int> num = 1,2,3,4,5;
LinkList temp;
// ListCreateE(temp, num);
// ListPrint(temp);
// ListCreateH(temp, num);
// ListPrint(temp);
ListInit(temp, 10); //创建List链表
ListInsertE(temp, 10); //尾端插入值
ListInsertE(temp, 10);
ListPrint(temp);
ListInsert(temp, 1, 20); //插入一个值 到序列index位置
ListPrint(temp);
ListDelete(temp, 3); //删除链表中序列index的值
ListPrint(temp);
int val;
ListGetElem(temp, 3, val); //通过序列index找到值，传给val
cout << val << "\\n";
ListPrint(temp);
cout << ListGetIndex(temp, 2) << "\\n"; //通过值找到序列index
双向循环链表
双向循环链表和单链表也是大致相同的
只是在修改结点的关系的时候需要修改每个结点的前后节点
//循环链表
#include "iostream"
#include "vector"
using namespace std;
typedef struct DuLNode //结点，每个结点有一个值，
int data; //每个结点包括两个指针，一个指向前一个结点，一个指向后一个结点
struct DuLNode *prior; //指定当前结点的前一个结点
struct DuLNode *next; //指定当前结点的后一个结点
DuLNode, *DuLinkList;
bool ListInitDul(DuLinkList &L, vector<int> data) //初始化双指针循环链表
DuLNode *headL = new DuLNode; //记录一下头结点，初始化结束后，把头结点重新赋值给L
DuLNode *node = new DuLNode; //初始化的时候，把第一个值给node，依次向下连接
node->data = data[0];
L = node;
headL = L;
for (int i = 1; i < data.size(); i++)
DuLNode *temp = new DuLNode;
temp->data = data[i]; //每次创建一个新的结点，当作node的下一个，绑定与node的关系
node->next = temp; //绑定temp变成node的下一个
temp->prior = node; //绑定node变成temp的上一个
node = temp; //绑定后，把当前点给node， 方便下次循环绑定下一个值
node->next = L; //node此时为最后一个值，，node的下一个绑定头结点（循环链表）
L->prior = node; //L的前一个为node，首结点的上一个就是当前链表的最后一个
L = headL; //把初始头结点给L
return true;
bool ListGetDulElem(DuLinkList L, int index, DuLNode &node) //得到链表序列为index的值，传给node
int j = 1;
while (L && j < index) //找到序列为index的结点，
L = L->next; //前面有几个，就循环几次，每次都向下走一位
j++;
if (!L) //如果L为空，直接跳过
return false;
node = *L; //如果不为空，把当前结点传给node
return true;
bool ListInsertDul(DuLinkList &L, int index, int data) //在序列index位置插入结点
DuLNode *node = new DuLNode;
if (!ListGetDulElem(L, index, *node)) //查找一下指定index位置，如果没有当前位置，返回false
return false;
//假设在a b的位置插入c（在a b中间插入c，b为node，c为newNode）
//设置c的前一个为a 设置a的下一个为c 设置c的下一个为b 设置b的上一个为c
DuLNode *newNode = new DuLNode;
newNode->data = data;
newNode->prior = node->prior; //把node的前一个给newNode的前一个，
node->prior->next = newNode; //把newNode给node的前一个的后一个
newNode->next = node; //把node给newNode的下一个
node->prior = newNode; //把newNode给node的前一个
if (index == 1) //如果是插入第一个的话，返回node的上一个
L = node->prior; //node此时为第二个，新插入的为第一个值，把第一个值给L
return true;
bool ListDeleteDul(DuLinkList &L, int index) //删除序列为index的值
DuLNode *headL = new DuLNode;
headL = L;
DuLNode *node = new DuLNode;
if (!ListGetDulElem(L, index, *node)) //找到序列index的结点，传给node
return false;
//删除node（node为序列index的结点）
//假设a b c删除 b （b为node）
//设置a的下一个为c 设置c的上一个为a
n22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情
22计算机408考研—数据结构—线性表栈队列数组(代码片段)
2022计算机考研408—数据结构—线性表、栈、队列、数组手把手教学考研大纲范围内的线性表、栈、队列、数组22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议... 查看详情
22计算机408考研—数据结构—树定义，遍历，huffman，并查集
...围内树定义，遍历，Huffman，并查集22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议或者不足欢迎大佬评论区或者私信指出初心是用最简单的语言描... 查看详情
(王道408考研数据结构)第三章栈和队列-第四节：特殊矩阵压缩方式
文章目录一：数组（1）数组的定义（2）二维数组二：矩阵的压缩存储（1）对称矩阵（2）三角矩阵（3）三对角矩阵（4）稀疏矩阵一：数组（1）数组的定义数组：是由nnn( 查看详情
[datastructure]线性数据结构之稀疏数组链表栈和队列java代码实现
线性数据结构线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。线性数据结构具有以下特征：1．... 查看详情
[datastructure]线性数据结构之稀疏数组链表栈和队列java代码实现
线性数据结构线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继。线性数据结构具有以下特征：1．... 查看详情
22计算机408考研—数据结构—树定义，遍历，huffman，并查集(代码片段)
...围内树定义，遍历，Huffman，并查集22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议或者不足欢迎大佬评论区或者私信指出初心是用最简单的语言描... 查看详情
考研目录链接
文章目录301高等数学线性代数概率论408数据结构计算机组成原理计算机网络操作系统缩写301高等数学线性代数概率论408数据结构计算机组成原理计算机网络操作系统缩写缩写全称中文名PCBProcessControlBlock进程控制块trap陷入BootBoot... 查看详情
22计算机408考研—数据结构—图(代码片段)
手把手教学考研大纲范围内图的存储和遍历22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议或者不足欢迎大佬评论区或者私信指出初心是用最简单的语言描述数... 查看详情
22计算机408考研—数据结构—树定义，遍历，huffman，并查集（持续更新）(代码片段)
...围内树定义，遍历，Huffman，并查集22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议或者不足欢迎大佬评论区或者私信指出初心是用最简单的语言描... 查看详情
考研目录链接
文章目录301高等数学线性代数概率论408数据结构计算机组成原理计算机网络操作系统缩写301高等数学线性代数概率论408数据结构计算机组成原理计算机网络操作系统缩写缩写全称中文名PCBProcessControlBlock进程控制块trap陷入BootBoot... 查看详情
考研数据结构模板：顺序表链表栈队列(代码片段)
考研数据结构模板：顺序表、链表、栈、队列考研数据结构模板：顺序表、链表、栈、队列前言代码风格偏向于考研风格而非算法竞赛风格。代码实现参考《2024数据结构王道复习指导》。注释详细、保证看懂。下面是已实现的... 查看详情
(王道408考研数据结构)第二章线性表-第二节2：顺序表的操作(代码片段)
文章目录一：顺序表初始化和销毁二：顺序表的打印三：顺序表插入四：顺序表的删除五：顺序表查找（1）使用顺序查找法查找（2）使用二分查找法完成顺序表使用动态数组方式实现，结点定义如下typedefintDataType;typedefstructSeqli... 查看详情
22计算机408考研—数据结构—图(代码片段)
...围内树定义，遍历，Huffman，并查集22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议或者不足欢迎大佬评论区或者私信指出初心是用最简单的语言描... 查看详情
线性表栈队列和优先队列(代码片段)
为一个特定的任务选择最好的数据结构和算法是开发高性能软件的一个关键。 数据结构是以某种形式将数据组织在一起的集合（collection）。数据结构不仅存储数据，还支持访问和处理数据的操作。 在面向对象思想... 查看详情
数据结构之线性表栈队列(代码片段)
温故而知新~~~~一、线性表顺序表实现（C++）1template<typenameE>2classAList34private:5intmaxSize;6intlistSize;7intcurr;8E*listArray;9public:10AList(intsize=defaultSize)1112maxSize=size;13listSize=curr=0;14listArr 查看详情
(王道408考研数据结构)第二章线性表-第二节1：顺序表的定义(代码片段)
文章目录一：顺序表实现（1）静态分配（2）动态分配二：顺序表特点顺序表：也叫做线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素一：顺序表实现（1）静态分配静态分配是指开始时就确... 查看详情
2022计算机考研408—数据结构—排序(代码片段)
手把手教学考研大纲范围内的排序22考研大纲数据结构要求的是C/C++，笔者以前使用的都是Java，对于C++还很欠缺，如有什么建议或者不足欢迎大佬评论区或者私信指出排序定义冒泡排序直接插入排序二分插... 查看详情