算法与数据结构_算法与程序设计需求分析

算法与数据结构

1. 数据结构

1.1 基本概念

• 数据是计算机加工处理的对象.
• 数据一般分为:数值数据和非数值数据.
• 数值数据包括整数,实数,复数等,主要用于科学与工程计算领域.
• 非数值数据包括文字,图形,语音和表格等,主要用于管理领域.
• 数据也可以是由某些成分数据而构成,而组成数据的成分数据称为数据元素(数据项)
• 数据元素为不可再分的.
• 数据元素是简单类型的 整型 浮点型 字符型等
• 数据可以是结构体类型.
• 数据结构(data structure)是数据组织形式和与之绑定的相关算法.
• 数据的组织形式的描述:对数据之间逻辑关系的描述(数据的逻辑结构),
  对数据在计算机内存中存储状态的描述(数据的存储结构).

1.2 数据的逻辑结构

数据之间的逻辑关系,可用二元组表示:
	DS={D,R}
	D为数据实体的集合,R为数据关系的集合.
根据数据之间逻辑关系所具有的不同特征,可分为四种基本逻辑结构:
	1. 集合结构
		在集合结构中,数据间没有先后顺序.关系:属于同一集合
	2. 线性结构
		在线性结构中,数据是一个有序序列,第一个元素没有前驱,
		最后一个元素没有后继,其它元素都只有一个前驱和一个后继.
	3. 树状结构
		在树状结构中,有一个特殊数据称为根,它没有前驱只有后继,而其它数据均只有一个前驱,
		但后继的数目不限.对于非根数据都有一条从根到该数据的路径.
	4. 图状结构
		图中的每一个元素的前驱和后继数目不限.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.3 数据的存储结构

数据需要存储在计算机内存中,数据的存储结构是数据在计算机内的组织形式.
计算机内存是由有限个存储单元(按字节码编址)组成的一个连续存储空间
顺序存储法和链表存储法是最基本的存储表示方法.
顺序存储法需要一块连续的存储空间,把在逻辑上相关的数据依次存储到这块连续的存储区域中.
链表存储法的存储空间不一定连续的,链中结点存放由数据信息和该数据的后继所存放的结点地址.
还有散列存储法等
1
2
3
4
5
6

1.4 数据结构的运算

常见运算:
(1). 创建运算:创建一个数据结构
(2). 清除运算:删除数据结构中的所有元素
(3). 插入运算:在数据结构中插入一个新元素	
(4). 删除运算:将数据结构中某个指定元素删除	
(5). 搜索运算:在数据结构中搜索满足一定条件的元素	
(6). 更新运算:修改数据结构中某个指定元素的值	
(7). 访问运算:访问数据结构中某个元素	
(8). 遍历运算:按某种次序访问数据结构中每个元素,使得每个元素恰好被访问一次.
1
2
3
4
5
6
7
8
9

2. 抽象数据类型

	数据结构可视为一个抽象数据类型,所谓抽象数据类型(abstract data type,ADT),
其实就是一种自定义的数据类型,它包含数据以及对数据的相关运算.
1
2

3. 算法与算法分析

3.1 算法

算法(algorithm)是对实际问题的一种求解方法.
算法是对实际问题所给出的求解步骤的描述,是一个有限的求解指令序列.
算法的应有特征:
	(1). 输入:算法有零个或多个输入
	(2). 输出:算法至少产生一个输出
	(3). 确定性:算法的每一条指令都有确切的定义,没有二义性
	(4). 可行性:算法的每一条指令,都可以通过已经实现的基本运算执行有限次来实现
	(5). 有穷性:算法必须在执行有限步之后而终止
1
2
3
4
5
6
7
8

3.2 算法的描述

	描述一个算法有多种方法:自然语言,伪代码语言,流程图,程序语言
	使用自然语言,数字和数学表达式来说明运算步骤.
	伪代码语言是一种介于自然语言和计算机程序语言之间的描述形式.利用伪代码语言描述算法比自
然语言更准确,简明,又比计算机程序语言更灵活,没有了程序语言中的严格的语法约束.
	流程图(flow diagram)是用一组几何图形表示各种类型的操作,在图形上用简明的文字和符号表
示具体的操作,用带有箭头的线段表示操作的先后顺序.
	程序语言:算法也可以直接用可读性好的高级语言来表示 Basic C C++语言等
1
2
3
4
5
6
7

3.3 算法的性能

衡量一个算法的性能,有一下几个主要标准:
(1) 正确性:算法的执行结果应该满足预期规定的功能和性能要求
(2) 健壮性:当输入不合法数据时,应能做适当处理,不至于引起严重后果
(3) 效率:存储空间的开销尽可能的少,运行时间尽可能的短.
(4) 简明性:算法应该思路清晰,层次分明,简单明了,易读易懂.
(5) 复用性:可被移植或再利用.
1
2
3
4
5
6

3.4 算法的时间复杂度

一个程序的时间复杂度是程序从开始运行到结束所需的时间.
1

3.5 渐进时间复杂度

描述渐进时间复杂度的函数f(n)通常取:log(n),n,nlog(n),n^2,2^n等
1

3.6 最好,最坏和平均时间复杂度

对于某些算法,即使问题规模相同,如果输入数据不同,算法所需的时间开销也会不同.
1

3.7 算法的空间复杂度

一个程序的空间复杂度是指程序从开始运行到结束所需的存储空间.
程序运行所需空间分为两部分:
固定部分:与问题的规模无关.主要包括程序代码,常量,简单变量,定长成分的结构变量所占的空间.
可变部分:与问题的规模有关.包括数据元素所占的空间,以及算法执行所需的额外空间等.
1
2
3
4

4. 程序设计

4.1 程序

	程序是由符合程序语言语法规则的指令所组成.而程序设计的目的就是通过程序代码的撰写与执行,
	实现程序的需求.
1
2

4.2 应用程序设计步骤

一个应用程序设计大致分为以下5步:
(1) 需求分析:了解程序所需要解决的问题是什么,有哪些输入及输出等.
(2) 设计规划:根据需求选择某种数据结构和算法,给出解决问题的初步方案.
(3) 分析讨论:思考其它可能的数据结构和算法,从而确定解决问题的最合适方案.
(4) 编写程序:根据所确定的方法,撰写程序代码.
(5) 测试检测:确认程序的输出是否符合需求,需要单步的执行程序并进行许多相关测试.
1
2
3
4
5
6

4.3 结构化程序设计

	结构化程序设计是以模块化设计为中心,将带设计的程序划分为若干个相互独立的模块,使完成每个模块的工作变得单纯而明确.
	实现结构化程序设计的具体方法如下:
	(1) 自顶向下,逐步求精.
	(2) 模块化设计,结构化编码.
	自顶向下,逐步求精就是先把问题分解成相对独立的子问题,再以同样的方式对每一个子问题逐层
细分,步步深入,直到整个问题可以用程序设计语言明确的描述出来为止.从而有效的将一个复杂的程序
设计任务分解成许多易于控制和处理的子任务,便于开发和维护.
	模块化设计就是将分解成的每个子任务,看成是一个模块,各模块之间尽量做到互相独立,这样在
设计其中一个模块时,就不会受到其它模块的干扰.模块的独立性,使得可以充分利用现有的模块作积
木式的扩展.
	结构化编码就是只用顺序结构,选择结构和循环结构这三种基本结构,以及他们的组合与嵌套来编
写程序代码.使程序结构清晰,便于修改和维护.
1
2
3
4
5
6
7
8
9
10
11
12

4.4 数据结构,算法与程序设计之间关系

算法依附于数据结构,不同的数据结构会产生不同的算法,而不同算法会编写出不同的程序.
	程序 = 数据结构 + 算法 ;
研究数据结构与算法的目的,就是为了能撰写出效率高,可读性好,易于实现与复用的程序.
1
2
3

写于2020-10-21