本章学习目标：

 1、对基本的运算符，理解优先级与结合性；

 2、掌握类声明、类定义的写法；

本章主要涉及两部分内容：

1、基本语句与表达式

 ppt中重点讲述了两个方面：

   （1）循环，条件等

这部分主要是注意括号的匹配，switch...case语句的break“闸刀”作用，contine在循环语句中的一跳等。

   （2）表达式

强调了运算符的优先级和结合性。

优先级：运算顺序

结合性：在左右有两个运算符的优先级相同时，先从哪个运算符开始。

我们常见的加、减法运算，优先级相同，结合性为左结合，也就是 从左到右。

例如： a + b - c  ，由于优先级相同，先加减后乘除，也就是 (a+b) - c。

又比如：

int a = 0; 

int* pa = &a; 

*pa++; 

分析*pa++;这行运算，*和++都是单目运算符，而且所有单目运算符优先级相同，且都是右结合，也就是先计算右边那个运算符++。

因此*pa++;相当于 *(pa++)，这就成了pa指向下一个内存空间。如果想通过pa的形式让a从0变成1，就需要下面这样写：

（*pa）++；

简单总结优先级和结合性：

  1）括号最高，逗号表达式最低

  2）赋值运算符优先级很低，仅高于逗号表达式

  3）在双目运算符中，赋值是唯一的右结合运算符

  4）单目运算符优先级很高，仅次于括号

  5）单目运算符优先级都相同，且为右结合

  6）？:是唯一的三目运算符，右结合

  （3）类声明、类定义

对于类的访问，有两种入口：一种是直接通过类的静态方法；另一种是通过类的变量（对象）

类是结构体的升级版，加入了函数，称之为成员函数，而struct类型中的分量属性，称之为数据成员。

将数据与对数据的操作合并放在一起，我们就自定义了一种新的类型，这种自定义类型比结构体更封装严谨，就不会说某个操作堆栈的push函数，会不小心被用户误操作去操作别的单链表去了。换句话说，类的定义（类型的声明）其实包含的两个含义：

   1）某类的成员函数，只能访问本类的数据成员；

   2）某类的数据成员，只能被本类的函数访问。

当然，上面说的不包括函数去访问全局变量（全局变量破坏了封装性，在现代语言中都已经取消了，比如java等）

类声明其实指的是类的数据成员和成员函数的声明。

  我们知道，在一个类的变量（对象被定义之前），类不过是一个类型的声明，虽然我们习惯上说定义了一个类，其实只是声明了一个类型或者说定义了一个类型（自定义类型），但这种声明比较特殊，因为它是不可重复的声明（类型定义是一种不可重复的声明）。

类定义其实是指类的数据成员的定义和成员函数的定义。

  我们知道，当我们定义一个类的变量，也就是定义了一个对象后（对象就是类这个类型的变量），对象的每一个分量，就是对象的每一个成员变量的定义。

  那么，函数的成员函数的定义，也对应于每个对象都会有一个这样的成员函数分量。

也就是说，一个对象的内存空间，其实是分代码段空间和数据段空间两部分的：前者是放函数代码的，后者是放数据成员的。

下面的例子：

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno();

  char* getName();

};  //千万不要掉了分号，因为类型定义其实是声明语法

红色部分这两个函数是声明，还需要它们的函数定义。蓝色的两个数据成员也是变量声明，还需要它们的变量定义。

下面定义一个全局对象 张三：

 Person zhangsan; //显然，zhangsan变量定义时，就自动定义了它的分量name和sno。

但这两个函数定义还没有找落。

一般有两种方法来安排函数的定义！

A 写在类型定义内部的隐式声明形式

  称为内联函数写法，

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno()  //注意这里不是分号结尾的声明，而是定义，可以看成隐式声明

  {...}

  char* getName() //注意这里不是分号结尾的声明，而是定义，可以看成隐式声明

  {...}

};

为什么我们说这种写法其实是隐式声明，因为这里写是它们的首次出现，也就是说，你写在类型定义里面，比如是被#include包含在别的cpp中的，比如出现在调用之前。出现在调用之前的定义，我们称为隐式声明。

B 写在类型声明外边的独立的定义体

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno();

  char* getName();

};  //注意分号

char* Person::getSno()

{...}

char* Person::getName()

{...}

注意到这两个函数是独立于类型声明的。所以我们成上半截绿色的为类声明，下半截紫色的是类定义。

在类型定义外部写成员函数定义时，需要加上类型前缀  类名::来表示函数的前缀

A/B两种写法可以进行混合，形成C这种形式：

例如：

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno()//内联写法的函数定义，隐式声明

  {...}  

  char* getName(); //显式函数声明

}; 

char* Person::getName() //getSno的定义

{...}

注意上面紫色的两个函数，一个用的内联写法给出的函数定义和隐式声明，一个用的显式声明和独立定义。

既然是定义就必然不可重复，所以对于混杂形式的写法，大家要注意不要出现定义缺失或重复。

类声明和类定义中的代码，都属于本类内部的代码。这个概念非常重要，牵涉到第4章我们描述访问属性的理解。

最后是第二章的笔记文档如下，一共两个：

  这个部分也就是我们常说的“三要素”。本章分三个二级标题。

  （1）对于函数声明、函数定义、函数调用不需赘述

  （2）对于变量声明、变量定义以及变量调用这里还是再行强调一下。

  在大多数程序语言中，变量的首次出现一般是以隐式声明出现的，也就是说，定义和声明合并的形式首次出现。

例如： 

  int a =1 ;

//我们说定义了一个变量a，初始化为1。也可以说声明了一个变量a，并定义为初始化值1。隐式声明

  a++;

//这里是对资源的访问，对变量我们称为使用和访问，对函数资源我们称之为调用。要声明在前。

只有全局变量，才有显式声明，而且，对于全局变量，我们强烈建议大家使用显式声明，这是为什么呢？

因为，全局变量需要跨文件使用，在多个cpp文件中的不同函数都需要访问这样的变量，就需要我们在每个cpp的头部#include变量的显式声明。注意不能是定义类型的隐式声明，否则的话就会造成多个cpp内各自定义了全局变量，造成了多处的重复定义。

全局变量的显式声明如下：

  external int global;//显式声明，可重复

全局变量的定义不应再任何{ }花括号表示的代码块内，而应是当exe被装载入内存后自动首先执行的全局代码。

全局变量的定义如下：

  int global ;// 定义，不可重复，当然，也可以给初始值

  （3）类声明、类定义

对于类的访问，有两种入口：一种是直接通过类的静态方法；另一种是通过类的变量（对象）

类是结构体的升级版，加入了函数，称之为成员函数，而struct类型中的分量属性，称之为数据成员。

将数据与对数据的操作合并放在一起，我们就自定义了一种新的类型，这种自定义类型比结构体更封装严谨，就不会说某个操作堆栈的push函数，会不小心被用户误操作去操作别的单链表去了。换句话说，类的定义（类型的声明）其实包含的两个含义：

   1）某类的成员函数，只能访问本类的数据成员；

   2）某类的数据成员，只能被本类的函数访问。

当然，上面说的不包括函数去访问全局变量（全局变量破坏了封装性，在现代语言中都已经取消了，比如java等）

类声明其实指的是类的数据成员和成员函数的声明。

  我们知道，在一个类的变量（对象被定义之前），类不过是一个类型的声明，虽然我们习惯上说定义了一个类，其实只是声明了一个类型或者说定义了一个类型（自定义类型），但这种声明比较特殊，因为它是不可重复的声明（类型定义是一种不可重复的声明）。

类定义其实是指类的数据成员的定义和成员函数的定义。

  我们知道，当我们定义一个类的变量，也就是定义了一个对象后（对象就是类这个类型的变量），对象的每一个分量，就是对象的每一个成员变量的定义。

  那么，函数的成员函数的定义，也对应于每个对象都会有一个这样的成员函数分量。

也就是说，一个对象的内存空间，其实是分代码段空间和数据段空间两部分的：前者是放函数代码的，后者是放数据成员的。

下面的例子：

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno();

  char* getName();

};  //千万不要掉了分号，因为类型定义其实是声明语法

红色部分这两个函数是声明，还需要它们的函数定义。蓝色的两个数据成员也是变量声明，还需要它们的变量定义。

下面定义一个全局对象 张三：

 Person zhangsan; //显然，zhangsan变量定义时，就自动定义了它的分量name和sno。

但这两个函数定义还没有找落。

一般有两种方法来安排函数的定义！

A 写在类型定义内部的隐式声明形式

  称为内联函数写法，

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno()  //注意这里不是分号结尾的声明，而是定义，可以看成隐式声明

  {...}

  char* getName() //注意这里不是分号结尾的声明，而是定义，可以看成隐式声明

  {...}

};

为什么我们说这种写法其实是隐式声明，因为这里写是它们的首次出现，也就是说，你写在类型定义里面，比如是被#include包含在别的cpp中的，比如出现在调用之前。出现在调用之前的定义，我们称为隐式声明。

B 写在类型声明外边的独立的定义体

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno();

  char* getName();

};  //注意分号

char* Person::getSno()

{...}

char* Person::getName()

{...}

注意到这两个函数是独立于类型声明的。所以我们成上半截绿色的为类声明，下半截紫色的是类定义。

在类型定义外部写成员函数定义时，需要加上类型前缀  类名::来表示函数的前缀

A/B两种写法可以进行混合，形成C这种形式：

例如：

class Person

{

  char* name;//姓名

  char* sno;//学号

  char* getSno()//内联写法的函数定义，隐式声明

  {...}  

  char* getName(); //显式函数声明

}; 

char* Person::getName() //getSno的定义

{...}

注意上面紫色的两个函数，一个用的内联写法给出的函数定义和隐式声明，一个用的显式声明和独立定义。

既然是定义就必然不可重复，所以对于混杂形式的写法，大家要注意不要出现定义缺失或重复。

类声明和类定义中的代码，都属于本类内部的代码。这个概念非常重要，牵涉到第4章我们描述访问属性的理解。

实验1的目的：

    A、多文件工程的方法

 首先要明确前两次课一个教学重点，即多文件工程的创建顺序。这里简要复习总结一下：

1、新建工程后，首先应该创建的第一个调用体文件，也就是程序的主控入口，我们一般习惯命名为main.cpp（文件命名是任意的，只要不是中文名都好），其内含有特殊的程序执行入口函数main，它是一个静态函数（学习过java的同学会明白，main其实是一个全局的静态static函数）。

注意不要在调用体中花太多时间去修饰输入界面，那些都没有用，因为程序员的职责是写好声明体和定义体，调用体其实是用户调用，他会自行编写一个新的调用体。我们构造这个main.cpp调用体，是我们程序员自行虚构一个调用，来测试自己的实现是否正确而已；

2、编译main.cpp，修改编译错误（在compile小窗中从最上面的错误开始双击，对应修改），成功生成main.obj方可。一般最常出现的错误除了拼写，就是声明不匹配：比如没有声明就调用了函数，没有声明就访问了变量等。为了编译调用体成功，需要构造声明体，比如f.h；

所以大家一定要强化认知：声明是调用前的授权，声明必须出现在调用/使用之前

3、如上所述，编写第二个文件f.h，构造和调用形式需要的授权类型（含函数名，参数类型，参数表中参数的个数等，注意不包括返回值类型）；

4、当编写好授权声明并在main.cpp中头部#include "f.h"后，编译main..cpp成功，生成main.obj；

5、编写最后第三个文件，也就是提供服务的函数定义f.cpp。

这个函数的编写一般来说是程序中的核心功能所在，也是难度最大的地方。但是只要前面的框架正确，我们即使是编程题，也是三个文件完成两个就是三分之二的分值会给。所以大家先学好规范！

  B、递归思想解决问题

  很多问题的解决，都可以简单用递归思想来思考，从而导出算法思想。但递归往往算法效率不高，后期需要我们优化算法解决。

  只要问题的规模能够缩小，那么递归一定就能解决问题。

第一题：主要是对不同文件创建粘贴复制对应内容。

  1、这个实验第一考察我们一个程序编程三个文件的能力。也就是不要再写一个整个的文件程序，而要拆分为多文件工程。

好处在于：能够分而治之的减少考虑的问题。

首先写调用体，也就是测试代码该怎么写，测试数据怎么给；

然后写为了让调用体能够编译成功，应该申请什么样的资源放在头上，也就是头文件(.h)改怎么写；

最后写定义体，也就是实现被调函数。

首先写调用体如下：

2、程序应该逐步写大，调用体可以调用一行，写一行被调用的声明，然后是被调用函数的定义。

其次编写声明体如下：

#include <stdio.h>

void func(int,int);

3、编写定义体如下：

//注意每个源程序文件（.cpp/.c都要独立compile编译成功，

//才能进行下一步build链接生成exe的动作） 

小视频如下：

第二题：

先给一个视频，给了实现过程的一部分，也就是简单复制粘贴之后，在交换函数func.cpp的内部加了测试语句发现是正确的交换，但交换的并非外部的main::a和main::b。

既然根源在函数调用不对，函数实现交换的对象不对 ，那么 我们就要直接操作main::a和main::b本身，而不是复制之后的内部变量func::a和func::b。

这就好比，我们必须传递main::a和main::b的房间号，然后到func函数内到这个房间去操作。这就涉及到 地址的概念：

  int a ;这是整型变量的定义，&a是这个变量入住内存房间的房间号，也就是地址 ；

 int *pa = &a; 这是顶一个了另外一个变量，来复制a变量的房间号，方便后面继续处理

那么*pa，其实就是a。为什么不直接继续用a而必须使用*pa来表示a呢，因为在新的函数func内，已经不能继续访问main::a了。这涉及到变量的作用域问题。就好比是A班的资源，不能到B班直接用一样。但可以间接被访问，不能直接看到。我们现在就是要在B班来操作改变A班的资源，也就是在func.cpp内改变main::a和main::b。

下面是改正的视频：

/*

1中的func未能正确交换两个整数，利用指针以工程项目的形式给出正确的交换函数程序。

问题出在函数的实现不对，也就是func.cpp不对，也可能是由于函数实现需要不同的参数传递。

其他文件直接新建空白文件以后，复制粘贴。

*/

首先是调用体main.cpp

#include "func.h"

int main()

   {

     int a=5,b=6;

     printf("即将调用func! ");

     printf("传递给处理前的参数是%d,%d ",a,b);

     func(&a,&b);//传递main::a和main::b的房间号给func.cpp文件继续处理

//那么就要对应修改授权声明

     printf("退出func!");

     printf("传递给处理后的参数是%d,%d ",a,b);

     return 0;

   }

/*

我们使用了指针类型，来传递变量的地址，也就是房间号，目的就是直接操作变量本身，而不是操作被拷贝的那份；

当然，这里仍然发生了复制，只是复制了房间号地址而已。

*/

然后是func.h声明体：

#include <stdio.h>

void func(int*,int*);//注意房间号对应的类型是地址类型，整型变量的房间号类型就是int*

最后是定义体：

//注意每个源程序文件（.cpp/.c都要独立compile编译成功，才能进行下一步build链接生成exe的动作） 

void func(int* pa, int* pb)

//这里发生值传递：

//int*pb = &main::b 

//int*pa = &main::a

   {

     int temp= *pa;//这里是a、b发生交换，不是main中的a和b发生交换

     *pa=*pb;

     *pb=temp;

  }

第三题：

3、根据以下递归语句直接编写求最大公约数gcd程序。

   gcd(a,b)=gcd(b,a%b)

很显然这里给出了辗转相除的递归式，但没有给出递归出口，需要我们加上f条件，否则会有递归无限循环。

下面有一个视频，从简单的数值入手，来想象如何设计递归出口。

视频中gcd. cpp还有最后一行没有写，大家想想，该加的一行是return谁呢？

第四题：

4、将3改写为非递归形式的程序。

首先给出第3题的核心函数实现gcd.cpp代码如下：

 int gcd(int m ,int n)

{

        int ret = 1;

if (n != 0) //当第二个参数不为0，开始递归

ret = gcd(n,m%n);

//当n为0时，就直接返回第一个参数，它就是最大公约数。

else ret = m;

        return ret;

}

为确保正确，我们还是使用了debug（调试）技巧，通过设置break point（断点），step into进我们希望了解的gcd函数内部，step over直接执行跳过我们认为肯定正确的语句。快速找出运行不正确的原因所在。

因此，我们还明白，除了每个cpp源程序可能发生编译错误，还可能会发生所有obj链接错误（无法形成一个整体的exe生成），最后还可能会有运行结果不正确的运行错误。断点调试，就是对付运行错误的利器。

下面的视频中，首先加入了一行返回参数的，结果发现运行结果不对，gcd(2,6) = 0的输出，于是设置了断点，跟踪进入函数，最后发现是return m写成了return  n。

这个最大公约数的求法是递归求解，为什么用递归，是因为递归算法相对容易获得。比如我们熟知的fibonacci数列，当前项=前两项之和。

fib(1) = 1

fib(2) = 2

fib(n) = fib(n-1) + fib(n-2) n>2

根据上面的式子，是很容易改写为递归函数的定义：

int fib(int n)

{ int ret = 1;

  if (n ==1) 

    ret = 1;

 if (n ==2)

    ret =  2;

 else  ret = return fib(n-1) + fib(n-2);

 return ret;

}

录屏如下：

但大家很容易发现一个现象，当n取较大的数，比如50时，程序很像死循环一样很久很久不出结果。至少等到三节课下了也不会有结果。说明递归实现很有缺陷，虽然算法正确，但似乎时间复杂度太差。

这个我们可以简单用特征方程求数列n项，发现原来是一个指数函数的时间复杂度，也就是说大约是O(2的n次方)的时间复杂度。我们知道，底数大于1的正整数的指数函数是上升极快的递增函数，这样的算法效率基本被认为是没有用的算法。

所以需要改写为非递归，才有应用价值。

这个fib改写为非递归的提供给大家为本次实验的作业。

下面的gcd的改写非递归的录屏视频：

从递归的迭代来看，就是不断的用新的实参去递归调用，将if改为循环即可解决。

第五题：

5、给定一个整型的从小到大排好了序的数组a[n]，要求对输入的任意整数在该数组中查找并返回其下标

这是一个简单的数组查找问题。同样的，可以简单归一为递归问题。

  从start到end顺序检查数组a查找x:

  search(a, start, end, x) ==>if (a[start]!= x) search(a, start+1, end, x)

于是一个数组长度为n的问题，缩减问题规模为n-1。

程序略。

6、将上述优化为二分查找问题（因为数组已经有序）

biSearch(a, start, end, x)=

      start                                      (start==end)&&a[start]==x)

         -1                             (start==end)&&a[start]!=x)

      biSearch(mid+1,end,x)                x>a[mid](其 (start==end)&&a[start]!=x)中mid=(start+end)/2)

      biSearch(start,mid-1,x);              x<a[mid](mid定义同上)

程序略

7、将6改为非递归

从gcd和fibonacci的例子，可以设计循环来解决，观察6中的递归调用，发现每次发生变更的是start和end下标，并总是重新求解mid。

8、爬楼梯问题。

这同样是一个递归思想问题：

  第一步该怎么做？或者最后一步该怎么做？

  step = step(n-1) + step(n-2) + step(n-3)   n>3

如果要改为非递归，又该如何做呢？留给大家自行练习。