【数据结构】【A鹿】malloc和结构体预备知识

前提

​ 数据结构会经常申请自定义大小的内存空间来组成特殊的数据结构，相比于C语言原本支持的几种数据结构（int，float，double，struct，char），它们固定的作用范围和生命周期会很明显的限制数据结构的高效性，所以我们需要一种可以允许开发人员按照需求自主生成、释放的内存空间用于管理数据结构中的特殊数据。

内存申请、释放

​ C语言提供了几个常用的内存管理函数，只需要调用标准库stdlib.h即可调用。

 #include <stdlib.h>extern void *malloc(unsigned int num_bytes);
void free(void *ptr);
void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);
//常用内存管理函数

malloc()

extern void *malloc(unsigned int num_bytes);

​ malloc()函数的定义如上所示，函数类型为void*，这表示为返回类型是未确定指针类型，在C/C++中未确定的指针类型可以通过强制转换符来转化为任意指针。函数实参为所需要的空间大小，常用的书写方法是sizeof(数据结构类型)*所需个数。

​ 如果返回成功，则返回申请大小的内存指针，如果失败则返回NULL指针。以下是malloc()申请一个带有4个int类型数据内存的方法:

int* ptr;
ptr = (int*)malloc(sizeof(int) * 4);
ptr[0] = 1;//实现结果可以认为ptr是一个携带有4个元素的整型数组（动态数组）
printf("%d", ptr[0]);
//输出结果为1

​ 由上可以得知，malloc()在使用时：

• 它的接收体为一个目标类型的指针。int* ptr

• 需要使用目标类型的操作符进行强制转换。(int*)

• 如果申请的空间大于一个的话使用个数和空间大小相乘。sizeof(int)*4

• 在使用目标内存中的元素时，可以使用数组操作符[]来选定所需元素。ptr[0]

  ​

free()

​ malloc()用于申请空间，申请的内存空间如果没有手动使用free()释放的话，它将永远占据这块内存成为垃圾内存（内存泄漏）。所以必须要每一个malloc()唯一对应一个free()。以下是free()的声明：

void free(void *ptr);

​ free()的实际原理实际上是将原本指针指向的位置设置为无效，并不会改变原本指针指向的内存，所以养成良好习惯，请将free()后的指针设置为NULL，防止再次使用出现野指针错误。free()必须和malloc一一对应，free缺失将会内存泄漏，而多次free同一指针将会报错。

free(ptr);
ptr=NULL;
//养成良好习惯，free后的指针一定要设置为NULL并且禁止再次使用。

利用malloc()和free()创建动态内存

​ 试想一下这个案例：

​ 如果需要制作一个注册程序，一般情况下将会怎么写？

​ 一般想法是写一个接收字符串的函数进行登记，但是C语言的字符串一旦定义以后将不能更改个数，如果目标对象只有中国人，则字符串最多使用6个就可以注册大部分人的姓名，即使有两字姓名的人使用了6个字符的字符串，多出的空余也可以不计。

​ 如果需要你制作一个能供大量中国人、外国人一起使用的注册系统，你该怎么定义这个字符串的存储大小？

​ 如果你字符串大小使用太小，很多外国人的姓名无法登记上去；如果你的字符串定义太大，则在登记中国人时会占用太多空白的存储空间。在此时，你就需要使用动态空间来解决这个问题。

void reg()
{int max_length = 30;		//设置一个最长姓名的最大限制char* base_name;			//这是接收姓名的基础姓名，他有固定长度为最大限制base_name = (char*)malloc(sizeof(char) * max_length);//给基础姓名给予一个最大限制的动态空间scanf("%s",base_name);//输入姓名//不要用vs提供的scanf_s会出错，用vs的同学可以在文件头加#pragma warning(disable:4996);无效C4996错误int real_length= strlen(base_name);//用strlen来计算base_name的长度，也就是真实姓名占用的长度。strlen需要string.hchar* real_name;//真正记录姓名的动态空间，真实姓名real_name = (char*)malloc(sizeof(char) * real_length);//为真实姓名申请一个长度为真实姓名长度的空间for (int i = 0; i < real_length; i++){real_name[i] = base_name[i];}//简单的复制free(base_name);//释放占用空间的基础姓名printf("%s", real_name);//没写登记保存函数，使用输出代替。free(real_name);//登记完成后释放基础姓名空间
}

​ 我给每一行都加了注释，想详细了解方法的同学可以一行一行看。大体做法是：

1.先申请一个很大长度的动态空间，确保所有人的名称都可以输入，用动态空间接收输入的姓名

2.给动态空间计算长度，这个长度是实际姓名的长度

3.用实际姓名的长度申请一段空间，将姓名复制进入实际姓名的变量

4.free之前接收姓名的动态空间

5.将实际姓名的动态空间保存，free掉实际姓名的动态空间

​

​ 这样可以使系统的内存使用率达到最大化，所有人的姓名都是按照它的实际长度进行保存，不会占用其他空间，并且动态的空间申请与释放也保证了程序再运行时不需要占用过多系统资源，每次只需要一个人的姓名长度即可。所以动态空间是一种很重要的功能，它给数据结构的空间申请带来了很大的便利。

calloc()与realloc()

void *calloc(size_t nmemb, size_t size);
//colloc()多一个参数，实际上是个数，也就是原本malloc()中的sizeof(type)*num中的num，所以这里的size只用sizeof(type)，个数num写在第一个参数位置上就行了

​ 使用malloc时，申请的空间是随机的，内存中可能会有垃圾数据，不小心调用会导致程序出错。而calloc()解决了这一问题，calloc()作用与malloc()完全相同，calloc()在申请空间后会将空间数据初始化为0，避免了垃圾内存错误。使用calloc()代替malloc()是好习惯，但是数据结构考研资料更常用的是malloc()，所以这里只做了解。

void *realloc(void *ptr, size_t size);//void *ptr放置原本动态空间指针，realloc赋值给新的空间指针

​ realloc()的作用：

1.如果重新申请的空间比原空间大，则开辟更大的空间供给使用，获取新的空间指针，原本数据不会被删除

2.如果重新申请的空间比原空间小，则删除多余数据，获得新的空间指针。

​ 正确的写法是声明一个新的指针，让其指向新的空间。原本指针实际上还是指向的这段空间，所以新指针的修改也会影响到原指针的值。新指针生命周期结束前不要free()原指针，否则会将新指针指向的数据一同清除了。以下是一个缩小空间的实例：

	int* i;i = (int*)malloc(sizeof(int) * 2);i[0] = 1;i[1] = 2;int* p;p=(int*)realloc(i,sizeof(int));printf("%d", p[0]);//输出结果为：1

结构体

​ 结构体是一种用户自定义数据结构，用户可以将多种基础数据类型整合入一个结构体中构成一种新的数据结构。C语言的结构体是C++类的前提，所以会使用面向对象语言类的同学可以认为结构体就是C语言的类，只不过这个类中只有单独的属性(变量)，没有方法(函数)。

通用使用方法

struct a
{int num;char name[2];
};main()
{a student1;student1.name="A鹿";student1.num=1;
}

​ 以上是一个结构体的使用方法。首先结构体本体包含了大括号和分号，内容是结构体的数据。

struct a
{int num;char name[2];//这里面的变量可以按需求更改
};//不要忘了分号，否则会报错

​ 因为结构体只是一种数据类型，所以在使用结构体变量的时候需要进行定义，结构体的定义和普通变量一样，不过定义符号是结构体名。

	a student1;

​ 调用结构体单独属性时使用.符号进行标点，想查看某一个属性就用.加属性名。

	student1.name="A鹿";student1.num=1;

​

结构体数组与指针

​ 一般的数组定义方法和普通变量的相同，再使用数组中某一个元素的属性时需要在前面标识。

	a student[2];student[0].name[0] = 'A';student[0].name[0] = '鹿';student[0].num = 2;

​ 如果有指针指向结构体，想通过指针调用结构体属性的话，则需要使用复合符号->

struct a
{int num;char name[2];
};int main()
{a *ptr;ptr=(a*)malloc(sizeof(a));//用malloc申请一个结构体a的动态空间ptr->num=2;//使用符合符号->来调用属性ptr->name[0] = 'A';ptr->name[1] = '2';
}

​ 如果申请的动态空间不止一个，即指针是一个结构体的动态数组，则用数组符号[]调用目标对象，然后用.来调用目标属性。

    a* ptr;ptr = (a*)malloc(sizeof(a)*2);ptr[0].num = 2;//加入[]符号后，整体变为了结构体类型变量而非数组，所以可以使用.来调用特定属性ptr[1].name[0] = 'A';ptr[0].name[1] = '2';

特殊结构体用法

​ C语言结构体在定义时没有进行标准化，所以在C语言中，有特定的结构体书写方法。不建议同学们使用这些方法来书写结构体，会使程序复杂性升高，但是必须要认识这种写法（教材非常喜欢使用）。

struct
{int num;char name[2];
}A,B;int main()
{A.num = 1;B.num = 2;printf("%d  %d", A.num, B.num);//控制台输出结构:1  2
}

​ 结构体是可以没有名称的，没有名称的结构体可以在结尾的分号前加入变量名（对象名），这里的变量名是默认的该结构体类型的变量，可以直接使用。变量可以有很多个，中间使用,隔开。

结构体与函数

​ 结构体可以作为函数参数。

struct A
{int num;char name[2];
};void funct(A a)//和普通变量的作为参数的方式相同，结构体+对象名
{a.num = 1;
}

​ 结构体也可以作为函数类型，这就使函数返回值的接收变量必须是相同的结构体变量。

struct A
{int num;char name[2];
};A funct()
{A a;a.num = 1;return a;
}
int main()
{A a;a.num = 0;a=funct();//此处a被返回结果覆盖printf("%d", a.num);
}
//控制台输出结果为：1

​ 结构体的默认传递方式是值传递，函数内的计算不会影响到实参的值。

struct A
{int num;char name[2];
};void funct(A a)
{a.num = 1;
}int main()
{A a;a.num = 0;funct(a);//此处是值传递，所以a.num的内容不会被改变，依旧是0printf("%d", a.num);
}
//控制台输出结果：0

​ 如果希望通过引用传递结构体，则可以采用以下方式进行传递：

​ 可以将函数与结构体有关的参数设置为结构体指针，因为指针是引用传递，所以函数内的计算结构将会被保留。

struct A
{int num;char name[2];
};void funct(A*a)
{a->num = 1;
}
int main()
{A a;A* b = &a;//这步是必要的，否则b是没有初始化的指针（没有指向），未初始化的指针时不能进行计算的funct(b);printf("%d", b->num);
}
//输出结果为1

​ 可以使用&取址符取出结构体变量的地址，进行传递。注意，此处和普通传递的唯一区别就是函数参数列表中的变量a前缀了一个&，传递参数是没有这个符号的。

struct A
{int num;char name[2];
};void funct(A &a)//和普通传递的唯一区别技术这个的方多了一个&
{a.num = 1;
}
int main()
{A a;funct(a);//此处不能加入&，否则会报错printf("%d", a.num);
}

指针（没有指向），未初始化的指针时不能进行计算的
funct(b);
printf("%d", b->num);
}
//输出结果为1

​	可以使用`&`取址符取出结构体变量的地址，进行传递。注意，此处和普通传递的唯一区别就是函数参数列表中的变量a前缀了一个`&`，传递参数是没有这个符号的。```C
struct A
{int num;char name[2];
};void funct(A &a)//和普通传递的唯一区别技术这个的方多了一个&
{a.num = 1;
}
int main()
{A a;funct(a);//此处不能加入&，否则会报错printf("%d", a.num);
}