学习目标

1.学习用指针实现动态分配内存的方法，掌握动态分配内存库函数；
2.学习指向结构的指针，初步掌握链表数据结构概念并实现链表的基本操作。

1.1 动态内存分配

引子

（1）静态内存分配：固定大小的内存分配。
（2）动态内存分配：在程序执行过程中动态地分配或回收储存空间的内存分配方法。动态内存分配不需要预先分配固定的内存空间，而是在运行时根据程序需要分配内存，或者释放不在需要的空间，因而可以优化存储空间的使用。
! ! 思考：如果需要存储多个同类型或者同结构的数据时，我们会想到用一个数组来存储。而数组到底应该有多大？大多数情况下，我们不能确定数组的大小，所以我们只好把数组定义的足够大！当时对于实际情况而言，数据有可能会增多或者减少。我们需要依据实际情况来修改程序，这样就有了动态内存分配。！！
（3）静态内存分配与动态内存分配的特点：
①动态内存分配是在运行时候完成的，根据程序的需要进行内存分配的释放，属于按需分配，内存的分配与释放需要占用CPU资源；而静态内存分配是编译的时完成的，需要在编译前确定内存块的大小，属于按计划分配，不需要占用CPU资源。
②动态内存分配需要指针或引用数据类型的支持，而静态内存分配不需要。
③动态内存分配是把内存的控制权交给了程序员，而静态内存分配则是内存的控制权交给了编译器。

1.1动态分配内存函数

四个内存管理库函数，定义在stdlib.h头文件中。

1.2malloc函数

函数原型：

void * malloc(unsinged size)

功能：在内存的动态内存分配size个字节的连续的存储空间。
返回值：返回一个空指针，指向所分配存储空间的起始地址。如果该函数执行失败（如：由于空间不足等原因），则返回空指针NULL。
说明：
（1）由于所申请的内存空间的数据类型没有确定，malloc函数将返回void类型的指针。在使用该函数时，需要用强制类型转化函数返回的地址转化成所需类型。例如：

int*p；
p=(int *)malloc(100 *sizeof(int));

该语句成功运行后，将分配一个大小为100个int类型的内存空间，该内存块的首地址将赋值给int类型的指针p。
malloc函数常被用来为结构体之类的复杂数据类型分配存储空间。例如：

struct student *p;
p=(struct student *)malloc(sizeof(struct student));

(2)malloc 函数分配的是连续的存储空间，如果空间无法满足分配的需求，则分配失败。此时，malloc函数返回空指针NULL。因此在使用内存指针之前，应当检查内存分配是否成功。例如：

if((p=(int *)malloc(100 *sizeof(int))==NULL)
{
printf(“No space available.\n”);
exit(1);
}

exit函数的原型为：

void exit(int state)

exit函数功能是关闭所有文件和缓冲区，并中止程序的执行，返回调用的过程。参数state的值为0的时候，说明程序正常中止，state的值非零的时候，说明程序异常中止。exit函数也被定义在stdlib.h头文件中。

1.3 calloc 函数

函数原型：

void * calloc (unsinged n,unsigned size)

功能：在内存的动态存储区中分配n个长度为size个字节的连续的存储空间。
返回值：返回一个空类型的指针，指向所分配储存空间的起始地址。如果该函数执行失败，则返回空指针NULL。
说明：和malloc函数差不多一样，主要差别在函数的参数的不同，其它功能一样！

1.4 realloc函数

函数原型：

void * realloc (void * p,unsigned size)

功能：为指针p重新分配size个字节的新的连续的储存空间。
返回值：返回一个空类型的指针，指向重新分配的储存空间的起始地址。如果函数执行失败，则返回空指针NULL。
强调：当调用realloc函数时，p必须指向内存块，且该内存块一定是之前通过malloc函数或calloc函数分配的。size表示内存块的新长度，该长度可能会大于或小于原有的内存块长度。
说明：（1）当扩展内存块时，realloc函数不会对新增加的内存块的字节进行初始化。
（2）如果realloc函数不能按要求扩大内存块，那么它会返回空指针，并且在原有的内存块中的数据不会发生改变。
（3）如果realloc函数调用时以空指针作为第一个实参，那么它与malloc函数的功能一样。
（4）如果realloc函数调用时以作为第二个实参，那么它会释放内存块。

1.5 free函数

函数原型：

void free（void *p）

功能：释放由malloc()、calloc()、realloc分配的内存空间，p指向所释放内存空间的地址。
说明：free函数在调用中，如果发现使用了非法的指针，可能产生问题甚至引起系统崩溃。
要注意的是：
（1）函数所释放的不是指针本身，而是指针所指向的内存空间。
（2）要释放由realloc函数分配的多个连续的内存块，只需要释放一次即可。试图释放每个内存块是错误的。
注意！：在c语言中，动态分配的内存在使用结束后，必须使用free函数将其释放掉。这是因为动态内存分配的内存都是来自一个称为“堆”的存储池。如果在程序执行结束前没有使用free函数释放这块动态分配的内存，该内存将永远的不到释放，所以后再也不能使用此块内存块了。长期这样，堆中的内存将耗尽，如果内存耗尽的话，再使用malloc函数时，将返回空指针。

1.6 动态内存编程实例

1. 动态分配内存空间

//编写一个程序，读入由用户指定个数的整数，然后逆序输出这些数值。

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

int main()
{
	//输入有几个整数
	int size;
	printf("请输入有几个整数：");
	scanf("%d", &size);
	//分配内存空间
	int *table = NULL;
	if ((table = (int *)malloc(size*sizeof(int))) == NULL)
	{
		printf("No space available.\n");
		exit(1);
	}
	//输入size个整数的值
	int *p = table;//用p来操作，保证table指向的地址不变，以便后面的释放内存空间
	printf("请输入%d个整数:",size);
	for (p=table; p < table + size; p++)
	{
		scanf("%d", p);
	}
	//逆序输出这些整数
	for (p = table + size - 1; p >= table; p--)
	{
		printf("%d的存储地址是:%p\n", *p, p);
	}
	//释放分配的内存空间
	free(table);
	return 0;
}

2. 释放动态分配的内存空间

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

int main()
{
	struct student
	{
		int sNo;
		char *name;
		char sex;
	} *p;
	p = (struct student *)malloc(sizeof(struct student));
	p->sNo = 101;
	p->name = "John";
	p->sex = 'M';
	printf("%d\t%s\t%c\n", p->sNo, p->name, p->sex);
	free(p);
	return 0;
}

注意：释放内存空间很重要！

3.改变动态分配的内存空间大小

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

int main()
{
	char *str=NULL;
	//第一次分配10个字节的内存空间
	if ((str = (char *)malloc(10)) == NULL)
	{
		printf("No space available.\n");
		exit(1);
	}
	strcpy(str, "hello!");
	printf("string:%s\n", str);
	//第二次分配20个字节的内存空间
	if ((str = (char *)realloc(str, 20)) == NULL)
	{
		printf("Reallocation failed.\n");
		exit(1);
	}
	strcpy(str, "Hello world!");
	printf("new string:%s\n", str);
	//释放内存空间
	free(str);
	return 0;
}

1模块小总结

注意：一定要记得释放申请的动态内空间，最好写代码的时，申请动态空间后，写上释放空间的代码，且要保持指向该动态内存空间内存的指向别再发生改变，可以加上 const语句！！

1.2链表

引子

当我们存放一组相同数据时，经常使用数组。但是使用数组描述一些数据的时候，在操作上有些不方便。比如：我们要用数组存放一个班的信息，由于每个班的人数不同，我们就必须按照最大数量来定义一个数组，这样经常浪费内存空间。如果在数组中，学生按照学号升序存放，当要删除一个学生，或增加一个学生的时候，有时候需要调整很多元素在数组中的位置。这时候我们就可使用另一种结构——链表。

链表中的每个元素称为一个“结点”，每个结点有都包括两个部分：
（1）所需的实际数据，例如一个学生的信息，包括学号，姓名，性别等；
（2）一个指针变量，用来指向下一个结点。
链表就是通过这样的指针变量形成“链”的。最后一个结点所包含的指针变量应当指向空地址“NULL”，以表示链表的结束。

2.1链表结点结构

链表的每个结点各是一个结构体变量，在内存中的存放是可以不连续，在链表中的顺序也不是由物理地址所决定的，而是由逻辑链接所确定。结构的结构表示如下：

struct node
{
type member1;
type member2;
……
struct node * next;
}

这个结构中有一个很重要的成员，就是指针next，它用来指向下一个结点。因为存放的是下一个结点的起始地址，所以这个指针就是指向想同类型的指针，这种结构称为自引用结构。
注意：由于链表中的每个结点都是通过上一个结点中的指针成员“链接”起来的，所以想要找到链表中的某个节点，必须通过上一个结点中的指针变量来访问。因此链表必须有具有一个头指针“head”，指向链表的第一个结点。如果没有头指针，整个链表都无法访问！

2.2 建立和输出静态链表

我们可以把链表看作一个抽象的数据结构，下面通过一个简单的例子，来看看链表是如何被创建和访问的。

//创建和输出一个简单的链表

#include<stdio.h>
#include<string.h>
struct student
{
	int num;
	char name[20];
	struct student * next;
};
int main()
{
	//声明和初始化三个学生的信息
	struct student s1, s2, s3;
	s1.num = 1001;
	strcpy(s1.name, "Jack");
	s2.num = 1002;
	strcpy(s2.name, "Liza");
	s3.num = 1003;
	strcpy(s3.name, "Ann");
	//实现链表
	struct student *head;
	head = &s1;
	s1.next = &s2;
	s2.next = &s3;
	s3.next = NULL;
	//访问并输出链表
	struct student *p = head;
	while(p != NULL)
	{
		printf("%d\t%s\n", p->num, p->name);
		p = p->next;
	}
	return 0;
}

本例中，所有的结点都是在程序中被静态声明的，而不是动态分配的，用完之后也不能被释放，这种链表叫做“静态链表”。

2.3建立和输出动态链表

接下来，我们来建立动态链表，也就是在程序的执行过程中，逐个生成结点，通过结点中的指针成员建立起一条“链”。

//创建和输出和一个简单的动态链表

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

//定义一个学生信息结点
struct student
{
	int sNo;
	char name[20];
	struct student * next;
};

//创建动态链表的函数实现。返回动态链表头地址
struct student * create()
{
	struct student *head;//用来存头指针并用来返回的
	struct student *p;//用来创建动态链表的
	int sNo;//用来判断是否生成结点的
	printf("请输入学号（输入0退出）:");
	scanf("%d", &sNo);
	//进行判断
	if (sNo == 0)
	{
		return NULL;
	}
	//开始动态分配储存空间
	if ((p = (struct student *)malloc(sizeof(struct student))) == NULL)
	{
		printf("No space available.\n");
		exit(1);
	}
	head = p;
	do
	{
		//分配空间成功的时候才开始存入学生信息
		p->sNo = sNo;
		printf("请输入学生姓名：");
		scanf("%s", p->name);
		//当一个学生信息储存完毕的时候，开始创建下一个结点
		printf("请输入学号（输入0退出）：");
		scanf("%d", &sNo);
		//对结点中的指针变量赋值
		//判断
		if (sNo == 0)
		{
			p->next = NULL;//设置链表结束标志
			return head;
		}
		else
		{
			//为前一个结点中的指针变量分配动态内存
			if ((p->next = (struct student *)malloc(sizeof(struct student))) == NULL)
			{
				printf("No space available.\n");
				exit(1);
			}
			p = p->next;//让p指向下一个结点
		}
	} while (1);
}
//输出链表函数的实现
void print(struct student * head)
{
	struct student *p = head;
	while (p != NULL)
	{
		printf("%d\t%s\n", p->sNo, p->name);
		p = p->next;
	}
}
int main()
{
	struct student *head;
	head = create();
	print(head);
	return 0;
}

程序说明：
（1）在本例中，create函数用来创建一个链表，返回指向链表头的指针。函数中声明了两个struct student的类型指针p和head分别用来指向新分配的结点和链表头。
在create函数的开始，语句：

if ((p = (struct student *)malloc(sizeof(struct student))) == NULL)

在内存中动态分配了链表的第一个结点空间，p指向该新建立的结点，head也指向该结点。
新的结点建立后，create函数要求用户输入学生的学号，如果用户输入学号为0，表示该链表为空，也就是没有任何结点，于是返回了空地址NULL，这样，该链表的头指针不指向任何内存单元，也就是链表没有结点。
如果用户输入的学号不为0，则用一个do……while循环，反复的生成新的结点，读入新数据。
语句：

if ((p->next = (struct student *)malloc(sizeof(struct student))) == NULL)

使得当前结点的next成员指向一个新分配的结点，链表就是这样得以延伸的。当前用户输入的学号为0，语句：

p->next = NULL;

使得当前结点的next成员指向空地址NULL，到此链表结束。函数返回头指针head指针的值，head指向的是向的是新生成的链表的第一个结点。
（2）print（）函数用来输出一个链表，它有一个参数head，它是一个struct student类型的指针。print函数输出head指向的链表，指针p用来指向当前要输出的结点，输出当前结点的数据后，语句：

p = p->next;

使指针p指向下一个结点。如此反复，直到p指向下一个空地址NULL的时候为止。

2.4 删除链表中的结点

如果想要删除带结点，只要使指向该结点的指针，指向下一个结点即可。
例题：

//编写一个函数，删除一个指定学号的学生结点
struct student * deletenode(struct student * head, int num)//函数要有表头的地址，删除的学号
{
	struct student *p1, *p2 = head;//用p2遍历整个链表，p1来实现删除功能
	//链表有两种情况，空表或非空
	if (head == NULL)
	{
		printf("List is null!\n");
	}
	else
	{
		//寻找特定的学号的结点
		while (p2->num != num&&p2-> != NULL)
		{
			p1 = p2;
			p2 = p2->next;
		}
		/*循环结束有三种情况：
		（1）没有找到特定的结点。
		（2）找到了需要删除的结点，并且该结点是链表的第一个结点
		（3）找到了需要删除的结点，该结点并不是链表的第一个结点
		*/
		if (p2->num == num)
		{
			if (p2 = head)
			{
				p1 = p2->next;
				free(head);//释放该结点所占的空间
				return p1;
			}
			else
			{
				p1->next = p2->next;
				free(p2);
			}
		}
		else//没有找到需要删除的结点
		{
			printf("Stuent number %d not been found!\n", num);
		}
	}
	return head;
}

2.5 在链表中插入结点

插入结点有如下三种情况
（1）将结点new插入到表头的最前面，也就是作为表头的第一个结点，此时只需要使得new的next成员指向链表头的结点，然后使原链表的头指针head指向new即可。
（2）将新结点new插入到两个节点之间（假设插入到结点1之后，结点2之前），此时只需要将new的next成员指向结点2，将结点1的next成员指向new即可。
（3）将新结点插入链表的结尾，只需要将原表头的最后一个结点的next成员指向new，new中next指向空指针NULL即可。

例1

//编写一个函数将一个新的结点插入到指定结点（称为关键结点）之前。如果未找到关键结点，则将新的结点插入到链表的末尾

struct student * insertnode(struct student * head)
{
	//生成新的结点
	struct student *new;
	if ((new = (struct student *)malloc(sizeof(struct student))) == NULL)
	{
		printf("No space available.\n");
		exit(0);
	}
	//对新的结点进行数据输入
	printf("Input the new student number:");
	scanf("%d", &new->num);
	printf("Input the new student name:");
	scanf("%s", new->name);
	//设置关键结点（学生的学号）
	int key;
	scanf("%d", &key);
	//寻找关键结点
	struct student *p = head, *q;//q,p为两个相连的结点
	while (p != NULL)
	{
		if (p->num == key)
			break;
		else
		{
			q = p;
			p = p->next;
		}
	}
	//关键的结点为表头
	if (p == head)
	{
		new->next = head;
		return new;
	}
	//未找到关键结点，将new加入链表的末尾
	else if (p == NULL)
	{
		q->next = new;
		new->next - NULL;
	}
	//找到了关键结点
	else
	{
		q->next = new;
		new->next = p;
	}
	return head;
}

注意：在使用链表的时候，注意最后一个结点的next成员应当设置为指向空地址NULL，否则会引起逻辑错误！

2.6 链表的扩展应用

链表的概念对于很多抽象数据类型（如队列、栈和树）的建模很有用处。
如果只规定一个链表只能从一端插入结点，另一端删除结点，就得到了队列的模型。换句话说，队列只能从末端插入数据，从前端删除数据，所以先加入的结点将最先被删除，这叫作“先进先出(FIFO)”原则。
如果规定一个链表只能从一端插入和删除结点，就得到了栈的模型。换句话说，栈只能从前端插入和删除数据，所以最后加入的结点最先被删除，这就叫做“先进后出（LIFO）”原则，因此栈也称为下压链表。
链表、队列和栈本质上都是一维的链表。
树表示的则是二维链表。

总结

本章主要讲述的是指针的高级应用。
（1）动态内存分配是在程序执行的过程中动态分配或回收储存空间的内存分配方法。c语言本身并不具备对内存进行动态管理的能力，而是通过4个内存管理库函数（malloc、calloc、realloc和free）来实现内存的动态分配和释放的，这些函数被定义在stdlib.h头文件中。
（2）在使用malloc、calloc和realloc函数分配存储空间是，要考虑所申请的连续的内存空间有可能会分配失败，此时，malloc函数返回空指针NULL。因此在使用指针内存指针之前，应当检查内存分配是否成功！
（3）如果动态分配的空间不在需要，应该运用free来释放该空间。在内存释放后，如果还继续使用指向这片空间的指针是错误的。
（4）不要释放由calloc创建数组的单个元素——只能从首元素地址开始释放内存。
（5）对于数组元素的个数或元素排放经常变更的情况来讲，我们可以采用链表结构，可以对链表进行生成、插入和删除。
（6）链表分为静态和动态两种结构：静态链表的所有的结点都是在程序中静态声明的，用完之后不能释放；动态链表是在程序执行过程中，逐个生成结点，通过结点中的指针成员建立一条“链”。
（7）在使用链表的时候，注意最后一个节点的next成员应当设置为空地址NULL，否则会引起逻辑错误！