计算机二级辅导：链表的c语言实现

准备:动态内存分配

1.为什么我们要使用动态内存分配
？当我们还没有学会链表的时候，如果要存储大量相同类型或结构的数据，我们总是使用数组。比如我们要存储某一科某一班学生的分数，我们总是定义一个float数组(0.5分):
float score[30]；
但是，在使用数组的时候，总有一个问题困扰着我们:数组应该有多大？
在许多情况下，您不确定要使用多大的数组。例如，在上面的示例中，您可能不知道班上的学生人数，因此您应该将数组定义为足够大。这样，当你的程序运行时，它申请的是你认为足够大的固定大小的内存空。即使知道班级人数，如果因为某种特殊原因，学生人数增加或减少，就必须再次修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称为静态内存分配。但这种内存分配方式存在严重缺陷，尤其是在处理一些问题时:多数情况下会浪费大量内存空，少数情况下当你定义的数组不够大时，可能会造成下标越界错误，甚至导致严重后果。【/br/】那么，这样的异物有没有其他的解决方法呢？没错，就是动态内存分配。
所谓动态内存分配，是指程序执行过程中，在存储空之间动态分配或回收内存的方法。与数组等静态内存分配方式不同，动态内存分配需要预先分配内存空，而是由系统根据程序的需要立即分配，分配的大小就是程序要求的大小。对比上面的动态和静态内存分配，可以知道动态内存分配相对于景泰内存分配的特点:
1。不需要预分配内存空；
2。分配的空房间可以根据节目需要扩大或缩小。

二。如何实现动态内存分配及其管理
要根据程序的需要动态分配内存空，必须使用以下函数
1。malloc函数
Malloc函数的原型是:
void * Malloc(unsigned int size)[/它的参数是一个无符号整数，它的返回值是一个指针，指向所分配的连续存储域的起始地址。另外需要注意的是，当函数分配存储空失败时(比如内存不足)，会返回一个空指针。所以在调用这个函数时，要检查返回值是否为NULL，并执行相应的操作。
下面的例子是一个动态分配的程序:
# include
# include
main()
{
int count，* array/*count是计数器，array是整数指针，也可以理解为指向整数数组的第一个地址*/
if((array(int *)malloc(10 * sizeof(int)))= = null)
{
printf("不能")；
退出(1)；
}
for(count = 0；计数〈10；Count++) /*将值赋给array */
array[count]= count；
for(count = 0；计数〈10；Count++) /*打印数组元素*/
printf ("-"，array[count])；
}
在上面的例子中，10个整数存储区被动态分配，然后被赋值和打印。例中if((array(int *)malloc(10 * sizeof(int)))= = NULL)语句可分为以下步骤:
1)在连续存储间分配10个整数空，返回一个指向其起始地址的整数指针
2)将这个整数指针地址赋给数组
3)检查返回值是否为NULL
2 .free function
因为内存区域总是有限的，不能无限制的分配，一个程序要尽量节约资源，所以当分配的内存区域没有使用时，就要释放。这时候我们就要用free函数了。
其函数原型为:
void free(void *p)
用于释放指针p所指向的内存区域，
其参数p必须是之前调用malloc函数或calloc函数(另一个动态分配存储区域的函数)时返回的指针。将其他值传递给free函数可能会导致崩溃或其他灾难性的后果。
注意:这里重要的是指针的值，而不是用来申请动态内存的指针本身。例如:
int *p1，* p2
P1 = malloc(10 * sizeof(int))；
p2 = P1；
...
free (p2)/*或free(p2)*/
malloc返回值赋给p1，p1的值赋给p2，所以p1和p2都可以作为free函数的参数。
malloc函数分配存储区域。
free函数释放未使用的内存区域。
所以这两个函数可以实现内存区域的动态分配和简单管理。一、单链表的建立
有了动态内存分配的基础，实现链表并不难。
所谓链表，就是用一组任意的存储单元来存储线性表元素的数据结构。
链表分为单链表、双链表和循环链表。先说单链表。
所谓单链表，是指数据接点按一个方向排列。单个链表节点有两种结构类型:
1。数据字段:用于存储自己的数据
2。链字段或指针字段:用于存储下一个节点的地址或指向其直接后继节点的指针。
示例:
typedef结构节点
{
charname[20]；
struct node * link；
}梭哈；
这定义了一个单链表的结构，其中char name[20]是一个用来存储名字的字符数组，pointer *link是一个用来存储其直接后继的指针。
定义好链表的结构后，程序运行时只要在love data字段中存储合适的数据，如果有后继节点，那么chain字段就会指向它的直接后继，否则就会设置为NULL。
我们来看一个完整的建立带表头的单链表的过程(除非特别说明，下面提到的链表都是有表头的)。
#include
#include /*包含动态内存分配函数的头文件*/
#define N 10 /*N是人数*/
typedef结构节点
{
charname[20]；
struct node * link；
}梭哈；
stud * creat(int n) /*构建单链表的函数，其中形参n为人数*/
{
stud *p，*h，* s；/* *h保存头节点的指针，*p指向当前节点的上一个节点，*s指向当前节点*/
int I；/* counter */
if((h =(stud *)malloc(sizeof(stud)))= = null)/* allocate空and detect */
{
printf("无法分配内存)；
退出(0)；
}
h--> name[0]= ' \ 0 '；/*将表头节点的数据字段设置为空*/
h-> link = NULL；/*设置头节点的链域为空*/
p = h；/*p指向头节点*/
for(I = 0；I {
if((s =(stud *)malloc(sizeof(stud)))= = null)/*分配新存储空和check */
{
printf("无法分配内存/[)；
退出(0)；
}
p-> link = s；/*将S的地址赋给P所指向的节点的链域，从而连接P和S所指向的节点*/
printf("请输入%d人的名字"，I+1)；
scanf("%s "，s-> name)；/*在当前节点的数据字段中存储name */
S--> link = NULL；
p = s；
}
return(h)；
}

main()
{
int number；/*被救人数的变量*/
stud * head；/*head是指向单链表头节点地址的指针*/
number = N；
head = creat(number)；/*将新创建的单链表头地址分配给head*/
}

这样就写出了一个包含n个名字的单链表。
写动态内存分配的程序要注意。请尝试检查分配是否成功。