《c 课件 第3章 基本语言成份》由会员分享，可在线阅读，更多相关《c 课件 第3章 基本语言成份（9页珍藏版）》请在金锄头文库上搜索。
1、第三章 基本语言成份在以前的C语言入门课程中，由于是学的是编程ABC，有一些稍难稍偏的基本问题被略过了，这些问题随着同学们编程能力的提高，逐渐变得重要，下面通过一些题目，补上一部分欠缺。一、表达式1怎样分析复杂表达式-从右向左读Q1：下面的代码做完后a,b,c各等于几？为什么？int a = 5, b = 7, c;c = a+b;在“第2章 指针和引用”曾讲过，对于指针的声明应从“从右向左读”，对复杂表达式的理解最好是 “总体顺序上从右向左，同时考虑算符优先级和左右结合性” 因为编译器就是这样读表达式的。为什么？请同学们选修下学期的“编译原理”。如何读Q1的表达式？从右向左。另外再考虑算符优
2、先级和结合性(本例的+算符优先级高于+，+是自右向左结合，+是左向右结合)。上面的代码被编译器理解为：（1）b+.+：右一的+是否向结合第二个+？还要再往左看。（2）（第二个）+左面无操作数自右向左结合左3的+，形成+。（3）从右到左扫瞄+时，一开始编译器以为+都是同级的，中间的+先和右3的+结合（+是自右向左结合），形成高优先级的+。而不会回头与右1的+结合。（4）所以，表达式被编译器解读为：C = a+ + b;/运行后a = 6, b = 7, c = 12但在实际编程中，不要采用这种费解的写法，直接写成c =（ a+）+b;这样可读性更好。2. 左值表达式在赋值号左边的表达式称为左值表
3、达式。按语法规定，=左面应是变量，不应是常量, 不能是字面量，也不应是临时变量(只存在一瞬间的、编译器内部的中间操作变量)。所以，=左面的表达式如果代表变量，就可以左值。比如:const int A = 10;A = 20; /错,第二句的左值A不能是常量10 = 20; /错,更不能是字面量int a=1,b=2;a+b=5; /错，第二句不能是只存在一瞬间的临时变量(a+b的和)C语言中,最常见的左值表达式有,左自增,左自减,指针取变量值。例如:+i；/先给i加1，然后返回i本身，相当于i=i+1; =左面是变量i，因此+i是左值表达式，可以这样写：+i=5; / i=5,按优先级，先+i
4、，再=-i=5; / i=5,按优先级，先-i，再=int a,*p=&a;*p=5;/*p代表一个变量，可以左值。Q2：右自增运算符i+是否左值？int i=3; i+; / 按语法要求是：先使用i，再给i加1，编译器怎么做呢？i+先由编译器内部产生一个临时变量，保存i的值，而后给i加1，接着返回临时变量，如果返回i的话，i+和+i就没有区别了。然后临时变量不存在了，因此i+是右值表达式。为什么说有个一个临时变量呢？比如：int i=3;j=i+；按运算符优先级分析，应先+后=，j接受的是i+1，应为4。而实际上应为3，说得通的解释是：j接受的是一个临时变量的值（3），也就是说表达式j=i+
5、返回的是临时变量的值，该临时变量返回j以后就不存在了。在C+中,由于引用的存在,左值表达式可以是函数。在第2章“指针与引用”中曾举过一个例子：int &max(int &d1,int &d2) /函数返回一个对int类型的引用return d1d2?d1:d2;/可以使用左值方式调用函数int main()int x=5, y=6;max(x,y)+=1; /左值调用return 0;为什么可以？首先，函数返回的是引用，引用是另一个变量的别名。这“另一个变量”是谁呢？从函数体内的return看，或是d1或是d2，而d1或d2在调用时又确切指向实参x或y，也就是说，函数max返回的是确定的变量x
6、或y，可以左值调用。上机习题1（选做-选作题不是期末考试内容，以下各章相同）如果把max的return d1d2?d1:d2;改为returnd1*d2，是否可以左值调用？如果把max的返回类型改为指针int*，是否也可以左值调用？为什么？或干脆只返回int，是否也可以左值调用？为什么？应该注意引用类型的性质：引用是另一个确定的量的别名，引用是不能为NULL的，引用必需确切绑定一个确定的量，而一旦绑定该量，就不能改变，除非引用自动消失。在max(x,y)+=1的左值调用中，函数返回的（隐式的临时）引用确定绑定了x或y，但函数调用完成后，该引用随函数“自动消失”，但它绑定的变量x或y还没消失。小
7、结： 关于一个表达式是否可以左值，可以用以下简单方法判别：返回有名称的变量且有确切地址（可在表达式前加一个取址操作符&），即可为左值表达式。上机习题2（选做）四则运算表达式的分析和求值输入一个四则运算表达式，比如 (2*9)+6/2, 怎样求出它的值？这道题如果没学过“编译原理”，不容易做。请你自已设计一个算法，不要上网或看书找答案。二、程序的效率问题1 位运算符与效率Q3：&和&的区别是什么？答：&是位运算符，表示按位与运算，&是逻辑运算符，表示逻辑与（and）。C/C+中有很多位操作符，主要用途是：可以对机器的低层（寄存器等）进行直接操作。使用位操作符运算比字节运算有更好的效率。Q4：用最
8、有效率的方法算出2乘以8等於几?答：C语言有字位操作能力。答案是2 3。为什么2 3比2*8更快？结合本学期“组成原理”有关机器指令及指令周期理解此问题。Q5编写一个函数，计算一个十进制整数在内存中二进制表示形式的“1”的个数，比如十进制8的二进制形式为1000，有一个“1”。答：这个题是很难的。很多同学可能先想到把十进制整数转成二进制串，然后再统计其“1”的个数。这是种平庸的做法。其实一个十进制整数在内存中已经是二进制了，为什么不能直接测试呢？请大家再想一想。Q6第16题答案稍后再公布，看下一个题，这个题也很难。下面的程序，输入x=9999，函数的返回值是多少呢？程序为：int func （
9、 x ） int countx = 0; /计数初值为0 while ( x ) countx +; x = x&(x-1); /减一，AND return countx; 上面这个函数就是Q5的完美答案。参考答案：这个题在程序员面试攻略，有详细说明，网上流传的程序员面试题也有它的变型（先给出程序，让你判断它输入一个值的运行结果）。这个题需要对二进制有深入了解，这个题依据的原理是：如把给定整数减去1再与它的原值“与”，新整数只有最右面的“1”变成“0”。比如：01110000 AND （01110000-1）=01110000 AND 01101111=01100000，上面的原始数01110
10、000，只需进行三次减去1，并“与”的操作，即可变为00000000。这个程序的时间复杂度是O（M）的，M是给定整数在内存二进制中“1”的个数，算法效率非常高。大O计数法我们在“数据结构”中学过，是评估算法效率的重要工具，是我们必需掌握的。当你在面试时写出一个程序时，考官往往要求你评价该算法，对本科生而言，大O计数法是你唯一可用的专业评估工具（虽然大O计数法本身是粗略的）。上面的程序，输入x=9999，函数的返回值是多少呢？手工算一下。9999910245122561591024中含有1的个数为2；512中含有1的个数为1；256中含有1的个数为1；15中含有1的个数为4；故共有1的个数为8，
11、结果为8。这道试题非常经典，它即考了C语言效率，又考了二进制，但是它非常难。2、递归与效率 如果一个问题即可以用循环，也可以用递归求解，那么从理论上，两者的时间复杂度是等效的。但如果考虑到递归是重复的函数调用，这种开销很大，所以实际上递归时间复杂度远高于循环。而且重复的函数调用要占用大量的栈空间，递归算法的空间复杂度也相当高。上机习题3（选做）（1）求解河内塔（梵塔）问题，每加高一层塔，增加多少计算时间（可以使用C+标准库中的时间函数）？当塔加到一定高度，是否会出现栈溢出？（2）求解背包问题（请上网查资料）（3）求解八皇后问题（请上网查资料）3循环与效率Q7对于任意一个算法，降低其时间复杂度最
12、有效的办法是什么？答：减少循环嵌套。Q8：goto语句能提高程序的效率吗？为什么？Q9：一个函数内的goto语句能跳出函数体以外吗？参考答案：不能，绝大多数编译器限制goto只能做本地跳转。非本地跳转要用的C语言的一个头文件的函数（见课件附录1）。goto语句有时很有用，可以很快跳出循环，提高效率。小结：关于效率的问题，暂时先到这里，以后的课程再陆续讨论。三、程序的内部和外部结构1 程序的内部结构Q10：堆（Heap）与栈（stack）有什么区别？答：stack是先进后出，Heap是自由存储区。Stack的空间常由操作系统或编译器自动分配/释放，Heap上的空间常由程序员手动分配/释放。Sta
13、ck空间有限，Heap是很大的自由存储区。C中的malloc函数分配的内存空间即在堆上,用free释放。C+中对应的是new操作符分配内存，用析构函数释放内存。程序在编译期对局部变量和函数分配内存常在栈上进行,且程序运行过程中函数调用时参数的传递也在栈上进行。Stack效率要比Heap高。程序（确切说是进程）在内存中的结构大致为：栈：用来存放函数的形参和函数内的局部变量。堆：用来存放由动态分配函数（如malloc）分配的空间。是由程序员自己手动分配的，并且必须由程序员使用free释放。如果忘记，会导致所分配的空间一直占着不放，导致内存泄露。 全局区：用来存放全局量和静态量。存在于程序的整个运行
14、期间，是由编译器分配和释放的。 常量区：也由编译器控制分配和释放。 程序代码区：用来存放程序的二进制代码。Q11. 堆栈溢出一般是由什么原因导致的？答：没有回收垃圾资源。注意：C/C+是没有垃圾自动回收功能的。对于C语言，用malloc函数分配的内存，用完后必需要用free释放。对于C+，new操作符分配的内存（实例化的对象），必需用析构函数释放。Q12. 请问以下代码有什么问题：int main()char a;char *str=&a;strcpy(str,hello);printf(str);return 0;答：没有为str分配内存空间，将会发生异常。问题出在将一个字符串复制进一个字符
15、变量指针所指地址。虽然可以正确输出结果，但因为越界进行内在读写而导致程序崩溃。2 程序的外部结构Q13： C语言结构化程序设计所规定的三种基本控制结构是？A)输入、处理、输出B)树形、网形、环形 C)顺序、选择、循环D)主程序、子程序、函数 Q14：结构化程序设计的一种基本方法是？ A)筛选法B)递归法C)归纳法D)逐步求精法答：1968年Dijskstra在计算机通讯上发表文章，注意到了“结构化程序设计”，之后，Wulf主张“可以没有GOTO语句”。至1975年起，许多学者研究了“把非结构化程序转化为结构化程序的方法”，“非结构的种类及其转化”，“结构化与非结构化的概念”，“流程图的分解理论”等问题。结构化程序设计逐步形成既有理论指导又有切实可行方法的一门独立学科。SP（结构化）方法主张使用顺序、选择、循环三种基本结构来
