数据结构

什么是数据结构?

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

通常有以下四类基本结构:

• 集合
• 线性结构
• 树形结构
• 图状结构或网状结构

数据的存储结构:

• 顺序存储结构
• 链式存储结构

高级程序语言中的数据类型可以分为两类:
一类是非结构的原子类型. 原子类型的值是不可分解的,例如C语言中的基本类型(整型,实型,字符型,枚举类型)指针类型和空类型.
另一类是结构类型.结构类型的值是由若干成分按某种结构组成的,因此可以分解的,并且它的成分可以是结构的,也可以是非结构的.

算法和算法分析
算法是对特定问题求解步骤的一种描述,他是指令的有限序列,其中每一条指令表示一个或多个操作;此外一个算法还具有下列5个重要特性:

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

算法的时间复杂度
T(n) = O(f(n))
算法的空间复杂度
S(n) = O(f(n))

线性表

线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,还可以进行插入和删除
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素.
线性表的插入和删除的时间复杂度为O(n)

线性链表 (单链表)

除了存储数据本身信息外,还需存储一个指示其直接后继的信息(即直接后继的存储位置),这种存储映像称作 结点,包含两个域,数据域和指针域

单向循环链表

表中最后一个结点的指针域指向头结点,整个链表形成一个环

双向链表

包含两个指针域,其一指向直接后继,另一指向直接前趋.

双向循环链表 (略)

栈和队列

栈是仅在表尾进行插入和删除操作的线性表,队列是只允许在表的一段进行插入元素,在另一端进行删除元素的线性表
栈 (后进先出)
队列(先进先出)

树和二叉树

树是n个结点的有限集.树的结点包含一个数据元素及若干指向其子树的分支.结点拥有的子树数成为结点的度.
森林是m(m>=0)棵互不相交的树的集合.

遍历二叉树

• 先序遍历
  1.访问根节点;
  2.先序遍历左子树;
  3.先序遍历有子树.
• 中序遍历
  1.中序遍历左子树;
  2.访问根节点;
  3.中序遍历右子树.
• 后序遍历
  1.后序遍历左子树;
  2.后序遍历有字数;
  3.访问根结点.

赫夫曼树

树的带权路径长度为树中所有叶子节点的带权路径长度之和.n个叶子节点分别带权,其中带权路径长度最小的二叉树称作最优二叉树或赫夫曼树

二叉排序树

• 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
• 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
• 它的左右子树也分别为二叉排序树.

平衡二叉树

它的左子树和右子树都是平衡二叉树,且左子树和右子树的的深度之差的绝对值不超过1.

哈希表

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的"像"作为记录在表中的存储位置,这种表便称为哈希表,所得存储位置称为哈希地址

哈希函数的构造方法

• 直接定址法
• 数字分析法
• 平方取中法
• 折叠法
• 除留取余法
• 随机数法

处理冲突的方法

• 开放定址法
• 再哈希法
• 链地址法
• 建立一个公共溢出区

排序

• 插入排序
  直接插入排序 是一种最简单的排序方法,它的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的,记录数增1的有序表

• 交换排序

• 选择排序

• 归并排序

• 计数排序

• 基数排序

• 希尔排序

• 堆排序