线性数据结构（vector、链表、栈、队列）_vector 结构体

一、简介

本文主要介绍算法竞赛中常用的一些线性数据结构，vector、链表、栈、队列。这里的线性数据结构用于算法竞赛，所以会与大学课堂所学的书写方法不同。

二、vector

1、介绍

定义一组长度不定的数组。

2、定义

vector <char> v;
// vector默认长度是0， 类型可以是c++的标准类型，也可以是自己定义的类或结构体
vector <int> v(N); 
// 效果类似int v[N];但是N可以是变量
vector <int> v(N, i); 
// 可变数组最开始有N个元素，每个元素的值是i,i可以省略不写
vector < vector<int> > v; 
// > > 分开写，有的编译器不分开会当成右移符合>>
1
2
3
4
5
6
7
8

3、常见用法

（1）size()

该函数会返回一个size_t类型的值，表示vector内元素的个数（数组的长度）。

int len = v.size();
// v.size()是 size_t 类型，注意这是一个无符号整数类型，在64位系统中为long long unsigned int，非64位系统中为long unsigned int
// 所以当v.size() == 0 的时候，v.size() - 1是一个很大的正数，而不是负一。切记切记。
1
2
3

（2）resize()

// 如果原本内存里不够5个元素，那么调用v[4]就会出现段错误
v.resize(5);
// 给vector重新分配内存，之后v内有5个元素,调用v[4]就不会有问题了
// 如果原本vector里元素个数已经多于5个了，那么调用resize(5)以后，vector会删除之后多于的元素
1
2
3
4

（3）push_back()

vector <int> v1;
vector <node> v2;
node s;
v1.push_back(5);
v2.push_back(s);
// 在vector末尾添加元素，自动增加vector的长度
1
2
3
4
5
6

（4）遍历

// vector 可以像数组一样访问。
vector <int> v;
// 从小到大遍历
for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << endl;
}
// c++11支持的语法，功能和上面一样
for (auto x: v) {
    cout << x << endl;
}
1
2
3
4
5
6
7
8
9
10

三、链表

1、介绍

链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 。

在现实生活中，如果我们想要按照之前排好的顺序进行排队的话。队伍中的每一个人并不需要知道整个队列的顺序，我们只需要知道排在我们后面（或者前面）的人是谁，那么，我们就可以通过排在队伍最前端的人找到队列里面所有的人。

类似于按顺序排队，链表中的每个节点在存储本身的相关信息的时候，还要再存储一个前驱或者后继。

2、定义实现

（1）单向链表

用数组模拟的话，代码是这样的：

struct student {
    string name; // 节点本身的信息，比如说姓名
    int next; // 后继，排在我后面的人的下标
};
student a[100]; // 用数组来存储学生的信息
//（一般来说都是用指针实现的，但是算法竞赛不大用指针）
1
2
3
4
5
6

增加与删除链表中的元素
链表可以以O(1)的效率快速地增加和删除元素。

如图所示的链表表示的队列。现在希望在原来的队列中加入一个标号为10的学生，这个学生排在标号为1的学生的后面。

那我们只需要先告诉10号：“1后面的人是6号，你进入队伍以后，后面的人就是6号。”

然后再告诉1号：“现在你后面的人是10号。”

这样就完成了一个单向链表的插入。

这个过程用代码来表示，就是这样的。

a[10].next = a[1].next; // 10进入队列，原本1后面的人现在变成10后面的人
a[1].next = 10; // 1后面的人变成10
1
2

如果想要把10号同学踢出队伍，我们需要找到他前面的1号同学。

然后告诉1号：“10号走了，他后面的人现在变成你后面的人了。”

然后10号就事实上被踢出队伍了。这个时候我们就可以把10号的信息清空。

这样就实现了删除。代码如下：

a[1].next = a[10].next;
a[10].next = 0;
1
2

（2）双向链表

刚刚介绍的是单向链表，单向链表中每个节点只存了他的后继或者前驱，在遍历链表的时候，只能从一个方向遍历。
而双向链表存了前驱和后继，这使得他两个方向都可以遍历。
我们可以把每相邻的的两个同学想象成他们牵着手（如图） 。

既然如此，我们就只需要改动左右手指向的同学就可以了 定义一个结构体

struct T{
    int l,r; // 每个同学的“左右手”就是链表节点的前驱和后继
}t[mx]={0};
1
2
3

现在我们就手动模拟一下加入同学（以右边为例） 将编号为 $J$ 的同学加入编号为 $i$ 的同学右边

第一步 $J$ 的右手牵 $I$ 右手牵的同学

t[j].r=t[i].r;
1

第二步 $J$ 的左手牵 $I$

t[j].l=i;
1

第三步 $I$ 的右手牵 $J$

t[i].r=j;
1

第四步 $J$ 右手牵的同学的左手牵 $J$
注意：此时 $i$ 的右手已经不牵原来那个同学了

t[t[j].r].l=j;
1

此时J就加入链当中了
左边同理
加入函数如下

void add(int i,int k,int f)       //新增同学 
{
    if(f==1)         //将 k 号同学插入到 i 号同学的右边
    {
        t[k].r=t[i].r;
        t[k].l=i; 
        t[i].r=k;
        t[t[k].r].l=k;
    }
    else             //将 k 号同学插入到 i 号同学的左边
    {
        t[k].r=i;
        t[k].l=t[i].l;
        t[i].l=k;
        t[t[k].l].r=k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

接下来是移除
我们虽然也可以用上面方法来删除
不过我们也可以用另一种方法（主要是懒）
我们可以给每个同学一个标记，标记了的将不会输出

struct T{
    int l,r;        //每个同学的“左右手” 
    int d;          //表示同学是否输出 
}t[mx]={0};
1
2
3
4

结构体

while(m--)
{
    cin>>x;           //要删去的同学
    t[x].d=1;         //将该同学标记为不输出 
}
1
2
3
4
5

ps:其实我更建议写一个del函数，真正从链表里删除。像这样：

void del(int x) { // 删除序号为x的同学
    if (t[x].l == 0 && t[x].r == 0) return; //已经被删除就忽略
    t[t[x].l].r = t[x].r; // 对于x左边的同学而言，他的右侧换成t[x].r了
    t[t[x].r].l = t[x].l; // 同理
    t[x].l = t[x].r = 0; // 清空x的信息，表明x已经出列
}
1
2
3
4
5
6

四、栈

1、介绍

栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

2、数组模拟栈

（1）入栈过程

首先声明一个固定大小的数组arr，并将索引index指向0位置，压入数据的时候，先给arr[index]赋值，再将index++

注意点：

如果index=arr.length的时候，用户要入栈，给用户抛出“栈已满”的异常（下图最右边的情况）

（2）弹栈过程

用户调用弹栈的功能的时候，先将index–,然后再将arr[index]返回即可

注意点：

如果index=0的时候，用户要弹栈，给用户抛出“栈为空”的异常（下图最右边的情况）

如果用户只是要查看栈顶的数据，不是弹栈的话，只需要将arr[index-1]返回就行，但是不要添加index–功能（查看的时候，也需要先判断有没有数据，即index是否为0）

（3）代码

#include<stdio.h>
// 数组模拟栈（先进后出） 
void Stack(int n){
	int stack[100],i;
	int m = 0;//栈底 是从一开始的 
	
	for(i = 0; i < n; i++){
		stack[++m] = i;
	}
	
	if(m == 0){
		return ; 
	}
	
	while(m > 0){
		printf("%d ",stack[m--]);
	} 
}
int main(){
	int N;
	scanf("%d",&N);
	Stack(N);//栈
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3、STL栈

（1）头文件

#include<stack>//栈
1

（2）定义方式

stack<int>  s;//参数也是数据类型，这是栈的定义方式
1

（3）常用操作

栈：
s.empty()//如果栈为空返回true，否则返回false  
s.size()//返回栈中元素的个数  
s.pop()//删除栈顶元素但不返回其值  
s.top()//返回栈顶的元素，但不删除该元素  
s.push(X)//在栈顶压入新元素 ，参数X为要压入的元素
1
2
3
4
5
6

五、队列

1、介绍

队列是只允许在表的前面进行删除操作，表的后面进行插入数据，也就是所谓的先进先出

2、数组模拟队列

（1）图解过程

首先准备一个数组，以及一个first索引，last索引
插入新数据的时候，在last位置插入数据，并且将last++(first不动)

---

删除数据的时候，将arr[first]返回，并且将first++

注意：

1、last来到数组末尾arr.length-1的时候，插入数据后，要将last=0，即回到数组索引0位置

2、first也是一样，到达arr.lenght-1时，删除数据后，也要将first=0

从上面的流程可以感觉的出，first一直追着last，记住这种感觉哈

（2）代码

//数组模拟队列 (先进先出 尾进头出)
void Queue(int n){
	int queue[100],i;
	int head = 0,last = 0;
	
	for(i = 0; i < n;i++){
		queue[last++] = i;
	}
	
	while(head - last){
		printf("%d ",queue[head++]);
	}
} 
int main(){
	int N;
	scanf("%d",&N);
	Queue(N);//队列 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、STL队列

（1）头文件

#include<queue>// 队列 
1

（2）定义方式

queue<int>  q; //参数是数据类型，这是队列的定义方式
1

（3）常用操作

队列：
q.empty()// 如果队列为空返回true，否则返回false  
q.size() // 返回队列中元素的个数  
q.pop()  //删除队列首元素但不返回其值  
q.front()  // 返回队首元素的值，但不删除该元素  
q.push(X) //在队尾压入新元素 ，X为要压入的元素
q.back() //返回队列尾元素的值，但不删除该元素  
1
2
3
4
5
6
7