【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

举报
春人. 发表于 2023/11/28 01:02:45 2023/11/28
【摘要】 前言: 相信大家在学习C语言的时候,最头疼的就是指针,经常会碰到一级指针、二级指针,这些指针使用起来,稍有不慎就会等导致程序崩溃,为了让广大程序员少掉点头发,C++中提出了引用这一概念。当然,在C++的代码中,仍然可以兼容C语言的指针。一、引用的概念 在语法上引用不是新定义一个变量,而是给已存在的变量取一个别名,编译器不会为引用变量开辟内存空间,它和它引用的变量共用同一块空间。例如:鲁迅和周...

前言:
 相信大家在学习C语言的时候,最头疼的就是指针,经常会碰到一级指针、二级指针,这些指针使用起来,稍有不慎就会等导致程序崩溃,为了让广大程序员少掉点头发,C++中提出了引用这一概念。当然,在C++的代码中,仍然可以兼容C语言的指针。


一、引用的概念

 在语法上引用不是新定义一个变量,而是给已存在的变量取一个别名,编译器不会为引用变量开辟内存空间,它和它引用的变量共用同一块空间。例如:鲁迅和周树人都是同一个人。
在这里插入图片描述

  • 类型& 引用变量名(对象名)= 引用实体
int main()
{
	int a = 0;
	int& b = a;//定义引用类型,b是a的引用
	int& c = a;
	return 0;

 通过汇编指令实现的角度看,引用底层是类似指针的方式实现的,如下图所示:
在这里插入图片描述

二、共用同一块空间验证

int main()
{
	int a = 0;
	int& b = a;
	int& c = a;
	cout << &a << endl;
	cout << &b << endl;
	cout << &c << endl;
	return 0;
}

在这里插入图片描述
 通过上面打印的结果可以看出,引用变量的地址和引用实体的地址是一样的,说明引用其实就是给同一块内存空间上取别名。

int main()
{
	int a = 10;
	int& b = a;
	int& c = a;
	b++;
	cout << a << endl;
	cout << b << endl;
	cout << c << endl;
	return 0;
}

在这里插入图片描述
 上面代码,对其中一个引用变量++,其他三个变量的值也发生了改变,这也能说明引用是给同一块内存空间取别名。

三、引用的特性

3.1 引用在定义时必须初始化

int main()
{
	int a = 10;
	int& d;//不能这样
	return 0;
}

在这里插入图片描述
 上面的代码是不被允许的,因为在定义引用变量b的时候,没有初始化。

3.2 一个变量可以有多个引用

int main()
{
	int a = 10;
	int& b = a;
	int& c = a;
	return 0;
}

 上面代码中,bc都是a变量的引用。这一点很容易理解,就像同一个人可以有多个外号一样,一个变量也可以同时有多个引用。

3.3 引用不能改变

 引用一旦引用一个实体,不能再引用其它实体。

int main()
{
	int a = 10;
	int num = 100;
	int& b = a;
	int& c = a;
	b = num;//这里是把num的值赋给a,并不是让b变成num的引用
	cout << "变量a的地址:" << &a << endl;
	cout << "引用b的地址:" << &b << endl;
	cout << "变量num的地址:" << &num << endl;
	return 0;
}

在这里插入图片描述
 上面代码中的b = num,是把num变量的值赋值b引用的实体,并不是让b变成num的引用。通过打印地址可以证明这一点,引用b的地址和变量a的地址一样,说明b任然是a的引用。这类似于终身制,引用一旦和实体绑定就不能再分离。
 这里还需要注意一点:给引用b赋值,引用实体a也是会跟着发生改变的,就像周树人吃了午饭,那鲁迅必定也吃了,不可能出现周树人吃了午饭,而鲁迅还饿肚子的情况。

四、引用的使用场景

4.1 做参数

 引用做参数有以下两个方面的意义:

  • 做输出型参数,即要求形参的改变可以影响实参
  • 提高效率,自定义类型传参,用引用可以避免拷贝构造,尤其是大对象和深拷贝对象(后续文章会讲到)

交换两个整型变量:

void Swap(int& num1, int& num2)
{
	int tmp = num1;
	num1 = num2;
	num2 = tmp;
}

int main()
{
	int a = 10;
	int b = 11;
	cout << "a:" << a << " " << "b:" << b <<  endl;
	Swap(a, b);
	cout << "a:" << a << " " << "b:" << b << endl;
	return 0;
}

在这里插入图片描述

 上面代码,利用引用做参数实现了两个数的交换,以前交换两个数的值,需要进行值传递,也就是实参去两个数的地址,形参用指针来接受。而用引用做参数后,实参无需再传递地址,形参num1是变量a的引用,和a表示同一块内存空间,形参num2是变量b的引用,和b表示同一块空间,因此在函数体内交换num1num2实际上就是交换ab
交换两个指针变量:

void Swap(int*& p1, int*& p2)
{
	int* tmp = p1;
	p1 = p2;
	p2 = tmp;
}

int main()
{
	int a = 10;
	int b = 11;
	int* pa = &a;
	int* pb = &b;
	cout << "pa:" << pa << " " << "pb:" << pb <<  endl;
	Swap(pa, pb);
	cout << "pa:" << pa << " " << "pb:" << pb << endl;
	return 0;
}

在这里插入图片描述
 如果用C语言来实现交换两个指针变量,实参需要传递指针变量的地址,那形参就需要用二级指针来接收,这显然十分繁琐,且容易出错。有了引用之后,实参直接传递指针变量即可,形参用指针类型的引用(指针也是一种类型)。
链表新玩法:
 之前用C语言实现的链表,在进行尾插、头插、头删等操作的时候,因为可能会涉及到对头节点的修改,因此在传参的时候,用的是指向头节点的指针的地址,也就是一个二级指针,如下:

SLTNode* node;//创建一个链表,其实只是定义了一个头节点
SLTPushBack(&node);//调用尾插函数,传递的是头指针的地址
void SLTPushBack(SLTNode** pphead,SLTDataType x)//函数原型

 在有了引用之后,可以对代码做如下修改:

SLTNode* node;//创建一个链表,其实只是定义了一个头节点
SLTPushBack(node);//调用尾插函数,直接传递头指针
void SLTPushBack(SLTNode*& pphead,SLTDataType x)//函数原型

 还可以对结构体指针类型进行重定义,像下面这样:

typedef struct SListNode
{
	SLTDataType data;//数据域
	struct SListNode* next;//指针域
}SLTNode, *PSLTNode;//对结构体指针类型进行重定义

PSLTNode node;//创建一个链表,其实只是定义了一个头节点
SLTPushBack(node);//调用尾插函数,直接传递头指针
void SLTPushBack(PSLTNode& pphead,SLTDataType x)//函数原型

 很多数据结构书上都是采用第三种写法,导致很多新手朋友学起来比较蒙,其本质上就是利用了C++中引用这一概念。

4.2 做返回值

 先来回顾下,普通的传值返回。

int add(int x, int y)
{
	int sum = x + y;
	return sum;
}

int main()
{
	int a = 5;
	int b = 4;
	int ret = add(a, b);
	return 0;
}

 上面代码中的add函数,实现了一个简单的两数求和,要将求和结果sum返回给调用它的地方,这里采用的是传值返回,由于sum是函数中的一个局部变量,存储在当前函数的栈帧中,随着函数调用结束栈帧销毁,sum也会随之灰飞烟灭。因此,对于这种传值返回,会生成一个临时的中间变量,用来存储返回值,在返回值比较小的情况下,这个临时的中间变量一般就是寄存器,下面通过调试来验证:
在这里插入图片描述
 不仅函数中的普通局部变量在传值返回的时候会创建临时的中间变量,函数中static修饰的静态变量,虽然存储在内存中的静态区,不会随着函数调用结束而销毁,但是在传值返回的时候,同样会创建一个临时的中间变量,以下面的代码为例:

int Text()
{
	static int a = 10;
	return a;
}

int main()
{
	int ret = Text();
	return 0;
}

在这里插入图片描述
 尽管函数中的a是一个静态变量,没有存储在当前函数调用的栈帧中,但是在返回a的时候,还是创建了一个临时的中间变量来存储a。因此可以得出结论:

  • 只要是传值返回,编译器都会生成一个临时的中间变量。
  • 临时的中间变量具有常性。

传引用返回:
 和传值返回不同,传引用返回不需要创建临时的中间变量,但前提是,在函数调用结束,函数栈帧销毁后,返回的变量任然存在。换句话说就是,返回的变量不能存储在函数调用所创建的栈帧中,即返回的变量,不能是普通的局部变量,而是存储在静态区的静态变量,或是在堆上动态申请得到的变量。
局部变量传引用返回存在的问题:
 引用即别名,传引用返回,就是给一块空间取了一个别名,再把这个别名返回。一个局部变量的空间,是函数栈帧的一部分,这块空间会随着函数调用结束,函数栈帧的销毁而销毁,因此给这块空间取一个别名,再把这个别名返回给调用它的地方,这显然是有问题的,因为这块空间已经被释放了,归还给了操作系统。

int& add(int x, int y)
{
	int sum = x + y;
	return sum;
}

int main()
{
	int a = 5;
	int b = 4;
	int ret = add(a, b);
	cout << ret << endl;
	return 0;
}

在这里插入图片描述
 还是上面这个求和代码,sum是一个局部变量,但是传引用返回,结果貌似没有什么问题,这是为什么呢?其实,sum标识的这块空间在函数调用结束,确确实实是归还给了操作系统,但是操作系统并没有将里面存储的内容清理,这就导致打印出来的结果貌似是正确的。可以对上面的代码稍作修改,继续验证:

int& add(int x, int y)
{
	int sum = x + y;
	return sum;
}

int main()
{
	int a = 5;
	int b = 4;
	int& ret = add(a, b);
	cout << ret << endl;
	printf("hello\n");
	cout << ret << endl;
	return 0;
}

在这里插入图片描述
 这一次验证,最重要的变化是从int ret = add(a, b);变成了int& ret = add(a, b);,可不要小瞧了这一个&,他让ret变成了引用,即ret从一个独立的变量,变成了一块空间的别名。原本调用add函数,返回sum所标识空间的一个别名,在把这块空间里的内容赋值给ret,而现在,ret也变成了sum所标识空间的别名,为什么要这样做?先看结果,两次打印ret的结果并不相同,第一次侥幸是正确的,因为sum标识的空间在归还给操作系统后,操作系统并没有对这块空间进行清理,接着调用了printf函数,由于函数调用会创建栈帧,sum标识的空间在此次创建的函数栈帧中被重新使用,这就导致里面存储的内容一定会发生改变,此时再去打印ret,结果就是错误的。假如这里的ret不是引用,是无法验证出这个错误的,因为此时ret有自己单独的空间,int ret = add(a, b);就是一次赋值操作,在第一次赋值后,ret就不会再变化,因此两次打印的结果可能侥幸都是正确的,所以需要让ret变成引用。
 上面说了这么多就是想告诉大家,局部变量传引用返回,你的结果可能侥幸是正确的。所以对于局部变量,大家还是老老实实的用传值返回。
引用做返回值的优势:

  • 减少拷贝,提高效率。
  • 可以同时读取和修改返回值(重载[ ]就是利用这个优势)

五、传值、传引用效率比较

 以值作为参数或返回值类型,在传参和返回期间,函数不会直接传递实参或者将变量本身直接返回,而是传递实参或返回变量的一份临时拷贝,因此用值作为参数或者返回值类型,效率是非常地下的,尤其是当参数或者返回值类型非常大时,效率就更低。
参数对比:

struct A
{
	int a[100000];
};

void TestFunc1(A a)
{
	;
}

void TestFunc2(A& a)
{
	;
}

void TestFunc3(A* a)
{
	;
}

//引用传参————可以提高效率(大对象或者深拷贝的类对象)
void TestRefAndValue()
{
	A a;
	// 以值作为函数参数
	size_t begin1 = clock();
	for (size_t i = 0; i < 10000; ++i)//就是单纯的调用一万次这个函数传一万次参
		TestFunc1(a);
	size_t end1 = clock();

	// 以引用作为函数参数
	size_t begin2 = clock();
	for (size_t i = 0; i < 10000; ++i)
		TestFunc2(a);//这里直接传的是变量名
	size_t end2 = clock();

	//以指针作为函数参数
	size_t begin3 = clock();
	for (int i = 0; i < 10000; i++)
	{
		TestFunc3(&a);
	}
	size_t end3 = clock();

	// 分别计算两个函数运行结束后的时间
	cout << "TestFunc1(A)-time:" << end1 - begin1 << endl;
	cout << "TestFunc2(A&)-time:" << end2 - begin2 << endl;
	cout << "TestFunc3(A*)-time:" << end3 - begin3 << endl;
}

在这里插入图片描述

 其中,A类型里面有一个四十万字节的数组,TestFunc1是值传递,TestFunc2是传引用,TestFunc3是传地址,分别把这三个函数调用一万次,通过结果可以看出,值传递花费的时间最长,并且也是最占用空间的,每次调用TestFunc1函数,都会重新创建一个四十万字节的A类型的变量,来存储实参,而传引用,形参只是给实参所标识的内存空间取了一个别名,并没有创建新的空间,传地址,只会创建一块空间来存储实参的地址,这块空间在32位机下是4字节,在64位机下是8字节。
返回值对比:

struct A
{
	int a[100000];
};
A a;//全局的,函数栈帧销毁后还在
// 值返回
A TestFunc1()
{
	return a;
}
// 引用返回
A& TestFunc2()
{
	return a;
}
void TestReturnByRefOrValue()
{
	// 以值作为函数的返回值类型
	size_t begin1 = clock();
	for (size_t i = 0; i < 100000; ++i)
		TestFunc1();//就让他返回不接收
	size_t end1 = clock();

	// 以引用作为函数的返回值类型
	size_t begin2 = clock();
	for (size_t i = 0; i < 100000; ++i)
		TestFunc2();
	size_t end2 = clock();

	// 计算两个函数运算完成之后的时间
	cout << "TestFunc1 time:" << end1 - begin1 << endl;
	cout << "TestFunc2 time:" << end2 - begin2 << endl;
}

int main()
{
	TestReturnByRefOrValue();
	return 0;
}

在这里插入图片描述
 值返回每次都要创建临时的中间变量,这就导致效率下降和空间上的浪费。

六、常引用

6.1 权限放大——不被允许

int main()
{
	const int a = 10;
	int& b = a;//权限放大
	return 0;
}

在这里插入图片描述
 上面代码中,用const定义了一个常变量a,接着想给a取一个别名b,但是编译的过程中报错了:无法从const int 转换为int &。为什么会这样呢?原因是:权限可以平移、缩小,但是不能放大
a最初是一个常变量,意味着a一旦定义就不能再修改,而此时引用b出现了,它是a的一个别名,但是它没有加const修饰,意味着可以对b进行修改,这时就相当于权限的放大,这种情况是不允许的。正确的做法是,给引用b加上const进行修饰,即:cconst int& b = a;,此时属于权限的平移。

6.2 权限平移

int main()
{
	const int a = 10;
	const int& b = a;//权限平移
	return 0;
}

在这里插入图片描述
 上面代码中的,给常变量a取一个别名b,这里的b其实就是一个常引用

6.3 权限缩小

int main()
{
	int a = 10;
	const int& b = a;//错误:权限缩小
	int& c = 10//错误:权限缩小
	return 0;
}

在这里插入图片描述

 上面代码中,给一个普通的变量a取了一个别名b,这个b是一个常引用。这意味着,可以通过a变量去对内存中存储的数据进行修改,但是不能通过引用b去修改内存中存储的数据。这就有点类似于:李逵在梁山泊的时候可以喝酒,下了梁山泊以后就叫黑旋风,不能喝酒一样。但是李逵在了梁山泊喝了酒,黑旋风的肚子里一定也是有酒的(黑旋风不能喝酒,管我李逵什么事dog)。这就意味着:通过a去对内存中存储的数据进行修改,b也会跟着变,虽然不能通过b去修改,但是它会跟着变。

int main()
{
	int a = 10;
	const int& b = a;
	cout << "修改前:" << endl;
	cout << "a:" << a << endl;
	cout << "b:" << b << endl;
	a++;
	//b++;//b是一个常引用,不能通过b去修改
	cout << "修改后:" << endl;
	cout << "a:" << a << endl;
	cout << "b:" << b << endl;
	return 0;
}

在这里插入图片描述

6.4 赋值拷贝不涉及权限问腿

 上面说到的权限放大,缩小问题,都是在取别名的时候发生的,即在定义一个引用变量的时候。权限的放大、缩小等,针对的必定是同一块空间,不同的空间有自己的权限,不存在权限变更的问题。而引用恰恰就是对同一块空间取了一个别名而已,赋值则是重新创建了一块空间。

int main()
{
	const int a = 10;
	const int b = a;
	int c = a;
	return 0;
}

 如上面的代码,可以把常变量a重新赋值给常变量b或者普通变量c,都是可以的,因为这三个变量标识了三个独立的内存空间,它们之间互不影响。

七、临时变量

 在4.2小节中提到,函数的传值返回,会创建一个临时变量,在最后的总结中还写到:临时的中间变量具有常性。这条性质适用于所有的临时变量,不只是传值返回产生的临时变量具有常性,在类型转换(包括但不限于:强制类型转换、隐式类型转换、整型提升、截断)过程中,也会产生临时变量,并且这个临时变量也具有常性。为什么要提这个?
 因为引用是针对同一块空间的操作,引用就是给同一块空间取别名,既然是同一块空间,就逃不了会涉及到权限变化问题,又因为临时变量不经过调试,我们是很难发现的它的存在,并且临时变量很特殊,具有常性,所以,我们需要特别注意哪些可能会产生临时变量的操作。下面举一些可能会产生临时变量的例子:

7.1 传值返回

int Text()
{
	int a = 99;
	return a;
}

int main()
{
	//int& ret = Text();//函数返回会创建临时变量
	const int& ret = Text();//用引用接收必须要加const修饰
	return 0;
}

7.2 类型转换

int main()
{
	double a = 3.14;
	//int& b = a;//错误的类型转换,产生临时变量
	const int& b = a;//正确
	return 0;
}

7.3 传参

void Text1(int& y)
{
	cout << y << endl;
}

void Text(const int& y)
{
	cout << y << endl;
}

int main()
{
	//Text1(1 + 3);//错误
	Text(1 + 3);//正确
	return 0;
}

 上面代码中的函数调用Text1(1 + 3);是错误的,因为1 + 3的结果会保存在一个临时变量里面,同时形参是一个引用,相当于要给这个临时变量取一个别名,但这个临时变量具有常性,而这里的引用只是一个普通引用,不是常引用,所以就会涉及权限的放大,导致函数调用出错。Text函数的形参是一个常引用,在调用的时候就不会出错。

八、引用与指针的区别

  • 引用在概念上定义一个变量的别名,指针存储一个变量的地址
  • 引用在定义时必须初化,指针没有要求。
  • 引用在初始化时引用一个一个实体后,就不能再引用其他实体,而指针可以在任何时候指向任何一个同类型实体。
  • 没有NULL引用,但有NULL空指针。
  • sizeof中的含义不同,引用结果为引用类型的大小,但指针始终是地址空间所占字节个数(32位机下占四个字节,64位机下占八个字节)。
  • 引用自加即引用的实体增加1,指针自加即指针向后偏移一个类型的大小。
  • 有多级指针,但是没多级引用
  • 访问实体方式不同。指针显式解引用,引用编译器自己做处理。
  • 引用比指针使用起来相对更安全

 今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,您的支持就是春人前进的动力!
在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。