dedecms网站地图插件,非标自动化外包平台,制作网页哪家好,网站建设合同 域名文章目录 四、链表理论五、哈希表理论五、栈和队列理论5.1 单调栈 六、二叉树理论6.1 树的定义6.2 二叉树的存储方式6.3 二叉树的遍历方式6.4 高度和深度 最近博主学习了算法与数据结构的一些视频#xff0c;在这个文章做一些笔记和心得#xff0c;本篇文章就写了一些基础算法… 文章目录 四、链表理论五、哈希表理论五、栈和队列理论5.1 单调栈 六、二叉树理论6.1 树的定义6.2 二叉树的存储方式6.3 二叉树的遍历方式6.4 高度和深度 最近博主学习了算法与数据结构的一些视频在这个文章做一些笔记和心得本篇文章就写了一些基础算法和数据结构的知识点具体题目解析会放在另外一篇文章。在学习时已经有C C的基础。文章附上了学习的代码仅供大家参考。如果有问题有错误欢迎大家留言。算法与数据结构一共有三篇文章剩余文章可以在
【CSDN文章】晚安66博客文章索引找到。 四、链表理论 单链表由一个个节点组成每个节点由一个数据域和一个指针域组成数据域放数据指针域指向下一个节点链表入口节点叫做head最后一个节点的next指针指向NULL(空指针)。 双链表在单链表的基础上增加了一个指针域这个指针域指向前一个节点head的prev指针指向NULL。双链表既可以向前查也可以向后查。 循环链表链表的首尾相连。循环链表可以解决约瑟夫环问题。 数组在内存中是连续分布的但是链表不是连续分布的它通过指针域的指针链接在内存中的各个节点。 链表定义方式
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};初始化链表
// 法一
ListNode* head new ListNode(5);
// 法二
ListNode* head new ListNode();
head-val 5;删除和添加节点 假如想删除图中D节点那么我们将C节点指针指向E节点然后释放D的内存C需要手动释放JavaPython有内存回收机制不需要手动释放。 假如要添加F节点将C节点的指针指向FF指针指向D即可。 查询 链表查询是比较费劲的例如想找第10个节点那么得从第一个节点开始按指针域一个一个找找到第九个节点才能找到第十个节点。因此链表查询时间复杂度为 O ( n ) O(n) O(n)
项目插入/删除查询使用场景数组 O ( n ) O(n) O(n) O ( 1 ) O(1) O(1)数据量固定频繁查询较少增删链表 O ( 1 ) O(1) O(1) O ( n ) O(n) O(n)数据量不固定频繁增删 较少查询
五、哈希表理论 哈希表可以通过索引直接访问表中的元素。哈希表一般用来快速判断一个元素是否出现在集合里但哈希法是牺牲空间换取时间因为要使用额外的数组set或map才能实现快速查找。举个例子班级里是否有小明这个同学如果要用枚举时间复杂度为 O ( n ) O(n) O(n)但如果哈希表只需要 O ( 1 ) O(1) O(1)就可以做到。 在初始化时只需要把全班的名字存在哈希表里查询的时候通过姓名直接可以知道是否有这位同学。哈希表通过哈希函数(hash funciton)将学生姓名映射到哈希表上。 工作原理如上图所示哈希函数将姓名转换成数值索引一般通过特定编码方式然后按索引在哈希表上得到目标数据。同时为了保证哈希函数计算的索引一定落在哈希表中还做了取模操作。有时候学生数量会大于哈希表长度不同学生会得到同一个索引也就是映射到哈希表上同一个位置也就出现所谓的哈希碰撞问题。
哈希碰撞解决办法
1、拉链法在碰撞位置引入链表链表指向依次指向不同的学生。拉链法要注意适当选择哈希表大小充分利用哈希表内存同时不要生成太长的链表。2、线性探测法当发生碰撞时就找表的下一个空位方置。因此一定要保证哈希表大小大于数据大小。
常用的哈希表有
数组集合set映射map 在C中set和map提供了下面几种形式使用集合来解决问题时优先使用unordered_set它底层用哈希表实现查询效率和增删效率最高。只有处理有序数据时用set或者multiset二者区别在于值能否重复。 虽然set、multiset、 map和multimap底层使用红黑树实现的但是使用方式还是哈希表的key和value方式同属于映射方法同样可以归类到哈希法中。此外红黑树是一种平衡二叉搜索树key值是有序的但key值不能修改改动key值会导致整颗树错乱所以智能删除和增加。map当中对key有限制不可修改value没有限制。
五、栈和队列理论 首先是关于栈和队列的元素进出关系栈是先进后出队列是先进先出。栈提供push 和 pop 等等接口所有元素必须符合先进后出规则所以栈不提供走访功能也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。 栈是以底层容器完成其所有的工作对外提供统一的接口我们可以控制使用哪种容器来实现栈的功能栈是可插拔例如vectorlistdeque等等。所以STL中栈往往不被归类为容器而被归类为container adapter容器适配器。目前最常见的SGI STLSTL库的其中一个版本如果没有指定底层实现默认以deque双向队列缺省为底层容器只要封住一端开通另一端就可以实现栈的逻辑。 也可以指定vector为底层实现
std::stackint, std::vectorint third; // 使用vector为底层容器的栈队列的情况是一样的队列中先进先出的数据结构同样不允许有遍历行为不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。队列也不归为容器也是容器适配器。
std::queueint, std::listint third; // 定义以list为底层容器的队列5.1 单调栈 单调栈问题长是针对一个一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。单调栈可以在 O ( n ) O(n) O(n)的时间复杂度内找到每一个元素的右边第一个比它大的元素位置。单调栈的本质是空间换时间优点是整个数组只需遍历一次。我们使用一个栈来保存遍历过程中的元素。因为我们遍历数组的时候我们不知道之前都遍历了哪些元素以至于遍历一个元素找不到是不是之前遍历过一个更小的所以我们需要用一个容器这里用单调栈来记录我们遍历过的元素。 单调栈问题需要考虑以下几点 单调栈里面存放的元素是什么 单调栈是递增还是递减的 这里的递增或者递减的顺序指的是从栈底到栈顶栈头的顺序C中使用STL库可以用st.top()来访问栈顶。
六、二叉树理论
6.1 树的定义 首先引入树的度的概念结点拥有的子树个数称为结点的度比如下图中结点3和结点4的度分别为3和2。对于树而言树的度是结点最大的度下面这棵树的度为4结点1的度。 二叉树是指树的度最大为2的树。满二叉树如果一棵树只有度为0和度为2的节点并且度为0的节点在同一层上则这棵二叉树为满二叉树。如下图所示这是一棵满二叉树。这棵二叉树为满二叉树也可以说深度为k有2^k-1个节点的二叉树。 完全二叉树在完全二叉树中除了最底层节点可能没有填满以外其余每层节点数量都达到最大值并且最下面一层节点都集中在该层的最左边若干位置。若底层为第k层则该层包含 [ 1 , 2 k − 1 ] [1, 2^{k-1}] [1,2k−1]个节点。 在【算法和数据结构】347、LeetCode前 K 个高频元素中提到的优先级队列。实际上优先级队列其实是一个堆堆就是一棵完全二叉树同时保证父子节点的顺序关系。下图当中第三棵树就不是一棵完全二叉树。 二叉搜索树又叫二叉排序树。它具有下面三个特点
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树 平衡二叉排序树又被称为AVLAdelson-Velsky and Landis树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。下图当中第三棵树就不是一棵平衡二叉树左右两个子树的高度差绝对值超过了1。 C中map、set、multimapmultiset的底层实现都是平衡二叉搜索树所以map、set的增删操作的时间复杂度是 l o g ( n ) log(n) log(n)。unordered_map、unordered_set底层实现是哈希表 增删操作的时间复杂度为 O ( 1 ) O(1) O(1)。详细内容可以看本文第五节。
6.2 二叉树的存储方式 二叉树可以用链式存储也可以顺序存储。那么链式存储方式就用指针 顺序存储的方式就是用数组。链式存储如下图所示 顺序存储如下图所示在遍历时假设父节点为i那么它的左孩子就是 i ∗ 2 1 i*21 i∗21右孩子就是 i ∗ 2 2 i*22 i∗22。相较于链式存储顺序存储方式比较不容易理解也不直观所以一般我们用链式存储二叉树。
6.3 二叉树的遍历方式
二叉树主要有两种遍历方式这两种也是图论当中最基本的两种遍历方式。
深度优先遍历先往深处走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。
在上面两种方式的基础之上进一步拓展有如下的分类 深度优先遍历 前序遍历递归法、迭代法中序遍历递归法、迭代法后序遍历递归法、迭代法 广度优先遍历 层次遍历迭代法
前中后是指中间节点的遍历顺序是在前、中或者是后。例如前序遍历中左右中序遍历左中右后序遍历左右后。 递归法和迭代法是这两种遍历的实现方法。深度优先遍历一般是用递归的方式实现也就是说用递归来实现前中后遍历比较方便。栈其实就是递归的一种实现结构前中后遍历的逻辑也可以用栈使用非递归的方式来实现。广度优先遍历的实现一般使用队列来实现队列是先进先出的结构这样才能一层层的遍历二叉树。 链式存储二叉树节点的定义方式如下相较于链表节点二叉树节点与其定义差不多二叉树节点有两个指针分别指向了其左右孩子。 树节点定义
// 树节点定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};迭代法实现前中后遍历
class Solution {
public:// 前序遍历void traversal_preOrder(TreeNode* cur, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal_preOrder(cur-left, vec); // 左traversal_preOrder(cur-right, vec); // 右}// 中序遍历void traversal_midOrder(TreeNode* cur, vectorint vec) {if (cur NULL) return; traversal_midOrder(cur-left, vec); // 左vec.push_back(cur-val); // 中traversal_midOrder(cur-right, vec); // 右}// 后序遍历void traversal_postOrder(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal_postOrder(cur-left, vec); // 左traversal_postOrder(cur-right, vec); // 右vec.push_back(cur-val); // 中}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal_preOrder(root, result);return result;}
};6.4 高度和深度 高度和深度是相反的表示深度是从上到下数而高度是从下往上数。深度指从根节点到该节点最长简单路径边数而高度指从该节点到叶子节点的最长简单路径边数。叶子节点是指没有子节点的节点。假设根节点的深度和叶子节点的高度为1那么树的深度和高度是相等的而对其他节点来说高度和深度不一定相等。例如下图当中8这个节点的深度为2高度为4。 end
