数据结构基础--蓝桥杯备考

1.优缺点总述

STL中各容器对比图

各类线性数据结构优缺点

1.数组

1.优点

1.简单，容易理解

2.访问快捷，只需要用下标就可以

3.有某些应用场景直接对应，例如二维数组对应平面

2.缺点

删除和插入数据非常耗时

2.链表

1.优点

插入和删除数据很便捷

2.缺点

定位数据比较耗时，要从链表头开始沿着指针一个一个走。

3.队列

有自己的使用场景，无优缺点

3.栈

有自己的使用场景，无优缺点

各类非线性数据结构优缺点

1.二叉树

2.哈希表

2.数组和高精度

1.大数组的使用

在大赛中经常用大数组，注意以下情况

1.建议不要用malloc（）动态分配，因为动态分配需要多写代码而且容易出错。

2.大数组应该定义成全局静态数组，而且不需要初始化为零，因为全局变量在初始化时自动赋值为零。因为定义到函数内部，可能会导致栈溢出。

2.对各种存储域的补充

1.栈

存储局部变量和函数调用信息等，容量较小

2.堆

由malloc，calloc，realloc等分配，需要手动释放。

3.数据段

存放已经初始化的全局变量与静态变量

4.bss段

存放未初始化的全局变量或静态变量。这些变量会被自动初始化0或NULL。

3.高精度算法

在计算机科学中，标准的数据类型如整型（int）、长整型（long）（long long）等都有其表示范围的限制。当需要处理比这些类型所能表示的范围更大的数字时，就需要使用高精度算法。

高精度算法这个过程类似于我们在学校里学习的手工算数，将数的每一位都存入数组，从最低位开始逐位处理，并处理进位。

除了C语言的静态数组，还可以用vector来定义大数组

1.代码演示高精度加法

#include<iostream>
using namespace std;
char a[1005],b[1005];//1005是防止有进位
string fun(string as, string bs)
{
	//注意不能写到主函数内，要写成子函数，因为a和b目前是指针类型，不能使用size
	string ss;//返回值
	int lmax;//两数组最长长度
	int lena = as.size(), lenb = bs.size();//长度
	for(int i=0;i<lena;i++)
	{
		a[lena - i - 1] = as[i] - '0';
	}
	for (int i = 0; i < lenb; i++)
	{
		b[lenb - i - 1] = bs[i] - '0';
	}
	lmax = lena > lenb ? lena:lenb;
	for (int i = 0; i < lmax; i++)
	{
		//这样就不用区分那个数字较大了
		a[i] += b[i];
		a[i + 1] += a[i] / 10;
		a[i] %= 10;
	}
	if (a[lmax])//如果非零，则有进位
	{
		lmax++;
	}
	for (int i = lmax - 1; i >= 0; i--)
	{
		ss += a[i] + '0';//将数字转化成字符，并且反转
	}
	return ss;
}
int main()
{
	string as, bs;
	cin >> as;
	cin >> bs;
	cout << fun(as,bs) << endl;
	return 0;
}

2.代码演示高精度减法

3.STL概述

1.string库

语法详情见STL-string容器

案例1

1.题目

问题描述

在烬寂海中居住着某种智慧生物。它们的文明发展程度相当于地球上的中世纪，但是它们拥有强大的科技与魔法。

一天，王国的法师得到了一段古老的魔法咒文，咒文中似乎隐藏着巨大的能量，但是咒文中有很多相似的字符串片段，法师们相信这些片段与魔法的启动有关。

现在，国王决定招募聪明的你，使用你的技术能力来帮助法师们解开这个谜团。

现在给你一个字符串 SS（主串），还有若干个模式串 PP。你需要统计每一个模式串在主串中出现的次数。

输入格式

第一行：一个字符串 SS，表示主串，只包含小写英文字母。

第二行：一个整数 nn，表示有 nn 个模式串。

接下来的 nn 行：每行一个字符串，代表一个模式串 PP，只包含小写英文字母。

输出格式

nn 行，每行一个整数，表示对应模式串在主串中出现的次数。

样例输入

bluemooninthedarkmoon
3
moon
blue
dark

 

样例输出

2
1
1

 

测评数据规模

主串的长度：∣S∣≤1×105∣S∣≤1×105。

模式串的数量：1≤n≤1001≤n≤100。

模式串的长度：∣P∣≤1000∣P∣≤1000。

运行限制

语言	最大运行时间	最大运行内存
C++	3s	128M
C	3s	128M
Java	5s	128M
Python3	7s	128M
PyPy3	7s	128M
Go	7s	128M
JavaScript	7s	128M

2.作答（第一版）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // 请在此输入您的代码
    string s;
    cin >> s;
    int n;
    cin >> n;
    int sumz[200]={0};
    for (int i = 0; i < n; i++)
    {
        string p;
        int posint = 0;
        int sum = 0;
        cin >> p;
        while (s.find(p,posint) != -1)
        {
            sum++;
            posint = s.find(p,posint);
            posint += p.size();
        }
        sumz[i] = sum;
    }
    for (int i = 0; i < n; i++)
    {
        cout << sumz[i] << endl;
    }
    return 0;
}

这一版只能通过百分之八十的案例，因为在第二十一行代码没有考虑到S为“aaaa”，P为“aa”，这样aa根据posint+=p.size();的话只能计数两次，应该改为posint++；这样就可以计数三次。

第二个问题是使用了静态数组sumz，浪费了空间，应该使用动态数组vector来节省空间。

3.作答（第二版）

#include <iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    // 请在此输入您的代码
    string s;
    cin >> s;
    int n;
    cin >> n;
    vector<int> sumz;
    for (int i = 0; i < n; i++)
    {
        string p;
        int posint = 0;
        int sum = 0;
        cin >> p;
        while (s.find(p,posint) != -1)
        {
            sum++;
            posint = s.find(p,posint);
            posint ++;
        }
        sumz.push_back(sum);
    }
    for (int i = 0; i < n; i++)
    {
        cout << sumz[i] << endl;
    }
    return 0;
}

4.官方题解

#include <iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    string s;
    int n;
    vector<int> sum;
    cin >> s >> n;
    int n1 = n;
    while (n--)
    {
        string p;
        cin >> p;
        int cnt = 0;
        for (int i = 0; i < s.length() - p.length() + 1; i++)
        {
            if (p == s.substr(i, p.length()))
                cnt++;
        }
        sum.push_back(cnt);
    }
    for (int i = 0; i < n1; i++)
    {
        cout << sum[i] << endl;
    }
    return 0;
}

使用了暴力算法

i < s.length() - p.length() + 1 的含义

• 这里的条件是 i < s.length() - p.length() + 1。

• s.length() 是主字符串 s 的长度，p.length() 是子字符串 p 的长度。

• s.length() - p.length() + 1 表示的是主字符串中最后一个可能与子字符串匹配的起始位置。

4.比较

时间复杂度比较

1. 官方题解：

   • 外层循环执行 n 次（每个子字符串 p 都需要处理一次）。
   • 内层循环的次数为 s.length() - p.length() + 1，每次调用 substr 提取子串并进行比较。
   • 假设主字符串 s 的长度为 m，子字符串 p 的平均长度为 k，则内层循环的时间复杂度为 O(m⋅k)O(m⋅k)。
   • 总时间复杂度为：O(n⋅m⋅k)O(n⋅m⋅k)。

2. 第二版：

   • 外层循环同样执行 n 次。
   • 内层使用 find 函数查找子字符串的位置。find 函数在最坏情况下需要扫描整个主字符串 s，其时间复杂度为 O(m)O(m)。
   • 如果子字符串匹配多次，find 会被调用多次，但总体上不会超过 m 次。
   • 总时间复杂度为：O(n⋅m)O(n⋅m)。

---

结果

• 官方题解的时间复杂度为 O(n⋅m⋅k)O(n⋅m⋅k)。
• 第二版的时间复杂度为 O(n⋅m)O(n⋅m)。

因此，第二段代码的时间复杂度更低，效率更高。

案例2

1.题目

元音大写

问题描述

输入一个由小写英文字母组成的字符串，请将其中的元音字母 (a,e,i,o,u)(a,e,i,o,u) 转换成大写，其它字母仍然保持小写。

输入格式

输入一行包含一个字符串。

输出格式

输出转换后的字符串。

样例输入

lanqiao

 

样例输出

lAnqIAO

 

评测用例规模与约定

对于所有评测用例，字符串的长度不超过 100100。

2.作答

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // 请在此输入您的代码
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
        {
            s[i] -= 32;
        }
    }
    cout << s << endl;
    return 0;
}

3.解答

题目设计数据限制较小直接用暴力即可。

2.迭代器

1.auto

补充：auto可以自动推导数据类型。

auto 关键字是 C++11 引入的一个非常有用的特性，它允许编译器自动推导变量的类型。使用 auto 可以简化代码，尤其是在处理复杂类型（如迭代器、模板实例化类型等）时。下面详细介绍 auto 的用法及其适用场景。

基本用法

当你声明一个变量并初始化它时，可以使用 auto 来让编译器根据初始化表达式的类型自动推导出变量的类型。

示例 1：基础类型

auto x = 5;       // x 是 int 类型
auto y = 3.14;    // y 是 double 类型
auto z = 'a';     // z 是 char 类型
auto str = "Hello"; // str 是 const char* 类型

示例 2：复杂类型

std::vector<int> vec = {1, 2, 3, 4};
auto it = vec.begin(); // it 是 std::vector<int>::iterator 类型

auto 结合引用和指针

auto 还可以与引用和指针结合使用，但需要注意的是，auto 默认不会推导出引用或指针类型。如果你希望得到引用或指针类型的变量，需要显式指定。

示例 3：引用

int a = 10;
auto b = a;        // b 是 int 类型，值为 10
auto& c = a;       // c 是 int& 类型，它是 a 的引用
c = 20;            // 修改 c 实际上修改了 a
std::cout << a << std::endl; // 输出 20

示例 4：指针

cpp

深色版本

int x = 10;
auto p = &x;       // p 是 int* 类型，指向 x
*p = 20;           // 修改 x 的值
std::cout << x << std::endl; // 输出 20

auto 结合常量

当初始化表达式是一个常量时，auto 推导出的类型也会是一个常量类型。

示例 5：常量

cpp

深色版本

const int ci = 10;
auto aci = ci;     // aci 是 int 类型，而不是 const int
const auto caci = ci; // caci 是 const int 类型

auto 结合模板

在模板编程中，auto 可以极大地简化代码，特别是在定义模板函数返回类型或模板参数类型时。

示例 6：模板中的 auto

cpp

深色版本

template <typename T>
auto get_value(T t) -> decltype(t + 1) {
    return t + 1;
}

auto 在范围循环中的应用

auto 在范围循环中特别有用，它可以让你轻松遍历容器中的元素，而无需显式声明迭代器类型。

示例 7：范围循环

cpp

深色版本

std::vector<int> vec = {1, 2, 3, 4, 5};

// 使用 auto 遍历 vector 中的每个元素
for (auto elem : vec) {
    std::cout << elem << " "; // 输出 1 2 3 4 5
}
std::cout << std::endl;

// 如果你想要修改元素，可以使用引用
for (auto& elem : vec) {
    elem *= 2; // 将每个元素乘以 2
}

for (auto elem : vec) {
    std::cout << elem << " "; // 输出 2 4 6 8 10
}
std::cout << std::endl;

注意事项

1. 类型推导规则：

   • auto 会忽略顶层 const 和引用，因此你需要显式添加它们。

   • 例如，auto x = 5; 推导出 int 而不是 const int 或 int&。

2. 复合类型：

   • 对于复合类型（如数组、函数指针等），直接使用 auto 可能会导致意外的结果。

   • 可以使用 decltype 辅助进行更复杂的类型推导。

3. 调试和可读性：

   • 虽然 auto 可以减少重复代码，但在某些情况下可能会影响代码的可读性。确保使用 auto 不会降低代码的理解难度。

总结

• auto 是一个强大的工具，用于简化代码并提高开发效率。

• 它可以自动推导变量的类型，尤其适用于复杂类型或模板编程。

• 注意使用 auto 时要理解其推导规则，并在必要时显式指定引用或指针类型，以避免潜在的错误

#include <iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
   vector<int> s;
   s.push_back(1);
   s.push_back(2);
   s.push_back(3);
   s.push_back(4);
   s.push_back(5);
   s.push_back(6);
   auto it = s.begin();
   it += 5;
   cout << *it << endl;
   return 0;
}

 目前蓝桥杯支持C++11标准库，支持auto关键字

3.容器

1.各个容器对比图

对比图

2.vector

vector详解

3.set

set详解

4.map

map详解

5.链表

1.手搓单链表

此次使用数组模拟静态链表，即逻辑上是链表，物理上是数组

#include<stdio.h>
using namespace std;
#include<iostream>
const int N = 10000;
struct cll
{
	int id;
	int data;
	int nextid;
}nodes[N];//nodes是结点的复数
int main()
{
	int n = 5;
	//构造链表
	nodes[0].id = 0;//显式赋值，将代码更加可视化。吐过不添加这串代码也没事，因为头节点会被隐式赋值，会自动赋值为0。
	nodes[0].nextid = 1;
	for (int i = 1; i <= n; i++)
	{
		nodes[i].id = i;
		nodes[i].nextid = i + 1;
		nodes[i].data = i * 10;
	}
	//定义为循环链表，尾指向头
	nodes[n].nextid = nodes[0].nextid;
	//删除链表节点
	cout << "是否删除" << endl;
	int bool1 = 0;
	cin >> bool1;
	if (bool1 == 1)
	{
		int nowid = 0;
		cout << "删除" << endl;
		cin >> nowid;//输入当前节点位置
		nodes[nowid - 1].nextid = nowid + 1;
		//定义为循环链表，尾指向头
		nodes[n].nextid = nodes[0].nextid;
	}
	//插入链表节点
	cout << "是否插入" << endl;
	int bool2 = 0;
	cin >> bool2;
	if (bool2 == 1)
	{
		cout << "插入位置" << endl;
		int n1 = n;
		int insert = 0;
		cin >> insert;
		nodes[++n1].id = n1;
		nodes[n1].data = 666;
		nodes[n1].nextid = nodes[insert].nextid;
		nodes[insert].nextid = nodes[n1].id;
		if (insert == 0)
		{
			//定义为循环链表，尾指向头
			nodes[n].nextid = nodes[0].nextid;
		}
	}
	//遍历链表
	int current = nodes[0].nextid;  // 从第一个数据节点开始
	do {
		printf("Node ID: %d, Data: %d\n", nodes[current].id, nodes[current].data);
		current = nodes[current].nextid;  // 移动到下一个节点
	} while (current != nodes[0].nextid);
}

对于插入操作中判断isnert==0的操作，是为了防止破坏链表结构

不更新链表结构的话，会导致无限循环

2.单链表题目

小王子单链表

题目描述

小王子有一天迷上了排队的游戏，桌子上有标号为 1−101−10 的 1010 个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把那个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了 MM 次，每次都是选取标号为 XX 个放到最前面，求每次排完后玩具的编号序列。

要求一：采用单链表解决

输入描述

第一行是一个整数 MM，表示小王子排玩具的次数。

随后 MM 行每行包含一个整数 XX，表示小王子要把编号为 XX 的玩具放在最前面。

输出描述

共 MM 行，第 ii 行输出小王子第 ii 次排完序后玩具的编号序列。

输入输出样例

示例 1

输入

5
3
2
3
4
2

输出

3 1 2 4 5 6 7 8 9 10
2 3 1 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

本题的解题思路是先删除再插入，不过由于是单链表，需要通过一个遍历算法算得到前面的节点id

3.手搓双向链表

#include<stdio.h>
using namespace std;
#include<iostream>
const int N = 10000;
struct cll
{
	int id;
	int data;
	int preid;
	int nextid;
}nodes[N];//nodes是结点的复数
int main()
{
	int n = 5;
	//构造链表
	nodes[0].id = 0;//显式赋值，将代码更加可视化。吐过不添加这串代码也没事，因为头节点会被隐式赋值，会自动赋值为0。
	nodes[0].nextid = 1;
	for (int i = 1; i <= n; i++)
	{
		nodes[i].preid = i - 1;
		nodes[i].id = i;
		nodes[i].nextid = i + 1;
		nodes[i].data = i * 10;
	}
	//定义为循环链表，尾指向头
	nodes[n].nextid = nodes[0].nextid;
	//删除链表节点
	cout << "是否删除" << endl;
	int bool1 = 0;
	cin >> bool1;
	if (bool1 == 1)
	{
		int nowid = 0;
		cout << "删除" << endl;
		cin >> nowid;//输入当前节点位置
		nodes[nowid - 1].nextid = nowid + 1;
		nodes[nowid + 1].preid = nodes[nowid - 1].id;
		//定义为循环链表，尾指向头
		nodes[n].nextid = nodes[0].nextid;
	}
	//插入链表节点
	cout << "是否插入" << endl;
	int bool2 = 0;
	cin >> bool2;
	if (bool2 == 1)
	{
		cout << "插入位置" << endl;
		int n1 = n;
		int insert = 0;
		cin >> insert;
		nodes[++n1].id = n1;
		nodes[n1].data = 666;
		nodes[n1].preid = nodes[insert].id;
		nodes[n1].nextid = nodes[insert].nextid;
		nodes[insert].nextid = nodes[n1].id;
		if (insert == 0)
		{
			//定义为循环链表，尾指向头
			nodes[n].nextid = nodes[0].nextid;
		}
	}
	//遍历链表
	int current = nodes[0].nextid;  // 从第一个数据节点开始
	do {
		printf("Node ID: %d, Data: %d\n", nodes[current].id, nodes[current].data);
		current = nodes[current].nextid;  // 移动到下一个节点
	} while (current != nodes[0].nextid);
}

4.极简链表

适合于单一场景，节点即值，值即节点

5.STL的list

list详解

1.list解决上面单链表题目

#include <iostream>
#include<list>
using namespace std;
const int n = 1000;
int main()
{
  list <int> toy{1,2,3,4,5,6,7,8,9,10};
  int m;
  int x;
  cin>>m;
  while(m--)
  {
    cin>>x;
    toy.remove(x);
    toy.push_front(x);
    for(auto i:toy)
    {
      cout<<i<<" ";
    }
    cout<<endl;
  }
  return 0;
}

2.list例题2

 问题描述

给定按从小到大的顺序排列的数字 11 到 nn，随后对它们进行 mm 次操作，每次将一个数字 xx 移动到数字 yy 之前或之后。请输出完成这 mm 次操作后它们的顺序。

输入格式

第一行为两个数字 n,mn,m，表示初始状态为 11 到 nn 的从小到大排列，后续有 mm 次操作。

第二行到第 m+1m+1 行，每行三个数 x,y,zx,y,z。当 z=0z=0 时，将 xx 移动到 yy 之后；当 z=1z=1 时，将x移动到 yy 之前。

输出格式

一行，nn 个数字，中间用空格隔开，表示 mm 次操作完成后的排列顺序。

样例输入样例输出

2 1 3 5 4

 

说明/提示

n≤1e4n≤1e4，m≤1e4m≤1e4。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

#include <iostream>
#include<list>
#include<algorithm>
using namespace std;
int main()
{
	// 请在此输入您的代码
	list<int>cll;
	int n, m, x, y, z;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cll.push_back(i);
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> z;
    cll.remove(x);
    auto it = find(cll.begin(), cll.end(), y);
		if (z == 0)
		{
			cll.insert(++it, x);
		}
		else if (z == 1)
		{
			cll.insert(it, x);
		}
	}
	for (auto i : cll)
	{
		cout << i << " ";
	}
	cout << endl;
	return 0;
}

6.队列

队列是一种先进先出的数据结构

1.手写队列

#include<iostream>
using namespace std;
const int N = 10000;
struct myqueue
{
	int a[N];//定义队列
	int head = 0;//对头
	int tail = -1;//队尾
	int size()
	{
		return tail - head + 1;
	}
	void push(int data)//入队
	{
		a[++tail] = data;
	}
	int front()//读队头
	{
		return a[head];
	}
	void pop()//弹出队头,不过注意保持head<=tail
	{
		if(head<=tail)
		head++;
		else
		{
			cout << "弹出失败" << endl;
		}
	}
};
int main()
{

}

这种写法有一个缺陷：如果进入队列的数据太多，导致tail超过了N，会导致数组溢出，导致出错，通过循环队列可以解决这个问题。

2.手写队列例题

题目描述

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

输入输出样例

输入 #1复制

10 3

输出 #1复制

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

#include<iostream>
using namespace std;
const int N = 10000;
struct myqueue
{
	int a[N];//定义队列
	int head = 0;//对头
	int tail = -1;//队尾
	int size()
	{
		return tail - head + 1;
	}
	void push(int data)//入队
	{
		a[++tail] = data;
	}
	int front()//读队头
	{
		return a[head];
	}
	void pop()//弹出队头,不过注意保持head<=tail
	{
		if(head<=tail)
		head++;
		else
		{
			cout << "弹出失败" << endl;
		}
	}
};
myqueue que;
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)//队列赋值
	{
		que.push(i);
	}
	while (que.size() != 0)
	{
		for (int i = 1; i < m; i++)
		{
			que.push(que.front());
			que.pop();
		}
		cout << que.front() << " ";
		que.pop();
	}
	cout << endl;
	return 0;
}

就是不断更新队头的位置，通过删除队头来解决问题

2.STL中的queue

queue详解