第一章-算法描述概要

《第一章-算法描述概要》由会员分享，可在线阅读，更多相关《第一章-算法描述概要（39页珍藏版）》请在金锄头文库上搜索。

1、1,算法的描述 选择算法描述语言的准则: 该语言应该具有描述数据结构和算法的基本功能； 该语言应该尽可能地简捷，以便于掌握、理解； 使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。 “类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。,2,1. 预定义常量及类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 数据元素被约定为ElemType 类型，用户需要根据具体情况，自行定义该数据类型。,3,2

2、. 算法描述为以下的函数形式： 函数类型 函数名（函数参数表） /算法说明 语句序列； /函数名 为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。 为便于描述算法，除值调用方式外，增加了C+语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。,4,在算法描述中可以使用的赋值语句形式有： 简单赋值 变量名=表达式； 串联赋值 变量名1=变量名2=.=变量名n= 达式； 成组赋值 （变量名1，.，变量名n）=（表达

3、式1，.，表达式n）； 结构赋值 结构名1 = 结构名2； 结构名 =（值1，值2，.，值n）； 条件赋值 变量名 = 条件表达式 ? 表达式1：表达式2； 交换赋值 变量名1 变量名2；,5,在算法描述中可以使用的选择结构语句形式有： 条件语句1 if （表达式） 语句； 条件语句2 if （表达式） 语句； else 语句； 开关语句1 switch （表达式） case 值1：语句序列1；break； case 值2：语句序列2；break； . case 值n：语句序列n；break； default：语句序列n+1； ,6,开关语句2 switch case 条件1：语句序列1；br

4、eak； case 条件2：语句序列2；break； . case 条件n：语句序列n；break； default：语句序列n+1； ,7,在算法描述中可以使用的循环结构语句形式有： for循环语句 for （表达式1；循环条件表达式；表达式2） 语句； while循环语句 while （循环条件表达式） 语句； do-while循环语句 do 语句序列； while （循环条件表达式）；,8,6. 在描述算法中可以使用的结束语句形式有： 函数结束语句 return 表达式； return; case结束语句 break; 异常结束语句 exit（异常代码）； 7. 在算法描述中可以使用的输

5、入输出语句形式有： 输入语句 scanf( 格式串，变量名1，.，变量名n)； 输出语句 printf( 格式串，表达式1，.，表达式n); 方括号（ ）中的内容是可以省略的部分。 8. 在算法描述中使用的注释格式为： 单行注释 /文字序列,9,9. 在算法描述中可以使用的扩展函数有： 求最大值 max（表达式1，.，表达式n） 求最小值 min（表达式1，.，表达式n） 求绝对值 abs（表达式） 求不足整数值 floor（表达式） 求进位整数值 ceil（表达式） 判定文件结束 eof（文件变量）或eof 判定行结束 eoln（文件变量）或eoln 10.逻辑运算约定 与运算& 对于A &

6、B，当A值为0 时，不再对B求值。 或运算| 对于A|B，当A值为1 时，不再对B求值。,10,程序设计语言简介 1.数据类型、运算符和表达式 2.程序的三种基本结构 3.数组 4.函数 5.指针 6.结构体和共用体,11,一个简单的C程序 main() int max(x,y) int x,y; int a,b,sum; int z; a=123;b=456; if (xy) z=x; sum=a+b; else z=y; printf(“sum is %d n”,sum); return(z); main() int a,b,c; scanf(“%d,%d”, ,12,数据类型、运算符和表

7、达式 1.C语言的基本元素 （1）符号集（字符集） C语言使用的符号集共5种:大写字母AZ，小写字母az，阿拉伯数字09，下划线_，标点符号和运算符。 （2）标识符 用来标记常量、变量、函数及文件名字的字符序列。构成规则如下： 以字母（大小写均可）或下划线开头； 随后可跟若干个（可以是0个）字母、数字、下划线； 标识符的长度各个系统不同，最好不超过8个； 区分大小写。 （3）关键字 也称“保留字”，是C语言中具有特定含义、专门用作语言特定成分的一类标识符。 所有关键字都有固定意义，不作它用。所有关键字都必须小写。,13,2.C的数据类型 数据是操作的对象，数据类型是指数据的内在表现形式（代码、

8、存储、运算）。,14,3.常量和变量 （1）常量和符号常量 常量：其值在运行过程中不能被改变的量。 通过表现形式可以区分常量的类型。如：12, 3.2 , a 符号常量：用一个标识符代表的一个常量。 定义方法：#define 标识符 常量 （2）变量 其值是可以改变的量，用标识符（变量名）来表示，在内存中占据一定的存储单元。 定义方法：类型符 标识符 注意：见名知意；先定义后使用；习惯上，符号常量名用大写，变量名用小写，以示区分。,15,4.整型数据 (1)整型常量：十进制常数、八进制常数、十六进制常数。 (2)整型变量：基本型int （2字节），短整型short int（2字节），长整型lo

9、ng int（4字节） 5.实型数据 (1)实型常量：实型又称浮点数，缺省为double型，有十进制数形式和指数形式两种表示方法。 (2)实型变量：单精度型（float）占4字节，双精度（double）占8字节。 6.字符型数据 (1)字符常量：用单引号括起来的一个字符；转义字符（特殊的字符常量，都以“”开头）。 (2)字符变量：用来存放字符，且只能存放一个字符。 (3)字符串常量：用一对双引号括起来的字符序列。一般情况下，每个字符串常量末尾都由系统自动加上一个字符“0”。,16,7.变量赋初值 在变量定义的同时设置初值，也称初始化。 8.算术运算符和算术表达式 (1)C运算符 算术运算符 +

10、 - * / % 关系运算符 = | & 赋值运算符 = 条件运算符 ? : 逗号运算符 , 指针运算符 * & 求字节运算符 sizeof 分量运算符 . 下标运算符 其它,17,(2)算术运算符和算术表达式 用算术运算符和括号将运算对象（包括常量、变量、函数等）连接起来的，符合C语言语法规则的式子，称为算术表达式。 运算符的优先级和结合性 优先级：先* / %后+ -。 结合性：当运算对象两侧的运算符优先级相同时，表达式从左往右计算称“左结合性”，从右往左计算称“右结合性”。 自增、自减运算符 +i，-i 在使用i之前，先使i的值加1或减1 i+，i- 在使用i之后，再使i的值加1或减1

11、注：自增自减运算符只能用于变量，不能用于常量或表达式。其优先级高于算术运算符，结合方向是“自右向左”。如：-i+相当于- (i+)。(-和+为 如：i=3; j=+i; /i=4 j=4 同一优先级) i=3; j=i+; /i=4 j=3,18,(3)复合的赋值运算符 在赋值运算符“=”之前加上其它运算符，构成复合赋值运算符。 +=，-=，*=，/=，%=，=，&=，=，|= 如：a+=3 等价于a=a+3 x*=y+9 等价于x=x*(y+9) 注：各类运算符优先级从高到低的排列： 初等运算符（） - . 单目运算符 算术运算符（先乘除后加减） 关系运算符 逻辑运算符（不包括！） 条件运算

12、符 赋值运算符 逗号运算符,19,程序的三种基本结构 1.顺序程序设计 程序中语句的执行顺序就是语句的书写顺序。 2.选择结构的程序设计 (1)if语句的三种格式 条件执行 if (e) A 分支选择 if (e) A else B else if形式（阶梯式的ifelse语句） if (P1) S1; else if (P2) S2; else if (Pn) Sn; else Sn+1;,20,(2)switch语句（开关语句） 也称多分支选择语句，处理多路分支问题时，比用嵌套的if语句程序更清晰易读。 switch (表达式) case 常量表达式1: 语句1； case 常量表达式2:

13、 语句2; case 常量表达式n: 语句n; default : 语句n+1; ,21,3.循环结构的程序设计 (1)while语句 用来实现“当型”循环。其一般形式如下： while (表达式) 语句 (2)dowhile语句 用来实现“直到型”循环。其一般形式为： do 语句 while （表达式） (3)for语句 for (表达式1；表达式2；表达式3) 语句 注：表达式1在进入循环之前求解（循环变量赋初值）；表达式2是此轮循环能否进行的判断条件；在一轮循环中执行完循环体中的语句后要求解表达式3，即表达式3是循环体的一部分。,22,数组 1.数组 数组是按序排列的具有相同类型的变量的

14、集合。 用一个符号名（数组名）来表示这一组数。 用数组名后跟下标来惟一地确定数组中的元素。 2.定义一维数组 类型名 数组名 常量表达式 定义即提供名、类型、维数、长度的信息，从而分配空间。 数组名命名规则与简单变量名相同。 数组名后只能跟方括号括起来的常量表达式（常量和符号常量）。 常量表达式的值确定数组元素的个数（数组尺寸）。 用连续的内存单元存放数组中的各个元素。 如：int a5;其内存存储为：,23,保存数组所需内存量与数组元素的基本类型和数组大小有关。 总字节数=sizeof（基本类型）*数组元素个数 如上例：总字节数=sizeof(int)*5=2*5=10 3.一维数组的引用

15、数组必须先定义后引用。C语言规定只能逐个引用数组元素，而不能一次引用整个数组。 引用一维数组的形式为：数组名下标 ，下标从0开始。 4.二维数组 在C语言中，数组的元素可以是数组，这样就构成了二维数组。同理可构成三维数组、四维数组等。 5.二维数组的定义和引用 类型名 数组名常量表达式常量表达式 如：int a34; 二维数组的引用：数组名下标下标,24,6.字符数组 在C语言中，没有专门的字符串变量，而是将字符串存入字符数组来处理。 即用一个一维数组来存放一个字符串，每个元素存放一个字符。 定义形式：char 数组名常量表达式常量表达式 为了确定实际字符串长度，C语言规定了一个“字符串结束标志”即0。当遇到0表