数据结构概论之算法的描述和分析[1]

算法

一个算法一般具有下列五个重要特性

有穷性一个算法必须总是在执行有限步之后结束

确定性算法中的每一条指令必须有确切的含义不能产生多义性

可行性算法中的每一条指令必须是切实可行的即原则上是可以通过已经实现的基本运算执行有限次来实现的

输入一个算法有零个或多个输入这些输入取自于特定对象的集合

输出一个算法有一个多个输出这些输出是同输入有某个特定关系的量

描述算法的一些要求和规则

正确性正确一词在含义上大体分为四个层次

程序不含语法错误

程序对几组输入数据能给出满足规格说明要求的结果

程序对精心选择的典型的苛刻而带有刁难性的几组输入数据能给出满足规格说明要求的结果

程序对一切合法的输入数据都能给出满足规格说明要求的结果

可读性算法主要是为了人的阅读其次才是机器的执行可读性有助于人对算法的理解

健壮性当输入数据非法时算法也能适当的作出反应或进行处理而不会产生莫名其妙的结果

效率和低存储量需求一般来说效率指的是算法执行的时间存储量制的是算法执行过程中需要的最大存储空间这两者都与问题的规模有关

其中第 项要求是其它所有要求的基础离开了正确性其它一切问题都谈不上其次算法的效率是一切算法设计者所追寻的目标算法的效率是直接影响算法在实际情况中的表现效率的高低很可能就决定了这个算法是否有实用价值

算法描述语言

因为考虑到大多数同学都已经学过 C 语言在这门课程的教学过程中我们将采用 C 语言作为算法描述语言如果读者想复习以下C语言的基本语法在这里复习

命名规则

任意字母开头由字母数字组成的任意长度的字符串

变量及数组

为简单起见变量在使用前不需声明但每一变量一经使用便有一确定类型不再更改

数组的格式如 C 语言的规定int a[n] 的数组由 a[] 到 a[n]共有 n 项

布尔运算

AND 与运算

OR 或运算

NOT 非运算

CAND 带短路的与运算

COR 带短路的或运算

赋值语句

简单赋值变量名 = 表达式

成组赋值(变量名变量名K)= (表达式表达式K)

结构名 = 结构名

交换赋值变量名 <> 变量名

分支语句

IF (条件)

语句

IF (条件)

语句

ELSE

语句

SWITCH (条件)

CASE 值语句;

CASE 值K语句K;

DEFAULT 语句K+;

ENDC

[] []