机试小课堂丨C++ 数据结构，提高运行和存储效率的钥匙！

【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】

/ 写在前面的话 /

苏世机试小课堂，考研机试不再慌！

公主号：苏世学社考研  苏世计算机考研

数据结构是什么？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构常用内容介绍

1

栈

 

1.1 概念

栈是一种操作受限的线性表，只允许从一端插入和删除数据。栈中的数据元素遵守“先进后出”（FILO）的原则，允许元素插入和删除的一端称为栈顶，另一端称为栈底。栈的插入操作叫做进栈，也叫压栈、入栈，栈的删除操作叫出栈、弹栈。

 

1.2 常用操作

 

1.3 栈的应用——括号匹配

题目描述

给定一个只包括 (、)、{、}、[、] 的字符串，判断字符串是否有效。有效字符串需满足：（1）左括号必须用相同类型的右括号闭合。（2）左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

示例

输入: “()”

输出: true

输入: “()[]{}”

输出: true

输入: “([)]”

输出: false

输入: “{[]}”

输出: true

算法思想

①：从左往右遍历输入的括号序列，左括号进入②，右括号进入③

②：入栈

③：出栈一个元素，看看能不能和当前的右括号组成一对，如果不可以，则返回false；如果出栈异常（从空栈中出栈）也要返回false

④：如果顺利遍历成功，检查栈中有没有剩余元素。如果有，则返回false；如果没有，则返回true

代码展示和运行结果

2

优先队列

2.1 概念

顾名思义，就是优先级最大的排在队列的头部，优先级是根据对象的compare方法比较获取的，保证根节点的优先级一定比子节点的优先级更大。

 

2.2 常用操作

 

2.3 代码示例

3

二叉树

3.1 概念

二叉树是树中结点的度不大于2的有序树，是一种最简单最重要的树。二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树组成的非空树，左子树和右子树同样都是二叉树。

 

3.2 特殊类型

满二叉树：一个二叉树只有度为0和2的结点，并且度为0的结点在同一层上，则这个二叉树称为满二叉树。

完全二叉树：叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序和右分支下子孙的最大层序相等或大1。

 

3.3 典型问题

利用队列实现层序遍历

用栈实现前序

用栈实现中序

用栈实现后续

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导