有的时候,我们所遇到的数据结构,不仅仅是一群数字或者是字符串那么简单。比如我们每一个人的学籍信息,学号是一个长整数,名字却是字符;甚至有更复杂的情况,这种问题在现实生活中并不少见。我们之前学过一种叫数组的数据结构,它可以允许我们把很多同类型的数据集中在一起处理。相对于之前,这已经是一次极大的进步。但是,新的问题,往往又会出现,这个时候,我们就得上更高端的装备——结构体。
相比于数组,结构体有以下的更强大的优势:
批量存储数据
存储不同类型的数据
支持嵌套
结构体的声明与定义
声明
结构体的声明使用struct关键字,如果我们想要把我们的学籍信息组织一下的话,可以这样表示:
struct Info { unsigned long identifier;//学号,用无符号长整数表示 char name[20];//名字,用字符数组表示 unsigned int year;//入学年份,用无符号整数表示 unsigned int years;//学制,用无符号整数表示 }
这样,我们就相当于描绘好了一个框架,以后要用的话直接定义一个这种类型的变量就好了。
定义
我们刚刚申请了一个名叫Info的结构体类型,那么理论上我们可以像声明其他变量的操作一样,去声明我们的结构体操作,但是C语言中规定,声明结构体变量的时候,struct关键字是不可少的。
struct 结构体类型名 结构体变量名
不过,你可以在某个函数里面定义:
#include struct Info { unsigned long identifier;//学号,用无符号长整数表示 char name[20];//名字,用字符数组表示 unsigned int year;//入学年份,用无符号整数表示 unsigned int years;//学制,用无符号整数表示 }; int main(void) { /** *在main函数中声明结构体变量 *结构体变量名叫info *struct关键字不能丢 */ struct Info info; ... }
也可以在声明的时候就把变量名定义下来(此时这个变量是全局变量):
#include struct Info { unsigned long identifier;//学号,用无符号长整数表示 char name[20];//名字,用字符数组表示 unsigned int year;//入学年份,用无符号整数表示 unsigned int years;//学制,用无符号整数表示 } info; /** *此时直接定义了变量 *该变量是全局变量 *变量名叫info */ int main(void) { ... }
访问结构体成员
结构体成员的访问有点不同于以往的任何变量,它是采用点号运算符.来访问成员的。比如,info.name就是引用info结构体的name成员,是一个字符数组,而info.year则可以查到入学年份,是个无符号整型。
比如,下面开始录入学生的信息:
//Example 01 #include struct Info { unsigned long identifier;//学号,用无符号长整数表示 char name[20];//名字,用字符数组表示 unsigned int year;//入学年份,用无符号整数表示 unsigned int years;//学制,用无符号整数表示 }; int main(void) { struct Info info; printf("请输入学生的学号:"); scanf("%d", &info.identifier); printf("请输入学生的姓名:"); scanf("%s", info.name); printf("请输入学生的入学年份:"); scanf("%d", &info.year); printf("请输入学生的学制:"); scanf("%d", &info.years); printf(" 数据录入完毕 "); printf("学号:%d 姓名:%s 入学年份:%d 学制:%d 毕业时间:%d ", info.identifier, info.name, info.year, info.years, info.year + info.years); return 0; }
运行结果如下:
//Consequence 01 请输入学生的学号:20191101 请输入学生的姓名:Harris 请输入学生的入学年份:2019 请输入学生的学制:4 数据录入完毕 学号:20191101 姓名:Harris 入学年份:2019 学制:4 毕业时间:2023
初始化结构体
像数组一样,结构体也可以在定义的时候初始化,方法也几乎一样:
struct Info info = { 20191101, "Harris", 2019, 4 };
在C99标准中,还支持给指定元素赋值(就像数组一样):
struct Info info = { .name = "Harris", .year = 2019 };
对于没有被初始化的成员,则「数值型」成员初始化为0,「字符型」成员初始化为‘’。
对齐
下面这个代码,大家来看看会发生什么:
//EXample 02 V1 #include int main(void) { struct A { char a; int b; char c; } a = {'a', 10, 'o'}; printf("size of a = %d ", sizeof(a)); return 0; }
我们之前学过,char类型的变量占1字节,int类型的变量占4字节,那么这么一算,一个结构体A型的变量应该就是6字节了。别急,我们看运行结果:
//COnsequence 02 V1 size of a = 12
怎么变成12了呢?标准更新了?老师教错了?都不是。我们把代码改一下:
//EXample 02 V2 #include int main(void) { struct A { char a; char c; int b; } a = {'a', 'o', 10}; printf("size of a = %d ", sizeof(a)); return 0; }
结果:
//Consequence 02 V2 size of a = 8
实际上,这是编译器对我们程序的一种优化——内存对齐。在第一个例子中,第一个和第三个成员是char类型是1个字节,而中间的int却有4个字节,为了对齐,两个char也占用了4个字节,于是就是12个字节。
而在第二个例子里面,前两个都是char,最后一个是int,那么前两个可以一起占用4个字节(实际只用2个,第一个例子也同理,只是为了访问速度更快,而不是为了扩展),最后的int占用4字节,合起来就是8个字节。
关于如何声明结构体来节省内存容量,可以阅读下面的这篇文章,作者是艾瑞克·雷蒙,时尚最具争议性的黑客之一,被公认为开源运动的主要领导者之一:
英文原版,中文版
结构体嵌套
在学籍里面,如果我们的日期想要更加详细一些,精确到day,这时候就可以使用结构体嵌套来完成:
#include struct Date { unsigned int year; unsigned int month; unsigned int day; }; struct Info { unsigned long identifier;//学号,用无符号长整数表示 char name[20];//名字,用字符数组表示 struct Date date;/*---入学日期,用结构体Date表示---*/ unsigned int years;//学制,用无符号整数表示 }; int main(void) { ... }
如此一来,比我们单独声明普通变量快多了。
不过,这样访问变量,就必须用点号一层层往下访问。比如要访问day这个成员,那就只能info.date.day而不能直接info.date或者info,day。
//Example 03 #include struct Date { unsigned int year; unsigned int month; unsigned int day; }; struct Info { unsigned long identifier;//学号,用无符号长整数表示 char name[20];//名字,用字符数组表示 struct Date date;/*---入学日期,用结构体Date表示---*/ unsigned int years;//学制,用无符号整数表示 }; int main(void) { struct Info info; printf("请输入学生的学号:"); scanf("%d", &info.identifier); printf("请输入学生的姓名:"); scanf("%s", info.name); printf("请输入学生的入学年份:"); scanf("%d", &info.date.year); printf("请输入学生的入学月份:"); scanf("%d", &info.date.month); printf("请输入学生的入学日期:"); scanf("%d", &info.date.day); printf("请输入学生的学制:"); scanf("%d", &info.years); printf(" 数据录入完毕 "); printf("学号:%d 姓名:%s 入学时间:%d/%d/%d 学制:%d 毕业时间:%d ", info.identifier, info.name, info.date.year, info.date.month, info.date.day, info.years, info.date.year + info.years); return 0; }
运行结果如下:
//Consequence 03 请输入学生的学号:20191101 请输入学生的姓名:Harris 请输入学生的入学年份:2019 请输入学生的入学月份:9 请输入学生的入学日期:7 请输入学生的学制:4 数据录入完毕 学号:20191101 姓名:Harris 入学时间:2019/9/7 学制:4 毕业时间:2023
结构体数组
刚刚我们演示了存储一个学生的学籍信息的时候,使用结构体的例子。那么,如果要录入一批学生,这时候我们就可以沿用之前的思路,使用结构体数组。
我们知道,数组的定义,就是存放一堆相同类型的数据的容器。而结构体一旦被我们声明,那么你就可以把它看作一个类型,只不过是你自己定义的罢了。
定义结构体数组也很简单:
struct 结构体类型 { 成员; } 数组名[长度]; /****或者这样****/ struct 结构体类型 { 成员; }; struct 结构体类型 数组名[长度];
结构体指针
既然我们可以把结构体看作一个类型,那么也就必然有对应的指针变量。
struct Info* pinfo;
但是在指针这里,结构体和数组就不一样了。我们知道,数组名实际上就是指向这个数组第一个元素的地址,所以可以将数组名直接赋值给指针。而结构体的变量名并不是指向该结构体的地址,所以要使用取地址运算符&才能获取地址:
pinfo = &info;
通过结构体指针来访问结构体有以下两种方法:
(*结构体指针).成员名
结构体指针->成员名
第一个方法由于点号运算符比指针的取值运算符优先级更高,因此需要加一个小括号来确定优先级,让指针先解引用变成结构体变量,在使用点号的方法去访问。
相比之下,第二种方法就直观许多。
这两种方法在实现上是完全等价的,但是点号只能用于结构体变量,而箭头只能够用于指针。
第一种方法:
#include ... int main(void) { struct Info *p; p = &info; printf("学号: ", (*p).identifier); printf("姓名: ", (*p).name); printf("入学时间:%d/%d/%d ", (*p).date.year, (*p).date.month, (*p).date.day); printf("学制: ", (*p).years); return 0; }
第二种方法:
#include ... int main(void) { struct Info *p; p = &info; printf("学号: ", p -> identifier); printf("姓名: ", p -> name); printf("入学时间:%d/%d/%d ", p -> date.year, p -> date.month, p -> date.day); printf("学制: ", p -> years); return 0; }
传递结构体信息
传递结构体变量
我们先来看看下面的代码:
//Example 04 #include int main(void) { struct Test { int x; int y; }t1, t2; t1.x = 3; t1.y = 4; t2 = t1; printf("t2.x = %d, t2.y = %d ", t2.x, t2.y); return 0; }
运行结果如下:
//Consequence 04 t2.x = 3, t2.y = 4
这么看来,结构体是可以直接赋值的。那么既然这样,作为函数的参数和返回值也自然是没问题的了。
先来试试作为参数:
//Example 05 #include struct Date { unsigned int year; unsigned int month; unsigned int day; }; struct Info { unsigned long identifier; char name[20]; struct Date date; unsigned int years; }; struct Info getInput(struct Info info); void printInfo(struct Info info); struct Info getInput(struct Info info) { printf("请输入学号:"); scanf("%d", &info.identifier); printf("请输入姓名:"); scanf("%s", info.name); printf("请输入入学年份:"); scanf("%d", &info.date.year); printf("请输入月份:"); scanf("%d", &info.date.month); printf("请输入日期:"); scanf("%d", &info.date.day); printf("请输入学制:"); scanf("%d", &info.years); return info; } void printInfo(struct Info info) { printf("学号:%d 姓名:%s 入学时间:%d/%d/%d 学制:%d 毕业时间:%d ", info.identifier, info.name, info.date.year, info.date.month, info.date.day, info.years, info.date.year + info.years); } int main(void) { struct Info i1 = {}; struct Info i2 = {}; printf("请录入第一个同学的信息... "); i1 = getInput(i1); putchar(' '); printf("请录入第二个学生的信息... "); i2 = getInput(i2); printf(" 录入完毕,现在开始打印... "); printf("打印第一个学生的信息... "); printInfo(i1); putchar(' '); printf("打印第二个学生的信息... "); printInfo(i2); return 0; }
运行结果如下:
//Consequence 05 请录入第一个同学的信息... 请输入学号:20191101 请输入姓名:Harris 请输入入学年份:2019 请输入月份:9 请输入日期:7 请输入学制:4 请录入第二个学生的信息... 请输入学号:20191102 请输入姓名:Joy 请输入入学年份:2019 请输入月份:9 请输入日期:8 请输入学制:5 录入完毕,现在开始打印... 打印第一个学生的信息... 学号:20191101 姓名:Harris 入学时间:2019/9/7 学制:4 毕业时间:2023 打印第二个学生的信息... 学号:20191102 姓名:Joy 入学时间:2019/9/8 学制:5 毕业时间:2024
传递指向结构体变量的指针
早期的C语言是不允许直接将结构体作为参数直接传递进去的。主要是考虑到如果结构体的内存占用太大,那么整个程序的内存开销就会爆炸。不过现在的C语言已经放开了这方面的限制。
不过,作为一名合格的开发者,我们应该要去珍惜硬件资源。那么,传递指针就是一个很好的办法。
将刚才的代码修改一下:
//Example 06 #include struct Date { unsigned int year; unsigned int month; unsigned int day; }; struct Info { unsigned long identifier; char name[20]; struct Date date; unsigned int years; }; void getInput(struct Info *info); void printInfo(struct Info *info); void getInput(struct Info *info) { printf("请输入学号:"); scanf("%d", &info->identifier); printf("请输入姓名:"); scanf("%s", info->name); printf("请输入入学年份:"); scanf("%d", &info->date.year); printf("请输入月份:"); scanf("%d", &info->date.month); printf("请输入日期:"); scanf("%d", &info->date.day); printf("请输入学制:"); scanf("%d", &info->years); } void printInfo(struct Info *info) { printf("学号:%d 姓名:%s 入学时间:%d/%d/%d 学制:%d 毕业时间:%d ", info->identifier, info->name, info->date.year, info->date.month, info->date.day, info->years, info->date.year + info->years); } int main(void) { struct Info i1 = {}; struct Info i2 = {}; printf("请录入第一个同学的信息... "); getInput(&i1); putchar(' '); printf("请录入第二个学生的信息... "); getInput(&i2); printf(" 录入完毕,现在开始打印... "); printf("打印第一个学生的信息... "); printInfo(&i1); putchar(' '); printf("打印第二个学生的信息... "); printInfo(&i2); return 0; }
此时传递的就是一个指针,而不是一个庞大的结构体。
动态申请结构体
结构体也可以在堆里面动态申请:
//Example 01 #include ... int main(void) { struct Info *i1; struct Info *i2; i1 = (struct Info *)malloc(sizeof(struct Info)); i2 = (struct Info *)malloc(sizeof(struct Info)); if (i1 == NULL || i2 == NULL) { printf("内存分配失败! "); exit(1); } printf("请录入第一个同学的信息... "); getInput(i1); putchar(' '); printf("请录入第二个学生的信息... "); getInput(i2); printf(" 录入完毕,现在开始打印... "); printf("打印第一个学生的信息... "); printInfo(i1); putchar(' '); printf("打印第二个学生的信息... "); printInfo(i2); free(i1); free(i2); return 0; }
实战:建立一个图书馆数据库
实际上,我们建立的数组可以是指向结构体指针的数组。
代码实现如下:
//Example 02 #include #include #define MAX_SIZE 100 struct Date { int year; int month; int day; }; struct Book { char title[128]; char author[48]; float price; struct Date date; char publisher[48]; }; void getInput(struct Book* book);//录入数据 void printBook(struct Book* book);//打印数据 void initLibrary(struct Book* lib[]);//初始化结构体 void printLibrary(struct Book* lib[]);//打印单本书数据 void releaseLibrary(struct Book* lib[]);//释放内存 void getInput(struct Book* book) { printf("请输入书名:"); scanf("%s", book->title); printf("请输入作者:"); scanf("%s", book->author); printf("请输入售价:"); scanf("%f", &book->price); printf("请输入出版日期:"); scanf("%d-%d-%d", &book->date.year, &book->date.month, &book->date.day); printf("请输入出版社:"); scanf("%s", book->publisher); } void printBook(struct Book* book) { printf("书名:%s ", book->title); printf("作者:%s ", book->author); printf("售价:%.2f ", book->price); printf("出版日期:%d-%d-%d ", book->date.year, book->date.month, book->date.day); printf("出版社:%s ", book->publisher); } void initLibrary(struct Book* lib[]) { for (int i = 0; i < MAX_SIZE; i++) { lib[i] = NULL; } } void printLibrary(struct Book* lib[]) { for (int i = 0; i < MAX_SIZE; i++) { if (lib[i] != NULL) { printBook(lib[i]); putchar(' '); } } } void releaseLibrary(struct Book* lib[]) { for (int i = 0; i < MAX_SIZE; i++) { if (lib[i] != NULL) { free(lib[i]); } } } int main(void) { struct Book* lib[MAX_SIZE]; struct Book* p = NULL; int ch, index = 0; initLibrary(lib); while (1) { printf("请问是否要录入图书信息(Y/N):"); do { ch = getchar(); } while (ch != 'Y' && ch != 'N'); if (ch == 'Y') { if (index < MAX_SIZE) { p = (struct Book*)malloc(sizeof(struct Book)); getInput(p); lib[index] = p; index++; putchar(' '); } else { printf("数据库已满! "); break; } } else { break; } } printf(" 数据录入完毕,开始打印验证... "); printLibrary(lib); releaseLibrary(lib); return 0; }
运行结果如下:
//Consequence 02 请问是否要录入图书信息(Y/N):Y 请输入书名:人类简史 请输入作者:尤瓦尔·赫拉利 请输入售价:32.25 请输入出版日期:2016-3-4 请输入出版社:中信出版集团 请问是否要录入图书信息(Y/N):N 数据录入完毕,开始打印验证... 书名:人类简史 作者:尤瓦尔·赫拉利 售价:32.25 出版日期:2016-3-4 出版社:中信出版集团
单链表
我们知道,数组变量在内存中,是连续的,而且不可拓展。显然在一些情况下,这种数据结构拥有很大的局限性。比如移动数据的时候,会牵一发而动全身,尤其是反转这种操作更加令人窒息。那么,需要需要一种数据结构来弄出一种更加灵活的“数组”,那么这,就是「链表」。
本节我们只讲讲单链表。
所谓链表,就是由一个个「结点」组成的一个数据结构。每个结点都有「数据域」和「指针域」组成。其中数据域用来存储你想要存储的信息,而指针域用来存储下一个结点的地址。如图:
单链表
当然,链表最前面还有一个头指针,用来存储头结点的地址。
这样一来,链表中的每一个结点都可以不用挨个存放,因为有了指针把他们串起来。因此结点放在哪都无所谓,反正指针总是能够指向下一个元素。我们只需要知道头指针,就能够顺藤摸瓜地找到整个链表。
因此对于学籍数据库来说,我们只需要在Info结构体中加上一个指向自身类型的成员即可:
struct Info { unsigned long identifier; char name[20]; struct Date date; unsigned int years; struct Info* next; };
在单链表中插入元素
头插法
这种每次都将数据插入单链表的头部(头指针后面)的插入法就叫头插法。
如果要把学生信息加入到单链表,可以这么写:
void addInfo(struct Info** students)//students是头指针 { struct Info* info, *temp; info = (struct Info*)malloc(sizeof(struct Info)); if (info == NULL) { printf("内存分配失败! "); exit(1); } getInput(info); if (*students != NULL) { temp = *students; *students = info; info->next = temp; } else { *students = info; info->next = NULL; } }
❝
由于students存放的是头指针,因此我们需要传入它的地址传递给函数,才能够改变它本身的值。而students本身又是一个指向Info结构体的指针,所以参数的类型应该就是struct Info**。
❞
往单链表里面添加一个结点,也就是先申请一个结点,然后判断链表是否为空。如果为空,那么直接将头指针指向它,然后next成员指向NULL。若不为空,那么先将next指向头指针原本指向的结点,然后将头指针指向新结点即可。
那么,打印链表也变得很简单:
void printStu(struct Info* students) { struct Info* info; int count = 1; info = students; while (book != NULL) { printf("Student%d: ", count); printf("姓名:%s ", info->name); printf("学号:%d ", info->identifier); info = info->next; count++; } }
想要读取单链表里面的数据,只需要迭代单链表中的每一个结点,直到next成员为NULL,即表示单链表的结束。
最后,当然还是别忘了释放空间:
void releaseStu(struct Info** students) { struct Info* temp; while (*students != NULL) { temp = *students; *students = (*students)->next; free(temp); } }
尾插法
与头插法类似,尾插法就是把每一个数据都插入到链表的末尾。
void addInfo(struct Info** students) { struct Info* info, *temp; info = (struct Info*)malloc(sizeof(struct Info)); if (info == NULL) { printf("内存分配失败! "); exit(1); } getInput(info); if (*students != NULL) { temp = *students; *students = info; //定位到链表的末尾的位置 while (temp->next != NULL) { temp = temp->next; } //插入数据 temp->next = info; info->next = temp; } else { *students = info; info->next = NULL; } }
这么一来,程序执行的效率难免要降低很多,因为每次插入数据,都要先遍历一次链表。如果链表很长,那么对于插入数据来说就是一次灾难。不过,我们可以给程序添加一个指针,让它永远都指向链表的尾部,这样一来,就可以用很少的空间换取很高的程序执行效率。
代码更改如下:
void addInfo(struct Info** students) { struct Info* info, *temp; static struct Info* tail;//设置静态指针 info = (struct Info*)malloc(sizeof(struct Info)); if (info == NULL) { printf("内存分配失败! "); exit(1); } getInput(info); if (*students != NULL) { tail->next = info; info->next = NULL; } else { *students = info; info->next = NULL; } }
搜索单链表
单链表是我们用来存储数据的一个容器,那么有时候需要快速查找信息就需要开发相关搜索的功能。比如说输入学号,查找同学的所有信息。
struct Info *searchInfo(struct Info* students, long* target) { struct Info* info; info = students; while (info != NULL) { if (info->identifier == target) { break; } info = info->next; } return book; }; void printInfo(struct Info* info) { ... } ... int main(void) { ... printf(" 请输入学生学号:"); scanf("%d", input); info = searchInfo(students, input); if (info == NULL) { printf("抱歉,未找到相关结果! "); } else { do { printf("相关结果如下: "); printInfo(book); } while ((info = searchInfo(info->next, input)) != NULL); } releaseInfo(...); return 0; }
插入结点到指定位置
到了这里,才体现出链表真正的优势。
设想一下,如果有一个有序数组,现在要求你去插入一个数字,插入完成之后,数组依然保持有序。你会怎么做?
没错,你应该会挨个去比较,然后找到合适的位置(当然这里也可以使用二分法,比较节省算力),把这个位置后面的所有数都往后移动一个位置,然后将我们要插入的数字放入刚刚我们腾出来的空间里面。
你会发现,这样的处理方法,经常需要移动大量的数据,对于程序的执行效率来说,是一个不利因素。那么链表,就无所谓。反正在内存中,链表的存储毫无逻辑,我们只需要改变指针的值就可以实现链表的中间插入。
//Example 03 #include #include struct Node { int value; struct Node* next; }; void insNode(struct Node** head, int value) { struct Node* pre; struct Node* cur; struct Node* New; cur = *head; pre = NULL; while (cur != NULL && cur->value < value) { pre = cur; cur = cur->next; } New = (struct Node*)malloc(sizeof(struct Node)); if (New == NULL) { printf("内存分配失败! "); exit(1); } New->value = value; New->next = cur; if (pre == NULL) { *head = New; } else { pre->next = New; } } void printNode(struct Node* head) { struct Node* cur; cur = head; while (cur != NULL) { printf("%d ", cur->value); cur = cur->next; } putchar(' '); } int main(void) { struct Node* head = NULL; int input; printf("开始插入整数... "); while (1) { printf("请输入一个整数,输入-1表示结束:"); scanf("%d", &input); if (input == -1) { break; } insNode(&head, input); printNode(head); } return 0; }
运行结果如下:
//Consequence 03 开始插入整数... 请输入一个整数,输入-1表示结束:4 4 请输入一个整数,输入-1表示结束:5 4 5 请输入一个整数,输入-1表示结束:3 3 4 5 请输入一个整数,输入-1表示结束:6 3 4 5 6 请输入一个整数,输入-1表示结束:2 2 3 4 5 6 请输入一个整数,输入-1表示结束:5 2 3 4 5 5 6 请输入一个整数,输入-1表示结束:1 1 2 3 4 5 5 6 请输入一个整数,输入-1表示结束:7 1 2 3 4 5 5 6 7 请输入一个整数,输入-1表示结束:-1
删除结点
删除结点的思路也差不多,首先修改待删除的结点的上一个结点的指针,将其指向待删除结点的下一个结点。然后释放待删除结点的空间。
... void delNode(struct Node** head, int value) { struct Node* pre; struct Node* cur; cur = *head; pre = NULL; while (cur != NULL && cur->value != value) { pre = cur; cur = cur->next; } if (cur == NULL) { printf("未找到匹配项! "); return ; } else { if (pre == NULL) { *head = cur->next; } else { pre->next = cur->next; } free(cur); } }
内存池
C语言的内存管理,从来都是一个让人头秃的问题。要想更自由地管理内存,就必须去堆中申请,然后还需要考虑何时释放,万一释放不当,或者没有及时释放,造成的后果都是难以估量的。
当然如果就这些,那倒也还不算什么。问题就在于,如果大量地使用malloc和free函数来申请内存,首先使要经历一个从应用层切入系统内核层,调用完成之后,再返回应用层的一系列步骤,实际上使非常浪费时间的。更重要的是,还会产生大量的内存碎片。比如,先申请了一个1KB的空间,紧接着又申请了一个8KB的空间。而后,这个1KB使用完了,被释放,但是这个空间却只有等到下一次有刚好1KB的空间申请,才能够被重新调用。这么一来,极限情况下,整个堆有可能被弄得支离破碎,最终导致大量内存浪费。
那么这种情况下,我们解决这类问题的思路,就是创建一个内存池。
内存池,实际上就是我们让程序创建出来的一块额外的缓存区域,如果有需要释放内存,先不必使用free函数,如果内存池有空,那么直接放入内存池。同样的道理,下一次程序申请空间的时候,先检查下内存池里面有没有合适的内存,如果有,则直接拿出来调用,如果没有,那么再使用malloc。
其实内存池我们就可以使用单链表来进行维护,下面通过一个通讯录的程序来说明内存池的运用。
普通的版本:
//Example 04 V1 #include #include #include struct Person { char name[40]; char phone[20]; struct Person* next; }; void getInput(struct Person* person); void printPerson(struct Person* person); void addPerson(struct Person** contects); void changePerson(struct Person* contacts); void delPerson(struct Person** contacts); struct Person* findPerson(struct Person* contacts); void displayContacts(struct Person* contacts); void releaseContacts(struct Person** contacts); void getInput(struct Person* person) { printf("请输入姓名:"); scanf("%s", person->name); printf("请输入电话:"); scanf("%s", person->phone); } void addPerson(struct Person** contacts) { struct Person* person; struct Person* temp; person = (struct Person*)malloc(sizeof(struct Person)); if (person == NULL) { printf("内存分配失败! "); exit(1); } getInput(person); //将person添加到通讯录中 if (*contacts != NULL) { temp = *contacts; *contacts = person; person->next = temp; } else { *contacts = person; person->next = NULL; } } void printPerson(struct Person* person) { printf("联系人:%s ", person->name); printf("电话:%s ", person->phone); } struct Person* findPerson(struct Person* contacts) { struct Person* current; char input[40]; printf("请输入联系人:"); scanf("%s", input); current = contacts; while (current != NULL && strcmp(current->name, input)) { current = current->next; } return current; } void changePerson(struct Person* contacts) { struct Person* person; person = findPerson(contacts); if (person == NULL) { printf("找不到联系人! "); } else { printf("请输入联系电话:"); scanf("%s", person->phone); } } void delPerson(struct Person** contacts) { struct Person* person; struct Person* current; struct Person* previous; //先找到待删除的节点的指针 person = findPerson(*contacts); if (person == NULL) { printf("找不到该联系人! "); } else { current = *contacts; previous = NULL; //将current定位到待删除的节点 while (current != NULL && current != person) { previous = current; current = current->next; } if (previous == NULL) { //若待删除的是第一个节点 *contacts = current->next; } else { //若待删除的不是第一个节点 previous->next = current->next; } free(person);//将内存空间释放 } } void displayContacts(struct Person* contacts) { struct Person* current; current = contacts; while (current != NULL) { printPerson(current); current = current->next; } } void releaseContacts(struct Person** contacts) { struct Person* temp; while (*contacts != NULL) { temp = *contacts; *contacts = (*contacts)->next; free(temp); } } int main(void) { int code; struct Person* contacts = NULL; struct Person* person; printf("| 欢迎使用通讯录管理程序 | "); printf("|--- 1:插入新的联系人 ---| "); printf("|--- 2:查找现有联系人 ---| "); printf("|--- 3:更改现有联系人 ---| "); printf("|--- 4:删除现有联系人 ---| "); printf("|--- 5:显示当前通讯录 ---| "); printf("|--- 6:退出通讯录程序 ---| "); while (1) { printf(" 请输入指令代码:"); scanf("%d", &code); switch (code) { case 1:addPerson(&contacts); break; case 2:person = findPerson(contacts); if (person == NULL) { printf("找不到该联系人! "); } else { printPerson(person); } break; case 3:changePerson(contacts); break; case 4:delPerson(&contacts); break; case 5:displayContacts(contacts); break; case 6:goto END; } } END://此处直接跳出恒循环 releaseContacts(&contacts); return 0; }
运行结果如下:
//Consequence 04 V1 | 欢迎使用通讯录管理程序 | |--- 1:插入新的联系人 ---| |--- 2:查找现有联系人 ---| |--- 3:更改现有联系人 ---| |--- 4:删除现有联系人 ---| |--- 5:显示当前通讯录 ---| |--- 6:退出通讯录程序 ---| 请输入指令代码:1 请输入姓名:HarrisWilde 请输入电话:0101111 请输入指令代码:1 请输入姓名:Jack 请输入电话:0101112 请输入指令代码:1 请输入姓名:Rose 请输入电话:0101113 请输入指令代码:2 请输入联系人:HarrisWilde 联系人:HarrisWilde 电话:0101111 请输入指令代码:2 请输入联系人:Mike 找不到该联系人! 请输入指令代码:5 联系人:Rose 电话:0101113 联系人:Jack 电话:0101112 联系人:HarrisWilde 电话:0101111 请输入指令代码:3 请输入联系人:HarrisWilde 请输入联系电话:0101234 请输入指令代码:5 联系人:Rose 电话:0101113 联系人:Jack 电话:0101112 联系人:HarrisWilde 电话:0101234 请输入指令代码:6
下面加入内存池:
//Example 04 V2 #include #include #include #define MAX 1024 struct Person { char name[40]; char phone[20]; struct Person* next; }; struct Person* pool = NULL; int count; void getInput(struct Person* person); void printPerson(struct Person* person); void addPerson(struct Person** contects); void changePerson(struct Person* contacts); void delPerson(struct Person** contacts); struct Person* findPerson(struct Person* contacts); void displayContacts(struct Person* contacts); void releaseContacts(struct Person** contacts); void releasePool(void); void getInput(struct Person* person) { printf("请输入姓名:"); scanf("%s", person->name); printf("请输入电话:"); scanf("%s", person->phone); } void addPerson(struct Person** contacts) { struct Person* person; struct Person* temp; //如果内存池不是空的,那么首先从里面获取空间 if (pool != NULL) { person = pool; pool = pool->next; count--; } //内存池为空,则直接申请 else { person = (struct Person*)malloc(sizeof(struct Person)); if (person == NULL) { printf("内存分配失败! "); exit(1); } } getInput(person); //将person添加到通讯录中 if (*contacts != NULL) { temp = *contacts; *contacts = person; person->next = temp; } else { *contacts = person; person->next = NULL; } } void printPerson(struct Person* person) { printf("联系人:%s ", person->name); printf("电话:%s ", person->phone); } struct Person* findPerson(struct Person* contacts) { struct Person* current; char input[40]; printf("请输入联系人:"); scanf("%s", input); current = contacts; while (current != NULL && strcmp(current->name, input)) { current = current->next; } return current; } void changePerson(struct Person* contacts) { struct Person* person; person = findPerson(contacts); if (person == NULL) { printf("找不到联系人! "); } else { printf("请输入联系电话:"); scanf("%s", person->phone); } } void delPerson(struct Person** contacts) { struct Person* person; struct Person* current; struct Person* previous; struct Person* temp; { }; //先找到待删除的节点的指针 person = findPerson(*contacts); if (person == NULL) { printf("找不到该联系人! "); } else { current = *contacts; previous = NULL; //将current定位到待删除的节点 while (current != NULL && current != person) { previous = current; current = current->next; } if (previous == NULL) { //若待删除的是第一个节点 *contacts = current->next; } else { //若待删除的不是第一个节点 previous->next = current->next; } //判断内存池中有没有空位 if (count < MAX) { //使用头插法将person指向的空间插入内存池中 if (pool != NULL) { temp = pool; pool = person; person->next = temp; } else { pool = person; person->next = NULL; } count++; } //没有空位,直接释放 else { free(person);//将内存空间释放 } } } void displayContacts(struct Person* contacts) { struct Person* current; current = contacts; while (current != NULL) { printPerson(current); current = current->next; } } void releaseContacts(struct Person** contacts) { struct Person* temp; while (*contacts != NULL) { temp = *contacts; *contacts = (*contacts)->next; free(temp); } } void releasePool(void) { struct Person* temp; while (pool != NULL) { temp = pool; pool = pool->next; free(temp); } } int main(void) { int code; struct Person* contacts = NULL; struct Person* person; printf("| 欢迎使用通讯录管理程序 | "); printf("|--- 1:插入新的联系人 ---| "); printf("|--- 2:查找现有联系人 ---| "); printf("|--- 3:更改现有联系人 ---| "); printf("|--- 4:删除现有联系人 ---| "); printf("|--- 5:显示当前通讯录 ---| "); printf("|--- 6:退出通讯录程序 ---| "); while (1) { printf(" 请输入指令代码:"); scanf("%d", &code); switch (code) { case 1:addPerson(&contacts); break; case 2:person = findPerson(contacts); if (person == NULL) { printf("找不到该联系人! "); } else { printPerson(person); } break; case 3:changePerson(contacts); break; case 4:delPerson(&contacts); break; case 5:displayContacts(contacts); break; case 6:goto END; } } END://此处直接跳出恒循环 releaseContacts(&contacts); releasePool(); return 0; }
typedef
给数据类型起别名
C语言是一门古老的语言,它是在1969至1973年间,由两位天才丹尼斯·里奇和肯·汤普逊在贝尔实验室以B语言为基础开发出来的,用于他们的重写UNIX计划(这也为后来UNIX系统的可移植性打下了基础,之前的UNIX是使用汇编语言编写的,当然也是这两位为了玩一个自己设计的游戏而编写的)。天才就是和咱常人不一样,不过他俩的故事,在这篇里面不多啰嗦,我们回到话题。
虽然C语言诞生的很早,但是却依旧不是最早的高级编程语言。目前公认的最早的高级编程语言,是IBM公司于1957年开发的FORTRAN语言。C语言诞生之时,FORTRAN已经统领行业数十年之久。因此,C语言要想快速吸纳FORTRAN中的潜在用户,就必须做出一些妥协。
我们知道,不同的语言的语法,一般来说是不同的,甚至还有较大的差距。比如:
C:
int a, b, c; float i, j, k;
而FORTRAN语言是这样的:
integer :: a, b, c; real :: i, j, k;
如果让FORTRAN用户使用原来的变量名称进行使用,那么就能够快速迁移到C语言上面来,这就是typedef的用处之一。
我们使用FORTRAN语言的类型名,那就这么办:
typedef int integer; typedef float real; integer a, b, c; real i, j, k;
结构体的搭档
虽然结构体的出现能够让我们有一个更科学的数据结构来管理数据,但是每次使用结构体都需要struct...,未免显得有些冗长和麻烦。有了typedef的助攻,我们就可以很轻松地给结构体类型起一个容易理解的名字:
typedef struct date { int year; int month; int day; } DATE;//为了区分,一般用全大写 int main(void) { DATE* date; ... }
甚至还可以顺便给它的指针也定义一个别名:
typedef struct date { int year; int month; int day; } DATE, *PDATE;
进阶
我们还可以利用typedef来简化一些比较复杂的命令。
比如:
int (*ptr) [5];
我们知道这是一个数组指针,指向一个5元素的数组。那么我们可以改写成这样:
typedef int(*PTR_TO_ARRAY)[3];
这样就可以把很复杂的声明变得很简单:
PTR_TO_ARRAY a = &array;
取名的时候要尽量使用容易理解的名字,这样才能达到使用typedef的最终目的。
共用体
共用体也称联合体。
声明
和结构体还是有点像:
union 共用体名称 { 成员1; 成员2; 成员3; };
但是两者有本质的不同。共用体的每一个成员共用一段内存,那么这也就意味着它们不可能同时被正确地访问。如:
//Example 05 #include #include union Test { int i; double pi; char str[9]; }; int main(void) { union Test test; test.i = 10; test.pi = 3.14; strcpy(test.str, "TechZone"); printf("test.i: %d ", test.i); printf("test.pi: %.2f ", test.pi); printf("test.str: %s ", test.str); return 0; }
执行结果如下:
//Consequence 05 test.i: 1751344468 test.pi: 3946574856045802736197446431383475413237648487838717723111623714247921409395495328582015991082102150186282825269379326297769425957893182570875995348588904500564659454087397032067072.00 test.str: TechZone
可以看到,共用体只能正确地展示出最后一次被赋值的成员。共用体的内存应该要能够满足最大的成员能够正常存储。但是并不一定等于最大的成员的尺寸,因为还要考虑内存对齐的问题。
共用体可以类似结构体一样来定义和声明,但是共用体还可以允许不带名字:
union { int i; char ch; float f; } a, b;
初始化
共用体不能在同一时间存放多个成员,所以不能批量初始化
union data { int i; char ch; float f; }; union data a = {520}; //初始化第一个成员 union data b = a; //直接使用一个共用体初始化另一个共用体 union data c = {.ch = 'C'}; //C99的特性,指定初始化成员
枚举
枚举是一个基本的数据类型,它可以让数据更简洁。
如果写一个判断星期的文章,我们当然可以使用宏定义来使代码更加易懂,不过:
#define MON 1 #define TUE 2 #define WED 3 #define THU 4 #define FRI 5 #define SAT 6 #define SUN 7
这样的写法有点费键盘。那么枚举就简单多了:
enum DAY { MON=1, TUE, WED, THU, FRI, SAT, SUN };
❝
**注意:**第一个枚举成员的默认值为整型的 0,后续枚举成员的值在前一个成员上加 1。我们在这个实例中把第一个枚举成员的值定义为 1,第二个就为 2,以此类推。
❞
枚举变量的定义和声明方法和共用体一样,也可以省略枚举名,直接声明变量名。
//Example 06 #include #include int main() { enum color { red = 1, green, blue }; enum color favorite_color; printf("请输入你喜欢的颜色: (1. red, 2. green, 3. blue): "); scanf("%d", &favorite_color); //输出结果 switch (favorite_color) { case red: printf("你喜欢的颜色是红色"); break; case green: printf("你喜欢的颜色是绿色"); break; case blue: printf("你喜欢的颜色是蓝色"); break; default: printf("你没有选择你喜欢的颜色"); } return 0; }
执行结果如下:
//Consequence 06 请输入你喜欢的颜色: (1. red, 2. green, 3. blue): 3 你喜欢的颜色是蓝色
也可以把整数转换为枚举类型:
//Example 07 #include #include int main() { enum day { saturday, sunday, monday, tuesday, wednesday, thursday, friday } workday; int a = 1; enum day weekend; weekend = (enum day) a; //使用强制类型转换 //weekend = a; //错误 printf("weekend:%d", weekend); return 0; }
运行结果如下:
//Consequence 07 weekend:1
位域
C语言除了开发桌面应用等,还有一个很重要的领域,那就是「单片机」开发。单片机上的硬件资源十分有限,容不得我们去肆意挥洒。单片机使一种集成威廉希尔官方网站
芯片,使采用超大规模集成威廉希尔官方网站
技术把具有数据处理能力的CPU、RAM、ROM、I/O、中断系统、定时器/计数器等功能(有的还包括显示驱动威廉希尔官方网站
、脉宽调制威廉希尔官方网站
、模拟多路转换器、A/D转换器等威廉希尔官方网站
)集成到一块硅片上构成的一个小而完善的微型计算机系统,在工控领域使用广泛。
对于这样的设备,通常内存只有256B,那么能够给我们利用的资源就十分珍贵了。在这种情况下,如果我们只需要定义一个变量来存放布尔值,一般就申请一个整型变量,通过1和0来间接存储。但是,显然1和0只用1个bit就能够放完,而一个整型却是4个字节,也就是32bit。这就造成了内存的浪费。
好在,C语言为我们提供了一种数据结构,称为「位域」(也叫位端、位字段)。也就是把一个字节中的二进制位划分,并且你能够指定每个区域的位数。每个域有一个域名,并允许程序中按域名进行单独操作。
使用位域的做法是在结构体定义的时候,在结构体成员后面使用冒号(:)和数字来表示该成员所占的位数。
//Example 08 #include int main(void) { struct Test { unsigned int a : 1; unsigned int b : 1; unsigned int c : 2; } test; test.a = 0; test.b = 1; test.c = 2; printf("a = %d, b = %d, c = %d ", test.a, test.b, test.c); printf("size of test = %d ", sizeof(test)); return 0; }
运行结果如下:
//Consequence 08 a = 0, b = 1, c = 2 size of test = 4
如此一来,结构体test只用了4bit,却存放下了0、1、2三个整数。但是由于2在二进制中是10,因此占了2个bit。如果把test.b赋值为2,那么:
//Consequence 08 V2 a = 0, b = 0, c = 2 size of test = 4
可以看到,b中的10溢出了,只剩下0。
当然,位域的宽度不能够超过本身类型的长度,比如:
unsigned int a : 100;
那么就会报错:
错误C2034“main::a”: 位域类型对位数太小
位域成员也可以没有名称,只要给出类型和宽度即可:
struct Test { unsigned int x : 1; unsigned int y : 2; unsigned int z : 3; unsigned int : 26; };
无名位域一般用来作为填充或者调整成员的位置,因为没有名称,所以无名位域并不能够拿来使用。
❝
C语言的标准只说明unsigned int和signed int支持位域,然后C99增加了_Bool类型也支持位域,其他数据类型理论上是不支持的。不过大多数编译器在具体实现时都进行了扩展,额外支持了signed char、unsigned char以及枚举类型,所以如果对char类型的结构体成员使用位域,基本上也没什么问题。但如果考虑到程序的可移植性,就需要谨慎对待了。另外,由于内存的基本单位是字节,而位域只是字节的一部分,所以并不能对位域进行取地址运算。
❞
虽然科技发展日新月异,但是秉承着节约成本这个放之四海而皆准的原则,还是要注意使用!毕竟5毛钱可能是小钱,但是乘以5000万呢?