一，链表的定义
链表是一种常见的采用动态存储分配方式的数据结构。在链表中，有一个头指针变量，用这个指针保存一个地址，头指针指向一个变量，这个变量称为元素。链表中，每一个元素包括两部分：数据部分和指针部分。数据部分用来存放元素中包含的数据，指针部分用来指向下一个元素 。（最后一个元素指向NULL）
在链表中，第一个结点前虚假一个头结点，头指针指向头结点，头结点的指针域指向第一个实际有效结点，该节点可以称为首元结点。
确定一个链表需要一个参数：头指针，通过头指针可以推算出链表其他所有的参数
二，单链表
链表中，每个结点只有一个指针，所有指针都是单线联系，除了末尾结点指针为空外，每个结点的指针都指向下一个结点，一环扣一环。
单链表的特点：
1）有一个head指针变量，存放头结点地址，称为头指针。
2）头结点的指针域head->next，存放首元结点（第一个实际有效结点）的地址。
3）数据域存放用户需要的实际数据，指针域存放下一个结点的地址。
4）链表的使用，可以使程序的内存利用率和时间效率大大提高。
5）链表各结点间顺序由指针域next来确定
1.单链表的初始化
由于链表的每个结点都包含数据域和指针域，即每个结点都要包含不同的数据类型，所以结点的数据类型必须选用结构体类型。其中必须有一个成员的类型是指向本结构体的指针类型。
对于这种结构体类型，C语言允许递归递归定义。例如定义一个链表表示一个班级，其中每一个结点表示一位学生，他的结构体类型如下：
typedef struct node{
char name[20];//姓名
int number;//学号
struct node *next;//next的类型是指向本结构体数据类型的指针类型
}Node,*LinkList;
Node是结构体类型，LinkList是结构体指针类型。LinkList head 相当于 Node *head,也相当于struct node *head。在 next 成员定义中，引用了本结构体类型，也就是说类型定义中采用了递归。
单链表的初始化就是创建一个头结点，若头结点的指针域为空，表示空单链表。单链表初始化代码如下：
LinkList InitList()
{
LinkList head;//定义头指针变量
head = (Node*)malloc(sizeof(Node));//头指针指向分配的头结点内存空间
head->next=NULL;//头指针指针域为空
return head;//返回头结点地址，即头指针
}2.单链表的建立
单链表的建立就是在程序运行过程中，从无到有的建立一个链表，即一个一个分配结点的内存空间，然后输入结点中的数据，并建立结点间的相连关系。单链表的建立分为尾插法和头插法。
1）尾插法建立单链表
从第一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾，直至读入结束标志为止。由于每次插入的新结点都插入到链表表尾，所以增加一个指针 r 来始终指向链表的最后一个结点，以便新结点的插入。尾插法创建单链表代码如下：
void CreatByRear(LinkList head)
{
Node *r,*s;//s指向新创建的结点
char name[20];
int number;
r = head;//r指向头结点 ，即当前单链表的尾结点
printf ("请输入学生姓名和学号：\n");
while(1)
{
scanf ("%s",name);
scanf ("%d",&number);
if (number==0)
break;
s = (Node*)malloc(sizeof(Node));//分配结点的内存空间 ，令s指向新分配的内存
//分别赋值姓名和学号
strcpy(s->name ,name);
s->number = number;
r->next = s;//原来的结点指向新结点
r = s;//r指向新结点
}
r->next = NULL;//链表的尾结点指针为空
}在 while 循环中，用 s 指向新分配的内存，分别赋值姓名和学号，如果学号为 0 ，则结束输入，退出循环，最后将链表的最后一个结点的指针域赋值为NULL，表示链表创建结束。
2）头插法创建单链表
从第一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。尾插法创建单链表代码如下：
void CreatByHead(LinkList head)
{
Node *s;
char name[20];
int number;
printf ("请输入学生姓名和学号：\n");
while(1)
{
scanf ("%s",name);
scanf ("%d",&number);
if (number==0)
break;
s = (Node*)malloc(sizeof(Node));
strcpy(s->name ,name);
s->number = number;
s->next = head->next ;//新结点指向原来的首元结点
head->next = s;//链表的头结点指向新结点
}
} 3.单链表的遍历
void OutPut(LinkList head)
{
Node *p;//循环所用的临时指针
p = head->next ;//p指向链表的首元结点
while (p)
{
printf ("姓名:%s\n",p->name);//输出姓名
printf ("学号:%d\n",p->number);//输出学号
p = p->next; //移动临时指针到下一个结点
}
} OutPut函数功能是将链表中的数据进行输出。函数参数中，head表示一个链表的头指针，函数中定义一个临时指针 p 用来进行循环操作，使其指向要输出链表的首元结点。
将链表的初始化，创建和遍历输出操作整合在一起，就编写了一个包含学生信息的链表结构。具体如下：
#include <>
#include <>
#include <>
typedef struct node{
char name[20];//姓名
int number;//学号
struct node *next;//next的类型是指向本结构体数据类型的指针类型
}Node,*LinkList;
//单链表的初始化：就是创建一个头结点
LinkList InitList()
{
LinkList head;//定义头指针变量
head = (Node*)malloc(sizeof(Node));//头指针指向分配的头结点内存空间
head->next=NULL;//头指针指针域为空
return head;//返回头结点地址，即头指针
}
//尾插法创建单链表
void CreatByRear(LinkList head)
{
Node *r,*s;//s指向新创建的结点
char name[20];
int number;
r = head;//r指向头结点 ，即当前单链表的尾结点
printf ("请输入学生姓名和学号：\n");
while(1)
{
scanf ("%s",name);
scanf ("%d",&number);
if (number==0)
break;
s = (Node*)malloc(sizeof(Node));//分配结点的内存空间 ，令s指向新分配的内存
//分别赋值姓名和学号
strcpy(s->name ,name);
s->number = number;
r->next = s;//原来的结点指向新结点
r = s;//r指向新结点
}
r->next = NULL;//链表的尾结点指针为空
}
//头插法创建单链表
void CreatByHead(LinkList head)
{
Node *s;
char name[20];
int number;
printf ("请输入学生姓名和学号：\n");
while(1)
{
scanf ("%s",name);
scanf ("%d",&number);
if (number==0)
break;
s = (Node*)malloc(sizeof(Node));
strcpy(s->name ,name);
s->number = number;
s->next = head->next ;//新结点指向原来的首元结点
head->next = s;//链表的头结点指向新结点
}
}
//单链表的遍历
void OutPut(LinkList head)
{
Node *p;//循环所用的临时指针
p = head->next ;//p指向链表的首元结点
while (p)
{
printf ("姓名:%s\n",p->name);//输出姓名
printf ("学号:%d\n",p->number);//输出学号
p = p->next; //移动临时指针到下一个结点
}
}
int main (void)
{
LinkList ha,hb;//定义单链表头指针
ha = InitList();//初始化单链表
CreatByRear(ha);//尾插法创建单链表
OutPut(ha);//输出单链表
hb = InitList();
CreatByHead(hb);
OutPut(hb);
return 0;
}