算法与数据结构

1. 数据结构

1.1 基本概念

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

1.2 数据的逻辑结构

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

1.3 数据的存储结构

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

1.4 数据结构的运算

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

2. 抽象数据类型

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

3. 算法与算法分析

3.1 算法

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

3.2 算法的描述

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

3.3 算法的性能

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

3.4 算法的时间复杂度

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

3.5 渐进时间复杂度

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

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

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

3.7 算法的空间复杂度

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

4. 程序设计

4.1 程序

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

4.2 应用程序设计步骤

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

4.3 结构化程序设计

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

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

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

写于2020-10-21