数据结构与算法知识点总结

2024-06-30 18:40| 来源: 网络整理| 查看: 265

绪论抽象数据类型

一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与计算机内部如何表示和实现无关。数据结构

相互之间存在一种或多种特定关系的数据元素的集合。

数据结构包括三方面内容：逻辑结构、存储结构、数据的运算。逻辑结构

数据元素之间的逻辑关系，与存储无关。可分为线性结构和非线性结构。

线性结构是一组有序的元素集合。存储结构

数据在计算机中的表示，也称物理结构。可分为顺序存储、链式存储、索引存储、散列存储。

顺序存储是把逻辑上相邻的元素存储在物理位置上也相邻的单元中。优点：随机存取缺点：可能产生较多的外部碎片链式存储不要求逻辑上相邻的单元在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。优点：没有外部碎片缺点：指针占用额外空间，且只能顺序存取索引存储除了存储数据，还建立附加的索引表。优点：检索速度快缺点：增加索引表占用较多的存储空间，修改表项也浪费时间散列存储是根据关键字直接计算出元素的存储地址。优点：检索、增加、删除结点都很快缺点：存在冲突算法

对特定问题求解步骤的一种描述。

算法不等于程序重要特性：有穷性、确定性、可行性、输入、输出线性表

具有相同数据类型的n个数据元素的有限序列。

顺序表动态分配：存储数组的空间是在程序执行过程中通过动态存储分配语句分配的。动态分配并非链式存储，它同样属于顺序存储结构，物理结构没有变化，依然可以采用随机存取方式，只不过分配空间的大小可以在运行时决定。链式表

单链表

头结点：头结点的指针域指向线性表的第一个元素结点。

头指针：不管有无头结点，头指针始终指向链表的第一个结点。在有头结点的链表中，头指针指向头结点；在物头结点的链表中，头指针指向第一个元素结点。头结点的优点：链表的第一个位置上的操作和其他位置上的操作一致，无需特殊处理。无论链表是否为空，头指针始终指向头结点。空表和非空表的处理得到统一。

链表创建

头插法尾插法。增加一个指向链表尾结点的指针。

插入结点

如果需要先找到前驱结点，则 f ( n ) = O ( n ) f(n)=O(n) f(n)=O(n);如果直接给出，则 f ( n ) = O ( 1 ) f(n)=O(1) f(n)=O(1) 插入结点元素为s，直接前驱是p。s.next = p.next; p.next = s; 插入结点元素为s，直接后继是p。s.next = p.next; p.next = s; swap(s.data,p.data);

删除结点

如果需要先找到前驱结点，则 f ( n ) = O ( n ) f(n)=O(n) f(n)=O(n);如果直接给出，则 f ( n ) = O ( 1 ) f(n)=O(1) f(n)=O(1) 待删除结点为q，直接前驱是p。p.next = q.next;

求表长

对不带头结点的链表，当表为空时，要单独处理。

双链表

增加一个指向前去的prior指针，使得访问前驱结点的时间复杂度为 O ( 1 ) O(1) O(1)。插入结点待插入结点为s，直接前驱为p。s.next = p.next; p.next.prior = s; s.prior = p; p.next = s.prior; 删除结点待删除结点为q，直接前驱为p。p.next = q.next; q.netx.prior = p;

循环链表

表中最后一个结点的指针不是NULL，而是改为指向头结点，形成一个环。循环单链表在处理表头和表尾的操作时，效率非常高，都只有 f ( n ) = O ( 1 ) f(n)=O(1) f(n)=O(1)。

静态链表

用数组描述线性表的链式存储结构，因此也要预先分配一块连续的内存空间。选取存储结构的理由基于存储的考虑。如果难以估算线性表长度时，宜采用链表。基于运算的考虑。如果按序号访问元素比较多，宜采用顺序表；如果插入删除操作比较多，宜采用链表。基于环境的考虑。顺序表容易实现。栈和队列栈

只允许在一端进行插入和删除操作的线性表。

顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素。栈的操作栈顶指针：S.top 栈空：S.top == -1 进栈：S.data[++top] = x; 出栈：x = S.data[top–]; 共享栈让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在数组两端，两个栈顶向数组中间延伸。目的：两个栈空间相互调节，更有效地利用存储空间。链栈优点：便于多个栈合理共享存储空间并提高效率、不存在栈满上溢的情况。采用单链表实现，所有操作都是在表头进行。表头是栈顶，表尾是栈底。队列

队列也是一种操作受限的线性表，只允许在表的一端进行插入，另一端进行删除。

循环队列顺序存储：分配一块连续的存储单元存放队列中的元素。循环队列：将顺序队列臆造为一个环状的空间，逻辑上成环。队尾指针Q.rear永远不可能小于队首指针Q.front。操作：初始情况：Q.front = Q.rear = 0; 队首指针进1：Q.front = (Q.front + 1) % MaxSize 队首指针进1：Q.rear = (Q.rear + 1) % MaxSize 队列长度：（Q.front - Q.rear + MaxSize）% MaxSize 链式队列一个带有头指针和尾指针的单链表。头指针始终指向队首结点，尾指针始终指向队尾结点。最好带有头结点，操作更简单。优点：便于多个队列合理共享存储空间并提高效率、不存在栈满上溢的情况。双端队列两端都可以进行入队和出队操作的队列。一般是输入受限或输出受限的双端队列。应用栈的应用括号匹配出现右括号则满足一个最急迫期待的左括号。要注意括号相同类型。表达式中缀表达式转后缀表达式字母按顺序写，符号按优先级低的往后放，去括号。递归递归既要有递归表达式，也要有边界条件。

*队列的应用

层次遍历二叉树用队列实现计算机系统中的应用主机和外部设备速度不匹配——缓冲区资源竞争问题——CPU调度树概念树是n个结点的有限集合。n=0时为空树。任意一棵非空树应满足：有且仅有一个根结点。当n>1时，其余结点可分为m个互不相交的有限集合，这些集合本身又是一棵树称为根结点的子树。度结点的度：一个结点的子结点的个数。树的度：结点的最大度数。分支结点：非终端结点。路径：两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。（树的路径是从上往下的，不能逆转）路径长度路径上所经过的边的个数。树的路径长度是树根到所有结点路径长度的总和。树的高度是树根到所有节点路径长度的最大值。进阶概念二叉树是n个结点的有限集合。（二叉树不同于度为2的树，是有序树，也可以是空树） n=0时为空二叉树。非空二叉树由一个根结点和两个互不相交的左子树和右子树组成。左右子树分别是一个二叉树。满二叉树：高度为h，且含有 2 h − 1 2^h-1 2h−1个结点的二叉树。完全二叉树：一个高度为h、有n个结点的二叉树，当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。二叉排序树：一棵二叉树，或者是空树，或者是左子树上所有结点的关键字都小于根结点的关键字，右子树上所有结点的关键字都大于根结点的关键字。左右子树又各是一棵二叉排序树。平衡二叉树：树上任一结点的左右子树高度差的绝对值不超过的二叉树。平衡因子：结点的左子树和右子树的高度差。可取值：-1，0，1。哈夫曼树：树的结点被赋予某种意义的数值，称为权。从根结点到任意结点的路径长度与该结点的权的乘积，称为该结点带权路径长。树种所有叶结点的带权路径长之和，称为树的带权路径长度（WPL）。带权路径长度最小的二叉树，称为哈夫曼树，也称最优二叉树。二叉树的遍历先序遍历先访问根结点，再依次访问左右子结点。//递归 void preOrder(Node n){ if(n != null){ visit(n); preOrder(n.left); preOrder(n.right); } } 中序遍历先访问左孩子，再访问根结点，最后访问右孩子。//非递归 void inOrder(Node n){ Stack s = new Stack(); Node p = n; while(p || !s.isEmpty){ if(p != null){ s.push(p); p = p.left; }else{ s.pop(p); visit(p); p = p.right; } } } 后序遍历先访问左右孩子结点，最后访问根结点。层次遍历能够根据两种特定的遍历序列唯一确定一棵二叉树。线索二叉树目的：加快查找结点前驱和后继的速度。定义：对二叉树的线索化，实质是遍历一次二叉树，只是在便利的过程中，检查当前结点左右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。原理：充分利用二叉树中大量的空指针；若无左子树，则left指向前驱；若无右子树，则right指向后继。引入左右tag表明当前指针指向的是左右孩子还是前驱后继。树的存储结构双亲表示法顺序存储可以快速查找双亲结点，但查找孩子结点时需要遍历整个结构。孩子表示法孩子兄弟表示法左指针指向第一个孩子结点、右指针指向下一个兄弟优点：灵活、将树、森林转换为二叉树树的遍历先根遍历先访问根结点，后依次访问孩子结点顺序和相应二叉树的先序遍历相同后根遍历先一次访问孩子结点，后访问根结点顺序和相应二叉树的中序遍历相同并查集二叉排序树查找：从根结点开始沿某个分支向下进行比较。插入：若原二叉排序树为空，则直接插入结点。若插入结点的关键字小于根结点的关键字，插入左子树。若插入结点的关键字大于根结点的关键字，插入右子树。递归进行。构造：多次插入。删除：若是叶子结点，直接删除。若只有一棵左子树或右子树，则让孩子代替删除结点的位置。若有两个子树，则让中序遍历的直接后继或前驱代替删除节点的位置。查找效率：BST的平均查找长度取决于树的高度。若是一个倾斜的单支树， f ( n ) = O ( n ) f(n)=O(n) f(n)=O(n) 若是平衡二叉树，平均 f ( n ) = O ( l o g 2 n ) f(n)=O(log_2n) f(n)=O(log2n) 静态查找，二分查找法合适；动态查找，BST合适。平衡二叉树

每当在二叉排序树中插入或删除一个结点，就要检查其插入路径上的结点是否不再平衡。如果不平衡，需要先找到插入路径上离插入结点的最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新平衡。

旋转方法：

RL不平衡，则先右转，再左转。 LR不平衡，则先左转，再右转。

设深度为h的平衡二叉树中含有的最少结点数为 N h N_h Nh，则： N 0 = 0 N_0=0 N0=0， N 1 = 1 N_1=1 N1=1，

【本文地址】

公司简介

联系我们