数据结构知识点

目录一、顺序表1、顺序表插入删除二、链表1、单链表1.1、插入具体操作1.2、删除2、循环链表2.1、双向循环链表判空2.2、双向循环插入链表和顺序表的区别三、栈3.1、链栈与顺序栈区别3.2、用栈模拟队列 注意事项四、队列1、出队列注意事项2、顺序结构实现循环队列循环队列判空五、堆1、堆的性质堆的常用场景六、二叉树1、二叉树的基本性质2、哈夫曼树的基本性质一、顺序表1、属于线性表。2、顺序表插入删除需要移动元素。3、动态顺序表中插入需要检查是否需要扩容4、数据在内存中是连续的可以支持随机访问1、顺序表插入删除a、顺序表插入元素需要移动元素这里需要把[i, n - 1]区间的元素全部向后移动一次故移动的次数为n - 1 - i 1b、顺序表删除元素需要移动元素这里需要把[i 1, n - 1]区间的元素全部向前移动一次故移动的次数为 n - i - 1二、链表1、属于线性表。2、链表插入删除元素只需要修改指针指向不需要移动元素。3、每次插入元素都是先出开一个节点的空间不需要事先估计存储空间。4、链表是用指针链接前后节点数据在内存中不一定连续链表没有索引不能随机访问。5、链表是由节点构成自然链表长度越大空间开销越大。因此会为节点间的逻辑关系而增加额外的存储开销1、单链表1.1、插入链表插入a、空链表插入时 首指针需要改变。b、非空链表插入时尾指针需要改变。//在单链表指针为p的结点之后插入指针为s的结点 s-nextp-next; p-nexts;具体操作1.2、删除//在一个单链表中q 的前一个节点为 p删除 q 所指向节点时 p-nextq-next; //链接起来 delete q;注意在长度为n(n1)的单链表上设有头和尾两个指针执行.删除单链表中的最后一个元素操作与链表的长度有关。因为其需要遍历单链表找到尾节点的前一个节点。所以与长度有关。其他的头删、头插、尾插都不需要遍历链表2、循环链表循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的 指针 域指向 头结点 整个链表形成一个环。1单循环链表——在单链表中将终端结点的指针域NULL改为指向表头结点或开始结点即可。2多重链的循环链表——将表中结点链在多个环上。指针 分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向 循环链表 。2.1、双向循环链表判空//双向带头循环链表中head不是存放有效数据的节点如果只有一个head节点说明链表为空。 head-nexthead;2.2、双向循环插入//在一个循环双向链表中要在p所指的节点之前插入s所指节点 s-nextp; s-prevp-prev; p-prev-nexts; p-prevs;// 最后对p的前继节点做出修改链表和顺序表的区别1、链表和顺序表都属于线性表。a、顺序存储结构---顺序表b、链式存储结构---链表2、链表不能随机访问其中的某个元素顺序表可以3、链表能做的事顺序表都可以完成只是操作方法不同效率不同4、链表插入和删除元素因为不需要移动节点所以相比较于数组而言链表的时间复杂度为O(1)数组的时间复杂度O(n)。注意链表的插入和删除不是所有情况下都比顺序表快比如尾插尾删顺序表的时间复杂度为O1并且如果是单链表如果要在中间某个节点的前面插入/删除一个节点则需要遍历。所以时间的快慢要分情况看待。5、链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。6、顺序表物理相邻逻辑相邻链表逻辑相邻物理不一定相邻三、栈1、栈是一种后进先出的数据结构2、顺序表和链表都可以用来实现栈不过一般都使用顺序表因为栈想当于是阉割版的顺序表只用到了顺序表的尾插和尾删操作顺序表的尾插和尾删不需要搬移元素效率非常高故一般都是使用顺序表实现。3、栈只能在栈顶进行输入的插入和删除操作。4、队列只能从队头删除元素。5、栈是有入栈和出栈操作出栈就是从栈中删除一个元素。3.1、链栈与顺序栈区别1、如果是链栈一般需要进行头插或者头删操作而顺序栈一般进行尾插和尾删操作链表的操作比顺序表复杂因此使用顺序结构实现栈更简单。2、链式结构实现栈时每次入栈相当于链表中头插一个节点没有扩容一说。3.2、用栈模拟队列 注意事项1、用栈模拟实现队列可以使用两个栈一个栈模拟入队列一个栈模拟出队列。2、出队列时直接弹出模拟出队列栈的栈顶元素当该栈为空时将模拟入队列栈中所有元素导入即可不是每次都需要导入元素。3、一个栈模拟入队列一个栈模拟出队列入队列时将元素直接往模拟入队列的栈中存放4、入队列操作时间复杂度为O(1)四、队列1、队列是先进先出的2、顺序表和链表都可以用来实现队列。3、出队操作一定会影响头指针如果出队之后队列为空会影响尾指针。4、数据入队列时一定从尾部插入、5、队列只能从队头删除元素。1、出队列注意事项用无头单链表存储队列其头指针指向队头结点尾指针指向队尾结点则在进行出队操作时。一定会修改头指针如果出队之后队列为空需要修改尾指针。2、顺序结构实现循环队列为什么用循环队列队列适合使用链表实现使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题因此大佬们设计出了循环队列循环队列就是为了解决顺序结构实现队列假溢出问题的。1、循环队列的长度都是固定的2、队头和队尾在同一个位置时 队列可能是空的也可能是满的因此无法判断。3、设置计数即添加一个字段来记录队列中有效元素的个数如果队列中有效元素个数等于空间总大小时队列满如果队列中有效元素个数为0时队列空。4、循环队列也是队列的一种是一种特殊的线性数据结构循环队列判空(rear - front) % (N 1)解释有效长度一般是rear-front, 但是循环队列中rear有可能小于front减完之后可能是负数所以需要N此时结果刚好是队列中有效元素个数但如果rear大于front减完之后就是有效元素个数了再加N后有效长度会超过N故需要%N。五、堆1、堆的性质1、堆是在完全二叉树的基础上进行了条件的限制即每个节点都比其孩子节点大则为大堆每个节点都比其孩子节点小则为小堆。2、大根堆根结点子结点总是最大的并且在堆的每一个局部都是如此。例如{3,1,2}可以看作为大根堆而{3,2,1}亦可以看作为大根堆。大根堆的根结点在整个堆中是最大的元素3、小根堆小根堆的性质与大根堆类似。4、删除操作需要执行向下调整算法5、插入操作需要执行向上调整算法向下调整的基本操作1、建堆时从每一个非叶子节点开始倒着一直到根节点都要执行一次向下调整算法。2、删除元素时首先交换堆顶元素与堆中最后一个元素对中有效元素个数减1即删除了堆中最后一个元素最后将堆顶元素向下调整。时间复杂度O(n)堆的常用场景1、堆排序。2、建立优先级队列若利用堆来建立优先级队列可以快速的获取到队列中优先级最高/低的任务。3、n个元素中排列出前k大的元素问题对于此类问题可以建立一个小根堆依次读入n个元素并调整并在堆的规模达到k1时剔除掉第1个元素剩下k个较大元素保持堆的规模不超过k一直循环即可得到最终的结果。六、二叉树1、二叉树的基本性质1、高度h log(n)向上取整 注意底数是2。 即log (n) 1。2、完全二叉树中如果一个节点没有左孩子则一定没有右孩子必定为一个叶子节点最后一层一定为叶子节点但是倒数第二层也可能存在叶子节点。3、在任意二叉树中度为0的节点都比度为2的节点多1个。4、在完全二叉树中如果节点总个数为奇数则没有度为1的节点如果节点总个数为偶数只有一个度为1的节点。5、对于任意的树都满足边的条数比节点个数少1因为每个节点都有双亲但是根节点没有6、一颗深度为 h 的满二叉树拥有 2^h-1 个结点根结点深度为17、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足只有一个叶子结点。8、一棵具有N个结点的二叉树采用二叉链表进行存储,其中空指针域有 n 1。n个节点n-1个非空。2、哈夫曼树的基本性质哈夫曼树(Huffman)树又称最优二叉树。它是n个带权叶子结点构成的二叉树中带权路径长度WPL最小的二叉树。因为构造这种树的算法是最早由哈夫曼于1952年提出的所以被称之为哈夫曼树。1、路径树中从“一个结点”到“另一个结点”之间的分支。2、路径长度一个路径上的分支数量。3、树的路径长度从树的根节点到每个节点的路径长度之和。4、节点的带权路径路径长度其实也就是该节点到根结点的路径长度乘以该节点的权。5、树的带权路径长度树中各个叶节点的路径长度*该叶节点的权的和常用WPL(Weight Path Length)表示。6、哈夫曼树的总结点数是2n-1n是叶子节点数并且非叶子节点数目总是比叶子节点数目小1。哈夫曼树没有度为1的节点3、搜索树1、线索二叉树中某节点P有左孩子的条件是 p -LTag 02、X是二叉树中序线索树中一个有左孩子的节点且X不为根则X的前驱为X的左子树的最右节点2、引入二叉线索树的目的是( 加快查找结点的前驱和后继速度 )。比如以数据集{4,5,6,7,10,12,18}为叶结点权值所构造的哈夫曼树,其带权路径长度为七、图邻接矩阵1、用邻接矩阵存储图用一个矩阵存储顶点信息和顶点间关系的信息。2、用邻接矩阵存储图占用的存储空间只与图中顶点数有关而与边数无关3、适用于稠密图邻接表1、用邻接表存储图图中每一个订点对应一个单链表链表中的一个节点包含了与该节点邻接的另一个顶点构成的一条边信息。2、用邻接表存储图占用的存储空间与图中顶点数和边数都有关。3、适用于稀疏图。