数据结构与算法

 第一章

数据源和数据项

数据项：数据结构中讨论的最小单位

数据元素使数据项的集合

 

例如：运动员是一个数据元素它包括姓名、俱乐部名称、出生年月、职务等数据项。

 

算法

算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：

1.有穷性

2.确定性

3.可行性

4.有输入

5.有输出

 

算法设计的原则

1.正确性

2.可读性

3.健壮性

4.高效率与低储存量的需求

 

一个特定算法的“运算工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

假如 ，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作:

T(n) = O(f(n))

称T(n)为算法的（渐进）时间复杂度

冒泡排序的时间复杂度为T(n) = O(n²)

 

算法 = 控制结构 + 原操作（固有数据类型的操作）

算法的执行时间 = 原操作（i）的执行次数*原操作（i）的执行时间

 

从算法中选取一种对于所研究的问题来说是 基本操作 的原操作， 以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则

 

算法的空间复杂度

 S(n) = O(g(n))

表示随着问题规模n的增大，算法运行所需储存量的增长率与g(n)的增长率相同。

 

第二章 线性表

线性机构是一个数据元素的有序(次序)集。

 

1.集合中必存在唯一的一个“第一元素”。

2.集合中必存在唯一的一个“最后元素”。

3.除最后元素在外，均有唯一的后继。

4.除了第一元素之外，均有唯一的前驱。

 

2.1线性表的类型定义

 

2.2线性表类型的实现--顺序映象

 

用一组地址连续的存储单元依次存放线性表中的数据元素

 

2.3线性表类型的实现--链式映象

 

用一组地址任意的存储单元存放线性表中的数据元素 以元素（数据元素的映像）+指针（指示后继元素存储位置的）=节点（表示数据元素）

以“节点的序列”表示线性表-----称作链表

 

2.4一元多项式的表示

 

例一、有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员）现要求一个新的结合A = A U B

 

例二、已知一个非纯集合B，试构造一个纯集合A，使A中包含B中所有值各不相同的元素。

 

第三章 栈和队列（和线性表类似）

3.1 栈的类型定义

 

栈是后进先出的

 

队列是后进后出的

 

 

3.2 栈的应用举例

 数制转换 括号匹配的检验 行编辑程序问题 迷宫求解 表达式求解 实现递归

 

 

在计算机中，表达式可以有三种

不同的标识方法

设 Exp = S1 + OP +S2

则称  OP+S1+S2为表达式的前缀表示法

   称  S1+OP+S2为表达式的中缀表示法

   称  S1+S2+OP为表达式的后缀表示法

可见，它以运算符所在不同位置命名的。

3.3 栈类型的实现

 顺序栈 链栈

 

3.4 队列的类型定义

 

3.5 队列类型的实现

 

 

 

树

 树：

 根：

子树：

层次：从根开始定义，层次数为0的结点是根结点，其字树的根的层次数为1。

父亲：

孩子：

兄弟：同一结点的孩子

树中结点的最大层次数称为树的深度（Depth）或高度。树中结点也有高度，其高度是以该结点为根的树的高度。

结点拥有的子树的数目称为结点的度（Degree）。度为0的结点称为叶子（leaf）或终端结点。度不为0的结点称为非终端结点或分支结点。

 

性质1：树中的结点数等于树的边数加1，也等于所有结点的度数之和加1。

 

树中任意两个结点之间都存在唯一的路径，同时又不会出现环路。

 

树中所有结点最大度数为m的有序树称为m叉树。（二叉树）

 

森林:是m棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。树和森林的概念相近。删去一棵树的根，就得到一个森林。

 

二叉树：每个结点的度均不超过2的有序树

 

性质2 在二叉树的第i层上最多有2ⁱ 个结点

性质3 在二叉树的第i层上最多有2^h+1-1个结点

性质4 对于一棵二叉树T，如果其终端结点数为n₀,度为2的结点数为n_2,,则n₀ =  n₂  + 1

 

 

 

 

满二叉树:高度为k并且有2^k+1-1 个节点的二叉树。

完全二叉树(Complete Binary Tree) ：

         若在一棵树二叉树中，在最下层最右侧起去掉相邻的若干叶子结点，得到的二叉树即为完全二叉树

　　若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。

　　完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

 

 

 

 

 

 

 

 二叉树的储存结构:顺序存储结构和链式存储结构。

 

先序遍历：1访问根节点；2先序遍历左子树；3先序遍历右子树；

中序遍历：1中序遍历左子树；2访问根节点；3中序遍历右子树；

后序遍历：1后序遍历左子树；2后序遍历右子树；3访问根节点；

 

红黑二叉树：

 

 

一般的，红黑树，满足一下性质，即只有满足一下性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。