【计算机专转本系列–理论】算法和数据结构

章节目录

一、算法

程序=算法+数据结构 （由科学家尼克劳斯·沃斯提出）

2.算法的设计一般采用 由粗到细，由抽象到具体的逐步求精 的方法。

3.算法的必要满足条件： 确定性，有穷性，可行性，0个或多个输入，至少1个或多个输出 。

4.关于算法需要考虑的方面：算法设计，算法表示，算法分析。

5.算法与程序的区别

• 算法是解决问题的方法。
• 程序是算法的具体代码实现
• 算法是程序设计的核心，算法的好坏直接决定了程序的效率。
• 算法与程序是相应的，但不是一一对应的。
• 程序可以不用满足算法的有穷性。

6.算法的表示

自然语言 （缺点：容易产生二义性）

2.流程图

3.程序设计语言

伪代码（PDL）

7.评价算法的标准

正确性 ：评价一个算法优劣的最重要的标准。

2.算法的复杂度

• 时间复杂度 ：执行算法所需要的计算工作量。
• 空间复杂度 ：执行算法所需要的内存空间。

可读性

健壮性

二、数据结构

1.基本概念

1.数据元素： 数据元素 是 数据 的基本单位。

2.数据对象：数据对象是性质相同的数据元素的集合。

3.数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。

4.常见的逻辑结构（考试考到了，选错了呜呜呜）：

• 集合结构

• 线性结构

• 树形结构

• 网状结构

  也可以分为 线性 结构（线性表，栈和队列，串，一维数组）和 非线性 结构（集合，树形，网状）。

  5.常见的存储结构

• 顺序存 储结构：把逻辑上 相邻 的数据元素，存储在 物理位置也相邻 的存储单元里。

• 链式 存储结构：各个数据元素存储位置随意，不要求逻辑上相邻的数据元素在物理位置上相邻。

2.数据结构

1.没有前继结点的称为“ 根结点 ”。

2.没有后继结点的称为“ 叶子结点 ”。

3.没有根结点或叶子结点的数据结构一定是非线性结构。

4.有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。

3.顺序表的插入和删除操作

1.顺序表的 插入操作

• 最好情况：插入的是尾元素，移动次数为 0 。
• 最坏情况：插入的是第一个元素，移动次数为 n 。
• 平均情况：在i位置插入新元素，移动次数为 n-i+1 。
• 算法的平均时间复杂度为O(n)。

2.顺序表的 删除操作

• 最好情况：删除的是尾元素，移动次数为 0 。
• 最坏情况：删除的是第一个元素，移动次数为 n-1 。
• 平均情况：在i位置删除一个元素，移动次数为 n-i 。
• 算法的平均时间复杂度为O(n)。

4.栈和队列

1.栈：先进后出

2.队列：先进先出

循环队列 的相关操作

• 初始状态： Q.front=Q.rear
• 队首指针进1（出队）： Q.front=（Q.front+1）%Maxsize
• 队尾指针进1（入队）： Q.rear=（Q.rear+1）%Maxsize
• 队列长度： （Q.rear-Q.front+Maxsize）%Maxsize
• 队满： （Q.rear+1）%Maxsize == Q.front
• 队空： Q.front == Q.rear

5.二叉树

1.性质

• 在二叉树的k层上，最多有 2^(k-1) 个结点。

• 在深度为m的二叉树最多有2^m-1个结点。

• 在任意一颗二叉树中，度为0的结点总是比度为2的结点多一个。 n0=n2+1 。

  还有结点数为n，其深度不小于（log2底n）+1。

2.前序遍历：根-左-右

中序遍历：左-根-右

后序遍历：左-右-根

层次遍历：按层来，由左向右，一层层来。

题目类型一般两种。(题目找的不是太好，主要是看两个的差别)

第一种：

1.某二叉树的前序遍历序列为ABCDE,中序遍历序列为CBADE,则后序遍历序列为

2.某二叉树的后序遍历序列为ABCDE,中序遍历序列为CBADE,则前序遍历序列为

第二种：

按照上图中：

前序遍历：ABDCEF

中序遍历：DBAECF

后序遍历：DBEFCA

层次遍历：ABCDEF