本文共 3469 字，大约阅读时间需要 11 分钟。

一、 数据结构

1. 数据（data） 是信息的载体。

   可以将数据分为两大类：一类是整数、实数等数值数据；另一类是文字、声音、图形和图像等非数值数据。

2. 数据元素（dataelement） 是数据的基本单位

   构成数据元素的不可分割的最小单位称为数据项（dataitem）。
   数据元素具有广泛的含义，一般来说，能独立、完整地描述问题世界的一切实体都是数据元素。

3. 数据结构（datastructure） 是指相互之间存在一定关系的数据元素的集合

   按照视点的不同，数据结构分为逻辑结构和存储结构。

   （1）逻辑结构

   数据的逻辑结构（logicalstructure）是指数据元素之间逻辑关系的整体，是从实际问题抽象出的数据模型，
   在形式上可定义为一个二元组：Data＿Structure=（D，R）其中，D是数据元素的有限集合，R是D上关系的集合。

   根据数据元素之间逻辑关系的不同，数据结构分为四类：

   ① 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；
   ② 线性结构：数据元素之间存在着一对一的线性关系；
   ③ 树结构：数据元素之间存在着一对多的层次关系；
   ④ 图结构：数据元素之间存在着多对多的任意关系。
   树结构和图结构也称为非线性结构。

   通常用逻辑关系图来描述数据的逻辑结构，其描述方法是：

   将每一个数据元素看做一个结点，用圆圈表示，元素之间的逻辑关系用结点之间的连线表示；如果强调关系的方向性，则用带箭头的连线表示关系。

   （2）存储结构

   数据的存储结构（storagestructure）又称为物理结构，是数据及其逻辑结构在计算机中的表示（也称映像）
   换言之，存储结构除了存储数据元素之外，必须隐式或显式地存储数据元素之间的逻辑关系。

   通常有两种存储结构：顺序存储结构和链接存储结构。

   顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
   链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。

二、抽象数据类型

1. 数据类型

   数据类型（datatype）是一组值的集合以及定义于这个值集上的一组操作的总称。
   数据类型规定了该类型数据的取值范围以及能够执行的操作。

   例如，C语言中整型变量的取值范围是机器所能表示的最小负整数和最大正整数之间的任何一个整数，允许执行的操作有算术运算（+、-、*、/、%）、关系运算（＜、＜=、＞、＞=、==、！=）和逻辑运算（&&、‖、！）等。

2. 抽象

   所谓抽象（abstract），就是抽出问题的本质特征而忽略非本质的细节，是对具体事物的一个概括。

   无论在数学领域还是程序设计领域，抽象的能力都源于这样一个事实：

   一旦一个抽象的问题得到解决，则很多同类的具体问题便可迎刃而解。抽象还可以实现封装和信息隐藏

3. 抽象数据类型

   抽象数据类型（AbstractDataType，ADT）是一个数据结构以及定义在该结构上的一组操作的总称。

   ADT可理解为对数据类型的进一步抽象，数据类型和ADT的区别仅在于：

   数据类型指的是高级程序设计语言支持的基本数据类型，而ADT指的是自定义的数据类型。

   一个ADT的定义不涉及它的实现细节，在形式上可繁可简，本书对ADT的定义包括抽象数据类型名、数据元素之间逻辑关系的定义、每种基本操作的接口（操作的名称和该操作的前置条件、输入、功能、输出、后置条件的定义），形式如下：

   形式如下：

ADT 抽象数据类型名Data	数据元素之间的逻辑关系的定义Operation操作1	前置条件： 执行此操作前数据所必须的状态	输入： 执行此操作所需要的输入	功能： 该操作将完成的功能	输出： 执行该操作后产生的输出	后置条件：执行该操作后数据的状态	操作2	...操作n 	...endADT

三、什么是算法

算法必须满足下列五个重要特性：

（1）输入： 一个算法有零或多个输入（即算法可以没有输入），这些输入通常取自某个特定的对象集合。 （2）输出： 一个算法有一或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。 （3）有穷性： 一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。 （4）确定性： 算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 （5）可行性： 算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

程序（program）是对一个算法使用某种程序设计语言的具体实现，原则上，算法可以用任何一种程序设计语言实现。

算法的有穷性意味着不是所有的计算机程序都是算法。

四、什么是“好”算法

一个“好”算法首先要满足算法的五个重要特性，此外还要具备下列特性：

（1）正确性：指算法能满足具体问题的需求，即对于任何合法的输入，算法都会得出正确的结果。

（2）健壮性：指算法对非法输入的抵抗能力，即对于错误的输入，算法应能识别并做出处理，而不是产生错误动作或陷入瘫痪。

（3）可理解性：指算法容易理解和实现。算法首先是为了人的阅读和交流，其次是为了程序实现，因此，算法要易于人的理解、易于转换为程序。晦涩难懂的算法可能隐藏一些不易发现的逻辑错误。

（4）抽象分级：算法一旦创建，必须由人来阅读、理解、使用和修改它们。而研究发现，对大多数人来说，人的认识限度是7±2。如果算法涉及的想法太多，人就会糊涂，因此，必须用抽象分级来组织算法表达的思想。换言之，算法中的每一个逻辑步骤可以是一条简单的指令，也可以是一个模块，通过模块调用完成相应功能。每个模块表示一种抽象，模块的内部描述了怎样实现抽象，而模块的名称描述了模块的功能。

（5）高效性：算法的效率包括时间效率和空间效率，时间效率显示了算法运行得有多快；而空间效率则显示了算法需要多少额外的存储空间。不言而喻，一个“好”算法应该具有较短的执行时间并占用较少的辅助空间。

五、算法描述方法

常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。

1. 自然语言

   用自然语言描述算法，最大的优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长。
   欧几里得算法用自然语言描述如下：
   步骤1：将m除以n得到余数r；
   步骤2：若r等于0，则n为最大公约数，算法结束，否则执行步骤3；
   步骤3：将n的值放在m中，将r的值放在n中，重新执行步骤1。

2. 流程图

   用流程图描述算法，优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。
   欧几里得算法用流程图描述如图1-16所示。
   

3. 程序设计语言

   用程序设计语言描述的算法能由计算机直接执行，而缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，

   欧几里得算法用C语言书写的程序如下：

#include 
   
    int CommonFactor(int m, int n){
   	int r = m % n;	while( r != 0){
   		m = n;		n = r;		r = m % n;	}	return}int main(void){
   	printf("最大公约数是：%d \n", CommonFactor(35, 25));	return 0;}
   

4. 伪代码
   伪代码（pseudo-code）是介于自然语言和程序设计语言之间的一种方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。
   至于算法中自然语言的成分有多少，取决于算法的抽象级别。抽象级别高的伪代码自然语言多一些，抽象级别低的伪代码程序设计语言的语句多一些。

算法：CommonFactor（m，n）输入：两个自然数m和n输出：m和n的最大公约数1.		r=m% n；2.		循环直到r等于02.1			m=n；2.2			n=r；2.3			r=m% n；3.		输出n；

为了便于描述算法，对C语言做了若干扩充和修改，

具体如下： （1）用函数来描述算法，并且不用在主函数中调用函数； （2）增加了C++语言的引用参数传递方式，在形参表中以符号“&”开始的参数即为引用参数； （3）当算法出现异常时，使用语句“exit（-1）；”结束算法的执行并将状态码-1返回； （4）不用包含头文件，输入/输出语句可以省略格式控制符； （5）局部变量可以不声明； （6）用符号“←→”表示交换两个变量的值。

转载地址：https://ciellee.blog.csdn.net/article/details/105111371 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！