7 用指针处理链表
7.1 链表概述
链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。
链表有一个 头指针 变量，它存放一个地址，该地址指向一个元素，链表中每一个元素称为 结点，每个结点都应包括两个部分，一为用户需要用的实际数据，二为下一个结点的地址。可以看出，头指针 head 指向第一个元素，第一个元素又指向第二个元素，。。。。直到最后一个元素，该元素不再指向其他元素，它称为 表尾，它的地址部分放一个
NULL（表示 空地址）链表到此结束。
可以看到链表中各元素在内存中可以不是连续存放的，要找某一元素，必须先找到上一个元素，根据它提供的下一元素地址才能找到下一个元素。如果不提供 头指针 head 则整个链表无法访问。
可以看到。这种链表的数据结构，必须利用指针变量才能实现，即一个结点中应包含一个指针变量，用它存放下一结点的地址。
前面介绍了结构体变量，用它作链表中的结点是最合适的，一个结构体变量包含若干成员，这些成员可以是数值类型，字符类型，数组类型，也可以是指针类型，我们用这个指针类型成员来存放下一个结点的地址。例如可以设计这样一个结构体类型：
struct student
{
int num;
float score;
struct student *next;
};
其中成员 num 和 score 用来存放结点中的有用数据（用户需要用到的数据），next 是指针类型成员，它指向 struct student 类型数据（这是 next 所在结构体类型）。一个指针类型的成员既可以指向其他类型的结构体数据，也可以指向自己所在的结构体类型的数据。现在 next 是 struct
student 类型中的一个成员，它又指向 struct student 类型的数据。用这种方法就可以建立链表。
请注意：只是定义一个 struct student 类型，并未实际分配存储空间，只有定义了变量才分配内存单元。
7.2 简单链表
下面通过一个例子来说明如何建立和输出一个简单链表
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
struct student
{
long num;
float score;
struct student *next;
};
void main()
{
struct student a, b, c, *head, *p;
a.num = 99101; a.score = 89.5;
b.num = 99103; b.score = 90;
c.num = 99107; c.score = 85;//对结点的 num 和 score 成员赋值
head = &a;//将结点 a 的起始地址赋给头指针 head
a.next = &b;//将结点 b 的起始地址赋给 a 结点的 next 成员
b.next = &c;
c.next = NULL;// c 结点的 next 成员不存放其他结点地址
p = head;//使 p 指针指向 a 结点
do
{
printf("%ld %5.1f\n", p->num, p->score);// 输出 p 指向的结点的数据
p = p->next;//使 p 指向下一结点
}while(p != NULL);//输出完 c 结点后 p 的值为 NULL
system("pause");
}
运行结果
99101 89.5
99103 90.0
99107 85.0
7.3 处理动态链表所需的函数
（1）malloc 函数
void *malloc(unsigned int size);
作用是在内存的动态存储区中分配一个长度为 size 的连接空间。些函数的值（即返回值）是一个指向分配空间起始地址的指针（基类型为 void）。如果些函数未能成功地执行（例如内存空间不足）则返回空指针 NULL。
（2）calloc 函数
void *calloc(unsigned n, unsigned size);
其作用是在内存的动态区存储中分配 n 个长度为 size 的连续空间。函数返回一个指向分配空间起始地址的指针，如果分配不成功，返回 NULL。
用 calloc 函数可以为一维数组开辟动态存储空间， n 为数组元素个数，每个元素长度为 size。
（3）free 函数
void free(void *p);
其作用是释放由 p 指向的内存区，使这部分内存区能被其它变量使用， p 是最后一次调用 calloc 或 malloc 函数时返回的值。free 函数无返回值。
请注意：以前的C版本提供的 malloc 和 calloc 函数得到的是指向字符型数据的指针。ANSI C 提供的 malloc 和 calloc 函数规定为 void * 类型。
7.4 建立动态链表
所谓建立动态链表是指在程序执行过程中从无到有地建立起一个键表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
long num;
float score;
struct student *next;
};
struct student *create()
{
struct student *p1, *p2, *head;
int num;
float score;
int n = 0;
head = NULL;
p1 = p2 = (struct student *)malloc(LEN);
printf("please input num and score.\n");
scanf("%d,%f", &p1->num, &p1->score);
while(p1->num != 0)
{
n ++;
if(n == 1)
head = p1;
else
p2->next = p1;
p2 = p1;
p1 = (struct student *)malloc(sizeof(struct student));
printf("please input num and score.\n");
scanf("%d,%f", &p1->num, &p1->score);
}
p2->next = NULL;
return head;
}
void printlist(struct student *head)
{
struct student *p;
p = head;
if(head != NULL)
{
do
{
printf("num=%d score=%f\n", p->num, p->score);
p = p->next;
}while(p != NULL);
}
}
void main()
{
struct student *head;
head = create();
printlist(head);
system("pause");
}
以下是对链表的各种操作
打印链表
void printlist(struct student *head)
{
struct student *p;
p = head;
if(head != NULL)
{
do
{
printf("num=%d score=%5.2f\n", p->num, p->score);
p = p->next;
} while (p != NULL);
}
/* while(p -> next != NULL)
{
printf("num=%d score=%f\n", p->num, p->score);
p = p->next;
}*/
}
删除节点
struct student *delNode(struct student *head, int num)
{
printf("delNode.\n");
struct student *p1, *p2;
if(head == NULL)
{
printf("The List is NULL.\n");
}
else
{
p1 = head;
while(p1->next != NULL && p1->num != num)
{
p2 = p1;
p1 = p1->next;
}
if(p1->num == num)
{
if(p1 == head)
head = p1->next;
else
p2->next = p1->next;
}
else
printf("Can not find list num.\n");
}
return head;
}
更新节点
struct student *update(struct student *head, int index, int num, float score)
{
printf("update.\n");
struct student *p;
if(head == NULL)
{
printf("The List is NULL.\n");
}
else
{
p = head;
while(p->next != NULL && p->num != index)
{
p = p->next;
}
if(p->num == index)
{
p->num = num;
p->score = score;
}
else
printf("Can not find list index.\n");
}
return head;
}
增加节点
struct student *add(struct student *head, int index, int num, float score)
{
printf("add.\n");
struct student *p1, *p2, *p3;
if(head == NULL)
{
printf("The List is NULL.\n");
}
else
{
p1 = p2 = head;
while(p1->next != NULL && p1->num != index)
{
p1 = p1->next;
p2 = p1;
}
if(p1->num == index)
{
p3 = (struct student *)malloc(LEN);
p3->num = num;
p3->score = score;
if(p2->next == NULL)
{
p2->next = p3;
p3->next = NULL;
}
else
{
p3->next = p2->next;
p2->next = p3;
}
}
else
printf("Can not find list index.\n");
}
return head;
}