C语言静态链表和动态链表
1. 静态链表
结构体中的成员可以是各种类型的指针变量，当一个结构体中有一个或多个成员的基类型是本结构体类型时，则称这种结构体为“引用自身的结构体”。如：
struct link
{
char ch;
struct link *p;
} a;
p是一个可以指向 struct link 类型变量的指针成员。因此，a.p = &a 是合法的表达式，由此构成的存储结构如图1所示。
图1 引用自身的结构体
例1 一个简单的链表
#include <stdio.h>
struct node
{
int data;
struct node *next;
};
typedef struct node NODETYPE;
int main()
{
//a是头结点，b是中间节点，c是尾节点
//h是基类型为NODETYPE的指针，指向头结点
//p是基类型为NODETYPE的指针，用于遍历链表
NODETYPE a, b, c, *h, *p;
//给变量中的data赋值
a.data = 10;
b.data = 20;
c.data = 30;
//将节点相连
h = &a;
a.next = &b;
b.next = &c;
c.next = '\0';
//移动p，使之依次指向a、b、c,输出它们data中的值
p = h;
while (p)
{
printf("%d\t", p->data);
p = p->next; //p顺序后移
}
printf("\n");
return 0;
}
STRUCT_LIST
STRUCT_LIST
以上程序中所定义的结构体类型 NODETYPE 共有两个成员：成员 data 是整型；成员 next 是指针类型，其基类型是 NODETYPE 类型。
a、b、c 是 NODETYPE 结构体类型变量，h 和 p 是指向 NODETYPE 结构体类型的指针变量。执行程序后，形成如图2所示的存储结构体：指针 h 中存放变量 a 的地址，变量 a 的成员 a.next 中存放变量 b 的地址……，最后一个变量 c 的成员 c.next 置为 '\0'(NULL)。这样就把同一类型的结构体变量 a、b、c “链接”到一起，形成所谓的“链表”，变量 a、b、c 称为链表的节点。
在此例中，链接到一起的每个节点（结构体变量 a、b、c）都是通过定义，由系统在内存中开辟了固定的、不一定连续的存储单元。在程序执行过程中，不可能人为的再产生新的存储单元，也不能认为的使已开辟的存储单元消失。这种链表成为“静态链表”。
图2 链表存储结构示意图
2.动态链表的概念
到目前为止，凡是遇到处理“批量”数据时，我们都是利用数组来存储。定义数组必须（显式的或隐含的）指明元素的个数，从而也就限定了一个数组中存放的数据量。在实际应用中，一个程序在每次运行时要处理的数据的数目通常并不确定。如果数组定义的小了，就没有足够的空间存放数据，定义大了又浪费存储空间。
对于这种情况，如果能在程序执行过程中，根据需要随时开辟存储空间，不需要时再随时释放，就能比较合理的使用存储空间。C 语言的动态存储分配提供了这种可能性。每次动态分配的存储单元，其地址不一定是连续的，而所需处理的批量数据往往是一个整体，各数据之间存在着接序关系。链表的每个节点中，除了要有存放数据本身的数据域外，至少还需要有一个指针域，用它来存放下一个节点元素的地址，以便通过这些指针把各节点连接起来（如图3）。由于链表每个存储单元都由动态存储分配获得，故称这样的链表为“动态链表”。
需要强调的是：动态链表中，每个节点没有自己的名字，只能靠指针维系节点之间的接序关系。一旦某个节点的指针“断开”，后续节点就再也无法找寻。
图3 带有头结点的单向链表
每个链表都用一个“头指针”变量来指向链表的开始，如图3中的 head。也就是说，在 head 中存放了链表的第一个节点的地址。在这个链表中，我们设置了一个“头结点”，这个节点的数据域中不存放数据（根据需要也可以不设头结点）。链表最后一个节点的指针域不存放地址，置为 '\0'(NULL) 值，标志着链表的结束。上述链表的每个节点都只有一个指针域，每个指针域存放着下一个节点的地址。因此，这种链表只能从当前节点找到后继节点，故称为“单向链表”。
您可能感兴趣的文章:老生常谈C语言动态函数库的制作和使用(推荐)C语言使用DP动态规划思想解最大K乘积与乘积最大问题使用C语言实现vector动态数组的实例分享在C语言中调用C++做的动态链接库C语言完美实现动态数组代码分享C语言实现支持动态拓展和销毁的线程池C语言创建链表错误之通过指针参数申请动态内存实例分析C语言构建动态数组完整实例c语言动态数组示例C语言 动态内存分配的详解及实例
