C语言_结构体

发表于2021-08-15更新于2025-09-28阅读次数

本章内容

  1. 结构体类型的设计
  2. 结构体变量初始化
  3. 结构体成员访问
  4. 结构体与数组

结构体类型的设计

C 语言提供了基本数据类型，如 char, short, int, float 等类型，我们称之为内置类型。
程序开发人员可以使用结构体来封装一些属性，设计出新的类型，在 C 语言中称为结构体类型。
在 C 语言中，结构体是一种数据类型。（由程序开发者自己设计的类型）
可以使用结构体（struct）来存放一组不同类型的数据。结构体的定义形式为：

1
2
3
4
struct 结构体名
{
    成员列表（可以是基本数据类型，指针，数组或其它结构类型）
};

我们自己设计一个学生类型

客观事物（实体）是复杂的，要描述它必须从多方面进行，也就是用不同的数据类型来描述不同的方面。如学生实体可以这样来描述：

  1. 学生学号（用字符串描述）
  2. 学生姓名（用字符串描述）
  3. 性别（用字符串描述）
  4. 年龄（用整型数描述）。
    这里用了2种不同数据类型，以及四个数据成员（data member）来描述学生实体。
    （数据成员，也可称之为属性，不能称之为函数中的变量概念）

image-20210815101308997

结构体变量的定义和初始化

既然结构体是一种数据类型，那么就可以用它来定义变量。结构体就像一个“模板”，定义出来的变量都具有相同的性质。
也可以将结构体比作“图纸”，将结构体变量比作“零件”，根据同一张图纸生产出来的零件的特性都是一样的。
结构体是一种数据类型，是创建变量的模板，不占用内存空间；结构体变量才包含了实实在在的数据，需要存储空间。

结构体变量在内存中表示

思考下述代码结构体在内存中的分配是A情况还是B情况？

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Student
{
    char s_id[8];
    char s_name[8];
    char s_sex[4];
    int s_age;
};
int main()
{
    int a = 10,b = 20;
    struct Student s1 = {"09001","yhping","man",23};
    return 0;
}

image-20210816155806100

答案是A，即结构体成员的内存分布顺序是从上到下依次排列。为什么不是像a,b那样的顺序？

我自己的解释：结构体的类型结构声明不像函数中变量的声明定义。我们要区分类型内部的成员和函数内部的变量，两者是截然不同的！结构体类型的抽象是一种类型，是由若干其他类型组成的一种新类型，那么类型内部的成员必然要按照我们在定义时的顺序从上到下分布内存空间，才符合程序设计的逻辑思路。按照如此规则如此分布，才能方便我们进行后续的给结构体变量初始化赋值，大括号内的值的顺序是按照成员顺序来的，而不是随意颠倒顺序，编译器是不会同意的。

示例

image-20210815102046756
如果把char数组改为指针：
image-20210815104639636

结构变量初始化

image-20210815102137170

大括号内的值的顺序是按照成员顺序来的，而不是随意颠倒顺序，编译器是不会同意的。

image-20210816162135598

如果把char数组改为指针：

这时按照上图的赋值方式，在VS2019中是不能通过的，因为，"09001"这种双引号引起来的字符串的类型是常量字符串型即const char*（要给s_id赋的值本质是字符串首字符'0'的指针，此指针只能读数据不能改数据，因此类型是const char*），与我们在结构体中声明的char*不匹配。

结构体嵌套结构体

image-20210815104658804

思考以下结构是否可行？

1
2
3
4
5
6
7
struct Student
{
    char s_name[8];
    int s_age;
    float score;
    struct Student studx;
};		//sizeof(Student)是计算不出来的，因为如此定义会导致无穷的递归下去。不能被sizeof计算的类型因此也叫做不完整的类型。

image-20210816181150361

结构体链接结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Student
{
    char s_name[8];
    int s_age;
    float score;
    struct Student* next;//如此定义才可行。
};		//sizeof(Student)==16
int main()
{
    struct Node a,b,c;
    struct Node* head = &a;
    a.data = 10;
    a.next = &b;
    b.data = 20;
    b.next = &c;
    c.data = 30;
    c.next = NULL;
    
    return 0;
}

image-20210816181426848
如何使用循环打印？

1
2
3
4
5
6
7
8
9
void Print_List(const struct Node* head)
{
    const struct Node* p = head;
    while(p!=nullptr)
    {
        printf("%d ",p->data);
        p = p->next;
    }
}

结构体成员的访问

结构体变量的成员使用.访问。
获取和赋值结构体变量成员的一般格式为：结构体变量.成员名；

结构体变量成员的访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<string.h>
struct Date
{
	int year;
	int month;
	int day;
};
struct Student stud1
{
	char s_name[20]; //姓名
	struct Date birthday; //生日
	float score; //成绩
};
int main()
{
	struct Student stud1={"Yhp",2007,10,1,145.5};
	struct Student stud2={"Liuwuyang",{2007,2,2},135.0};
    
	int y = stud1.birthday.year;//用.访问结构体变量的成员
    struct Student* sp = &stud1;
    sp->s_name;//用->访问结构体变量指针对应的结构体变量的成员
    (*sp).s_name;//用.访问结构体变量的成员
    sp->birthday.year;//前sp是指针，后birthday是结构体，所以前用->后用.
    
	return 0;
}

结构体变量（的成员）的赋值

对结构变量整体赋值有三种情况：

  1. 定义结构体变量（用{ }花括号初始化）；
  2. 用已定义的结构变量初始化；
  3. 结构体类型相同的变量可以作为整体相互赋值。

在其他情况的使用过程中只能对成员逐一赋值。
在 C 语言中不存在对结构体类型的强制转换（和内置类型的区别）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Student
{
	char s_id[8];
    char s_name[8];
    char s_sex[4];
    int s_age;
}Student;
int main
{
    Student stda={"09001","xcg","M",23};
    Student stdb=stda;//调用了memcpy(&stdb,&stda,sizeof(stda));
    Student stdc;
    Student stdx;
    stdc = stda;
    stdx.s_name = stda.s_name;//此语句是错误的。
    strcpy_s(stdx.s_name,stda.s_name);//正确的做法！
}

关于两结构体变量整体赋值如何实现

首先，抓住两个结构体变量各自的地址，再依次同步迭代拷贝，调用的函数是memcpy();如memcpy(&stdb,&stda,sizeof(stda));

关于上面提到的错误赋值

stdx.s_name = stda.s_name;此语句是错误的。`

为什么？

s_name是一个数组，数组是不可能给另一个数组直接赋值的。因为：s_name代表首元素指针，根据我们数组那一节的知识储备，这个指针是常量（即数组名所代表的指针），stdx.s_name = stda.s_name这个语句的意思是把stda.s_name这个指针赋给stdx.s_name这个指针，这显然是不可行的，数组首元素指针不可能改变！

同理，数组名不可以++，如已知int ar[100]={};的ar数组，ar++这个语句是错误的。

应该对数组进行全部迭代拷贝，如调用strcpy_s(stdx.s_name,stda.s_name);

与数组{}花括号赋值的异同

不同点是：数组的花括号内的值类型必须一致，而结构体花括号内的值可能不一致。

共同点：如果{}花括号内的内容缺省，默认赋值为0。

结构体变量和函数

拿打印函数举例

image-20210816183332238

二个打印函数那个好 ？ 原因是什么？

image-20210816183348520

二个打印函数那个好 ？ 原因是什么？和指针比较的优势？ 限制条件是什么？

肯定是Print_c好。优势在于如果不是用指针来传值，那么还要再次开辟空间且给形参复制源变量的信息，导致空间和时间的效率都大大降低。而用指针来传值，直接能操作源变量。而用const来读取信息更为谨慎，因为const能保证该指针只能读取变量信息而不能改变变量信息。

结构体的大小

1
2
3
4
5
6
7
8
9
10
11
struct Node_a
{
    char ca;
    int sum;
    char cb;
}
int main()
{
    struct Node_a ax;
    printf("%d %d \n",sizeof(struct Node_a),sizeof(ax));//12 12
}

为什么要理解字节对齐问题

  1. 内存大小的基本单位是字节，理论上来讲，可以从任意地址访问变量，但是实际上，cpu并非逐字节读写内存，而是以 2, 4 或 8 的倍数的字节块来读写内存，因此就会对基本数据类型的地址作出一些限制，即它的地址必须是 2，4 或 8 的倍数。那么就要求各种数据类型按照一定的规则在空间上排列，这就是对齐。
  2. 有些平台每次读都是从偶地址开始，如果一个 int 型（假设为 32 位系统）如果存放在偶地址开始的地方，那么一个读周期就可以读出这 32 bit，而如果存放在奇地址开始的地方，就需要 2 个读周期，并对两次读出的结果的高低字节进行拼凑才能得到该 32 bit 数据。显然在读取效率上下降很多。
  3. 由于不同平台对齐方式可能不同，如此一来，同样的结构在不同的平台其大小可能不同，在无意识的情况下，互相发送的数据可能出现错乱，甚至引发严重的问题。

计算规则

由于存储变量地址对齐的问题，计算结构体大小的 3 条规则：

  1. 结构体变量的首地址，必须是结构体变量中的“最大基本数据类型成员所占字节数”的整数倍。

  2. 结构体变量中，相对于结构体首地址，每个成员的偏移量，都是成员本身基本数据类型所占字节数的整数倍。

    1
    2
    3
    4
    5
    6
    struct Node
    {
        char ca;//偏移地址为0，占1字节。偏移地址1-7起地址对齐占位作用，内容无实际意义。
        double dx;//偏移地址为8，占8字节。因为要满足原则2即double的偏移量要相对于结构体首地址（视为0），是成员本身基本数据类型所占字节数的整数倍。只有在偏移地址8时，才满足(8-0)/8==1。
        char cb;
    };//24

  3. 结构体变量的总大小，为结构体变量中 “最大基本数据类型成员所占字节数”的整数倍。
    image-20210817015222060

实例/测验

1
2
3
4
5
6
struct node
{
    char cha;
    double da;
    char chb;
};//24,因为da是从0x08开始的。cha和chb都占了8个
1
2
3
4
5
6
7
8
9
10
11
12
13
struct sdate
{
    int year;
    int ia;
    int day;
};
struct Student
{
    char s_id[10];//1-10
    char s_name[8];//11-18
    struct sdate birthday;//21-32
    double grade;//33-40
};//40
1
2
3
4
5
6
7
8
struct Inventory
{
    char description[15];//货物名称
    char no[10];//货号
    int quantity;//库存数量
    double cost;//成本
    double retail;//零售价格
};//48
1
2
3
4
5
6
7
8
struct Employee
{
    char name[27];//1-27
    char address[30];//28-57
    long int zip;//61-64
    long int telenum;//65-68
    double salary;//72-80
};//80

如何巧妙计算偏移量

有Employee类型的结构体，成员有name, address, zip, telenum, salary等，现要求：不要定义任何结构体变量计算zip相对结构体自身首地址的偏移量。
利用宏+无中生有法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define my_offset(type,exp) ( (int) & (( (type*)0 )->exp ))
struct Employee
{
    char name[27];//1-27
    char address[30];//28-57
    long int zip;//61-64
    long int telenum;//65-68
    double salary;//72-80
};//80
int main()
{
    int offset = 0;
    //struct Employee x;
    //offset = (char*)&x.salary - (char*)&x;  //72-0==72
    offset = (int) & ( (struct Employee*)0 )->salary;//无中生有  0x00->0x72
    offset = my_offer(struct Employee,zip);//利用宏定义
    printf("%d \n",offset);
}

#pragma pack指定对齐值

预处理指令#pragma pack(n)可以改变默认对齐数。n取值是 1, 2, 4, 8, 16。
VS 中默认值 = 8，gcc 中默认值 = 4

1
2
3
4
5
6
7
8
9
10
11
12
13
#pragma pack(1)
struct node
{
    char cha;
    double dx;
    char chb;
};
//若( )内为1->size:10;
//		为2->	12;
//		为4->	16;
//		为8->	24;
//		为16->	24;
#pragma pack

终极总结

  1. 结构体变量的首地址，必须是MIN{"结构体 最大基本数据类型成员 所占字节数", 指定对齐方式}的整数倍。
  2. 结构体中，相对于结构体首地址，每个成员的偏移量，都是MIN{该基本数据类型成员, 指定对齐方式}的整数倍。
  3. 结构体的总大小，为MIN{结构体最大基本数据类型成员所占字节数, 指定对齐方式}的整数倍。

比较结构体变量

不要轻易地使用memcmp函数来对比两个结构体变量。因为结构体内存结构层面中，成员间的空隙填充的内容是不可控的，即结构体是一种非连续型内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Node
{
    char cha;
    int ix;
    char chb;
};
//当调用主函数时，将对分配得到的栈帧的每个字节进行刷新，全部赋为'0xcc'
int main()
{
    int ar[10]={};
    int br[10]={};
    int x = memcmp(ar,br,sizeof(ar));
    printf("%d\n",x);
    
    struct Node x = {'a',12,'b'};
    struct Node y = {'a',12,'b'};
    int tag1 = memcmp(&x,&y,sizeof(x));//不要轻易地使用memcmp比较结构体。因为结构体是一种非连续型内存空间。
    struct Node z = {};//{}代表:把12个字节全赋成了0
    z.cha = 'a';
    z.chb = 'b';
    z.ix = 12;
    int tag2 = memcmp(&x,&z,sizeof(x));//返回值0代表相等，1代表大于，-1代表小于
    printf("%d %d\n",tag1,tag2);//0 1
    return 0;
}

image-20210817153745134

结构体与数组

所谓结构体数组，是指数组中的每个元素都是一个结构体类型。在实际应用中，C 语言结构体数组常被用来表示一个拥有相同数据结构的群体，比如一个班的学生、一个公司的员工等。

联合体

联合体(union)与结构体(struct)有一些相似之处。但两者有本质上的不同。在结构体中,各成员有各自的内存空间。而在联合体中,各成员共享同一段内存空间, 一个联合体变量的长度等于成员中最长的长度。
应该说明的是, 这里所谓的共享不是指把多个成员同时装入一个联合变量内, 而是指该联合变量可被赋予任一成员值,但每次只能赋一种值, 赋入新值则冲去旧值。
一个联合体类型必须经过定义之后, 才能使用它，才能把一个变量声明定义为该联合体类型。
联合体不仅可以节省内存空间，最本质、重要的用法是对同一段空间采取不同的类型格式去识别、读取数据。

image-20210817164050152

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
union Node
{
    short sx;
    char cx[2];
};
int main()
{
    union Node x;
    x.sx = 0x6162;//0x62,0x61
    printf("%c %c \n",x.cx[0],x.cx[1]);//b a 而非a b 
    
    x.cx[0]=1;
    x.cx[1]=2;
    printf("%d \n",x.sx); //0x01,0x02=>0x0201
    return 0;
}

image-20210817162154866

声明和定义时的注意

设计有名的联合体，同时没有定义变量。

1
2
3
4
5
6
union UnData
{
    short st;
    char cs[2];
};
union UnData x;

设计有名的联合体，同时定义变量。与上述代码等效，节省了一行代码。

1
2
3
4
5
union UnData
{
    short st;
    char cs[2];
}x;

设计无名的联合体，同时定义变量。这样是可行的。

1
2
3
4
5
union
{
    short st;
    char cs[2];
}x;

但要注意的是，如下做法编译器是不认为x,y属于同一种类型的联合体的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
union
{
    short st;
    char cs[2];
}x;
union
{
    short st;
    char cs[2];
}y;
int main()
{
    x = y;//不可编译通过。编译器不认为x,y属于同一种类型的联合体。
}

当然，我们可以用typedef关键字把无名的联合体定义出的变量名赋予其类型的性质。

1
2
3
4
5
typedef union
{
    short sx;
    char cx[2];
}x;

重要的面试笔试题目

IP地址本质上是一串32位二进制代码（对于ipv4是32位，ipv6是128位），可看作无符号int数。题目要求把32位二进制代码的每八位转换为一个无符号十进制数，并用“点”隔开，最终转为字符串。同时也要求把该格式的字符串能逆转换为32位二进制代码构成的无符号int数。

image-20210817114120334

要运用到的输入/输出函数

1
2
3
4
5
6
7
8
9
10
11
12
13
char buff[20];
int a = 10,b = 20;

printf();//打印到屏幕上
int len = printf("a = %d b = %d \n",a,b);//将格式化字符串写入到标准输出设备中

sprintf(buff,"%d.%d.%d.%d",x.s4,x.s3,x.s2,x.s1);//将格式化字符串写入到buff中
int sprintf(char* buff,const char* fmt, ...);//返回的值：格式化字符串探测到'\0'时，返回有效字符的长度
int len = sprintf(buff,"a = %d b = %d \n",a,b);

fprintf(stdout,"a = %d b = %d \n",a,b);//将格式化字符串写入到文件指针对应的位置。如果该文件是标准输出设备则是打印到屏幕上。

//由此可知，printf()实际上内部调用了fprintf()，文件指针为stdout；而fprintf()实际上内部调用了sprintf()，buff指针指向文件指针。即sprintf才是根本所在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
scanf();//从标准输入设备stdin中输入的数据读取值。

sscanf(char* buff,"%...", &...);//从buff（字符串）中读值。按格式化控制将%...对应的值写到&...中


int main()
{
    int a,b;
    int sum = scanf("%d %d",&a,&b);//scanf返回正确读取到的值的个数，此处若正确输入则返回2。若输入"12,23"则只能正确读取一个值
    //如果输入时两数中间分开的不是空格，则无法正常输入。因此此处就体现了scanf的“格式控制”，那么同样的，我们若想要用户用.来隔开数据，则可以通过限制格式来达到控制效果。
    
    char buff[]={"12,23,34,45"};
    unsigned int s[4];
    //sum = sscanf(buff,"%d.%d.%d.%d",&s[0],&s[1],&s[2],&s[3]);
    //为了能检测到用户多输入了字符，则我们在格式化控制中多加一个哨兵位检测是否多输入了值。
	char ch;
    sum = sscanf(buff,"%d.%d.%d.%d%c",&s[0],&s[1],&s[2],&s[3],&ch);
    //一旦用户多输入了字符如'.'，则sum将大于4，则可以条件判断意外情况。
    printf("%d \n",num);//4为正常，5为多输入了字符-意外情况
}

代码编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
union IPNode
{
    unsigned int addr;
    struct //没有名字，称为哑元结构（dummy），对应于实元。
    {
        unsigned char s1,s2,s3,s4;//或者声明一个数组也可以。unsigned char s[4];
    };
    //unsigned char s1,s2,s3,s4;不能简单地写成这样，因为这样写的结果是：四个变量都只共享第一个字节。
};
void int_to_str(unsigned int ip,char* buff)
{
    assert(buff!=nullptr);
    union IPNode x;
    x.addr = ip;
    sprintf_s(buff,20,"%d.%d.%d.%d",x.s4,x.s3,x.s2,x.s1);
}
int main()
{
    unsigned int ip = 2394117684;
    char buff[20]={};
    int_to_str(ip,buff);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
unsigned int str_to_int(const char* buff)
{
    unsigned int ip=0;
    if(buff==NULL)return ip;
    
    union IPNode x;
    
    unsigned int s[4]={};
    char ch=0;
    int sum=sscanf_s(buff,"%d.%d.%d.%d%c",&s[3],&s[2],&s[1],&s[0],&ch);
    if(num>4)return ip;
    for(int i=3;i>=0;--i)
    {
        if(s[i]>255)return ip;
        x.s[i]=s[i];
    }
    ip=x.addr;
    return ip;
}
int main()
{
    unsigned int ip = 2394117684;
    char buff[20];
    printf("%u \n",ip);
    
    int_to_str(ip,buff);
    printf("%s \n",buff);
    
    unsigned ipx = str_to_int(buff);
    printf("%u \n",ipx);
}

作业

  1. 给结构体变量赋值和输出结构体变量的值。想尽办法做初始化。

    image-20210815114633078

C语言_递归

发表于2021-08-14更新于2025-09-28阅读次数

递归内容

  1. 栈帧的理解
  2. 分治策略和递归

复习函数

编译链接和内存布局

image-20210814025249988

根据不同的操作系统，一个进程可能被分配到不同的内存区域去执行。但是不管什么样的操作系统、什么样的计算机架构，进程使用的内存都可以按照功能大致分为以下4个部分：

  1. 代码区：这个区域存储着被装入执行的二进制机器代码，处理器(CPU)会到这个区域取指并执行。
  2. 数据区：用于存储全局变量, 静态全局变量，静态局部变量，字符串常量等。
  3. 堆区：进程可以在堆区动态地请求一定大小的内存，并在用完之后归还给堆区。动态分配和回收是堆区的特点。
  4. 栈区：函数被调时分配栈区，用于存放函数的参数值，局部变量等值；还要动态地存储函数之间的关系，以保证被调用函数在返回时恢复到被调用函数中继续执行。

函数调用机制

局部变量占用的内存是在程序执行过程中“动态”地建立和释放的。这种“动态”是通过栈由系统自动管理进行的。当任何一个函数调用发生时，系统都要作以下工作：

  1. 建立栈帧空间；
  2. 保护现场：主调函数运行状态和返回地址入栈；
  3. 为被调函数传递数据（进行实参和形参的结合），同时形参获得存储空间；接着给局部变量分配空间；
  4. 执行被调函数函数体；
  5. 当被调函数执行完成，释放被调函数中局部变量占用的栈空间；
  6. 恢复现场：取主调函数运行状态及返回地址，释放栈帧空间；
  7. 继续主调函数后续语句。

image-20210814025448484

在进入main函数时，只创建了main函数的栈帧，在调用Add函数时才会建立Add函数的栈帧，当Add函数return时，栈帧收回。

有启发的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int* fun()
{
    int ar[10]={12,23,34,45,56,67,78,89,90,100};
    return ar;
}
int main()
{
    int* p = fun();
    for(int i = 0;i<10;++i)
    {
        printf("%d ",p[i]);
    }
    printf("\n");
    return 0;
}

ar大小为10时，fun函数调用时还正常存在着ar数组的信息，而fun函数调用完后，再循环调用printf函数，致使冲掉了以前栈帧的信息，导致输出错误。

image-20210814032349532

而把fun函数中的ar大小改为1000时，运行结果就不一样了，输出的是正常的。

image-20210814032439500

因为，ar占用的栈帧很多，printf函数未能冲刷到之前ar的原有数据。但是本质上ar的信息还是失效了的。懂了这个例子，会对函数调用与栈帧分配的关系深入理解。

分治策略与递归

分治策略：是将规模比较大的问题可分割成规模较小的相同问题。问题不变，规模变小。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法步骤

在分治策略中递归地求解一个问题，在每层递归中应用如下三个步骤：

  1. 分解：将问题划分成一些子问题，子问题的形式与原问题一样，只是规模更小。
  2. 解决：递归地求解子问题。如果子问题的规模足够小，则停止递归，直接求解。
  3. 合并：将小规模的解组合成原规模问题的解。

递归函数的执行分为“递推”和“回归”两个过程，这两个过程由递归终止条件控制，即逐层递推，直至递归终止条件满足，终止递归，然后逐层回归。
　　递归调用同普通的函数调用一样，每当调用发生时，就要分配新的栈帧（形参数据，现场保护，局部变量）；而与普通的函数调用不同的是，由于递推的过程是一个逐层调用的过程，因此存在一个逐层连续的分配栈帧过程，直至遇到递归终止条件时，才开始回归，这时才逐层释放栈帧空间，返回到上一层，直至最后返回到主调函数。

经典题目

我们对于递归要达到的初级水平是：可以把循环程序改为递归程序。

最终的目标是：在递归的活动中，直接能捕获到某一步的运行情况。

求解阶乘

image-20210814032743926

1
2
3
4
5
6
n! = (n-1)!\*n
(n-1)! = (n-2)!\*n-1
(n-2)! = (n-3)!\*n-1
...
2! = 1! \* 2
1! = 1

阶乘可递归的定义为：
image-20210814033732211

可以看出是用阶乘定义阶乘，这种拿自己定义自己的方法称为递归定义。

在写出递归程序前，我们先拿循环程序解决一下。

1
2
3
4
5
6
7
8
9
10
//不考虑整型溢出
int factorial(int n)
{
    int sum=1;
    for(int i=1;i<=n;++i)
    {
        sum=sum*i;
    }
    return sum;
}

递归的写法：

1
2
3
4
5
6
7
8
9
10
11
int factorial_recursion(int n)//factorial:阶乘 recursion:递归
{
    if(n<=1)
    {
        return 1;
    }
    else//n>1
    {
        return factorial_recursion(n-1)*n;
    }
}

可以把一切的循环改为递归，也可把一切的递归改为循环，两者本质上可以相通。

整数倒序输出

输入一个整数（无符号整型），用递归算法将整数倒序输出。

循环法

1
2
3
4
5
6
7
8
void reverse_print(unsigned int n)
{
    while(n!=0)
    {
        printf("%d ",n%10);//1234%10=4 ...
        n=n/10;
    }
}

递归法

1
2
3
4
5
6
7
8
void reverse_print(unsigned int n)
{
    if(n!=0)
    {
        printf("%d ",n%10);
        reverse_print(n/10);
    }
}

上述递归代码是正确的，即输出了"4 3 2 1 "。而如果调用函数和打印顺序颠倒，则结果会完全不一样。分析代码结构，打印函数是在调用reverse_print之前的，就是说我们是在递推的同时打印模10结果的，而回归时reverse_print函数后面没有语句，因此没有其他的操作。

1
2
3
4
5
6
7
8
void fun(unsigned int n)
{
    if(n!=0)
    {
        fun(n/10);
        printf("%d ",n%10);
    }
}

上述代码为先递归切割（每次都除10），最后则从1%10开始打印到1234%10，即"1 2 3 4 "。分析递归时，一定要明确各层函数在栈区中的结构和意义。那么我们分析，由于打印函数在fun函数之后，所以这个程序在从1234递推到1的过程中没有打印，而是在递推完毕回归时才打印（即执行fun函数之后的语句）。

打印无序数组

有一个整型数组，数值无序，使用循环和递归完成打印和查询。

循环方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Print_Ar(const int* ar, int n)
{
    assert(ar!=NULL);
    for(int i=0;i<n;++i)
    {
        printf("%d ",ar[i]);
    }
    printf("\n");
}
int main()
{
    int ar[]={12,23,34};
    int n = sizeof(ar)/size(ar[0]);
    Print_Ar(ar,n);
}

递归方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Print_recursion(const int* ar, int n)
{
    if(n>0)
    {
        Print_recursion(ar,n-1);//n-1代表打印前n-1个元素
    	printf("%d ",ar[n-1]);//n-1代表此时的第n下标值
    }
}
void Print_Ar(const int* ar, int n)
{
    assert(ar!=NULL);
    Print_recursion(ar, n)；
    printf("\n");
}
int main()
{
    int ar[]={12,23,34};
    int n = sizeof(ar)/size(ar[0]);
    Print_Ar(ar,n);
}

思考1

如果把递归函数体中的Print_recursion(ar,n-1);中的"n-1"改为"n--"会发生什么现象？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Print_recursion(const int* ar, int n)
{
    if(n>0)
    {
        Print_recursion(ar,n--);//n-1代表打印前n-1个元素
    	printf("%d ",ar[n-1]);//n-1代表此时的第n下标值
    }
}
void Print_Ar(const int* ar, int n)
{
    assert(ar!=NULL);
    Print_recursion(ar, n);
    printf("\n");
}
int main()
{
    int ar[]={12,23,34};
    int n = sizeof(ar)/size(ar[0]);
    Print_Ar(ar,n);
}

答案是运行时内存溢出了。因为n--是后置--，先取值运行函数，函数调用完才回写减一后的结果。开始时n是3，函数调用时传的值永远都是2。

思考2

如果把递归函数体中的Print_recursion(ar,n--);中的"n--"改为"--n"会发生什么现象？

答案是"随机值 12 23 "。因为--n是前置--，在运行函数前就把n-1并回写了，这导致一个问题，函数调用时，n已经减了1，那么打印ar[n-1]又会减1，则会导致n=1时调用Print_recursion(ar, n);时满足条件执行语句--n，此时n变0，接下来打印ar[n-1]即ar[-1]，就产生了越界。

查询无序数组某值的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int FindValueIndex(const int* ar, int n, int val)
{
	int pos = -1;
	if (n > 0)
	{
		if (ar[n - 1] == val)
		{
			pos = n - 1;
		}
		else
		{
			pos = FindValueIndex(ar, n - 1, val);
		}
	}
	return pos;
}
int findValue(const int*ar, int n,int val)
{
    if(ar==NULL) return -1;
    return FindValueIndex(ar, n, val);
}

老师的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int FindValueIndex(const int* ar, int n, int val)
{
	if (n < 1 || ar[n-1] == val)
	{
		return n-1;
	}
    else
    {
        return FindValueIndex(ar, n-1, val);
    }
}
int findValue(const int*ar, int n,int val)
{
    if(ar==NULL) return -1;
    return FindValueIndex(ar, n, val);
}

全排列/子集问题：树形结构(组合树/子集树)

现要求输出集合{1,2,3}的全部子集。

image-20210815021627089
image-20210816014510751

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void fun(int* ar,int* br,int i,int n)
{
    if(i==n)
    {
        for(int k=0;i<n;++k)
        {
            if(br[k]==1)
            {
                printf("%d ",ar[k]);
            }
        }
        printf("\n");
        
    }
    else
    {
        br[i]=1;
        fun(i+1,n);
        br[i]=0;
        fun(i+1,n);
    }
}
int main()
{
    const int n = 3;
    int ar[]={1,2,3};
    int br[]={0,0,0};
    fun(ar,br,0,n);
    return 0;
}

此类递归程序的时间复杂度为O(2n)O(2^n)，空间复杂度为树的高度S(n)S(n)。

图解递归过程

代码的调动过程

image-20210814220256021

栈帧的动态调动过程

image-20210814220321049

总结

关于分配栈帧

函数被调用，不管是自己调用自己，还是被其它函数调用，都将会给被调用函数分配栈帧。

关于死循环

存在死循环，但不存在无穷递归。即递归函数必须要有一个是递归结束的出口（要有递归中止的条件语句）。

1
2
3
4
5
6
7
8
9
int factorial(int n)
{
    int sum=1;
    for(int i=1; ;++i)//中间语句缺省，意味着死循环。
    {
        sum=sum*i;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
int factorial_recursion(int n)//factorial:阶乘 recursion:递归
{
    if(false)//达不到原来的函数出口了
    {
        return 1;
    }
    else
    {
        return factorial_recursion(n-1)*n;
    }
}

死循环只是重复的在开辟的某一个空间里反复计算赋值，过程都是在一个内存空间完成的。即时间复杂度是O(n)O(n)，空间复杂度是S(1)S(1)。死循环只是全负荷的使用CPU的运算资源，但不会影响内存结构。

而无穷递归是反复开辟新的栈帧，时间复杂度是O(n)O(n)，空间复杂度是S(n)S(n)，因为栈区的大小是有限的，默认为1M，如果一直递归下去，则会溢出栈区破坏内存结构，则不可能一直递归下去。所以问题的规模不要过大，递归过深，引起栈溢出。

找数组某一值

1
2
3
4
5
6
7
8
9
10
11
int Find(const int* ar,int n,int val)
{
    if(n<1 || ar[n-1]==val)
    {
        return n-1;
    }
    else
    {
        return Find(ar,n-1,val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Find(const int* ar,int n,int val)
{
	int pos = -1;
	if (n > 0)
	{
		if (ar[n - 1] == val)
		{
			pos=n-1;
		}
		else
		{
			pos = FindValueIndex(ar, n - 1, val);
		}
	}
	return pos;
}

体会递归的分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Print(const int* ar,int n)
{
    if(n>0)
    {
        Print(ar,n-1);//括号内的n-1改成n--和--n,结果都会不一样。
        printf("%d ",ar[n-1]);
    }
}
void Print_Ar(const int* ar,int n)
{
    assert(ar!=nullptr);
    Print(ar,n);
    printf("\n");
}
int main()
{
    int ar[] = { 12,23,34 };
	int n = sizeof(ar) / sizeof(ar[0]);
	Print_Ar(ar, n);
}

作业

  1. 斐波那契数列
    循环法
1
2
3
4
5
6
7
8
9
10
11
int fun(int n)
{
   int a=1,b=1,c=1;
   for(int i=3;i<=n;++i)
   {
       c=a+b;
       b=a;
       a=c;
   }
   return c;
}

递归法（目标要达到时间复杂度O(n)O(n)）
https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/solution/fei-bo-na-qi-shu-lie-wen-ti-de-si-chong-jie-fa-by-/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int Fibonacci(int n)
{
    if (n == 1 || n == 2)return 1;
    else if (n > 0)
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    else
    {
        return 0;
    }
}
int Fibonacci_Ar(int* ar,int n)
{
    int i = 2;
    for (i; i <= n;++i)
    {
        ar[i] = ar[i - 2] + ar[i - 1];
    }
    return ar[n];
}
int main()
{
    int ar[101] = { 0,1,1 };
    int fibo = Fibonacci_Ar(ar,30);
    printf("%d ", fibo);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*记忆化递归解法
解题思路:
既然普通的递归解法产生大量的重复计算，如果已经计算过的f(x) 把结果保存不就减少了计算么？ 用一个数组记忆计算结果，如果f(x)已经计算过了，直接返回a[x]
时间复杂度:
O(n)， 由于计算过的记忆下了，只要n次
空间复杂度:
O(n)， 递归调用栈消耗了线性数量级，记忆数组使用了n的空间
*/
#define N 100 + 1
class Solution {
private:
   int arr[N] = {0, 1, 1, } ;
public:
   int fib(int n) {
       if (arr[n] || !n)
           return arr[n] ;
       return arr[n] = (fib(n-1) + fib(n-2))%1000000007 ;
   }
};
  1. 二分查找递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int binary_search(const int* ar, int n, int val, int left, int right)
{
    int pos = -1;
    int mid = (right+left)/2;
    if (n < 1 || ar[mid] == val)
    {
        pos = mid;
    }
    else if(ar[mid]>val)
    {
        return binary_search(ar, n/2, val, left, right-1);
    }
    else
    {
        return binary_search(ar, n/2, val, left+1, right);
    }
    return pos;
}
/*
int FindValueIndex(const int* ar, int n, int val)
{
if (n < 1 || ar[n-1] == val)
{
    return n-1;
}
   else
   {
       return FindValueIndex(ar, n-1, val);
   }
}
*/
int findValue(const int*ar, int n,int val)
{
    if(ar==NULL) return -1;
    return binary_search(ar, n, val, 0, n-1);
}
  1. 思考以下代码'#'会输出几次？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void fun(int i,int n)
{
    if(i==n)
    {
        printf("# ");
    }
    else
    {
        fun(i+1,n);
        fun(i+1,n);
    }
}
int main()
{
    int n = 3;
    fun(0,n);
    return 0;
}

答案是输出8次。如果只写了一行fun(i+1,n);则只打印1次。思考为什么。
大体上分析用层次分析，具体调动是深度优先搜索分析。
image-20210816010631178
只调用一次的情况：
image-20210816010852815
只有一条路径，即只打印一次。

调用两次的情况：
image-20210816012051272
规律：调用两次时，此类递归程序的时间复杂度为O(2^n)，空间复杂度为树的高度S(n)。

层次分析：（一层一层看，而不是具体的实现步骤）
image-20210816012904753
由此题可以延伸出全排列/子集树(组合树)问题！