上海网站建设 找思创网络,做汽车新闻哪个网站好,win7如何安装iis来浏览asp网站,做公益的网站文章目录 1. 基本数据结构概述1.1 数据结构和算法的关系1.2 线性数据结构概述1.3 二叉树简介 2. 栈2.1 手写栈2.2 CSTL栈2.3 Java 栈2.4 Python栈 3 习题 1. 基本数据结构概述
很多计算机教材提到#xff1a;程序 数据结构 算法。 “以数据结构为弓#xff0c;以算法为箭”… 文章目录 1. 基本数据结构概述1.1 数据结构和算法的关系1.2 线性数据结构概述1.3 二叉树简介 2. 栈2.1 手写栈2.2 CSTL栈2.3 Java 栈2.4 Python栈 3 习题 1. 基本数据结构概述
很多计算机教材提到程序 数据结构 算法。 “以数据结构为弓以算法为箭” 数据结构是是计算机存储、组织数据的方法。常用的数据结构有数组Array、栈Stack、队列Queue、链表Linked List、树Tree、图Graph、堆Heap、散列表Hash等。分为两大类线性表、非线性表。数组、栈、队列、链表是线性表其他是非线性表。
1.1 数据结构和算法的关系
数据结构和算法往往密不可分。下面以图的存储为例说明数据结构和算法的关系。这几种存图的数据结构各有优缺点也各有自己的应用场景。
1边集数组
定义结构体数组
struct Edge{int u, v, w;
}edges[M];其中(u,v,w)表示一条边起点是u终点是v边长是w。edges[M]可以存M条边。
边集数组的优点是最节省空间的存图方法存储空间不可能再少了。n1000个点m5000条边的图使用的存储空间是12×5000 60KB。
边集数组的缺点不能快速定位某条边。如果要找某点u和哪些点有边连接得把整个edges[M]从头到尾搜一遍才能知道。
边集数组的的应用场景如果算法不需要查找特定的边就用边集数组。例如最小生成树Kruskal算法、最短路径Bellman-ford算法。
2邻接矩阵
定义一个二维数组 int edge[N][N];其中edge[i][j]表示点i和点j之间有一条边边长为edge[i][j]。它可以存N个点的边。若edge[i][j]0表示i和j之间没有边若edge[i][j] ! 0i和j之间有边边长为edge[i][j]。
邻接矩阵的优点能极快地查询任意两点之间是否有边。如果edge[i][j] ! 0说明点i和j之间有一条边边长edge[i][j]。
邻接矩阵的缺点如果图是一张稀疏图大部分点和边之间没有边那么邻接矩阵很浪费空间因为大多数edge[][]0没有用到。n1000个点m5000条边的图使用的存储空间是12×1000×1000 12MB。
邻接矩阵的应用场景1稠密图几乎所有的点之间都有边edge[][]数组几乎用满了很少浪费2算法需要快速查找边而且计算结果和任意两点的关系有关例如最短路径算法的Floyd算法。
3邻接表
邻接矩阵的优点十分节省空间因为只存储存在的边。
邻接矩阵的缺点没有明显的缺点。它的存储空间只比边集数组大一点点而查询边的速度只比邻接矩阵慢一点点。
邻接矩阵应用场景基于稀疏图的大部分算法。
1.2 线性数据结构概述
在所有数据结构中线性表是最简单的。线性表有数组、链表、队列、栈它们有一个共同的特征把同类型的数据一个接一个地串在一起。
下面对线性表做个概述并比较它们的优缺点。
1数组
数组是最最简单的数据结构它的逻辑结构和物理内存的存储完全一样。例如C语言中定义一个整型数组int a[10]系统会分配一个40字节的存储空间这100个字符的存储地址是连续的。
#include bits/stdc.h
using namespace std;
int main(){int a[10];for (int i0;i10;i) cout a[i] ; //打印10个整数的存储地址return 0;
}在作者机器上运行输出10个整数的存储地址 0x6dfec4 0x6dfec8 0x6dfecc 0x6dfed0 0x6dfed4 0x6dfed8 0x6dfedc 0x6dfee0 0x6dfee4 0x6dfee8
数组的优点1简单容易编程2访问快捷要定位到某个数据只需使用下标即可例如a[0]是第1个数据a[i]是第i-1个数据3与某些应用场景直接对应例如数列是一维数组可以在一维护数组上排序矩阵是二维数组表示空间坐标等等。
数组的缺点删除和增加数据很麻烦非常耗时。例如要删除数组int a[10]的第5个数据只能采用覆盖的方法从第6个数据开始每个往前挪一位。增加数据也麻烦例如要在第5个位置插入一个数据只能把原来第5个开始的数据逐个往后挪一位空出第5个位置给新数据。
2链表
链表是为了克服数组的缺点提出的一种线性表链表的插入和删除操作不需要挪动其他数据。简单地说链表是“是用指针串起来的数组”。链表的数据不是连续存放的而是用指针串起来的。例如下图删除链表的第3个数据只要把原来连接第3个数据的指针断开然后连接它前后的数据即可不用挪动其他的数据。 链表的优点增加和删除数据很便捷。这个优点弥补了数组的缺点。
链表的缺点定位某个数据比较麻烦。例如要输出第5个数据需要从链表头开始沿着指针一步步走找到第5个。链表的这个缺点却是数组的优点。
链表和数组的优缺点正好相反它们的应用场合不同数组适合静态数据链表适合动态数据。
链表如何编程实现在常见的数据结构教材中链表的数据节点是动态分配的各节点之间用指针来连接。但是在算法竞赛中如果手写链表一般不用动态分配而是用静态数组来模拟。
手写链表的代码见题目排队顺序
题解
#includebits/stdc.h using namespace std;int arr[1000010];
int main()
{int n;cin n;for (int i 1; i n; i) {cin arr[i];}int head;cin head;cout head;while (arr[head] ! 0) {cout arr[head];head arr[head];}return 0;
}
当然除非必要一般不手写链表而是用系统提供的链表例如C STL的listJava LinkedListPython的list。
链表在蓝桥杯等算法竞赛中不太常用所以本章没有详细介绍。 3队列
队列是线性数据的一种使用方式模拟现实世界的排队操作。例如排队购物只能从队头离开队伍新来的人只能排到队尾不能插队。队列有一个出口和一个入口出口是队头入口是队尾。队列的编程实现可以用数组也可以用链表。
队列这种数据结构无所谓优缺点只有适合不适合。例如宽度优先搜索BFS就是基于队列的用其他数据结构都不合适。
4栈
栈也是线性数据的一种使用方式模拟现实世界的单出入口。例如一管泡腾片先放进去的泡腾片后出来。栈的编程比队列更简单同样可以用数组或链表实现。
栈有它的使用场合例如递归使用栈来处理函数的自我调用过程。
1.3 二叉树简介
二叉树是一种高度组织性、高效率的数据结构。例如在一棵有n个节点的满二叉树上定位某个数据只需走logn步插入和删除某个数据也只需logn步。在二叉树的基础上发展出了很多高级数据结构和算法。大多数高级数据结构例如树状数组、线段树、树链剖分、平衡树、动态树等都是基于二叉树的。
2. 栈
栈stack是比队列更简单的数据结构它的特点是“先进后出”。
队列有两个口一个入口和一个出口。而栈只有唯一的一个口既从这个口进入又从这个口出来。所以如果自己写栈的代码比队列的代码更简单。
2.1 手写栈
如果使用环境简单最简单的手写栈代码用数组实现。
const int N 300008; //定义栈的大小
struct mystack{int a[N]; //存放栈元素从a[0]开始int t -1; //栈顶位置初始栈为空置初值为-1void push(int data){ a[t] data; } //把元素data送入栈int top() { return a[t]; } //读栈顶元素不弹出void pop() { if(t-1) t--;} //弹出栈顶int size() { return t1;} //栈内元素的数量int empty() { return t-1 ? 1:0; } //若栈为空返回1
};使用栈时要注意不能超过栈的空间。上面第1行定义了栈的大小是N栈内的元素数量不要超过它。
用下面的例子给出上述手写代码的应用。
例题表达式括号匹配
题解
合法的括号串例如“(())”、“()()()”像“)(()”这样是非法的。合法括号组合的特点是左括号先出现右括号后出现左括号和右括号一样多。
括号组合的合法检查是栈的经典应用。用一个栈存储所有的左括号。遍历字符串的每一个字符处理流程是 1若字符是 ‘(’进栈。 2若字符是’)有两种情况如果栈不空说明有一个匹配的左括号弹出这个左括号然后继续读下一个字符如果栈空了说明没有与右括号匹配的左括号字符串非法输出NO程序退出。 3读完所有字符后如果栈为空说明每个左括号有匹配的右括号输出YES否则输出NO。
C代码
手写栈
#include bits/stdc.h
using namespace std;
const int N 300008; //定义栈的大小
struct mystack{int a[N]; //存放栈元素从a[0]开始int t -1; //栈顶位置初始栈为空置初值为-1void push(int data){ a[t] data; } //把元素data送入栈int top() { return a[t]; } //读栈顶元素不弹出void pop() { if(t-1) t--; } //弹出栈顶int size() { return t1;} //栈内元素的数量int empty() {return t-1 ? 1:0; } //若栈为空返回1
}st;
int main(){char x;while(cinx){ //循环输入if(x) break; //输入为停止if(x() st.push(x); //左括号入栈if(x)){ //遇到一个右括号if(st.empty()) {coutNO;return 0;} //栈空没有左括号与右括号匹配else st.pop(); //匹配到一个左括号出栈}}if(st.empty()) coutYES; //栈为空所有左括号已经匹配到右括号输出yeselse coutNO;return 0;
}STL
#includebits/stdc.h
using namespace std;
string str;
stackchar ops;
int main()
{cin str;long res 0;for (int i 0; i str.length(); i) {char c str[i];if (c () {ops.push(c);}else if (c )) {if (!ops.empty()) {ops.pop();}else {cout NO;return 0;}}}if (!ops.empty()) {cout NO;return 0;}cout YES;return 0;
}
Java代码
import java.util.Scanner;
public class Main {static final int N 300008;static class mystack {int[] a new int[N];int t -1;void push(int data) { a[t] data; }int top() { return a[t]; }void pop(){ if(t -1) t--; }int size(){ return t 1; }boolean empty() { return t -1 ? true : false; }}public static void main(String[] args) {Scanner sc new Scanner(System.in);mystack st new mystack();String s sc.next();for (int i 0; i s.length(); i) {char x s.charAt(i);if(x ) break;if(x () st.push(x);if(x )) {if(st.empty()) {System.out.println(NO);return;}else st.pop();}}if(st.empty()) System.out.println(YES);else System.out.println(NO);}
}Python代码
Python的手写栈用到了list。用list模拟栈有一个好处不用担心栈空间不够大因为list自动扩展空间。而且list的栈操作非常快因为栈顶是list的末尾元素栈只有一个出入口只在list的末尾进行进栈和出栈操作操作极为快捷。下面是list实现的栈功能。 下面是例题的Python代码栈用list模拟。
st [] #定义栈用list实现
flag True #判断左括号和右括号的数量是否一样多
s input().strip()
for x in s:if x(: st.append(() #进栈if x):if len(st)!0: #len()栈的长度st.pop() #出栈也可以写成 del st[-1] st[-1]是栈顶else: #栈已空没有匹配的左括号flag Falsebreak
if len(st)0 and flag: print(YES)
else: print(NO)2.2 CSTL栈
竞赛时一般不自己手写栈而是用STL stackhttps://wyqz.top/p/870124582.html#toc-heading-9。
STL stack的主要操作见下表。 用下面的例题说明STLqueue的应用
例题排列
题解
把符合条件的一对i, j称为一个“凹”。首先模拟检查“凹”了解执行的过程。以“3 1 2 5”为例其中的“凹”有“3-1-2”和“3-1-2-5”还有相邻的“3-1”、“1-2”、“2-5”。一共5个“凹”总价值13。
像“3-1-2”和“3-1-2-5”这样的“凹”需要检查连续3个以上的数字。
例如“3 1 2”从“3”开始下一个应该比“3”小例如“1”再后面的数字比“1”大才能形成“凹”。
再例如“3-1-2-5”前面的“3-1-2”已经是“凹”了最后的“5”也会形成新的“凹”条件是这个“5”必须比中间的“1-2”大才行。
总结上述过程是先检查“3”再检查“1”符合“凹”再检查“2”比前面的“1”大符合“凹”再检查“5”比前面的“2”大符合“凹”。
以上是检查一个“凹”的两头还有一种是“嵌套”。一旦遇到比前面小的数字那么以这个数字为头可能形成新的“凹”。例如“6 4 2 8”其中的“6-4-2-8”是“凹”内部的“4-2-8”也是凹。如果学过递归、栈就会发现这是嵌套所以本题用栈来做很合适。
以“6 4 2 8”为例用栈模拟找“凹”。当新的数比栈顶的数小就进栈如果比栈顶的数大就出栈此时找到了一个“凹”并计算价值。下图中的圆圈数字是数在数组中的下标位置用于计算题目要求的价值。 图(1)6进栈。 图(2)4准备进栈发现比栈顶的6小说明可以形成凹4进栈。 图(3)2准备进栈发现比栈顶的4小说明可以形成凹2进栈。 图(4)8准备进栈发现比栈顶的2大这是一个凹“4-2-8”对应下标“②–④”弹出2然后计算价值j-i1④-②13。 图(5)8准备进栈发现比栈顶的4大这是一个凹“6-4-8”对应下标“①–④”弹出4然后计算价值j-i1④-①14。 图(6)8终于进栈了数字也处理完了结束。
在上述过程中只计算了长度为3和3以上的凹并没有计算题目中“3a[i]-a[j]之间不存在其他数字”的长度为2的凹所以最后统一加上这种情况的价值(n-1)×2 6。
最后统计得“6 4 2 8”的总价值是34613。
C代码
#include bits/stdc.h
using namespace std;
const int N 300008;
int a[N]; //这里a[]是题目的数字排列
int main(){int n; cinn;for(int i 1;i n;i) cina[i]; //输入数列stack int st; //定义栈long long ans 0;for(int i 1;i n;i){while(!st.empty() a[st.top()] a[i]){st.pop();if(!st.empty()){int last st.top();ans (i - last 1);}}st.push(i);}ans (n - 1) * 2; //3a[i]-a[j]之间不存在其他数字的情况coutans;
}2.3 Java 栈
Java Stack https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Stack.html
有以下操作。 例题 排列 的Java代码。
import java.util.Scanner;
import java.util.Stack;
public class Main {static final int N 300008;public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] a new int[N];for(int i 1; i n; i) a[i] sc.nextInt(); StackInteger st new Stack();long ans 0;for(int i 1; i n; i) {while(!st.empty() a[st.peek()] a[i]) {st.pop();if(!st.empty()) {int last st.peek();ans (long)(i - last 1);}}st.push(i);}ans (n - 1) * 2;System.out.println(ans);}
}2.4 Python栈
python的栈可以用以下三种方法实现1list2deque3LifoQueue。比较它们的运行速度list和deque一样快而LifoQueue慢得多建议使用list。前面已经介绍了用list实现栈的方法。
下面是例题 排列 的代码。
n int(input())
a [int(x) for x in input().split()]
st [] #定义栈用list实现
ans 0
for i in range(n):while len(st) ! 0 and a[st[-1]] a[i]: #st[-1]是栈顶st.pop() #弹出栈顶if len(st) ! 0:last st[-1] #读栈顶ans (i - last 1)st.append(i) #进栈
ans (n - 1) * 2
print(ans)3 习题
表达式括号匹配
表达式求值
小鱼的数字游戏
后缀表达式
【模板】栈
栈
