软考中级之数据库系统工程师笔记总结(二)数据结构与算法

二、数据结构与算法

2.1数据结构

数据结构指数据元素的组织形式。

2.2线性表的顺序存储结构

​ 特点是物理位置上的邻接关系来表示结点的逻辑关系，具有可以随机存取表中的任一结点的，但插入删除不方便

2.3线性表的链式存储结构

​ 用一组任意的存储单元来存放线性表的数据元素，链表中的结点的逻辑次序和物理次序不一定相同。

2.4线性表的插入和删除

2.5栈的顺序存储

采用两个顺序栈共享一个数据空间：（先进后出）

### 2.6队列 只允许在表的一端插入元素（队尾），另一端删除元素（队头）。（先进先出）

2.7子串

子串包含在它的主串中的位置是子串的第一个字符首次出现的位置。

2.8广义表

​ 广义表是线性表的推广,是由零个或多个单元素或子表所组成的有限序列。广义表与线性表的区别在于：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元崇，也可以是有结构的表。

2.9二叉树的性质

二叉树第i层上的结点数目最多为2i-1（i≥1）。 深度为K的二叉树至多有2k-1个结点（k≥1）。 在任意一颗二叉树中，若终端结点的个数为n0，度为2的节点数为n2，则n0=n2+1。 具有n个结点的完全二叉树的深度为

2.10树与二叉树的转换

左孩子不变，其兄弟结点变为左孩子的右孩子；或是将树置保留左孩子结点，其它全删去，然后将各层的兄弟结点连起来。如：

2.11相同遍历

树的前序遍历与二叉树的先序遍历一样；树的后序与二叉树的中序遍历一样。

2.12散列

散列就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值，如此建立的表为散列表，散列表是可以动态创建的。

2.13二分查找

二分查找（折半查找）：要求关键字必须采用顺序存储结构，并且必须按关键字的大小有序排序。

2.14查找二叉树

查找二叉树（二叉排序树）——动态查找表：或者为空树或者满足：

查找树的左右子树各是一颗查找树。 若查找树的左子树非空，则其左子树上各节点的值均小于根结点的值。 若查找树的右子树非空，则其右子树上各节点的值均大于根结点的值。 平衡二叉树：或者是空树，或者是满足：树中任一节点左右子树的深度相差不超过1。结点的平衡度：其右子树的深度减去左子树的深度（因此平衡度只能为1,0，-1）。

2.15有向图中所有顶点的出度数之和

有向图中所有顶点的出度数之和等于入度数之和。

2.16图中边数

在图中，边数等于所有顶点的度数之和的一半。

2.17顶点和边数

2.18长度

C语言中，struct中各成员都占有自己的内存空间，总长度为所有成员的长度之和，而union中的长度等于最长的成员的长度。