1700415480
1700415481
1700415482
1700415483
计算机是怎样跑起来的 [:1700412676]
1700415484
计算机是怎样跑起来的 6.7 要点7：了解链表和二叉树的实现方法
1700415485
1700415486
下面讲解如何使用结构体的数组实现链表和二叉树。链表是一种类似数组的数据结构，这个“数组”中的每个元素和另一个元素都好像是手拉着手一样。在现有的以结构体TestResult为数据类型的数组Student[100]中，为了让各个元素“把手拉起来”，就需要在结构体中再添加一个成员（如代码清单6.10所示）
1700415487
1700415488
代码清单6.10 带有指向其他元素指针的自我引用结构体
1700415489
1700415490
struct TestResult{
1700415491
1700415492
char Chinese; /*语文成绩*/
1700415493
1700415494
char Math; /*数学成绩*/
1700415495
1700415496
char English; /*英语成绩*/
1700415497
1700415498
struct TestResult* Ptr; /*指向其他元素的指针*/
1700415499
1700415500
};
1700415501
1700415502
请注意，这里在结构体TestResult中添加了这样一个元素：
1700415503
1700415504
struct TestResult* Prt
1700415505
1700415506
本节不会详细分析这条语句，但简单地说，这里的成员Prt存储了数组中另一个元素的地址。在C语文中，把存储着地址的变量称为“指针”。这里的*（星号）就是指针的标志。可以看到，Ptr就是以结构体TestResult的指针（struct TestResult*）为数据类型的成员。这种特殊的结构体可以称为“自我引用的结构体”。之所以叫这个名字是因为在结构体TestResult的成员中，含有以TestResult的指针为数据类型的成员，这就相当于TestResult引用了与自身相同的数据类型。
1700415507
1700415508
在结构体TestResult（已变成了自我引用的结构体）的数组中，每个元素都含有一个学生的语文、数学、英语成绩以及成员Ptr。Prt中存储着本元素接下来该与哪个元素相连的信息，即一个元素的地址。
1700415509
1700415510
在链表的初始状态中，会按照元素在内存上的分布情况设定成员Ptr的值（如图6.11所示）
1700415511
1700415512
图6.11 初始状态的链表中，元素的排列顺序与元素在内存上的物理排列顺序相同
1700415513
1700415514
1700415515
1700415516
1700415517
那么，接下来就是链表的有趣之处了。因为Ptr中存储的是与下一个数组元素的连接信息，所以只要替换了Ptr的值，就可以对数组中的元素排序，使元素的排列顺序不同于其在内存上的物理排列顺序。首先，我们来试着把数组中元素A的Ptr的值改为元素C的地址，然后把元素C的Ptr的值改为B的地址，通过这样的改变，原有的顺序A→B→C就变成了A→C→B（如图6.12所示）
1700415518
1700415519
图6.12 只要改变连接信息，元素就可以呈现出新顺序，不同于其在内存上的物理排列顺序
1700415520
1700415521
1700415522
1700415523
1700415524
为什么说链表很方便呢？请思考一下不使用链表且还要对大量的数据进行排序时应该怎样处理。答案是那就必须要改变元素在内存上的物理排列顺序了。这不仅要改变大量数据的位置，而且程序的处理时间也会变长。如果是使用链表，对元素的排列顺序就只需要变更Ptr的值，程序的处理也会缩短，这个特性也适用于对元素进行删除和插入。在实际的程序中，为了能够处理大量数据，都会在各种各样的情况下灵活运用链表，不使用链表的情况很少见。
1700415525
1700415526
只要明白了链表的构造，也就明白了二叉树的实现方法。在二叉树的实现中，用的还是自我引用的结构体，只不过要改为要带有两个连接信息的成员的自我引用结构体（如代码清单6.11所示）
1700415527
1700415528
代码清单6.11 带有两个链表连接信息的自我引用结构体
1700415529