数组在使用之前必须分配固定大小,而且分配的数量还不好确定,或大或小都会导致低劣程序。
链表则可以实现动态大小。
用指针来实现链表真是再方便不过了。
每个节点中的指针称为链(link)
这种数据结构叫链表(linked list)
每个链表都以一个简单的指针开始,指向链表中的第一个数据项,称为头指针(head)
C语言中链表的表示为:
struct Node { char *City; int Temp; struct Node * Next;}; // 链节点的定义typedef strcut Node * Link; // 类型的别名Link Head; // 定义头指针
在结构体中定义结构的指针叫做自引用,
还有不同结构体中相互定义指针,叫做互引用
typedef可增强代码的可读性
头指针在链表为空时它是NULL,否则他应该指向第一个节点。
如果要按照某种顺序向链表中插入节点时,还应当有比较两个节点的函数。
链表插入的特殊情况在于:
向空链表中插入一个节点;
在第一个节点之前插入节点;
在链表的尾部插入节点。
单链表还可以有的操作比如:
查找;
删除;
反转;
链接;
比较。
双链表
单链表必须得维护好头结点,不然头结点没了就啥都没了,哭都没处哭
现在好了有双链表了
双向链表的节点中包含数据以及指向前一个和后一个节点的链
可以前向遍历,也可以后向遍历
双链表还有一个尾指针(tail)
双向链表的操作比单链表要要稍微复杂些,因为删除和插入的时候都要操纵一个额外的指针。
操作发生在尾部时必须更新尾指针。
编码的时候要特别小心指针的指向。
通用的例程来实现双向链表有一个功能全面的原函数:这些函数与数据的访问与处理无关,之和链表的操作有关。
值得注意的是删除链节点并不是primitive的,因为删除数据可能还得释放占用内存的地方,因此首先删除数据,然后再释放节点。
创建节点需要注意的是,不能简单地复制一个指向数据的指针,函数不知道这个数据可以持续多久。
在分配空间是一定要判断是否分配成功了
/* Make a copy of the input node */ pn = ( Link ) malloc ( sizeof ( struct Node ) ); if ( pn == NULL ) /* if allocation failures */ return 0; /* 如果返回的值是0, 则代表着结点的分配失败 */