服务器之家

服务器之家 > 正文

C语言静态链表和动态链表

时间:2021-04-01 15:17     来源/作者:web1013

1. 静态链表

  结构体中的成员可以是各种类型的指针变量,当一个结构体中有一个或多个成员的基类型是本结构体类型时,则称这种结构体为“引用自身的结构体”。如:

?
1
2
3
4
5
struct link
{
  char ch;
  struct link *p;
} a;

  p是一个可以指向 struct link 类型变量的指针成员。因此,a.p = &a 是合法的表达式,由此构成的存储结构如图1所示。

C语言静态链表和动态链表

图1 引用自身的结构体

  例1 一个简单的链表

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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)都是通过定义,由系统在内存中开辟了固定的、不一定连续的存储单元。在程序执行过程中,不可能人为的再产生新的存储单元,也不能认为的使已开辟的存储单元消失。这种链表成为“静态链表”。

C语言静态链表和动态链表

图2 链表存储结构示意图

2.动态链表的概念

  到目前为止,凡是遇到处理“批量”数据时,我们都是利用数组来存储。定义数组必须(显式的或隐含的)指明元素的个数,从而也就限定了一个数组中存放的数据量。在实际应用中,一个程序在每次运行时要处理的数据的数目通常并不确定。如果数组定义的小了,就没有足够的空间存放数据,定义大了又浪费存储空间。

  对于这种情况,如果能在程序执行过程中,根据需要随时开辟存储空间,不需要时再随时释放,就能比较合理的使用存储空间。C 语言的动态存储分配提供了这种可能性。每次动态分配的存储单元,其地址不一定是连续的,而所需处理的批量数据往往是一个整体,各数据之间存在着接序关系。链表的每个节点中,除了要有存放数据本身的数据域外,至少还需要有一个指针域,用它来存放下一个节点元素的地址,以便通过这些指针把各节点连接起来(如图3)。由于链表每个存储单元都由动态存储分配获得,故称这样的链表为“动态链表”。

  需要强调的是:动态链表中,每个节点没有自己的名字,只能靠指针维系节点之间的接序关系。一旦某个节点的指针“断开”,后续节点就再也无法找寻。

C语言静态链表和动态链表

图3 带有头结点的单向链表

  每个链表都用一个“头指针”变量来指向链表的开始,如图3中的 head。也就是说,在 head 中存放了链表的第一个节点的地址。在这个链表中,我们设置了一个“头结点”,这个节点的数据域中不存放数据(根据需要也可以不设头结点)。链表最后一个节点的指针域不存放地址,置为 '\0'(NULL) 值,标志着链表的结束。上述链表的每个节点都只有一个指针域,每个指针域存放着下一个节点的地址。因此,这种链表只能从当前节点找到后继节点,故称为“单向链表”。

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部