C基础-12

都是给自己学习的啊 不对的 网友们忙请告诉我哦~~

一、C语言结构体

本次分享一篇关于结构体的入门、提高的笔记，文章比较长，前面部分是结构体基础，已经掌握的童鞋可以跳过，直接看看后半部分的提高实例。

    有的时候，我们所遇到的数据结构，不仅仅是一群数字或者是字符串那么简单。比如我们每一个人的学籍信息，学号是一个长整数，名字却是字符；甚至有更复杂的情况，这种问题在现实生活中并不少见。我们之前学过一种叫数组的数据结构，它可以允许我们把很多同类型的数据集中在一起处理。相对于之前，这已经是一次极大的进步。但是，新的问题，往往又会出现，这个时候，我们就得上更高端的装备——结构体。

    相比于数组，结构体有以下的更强大的优势：

• 批量存储数据

• 存储不同类型的数据

• 支持嵌套

结构体的声明与定义

声明

    结构体的声明使用struct关键字，如果我们想要把我们的学籍信息组织一下的话，可以这样表示：

struct Info
{unsigned long identifier;//学号，用无符号长整数表示char name[20];//名字，用字符数组表示unsigned int year;//入学年份，用无符号整数表示unsigned int years;//学制，用无符号整数表示
}

这样，我们就相当于描绘好了一个框架，以后要用的话直接定义一个这种类型的变量就好了。

定义

    我们刚刚申请了一个名叫Info的结构体类型，那么理论上我们可以像声明其他变量的操作一样，去声明我们的结构体操作，但是C语言中规定，声明结构体变量的时候，struct关键字是不可少的。

    struct 结构体类型名 结构体变量名

    不过，你可以在某个函数里面定义：

#include <stdio.h>struct Info
{unsigned long identifier;//学号，用无符号长整数表示char name[20];//名字，用字符数组表示unsigned int year;//入学年份，用无符号整数表示unsigned int years;//学制，用无符号整数表示
};int main(void)
{/***在main函数中声明结构体变量*结构体变量名叫info*struct关键字不能丢*/struct Info info;...
}

    也可以在声明的时候就把变量名定义下来（此时这个变量是全局变量）：

#include <stdio.h>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 <stdio.h>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("\n数据录入完毕\n\n");printf("学号：%d\n姓名：%s\n入学年份：%d\n学制：%d\n毕业时间：%d\n", \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，「字符型」成员初始化为‘\0’。

对齐

下面这个代码，大家来看看会发生什么：

//EXample 02 V1
#include <stdio.h>int main(void)
{struct A{char a;int b;char c;} a = {'a', 10, 'o'};printf("size of a = %d\n", sizeof(a));return 0;
}

    我们之前学过，char类型的变量占1字节，int类型的变量占4字节，那么这么一算，一个结构体A型的变量应该就是6字节了。别急，我们看运行结果：

//COnsequence 02 V1
size of a = 12

    怎么变成12了呢？标准更新了？老师教错了？都不是。我们把代码改一下：

//EXample 02 V2
#include <stdio.h>int main(void)
{struct A{char a;char c;int b;} a = {'a', 'o', 10};printf("size of a = %d\n", 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 <stdio.h>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 <stdio.h>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("\n数据录入完毕\n\n");printf("学号：%d\n姓名：%s\n入学时间：%d/%d/%d\n学制：%d\n毕业时间：%d\n",\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;

    通过结构体指针来访问结构体有以下两种方法：

1. (*结构体指针).成员名

2. 结构体指针->成员名

    第一个方法由于点号运算符比指针的取值运算符优先级更高，因此需要加一个小括号来确定优先级，让指针先解引用变成结构体变量，在使用点号的方法去访问。

    相比之下，第二种方法就直观许多。

    这两种方法在实现上是完全等价的，但是点号只能用于结构体变量，而箭头只能够用于指针。

    第一种方法：

#include <stdio.h>
...
int main(void)
{struct Info *p;p = &info;printf("学号：\n", (*p).identifier);printf("姓名：\n", (*p).name);printf("入学时间：%d/%d/%d\n", (*p).date.year, (*p).date.month, (*p).date.day);printf("学制：\n", (*p).years);return 0;
}

    第二种方法：

#include <stdio.h>
...
int main(void)
{struct Info *p;p = &info;printf("学号：\n", p -> identifier);printf("姓名：\n", p -> name);printf("入学时间：%d/%d/%d\n", p -> date.year, p -> date.month, p -> date.day);printf("学制：\n", p -> years);return 0;
}

传递结构体信息

传递结构体变量

    我们先来看看下面的代码：

    运行结果如下：

//Consequence 04
t2.x = 3, t2.y = 4

    这么看来，结构体是可以直接赋值的。那么既然这样，作为函数的参数和返回值也自然是没问题的了。

    先来试试作为参数:

//Example 05
#include <stdio.h>
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\n姓名：%s\n入学时间：%d/%d/%d\n学制：%d\n毕业时间：%d\n", \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("请录入第一个同学的信息...\n");i1 = getInput(i1);putchar('\n');printf("请录入第二个学生的信息...\n");i2 = getInput(i2);printf("\n录入完毕，现在开始打印...\n\n");printf("打印第一个学生的信息...\n");printInfo(i1);putchar('\n');printf("打印第二个学生的信息...\n");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 <stdio.h>
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\n姓名：%s\n入学时间：%d/%d/%d\n学制：%d\n毕业时间：%d\n", \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("请录入第一个同学的信息...\n");getInput(&i1);putchar('\n');printf("请录入第二个学生的信息...\n");getInput(&i2);printf("\n录入完毕，现在开始打印...\n\n");printf("打印第一个学生的信息...\n");printInfo(&i1);putchar('\n');printf("打印第二个学生的信息...\n");printInfo(&i2);return 0;
}

    此时传递的就是一个指针，而不是一个庞大的结构体。

动态申请结构体

    结构体也可以在堆里面动态申请：

//Example 01
#include <stdio.h>
...
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("内存分配失败！\n");exit(1);}printf("请录入第一个同学的信息...\n");getInput(i1);putchar('\n');printf("请录入第二个学生的信息...\n");getInput(i2);printf("\n录入完毕，现在开始打印...\n\n");printf("打印第一个学生的信息...\n");printInfo(i1);putchar('\n');printf("打印第二个学生的信息...\n");printInfo(i2);free(i1);free(i2);return 0;
}

实战：建立一个图书馆数据库

    实际上，我们建立的数组可以是指向结构体指针的数组。

    代码实现如下：

//Example 02
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100struct 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\n", book->title);printf("作者：%s\n", book->author);printf("售价：%.2f\n", book->price);printf("出版日期：%d-%d-%d\n", book->date.year, book->date.month, book->date.day);printf("出版社：%s\n", 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('\n');}}
}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('\n');}else{printf("数据库已满！\n");break;}}else{break;}}printf("\n数据录入完毕，开始打印验证...\n\n");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("内存分配失败！\n");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:\n", count);printf("姓名：%s\n", info->name);printf("学号：%d\n", 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("内存分配失败！\n");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("内存分配失败！\n");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("\n请输入学生学号：");scanf("%d", input);info = searchInfo(students, input);if (info == NULL){printf("抱歉，未找到相关结果！\n");}else{do{printf("相关结果如下：\n");printInfo(book);} while ((info = searchInfo(info->next, input)) != NULL);}releaseInfo(...);return 0;
}

插入结点到指定位置

    到了这里，才体现出链表真正的优势。

    设想一下，如果有一个有序数组，现在要求你去插入一个数字，插入完成之后，数组依然保持有序。你会怎么做？

    没错，你应该会挨个去比较，然后找到合适的位置（当然这里也可以使用二分法，比较节省算力），把这个位置后面的所有数都往后移动一个位置，然后将我们要插入的数字放入刚刚我们腾出来的空间里面。

    你会发现，这样的处理方法，经常需要移动大量的数据，对于程序的执行效率来说，是一个不利因素。那么链表，就无所谓。反正在内存中，链表的存储毫无逻辑，我们只需要改变指针的值就可以实现链表的中间插入。​​​​​​​

//Example 03
#include <stdio.h>
#include <stdlib.h>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("内存分配失败！\n");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('\n');
}int main(void)
{struct Node* head = NULL;int input;printf("开始插入整数...\n");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("未找到匹配项!\n");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 <stdio.h>
#include <stdlib.h>
#include <string.h>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("内存分配失败！\n");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\n", person->name);printf("电话：%s\n", 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("找不到联系人！\n");}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("找不到该联系人！\n");}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("| 欢迎使用通讯录管理程序 |\n");printf("|--- 1:插入新的联系人 ---|\n");printf("|--- 2:查找现有联系人 ---|\n");printf("|--- 3:更改现有联系人 ---|\n");printf("|--- 4:删除现有联系人 ---|\n");printf("|--- 5:显示当前通讯录 ---|\n");printf("|--- 6:退出通讯录程序 ---|\n");while (1){printf("\n请输入指令代码：");scanf("%d", &code);switch (code){case 1:addPerson(&contacts); break;case 2:person = findPerson(contacts);if (person == NULL){printf("找不到该联系人！\n");}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 <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX 1024struct 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("内存分配失败！\n");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\n", person->name);printf("电话：%s\n", 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("找不到联系人！\n");}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("找不到该联系人！\n");}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("| 欢迎使用通讯录管理程序 |\n");printf("|--- 1:插入新的联系人 ---|\n");printf("|--- 2:查找现有联系人 ---|\n");printf("|--- 3:更改现有联系人 ---|\n");printf("|--- 4:删除现有联系人 ---|\n");printf("|--- 5:显示当前通讯录 ---|\n");printf("|--- 6:退出通讯录程序 ---|\n");while (1){printf("\n请输入指令代码：");scanf("%d", &code);switch (code){case 1:addPerson(&contacts); break;case 2:person = findPerson(contacts);if (person == NULL){printf("找不到该联系人！\n");}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 <stdio.h>
#include <string.h>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\n", test.i);printf("test.pi: %.2f\n", test.pi);printf("test.str: %s\n", 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 <stdio.h>
#include <stdlib.h>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 <stdio.h>
#include <stdlib.h>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 <stdio.h>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\n", test.a, test.b, test.c);printf("size of test = %d\n", 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::test::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类型的结构体成员使用位域，基本上也没什么问题。但如果考虑到程序的可移植性，就需要谨慎对待了。另外，由于内存的基本单位是字节，而位域只是字节的一部分，所以并不能对位域进行取地址运算。

 whaosoft aiot http://143ai.com
 

二、使用回调函数模拟委托与反射

  函数是C语言的核心概念。主调函数（caller）调用被调函数（callee）是一般的调用关系，如果被调函数（callee）参数包含函数指针，函数指针还可以形成多一层的调用关系，形成第三方函数的调用，专业术语称为回调（callback），通过函数指针参数调用的第三方函数称为回调函数。

    回调可以让被调函数（这里是指用函数指针做函数参数的函数）的代码更加泛化或抽象，能够简单模拟其它编程语言的委托与反射语法。

1、简单模拟委托

//C语言简单模拟委托
//需要用的指针函数。通过用指针函数作为地址接收函数地址，以达到委托其他函数实现某方法的目的。
#include <stdio.h>
typedef void(* fun)();  //typedef 把void(*)()类型重命名为fun
void func(fun);  // 被调函数
void func_1();  // 回调函数1
void func_2();  // 回调函数2int main() // 主函数用做主调函数
{func(func_1);fun f = func_2;f();func(func_1);func(func_2);getchar();return 0;
}
void func(fun f)  //fun f为地址，fun * f为f指向的地址的量或者其他
{printf("func\n");if (f != NULL){f();}
}
void func_1()
{printf("func_1\n");
}
void func_2()
{printf("func_2\n");
}
/*
func
func_1
func_2
func
func_1
func
func_2
*/

2、简单模拟反射

（1）简单模拟反射

    高级语言的反射机制，简单来说就是可以通过字符串型获取对应的类或者函数。

    下面用C来简单模拟反射：

#include <stdio.h>
#include <string.h>typedef void (*callback)(void);typedef struct {const char *name;callback fn;
}callback_t;void f0();
void f1();callback_t callbacks[] = {{"cmd0", f0},{"cmd1", f1},
};void f0()   // 回调函数0
{printf("cmd0");
}void f1()  // 回调函数1
{printf("cmd1");
}void do_callback(const char *name)  
{size_t i;for (i = 0; i < sizeof(callbacks) / sizeof(callbacks[0]); i++) {if (!strcmp(callbacks[i].name, name)) {callbacks[i].fn();}}
}int main()
{do_callback("cmd1");getchar();return 0;
}

（2）利用自定义段

    gcc支持通过使用 __ attribute __ ((section()))，将函数、变量放到指定的数据段中。

    也就是说，可以让编译器帮我们完成上例中向数组添加成员的动作。借助此机制，回调函数可以在任意文件声明，不需要修改其他文件。自定义段的起始和结束地址，可以通过变量 __ start_SECTIONNAME 和 __ stop_SECTIONNAME得到例如通过 __ attribute __ ((section("ss"))定义自定义段，其开始地址为 & __ start_ss，结束地址为 & __stop_ss。

// https://www.bejson.com/runcode/c920/
#include <stdio.h>
#define SEC __attribute__((__section__("ss"), aligned(sizeof(void*))))void func_1 (int a, int b)
{printf("%s %d %d\n", __func__, __LINE__, a+b); 
}
void func_2 (int a, int b)
{printf("%s %d %d\n", __func__, __LINE__, a*b); 
}// 编译器会自动提供__start_ss，__stop_ss标志段ss的起止地址
extern size_t __start_ss;
extern size_t __stop_ss;typedef struct {void (*p)(int, int);
} node_t;// 结构体变量a位于自定义段ss
SEC node_t a = { .p = func_1, 
};
SEC node_t b = { .p = func_2, 
};
int main(int argc, char **argv)
{int a = 3, b = 4;node_t *p;// 遍历段ss，执行node_t结构中的p指向的函数for (p = (node_t *)&__start_ss; p < (node_t *)&__stop_ss;p++) {p->p(a, b);a+=1;b+=2;}
}
/*
func_1 6 7
func_2 10 24*/

三、C＋＋程序的编辑、编译和运行C++的特点

    C++继承了C的优点，并有自己的特点，主要有：

1、全面兼容C，C的许多代码不经修改就可以为Cpp所用，用C编写的库函数和实用软件可以用于Cpp。

2、用C++编写的程序可读性更好，代码结构更为合理，可直接在程序中映射问题空间结构。

3、生成代码的质量高，运行效率高。

4、从开发时间、费用到形成软件的可重用性、可扩充性、可维护性和可靠性等方面有了很大提高，使得大中型的程序开发项目变得容易得多。

5、支持面向对象的机制，可方便的构造出模拟现实问题的实体和操作。

C++的程序特征

    例1.1 输出一行字符：“This is a C++ program.”。

    程序如下：​​​​​​​

#include <iostream> //包含头文件iostreamusing namespace std; //使用命名空间stdint main( ){    cout<<″This is a C++ program.″;    return 0;}

    在运行时会在屏幕上输出以下一行信息：

This is a C++ program.

• 用main代表“主函数”的名字。每一个C++程序都必须有一个 main 函数。main前面的int的作用是声明函数的类型为整型。程序第6行的作用是向操作系统返回一个零值。如果程序不能正常执行，则会自动向操作系统返回一个非零值，一般为-1。

• 函数体是由大括号{}括起来的。本例中主函数内只有一个以cout开头的语句。注意C++所有语句最后都应当有一个分号。

• 再看程序的第1行“#include

• ”，这不是Cpp的语句，而是Cpp的一个预处理命令，它以“#”开头以与Cpp语句相区别，行的末尾没有分号。

• #include <iostream>是一个“包含命令”，它的作用是将文件iostream的内容包含到该命令所在的程序文件中，代替该命令行。文件iostream的作用是向程序提供输入或输出时所需要的一些信息。

• iostream是i-o-stream3个词的组合，从它的形式就可以知道它代表“输入输出流”的意思，由于这类文件都放在程序单元的开头，所以称为“头文件” (head file)。在程序进行编译时，先对所有的预处理命令进行处理，将头文件的具体内容代替#include命令行，然后再对该程序单元进行整体编译。

• 程序的第2行“using namespace std;”的意思是“使用命名空间std”。Cpp标准库中的类和函数是在命名空间std中声明的，因此程序中如果需要用到Cpp标准库(此时就需要用#include命令行)，就需要用“using namespace std;”作声明，表示要用到命名空间std中的内容。

• 在初学C++时，对本程序中的第1,2行可以不必深究，只需知道：如果程序有输入或输出时，必须使用“#include

• ”命令以提供必要的信息，同时要用“using namespace std;”，使程序能够使用这些信息，否则程序编译时将出错。

    例1.2 求a和b两个数之和:​​​​​​​

// 求两数之和 (本行是注释行)#include <iostream> //预处理命令using namespace std; //使用命名空间stdint main( ) //主函数首部{ //函数体开始    int a,b,sum; //定义变量    cin>>a>>b; //输入语句    sum=a+b; //赋值语句    cout<<″a+b=″<<sum<<endl; //输出语句    return 0; //如程序正常结束，向操作系统返回一个零值} //函数结束

    本程序的作用是求两个整数a和b之和sum。

    第1行“//求两数之和”是一个注释行，Cpp规定在一行中如果出现“//” ，则从它开始到本行末尾之间的全部内容都作为注释。

    例1.3 给两个数x和y， 求两数中的大者：

#include <iostream> //预处理命令using namespace std;int max(int x,int y) //定义max函数，函数值为整型，形式参数x， y为整型{ //max函数体开始    int z; //变量声明，定义本函数中用到的变量z为整型    if(x>y) z=x; //if语句，如果x>y， 则将x的值赋给z    else z=y; //否则，将y的值赋给z    return(z); //将z的值返回，通过max带回调用处} //max函数结束int main( ) //主函数{ //主函数体开始    int a,b,m; //变量声明    cin>>a>>b; //输入变量a和b的值    m=max(a,b); //调用max函数，将得到的值赋给m    cout<<″max=″<<m<<′\\n′; //输出大数m的值    return 0; //如程序正常结束，向操作系统返回一个零值} //主函数结束

    本程序包括两个函数:主函数main和被调用的函数max。

    程序运行情况如下:

• 18 25 ↙ (输入18和25给a和b)

• max=25 (输出m的值)

    注意输入的两个数据间用一个或多个空格间隔，不能以逗号或其他符号间隔。

    在上面的程序中，max函数出现在main函数之前，因此在main函数中调用max函数时，编译系统能识别max是已定义的函数名。如果把两个函数的位置对换一下，即先写main函数，后写max函数，这时在编译main函数遇到max时，编译系统无法知道max代表什么含义，因而无法编译，按出错处理。

    为了解决这个问题，在主函数中需要对被调用函数作声明。上面的程序可以改写如下：​​​​​​​

#include <iostream>using namespace std;int max(int x,int y); //对max函数作声明int main( ){    int a,b,c;    cin>>a>>b;    c=max(a,b); //调用max函数例1.3 给两个数x和y， 求两数中的大者。    cout<<″max=″<<c<<endl;    return 0;}int max(int x,int y) //定义max函数{    int z;    if(x>y) z=x;    else z=y;    return(z);}

    只要在被调用函数的首部的末尾加一个分号，就成为对该函数的函数声明。函数声明的位置应当在函数调用之前。

C++程序的结构特性

    一个面向对象的C++程序一般由类的声明和类的使用两大部分组成。

    类的使用部分一般由主函数及有关子函数组成

 典型的C++程序结构:​​​​​​​

#include <iostream.h>//类的声明部分class A{    int x,y,z;    ……    fun( ){……}    ……};//类的使用部分int main(){    A a;    ……    a.fun();    return 0;}

    在C++程序中，程序设计始终围绕“类”展开。通过声明类，构建了程序所要完成的功能，体现了面向对象程序设计的思想。

C＋＋程序的编辑、编译和运行

    C++源程序文件的扩展名为.CPP，可以用多种编译器编辑、编译和运行。

    C++对C的补充：

1、注释与续行

• 注释符：“/*”和“*/” 或“//” 。

    Cpp新增了注释语句，它由“//”开始，到行尾结束。

    例如：​​​​​​​

X = y + z; /*This is a comment */
X = y + z; //This is a comment

• 续行符：“\”（反斜杠）。作用是当一个语句太长时可以用该符号把它分段写在几行中。
  例：

cout << ‘\n’ << “x=” << x << “y=” << y << “z=” << z\ << “u=” << u << “v\=” << v << “w=” << w << endl;

2、输入输出流

    C中I/O操作出现的问题：​​​​​​​

int i;float f;scanf(“%f”,i);printf( “%d”,d);

    Cpp中使用更安全更方便的方法：

int i;float f;cin >> i;cout << f;

    cout和cin分别是C++的标准输出流和输入流。Cpp支持重定向，但一般cout指的是屏幕， cin指的是键盘。

    操作符“<<”和“>>”除了具有C语言中定义的左移和右移的功能外，在这里符号“<<”是把右方的参数写到标准输出流cout中；相反，符号“>>”则是将标准输入流的数据赋给右方的变量。

    例1.4 一个完整的C++程序：​​​​​​​

#include <iostream.h>int main(){    char name[20];    cout << "Hello， your name：";    cin >> name;    cout << name;    return 0;}

    注意：

• 程序中必须包含头文件iostream.h

• cin和>>,cout和<<配套使用

• cin可以输入多个数据,但要用空白符隔开（tab，空格，回车）   

    如：cin >> a >> b >> c;

• 换行符：‘\n’或endl

    如：cout << “x=” << x << endl; cout << “x=” << x << ‘\n’;

• 使用cout和cin时，也可以对输入和输出的格式进行控制，比如可用不同的进制方式显示数据，只要设置转换基数的操作符dec、hex和oct即可。

    例1.5 操作符dec、 hex和oct的使用:​​​​​​​

#include<iostream.h>void main(){    int x=25;    cout << hex << x << ' ' << dec << x << ' ' << oct << x << '\n';}

    输出结果为：19 25 31

3、灵活的变量说明

    定义变量的位置:

    在程序中的不同位置采用不同的变量定义方式，决定了该变量具有不同的特点。变量的定义一般可有以下三种位置：

(1) 在函数体内部

    在函数体内部定义的变量称为局部变量，这种局部变量只在进入定义它的函数体时起作用，离开该函数体后该变量就消失（被释放），即不再起作用。因此，不同函数体内部可以定义相同名称的变量，而互不干扰。

(2) 形式参数

    当定义一个有参函数时，函数名后面括号内的变量，统称为形式参数。

(3) 全局变量

    在所有函数体外部定义的变量，其作用范围是整个程序，并在整个程序运行期间有效。

• 在C语言中，全局变量声明必须在任何函数之前，局部变量必须集中在可执行语句之前。

• Cpp中的变量声明非常灵活，它允许变量声明与可执行语句在程序中交替出现。

    例如:

f( ){    int i;    i=10;    int j;    j=25;    // …}float fun(int x,int y){    for(int i=0;i<10;i++)    {        int sum=0;        sum=sum+i;        cout<<“sum=”<<sum;    }    int z=0;    z=x+y;}

4、结构、联合和枚举名

    在C++中，结构名、联合名、枚举名都是类型名。在定义变量时，不必在结构名、联合名或枚举名前冠以struct、union或enum。

    例如：​​​​​​​

enum boole{FALSE,TRUE};struct string{    char *string;    int length;};union number{    int i;    float f;};

    在传统的C中，定义变量时，必须写成：​​​​​​​

enum boole done;struct string str;union number x;

    但是，在C++中，可以说明为：​​​​​​​

boole done;string str;number x;

5、函数原型

    C语言建议编程者为程序中的每一个函数建立原型，而Cpp要求为每一个函数建立原型，以说明函数的名称、参数类型与个数，以及函数返回值的类型。

    其主要目的是让C++编译程序进行类型检查，即形参与实参的类型匹配检查，以及返回值是否与原型相符，以维护程序的正确性。

    例如:

int sum(int a,int b);   //是函数sum的原型

• 函数原型语法的一般形式为：返回类型 函数名（参数表）；

• 函数原型是一条语句，它必须以分号结束。

    例1.6 函数原型的说明：​​​​​​​

#include<iostream.h>void write(char *s);void main(){write("Hello,world!");}void write(char *s){cout<<s;}

    在程序中，要求一个函数的原型出现在该函数的调用语句之前。

    说明：

• 函数原型的参数表中可不包含参数的名字，而只包含它们的类型。例如：long Area(int ,int);

• 函数定义由函数首部和函数体构成。函数首部和函数原型基本一样，但函数首部中的参数必须给出名字而且不包含结尾的分号。

• Cpp的参数说明必须放在函数说明后的括号内，不可将函数参数说明放在函数首部和函数体之间。这种方法只在C中成立。

• 主函数不必进行原型说明，因为它被看成自动说明原型的函数。

• 原型说明中没有指定返回类型的函数(包括主函数main)，Cpp默认该函数的返回类型是int

• 如果一个函数没有返回值，则必须在函数原型中注明返回类型为void，主函数类似处理。

• 如果函数原型中未注明参数，Cpp假定该函数的参数表为空(void)。

6、const修饰符

• 在C中，习惯使用#define定义常量。

一般格式： #define 宏名 常数

    如:​​​​​​​

#define PI 3.14…………s = 2 * PI * r;…………

• C++利用const定义正规常数

    一般格式：const 数据类型标识符 常数名=常量值；

    采用这种方式定义的常量是类型化的，它有地址，可以用指针指向这个值，但不能修改它。

    说明:

1、const必须放在被修饰类型符和类型名前面

2、数据类型是一个可选项，用来指定常数值的数据类型，如果省略了该数据类型，那么编译程序认为它是 int 类型。

    如：const int a=10; 表示定义了一个初始值为10的整型常量，它在程序中不可改变，但可用于表达式的计算中。

    例2.6 #define的不安全性：​​​​​​​

#include "iostream.h"main(){    int a=1;    #define T1 a+a    #define T2 T1-T1    cout<<"T2 is "<<T2<<endl;    return 0;}

    但实际的输出是：T2 is 2。

    const作用与#define相似，但消除了#define的不安全性。

    如果用const取代了两个#define,就不会引起这个错误。

#include<iostream.h>int main(){    int a=1;    const T1=a+a;    const T2=T1-T1;    cout <<"T2 is"<<T2<<endl;    return 0;}

    const可以与指针一起使用:

• （1）指向常量的指针：一个指向常量的指针变量。

    例如：​​​​​​​

const char* pc=“abcd”;  //声明指向常量的指针pc[3]=‘x’;  //错误
pc=“efgh”;  //允许

• （2）常指针：把指针本身，而不是它指向的对象声明为常量。

    例如：​​​​​​​

char* const pc=“abcd”;  //常指针pc[3]=‘x’;  //合法pc=“efgh”;  //出错

    创建一个常指针，就是创建一个不能移动的固定指针，但是它所指的数据可以改变。例如:

• （3）指向常量的常指针：这个指针本身不能改变，它所指向的值也不能改变。

    要声明一个指向常量的常指针，二者都要声明为const。

    例如：​​​​​​​

const char* const pc=“abcd”;    //指向常量的常指针pc[3]=‘x’;  //出错pc=“efgh”;  //出错

    这个语句的含义是：声明了一个名为pc的指针变量，它是一个指向字符型常量的常指针，用“abcd”的地址初始化该指针。

    说明：

• (1). 如果用const定义的是一个整型常量，关键词int可以省略。所以下面的两语句是等价的

  const int bufsize=200;const bufsize=200;

• ​​​​​​​

• (2). 常量一旦被建立，在程序的任何地方都不能再更改。

• (3). 与#define定义的常量有所不同，const定义的常量可以有自己的数据类型，这样C++的编译程序可以进行更加严格的类型检查，具有良好的编译时的检测性。

• (4). 函数参数也可以用const说明，用于保证实参在该函数内部不被改动，大多数C++编译器能对具有const参数的函数进行更好的代码优化。   

    例如：通过函数i_Max求出整型数组a[200]中的最大值，函数原型应该是：int i_Max(const int* ptr);

    这样做的目的是确保原数组的数据不被破坏，即在函数中对数组元素的操作只许读，而不许写。调用时的格式可以是：i_Max(a);

7、void型指针

    void 通常表示无值，但将void作为指针的类型时，它却表示不确定的类型。

    这种void型指针是一种通用型指针，也就是说任何类型的指针值都可以赋给void类型的指针变量。

    例如下面的程序段：​​​​​​​

void pa;    //错误，不能声明void类型的指针变量void* pc;   //正确，可以声明void类型的指针int i=456;char c=‘a’;pc=&i;pc=&c;

    void型指针可以接受任何类型的指针的赋值，但对已获值的void型指针，对它在进行处理，如输出或传递指针值时，则必须进行强制类型转换，否则会出错。

#include <iostream.h>main(){    void *pc;    int i=456;    char c='a';    pc=&i;    cout<<*(int *)pc<<endl;    pc=&c;    cout<<*(char *)pc<<endl;    return 0;

8、内联函数

    调用函数时系统要付出一定的开销，用于信息入栈出栈和参数传递等。特别是对于那些函数体较小但调用又较频繁的函数，计算机的开销相对就比较可观。

    在C语言中，用宏替换，可解决这个问题。例如，有如下的函数：​​​​​​​

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

    用宏替换时，上面的函数功能可写为：

#define add(x,y) x+y

    C++引进了内联函数（inline function）的概念。

    宏替换实质上是文字替换。内联函数与一般函数不同的是，在进行程序的编译时，编译器将内联函数的目标代码作拷贝并将其插入到调用内联函数的地方。

    例1.7 内联函数的使用：​​​​​​​

#include "iostream.h"inline double circle(double r){return 3.1416*r*r;}int main(){    for(int i=1;i<=3;i++)        cout<<"r="<<i<<" area="<<circle(i)<<endl;    return 0;}

    说明：

• (1). 内联函数在第一次被调用前必须进行声明或定义，否则编译器将无法知道应该插入什么代码。

• (2). C++的内联函数具有与C中的宏定义#define相同的作用和类似机理，但消除了#define的不安全性。

• (3). 内联函数体内一般不能有循环语句和开关语句。

• (4). 后面类结构中所有在类说明体内定义的函数都是内联函数。

• (5). 通常较短的函数才定义为内联函数。

9、带有缺省参数值的函数

    在C++中，函数的参数可以有缺省值。

    当调用有缺省参数的函数时，如果相应的参数没有给出实参，则自动用相应的缺省参数值作为其实参。

    函数的缺省参数，是在函数原型中给定的。

    例如：​​​​​​​

int init(int x=5, int y=10);init(100,80);   //允许init(25);   //允许init();   //允许

    说明：

• （1）在函数原型中，所有取缺省值的参数必须出现在不取缺省值的参数的右边。

  int fun(int I,int j=5,int k); 错误

  int fun(int I,int k,int j=5); 正确

• （2）在函数调用时，若某个参数省略，则其后的参数皆应省略而采用缺省值。

  init (,20) 错误

    例.编写一个带有默认参数的函数，使得在默认情况下显示两个整数的较大者，否则显示两个整数的较小者。​​​​​​​

int main(){    void showValue(int x, int y, bool Max = true); // 声明函数    int a = 5, b = 10;    showValue(a,b);    showValue(a,b,false);    return 0;}void showValue(int x, int y, bool Max = true) // 定义函数{    if(Max)        cout << “the bigger value is: " << (x>y)?x:y << endl;    else        cout << "the smaller value is: " << (x<y)?x:y << endl;}

10、函数重载

(1) 什么是函数重载

    函数重载是指一个函数可以和同一作用域中的其他函数具有相同的名字，但这些同名函数的参数类型、参数个数不同。如：

#include <iostream.h>void whatitis(int i){ cout<<"this is integer"<<i<<endl;}void whatitis(char c[]){ cout<<“this is string”<<c<<endl; }main(){    int i=1;    char c[]="abcdef";    whatitis(i);    whatitis(c);}

    在本例中定义了两个名称都叫whatitis的函数，但它们的形参类型不同。因此，这两个函数就是重载函数。

(2) 为什么要使用函数重载

    在原有C语言中，每个函数必须有其唯一的名称，这样的缺点是所有具有相同功能、而只是函数参数不一样的函数，就必须用一个不同的名称.

    而C++中采用了函数重载后，对于具有同一功能的函数，如果只是由于函数参数类型不一样，则可以定义相同名称的函数。

(3) 匹配重载函数的顺序

    由于重载函数具有相同的函数名，在进行函数调用时，系统一般按照调用函数时的参数个数、类型和顺序来确定被调用的函数。

    具体来说，按以下三个步骤的先后次序找到并调用那个函数：

• （1）寻找一个严格的匹配，即：调用与实参的数据类型、个数完全相同的那个函数。

• （2）通过内部转换寻求一个匹配，即：通过（1）的方法没有找到相匹配的函数时，则由C++系统对实参的数据类型进行内部转换，转换完毕后，如果有匹配的函数存在，则执行该函数。

• （3）通过用户定义的转换寻求一个匹配，若能查出有唯一的一组转换，就调用那个函数。即：在函数调用处由程序员对实参进行强制类型转换，以此作为查找相匹配的函数的依据。

 例1.8 重载例子：​​​​​​​

#include <iostream.h>void print(double d){ cout<<"this is a double "<<d<<"\n"; }void print(int i){ cout<<"this is an integer "<<i<<"\n"; }void main(){    int x=1,z=10;    float y=1.0;    char c='a';    print(x);   //按规则（1）自动匹配函数void print(int i)    print(y);   //按规则（2）通过内部转换匹配函数 void print(double i)    //因为系统能自动将float型转换成double型    print(c);   //按规则（2）通过内部转换匹配函数 void print(int i)    //因为系统能自动将char型转换成int型    print(double(z));   //按规则（3）匹配void print(double i)    //因为程序中将实参z强制转换为double型。}

    例 重载例子:

    编写一个程序，用来求两个整数或3个整数中的最大数。如果输入两个整数，程序就输出这两个整数中的最大数，如果输入3个整数，程序就输出这3个整数中的最大数。​​​​​​​

#include <iostream>using namespace std;int main( ){    int max(int a,int b,int c); //函数声明    int max(int a,int b); //函数声明    int a=8, b=-12, c=27;    cout<<"max(a,b,c)="<<max(a,b,c)<<endl; //3个整数中的最大者    cout<<"max(a,b)="<<max(a,b)<<endl; //2个整数中的最大者}int max(int a,int b,int c){    if(b>a) a=b;    if(c>a) a=c;    return a;}int max(int a,int b){    if(a>b) return a;    else return b;}

(4) 定义重载函数时的注意事项

• 重载函数间不能只是函数的返回值不同，应至少在形参的个数、参数类型或参数顺序上有所不同。
  如：​​​​​​​

void myfun(int i){………………}int myfun(int i){………………}// 这种重载是错误的

• 应使所有的重载函数的功能相同。如果让重载函数完成不同的功能，会破坏程序的可读性。

(5) 函数模板

1) 函数模板 (function template)：

    建立一个通用函数，其函数类型和形参类型不具体指定，而是一个虚拟类型。

2) 应用情况：

    凡是函数体相同的函数都可以用这个模板来代替，不必定义多个函数，只需在模板中定义一次即可。在调用函数时系统会根据实参的类型来取代模板中的虚拟类型，从而实现了不同函数的功能。

3) 一般形式：
- template < typename T> // 模板头 通用函数定义
- template <class T> // 模板头 通用函数定义
- template <class T1,typename T2> // 多个参数 通用函数定义

    说明：class与typename可以通用

#include <iostream>using namespace std;template<typename T> // 模板声明，其中T为类型参数T max(T a, T b) // 定义一个通用函数， T作为虚拟的类型名{    if(b>a) return b;    else return a;}//template <typename T> T max(T a, T b)//{//…//}int main( ){    int i1=111, i2=222, i;    double d1=12.34, d2=56.78,d;    i=max(i1,i2); // 调用模板函数，此时T被 int 取代    d=max(d1,d2,d3); // 调用模板函数，此时T被 double 取代    cout<<"i_max=" << i <<endl;    cout<<"f_max=" <<f<<endl;    return 0;}

    函数模板说明：

1) 在对程序进行编译时，遇到第13行调用函数max(i1,i2)， 编译系统会将函数名max与模板max相匹配，将实参的类型取代了函数模板中的虚拟类型T。此时相当于已定义了一个函数，然后调用它。​​​​​​​

int max(int a,int b){if(b>a) a=b;if(c>a) a=c;return a;}

2) 与重载函数比较：用函数模板比函数重载更方便，程序更简洁。但应注意它只适用于：函数的参数个数相同而类型不同，且函数体相同的情况。如果参数的个数不同，则不能用函数模板；

3) main函数不能定义为模板函数。

11、作用域标示符::

    通常情况下，如果有两个同名变量，一个是全局的，另一个是局部的，那么局部变量在其作用域内具有较高的优先权。

    下面的例子说明了这个问题。​​​​​​​

#include "iostream.h"int avar=10;main( ){    int avar;    avar=25;    cout<<"avar is"<<avar<<endl;    return 0;}

    如果希望在局部变量的作用域内使用同名的全局变量，可以在全局变量加上“::”，此时::avar代表全局变量avar

#include <iostream.h>int avar=10;main(){int avar;avar=25;cout<<"local avar ="<<avar<<endl;cout<<"global avar="<<::avar<<endl;return 0;}

12、无名联合

    无名联合是C++中的一种特殊联合，可以声明一组无标记名共享同一段内存地址的数据项。如：​​​​​​​

union{    int i;    float f;}

    在此无名联合中，声明了变量i和f具有相同的存储地址。无名联合可通过使用其中数据项名字直接存取，例如可以直接使用上面的变量i或f，如：i=20;

13、强制类型转换

    在C中数据类型转换的一般形式：（数据类型标识符）表达式:​​​​​​​

int i=10;float x=(float) i;

    C++支持这样的格式，还提供了一种更为方便的函数调用方法，即将类型名作为函数名使用，使得类型转换的执行看起来好像调用了一个函数。形式为：数据类型标识符 （表达式）​​​​​​​

int i=10;float x=float(i);

    以上两种方法C++都接受，但推荐使用后一种方式。

14、动态内存分配

    作为对C语言中malloc和free的替换，C++引进了new和delete操作符。它们的功能是实现内存的动态分配和释放。

    动态分配new的一般形式是：

• 指针变量=new 数据类型；

• 指针变量=new 数据类型(初始值);

int *a， *b;a=new int;b=new int(10);

    释放由new操作动态分配的内存时，用delete操作。

    它的一般形式是：delete 指针变量;

delete a;delete b;

    例1.9 操作符new和delete的使用：​​​​​​​

#include <iostream.h>main(){    int *p; // 声明一个整型指针变量p    p=new int; // 动态分配一个存放int型数据的内存空间，并将首地址赋给p    *p=10;    cout<<*p;    delete p; // 释放指针变量p指向的内存空间    return 0;}

    例1.10 将new和delete用于结构类型:​​​​​​​

#include<iostream.h>#include<string.h>struct person {    char name[20];    int age;};main(){    person *p;    p=new person;    strcpy(p->name， "Wang Fun");    p->age=23;    cout<<"\n"<<p->name<<" "<<endl<<p->age;    delete p;    return 0;}

    与C的内存动态分配和释放操作（malloc和free）相比，C++提供的动态分配有以下优点：

• (1) new和delete 操作自动计算需要分配和释放类型的长度。这不但省去了用sizeof计算长度的步骤，更主要的是避免
  了内存分配和释放时因长度出错带来的严重后果；

• (2) new操作自动返回需分配类型的指针， 无需使用强制类型转换；

• (3) new操作能初始化所分配的类型变量。

• (4) new和delete都能可以被重载，允许建立自定义的内存管理法。

    对使用new和delete的几点说明：

• (1)用new分配的空间，使用结束后应该用delete显示的释放，否则这部分空间将不能回收而变成死空间。

• (2)使用new动态分配内存时，如果没有足够的内存满足分配要求， new将返回空指针(NULL)。因此通常要对内存的动态分配是否成功进行检查。

    例1.11 对内存的动态分配是否成功进行检查：​​​​​​​

#include <iostream.h>main(){    int * p;    p=new int;    if(!p){        cout<<"allocation failure\n";        return 1;    }    *p=20;    cout<<*p;    delete p;    return 0;}

• (3) 使用new可以为数组动态分配内存空间这是需要在类型后面缀上数组大小。其语法形式为：
  指针变量=new 类型名 [下标表达式];

  如：int *pi=new int[2][3][4];

  其中第一维的界值可以是任何合法的表达式，如：int i=3; int *pi=new int[ i ][2][3];

  例如：int *pi=new int[10];

  这时new为具有10个元素的整型数组分配了内存空间，并将首地址赋给了指针pi。

  使用new为多维数组分配空间时，必须提供所有维的大小，

• (4) 释放动态分配的数组存储区时，可使用delete运算符，其语法形式为：delete [ ]指针变量;

  无须指出空间的大小，但老版本的Cpp要求在delete的方括号中标出数字，以告诉Cpp要释放多少个元素所占的空间。例如：delete []pi; delete [10]pi;

• (5) new可在为简单变量分配内存空间的同时，进行初始化。这时的语法形式为：指针变量=new 类型名(初始值列表)

    例 1.12 new为简单变量分配内存空间的同时，进行初始化:​​​​​​​

#include <iostream.h>int main(){    int *p;    p=new int(99); // 动态分配内存，并将99作为初始值赋给它    if (!p)    {        cout<<"allocation failure\n";        return 1;    }    cout<<*p;    delete p;    return 0;}

    例 1.13 给数组分配内存空间的例子。​​​​​​​

#include <iostream.h>main(){    double *s;    s=new double[10];    if(!s){        cout<<"alocation failure\n";        return 1;    }    for(int i=0;i<10;i++)        s[i]=100.00+2*i;    for(int i=0;i<10;i++)        cout<<s[i]<<" ";    delete []s;    return 0;}

15、引用

(1) 引用的概念

    引用就是某一变量（目标）的一个别名，这样对引用的操作就是对目标的操作。

    引用的声明方法： 类型标识符 &引用名=目标变量名;​​​​​​​

int a;int &ra=a; //定义引用ra,它是变量a的引用，即别名

    说明：

• （1） &在此不是求地址运算，而是起标识作用。

• （2） 类型标识符是指目标变量的类型。

• （3）声明引用时，必须同时对其进行初始化。

• （4）引用声明完毕后，相当于目标变量名有两个名称。

• （5）声明一个引用，不是新定义了一个变量，系统并不给引用分配存储单元。

    例1.15 引用的使用：​​​​​​​

#include <iostream.h>void main(){    int i;    int &j=i;    i=30;    cout<<"i="<<i<<"j="<<j<<"\n";    j=80;    cout<<"i="<<i<<"j="<<j<<"\n";    cout<<"Address of i"<<&i<<"\n";    cout <<"Address of j"<<&j<<"\n";}

    结果：​​​​​​​

i=30 j=30i=80 j=80Address of oxfff4Address of oxfff4

    例1.16 使用引用可以简化程序：​​​​​​​

#include<iostream.h>main(){    int i=15;    int* iptr=&i;    int & rptr=i;    cout<<" i is "<<i<<endl;    cout<<" *iptr is "<<*iptr<<endl;    cout<<" rptr is "<<rptr<<endl;    i=29;    cout<<" After changing i to 29："<<endl;    cout<<" i is "<<i<<endl;    cout<<" *iptr is "<<*iptr<<endl;    cout<<" rptr is "<<rptr<<endl;    return 0;}

    运行结果：​​​​​​​

i is 15*iptr is 15rptr is 15After changing i to 29：i is 29*iptr is 29rptr is 29

(2) 引用的使用

• （1）引用名可以是任何合法的变量名。除了用作函数的参数或返回类型外，在声明时，必须立即对它进行初始化，不能声明完后再赋值。​​​​​​​

int i;int &j;j=i;

• （2）引用不能重新赋值，不能再把该引用名作为其他变量名的别名，任何对该引用的赋值就是该引用对应的目标变量名的赋值。对引用求地址，就是对目标变量求地址

int i=5;int &j1=i; int &j2=j1; 
int num=50;int & ref=num;int *p=&ref;

• （3）由于指针变量也是变量，所以，可以声明一个指针变量的引用。方法是： 类型标识符 *&引用名=指针变量名;​​​​​​​

#include <iostream.h>void main(){    int *a; //定义指针变量a    int *&p=a; //定义引用p，初始化为指针变量a，所以p是a的引用（别名）    int b=10;    p=&b; //等价于a=&b，即将变量b的地址赋给a。    cout<<*a<<endl; //输出变量b的值    cout<<*p<<endl; //等价于cout<<*a;    cout<<a<<endl; //输出a和p的地址    cout<<p<<endl;}

• （4）引用是对某一变量或目标对象的引用，它本身不是一种数据类型，因此引用本身不占存储单元，这样，就不能声明引用的引用，也不能定义引用的指针。​​​​​​​

int a;int & & ra=a; //错误int &*p=&ra; //错误

• （5）不能建立数组的引用，因为数组是一个由若干个元素所组成的集合，所以就无法建立一个数组的别名。

• （6）不能建立空指针的引用

int &rp=NULL; //错误

• （7）也不能建立空类型void的引用，因为尽管在C++语言中有void数据类型，但没有任何一个变量或常量属于void类型。

void &ra=3; //错误

• (8) 尽管引用运算符与地址操作符使用相同的的符号，但时不一样的。引用仅在声明时带有引用运算符&，以后就像普通变量一样使用，不能再带&。其他场合使用的&都是地址操作符。

int j=5;int& i=j; // 声明引用i， "&"为引用运算符i=123; // 使用引用i，不带引用运算符int *pi=&i; // 在此， "&"为地址操作符cout<<&pi; // 在此， "&"为地址操作符

(3) 用引用作为函数的参数

    一个函数的参数也可定义成引用的形式:​​​​​​​

void swap(int &p1, int &p2) //形参p1, p2都是引用{    int p;    p=p1;    p1=p2;    p2=p;}

    在主调函数的调用点处，直接以变量作为实参进行调用即可，不需要实参变量有任何的特殊要求。

swap(a,b); //直接以a和b作为实参调用swap函数

    例1.17 采用指针参数的例子:​​​​​​​

#include<iostream.h>void swap(int *m， int *n){    int temp;    temp=*m;    *m= *n;    *n=temp;}main(){    int a=5， b=10;    cout<<"a="<<a<<" b="<<b<<endl;    swap(&a， &b);    cout<<"a="<<a<<" b="<<b<<endl;    return 0;}

    运行结果：​​​​​​​

a=5 b=10a=10 b=5

    例1.18 采用“引用参数”传递函数参数。​​​​​​​

#include <iostream.h>void swap(int& m， int& n){    int temp;    temp=m;    m=n;    n=temp;}main(){    int a=5， b=10;    cout<<"a="<<a<<" b="<<b<<endl;    swap(a， b);    cout<<"a="<<a<<" b="<<b<<endl;    return 0;}

    运行结果：​​​​​​​

a=5 b=10a=10 b=5

(4) 用引用返回函数值

    函数可以返回一个引用，将函数说明为返回一个引用的主要目的是：为了将函数用在赋值运算符的左边。

    要以引用返回函数值，则函数定义时要按以下格式：​​​​​​​

类型标识符 &函数名（形参列表及类型说明）{函数体}

    说明:

• 以引用返回函数值，定义函数时需要在函数名前加&

• 用引用返回一个函数值的最大好处是，在内存中不产生被返回值的副本。

    例1.19 返回引用的函数。

#include <iostream.h>int a[]={1， 3， 5， 7， 9};int& index(int); // 声明返回引用的函数void main(){    cout<<index(2)<<endl;    index(2)=25; // 将a[2]重新赋值为25    cout<<index(2)<<endl;}int& index(int i){    return a[i];}

    例1.20 用引用返回函数的值。​​​​​​​

#include<iostream.h>int A[10];int& array(int i);void main(){    int i， number;    A[0]=0;    A[1]=1;    cin>>number;    for (i=2;i<number;i++)    {        array(i)=array(i-2)+array(i-1);        cout<<"array("<<i<<")="<<array(i)<<endl;    }}int& array(int i){    return A[i];}

    运行结果：

array(2)=1array(3)=2array(4)=3array(5)=5array(6)=8array(7)=13array(8)=21array(9)=34

• 在定义返回引用的函数时，注意不要返回该函数内的自动变量 (局部变量)的引用，由于自动变量的生存期仅限于函数内部，当函数返回时，自动变量就消失了。

int& fun(){    int a;    //...    return a;}

• 传递引用给函数与传递指针的效果是一样的，但使用更简练。

• 使用引用传递函数的参数，在内存中并没有产生实参的副本，它是直接对实参操作；

void swap(int *p1, int *p2){    int p;    p=*p1; //必须用“*指针变量名”的形式操作目标变量    p1=*p2;    *p2=p;}main(){    int a,b;    cin>>a>>b;    swap(&a,&b); //必须以变量a和b的地址作为实参    cout<<a<<b;}

    如何使一个被调函数同时返回多个值？

    由于函数的返回值是通过函数体中的return语句完成的，但一个return语句只能返回一个值，为此，我们可以采用以下方法：

• （1）利用全局变量的方法：在函数中把所需数据保存在全局变量中。当被调函数执行完毕后在主调函数中直接读取全局变量的值即可。

• （2）使用指针或数组的方法：指针作为函数参数的情况下，可将主调函数的某些变量的地址传递给被调函数。

• （3）利用引用的方法：使用引用传递参数，可以在被调函数中改变主调函数中目标变量的值，这种方法实际上就是可以使被调函数返回多个值。

    例 使用引用使函数返回多个值：

    以下定义了可以同时返回10个数中的最大值和最小值的函数max_min。​​​​​​​

#include <iostream.h>void max_min(int *p,int n,int &max,int &min);//声明函数max_minvoid main(){    int a[10];    int ma,mi;    int i;    for(i=0;i<10;i++)        cin>>a[i];    max_min(a,10,ma,mi); //调用函数max_min    cout<<ma<<mi;}void max_min(int *p,int n,int &max,int &min)//形参max 和min定义成引用{    int i=0;    max=*(p+i);    min=*(p+i);    for(i=1;i<n;i++) {        if(max<*(p+i))            max=*(p+i); //实质上就是对实参变量ma赋值        if(min>*(p+i))            min=*(p+i); //实质上就是对实参变量mi赋值    }}

    例 以下程序中定义了一个普通的函数fn1（它用返回值的方法返回函数值），另外一个函数fn2，它以引用的方法返回函数值。​​​​​​​

#include <iostream.h>float temp; //定义全局变量tempfloat fn1(float r); //声明函数fn1float &fn2(float r); //声明函数fn2float fn1(float r) //定义函数fn1，它以返回值的方法返回函数值{    temp=(float)(r*r*3.14);    return temp;}float &fn2(float r) //定义函数fn2，它以引用方式返回函数值{    temp=(float)(r*r*3.14);    return temp;}void main() //主函数{    float a=fn1(10.0);//第1种情况，系统生成要返回值的副本(即临时变量)    float &b=fn1(10.0);//第2种情况，可能会出错(不同C++系统有不同规定)    //不能从被调函数中返回一个临时变量或局部变量的引用    float c=fn2(10.0); //第3种情况，系统不生成返回值的副本    //可以从被调函数中返回一个全局变量的引用    float &d=fn2(10.0); //第4种情况，系统不生成返回值的副本    //可以从被调函数中返回一个全局变量的引用    cout<<a<<c<<d;}

    一个返回引用的函数值作为赋值表达式的左值。

    一般情况下，赋值表达式的左边只能是变量名，即被赋。

    值的对象必须是变量，只有变量才能被赋值，常量或表达式不能被赋值，但如果一个函数的返回值是引用时，赋值号的左边可以是该函数的调用。

    例2-26 测试用返回引用的函数值作为赋值表达式的左值。​​​​​​​

#include <iostream.h>int &put(int n);int vals[10];int error=-1;void main(){    put(0)=10; //以put(0)函数值作为左值， 等价于vals[0]=10;    put(9)=20; //以put(9)函数值作为左值， 等价于 vals[9]=10;    cout<<vals[0];    cout<<vals[9];}int &put(int n){    if (n>=0 && n<=9 )        return vals[n];    else{        cout<<”subscript error”;        return error;    }}

    用const限定引用:

    声明方式：const 类型标识符 &引用名=目标变量名;

    用这种方式声明的引用，不能通过引用对目标变量的值进行修改，从而使引用的目标成为const，达到了引用的安全性。

    例2-27:​​​​​​​

#include “iostream.h”double &fn(const double &pd){    static double ad=32;    ad+=pd;    cout<<pd<<endl;    return ad;}void main(){    double a=100.0;    double &pa=fn(a);    cout<<pa<<endl;    a=200.0;    pa=fn(a);    cout<<pa<<endl;}

    程序运行的结果：​​​​​​​

100132200332

    引用总结:

• （1）在引用的使用中，单纯给某个变量取个别名是毫无意义的，引用的目的主要用于在函数参数传递中，解决大对象的传递效率和空间不如意的问题。

• （2）用引用传递函数的参数，能保证参数传递中不产生副本，提高传递的效率，且通过const的使用，保证了引用传递的安全性。

• （3）引用与指针的区别是，指针通过某个指针变量指向一个对象后，对它所指向的变量间接操作，程序中使用指针，程序的可读性差；而引用本身就是目标变量的别名，对引用的操作就是对目标变量的操作。

    课后练习题目:

#include<iostream.h>int &max(int &num1,int &num2); // 返回一个较大值int &min(int &num1,int &num2); // 返回一个较小值main(){    int num1， num2;    cout<<"Enter the first number: ";    cin>>num1;    cout<<"Enter the second number: ";    cin>>num2;    max(num1,num2)=0;    cout<<"\nAfter putting zero in largest, the numbers are";    cout<<"\n"<<num1<<" and "<<num2<<"\n";    cout<<"\nNow， please enter two more numbers.\n";    cout<<"Enter the first number :";    cin>>num1;    cout<<"Enter the second number:";    cin>>num2;    min(num1， num2)=0;    cout<<"\nAfter putting zero in smallest the numbers are";    cout<<"\n"<<num1<<" and "<<num2<<"\n";    return 0;}int &max(int &num1,int &num2){    return (num1>num2)?num1:num2;}int &min(int &num1,int &num2){    return (num1<num2)?num1:num2;}

四、 Linux内核代码中常用的数据结构

Linux内核代码中广泛使用了数据结构和算法，其中最常用的两个是链表和红黑树。

链表

Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。

链表的每个元素都是离散存放的，因此不需要占用连续的内存。链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息，而指针区用来指向链表的前继节点或者后继节点。因此，链表就是利用指针将各个节点串联起来的一种存储结构。

（1）单向链表

单向链表的指针区只包含一个指向下一个节点的指针，因此会形成一个单一方向的链表，如下代码所示。​​​​​​​

struct list {    int data;   /*有效数据*/    struct list *next; /*指向下一个元素的指针*/};

如图所示，单向链表具有单向移动性，也就是只能访问当前的节点的后继节点，而无法访问当前节点的前继节点，因此在实际项目中运用得比较少。

（2）双向链表

如图所示，双向链表和单向链表的区别是指针区包含了两个指针，一个指向前继节点，另一个指向后继节点，链表头应该是next指向节点，如下代码所示。​​​​​​​

struct list {    int data;   /*有效数据*/    struct list *next; /*指向下一个元素的指针*/    struct list *prev; /*指向上一个元素的指针*/};

（3）Linux内核链表实现

单向链表和双向链表在实际使用中有一些局限性，如数据区必须是固定数据，而实际需求是多种多样的。这种方法无法构建一套通用的链表，因为每个不同的数据区需要一套链表。

为此，Linux内核把所有链表操作方法的共同部分提取出来，把不同的部分留给代码编程者自己去处理。

Linux内核实现了一套纯链表的封装，链表节点数据结构只有指针区而没有数据区，另外还封装了各种操作函数，如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。

Linux内核链表使用 struct list_head 数据结构来描述。​​​​​​​

<include/linux/types.h>struct list_head {struct list_head *next, *prev;
};

struct list_head数据结构不包含链表节点的数据区，通常是嵌入其他数据结构，如struct page数据结构中嵌入了一个lru链表节点，通常是把page数据结构挂入LRU链表。​​​​​​​

<include/linux/mm_types.h>struct page {...struct list_head lru;...
}

链表头的初始化有两种方法，一种是静态初始化，另一种动态初始化。

把next和prev指针都初始化并指向自己，这样便初始化了一个带头节点的空链表。​​​​​​​

<include/linux/list.h>/*静态初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)/*动态初始化*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{list->next = list;list->prev = list;
}

添加节点到一个链表中，内核提供了几个接口函数，如list_add()是把一个节点添加到表头，list_add_tail()是插入表尾。​​​​​​​

<include/linux/list.h>void list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

遍历节点的接口函数。​​​​​​​

#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)

这个宏只是遍历一个一个节点的当前位置，那么如何获取节点本身的数据结构呢？这里还需要使用list_entry()宏。​​​​​​​

#define list_entry(ptr, type, member) \container_of(ptr, type, member)
//container_of()宏的定义在kernel.h头文件中。
#define container_of(ptr, type, member) ({            \const typeof( ((type *)0)->member ) *__mptr = (ptr);    \(type *)( (char *)__mptr - offsetof(type,member) );})#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

其中offsetof()宏是通过把0地址转换为type类型的指针，然后去获取该结构体中member成员的指针，也就是获取了member在type结构体中的偏移量。最后用指针ptr减去offset，就得到type结构体的真实地址了。对linux内核中container_of()宏的理解 

下面是遍历链表的一个例子。​​​​​​​

<drivers/block/osdblk.c>static ssize_t class_osdblk_list(struct class *c,struct class_attribute *attr,char *data)
{int n = 0;struct list_head *tmp;list_for_each(tmp, &osdblkdev_list) {struct osdblk_device *osdev;osdev = list_entry(tmp, struct osdblk_device, node);n += sprintf(data+n, "%d %d %llu %llu %s\n",osdev->id,osdev->major,osdev->obj.partition,osdev->obj.id,osdev->osd_path);}return n;
}

红黑树

红黑树（Red Black Tree）被广泛应用在内核的内存管理和进程调度中，用于将排序的元素组织到树中。红黑树被广泛应用在计算机科学的各个领域中，它在速度和实现复杂度之间提供一个很好的平衡。

红黑树是具有以下特征的二叉树：

• 每个节点或红或黑。

• 每个叶节点是黑色的。

• 如果结点都是红色，那么两个子结点都是黑色。

• 从一个内部结点到叶结点的简单路径上，对所有叶节点来说，黑色结点的数目都是相同的。

红黑树的一个优点是，所有重要的操作（例如插入、删除、搜索）都可以在O(log n)时间内完成，n为树中元素的数目。

经典的算法教科书都会讲解红黑树的实现，这里只是列出一个内核中使用红黑树的例子，供读者在实际的驱动和内核编程中参考。这个例子可以在内核代码的documentation/Rbtree.txt文件中找到。​​​​​​​

#include <linux/init.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/mm.h>
#include <linux/rbtree.h>MODULE_AUTHOR("figo.zhang");
MODULE_DESCRIPTION(" ");
MODULE_LICENSE("GPL");struct mytype { struct rb_node node;int key; 
};/*红黑树根节点*/struct rb_root mytree = RB_ROOT;
/*根据key来查找节点*/
struct mytype *my_search(struct rb_root *root, int new)
{struct rb_node *node = root->rb_node;while (node) {struct mytype *data = container_of(node, struct mytype, node);if (data->key > new)node = node->rb_left;else if (data->key < new)node = node->rb_right;elsereturn data;}return NULL;}/*插入一个元素到红黑树中*/int my_insert(struct rb_root *root, struct mytype *data)
{struct rb_node **new = &(root->rb_node), *parent=NULL;/* 寻找可以添加新节点的地方 */while (*new) {struct mytype *this = container_of(*new, struct mytype, node);parent = *new;if (this->key > data->key)new = &((*new)->rb_left);else if (this->key < data->key) {new = &((*new)->rb_right);} elsereturn -1;}/* 添加一个新节点 */rb_link_node(&data->node, parent, new);rb_insert_color(&data->node, root);return 0;}static int __init my_init(void)
{int i;struct mytype *data;struct rb_node *node;/*插入元素*/for (i =0; i < 20; i+=2) {data = kmalloc(sizeof(struct mytype), GFP_KERNEL);data->key = i;my_insert(&mytree, data);}/*遍历红黑树，打印所有节点的key值*/for (node = rb_first(&mytree); node; node = rb_next(node)) printk("key=%d\n", rb_entry(node, struct mytype, node)->key);return 0;
}static void __exit my_exit(void)
{struct mytype *data;struct rb_node *node;for (node = rb_first(&mytree); node; node = rb_next(node)) {data = rb_entry(node, struct mytype, node);if (data) {rb_erase(&data->node, &mytree);kfree(data);}}
}
module_init(my_init);
module_exit(my_exit);

mytree是红黑树的根节点，my_insert()实现插入一个元素到红黑树中，my_search()根据key来查找节点。内核大量使用红黑树，如虚拟地址空间VMA的管理。

无锁环形缓冲区

生产者和消费者模型是计算机编程中最常见的一种模型。生产者产生数据，而消费者消耗数据，如一个网络设备，硬件设备接收网络包，然后应用程序读取网络包。

环形缓冲区是实现生产者和消费者模型的经典算法。环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区可写的数据。通过移动读指针和写指针实现缓冲区数据的读取和写入。

在Linux内核中，KFIFO是采用无锁环形缓冲区的实现。FIFO的全称是“First In First Out”，即先进先出的数据结构，它采用环形缓冲区的方法来实现，并提供一个无边界的字节流服务。

采用环形缓冲区的好处是，当一个数据元素被消耗之后，其余数据元素不需要移动其存储位置，从而减少复制，提高效率。

（1）创建KFIFO

在使用KFIFO之前需要进行初始化，这里有静态初始化和动态初始化两种方式。​​​​​​​

<include/linux/kfifo.h>int kfifo_alloc(fifo, size, gfp_mask)

该函数创建并分配一个大小为size的KFIFO环形缓冲区。第一个参数fifo是指向该环形缓冲区的struct kfifo数据结构；第二个参数size是指定缓冲区元素的数量；第三个参数gfp_mask表示分配KFIFO元素使用的分配掩码。

静态分配可以使用如下的宏。​​​​​​​

#define DEFINE_KFIFO(fifo, type, size)#define INIT_KFIFO(fifo)

（2）入列

把数据写入KFIFO环形缓冲区可以使用kfifo_in()函数接口。

int kfifo_in(fifo, buf, n)

该函数把buf指针指向的n个数据复制到KFIFO环形缓冲区中。第一个参数fifo指的是KFIFO环形缓冲区；第二个参数buf指向要复制的数据的buffer；第三个数据是要复制数据元素的数量。

（3）出列

从KFIFO环形缓冲区中列出或者摘取数据可以使用kfifo_out()函数接口。

#define    kfifo_out(fifo, buf, n)

该函数是从fifo指向的环形缓冲区中复制n个数据元素到buf指向的缓冲区中。如果KFIFO环形缓冲区的数据元素小于n个，那么复制出去的数据元素小于n个。

（4）获取缓冲区大小

KFIFO提供了几个接口函数来查询环形缓冲区的状态。​​​​​​​

#define kfifo_size(fifo)#define kfifo_len(fifo)#define kfifo_is_empty(fifo)#define kfifo_is_full(fifo)

kfifo_size()用来获取环形缓冲区的大小，也就是最大可以容纳多少个数据元素。kfifo_len()用来获取当前环形缓冲区中有多少个有效数据元素。kfifo_is_empty()判断环形缓冲区是否为空。kfifo_is_full()判断环形缓冲区是否为满。

（5）与用户空间数据交互

KFIFO还封装了两个函数与用户空间数据交互。​​​​​​​

#define    kfifo_from_user(fifo, from, len, copied)#define    kfifo_to_user(fifo, to, len, copied)

kfifo_from_user()是把from指向的用户空间的len个数据元素复制到KFIFO中，最后一个参数copied表示成功复制了几个数据元素。

kfifo_to_user()则相反，把KFIFO的数据元素复制到用户空间。这两个宏结合了copy_to_user()、copy_from_user()以及KFIFO的机制，给驱动开发者提供了方便。