线性表的链式存储结构是指：用一组任意地址（可连续也可不连续）的存储单元来存储线性表的数据元素。
因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的信息之外，还需存储一个指向其直接后继的地址指针，这两部分信息组成数据元素ai的存储结构，称为结点（Node）。结点包括两个域：数据域和地址域（指针域）。指针域中存储的信息称为指针或链，n个结点链结成一个链表，即为线性表的链式存储结构，此线性表称为线性链表，又称单链表。
单链表有一个头指针，指向第一个结点。同时由于最后一个数据元素没有直接后继，则线性表中最后一个结点的指针域为空（NULL）。
下面是线性链表的物理状态示意图。
|
头指针P |
存储地址 |
数据域 |
指针域 |
|
1200H |
1000H 1200H 1700H 5000H 5400H 7000H |
a3 a1 a4 a2 a6 a5 |
1700H 5000H 7000H 1000H NULL 5400H |
下面是线性链表的逻辑状态示意图。
|
P → |
a1 |
|
→ |
a2 |
|
→ |
a3 |
|
→ |
a4 |
|
→ |
a5 |
|
→ |
a6 |
∧ |
由上可知，单链表可由头指针P唯一确定，P可以用C语言中的结构指针来表示，链表中的结点则可用C结构数据类型来描述。如：
struct NODE
{
int data;
struct NODE *next;
};
将上述描述表示为一般形式的抽象数据类型则可表示如下：
typedef struct LNode
{
ElemType data;
struct LNode *next;
};
2．构造单链表
上述用结构类型数据变量来实现单链，并未实际分配存储空间，链表结构是动态地分配存储空间，即在需要时才开辟一个结点的存储单元。
下面以学生成绩单为例，来说明如何构造一个单链表。
成绩单的每条记录便是一个数据元素，其对应的结构类型定义如下：
struct student
{
int num; /*学号*/
float score; /*成绩*/
struct student *next; /*指针域*/
}；
构造单链表如下：
struct student *creat() /*此函数返回一个指向链表的头结点*/
{
struct student *head; /*指向student类型变量的指针head为头指针*/
struct student *p,*tail; /*tail指向链表末尾元素，p指向新分配的结点*/
float temp; /*临时数据变量*/
head=NULL;
do
{
p=(struct student *)malloc(sizeof(struct student));/*分配新结点*/
printf(“Number Score:”);
fflush(stdin); /*清除输入缓冲区*/
scanf("%d %f",&p->num,&temp);
if(p->num==0)
{
free(p);
break;
};
p->score=temp; /*取得结点数据*/
p->next=NULL;
if(head==NULL)
{
head=p;
tail=p;
}
else
{
tail->next=p;
tail=p; /*指向尾结点*/
}
}while(p->num!=0);
return(head);
}
以上算法的思路是：让p指向新开辟的结点，tail指向链表中最后一个结点，把p所指向的结点链接在tail所指向的结点的后面，由语句“tail->next=p”来实现。
3．遍历单链表
遍历单链表就是将链表中的各结点的数据依次输出。
显然，首先应知道链表的头指针head（即第一个结点元素的地址）,然后设一个指针变量p，先指向第一个结点，输出p所指的结点，然后使p后移一个结点，再输出，直到链表的尾结点。
算法：遍历单链表。
void display(struct student *head)
{
struct student *p;
p=head;
while(p!=NULL)
{
printf("%4d %5.1f\n",p->num,p->score);
p=p->next;
}
}
