链表类型
链表的基本结构
链表结构是利用指针进行动态存储分配的最简单的一种结构。动态存储分配是指根据需要临时分配内存单元以存放有用的数据，当数据不用时又可以随时释放存储单元，此后这些存储单元又可以用来分配给其它数据使用。在前面的程序中，一个变量如果被指定为全局变量，它在整个程序运行期间都占据存储单元.
例如：如果要存放一个班的学生的数据（如学号、姓名、各门成绩等）就要定义一个数组。如果不能事先不能确定人数的多少，就要定义一个足够大的数组；可以看出，用这种方法处理问题缺乏灵活性，往往会浪费许多内存。链表是指若干个数据（每一个数据组称为一?quot;结点"）按一定的原则连接起来。这个原则是：前一个结点"指向"下一个结点，只能通过前一个结点才能找到下一个结点。不象对数组元素的访问可以是随机的。
链表中每个元素称为结点，图中链表的每个结点包含两个域，一个域中存放数据，另一域中存放下一个结点的地址。在表尾结点中，由于不必指向任何地址，因此放入一个NULL值。NULL是一个符号常量，被定义为0，也就是将0地址赋给最后一个结点中的地址项。 链表中的每个结点至少应该包含两个域：用一个域来存放数据，其类型根据存放数据的类型而定（例如可以是结构体类型的数据）；另一个域用来存放地址，因此必然是一个指针类型，此指针类型是所指向的表结点的类型。
注意：链表中各结点在内存中并不是占连续的一片内存单元。各个结点可以分别存放在内存的各个位置，只要知道其地址，就能访问此结点。当链表结点中的指针失去了下一个结点的地址后，链表就会断开，其后的结点将会全部丢失。
当使用链表结构时，如果需要，可以采用适当的操作步骤使链表加长或缩短，而使存储分配具有一定的灵活性。
用含指针项的结构体变量构成结点
链表中的每一结点是由两部分组成的：
（1）对用户有用的数据，是链表的结点的实体部分。
（2）用来存放下一个结点地址的一个指针类型数据项，是用来建立结点间的联系的，也就是用它来构成"链"。用C语言实现链表这种数据结构是很方便的。包含指针项的结构体变量就是一个结点。例如：
struct stud_ score
{
long num；
float score；
struct stud_score *next；
}；
num和score成员用来存放学号和成绩，next是指针变量，它指向struct stud_score类型的变量。next指针项必须指向与next所在的结点是同一类型的结点。
可以用下面的方法建立一个简单的链表：
struct stud_score stud1,stud2,stud3,stud4,*head;
stud1.num=970101; stud1.score=85.5; /* 赋值 */
stud2.num=970102; stud2.score=90.5;
stud3.num=970103; stud3.score=75.5;
stud4.num=970104; stud4.score=68.0;
head.next=&stud1; /* 形成链 */
stud1.next=&stud2;
stud2.next=&stud3;
stud3.next=NULL;
用以上方法可建立一个简单链表。用户不必其体了解每个结点中next成员的值是什么，只需将需要链入的下一结点的地址赋给它即可。系统在对程序编译时对每一个变量都分配了确定的地址。
注意：head不是一个结构体变量而只是一个指向结构体变量的指针变量，它不包括有用数据
输出链表中的数据
对于前面已建立的链表，如果想逐项输出其中学生的数据，可用以下函数来实现。
void print(void)
{
struct stud_score *p;
int i;
if(head==NULL)
{
printf("\nempty list.\n");
return;
}
p=head; /* 使指向第一个结点 */
do {
printf("\nrecord number%d\n",++i);
printf("num:%ld\n",p->num);
printf("score:%6.1f\n",p->score);
p=p->next;
}
while(p!=NULL)/* 输出最后一个结点不再输出*/
head代表链表的头指针，p从第一个结点开始，通过p=p->next操作，顺序指向链表中的每一个结点并输出该结点内容，直到遇到最后一个结点。 以上的方法虽然也能实现简单的链表结构，但它必须在程序中事先确定个数的结构体变量（结点），这就缺乏灵活性，想再增加一个结点就要修改程序，并且所有结点都自始至终占据内存单元，而不是动态地进行存储分配。为了能动态地开辟和释放内存单元，要用到C标准函数库中的malloc函数和free函数。
用于动态存储分配的函数
C语言新标准ANSI C要求各C编译版本提供的标准库函数中应包括动态存储分配的函数，它们是：
malloc（ ）；
calloc（ ）；
free（ ）；
recalloc（ ）；
1．malloc函数
其作用是在内存开辟指定大小的存储空间，并将此存储空间的起始地址作为函数值带回。
malloc函数的形式： void *malloc（unsigned int size） 或 char *malloc（unsigned int size）
它的形参size为无符号整型。函数值为指针（地址），例如：用malloc（8）来开辟一个长度为8个字节的内存空间，如果系统分配的此段空间的起始地址为1362，则malloc（8）的函数返回值为1362。
如果内存缺乏足够大的空间进行分配，则malloc函数值为"空指针"，即地址为0。
2．calloc函数
其函数模型为： void *calloc（unsigned int num，unsigned int size）
它有两个形参num和size，其作用是分配num个大小为size字节的空间，例如：用calloc（10，16）可以开辟10个（每个大小为16字节）的空间，共160字节。函数返回值为该空间的首地址。
3．free函数其函数模型为： void free（void *ptr）
其作用是将指针变量ptr指向的存储空间释放，系统可以另分配。注意：ptr值不能是任意的地址，而是在程序中执行过的malloc或calloc函数所返回的地址。free函数无返回值。
4．realloc
用来使已分配的空间改变大小，即重新分配。其函数模型为： void *recalloc（void *ptr，unsigned int size）其作用是将ptr指向的存储区（用malloc函数分配的）的大小改为size个字节。它的返回值是新的存储区的首地址。
使用这些函数时要用#include命令将stdlib.h文件包含进来。但有的系统用malloc.h而不是stdlib.h。在使用时请注意系统的规定。有的系统则不要求包括任何"头文件"。
评论