PYQ Blog

「想成为真正的工程师」

数据结构—堆、哈夫曼树

[Data Structre] Heap, Huffman tree

Ⅰ. 推荐课程 【浙江大学】数据结构，浙大的数据结构讲的很精炼，不枯燥易懂，十分适合数据结构的学习。 以下笔记也是根据以该课程为主，并加以具体实现代码。 Ⅱ. 堆 堆：堆是使用数组实现的完全二叉树，其任一结点的值是其子树所有结点的最大值或最小值。 堆可分为大根堆和小根堆： 大根堆：在完全二叉树中，任何一个子树的最大值都在这个子树的根结点。 小根堆：在完全二叉树中，任何一...

Posted by PYQ on April 25, 2022

数据结构—二叉搜索树、平衡二叉树

[Data Structre] Search Binary Tree, Balanced Binary Tree

Ⅰ. 推荐课程 【浙江大学】数据结构，浙大的数据结构讲的很精炼，不枯燥易懂，十分适合数据结构的学习。 以下笔记也是根据以该课程为主，并加以具体实现代码。 Ⅱ. 二叉搜索树 二叉搜索树：也称为二叉排序树或二叉查找树 非空左子树所有键值小于其根结点的键值。 非空右子树所有键值大于其根结点的键值。 左、右子树都是二叉搜索树。 二叉搜索树的查找操作： 从根结点开始...

Posted by PYQ on April 24, 2022

数据结构—树的定义和表示

[Data Structre] Definition and Representation of Tree

Ⅰ. 推荐课程 【浙江大学】数据结构，浙大的数据结构讲的很精炼，不枯燥易懂，十分适合数据结构的学习。 以下笔记也是根据以该课程为主，并加以具体实现代码。 Ⅱ. 树的定义 树的定义：是n(n>=0)个结点构成的有限集合。 n=0时，即没有一个结点，称为空树。 n>0时，没有双亲结点的唯一结点称为根结点。 树由多个子树构成。 结点为n的树，其边的数量为n-...

Posted by PYQ on April 21, 2022

数据结构—二叉树的定义、存储结构和遍历

[Data Structre] Definition, Structure and Traversal of Binary Tree

Ⅰ. 推荐课程 【浙江大学】数据结构，浙大的数据结构讲的很精炼，不枯燥易懂，十分适合数据结构的学习。 以下笔记也是根据以该课程为主，并加以具体实现代码。 Ⅱ. 二叉树的定义 二叉树： 二叉树是有穷结点的集合 二叉树可为空。 二叉树若不为空，则由根结点，其左子树和右子树的两个不相交的二叉树构成。 二叉树的子树也为二叉树。 二叉树可以由如下5种基本形态：空、只有根...

Posted by PYQ on April 21, 2022

数据结构—KMP模式匹配算法

[Data Structre] KMP

Ⅰ. 字符串匹配 字符串匹配问题：字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？ 其中 S 称为主串；P 称为模式串。C语言函数strstr()就是解决字符串匹配的函数，下图为Leetcode 28题，也是解决字符串匹配问题。 如何去解决字符串匹配问题呢？ Ⅱ. Brute-Force (BF) 按照人脑的第一反应，进行字符串匹配时，从主串的第一个元素开...

Posted by PYQ on April 20, 2022

数据结构—静态链表

[Data Structre] Static Link List

Ⅰ.前言 之前的数据结构学习中对“静态链表”不太熟悉，最近在阅读《大话数据结构》以及刷算法题时再次遇到“静态链表”，觉得很有意思，对解题的思维有所帮助，遂记录。 Ⅱ. 静态链表 C/C++以及面向对象语言可以非常容易地操作内存中的地址和数据，而对于早期的编程语言，如何实现链表呢？答案是“静态链表”。 结构定义 使用数组代替指针用于表示链表，数组的元素由两个数据域构成，即data（用...

Posted by PYQ on April 19, 2022

数据结构—两栈共享存储空间

[Data Structre] Two Stacks Share Storage Space

Ⅰ. 栈的应用 子程序的调用 递归 进制转换 表达式的转换与求值（后缀表达式） 二叉树的便利 图的深度优先算法 浏览器的返回 软件的撤销操作 Ⅱ. 两栈共享存储空间 假设有两个同类型的栈，各自有各自的数组空间，当一个栈已经满了，再进栈就会发生溢出，而另外一个栈还有很多存储空间，此时为了更好的利用存储空间，我们可以设计两个栈共享一个存储空间。 定...

Posted by PYQ on April 19, 2022

数据结构—循环队列

[Data Structre] Circular Queue

Ⅰ 队列的假溢出 队列与生活中的队列很相似，即先进先出。在入队时，只需在队尾增加一个元素，无需移动，即O(1)；而出队时，生活中则是后面的人全部前移一步，这大大增加了时间复杂度。若假定队头不需要出现在下标为0的位置，这样出队的性能就会大大增加。 但这也带来了新的问题，即假溢出。由于队列中对元素的操作发生在队头和队尾，即入队时尾指针rear+1，出队时头指针front加一，因此会发生如下情...

Posted by PYQ on April 19, 2022

数据结构—ADT

[Data Structre] Abstact Data Type

ADT（Abstact Data Type，抽象数据类型），一般用于数据结构的抽象模型。 ADT可以看作一些数据对象以及附加在这些数据对象上的操作的集合 ADT重在对功能的描述而不关心具体实现 ADT可由三元组表示（D，S，P），其中D是数据对象，S是D上的关系集，P是对D的基本操作集 ADT的表示和写法可参考《大话数据结构中的写法》。

Posted by PYQ on April 18, 2022

iPhone 5C—For the colorful

2022年的iPhone 5C

Ⅰ 5C简介 iPhone 5c是苹果公司于2013年9月10日发表的新一代智能手机，宣传口号为“生来多彩（For the colourful）”。iPhone 5c继iPhone 3GS之后再度使用聚碳酸酯作为外壳材质，并首次在iPhone产品中引入多种颜色，同时推出的专用保护壳亦有多种颜色可选。 由于价格和规格与iPhone 5极其相近，iPhone 5C被认为是iPhone 5的继...

Posted by PYQ on April 10, 2022

FEATURED TAGS
life cloud native OS 数据结构 xv6 Linux docker C++ Git os security security
ABOUT ME

Hi, it's PYQ here!
想成为真正的工程师。

FRIENDS