c语言定义通用链表（C语言-线性表的定义和逻辑结构-单向链表的存储结构和操作）

c语言定义通用链表（C语言-线性表的定义和逻辑结构-单向链表的存储结构和操作）以上介绍的程序是在程序一开始通过说明结构变量来为链表的结点开辟存储单元。而实际应用中链表通常是一种动态存储结构，结点所占用的存储空间是在程序的执行过程中，根据需要临时开辟的。当链表中需要增加一个结点时，要为新结点申请一个存储空间。当链表中要删除一个结点时，要将已删除的结点的存储空间释放，归还给系统。C语言编译系统的库函数提供了动态分配和释放存储空间的函数。 若没有特别说明，以下讨论的链表都设定为带头结点的链表。静态法建立链表带注释的完整程序： #define NULL 0 void main() { NODE a b c d *head *p; a.data=3; b.data=5; c.data=8; d.data=2; /* 对结点的数据域（结构变量的data成员）赋值 */ head=&a; /* a结点的起始地址赋值给头指针变量head */ a.next=&am

单向链表的表示

与线性表（a₁，a₂，…，a_n）相应的单向链表由n个结点链接而成。每个数据元素对应链表中一个结点，数据元素a_i相应的结点在单向链表中称为结点a_i。结点a_i中的数据域存储数据元素a_i，指针域用于存放a_i的直接后继元素a_{i 1}相应结点的存储地址。链表中第一个结点的存储位置称为头指针，程序中通常用一个指针变量存储头指针。本章命名该指针变量为head。最后一个数据元素a_n没有直接后继，所以链表中最后一个结点的指针域存放的是空指针（NULL）。该单向链表如图2-4所示。

单向链表示意图

由单向链表的结构可知，只要已知头指针，就可以由前到后逐次访问到链表中任意一个结点。具体做法是由头指针出发，可以访问到第一个结点，由第一个结点的指针域可以访问到第二个结点，…，一般地，由第i个结点的指针域可以访问到第i 1个结点。

静态法建立链表

带注释的完整程序： #define NULL 0 void main() { NODE a b c d *head *p; a.data=3; b.data=5; c.data=8; d.data=2; /* 对结点的数据域（结构变量的data成员）赋值 */ head=&a; /* a结点的起始地址赋值给头指针变量head */ a.next=&b; /* b结点的起始地址赋值给a结点的指针域（结构变量的next成员）*/ b.next=&c; c.next=&d; d.next=NULL; /* d是尾结点，把空指针赋值给d结点的指针域 （结构变量的next成员）*/ p=head; /* 工作指针p指向结点a */ do { printf("%d\n" p->data); /* 逐次输出p所指结点的数据 */ p=p->next; /* 使p指向当前所指结点的直接后继结点 */ }while(p!=NULL) }

在某些情况下，为了操作方便，在线性链表的第一个结点前增加一个附加结点，称它为头结点。头结点的数据域可以不存储任何信息，或者只是存储一些非线性表的数据元素的附加信息。而头结点指针域用以存储第一个结点的指针（地址）

带头结点的单向链表示意图

若没有特别说明，以下讨论的链表都设定为带头结点的链表。

以上介绍的程序是在程序一开始通过说明结构变量来为链表的结点开辟存储单元。而实际应用中链表通常是一种动态存储结构，结点所占用的存储空间是在程序的执行过程中，根据需要临时开辟的。当链表中需要增加一个结点时，要为新结点申请一个存储空间。当链表中要删除一个结点时，要将已删除的结点的存储空间释放，归还给系统。C语言编译系统的库函数提供了动态分配和释放存储空间的函数。

例如： NODE *p; /*说明一个指向结点（结构体变量）的指针变量*/ p= (NODE *) malloc ( sizeof (NODE)); /*动态分配一个新结点，并使p指向该结点*/ free(p); /*释放p所指向的结点*/

分配、释放存储空间

动态法建立链表

建立单向链表的算法是一个动态过程，即从“空表”开始，依次生成各元素的结点，并逐次插入到链表中。根据插入位置的不同，建立链表的方法可以分为尾插法和头插法。尾插法是逐次生成的新结点总是作为当前链表的尾结点插入，头插法是逐次生成的新结点总是作为当前链表的第一个结点插入，算法2-3、算法2-4分别是用尾插法和头插法建立单向链表的算法。

用尾插法建立带头结点且有n个结点的单向链表的算法。

NODE *create1(int n) /* 对线性表(1 2 ..... n) 建立带头结点的单向链表 */ { NODE *head *p *q; int i; p=(NODE *)malloc(sizeof(NODE)); head=p; q=p; p->next=NULL; for(i=1;i<=n;i ) { p=(NODE *)malloc(sizeof(NODE)); p->data=i; p->next=NULL; q->next=p; q=p; } return(head); }

算法要点： 程序中有3个结构指针变量，其中指针变量head存放头结点的地址，指针变量p用以在动态开辟新结点的存储单元时，存放新的结点的地址，我们称它为“生成指针”。指针q始终指向当前链表的尾结点。当p所指向的新结点被链入表尾后，由q来替代p指向表尾结点，目的是可以通过q访问尾结点，我们称它为“接应指针”。具体步骤为：用p开辟新结点，并由p指向新结点，把p链入表尾，用q指向尾结点，由p继续生成新结点。

用头插法建立带头结点且有n个结点的单向链表的算法。

NODE *create2(int n) /*对线性表(n n-1 ..... 1) 建立带头结点的线性链表 */ { NODE *head *p *q; int i; p=(NODE *)malloc(sizeof(NODE)); head=p; p->next=NULL; q=p; for(i=1;i<=n;i ) { p=(NODE *)malloc(sizeof(NODE)); p->data=i; if(i==1) p->next=NULL; else p->next=q->next; q->next=p; } return(head); }

算法要点： 程序中有3个结构指针变量head、p、q，head和p的作用与上例相同，指针q始终指向当前链表的头结点。具体步骤为：用p开辟新结点，利用指针q把p所指向的新结点插入当前链表的头结点之后，作为第一个结点，再由p继续生成新结点。（使用指针变量q是为了与后面的插入算法一致，而就本例可以不设q，而利用head就可以完成q的功能）。