当前位置:首页 >> 其它课程 >> 第一章 算法描述

第一章 算法描述


算法的描述
选择算法描述语言的准则: ?该语言应该具有描述数据结构和算法的基本功能; ?该语言应该尽可能地简捷,以便于掌握、理解; ?使用该语言描述的算法应该能够比较容易地转换成任何一 种程序设计语言。 “类C”描述语言是通过对C语言进行精心筛选保留的一个

核心子集,并为了便于描述,又做了若干扩展修改,从而,
增强了语言的描述功能。

/>
1

1. 预定义常量及类型

#define TRUE 1
#define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 数据元素被约定为ElemType 类型,用户需要根据具体 情况,自行定义该数据类型。

2

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

3. 在算法描述中可以使用的赋值语句形式有: 简单赋值 变量名=表达式;

串联赋值

变量名1=变量名2=...=变量名n= 达式;

成组赋值 (变量名1,...,变量名n)=(表达式1,...,表 达式n); 结构赋值 结构名1 = 结构名2; 结构名 =(值1,值2,...,值n);

条件赋值
交换赋值

变量名 = 条件表达式 ? 表达式1:表达式2;
变量名1 ? 变量名2;

4

4. 在算法描述中可以使用的选择结构语句形式有: 条件语句1 条件语句2 开关语句1 if (表达式) 语句; if (表达式) 语句; else 语句; switch (表达式) { case 值1:语句序列1;break; case 值2:语句序列2;break; ... case 值n:语句序列n;break; default:语句序列n+1; }
5

开关语句2

switch {
case 条件1:语句序列1;break; case 条件2:语句序列2;break; ... case 条件n:语句序列n;break; default:语句序列n+1; }

6

5. 在算法描述中可以使用的循环结构语句形式有:

for循环语句
for (表达式1;循环条件表达式;表达式2) 语句; while循环语句 while (循环条件表达式) 语句; do-while循环语句 do { 语句序列; } while (循环条件表达式);

7

6. 在描述算法中可以使用的结束语句形式有: 函数结束语句 return 表达式; return; case结束语句 break; 异常结束语句 exit(异常代码); 7. 在算法描述中可以使用的输入输出语句形式有: 输入语句 scanf( [格式串],变量名1,...,变量名n); 输出语句 printf( [格式串],表达式1,...,表达式n); 方括号([ ])中的内容是可以省略的部分。 8. 在算法描述中使用的注释格式为: 单行注释 //文字序列

8

9. 在算法描述中可以使用的扩展函数有: 求最大值 max(表达式1,...,表达式n) 求最小值 min(表达式1,...,表达式n) 求绝对值 abs(表达式) 求不足整数值 floor(表达式) 求进位整数值 ceil(表达式) 判定文件结束 eof(文件变量)或eof 判定行结束 eoln(文件变量)或eoln
10.逻辑运算约定 与运算&& 对于A &&B,当A值为0 时,不再对B求值。 或运算|| 对于A||B,当A值为1 时,不再对B求值。

9

程序设计语言简介
1.数据类型、运算符和表达式 2.程序的三种基本结构 3.数组 4.函数

5.指针
6.结构体和共用体

10

一个简单的C程序
main() { int max(x,y) int x,y;

int a,b,sum;
a=123;b=456; sum=a+b;

{int z;
if (x>y) z=x; else z=y;

printf(“sum is %d \n”,sum);
}

return(z);
} main()

{int a,b,c;
scanf(“%d,%d”,&a,&b); c=max(a,b);

printf(“max=%d”,c);
}
11

数据类型、运算符和表达式
1.C语言的基本元素
(1)符号集(字符集) C语言使用的符号集共5种:大写字母A~Z,小写字母a~z,阿拉伯数字0~9, 下划线_,标点符号和运算符。

(2)标识符
用来标记常量、变量、函数及文件名字的字符序列。构成规则如下: ?以字母(大小写均可)或下划线开头;

?随后可跟若干个(可以是0个)字母、数字、下划线;
?标识符的长度各个系统不同,最好不超过8个; ?区分大小写。

(3)关键字
?也称“保留字”,是C语言中具有特定含义、专门用作语言特定成分的一 类标识符。 ?所有关键字都有固定意义,不作它用。所有关键字都必须小写。
12

2.C的数据类型
数据是操作的对象,数据类型是指数据的内在表现形式(代码、存储、 运算)。 整型 int 基本类型 实型(浮点型) 单精度 float 双精度 double

字符型 char
数组 结构体 共用体 枚举型 指针类型

数据类型

构造类型

空类型

13

3.常量和变量
(1)常量和符号常量 ?常量:其值在运行过程中不能被改变的量。

通过表现形式可以区分常量的类型。如:12, 3.2 , ?a?
?符号常量:用一个标识符代表的一个常量。 定义方法:#define 标识符 常量 (2)变量 ?其值是可以改变的量,用标识符(变量名)来表示,在内存中占据一定 的存储单元。 ?定义方法:类型符 标识符 ?注意:见名知意;先定义后使用;习惯上,符号常量名用大写,变量名 用小写,以示区分。
14

4.整型数据 (1)整型常量:十进制常数、八进制常数、十六进制常数。 (2)整型变量:基本型int (2字节),短整型short int(2字节),长整型 long int(4字节) 5.实型数据 (1)实型常量:实型又称浮点数,缺省为double型,有十进制数形式和指数 形式两种表示方法。 (2)实型变量:单精度型(float)占4字节,双精度(double)占8字节。 6.字符型数据 (1)字符常量:用单引号括起来的一个字符;转义字符(特殊的字符常量, 都以“\”开头)。 (2)字符变量:用来存放字符,且只能存放一个字符。 (3)字符串常量:用一对双引号括起来的字符序列。一般情况下,每个字符 串常量末尾都由系统自动加上一个字符“\0”。 15

7.变量赋初值 在变量定义的同时设置初值,也称初始化。 8.算术运算符和算术表达式 (1)C运算符 算术运算符 + - * / %

关系运算符
逻辑运算符 位运算符 赋值运算符 条件运算符 逗号运算符 指针运算符 分量运算符 下标运算符

>
! << = ? : , * . [ ]

<
&&

==
||

>=
| ^

<=
&

!=

>> ~

& ?
16

求字节运算符 sizeof

其它

(2)算术运算符和算术表达式
?用算术运算符和括号将运算对象(包括常量、变量、函数等)连接起来的, 符合C语言语法规则的式子,称为算术表达式。

?运算符的优先级和结合性
优先级:先* / %后+ -。 结合性:当运算对象两侧的运算符优先级相同时,表达式从左往右计算称 “左结合性”,从右往左计算称“右结合性”。 ?自增、自减运算符 ++i,--i 在使用i之前,先使i的值加1或减1

i++,i--

在使用i之后,再使i的值加1或减1

注:自增自减运算符只能用于变量,不能用于常量或表达式。其优先级高 于算术运算符,结合方向是“自右向左”。如:-i++相当于- (i++)。(-和++ 为 如:i=3; j=++i; i=3; j=i++; //i=4 //i=4 j=4 j=3 同一优先级) 17

(3)复合的赋值运算符

在赋值运算符“=”之前加上其它运算符,构成复合赋值运算符。
+=,-=,*=,/=,%=,<<=,>>=,&=,^=,|= 如:a+=3 等价于a=a+3

x*=y+9 等价于x=x*(y+9)
注:各类运算符优先级从高到低的排列: 初等运算符()[] -> . 关系运算符 赋值运算符 单目运算符 算术运算符(先乘除后加减) 逻辑运算符(不包括!) 条件运算符 逗号运算符

18

程序的三种基本结构
1.顺序程序设计
程序中语句的执行顺序就是语句的书写顺序。 2.选择结构的程序设计

(1)if语句的三种格式
?条件执行 if (e) A ?分支选择 if (e) A else B

?else if形式(阶梯式的if—else语句)
if (P1) S1; else if (P2) S2;

……
else if (Pn) Sn; else Sn+1;
19

(2)switch语句(开关语句) 也称多分支选择语句,处理多路分支问题时,比用嵌套的if语句程序 更清晰易读。 switch (表达式) {case 常量表达式1: 语句1; case 常量表达式2: 语句2; …… case 常量表达式n: default } 语句n;

: 语句n+1;

20

3.循环结构的程序设计
(1)while语句 用来实现“当型”循环。其一般形式如下:

while (表达式)
(2)do—while语句

语句

用来实现“直到型”循环。其一般形式为:

do 语句
while (表达式) (3)for语句

for (表达式1;表达式2;表达式3)

语句

注:表达式1在进入循环之前求解(循环变量赋初值);表达式2是此轮 循环能否进行的判断条件;在一轮循环中执行完循环体中的语句后要求 解表达式3,即表达式3是循环体的一部分。
21

数组
1.数组 ?数组是按序排列的具有相同类型的变量的集合。

?用一个符号名(数组名)来表示这一组数。
?用数组名后跟下标来惟一地确定数组中的元素。 2.定义一维数组 类型名 数组名 [常量表达式] ?定义即提供名、类型、维数、长度的信息,从而分配空间。 ?数组名命名规则与简单变量名相同。 ?数组名后只能跟方括号括起来的常量表达式(常量和符号常量)。

?常量表达式的值确定数组元素的个数(数组尺寸)。
?用连续的内存单元存放数组中的各个元素。 如:int a[5];其内存存储为: 1000 1002 1004 1006 a[0] a[1] a[2] 1008 a[4]
22

a[3]

?保存数组所需内存量与数组元素的基本类型和数组大小有关。
总字节数=sizeof(基本类型)*数组元素个数 如上例:总字节数=sizeof(int)*5=2*5=10

3.一维数组的引用
?数组必须先定义后引用。C语言规定只能逐个引用数组元素,而不能一次 引用整个数组。 ?引用一维数组的形式为:数组名[下标] ,下标从0开始。 4.二维数组 在C语言中,数组的元素可以是数组,这样就构成了二维数组。同理可 构成三维数组、四维数组等。 5.二维数组的定义和引用 类型名 数组名[常量表达式][常量表达式] 如:int a[3][4]; ?二维数组的引用:数组名[下标][下标]
23

6.字符数组 ?在C语言中,没有专门的字符串变量,而是将字符串存入字符数组来处理。 ?即用一个一维数组来存放一个字符串,每个元素存放一个字符。 ?定义形式:char 数组名[常量表达式][[常量表达式]]…… ?为了确定实际字符串长度,C语言规定了一个“字符串结束标志”即‘\0?。 当遇到‘\0?表示字符串结束。 ?以字符串方式赋值时,必须保证数组元素个数>=字符个数+1(字符串后面自 动加上一个‘\0? )。 如:char c[6]=“china”;

c
c[0]

h
c[1]

i
c[2]

n
c[3]

a
c[4]

\0
c[5]

24

函数
1.概述
?一个C程序可以分成若干个函数。 ?每个程序有且只能有一个主函数(main),其它的都是子函数。

?子函数可以互相调用,但主函数不能被调用。
?C程序的执行从main函数开始,调用其它函数后仍回到主函数,程序在 main函数结束时结束。

?所有子函数都是平行的,任何子函数都不属于其它函数。
?从用户角度看,函数可分为:标准函数(即库函数)和自定义函数。 ?从函数形式上看,可分为:无参数函数和有参数函数。 2.函数定义的一般形式 类型说明 函数名([形式参数说明]) {函数体}
25

3.函数参数和函数的值
?组成C程序的各函数间进行函数调用时要传递一些数据,这些信息的往 来是由参数传递和返回语句实现的。 ?形式参数:定义函数时使用的参数。 ?实际参数:引用函数时使用的参数。 如:int max(int x,int y) {…} void main() {int a,b,c; a=2; b=3; c=max(a,b); ……} ?定义函数时,必须说明形参的类型,它只能是变量或数组。 ?函数被调用前,形参不占用内存。函数调用结束后,形参占用的内存将 被收回。 ?实参可以是常量、变量或表达式。 ?实参与形参的类型必须一致。 ?C语言中实参对形参的数据传递是“值传递”,即单向传递。它仅由参 数的对应位置确定,与名字无关。
26

指针
1.变量的地址
计算机中,数据存放在内存中。内存可划分成若干存储单元,每个单元 可存放一个字节(即8位二进制数)。内存单元采用线性地址编码,每个 单元具有惟一一个地址编码。 变量的地址:系统为变量分配的内存单元的地址。 2.变量的访问 ?直接访问:int a; a=3; ?间接访问:定义一个变量p存放a的地址,通过p访问a。 问题:如何定义p?如何获得变量a的地址?如何通过p访问a? 3.指针变量 指针变量是存放地址的变量。如:设p为指针变量,存放整型变量a的首 地址,则称指针变量p指向整型变量a。

3A50

3A58

3 a

5 b

3A50

p
27

4.指针变量的定义

类型名

*指针变量名

指针变量的类型:指针所指向的内存单元中存放的数据的类型。
如:int *p1,*p2; char *ps;

5.指针变量的赋值
指针变量的值为地址,是一个无符号整数,但不能直接把整型常量赋给指 针变量。 可将变量的地址赋给指针变量(求地址运算符&),注意变量的类型必须 要与指针变量的类型相一致。如:int a,b,*p; p=&a; 也可用相同类型的指针变量赋值。如:int a,*p1,*p2; p1=&a; p2=p1;

若不赋值,指针变量的值是随机的。
赋空值NULL。如:int *p; p=NULL; 或p=0;
28

6.两个相关的运算符
&任意变量 *指针变量 //取地址运算符 //指针运算符

含义:&a表示变量a所占据的内存空间的首地址; *p表示指针变量p所指向的内存中的数据。 应用:通过指针变量访问所指变量。 ?将指针变量指向被访问的变量。 *p=a

如:int a,*p,b;
?访问所指变量。

p=&a;

取内容: b=*p; printf(“%d\n”,*p);

存内容:*p=100;
注:*p若出现在“=”右边或其他表达式中则为取内容; *p若出现在“=”左边则为存内容。
29

7.运算规则
*和&优先级相同,且右结合(从右往左进行运算),它们与++、--、! 等单目运算符的优先级相同,但高于算术运算符*、/、%。 如:int a=2,*p=&a,*q=&a; printf(“%d %d\n”,*p++,*(q++)); p=&a; q=&a; //2 2

printf(“%d %d\n”,*p,(*q)++);

//3 2 (参数的求值过程从右往左)

如:找出下列表达式中具有等价关系的对子。 int a=5,*p=&a;

&*p, *&a, (*p)++, &a, a, *p++, *(p++), a++
解: &*p=&a =p (*p)++=a++ *&a=*p=a *p++=*(p++)

30

8.指针和一维数组 ?数组是连续存放的若干个元素的集合。 ?数组名就是指向此数组中第1个元素的指针(首地址)。 如:int a[10],*p; 则p=a等价于p=&a[0] ?某一元素的地址:p=&a[i] 用指针引用该元素:*p等价于a[i] ?数组元素的下标在内部实现时,统一按“基地址+位移”的方式来处理, 即a, a+1, …, a+i 故表示数组元素的地址可用:p+i, a+i 表示数组元素的内容可用:a[i], *(p+i), *(a+i) ?数组名a(数组的指针)和指向数组首地址的指针变量p不同,a不是变量。

31

结构体
1.概述 ?有时需要将不同类型的数据组合成一个有机的整体。

?结构体:若干个数据类型不同(也可相同)的数据项的一个组合。
?结构体与数组不同,数组中的各元素是属于同一个类型的。 ?结构体是一种数据结构,需要用户根据自己的需要、按某种规则定义, 即定义结构体类型。 如:struct student {int num;

char nmae[20];
int age; float score

};
32

2.定义结构体类型变量的方法
(1)先定义结构体类型再定义变量名 定义形式: 如:

struct 结构体类型名
{ 成员列表 } struct 结构体类型名 变量名 (2)在定义类型的同时定义变量 定义形式: struct 结构体类型名 { 成员列表 }变量名表列;

struct student
{ int num; char name[20]; }; struct student stu1,stu2; 如: struct student {int num; char name[20]; }stu1,stu2;
33

(3)直接定义结构类型变量 定义形式: struct { 成员表列 }变量表列; 如: struct {int num; char name[20]; }stu1,stu2;

说明:结构体类型变量的成员也可以是一个结构体变量。如: struct date {int month; int day; int year; }; struct student {int num; char name[20]; struct date birthday; }stu1,stu2;
34

3.结构体类型变量的引用 ?形式:结构体变量名.成员名 ?“.”是成员(分量)运算符,它在所有的运算符中优先级最高。 ?如果成员本身又属于一个结构体类型,则要用若干个成员运算符,一级一 级地找到最低一级的成员。 4.结构体数组 ?结构体数组中,每个数组元素都是一个结构体类型的数据。 如:struct student {int num; char name[20];

}stu[3];
?数组各元素在内存中连续存放。
35

5.指向结构体变量的指针 ?定义形式:struct 结构体类型名 *指针名 ?引用方式:(*p) . 成员名 等价于 p->成员名 等价于 结构体变量名 . 成员名 ?->称为指向运算符。 如:struct student stu1,*p; p=&stu1; p->num=10; (*p).name=“Li Lin”; stu1.num=20;

36

共用体
?有时需要把几种不同类型的变量存放到同一段内存单元中,也即使用覆盖 技术,几个变量互相覆盖。这种使几个不同的变量共占同一段内存的结构, 称为“共用体”。
?定义形式: union 共用体名 {成员表列 }变量表列; 如: union data {int i; char ch; }a,b; ?结构体变量所占内存长度是各成员所占的内存长度之和,共用体变量所占 的内存长度等于最长的成员的长度。

?共用体变量中起作用的成员是最后一次存入的成员,在存入一个新的成员 后原成的成员就失去作用。如:a.i=1; a.ch=?a?;则只有a.ch有效,a.i已无意 义。
?共用体变量的地址和它的各成员的地址是同一地址。
37

用typedef定义类型
?除了可以直接使用C提供的标准类型名(如int,char,float等)和自己定义的 结构体、共用体、指针、枚举类型外,还可用typedef定义新的类型名来代 替已有的类型名。如:typedef int INTEGER; 它指定用INTEGER代表int 类型,以下两句等价。 int i,j; INTEGER i,j;

?可以定义结构体类型: typedef struct {int month; int day; int year; }DATE; 定义新类型名DATE,它代表上面定义的一个结构体类型。此时可用DATE 定义变量:DATE birthday; DATE *p; 38

?还可进一步:
1.typedef int NUM[100]; //定义NUM为整型数组类型 NUM n; //定义n为整型数组变量

2.typedef char *STRING; //定义STRING为字符指针类型 STRING p,s[10]; //p为字符指针变量,s为指针数组 3.typedef int (* POINTER)() //定义POINTER为指向函数的指针类型, 该函数返回整型值 POINTER p1,p2; //p1,p2为POINTER类型的指针变量。

?习惯上常把用typedef定义的类型名用大写字母表示,以便与系统提供的 标准类型标识符相区别。

39


更多相关文档:

第一章算法

第一章算法 1.1.1 算法的概念 一.选择题 1.算法的有穷性是指( (A)算法必须包含输出 (C)算法的步骤必须有限 2.下列用算法语言描述正确的是( A.算法只能...

第一章算法的概念

第一章算法的概念 隐藏>> §1.1.1 【教学目标】 :(1) (2) (3) (4)...说明: 1.“算法”没有一个精确化的定义,教科书只对它作了描述性的说明. 2...

第一章算法001首选

第​一​章​算​法​0​0​1​首​选 暂无评价|0人阅读|0...0 其中不需要用 条件语句来描述算法的有 ( A. 1 个 C. 3 个 B. 2 ...

必修3知识点总结:第一章_算法初步

必修3知识点总结:第一章_算法初步_从业资格考试_资格考试/认证_教育专区。高中...5、 在图形符号内描述的语言要非常简练清楚。 (三) 、算法的三种基本逻辑结构...

第一章 C概述

第一章 C概述_理学_高等教育_教育专区。1. 以下叙述中错误的是( )。 A) ...7. 以下不能用于描述算法的是 A) B) C) D) 文字叙述 程序语句 伪代码和...

第一章第二节 算法和算法的描述教学设计(高中信息技术精品)

第一章第二节 算法算法描述教学设计(高中信息技术精品)_其它课程_初中教育_教育专区。第一章第二节 算法算法描述 一、课程内容标准: 经历用自然语言、...

第一章 算法初步

第​一​章​ ​算​法​初​步 暂无评价|0人阅读|0次下载|举报文档《算法初步》练习题 一、选择题 1.下面对算法描述正确的一项是( ) A.算法...

第一章111算法的概念

第一章111算法的概念_其它_高等教育_教育专区。第一章111算法的概念第...问题的想法.为建立算法的概念,以及下面学习复杂问题中用自然语言描述算法 打好...

第一章“算法初步” 简介

第一章算法初步” 简介_其它课程_高中教育_教育专区。第一章算法初步” 简介...但是,用自然语言或程序框图描述算法计算 机是无法“理解”的,我们还需要将...

必修3第一章算法

必修3 数学第一章 算法初步一.本章的知识结构 1. 算法定义描述:在数学中,通常指按照一定规则解决某一类问题的明确和有限的步骤。 ... 解读为:现代意义上的“...
更多相关标签:
算法导论第一章答案 | 算法第四版第一章 | 第一章运动的描述ppt | 第一章 运动的描述 | 算法精解 c语言描述 | 算法描述 | 算法的描述方法包括 | 算法描述方法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com