puppet_pyt的博客

为什么需要AVL树，以树的结构插入或删除大量随机数据时，有可能会导致树的一边轻一边重， 例如极端情况插入依次123456时，树就与链表无异了，Ologn的查找效率也变成了On; AVL树的特性：左右子树高度差最大为1，为了维持这个特性，在插入和删除操作时就需要旋转； 旋转规则：当插入位置为对左儿子的左子树进行插入则左单旋，左儿子的右子树时左双旋， 右儿子则镜像； #inclu

采用分离链接法处理冲突， 即当产生冲突时，将以链表的形式将新元素插入原来的元素之后 /*********************************************** > Filename: HashTable.cpp > Author: Pyt > Create: 2017-08-19 10:00:00 ***********

查找二叉树：始终满足任一节点的左儿子小于该节点，右儿子大于该节点， 由于其特性，查找二叉树的中序遍历始终为从小到大； 需要注意的是二叉查找树的删除，有2种策略，在删除节点不多时可以采用懒惰删除，即标记该节点删除而非真正的delete，第二种是当删除节点只有一个儿子或则为叶子节点即没有儿子时，可直接删除并将儿子移至该节点，而当删除节点有左右儿子时将其右子树最小的节点移动至该节点，当然这里并非真正

二叉堆： 堆是一颗完全二叉树， 即除了底层外都被填满，底层从左到右填入的二叉树，注意不是满二叉树； 堆的特性：最大堆，堆顶元素始终为最大值，任一节点的左右儿子则均小于该节点，最小堆则相反 堆由于其特性可以以数组实现并且不大量浪费空间； 当该节点为位置为i时，其左二子位置为2i， 右儿子为2i+1; root节点应在下标为1的位置； 这里实现了最大堆 /*********

队列：先进先出，以尾插法链表实现，增加一个指针记录链表尾，入队时插入尾部，出队时删除链表头以实现先进先出的特性 /*********************************************** > Filename: Queue.cpp > Author: Pyt > Create: 2017-08-19 14:46:15 ******

栈：先进后出 关于其应用值得一提的便是后缀表达式 /*********************************************** > Filename: Stack.cpp > Author: Pyt > Create: 2017-08-19 13:41:43 ************************************

准备把基本数据结构以模板类的形式都敲一遍以准备秋招和PAT考试 /*********************************************** > Filename: list.cpp > Author: Pyt > Create: 2017-08-04 09:36:04 *******************************

树的递归理解起来需要花点时间； 关于查找二叉树的删除： #include #include typedef struct TreeNode{ int data; struct TreeNode *left; struct TreeNode *right; }tree; typedef tree *PtrToTree; typedef PtrToTree Searc

最近在学数据结构，看的是《数据结构与算法分析》这本书，尝试着写了下链表和二叉树； #include #include typedef struct NODE{ struct NODE *next; int data; }Node; typedef Node *PtrToNode; typedef PtrToNode Linklist; Linklist find(int x