1.什么是链表？

        链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。由前面的学习中已知：用数组存放数据时,必须事先定义固定的数组长度(即元素个数)。如果有的班级有 100 人,而有的班级只有 30 人,若用同一个数组先后存放不同班级的学生数据,则必顺定义长度为 100 的数组。如果事先难以确定一个班的最多人数,则必须把数组定得足够大,以便能存放任何班级的学生数据,显然这将会浪费内存。链表则没有这种缺点,它根据需要开辟内存单元。

        链表有一个“头指针”变量,图中以 head 表示,它存放一个地址,该地址指向一个元素。链表中每一个元素称为“结点”,每个结点都应包括两个部分；(1)用户需要用的实际数据；(2)下一个结点的地址。可以看出,head 指向第 1 个元素,第1个元素又指向第 2 .个元素……直到最后一个元素,该元素不再指向其他元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。

        可以看到链表中各元素在内存中的地址可以是不连续的。要找某一元素,必须先找到上一个元素,根据它提供的下一元素地址才能找到下一个元素。如果不提供“头指针”(head),则整个链表都无法访问。链表如同一条铁链一样,一环扣一环,中间是不能断开的。

        为了理解什么是链表,打一个通俗的比方:幼儿园的老师带领孩子出来散步,老师牵着第1个小孩的手,第 1 个小孩的另一只手牵着第 2 个孩子……这就是一个“链”,最后一个孩子有一只手空着,他是“链尾”。要找这个队伍,必须先找到老师,然后顺序找到每一个孩子。
        显然,链表这种数据结构,必须利用指针变量才能实现,即一个结点中应包含一个指针变量,用它存放下一结点的地址。前面介绍了结构体变量,用它去建立链表是最合适的。一个结构体变量包含若干成员，这些成员可以是数值类型，字符类型，数组类型，也可以是指针类型。用指针类型成员来存放下一个节点的地址。例如，可以设置这样一个结构体类型：

struct Student
{
	int num;
	float score;
	struct Student *next;          //next是指针变量，指向结构体变量 
}; 

其中，成员num和score是用来存放用户需要的数据的，next是指针类型的成员，它既可以指向其他类型的结构体数据，也可以指向自己所在的结构体类型的数据。

注意：上面只是定义了一个结构体数据类型，并未实际分配存储空间，只有定义了变量才分配存储空间。

2.建立简单的静态链表

【例题】建立一个简单的链表，它由3个学生数据的结点组成，要求输出各组结点中的数据。

#include<stdio.h>
#include<string.h>
struct Student
{
	int num;
	float score;
	struct Student *next;
};
int main()
{
	struct Student a,b,c,*head,*p;
	a.num=101;
	a.score=89.5;
	b.num=103;
	b.score=90;
	c.num=107;
	c.score=85;
	head=&a;
	a.next=&b;
	b.next=&c;
	c.next=NULL;
	p=head;
	do{
		printf("%1d %5.1f\n",p->num,p->score);
		p=p->next;
	}while(p!=NULL);
	return 0;
}