软件设计师笔记-数据结构

数据结构

数据元素的集合及元素间的相互关系和构造方法。

线性表的存储结构

• 顺序存储
• 链式存储

单链表节点

typedef struct node { int data; struct node *link; 
}NODE, *LinkList; 

双向链表

每个节点有两个指针，分别指出直接前驱和直接后继。

循环链表

尾节点指针指向第一个节点。

静态链表

借助数组来描述线性表的链式存储结构。

栈

• 特点：后进先出
• 初始化栈： InitStack(S)
• 判栈空：StackEmpty(S)
• 入栈：Push(S,x)
• 出栈：Pop(S)
• 读取栈顶元素：Top(S)-----顺序存储+链式存储

队列

• 特点：先进先出，尾入头出
• 初始化队列：InitQueue(Q)
• 判队空：Empty(Q)
• 入队：EnQueue(Q,x)
• 出队：DeQueue(Q)
• 读队头元素：FrontQue(Q)-----顺序存储+链式存储

串

仅由字符构成的有限序列，是取值范围受限的线性表。

数组

定长线性表在维数上的扩张，一般不做插入删除运算。

矩阵

• 特殊矩阵：元素分布有一定的规律（对称矩阵、三角矩阵、对角矩阵）
• 稀疏矩阵：非零元素远少于零元素且分布无规律，用三元组存储(行号，列号，值)

广义表

• 表中有表
• 表头：表中第一个元素
• 表尾：表中除去表头剩下的部分

树

• 递归的，元素之间有明显的层次关系。
• 完全二叉树应采用顺序存储结构，一般二叉树则应采用链式存储结构
• 二 叉 树 的 链 式 存 储 结 构：

  typedef struct BiTnode {int data; struct BiTnode *lchild, *rchild; }BiTnode, *BiTree; 
  

二叉树的遍历

• 先序遍历（先访问根节点）
• 中序遍历（第二访问根节点）
• 后序遍历（最后访问根节点）
• 层序遍历（利用队列、每次出同一层的节点时进他们的子节点层）

线索二叉树

加上线索（直接前驱和直接后继）的二叉树。

最优二叉树（哈夫曼树）

一类带权路径长度最短的树。

树的存储结构

• 双亲表示法：顺序存储
• 孩子表示：链式存储
• 孩子兄弟表示：链式存储，两个指针分别为第一个孩子和下一个兄弟

图

一个节点的前驱节点和后继节点数目没有任何限制。

图的表示

• G=(V，E)；
• V：顶点的集合；

网

边带权值的图。

图的相关概念

图的存储结构

• 邻接矩阵表示法
• 邻接链表表示法

图的遍历

• 深度优先搜索
• 广度优先搜索

生成树

极小连通子图，针对连通图。

最小生成树（权值和最小的生成树）算法

• 普尼姆算法：在相邻边的基础上求最小，与边数无关，适于边稠密的网。
• 克鲁斯科尔算法：在不构成环的基础上找最小边直至连通，与顶点数无关，适于边稀疏的网。

AOV 网

有向图中顶点表示活动，有向边表示活动间的优先关系。

拓扑排序

将 AOV 网中所有顶点按优先顺序排成一个线性序列的过程。

AOE 网

有向图中有向边表示活动，边上的权值表示该活动持续的时间。

关键路径

从源点到汇点的路径中长度最长的。

最短路径

从源点到其余各顶点的最短路径-----迪杰斯克拉算法。

平均查找长度

关键字和给定值进行过比较的记录个数的平均值。

静态查找方法

• 顺序查找
• 折半查找
• 分块查找

动态查找

表结构本身在查找过程中是动态生成的。

二叉排序树

左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节
点的值。

平衡二叉树（AVL 树）

左子树和右子树高度之差的绝对值不超过1 。

B_树（m 阶）

每个节点子树个数<=m，根节点子树个数=0 或>=2，其他节点子树个数=0
或>=m/2。

哈希表

• 通过哈希函数（以记录的关键字为自变量）得到记录的存储地址
• 定长按一定函数规律存放数据
• 哈希地址+关键字

哈希表的重点

• 构造哈希函数：直接定址法，数字分析法，平方取中法，折叠法，随机
  数法，除留余数法
  解决冲突：开放定址法，链地址法，再哈希法

简单排序

• 时间复杂度 O($n^2$)，空间复杂度 O($1$)）
• 直接插入排序：插入第 i 个时，前 i-1 个已经排序好
• 冒泡排序：相邻两个比较排序，每次循环确定一个极值
• 简单选择排序：第 i个依次与后面每个元素比较排序，每次循环确定一个极值，不稳定

高端内部排序

• 希尔排序：先将整个序列分割成若干序列分别进行直接插入排序，再对整个序列进行一次直接插入排序，不稳定
• 快速排序：将整个记录分割成独立的两部分，两个指针分别指向对应部分的两端，往中间移动比较排序，递归，不稳定
• 堆排序：建立初始堆输出并删除堆顶关键字，再建立新堆得到新的关键字依次输出，不稳定
• 归并排序：将若干个有序序列合并为新的有序序列
• 基数排序：按组成关键字的各个数位的值进行排序