第五章 数据结构与算法

5.1.3 算法描述

1 描述一个算法可以采用文字描述，也可以采用传统流程图、N-S图或PAD图。

2 算法特性：有穷性、确定性、可行性、输入、输出。

3 算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如流程图、Pascal语言、C语言、伪代码或决策表。

5.1.4 算法评价

4一个“好”的算法应满足正确性、可读性、健壮性、效率和低存储量需求。

5 算法评价：时间复杂度和空间复杂度。

5.1.5 算法与数据结构的关系

5.2 线性表

5.2.1 线性表的定义和逻辑结构

6 线性表表示：A=（a1 ，a2，…，ai-1，ai，ai+1，…， an）

linear_list=（A，R）

7 线性表的抽象数据类型包括数据对象和数据关系2部分。

5.2.2 线性表的顺序存储结构

8 线性表的存储结构有顺序、链接、散列。

5.2.3 线性表的链式存储结构

5.3 栈和队列

5.3.1 栈的定义和实现

9 栈的主要操作是初始化、插入、删除、判断是否空、读取栈顶结点值。

5.3.2 表达式求值

10 表达式是由操作数（operand）、运算符（operator）、界限符（delimiter）组成。

11 表达式一般分为中缀表达式和后缀表达式。

5.3.3 队列

12 队列分为链队列和循环队列。

5.4 数组和广义表

5.4.1 数组

13 数组一般采用顺序存储结构表示，多维数组的顺序存储有两种形式：以列序为主序、以行序为主序。

14 行优先顺序又称为低下标优先或左下标优先于右下标。Basic、Pascal、C都是采用行优先顺序。

5.4.2 广义表的定义和存储结构

15 广义表有两种结构的结点：表结点，表示列表；原子结点，表示原子。表结点可以由标志域、指示表头的指针域、指示表尾的指针域，原子结点由标志域和值域组成。

5.5 树和二叉树

5.5.1 树的定义

16 树的表示方法：常用方法（树型）、括号、嵌套集合、凹入。

5.5.2 树的存储结构

17 常用的树存储结构主要有三种：双亲表示法、孩子表示法、孩子兄弟表示法。

5.5.3 树的遍历

18 树的遍历方式分为三种：前序遍历、后序遍历、层次遍历。

19 如下图进行三种遍历的结果：前序遍历—ABCEFHIGD;后序遍历—BEHIFGCDA;层次遍历—ABCDEFGHI。

5.6 图

5.6.1 图的定义和术语

5.6.2 图的存储结构

20 邻接矩阵表示法的空间复杂度为S（n）=O（n²）。

5.6.3 图的遍历

21 图的遍历方法深度优先遍历、广度优先遍历。