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; }