链表——链式存储结构
① 静态链表：把线性表的元素存放在数组中，这些元素之间通过逻辑关系来连接。数组单元存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在的数组单元的下标。但是涉及长度定义的问题，所以就出现了动态链表。
② 动态链表：在程序执行过程中从无到有建立起来，一个一个地开辟结点和输入各结点的数据，并建立前后相连的关系。
单链表——所有结点都是单线联系
① 特点：（1）头指针变量存放第一个结点的地址。
（2）每个结点包含一个数据（用户需要的实际数据）和一个指针（存放下一个结点的地址）。
（3）表尾结点不再指向其他结点，指针域为NULL，表示链表到此结束。
② 优点：（1）链表中各结点之间的顺序关系由指针域来确定，不需要占用一片连续的内存空间。
（2）链表可以无限延长（仅受内存总量的限制）。
（3）在插入和删除操作中，只需修改相关结点指针域的链接关系。
即：用则申请，不用则释放，大大提高内存利用率和时间效率。
③ 缺点： 查找元素的速度不如数组。
————————————————————————————————————————————————————————————————————
❤单链表的建立
结点的数据类型必须选用结构体类型，可以包含多个各种类型的成员，而且其中必须含有一个指向本结构体类型的指针成员。以班级学生为例，将学生作为结点，把所有学生的信息存放到链表结构中。首先，要创建结点结构，表示每一个学生。
struct student //学生结构体
{
char name[20]; //姓名
int id; //学号
struct student *next; //指向下一个结点的指针
};然后，定义一个create函数，用来创建链表，该函数返回链表的头指针。
int count; //全局变量 表示链表长度
struct student *create()
{
struct student *head=NULL; //初始化头指针为空
struct student *end,*new;
end=new=(struct student *)malloc(sizeof(struct student));
count=0; //初始化链表长度
printf("请输入学生的姓名和学号：\n");
scanf("%s",new->name);
scanf("%d",&new->id);
while(new->id!=0) //当学生学号不为0，执行循环
{
count++;
if(count==1) //链表中只有一个结点
{
new->next=NULL; //新结点的指向为空
end=new;
head=new; //新结点既是首结点又是尾结点
}
else //链表中结点个数>1
{
new->next=NULL; //新结点的指向为空
end->next=new; //原来的尾结点指向新结点
end=new; //新结点当作尾结点
}
new=(struct student *)malloc(sizeof(struct student)); //再次分配结点的内存空间
scanf("%s",new->name);
scanf("%d",&new->id);
}
free(new); //释放结点空间
return head;
}然后用malloc函数分配内存，先将end，new均指向第一个分配的内存，然后输入学生信息。
再使用while语句进行判断，如果学号为0，则结束输入。否则执行循环，继而count自增，表示链表中结点个数的增加，然后判断结点个数。若count==1，进入if语句，因为第一次加入结点，所以新结点new既是首结点，又是尾结点，并且新结点的指针应指向NULL。若count>1，进入else语句，实现的是链表中已经有结点时的插入操作，所以新结点的指针指向NULL，原来的结点指向新结点，最后将end指针指向新结点。
一个结点创建完之后，紧接着要再次分配内存，输入数据，进行while循环。当结点不符合要求时，终止循环，并用free函数将该结点空间进行释放，否则会出现内存泄漏的问题。
❤单链表的遍历
遍历链表中的数据并进行输出。
void print(struct student *head)
{
struct student *t; //循环所用到的临时指针
int index=1; //链表结点的序号
t=head; //临时指针得到首结点地址
printf("\n**********本名单中有%d个学生**********\n",count);
while(t!=NULL)
{
printf("第%d个学生是：\n",index); //输出结点序号
printf("姓名:%s\n",t->name); //输出姓名
printf("学号:%d\n",t->id); //输出学号
t=t->next; //移动临时指针到下一个结点
index++; //结点序号增加
}
printf("\n\n");
}
函数参数中的head表示头结点。函数中定义的临时指针 t 用来进行循环操作，每输出一个结点的内容，就移动 t 指针到下一个结点的地址，当作为最后一个结点时，指针指向NULL，表示链表输出完成，循环结束。
❤单链表的插入
链表的插入操作有三种，可以在头指针位置插入，也可以在某个结点的位置插入，或者在最后添加结点。这里以头插法为例。
struct student *insert(struct student *head)
{
struct student *new;
printf("输入学生的姓名和学号：\n");
new=(struct student *)malloc(sizeof(struct student)); //给插入的新结点分配内存空间
scanf("%s",new->name);
scanf("%d",&new->id);
new->next=head; //插入的新结点指向原来的首结点（即得到首结点的地址）
head=new; //头指针指向新结点（头->新->原来的首结点）
count++; //增加链表结点数量
return head;
}
首先为插入的新结点分配内存，然后向新结点输入数据。插入时，首先将新结点的指针指向原来的首结点，得到首结点的地址，然后将头指针指向新结点，则完成插入操作。最后再增加链表结点数量，返回头指针。
❤单链表的删除
delete函数中有两个参数，head表示链表的头指针，index表示要删除结点在链表中的位置。
void delete(struct student *head,int index)
{
int i;
struct student *t; //临时指针
struct student *pre; //要删除结点前的结点
t=head; //临时指针得到链表头结点的地址
pre=t;
printf("——————删除第%d个学生——————\n",index);
for(i=1;inext;
}
pre->next=t->next; //连接删除结点两边的结点
free(t); //释放要删除结点的内存空间
count--; //减少链表结点个数
}
定义指针t，指针pre，分别表示要删除的结点和这个结点之前的结点。然后在for语句中进行循环找到要删除的结点，使用t保存要删除结点的地址，pre保存前一个结点的地址，连接要删除结点两边的结点，并用free将t指向的内存空间释放。
—————————————————————————————————————————————————————————
最后在main函数里对各个自定义函数进行调用，实现相应的功能。
int main()
{
struct student *head; //定义头结点
head=create(); //创建结点
print(head); //输出链表
head=insert(head); //插入结点
print(head); //输出链表
delete(head,2); //删除第二个结点
print(head); //输出链表
return 0;
}#include
#include
struct student //学生结构体
{
char name[20]; //姓名
int id; //学号
struct student *next; //指向下一个结点的指针
};
int count; //全局变量 表示链表长度
struct student *create()
{
struct student *head=NULL; //初始化头指针为空
struct student *end,*new;
end=new=(struct student *)malloc(sizeof(struct student));
count=0; //初始化链表长度
printf("请输入学生的姓名和学号：\n");
scanf("%s",new->name);
scanf("%d",&new->id);
while(new->id!=0) //当学生学号不为0，执行循环
{
count++;
if(count==1) //链表中只有一个结点
{
new->next=NULL; //新结点的指向为空
end=new;
head=new; //新结点既是首结点又是尾结点
}
else //链表中结点个数>1
{
new->next=NULL; //新结点的指向为空
end->next=new; //原来的尾结点指向新结点
end=new; //新结点当作尾结点
}
new=(struct student *)malloc(sizeof(struct student)); //再次分配结点的内存空间
scanf("%s",new->name);
scanf("%d",&new->id);
}
free(new); //释放结点空间
return head;
}
void print(struct student *head)
{
struct student *t; //循环所用到的临时指针
int index=1; //链表结点的序号
t=head; //临时指针得到首结点地址
printf("\n**********本名单中有%d个学生**********\n",count);
while(t!=NULL)
{
printf("第%d个学生是：\n",index); //输出结点序号
printf("姓名:%s\n",t->name); //输出姓名
printf("学号:%d\n",t->id); //输出学号
t=t->next; //移动临时指针到下一个结点
index++; //结点序号增加
}
printf("\n\n");
}
struct student *insert(struct student *head)
{
struct student *new;
printf("输入学生的姓名和学号：\n");
new=(struct student *)malloc(sizeof(struct student)); //给插入的新结点分配内存空间
scanf("%s",new->name);
scanf("%d",&new->id);
new->next=head; //插入的新结点指向原来的首结点（即得到首结点的地址）
head=new; //头指针指向新结点（头->新->原来的首结点）
count++; //增加链表结点数量
return head;
}
void delete(struct student *head,int index)
{
int i;
struct student *t; //临时指针
struct student *pre; //要删除结点前的结点
t=head; //临时指针得到链表头结点的地址
pre=t;
printf("——————删除第%d个学生——————\n",index);
for(i=1;inext;
}
pre->next=t->next; //连接删除结点两边的结点
free(t); //释放要删除结点的内存空间
count--; //减少链表结点个数
}
int main()
{
struct student *head; //定义头结点
head=create(); //创建结点
print(head); //输出链表
head=insert(head); //插入结点
print(head); //输出链表
delete(head,2); //删除第二个结点
print(head); //输出链表
return 0;
}
—————————————————————————————————————————————————————————
循环链表
由单链表演化而来，不同点如下：
① 链表的建立。单链表需要创建一个头结点，专门存放第一个结点的地址。单链表的尾结点指针域指向NULL。而循环链表的建立，不需要专门的头结点，让最后一个结点的指针域指向链表的头结点即可。
② 链表表尾的判断。单链表判断结点是否为表尾结点，只需判断结点的指针域是否为NULL。而循环链表判断是否为表尾结点，则是判断该结点的指针域是否指向链表头结点。
双向链表
单链表是单向的，不能逆着进行。而双向链表添加了一个指针域，通过两个指针域，分别指向结点的前结点（左链域）和后结点（右链域）。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。
*********
参考文献：《C语言程序设计教程》王曙燕等