递归 -- 字符串处理-----指针/地址的传递---ADT : 算法分析与设计

递归 -- 字符串处理-----指针/地址的传递---ADT : 算法分析与设计

• 【递归例题1】上楼梯问题。用递归方法编写函

数f(n)：一共有n个台阶，某人上楼一步可以跨1个台

阶，也可以跨2个台阶，问有多少种走法。详细解释

思路和算法。

分析如下：

（1）当n=1时，共1种走法；

（2）当n=2时，可以一步一个台阶，也可以一步走

完2个台阶，共2种走法；

（3）假设已经知道n-1时的走法（当然也知道知道

n-2时的走法），那么当n时，可以归结为两种情况：

（a）一步1个台阶，剩n-1个台阶；

因此f(n)=f(n-1)+f(n-2)

（b）一步2个台阶，剩n-2个台阶。

#include <stdio.h>

#include <string.h>

int f(int n)

{

if (n==1)

return 1;

else if (n==2)

return 2;

else

return f(n-1)+f(n-2);

}

main( )

{ int m,n;

scanf("%d", &n);

printf("T=%d\n", f(n));

}

• 【递归补充例题2B】上楼梯问题的拓展。用递归方法

编写函数f(n,m)：一共有n个台阶，某人上楼可能一

步可以跨1个台阶，也可以跨2个台阶，最多一步跨m

个台阶，问有多少种不同走法。详细解释思路和算法。

有人提出了另一种思路，分析如下：

(1)当n=1或者m=1时，共1种走法；

(2)当n<m时，一步最多n个台阶，因此f(n,m)=f(n,n)

(3)当n=m时，可以一步走m个台阶，共1种走法,也可以

不一步走m个台阶，有f(n,m-1)种走法，因此

f(n,m)=f(n,m-1)+1

(4)当n>m时，可以一步走m个台阶，有f(n-m,m)种

走法;也可以一步走小于m个台阶，有f(n,m-1)种走

法; 因此

f(n,m)=f(n-m,m)+f(n,m-1)

#include <stdio.h>

int f(int n, int m)

{

if (n==1 || m==1) return 1;

else if (n<m) return f(n,n);

else if (n==m) return f(n,m-1)+1;

else

return f(n-m, m)+f(n,m-1);

}

main()

{ int m,n;

scanf("%d%d", &n, &m);

printf("T=%d\n", f(n,m));

}

运行结果：

3 2

T=2

请按任意键继续. . .

10 2

T=6

请按任意键继续. . .

30 3

T=91

请按任意键继续. . .

30 4

T=297

请按任意键继续. . .

结果显然不

对，问题出

在哪里？？

因为递归式：

f(n,m)=f(n-m,m)+f(n,m-1)

中f(n,m-1)意味着，如果第

一步没跨m个台阶，以后只能

一步跨小于m个台阶，这是不

合理的。

• 【递归补充例题3】用递归方法编写函数：把M个同样

的苹果放在N个同样的盘子里，允许有的盘子空着不

放，问共有多少种不同的分法？当M=7，N=3时，视

5,1,1和1,5,1为同一种分法。详细解释思路和算法。

解题思路：所有不同的摆放方法可以分为两类：至少

有一个盘子空着和所有盘子都不空。分别计算这两类

摆放方法的数目，然后把它们加起来。

设f(m,n)为m个苹果n个盘子的摆法数，如果n>m，

必定有n-m个盘子要空着，去掉它们对摆法数不产生

影响；即n>m时,f(m,n)=f(m,m)。当n<=m时，不同的摆

法可以分成两类：即有至少一个盘子空着，相当于

f(m,n)= f(m,n-1)；或者所有盘子都有苹果，每个盘

子至少要先放一个苹果，即f(m,n)=f(m-n, n) 。总的

放苹果的放法数目等于两者的和，即

f(m,n)=f(m,n-1)+f(m-n,n)

算法：

(1)当m=1或n=1时，只有1种摆法, f(m,n)=1;

(2)当m=n时，可以分为两种情况：一是每个盘子放

一个，只有1种摆法；二是第n个盘子不放，有

f(m,n-1)种摆法。因此f(m,n)= f(m,n-1)+1;

(3)当n>m时，必定有n-m个盘子要空着。因此

f(m,n)=f(m,m);

(4)当n<m时,可以分成两类：一是至少一个盘子空着，

相当于f(m,n)=f(m,n-1)；二是所有盘子都有苹果，

每个盘子至少要先放一个苹果，即f(m,n)=f(m-n,n)。

总的摆法数等于两者的和，因此

f(m,n)=f(m,n-1)+f(m-n,n)。

#include <stdio.h>

int f(int m,int n)

{

if(m==1||n==1)

return 1;

else if(m==n)

return f(m,n-1)+1;

else if(n>m)

return f(m,m);

else

return f(m,n-1)+f(m-n,n);

} void main( )

{ int m,n,c;

printf("Input m and n:");

scanf("%d%d", &m, &n);

c = f(m, n);

printf("C=%d\n", c);

}

运行结果：

Input m and n:5 3

C=5

请按任意键继续. . .

Input m and n:7 3

C=8

请按任意键继续. . .

Input m and n:10 4

C=23

请按任意键继续. . .

Input m and n:50 10

C=62740

请按任意键继续. . .

• 【字符串处理补充例题4】去除C代码中的注释

C代码中有两种注释，/* */和//。编译器预编译时

先移除注释。就是把/*和*/之间的部分去掉，把//

以及之后的部分删掉。这里约定一样，如果出现了

/* AAAA /* BBBB */的情况，也就是/* */中出现

了/*，那么第二个/*是不当作注释起始的。

编写函数void removeComment(char *str)

分析：对于字符串

”int c=4,/*c累计量*/ a=3;/*变量*/ // a初值为3 ”

先用strstr函数在str中确认”/*”是否出现过，是则确

认”*/”是否出现过,是则把str中字”*/”出现位置后2个

字符起始的字符串复制到str中”/*”出现的位置，循环查

找直到找不到”/*”为止；用strstr在str中确认”//”是否

出现过，是则把出现”//”的位置置为’\0’。

#include <stdio.h>

#include <string.h>

void removeComment(char *str)

{ char *p=str, *q;

while ((p=strstr(p, "/*")) != NULL)

{ q=strstr(p, "*/");

if (q != NULL)

strcpy(p, q+2);

}p

= strstr(str, "//");

if (p !=NULL)

*p = '\0';

} void main()

{ char s[]=“int c=4, /*c累计量*/ a=3; /*变量*/ // a初值为3”;

removeComment(s);

printf("%s\n", s);

}

运行结果：int c=4, a=3;

• 【字符串处理补充例题5】去除字符串中非字母字符

编写函数void FilterNonChar (char *str)

对于字符串

str= ”int c=4,/*c累计量*/ a=3;/*变量*/ // a为3 ”

最后结果应该是：

str= ”intccaa”

分析：

设循环变量k从0到strlen(str)循环，逐个字符判断

str[k]是否为字符，是留下，向前移动，不是忽略

for(k=0; k<strlen(str); k++)

if (str[k]>=‘a’&&str[k]<=‘z’

|| str[k]>=‘A’&&str[k]<=‘Z’)

// if (isalpha(str[k])) // 此函数隶属于ctype.h

#include <stdio.h>

#include <string.h>

#include <ctype.h>

void FilterNonAlpha(char *str)

{ int k, n=0;

for(k=0; k<strlen(str); k++)

//if (str[k]>='a'&&str[k]<='z'|| str[k]>='A'&&str[k]<='Z')

if (isalpha(str[k]))

str[n++]=str[k];

str[n] = ‘\0’; /* 设置新的字符串尾

} void main()

{ char s[]="int c=4,/*c累计量*/ a=3;/*变量*/ // a初值为3";

FilterNonAlpha(s);

printf("%s\n", s);

}

运行结果：

intccaa

请按任意键继续. . .

C++简介

•1983年, 美国AT&T公司Bell(新泽西)实验室的

Bjarne Stroustrup在C语言的基础上研制了C++

•他现在是美国Texas A&M大学CS系的教授，同

时仍是AT&T Fellow, 主页:

http://www2.research.att.com/~bs/

•最初1980年被称为多(带)类C（C with Class），

1983年正式命名为C++。从1989年开始C++的

标准化工作，1994年出了ANSI C++标准，

1998年11月ISO批准为ISO C++ 标准: C++98

(ISO/IEC 14882)。2011年8月ISO批准的最新

C++标准是：C++11(ISO/IEC 14882:2011)

C++被称为面向对象的程序设计语言

OOPL(Object-Oriented Programming Language)

C是C++的子集，C++保持了C的原始思想，程序员

写程序时可用也可以不用C++所增加的功能。

C++在C的关键字的基础上增加了：catch, class, const,

delete, friend, inline, new, operator, private, protected,

public, template, this, throw, try, typeid, virtual,

volatile 等关键字

C++增加的最重要的机制有三个：

•类(class)

•函数重载(function overloading)

•操作符重载(operator overloading)

主要目的：

1. 用于大型软件(指源程序超过5万行)的开发

2. 解决C语言程序访问权限不受任何限制而导

致的副作用严重的问题:

 全局变量全局可见可任意访问

 不检查数组越界

3. 生成严格控制存取权限的“黑盒子功能单元”

---对象（object）

• 动态内存分配

C++用new和delete动态分配和释放内存，等同于C

的malloc和free函数，但new和delete功能更强大。

例如：

int *p=new int(10);

//分配1个int单元,并赋初值为10

等同于C的：

int *p=(int *)malloc(sizeof(int)); *p = 10;

C++用：

delete p; // 释放p所指的1个int单元

等同于C的：

free(p);

int *pt=new int[10]; // 分配10个int单元，

// 即pt是一个动态数组，pt[0]~pt[9]

等同于C的：

int *pt = (int *)malloc(sizeof(int)*10);

C++用：

delete []pt;

释放pt所指的10个连续int单元，等同于C的：

free(pt);

int (*pt)[10]=new int[8][10]; //分配80个int单元

// pt是一个二维动态数组，pt[0][0]~pt[7][9]

等同于C的：

int (*pt)[10];

pt = (int (*)[10])malloc(sizeof(int)*8*10);

C++用：

delete []pt;

释放pt所指的80个连续int单元，等同于C的：

free(pt);

int **q = new int *[10]; //分配10个int指针单元

// q是一个一维动态指针数组，q[0]~q[9]

等同于C的：

int **q;

q = (int **)malloc(sizeof(int *)*10);

C++用：

delete []q;

释放q所指的10个连续int指针单元，等同于C的：

free(q);

• 指针/地址的传递

C的参数传递只是传值,无法将变量地址传递到

函数中。

除非通过显式的指针方式传递

C++提供了传递变量地址这种机制

方法是: 在函数头中要传递地址的变量前加&

而函数调用方式不变。

这样在被调用函数中对声明传递变量地址的变

量的赋值操作直接是对调用函数中相应变量

的操作。

例如：交换两个变量的值(C版本)

#include <iostream>

using namespace std;

void swap(int a, int b) // 将a，b变量的值交换

{ int t=a;

a=b; b=t;

}

void main( )

{ int i=3, j=5;

swap(i, j); //交换i, j的值

cout << i << " "<< j<<endl ;

}

输出结果将是：3 5 a和b的值并未交换

除非改成指针方式：

#include <iostream>

using namespace std;

void swap(int *a, int *b)

{ int t=*a;

*a=*b; *b=t;

}

void main( )

{ int i=3, j=5;

swap(&i, &j); //交换i, j的值

cout << i << " "<< j<<endl ;

}

输出结果将是：5 3 // a和b的值已经交换

采用声明传地址方式：

#include <iostream>

using namespace std;

void swap(int &a, int &b) // 声明传递a，b变量的地址

{ int t=a;

a=b;

b=t;

}

void main( )

{ int i=3, j=5;

swap(i, j); //交换i, j的值

cout << i << " "<< j<<endl ;

}

输出结果将是：5 3 // a和b的值已经交换

又例如：交换两个指针变量的值

#include <iostream>

using namespace std;

void swap(int *a, int *b) // 将a，b指针变量的值交换

{ int *t;

t=a; a=b; b=t;

}

void main( )

{ int i=3, j=5, *p=&i, *q=&j; // p指向i，q指向j

swap(p, q); //交换p, q指针的值, 让p指向j，q指向i

cout << *p << " "<< *q<<endl ;

}

输出结果将是：3 5 // p和q的值并未交换

除非传指针变量的地址

#include <iostream>

using namespace std;

void swap(int **a, int **b) // 将a,b指针变量的值交换

{ int *t;

t=*a; *a=*b; *b=t;

}

void main( )

{ int i=3, j=5, *p=&i, *q=&j; // p指向i，q指向j

swap(&p, &q); //交换p, q指针的值, 让p指向j，q指向i

cout << *p << " "<< *q<<endl ;

}

输出结果将是：5 3 // p和q的值已交换

传指针变量地址

#include <iostream>

using namespace std;

void swap(int *&a, int *&b) // 将a,b指针变量的值交换

{ int *t;

t=a; a=b; b=t;

}

void main( )

{ int i=3, j=5, *p=&i, *q=&j; // p指向i，q指向j

swap(p, q); //交换p, q指针的值, 让p指向j，q指向i

cout << *p << " " << *q<<endl ;

}

输出结果将是： 5 3 p和q的值已经交换，p指向了j,

q指向了i，但i=3, j=5不变

指针/地址的传递(续1)

引用机制:

引用是一种特殊类型的变量,可以认为是给一

个变量起别名。

int i, j;

int &r=i; // 变量引用，r和i是同一个内存单元

// r不能再改变引用,可以认为r是i的别名

int *p=&i;

i=10;

j=r; // 等价于j=i

*p = 20; // 等价于i=20

#include <iostream>

using namespace std;

void main( )

{ int i=10, j=20, k=30, *p=&i;

int *&q=p;//指针引用，q和p是同一个指针单元

// q不能再改变引用, 可以认为q是p的别名

cout << *p << ' ' << *q << endl;

p = &j;

cout << *p << ' ' << *q << endl;

q = &k;

cout << *p << ' ' << *q << endl;

}

10 10

20 20

30 30

• 作用域与可见性

在C语言中可以出现局部变量和全局变量同名

但函数中的局部变量将掩蔽全局变量（mask)

直到局部变量的作用域失效，才能访问同名的

全局变量，

而实际应用中可能需要同时访问同名的局部变

量和全局变量

C++为了克服这个缺点，引入了作用域操作符

(scope operator)‘::’，使我们可以同时访问同

名的局部变量(max)和全局变量(::max)。

例如:下例中max是局部变量, ::max是全局变量

#include <iostream>

using namespace std;

const int max=10000;

void main( ) // 从键盘上读入10个数，求最大值max输出,但最大不超过10000

{ int max, i,j;

cin >> max;

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

{ cin >> i;

if (i>max) max = i;

if (max > ::max) max = ::max;

}

cout << max<<endl;

}

若max大于外部变量max的值，则取外部常量max的值,

通常用来防止数组越界或溢出

• 数据抽象（data abstraction）

•将数据类型与操作分开，被称为数据抽象

•例如：栈操作，操作对象的类型可以是

int,long, float, double等等，但不考虑类型，

就可以成为一个数据抽象－－－栈操作，

可以由此写出一个栈操作模板，适用于任

何数据类型的栈操作

例如： T abs(T i)

{ return i<0?-i:i; }

abs是一个函数模板，可对任意类型的数据求绝

对值，只要此数据可以和0比较大小

• 对象（object）

•将一个(组)变量，以及作用于这些变量的一

个(组)函数封装为一个单元，这个单元就被

称为对象，同类对象的抽象(共同特性)被称

为类，类的实例化称之为对象

•对象具有封闭性，可以自己控制外界对他

的访问权限，从而严格控制对其中被封装

变量的访问