c语言逆波兰表

重庆市农业学校

理论课程教师教案本

（ 2013 — 2014 学年 第 二 学期）

专业名称 农村电气技术

课程名称 C语言程序设计

授课教师 甘 雨

学 校 重庆市农业学校

课题序号 1 授课班级

授课课时 2h 授课形式 理论

授课章节

名称 1．1C语言的产生过程及特点

1．2C语言程序的结构及书写格式

使用教具

教学目的 1. 了解C语言的产生过程和发展特点

2. 初步认识C语言程序的结构

3. 了解C语言的一些相关知识

教学重点 1. C语言程序的结构

2. C语言程序的特点

教学难点 1. C语言程序的结构特点

2. C语言程序的书写格式

更新、补

充、删节

内容

课外作业 P10 1-3 教学后记

授课主要内容或板书设计

第一章 C语言概述

1.1 C语言的产生过程及特点

一、C语言出现的历史背景

二、C语言的特点

1.2 C语言程序的结构及书写格式

一、简单的C程序介绍

二、C语言的一般形式

课 堂 教 学 安 排 教学过程 主 要 教 学 内 容 及 步 骤

（一）导入新课

（二）新授

C语言是国际上广泛流行的、很有发展前途的计算机高级语言。以前的操作系统软件主要是用汇编语言编写的，然而，汇编语言依赖于计算机硬件，程序的可读性和可执行性都比较差。为了解决这一问题，产生了C语言。本学期我们就将共同来学习C语言的一些相关知识，本堂课先来了解一下C语言程序的发展及其结构特点。

1.1C语言的产生过程及特点

一 、C语言出现的历史背景

1. Ｃ语言是第三代语言即为面向过程的高级语言。

第一代：机器语言；第二代：汇编语言；

在C语言的基础上又发展出来了第四代语言：面向对象的程序设计语言，例如C++和VB等高级语言。

二,填空题（10道小题，共20分）

1、一个C源程序中至少应包含一个[main] 函数。

2、a是整型变量，则执行表达式a=25/3%3后a的值为。[2]

3、int m=5,y=2;则表达式y+=y- =m*=y的值为。[-16]

4、执行下列语句: int a=1, b=2; a=a+b; b=a-b; a=a-b; printf("%d , %d \n", a,b );的输出结果分别是[2,1]

5、条件表达式的格式为表达式1？表达式2：表达式3,若表达式2和表达式3的类型不同，此时条件表达式的值的类型为二者中较[高]的类型

6、当运行以下程序时，从键盘键入right?(代表回车)，则下面程序的运行结果是。

#include

main( )

{ char c;

while((c=getchar())! ='?') putchar(++c)

}

[sjhiu?]

7、C语言中的数组必须先[定义],然后使用。

8、如果需要从被调用函数返回一个函数值，被调用函数必须包含【return】语句。

9、已知：float f1=3.2,f2,*pf1=&f1;f2=f1，则*f2的值为。[3.2]

10、以下程序

void fun(char *a, char *b)

{ a=b; (*a)++; }

main () { char c1="A", c2="a", *p1, *p2;

p1=&c1; p2=&c2; fun(p1,p2);

printf(“&c&c\n”,c1,c2);

}

运行后的输出结果是 。[&c&c]

11、字符串常量“123”在内存中的字节数是 。[8字节]

12、已有定义 :int x=3 ;则表达式 :x=x+1.78 的值是 。【4】

13、int a=24; printf("%o ", a );输出结果是 。【30】

14、当a=3,b=2,c=1时，表达式f=a>b>c的值是 。【0】

逆波兰表达式

逆波兰表达式

表达式⼀般由操作数(Operand)、运算符(Operator)组成，例如算术表达式中，通常把运算符放在两个操作数的中间，

这称为中缀表达式(Infix Expression)，如A+B。

波兰数学家Jan Lukasiewicz提出了另⼀种数学表⽰法，它有两种表⽰形式：

把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；

把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+；

其中，逆波兰表达式在编译技术中有着普遍的应⽤。

算法：

⼀、 将中缀表达式转换成后缀表达式算法：1、从左⾄右扫描⼀中缀表达式。

2、若读取的是操作数，则判断该操作数的类型，并将该操作数存⼊操作数堆栈

3、若读取的是运算符

(1) 该运算符为左括号"("，则直接存⼊运算符堆栈。

(2) 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为⽌。

(3) 该运算符为⾮括号运算符：

(a) 若运算符堆栈栈顶的运算符为括号，则直接存⼊运算符堆栈。

(b) 若⽐运算符堆栈栈顶的运算符优先级⾼或相等，则直接存⼊运算符堆栈。

(c) 若⽐运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压⼊运算符堆栈。

4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

⼆、逆波兰表达式求值算法：1、循环扫描语法单元的项⽬。

2、如果扫描的项⽬是操作数，则将其压⼊操作数堆栈，并扫描下⼀个项⽬。

3、如果扫描的项⽬是⼀个⼆元运算符，则对栈的顶上两个操作数执⾏该运算。

4、如果扫描的项⽬是⼀个⼀元运算符，则对栈的最顶上操作数执⾏该运算。

5、将运算结果重新压⼊堆栈。

6、重复步骤2-5，堆栈中即为结果值。

第一章

三、计算下列程序段中X=X+1 的语句频度

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

for(k=1;k<=j;k++)

x=x+1;

[提示]：

i=1 时： 1 = (1+1)×1/2 = (1+1 )/2

i=2 时： 1+2 = (1+2)×2/2 = (2+22)/2

i=3 时： 1+2+3 = (1+3)×3/2 = (3+32)/2

„

i=n时： 1+2+3+„„+n = (1+n)×n/2 = (n+n )/2

f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2

=[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2

=n(n+1)(n+2)/6

=n /6+n /2+n/3

区分语句频度和算法复杂度：

O(f(n)) = O(n )

四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +„a x 的值P (x )，并确定算法中的每

一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能

使用求幂函数。注意：本题中的输入a (i=0,1,„,n), x和n，输出为P (x ).通常算法的输入和输出可采用下列两种方式之一：

（1）通过参数表中的参数显式传递；

（2 ）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

[提示]：float PolyValue(float a[ ], float x, int n) {„„}