软件设计师必考精华 – 数据结构与算法

目录

数据结构与算法

1、线性表

2、 队列、栈、堆

3、 树

4、图

5、算法

6、字符串

数据结构与算法

1、线性表

线性表分为：

• 顺序存储：可以随机访问任何元素（因为有数组下标），查询效率高，但是增删慢（因为数组的物理结构，必须遍历）

• 链式存储：查找慢（链表结构，指针按顺序指向），增删快（直接修改指针指向）

包含n个元素的有序线性表，在等概率情况下，删除一个元素，平均需要移动(n-1)/2个元素，如果用单链表存储，平均需要移动0个元素

1.1 顺序存储

通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系，因为逻辑相对位置与物理相对位置一致

特点：逻辑相邻的数据元素，物理结构必相邻。

• 数组，一段连续的地址空间，一维数组是线性结构，多维数组是非线性结构。

• 稀疏矩阵：0元素的个数远多于非0元素，并且非0元素分布没有规律。可用三元组或者十字链表来表示。

  三元组表示（行、列、值）

  常见系数矩阵：

  上三角矩阵：当(i>j时,矩阵元素a{ij}=0)

  矩阵元素对应一维数组下标：

  下三角矩阵：当(i<j时,矩阵元素a{ij}=0)

  矩阵元素对应一维数组下标：

  三角矩阵：

矩阵元素对应一维数组下标：

1.2 链式存储

链表动态分配节点，通过指针，将各个节点按逻辑顺序连接。

用循环单链表

• 表示队列，入队操作需要遍历，而出队操作不需要遍历链表（单链表只能向后遍历，无法逆序遍历，每删除一个元素，队头移动，每添加一个元素队尾移动）

• 表示栈，头指针为栈顶指针，则入栈出栈都不需要遍历（指针只对栈顶操作元素）

1.3 哈希表

线性探测法：mod模位运算，若冲突，放入相邻的下一个元素；若关键字小，则模位为关键字 3mod11 = 3

通过一个已记录的关键字为自变量得到该记录的存储地址

冲突：关键字不同元素被映射到了相同的位置：p的值一般为不大于n且最接近n的质数

哈希表又称散列表，根据关键码值（Key Value）来访问元素

查找：

• 顺序查找：平均长度(n+1)/2，时间复杂度O(n)

• 二分查找：要求必须是顺序存储且是有序排列。最大查找长度[log2(n+1)]，时间复杂度O(log(n))

2、 队列、栈、堆

2.1 队列

先进先出，入队列为队尾，出队列为队头

队列的存储

问题：当执行若干次，front会超过度列长度MAXSIZE，会出现假溢出，可用循环队列解决。

循环队列

入队操作：rear = rear + 1 mod MAXSIZE

出队操作：Front = Front + 1 mod MAXSIZE

循环队列的长度：(Q.rear-Q.front+M)%M（M为队列的容量）

双端队列：要求元素进出必须从同一端口，这就使得双端队列具有了栈的特点，此时元素满足先进后出

优先队列通常采用堆排序数据结构实现

2.2 栈

递归调用用到的是栈存储

先进后出

2.3 堆

判断小根堆，K<= K且 K<= K/strong>

3、 树

常见遍历方法：

• 先序（根左右）

• 后序遍历（左右跟）

• 层次遍历

3.1 二叉树重要特性

• 二叉树第i层最多有 2i-1个节点

• 深度为K的二叉树，最多2k-1个节点

• 完全二叉树（每个节点都是满状态，有1根2叶子）的深度/p>

• n个节点的二叉树形态，/p>

3.2 二叉树的遍历

• 先序：根左右

• 中序：左跟右

• 后序：左右跟

3.3 二叉排序树

• 左子树不为空，左子树所有节点值小于根节点

• 右子树不为空，右子树所有节点值大于根节点

• 从左到右排列同层次节点，左右子树分别是二叉排序树，节点的关键字码呈递增序列

3.4 哈夫曼树（最优二叉树）带权的概念

• 带权值路径最短的树

• 树中不存在只有一个子树的结点

• 权值越大的叶子离根结点越近

• 树中的结点总数一定为奇数

文档压缩问题

• 先画出哈夫曼树，根据带权路径算出经过哈夫曼树优化后的加权平均编码长度

• 判断文档包含的字符，如若文档包含5个字符，则 22 < 5 < 23，求得表示5个字符至少3位编码

• 文档压缩比 = 3 – 平均编码长度 / 3

3.5 树转二叉树

兄弟相连，长兄为父（留最左的左子树），孩子靠左

4、图

• 无向图：最多n(n-1)/2条边

  • 无向连通图任意两点都有路径，但不一定都有边

  • 任意点出发可以遍历所有点

  • 邻接矩阵是对称矩阵，只有0和1

  • 存在<v1,v2>则一定有<v2,v1>

• 有向图：

• 若为强连通图的条件是：任意两点之间有路径

• 最多n(n-1)条边

表示有向图

用邻接矩阵存储有向图，图中每一条弧对应矩阵一个非零元素，一共有e条弧，所以一共e个非零元素。

图的遍历：从某一个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且仅访问一次的过程，所以回路不影响遍历，访问是沿着某条搜索路径，并不是任意的

• 深度优先探索：先跟序，可以用栈存储

• 广度优先探索：按层次，可以用队列存储

邻接矩阵的时间复杂度是O(n2)，使用邻接表的时间复杂度是O(n+e)

例题：

深度优先遍历：234（深度遍历，v1-v2，下一个遍历的结点，一定是有v2指向的v4或v5）

广度优先遍历：13（广度遍历，v1下一个访问的一定是邻接顶点v2或v3，这2个顶点访问结束后，才能往后进行遍历）

最小生成树：

• 普利姆算法：O(n2)，只和顶点有关

• 库鲁斯卡尔算法：O(elog2e)，只和边有关

5、算法

渐进分析的表达式序列大小：

背包问题最优解模块方程：

分支—界限算法的策略，使用广度优先，常用于解决组合优化问题

归纳法：从测试所暴露的问题出发，收集所有正确或不正确的数据，分析他们的关系，提出假想的错误原因，用数据来证明和反驳，从而找到错误，由较大范围，逐步缩小到所需的特定范围。

演绎法：从普遍性结论或一般性事理推导出个别性结论的论证方法

例题：

15、Ow)、16.67、Onlogn+w) = Onlogn) (因为Θ(nlgn)>Θ(n))

6、字符串

• 字符串长度是指串中所含字符的个数 = 字符 + 数字 + 空格数

• 空串是不含任何字符的串

• 包含任意空格字符的串是空格串

• 字符串是线性结构

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34233 人正在系统学习中

来源：WideAwaker