学习数据结构重要的三个部分:指针、结构体、动态内存管理(malloc、calloc、realloc、free)。
1.为什么存在动态内存分配?
1.空间开辟大小是固定的;
2.数组在声明时,必须指定数组的长度,它所需要的内存在编译时分配。
int main()
{int a = 10; //4个字节int arr[10]; //40个字节return 0;
}
2.动态内存函数的介绍
2.1malloc和free
C语言提供了一个动态内存开辟的函数:malloc()
这个函数向内存申请一块连续可用的空间,并返回指向这块空间的指针。
- 如果开辟成功,则返回一个指向开辟好的空间的指针;
- 如果开辟失败,则返回一个NULL指针。因此malloc的返回值一定要做检查;
- 返回值的类型是void*,所以malloc函数并不知道开辟空间的类型,具体在使用的时候使用者自己来决定。
- 如果参数size为0,malloc的行为是标准未定义的,取决于编译器。
#include <stdlib.h>
#include <string.h>
#include <errno.h>int main()
{int arr[10] = {0};//动态内存开辟int* p = (int*)malloc(40);if (p == NULL){printf("%s\n", strerror(errno));return 1;}//使用int i = 0;for (i = 0; i < 10; i++){*(p+i) = i;}//打印for (i = 0; i < 10; i++){printf("%d ", *(p+i)); //0 1 2 3 4 5 6 7 8 9 }return 0;
}
#include <stdlib.h>
#include <string.h>
#include <errno.h>int main()
{int arr[10] = {0};//动态内存开辟int* p = (int*)malloc(INT_MAX);if (p == NULL){printf("%s\n", strerror(errno));return 1;}//使用int i = 0;for (i = 0; i < 10; i++){*(p+i) = i;}//打印for (i = 0; i < 10; i++){printf("%d ", *(p+i)); //0 1 2 3 4 5 6 7 8 9 }return 0;
}
free(动态内存的释放和回收)
void free(void* ptr)
- 如果参数ptr指向的空间不是动态开辟的,那么free函数的行为是未定义的;
- 如果参数ptr是NULL指针,则函数什么事情也不做。
没有free,并不是说内存空间就不回收了。当程序退出时,系统会自动回收内存空间。
#include <stdlib.h>
#include <string.h>
#include <errno.h>int main()
{int arr[10] = {0};//动态内存开辟int* p = (int*)malloc(40);if (p == NULL){printf("%s\n", strerror(errno));return 1;}//使用int i = 0;for (i = 0; i < 10; i++){*(p+i) = i;}//打印for (i = 0; i < 10; i++){printf("%d ", *(p+i)); //0 1 2 3 4 5 6 7 8 9 }free(p);p = NULL; //最好的做法,free释放后,赋值为NULLreturn 0;
}
//error,必须释放动态开辟的空间
int main()
{int a = 10;int* p = &a;//···free(p); p = NULL;return 0;
}
int main()
{int* p = NULL;free(p); //啥事也不干return 0;
}
2.2calloc
#include <stdlib.h>
#include <string.h>
#include <errno.h>//开辟10个整型的空间
int main()
{int* p = (int*)calloc(10, sizeof(int));if (p == NULL){printf("%s\n", strerror(errno));return 1;}//打印int i = 0;for (i = 0; i < 10; i++){printf("%d ", *(p+i)); //calloc会初始化为全0}//释放free(p);p = NULL;return 0;
}
可以理解为:calloc=malloc+memset
2.3realloc
#include <stdlib.h>
#include <string.h>
#include <errno.h>int main()
{int* p = (int*)malloc(40);if (NULL == p){printf("%s\n", strerror(errno));return 1;}//使用1 2 3 4 5 6 7 8 9 10int i = 0;for (i = 0; i < 10; i++){*(p+i) = i+1;}//扩容int* ptr = (int*)realloc(p, 80);if (ptr != NULL) //扩容成功{p = ptr;}//打印for (i = 0; i < 10; i++){printf("%s\n", *(p+i)); //1 2 3 4 5 6 7 8 9 10}//释放free(p);p = NULL;return 0;
}
第一种情况:
第二种情况:
int main()
{realloc(NULL, 40); //等价于malloc(40);return 0;
}
练习:动态版本的通讯录
动态版本的通讯录:
1.通讯录默认能存放3个人的信息
2.如果空间不够了,就增加空间,每次增加2个人的空间
//test.c
#define _CRT_SECURE_NO_WARNINGS #include "contact.h"void menu()
{printf("*************************************************\n");printf("************1.add 2.del**********************\n");printf("************3.search 4.modify*******************\n");printf("************5.show 6.sort*********************\n");printf("************ 0.exit **********************\n");printf("*************************************************\n");
}
int main()
{int input = 0;Contact con; //通讯录InitContact(&con); //初始化通讯录do{menu();printf("请选择:>");scanf("%d", &input);switch (input){case 1:AddContact(&con);break;case 2:DelContact(&con);break;case 3:SearchContact(&con);break;case 4:ModifyContact(&con);break;case 5:ShowContact(&con);break;case 6:SortContact(&con);break;case 0:DestroyContact(&con); //动态版本,销毁通讯录printf("退出通讯录\n");break;default:printf("选择错误\n");break;}} while (input);return 0;
}
//contact.h
#pragma once#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>#define DEFAULT_SZ 3
#define INC_SZ 2#define MAX 100
#define MAX_NAME 20
#define MAX_SEX 10
#define MAX_TELE 12
#define MAX_ADDR 30//类型的声明
typedef struct PeoInfo //人的信息
{char name[MAX_NAME];int age;char sex[MAX_SEX];char tele[MAX_TELE];char addr[MAX_ADDR];
}PeoInfo;//静态版本
//typedef struct Contact //通讯录的信息
//{
// PeoInfo data[MAX]; //存放人的信息
// int count; //记录当前通讯录中实际人的个数
//}Contact;//动态版本
typedef struct Contact //通讯录的信息
{PeoInfo* data; //存放人的信息int count; //记录当前通讯录中实际人的个数int capacity;//记录当前通讯录的容量
}Contact;int InitContact(Contact* pc); //初始化通讯录void DestroyContact(Contact* pc); //动态版本,销毁通讯录void AddContact(Contact* pc); //添加联系人的通讯录void ShowContact(const Contact* pc); //打印通讯录的信息void DelContact(Contact* pc); //删除指定联系人void SearchContact(Contact* pc); //查找指定联系人void ModifyContact(Contact* pc); //修改指定联系人void SortContact(Contact* pc); //排序通讯录中的内容,可以按照名字来排序,按照年龄来排序···
//contact.c
#define _CRT_SECURE_NO_WARNINGS #include "contact.h"//静态版本
//void InitContact(Contact* pc)
//{
// assert(pc);
// pc->count = 0;
// memset(pc->data, 0, sizeof(pc->data));
//}//动态版本
int InitContact(Contact* pc)
{assert(pc);pc->count = 0;pc->data = (PeoInfo*)calloc(3, sizeof(PeoInfo));if (pc->data == NULL){printf("InitContact::%s\n", strerror(errno));return 1;}pc->capacity = DEFAULT_SZ;return 0;
}void DestroyContact(Contact* pc) //动态版本,销毁通讯录
{assert(pc);free(pc->data);pc->data = NULL;
}//静态版本
//void AddContact(Contact* pc)
//{
// assert(pc);
// if (pc->count == MAX)
// {
// printf("通讯录已满,无法添加\n");
// return;
// }
// printf("请输入名字:>");
// scanf("%s", pc->data[pc->count].name);
// printf("请输入年龄:>");
// scanf("%d", &(pc->data[pc->count].age));
// printf("请输入性别:>");
// scanf("%s", pc->data[pc->count].sex);
// printf("请输入电话:>");
// scanf("%s", pc->data[pc->count].tele);
// printf("请输入地址:>");
// scanf("%s", pc->data[pc->count].addr);
//
// pc->count++;
// printf("添加成功\n");
//}//动态版本
void CheckCapacity(Contact* pc)
{if (pc->count == pc->capacity){PeoInfo* ptr = (PeoInfo*)realloc(pc->data, (pc->capacity + INC_SZ)*sizeof(PeoInfo));if (ptr == NULL){printf("AddContact::%s\n", strerror(errno));return;}else{pc->data = ptr;pc->capacity += INC_SZ;printf("扩容成功\n");}}
}
void AddContact(Contact* pc)
{assert(pc);//扩容CheckCapacity(pc);printf("请输入名字:>");scanf("%s", pc->data[pc->count].name);printf("请输入年龄:>");scanf("%d", &(pc->data[pc->count].age));printf("请输入性别:>");scanf("%s", pc->data[pc->count].sex);printf("请输入电话:>");scanf("%s", pc->data[pc->count].tele);printf("请输入地址:>");scanf("%s", pc->data[pc->count].addr);pc->count++;printf("添加成功\n");
}void ShowContact(const Contact* pc)
{assert(pc);int i = 0;printf("%-20s\t%-5s\t%-5s\t%-12s\t%-30s\n", "名字", "年龄", "性别", "电话", "地址");for (i = 0; i < pc->count; i++){printf("%-20s\t%-5d\t%-5s\t%-12s\t%-30s\n", pc->data[i].name,pc->data[i].age,pc->data[i].sex,pc->data[i].tele,pc->data[i].addr);}
}static int FindByName(Contact* pc, char name[])
{assert(pc);int i = 0;for (i = 0; i < pc->count; i++){if (0 == strcmp(pc->data[i].name, name)){return i;}}return -1;
}void DelContact(Contact* pc)
{char name[MAX_NAME] = { 0 };assert(pc);int i = 0;if (pc->count == 0){printf("通讯录为空,没有信息可以删除\n");return;}printf("请输入要删除人的名字:>");scanf("%s", name);//删除//1.查找int pos = FindByName(pc, name);if (pos == -1){printf("要删除的人不存在\n");return;}//2.删除for (i = pos; i < pc->count - 1; i++){pc->data[i] = pc->data[i + 1];}pc->count--;printf("删除成功\n");}void SearchContact(Contact* pc)
{assert(pc);char name[MAX_NAME] = { 0 };printf("请输入要查找人的名字:>");scanf("%s", name);//1.查找int pos = FindByName(pc, name);if (pos == -1){printf("要查找的人不存在\n");return;}//2.打印printf("%-20s\t%-5s\t%-5s\t%-12s\t%-30s\n", "名字", "年龄", "性别", "电话", "地址");printf("%-20s\t%-5d\t%-5s\t%-12s\t%-30s\n", pc->data[pos].name,pc->data[pos].age,pc->data[pos].sex,pc->data[pos].tele,pc->data[pos].addr);}void ModifyContact(Contact* pc)
{assert(pc);char name[MAX_NAME] = { 0 };printf("请输入要修改人的名字:>");scanf("%s", name);//1.查找int pos = FindByName(pc, name);if (pos == -1){printf("要修改的人不存在\n");return;}printf("要修改的人的信息已经找到,接下来开始修改\n");//2.修改printf("请输入名字:>");scanf("%s", pc->data[pos].name);printf("请输入年龄:>");scanf("%d", &(pc->data[pos].age));printf("请输入性别:>");scanf("%s", pc->data[pos].sex);printf("请输入电话:>");scanf("%s", pc->data[pos].tele);printf("请输入地址:>");scanf("%s", pc->data[pos].addr);printf("修改成功\n");
}int cmp_peo_by_name(const void* e1, const void* e2)
{return strcmp(((PeoInfo*)e1)->name, ((PeoInfo*)e2)->name);
}
void SortContact(Contact* pc) //按照名字来排序
{assert(pc);qsort(pc->data, pc->count, sizeof(PeoInfo), cmp_peo_by_name);printf("排序成功\n");
}
3.常见的动态内存错误
3.1对NULL指针的解引用操作
#include <stdlib.h>
int main()
{int* p = (int*)malloc(40);*p = 20; //如果p的值是NULL,就会出现问题return 0;
}
修正:
#include <stdlib.h>int main()
{int* p = (int*)malloc(40);if (p == NULL){return 1;}*p = 20;free(p);p = NULL;return 0;
}
3.2对动态开辟空间的越界访问
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>int main()
{int* p = (int*)malloc(40);if (p == NULL){printf("%s\n", strerror(errno));return 1;}//使用int i = 0;for (i = 0; i <= 10; i++) {p[i] = i;}free(p);p = NULL;return 0;
}
3.3对非动态开辟内存使用free释放
#include <stdlib.h>int main()
{int a = 10;int* p = &a;//···free(p);p = NULL;return 0;
}
3.4使用free释放一块动态开辟内存的一部分
#include <stdlib.h>int main()
{int* p = (int*)malloc(40);if (p == NULL){return 1;}//使用int i = 0;for (i = 0; i < 5; i++){*p = i;p++;}//释放free(p); //此时p的地址早已不是起始位置,必须指向开辟空间的起始位置p = NULL;return 0;
}
3.5对同一块动态内存多次释放
#include <stdlib.h>int main()
{int* p = (int*)malloc(40);//···free(p);//···free(p);return 0;
}
修正:
#include <stdlib.h>int main()
{int* p = (int*)malloc(40);//···free(p);p = NULL;//···free(p);return 0;
}
3.6动态开辟内存忘记释放(内存泄漏)
#include <stdlib.h>void test()
{int* p = (int*)malloc(100);//···int flag = 0;scanf("%d", &flag); //5if (flag == 5)return;free(p);p = NULL;
}int main()
{test();//···return 0;
}
场景2:
#include <stdlib.h>int* test()
{int* p = (int*)malloc(100); //开辟空间if (p == NULL){return p;}//···return p;
}int main()
{int* ret = test();//忘记释放了return 0;
}
4.经典笔试题(出自《高质量的C-C++编程》)
修改版本2:(有点别扭)
#include <stdio.h>
int main()
{printf("hello world\n"); //hello worldchar* p = "hello world";printf(p); //hello worldprintf("%s\n", p); //hello worldreturn 0;
}//要理解底层原理,传递的是h字符的地址
返回栈空间地址的问题。
#include <stdio.h>int* test()
{//返回栈空间地址的问题int a = 10;return &a;
}int main()
{int* p = test();printf("%d\n", *p); //10return 0;
}
#include <stdio.h>int* test()
{int a = 10;return &a;
}int main()
{int* p = test();printf("hehe\n"); //heheprintf("%d\n", *p); //5return 0;
}
5.C/C++程序的内存开辟
自行学习。
书籍《深入理解计算机系统》
6.柔性数组(flexible array)
C99中,结构中的最后一个元素允许是未知大小的数组,这就叫做柔性数组成员。
typedef struct st_type
{int i;int a[0]; //柔性数组成员
}type_a;
有些编译器会报错无法编译可以写成:
typedef struct st_type
{int i;int a[]; //柔性数组成员
}type_a;
6.1柔性数组的特点
结构中的柔性数组成员前面必须至少一个其它成员;
sizeof返回的这种结构大小不包括柔性数组的内存;
包含柔性数组成员的结构用malloc()函数进行内存的动态分配,并且分配的内存应该大于结构的大小,以上适应柔性数组的预期大小。
#include <stdio.h>struct S
{int n;int arr[]; //柔性数组成员
};int main()
{int sz = sizeof(struct S);printf("%d\n", sz); //4 return 0;
}
6.2柔性数组的使用
#include <stdio.h>
#include <stdlib.h>struct S
{int n;int arr[]; //柔性数组成员
};int main()
{//柔性数组的使用struct S* ps = (struct S*)malloc(sizeof(struct S) + 40);if (ps == NULL){//···return 1;}ps->n = 100;int i = 0;for (i = 0; i < 10; i++){ps->arr[i] = i;}//打印for (i = 0; i < 10; i++){printf("%d ", ps->arr[i]);}//调整struct S* ptr = (struct S*)realloc(ps, sizeof(struct S) + 80);if (ptr != NULL){ps = ptr;ptr = NULL;}//···//释放free(ps);ps = NULL;return 0;
}
方案二:
#include <stdio.h>
#include <stdlib.h>
struct S
{int n;int* arr;
};int main()
{struct S* ps =(struct S*)malloc(sizeof(struct S));if (ps == NULL){return 1;}ps->n = 100;ps->arr = (int*)malloc(40);if (ps->arr == NULL){return 1;}//使用int i = 0;for (i = 0; i < 10; i++){ps->arr[i] = i;}//打印for (i = 0; i < 10; i++){printf("%d ", ps->arr[i]);}//调整int* ptr = (int*)realloc(ps->arr, 80);if (ptr == NULL){return 1;}//释放free(ps->arr);free(ps);ps = NULL;return 0;
}
方案二:释放时容易忘记导致内存泄漏;多次开辟空间,碎片化严重,导致内存利用率下降。
6.3柔性数组的优势
方便内存释放;
理论上有利于访问速度(连续的内存有利于访问速度,减少内存碎片)。
总结
今天就暂且更新至此吧,期待下周再会。如有错误还请不吝赐教。希望对您学习有所帮助,翻页前留下你的支持,以防下次失踪了嗷。
作者更新不易,免费关注别手软。