18-指针的高级应用

指针的高级应用

A language that doesn’t affect the way you think about programming, is
not worth knowing. [^1]

指针的高级应用

零前言

一动态存储分配

C 语言的数据结构通常是固定大小的。例如，一旦程序完成编译，数组元素的数组就固定了。（C99 中，变长数组的长度在运行时确定，但是数组的声明周期内仍然是固定长度的。）因为在编写程序时强制选择了大小，在不修改程序并且再次编译程序的情况下无法改变数据结构的大小。

为了扩大数据结构（前面我们通常用到的是数组）的大小，可以增加数组大小并重新编译程序。但是，无论如何增大数组，始终有可能填满数组。幸运的是，C 语言支持动态存储分配，即在程序执行期间分配内存单元的能力。利用动态存储分配，可以设计出根据需要扩大（和缩小）的数据结构。

0. 内存分配函数

为了动态地分配存储空间，需要调用三种内存分配函数的一种，这些函数都是声明在头<stdlib.h>中的。

malloc函数 —— 分配内存块，但是不对内存块进行初始化
calloc 函数 —— 分配内存块，并对内存块进行清零
realloc 函数 —— 调整先前分配的内存块的大小

这三种函数中，malloc函数是最常用的。因为 malloc 不需要对分配的内存块进行清零，所以它比 calloc 函数效率更高。

当为申请内存块而调用内存分配函数时，由于函数无法知道计划存储在内存块中的数据是什么类型的，所以它不能返回 int 类型，char类型等普通类型的指针。取而代之的是，函数返回void*类型的值。void*类型的值是“通用”指针，本质上它只是内存地址。

1. 空指针

当调用内存分配函数中时，总存在这样的可能性：找不到满足我们需要的足够大的内存块。如果真的发生了这类问题，函数会返回空指针（null pointer）。空指针是“不指向任何地方的指针”，这是一个区别于所有有效指针的特殊值。

**注意：试图通过空指针访问内存的效果是未定义的，程序可能出现崩溃或者出现不可预测的行为。**因此，在把内存分配函数的返回值存储到指针变量中以后，需要判断该指针变量是否为空指针。

空指针用名为 NULL 的宏来表示，所以可以使用下列方式测试 malloc 函数的返回值：

p = malloc(10000);
if(p == NULL){
    // allocation failed; take approriate action
}

一些程序员把 malloc 函数的调用和 NULL 的测试组合起来：

if((p == malloc(10000)) == NULL){
     // allocation failed; take approriate action
}

名为 NULL的宏在 6 个头<locale.h> <stddef.h> <stdio.h> <stdlib.h> <string.h> <time.h>中都有定义。

语句：

if(p == NULL) ...

可以写成：

if(!p) ...

而语句：

if(p != NULL) ...

可以写成：

if(p) ...

二动态分配字符串

0. 使用 malloc 函数为字符串分配内存

malloc函数具有如下原型：

void* malloc(size_t size);

size_t是 C 语言库定义的无符号整数类型，除非分配的空间巨大，否则可以用 int型。

为长度为 n 的字符串分配内存空间：

char* p = malloc(n + 1);

n + 1为空字符留出空间。执行赋值操作时会把 malloc 函数返回的通用指针转化为char*类型，而不需要强制类型转换。然后，一般我们都会进行强制类型转换：

p = (char*)malloc(n + 1);

注意：为字符串分配内存空间时，不要忘记包含空字符的空间

1. 在字符串函数中使用动态存储分配

我们自行编写一个函数将两个字符串连接起来而不改变其中任何一个字符串。先调用 malloc 分配适当大小的内存空间。接下来函数把第一个字符串复制到新的内存空间中，然后调用 strcat函数来拼接第二个字符串：

char* concat(const char* s1, const char* s2){
    
    char* ret = (char*)malloc(strlen(s1) + strlen(s2) + 1);
    
    if(ret == NULL){
        printf("Error:malloc failed in concat.\n");
        exit(EXIT_FAILURE);
    }
    strcpy(ret, s1);
    strcat(ret, s2);
    
    return ret;
}

如果 malloc 函数返回 NULL，函数显示出错信息并终止程序。这并不是正确的措施。

下面时可能的 concat 函数调用方式：

p = concat("abc", "def");

这个调用后，p 将指向字符串"abcdef"，此字符串存储在动态内存分配的数组中。数组包含结尾的空字符一共 7 个字符长。

注意：注意最后调用 free 函数释放申请的空间

3. 动态分配字符串的数组

程序：显示一个月的提醒列表

前面我们把字符串存储在二维数组中，但是这可能会浪费空间。后面的教学中我们设想使用指针数组存储字符串，让一维数组的每个元素都指向一个字符串字面量。如果数组元素是指向动态分配的字符串的指针，那么是可以实现我们的设想的。

下面的程序对之前的程序作了小部分修改，修改的地方后面用注释注明了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX_REMIND 50
#define MSG_LEN 100


int read_line(char str[], int read_num);

int main(void) {
	
	char* reminders[MAX_REMIND]; // 存放提示的数组 // change
	char day_str[3];//当前日期转换为字符串
	char msg_str[MSG_LEN + 1]; //当前输入的提示消息
	int day, num_remind = 0; // 日期和当前提示数
	int i, j;


	for (;;) {

		if (num_remind == MAX_REMIND) {
			printf("-- No space left --\n");
			break;
		}

		printf("Enter day and reminder:");

		scanf("%2d", &day); //每月的日期只用两个数表示即可，只读 2 个字段

		if (day == 0)
			break;

		sprintf(day_str, "%2d", day); // 将 day 以 "%2d" 的格式写入 day_str 字符数组中。"%2d" 保证小于10的天占两位右对齐
		read_line(msg_str, MSG_LEN);
		

		// 寻找当前输入的提示应该放到提示数组的那个位置
		for (i = 0; i < num_remind; i++) {
			// 说明当前输入的日期应该排在此行前
			if (strcmp(day_str, reminders[i]) < 0)
				break;
		}
		
		// 将当前输入的提示插入到正确的位置
		for (j = num_remind; j > i; j--) {
			reminders[j] = reminders[j - 1]; // change
		}

		reminders[i] = (char*)malloc(sizeof(msg_str) + sizeof(day_str) + 1); // change
		
		// change																	 
		if (reminders[i] == NULL) {
			printf("-- No space left --\n");
			break;
		}
	
		strcpy(reminders[i], day_str);
		strcat(reminders[i], msg_str);// 刚好将 day_str 复制进去的空字符覆盖掉了

		num_remind++;
	}

	printf("Day Reminder: \n");
	for (i = 0; i < num_remind; i++)
		printf("%s\n", reminders[i]);


	return 0;
}


int read_line(char str[], int read_num) {

	int ch, count = 0;

	while ((ch = getchar()) != '\n') {
		if (count < read_num) {
			str[count++] = ch;
		}
	}

	str[count] = '\0';

	return count;
}

三动态分配数组

当编写程序时，常常很难为数组估计合适的大小。前面我们是用宏来定义数组的大小；现在我们可以在程序执行期间为数组动态分配内存空间。

0. 使用 malloc 函数为数组分配存储空间

分配一个int[n]大小的数组：

int* a = (int*)malloc(sizeof(int) * n);

对 a 指向的数组进行初始化：

for(i = 0; i < n; i++)
    a[i] = 0;

1. `calloc` 函数

函数原型：

void* calloc(size_t nmemb, size_t size);

下面 calloc 函数调用为 n 个整数的数组分配存储空间，并且初始化所有整数为 0：

a = calloc(n, sizeof(int));

调用以 1 作为第一个实参的 calloc 函数，可以为任何类型的数据分配空间：

struct point {int x, y}*p;
p = calloc(1, sizeof(struct point));

执行完此语句后，p 将指向一个结构，且此结构的成员 x 和 y 都会被设为 0 。

2. `realloc` 函数

一旦为数组分配完内存，稍后可能会发现数组过大或过小。realloc 函数可以调整数组的大小使它更适合需要。

函数原型

void* realloc(void* ptr, size_t size);

当调用realloc函数时，ptr 必须指向先前通过 malloc，calloc 或 realloc 的调用获得的内存块。size 表示内存块的新尺寸，新尺寸可能大于或小于原有尺寸。

注意：要确定传递给 realloc 函数的指针来自于先前 malloc，calloc 或 realloc 的调用。如果不是这样的指针，程序可能会行为异常

C 标准列出了几条关于 realloc 函数的规则：

当扩展内存块时，realloc 不会对添加进内存块的字节进行初始化
如果 realloc 函数不能按要求扩大内存块，那么它会返回空指针，并且原有的内存块中的数据不会发生改变
如果 realloc 函数调用时以空指针作为第一个参数，那么它的行为就像 malloc 函数一样
如果 realloc 函数被调用时以 0 作为第二个实参，那么它会释放掉内存块

如果无法扩大内存块（因为内存块后面的字节已经用于其他目的），realloc 函数会在别处分配新的内存块，然后把旧块中的内容复制到新块中。

注意：一旦 realloc 函数返回，请一定要对指向内存块的所有指针进行更新，因为 realloc 函数可能会使内存块移动到了其他地方。

四释放存储空间

动态存储分配函数所获得的内存都来自一个称为堆（heap）的存储池。过于频繁地调用这些函数（或者让这些函数申请大内存块）可能会耗尽堆，这回导致函数返回空指针。

更糟的是，程序可能分配了内存块，然后又丢失了对这些块的记录，因而浪费了空间。请思考下例：

p = malloc(...);
q = malloc(...);
p = q;

如图：

因为没有指针指向第一个内存块，所以再也不能使用此块内存了。

对于程序而言，不可再访问到的内存称为垃圾（garbage）。留有垃圾的程序存在内存泄漏（memory leak）现象。一些语言提供垃圾收集器（garbage collector）用于垃圾的自动定位和回收，但是 C 语言不提供。所以我们使用 free函数来释放不需要的内存。

0. `free`函数

函数原型：

void* free(void* ptr);

使用 free 函数很简单，将指向不再需要的内存块的指针传递给 free 函数即可：

p = malloc(...);
q = malloc(...);
free(p);
p = q;

调用 free 函数会释放 p 指向的内存块。然后此内存块可以被后续的 malloc 函数或其他内存分配函数的调用重新使用。

注意：

free 函数实参必须是先前由内存分配函数返回的指针，如果参数是指向其他对象的指针，可能会导致未定义行为。
实参可以空指针，此时 free 调用不起作用

1. “悬空指针”问题

虽然 free 函数允许收回不再需要的内存，但会导致一个新的问题：悬空指针（dangling pointer）。调用 free(p)函数会释放 p 指向的内存块，但是不会改变 p 本身。如果忘记了 p 不再指向有效内存块：

char* p = malloc(4);
...
free(p);
...
strcpy(p, "abc"); // wrong

修改 p 指向的内存是严重的错误，因为程序不再对此内存由任何控制权了。

注意：试图访问或修改释放掉的内存块会导致未定义行为。

五链表

链表这部分请参考【数据结构轻松学】部分。

程序：维护零件数据库

下面重做前面的程序，这次把数据库存储在链表中。链表代替数组主要有两个好处：

不需要事先限制数据库的大小
可以很容易地按零件编号对数据库排序（本程序采用默认升序排序）

#include<stdio.h>
#include<stdlib.h>
#include"readline.h"

#define NAME_LEN 20

typedef struct part {
	int number;
	char name[NAME_LEN + 1];
	int on_hand;
	struct part* next;
}part;


void menu();
part* find_part(part* head, int number);
void insert(part* head);
void search(part* head);
void update(part* head);
void print(part* head);


int main(void) {

	char code = 'a';
	part* head = (part*)malloc(sizeof(part));
	head->next = NULL;

	if (head == NULL) {
		printf("Database establish failed\n");
		exit(EXIT_SUCCESS);
	}

	menu();

	for (;;) {
		printf("Enter operation code: ");
		scanf(" %c", &code);
		while (getchar() != '\n') // skips to end of line
			;
		switch (code) {
		case 'i': insert(head); break;
		case 's': search(head); break;
		case 'u': update(head); break;
		case 'p': print(head); break;
		case 'q': return 0;
		default: printf("Illegal code.\n"); break;
		}
	}




	return 0;
}

void menu() {

	printf("                        ==================================\n");
	printf("                        *                                *\n");
	printf("                        *            i:  insert          *\n");
	printf("                        *            s:  search          *\n");
	printf("                        *            u:  undate          *\n");
	printf("                        *            p:  print           *\n");
	printf("                        *            q:  quit            *\n");
	printf("                        *                                *\n");
	printf("                        ==================================\n");
}


/**********************************************************
*
*	find_part: Looks up a part number in the inventory
*			   array.Returns the array index if the part
*			   number is found;otherwise,return -1
*
***********************************************************/
part* find_part(part* head, int number) {

	part* cur;

	// 链表是按照编号升序排序的
	for (cur = head->next; cur != NULL && cur->number > number;
		cur = cur->next)
		;
	
	if (cur == NULL)
		return NULL;

	if (cur->number == number)
		return cur;

}


/**********************************************************
*
*	insert: Inserts the part into the database.Prints
*		    an error message and returns prematurely
*			if the part already exists or the database
*			is full.
*
***********************************************************/
void insert(part* head) {

	int part_number;
	part* cur, * prev, *new_part;
	

	printf("Enter part number: ");
	scanf("%d", &part_number);
	
	// 寻找 part_number 所应插入的位置，我们需要 cur 遍历链表，但是应该保留 cur 前面的结点 prev 
	// 退出循环条件：cur == NULL 说明是头插或尾插
	//				 cur->number > part_number 说明 输入的编号重复
	//												应该在 cur 和 prev 之间插入新的零件 或 头插
	for (cur = head->next, prev = NULL;cur != NULL && cur->number < part_number ;
		prev = cur, cur = cur->next)
		;
	
	// 判断输入的编号是否于数据库中的现有重复
	if (cur != NULL && cur->number == part_number) {
		printf("Part already exists.\n");
		return;
	}

	// 申请新结点
	new_part = (part*)malloc(sizeof(part));

	// 判断申请是否成功
	if (new_part == NULL) {
		printf("Database is full; can't add more parts.\n");
		return;
	}

	
	new_part->number = part_number;
	printf("Enter part name: ");
	read_line(new_part->name, NAME_LEN);
	printf("Enter quantity on hand: ");
	scanf("%d", &new_part->on_hand);
	
	// 插入的方式：
	// 链表为空时：对 head 进行操作（prev == NULL, cur == NULL）
	// 链表不为空：
	//			  头插：对 head 操作 (prev == NULL, cur != NULL)
	//			  尾插：对 prev 操作 (prev != NULL, cur == NULL)
	//			  普通位置插入：对 prev 操作(prev,cur 都不为 NULL)
	new_part->next = cur;

	if (prev == NULL)
		head->next = new_part;
	else
		prev->next = new_part;

}


/************************************************************
*
*	search: Look up a part by the number user enters.
*			If the part exists, prints the name and quantity
*			on hand;if not, print an error message.
*
************************************************************/
void search(part* head) {

	int number;
	part* trg;

	printf("Enter part number: ");
	scanf("%d", &number);

	trg = find_part(head, number);

	if (trg == NULL) {
		printf("Part not found.\n");
		return;
	}

	printf("Part name: %s\n", trg->name);
	printf("Quantity on hand: %d\n", trg->on_hand);

}


/************************************************************
*
*	update: Prompts user to enter a number.
*			Print an error message if the part doesn't exist;
*			otherwise,prompts the user to enter change in
*			quantity on hand and updates the database.
*
************************************************************/

void update(part* head) {

	int number, change;
	part* trg;

	printf("Enter part number: ");
	scanf("%d", &number);

	trg = find_part(head, number);

	if (trg == NULL) {
		printf("Part not found.\n");
		return;
	}

	printf("Enter change in quantity on hand(- means minus): ");
	scanf("%d", &change);
	trg->on_hand += change;

}


/************************************************************
*
*	print: Print a listing of all parts in the database,
*		   showing the part number,part name and quantity
*		   on hand.Parts are printed in the order in which
*		   they were entered into the database.
*
************************************************************/

void print(part* head) {


	printf("Part Number      Part Name      Quantity on Hand\n");
	for (part* cur = head->next; cur != NULL; cur = cur->next) {
		printf("%6d%20s%15d\n", cur->number, cur->name, cur->on_hand);
	}
}

六指向指针的指针

前面我们使用元素类型为char*的数组，指向数组元素的指针的类型为char**。下面我们以链表的头插为应用场景，帮助大家了解指向指针的指针应该如何应用。

我们知道，链表的头插需要改变头指针。传递给函数的list为头指针（指向首节点的指针），函数返回指向新的首结点的指针。

struct node* add_to_list(struct node* list, int n){
    struct node* new_node;
    
    new_node = malloc(sizeof(struct node));
    if(new_code == NULL){
        printf("Error: mallloc failed in add_to_list.\n");
        exit(EXIT_FAILURE);
    }
    new_node->val = n;
    new_node->next = list;
    return new_node;
}

假如我们将 return 语句删除，然后添加下面的语句：

list = new_node;

可惜的是，这个想法无法实现。假设以此方法调用函数 add_to_list：

add_to_list(first, 10);

在调用点，会把 first 复制给 list 。（像所有其他参数一样，指针也是按值传递的。）函数最后一行改变了 list 的值，使它指向了新的结点。但是此复制操作对 first 没有影响。

让函数修改 first 是可能的，但是需要给函数 add_to_first 传递一个指向 first 的指针。下面是函数的正确形式：

void add_to_list(struct node** list, int n){
    struct node* new_node;
    
    new_node = malloc(sizeof(struct node));
    if(new_code == NULL){
        printf("Error: mallloc failed in add_to_list.\n");
        exit(EXIT_FAILURE);
    }
    new_node->val = n;
    new_node->next = *list;
	
    *list = new_node;
}

调用此函数，第一个实参为 first 的地址：

add_to_list(&first, 10);

使用*list作为 first 的别名，修改它是可以改变 first 的内容的。

七指向函数的指针

指向函数的指针（函数指针），不像人们想的那么奇怪。毕竟函数占用内存单元，所以每个函数都有地址，就像每个变量都有地址一样。

[^1]: 没有影响你思考编程的语言不值得学。Epigrams on Programming 编程警句

参考资料：《C语言程序设计：现代方法》

指针的高级应用

目录

指针的高级应用

零 前言

一 动态存储分配

0. 内存分配函数

1. 空指针

二 动态分配字符串

0. 使用 malloc 函数为字符串分配内存

1. 在字符串函数中使用动态存储分配

3. 动态分配字符串的数组

程序：显示一个月的提醒列表

三 动态分配数组

0. 使用 malloc 函数为数组分配存储空间

1. calloc 函数

2. realloc 函数

四 释放存储空间

0. free函数

1. “悬空指针”问题

五 链表

程序：维护零件数据库

六 指向指针的指针

七 指向函数的指针

零前言

一动态存储分配

二动态分配字符串

三动态分配数组

1. `calloc` 函数

2. `realloc` 函数

四释放存储空间

0. `free`函数

五链表

六指向指针的指针

七指向函数的指针