双向链表存储结构是线性表的一种实现方式,它在数据结构中扮演着重要的角色。在第2章中,线性表被定义为一种有限集合,其中的数据元素具有相同的特性,并且相邻元素之间存在顺序关系。每个元素都有唯一的前驱和后继,除了第一个元素和最后一个元素之外。例如,字母表和扑克牌可以被视为线性表。
在双向链表中,数据结构定义如下:
```c
typedef struct DuLNode{
ElemType data; // 存储元素的数据类型
struct DuLNode *prior; // 指向前一个节点的指针
struct DuLNode *next; // 指向后一个节点的指针
}DuLNode, *DuLinkList;
```
这种结构允许节点在链表中双向链接,即每个节点不仅可以访问其下一个节点,还可以访问其前一个节点,这为链表的操作提供了灵活性。双向循环链表是特殊的双向链表,它形成一个环状结构,头节点的`next`指针指向尾节点,尾节点的`prior`指针指向头节点。
对于线性表的基本操作,如初始化(`InitList`)、销毁(`DestroyList`)、清空(`ClearList`)、判断表是否为空(`ListEmpty`)、获取指定位置的元素(`GetElem`)、查找元素并返回其前驱或后继(`PriorElem` 和 `NextElem`)、插入元素(`ListInsert`)、删除元素(`ListDelete`)以及遍历整个列表(`ListTraverse`),这些操作构成了数据结构的核心功能,它们使得复杂的数据处理成为可能。例如,通过这些基本操作,可以设计高效的算法来实现复杂任务,如在例2-1中求两个集合的并集,或者在例2-2中构造一个只包含不重复元素的纯集合。
在例2-1中,`union`函数展示了如何使用基本操作来扩展线性表La,将Lb中La中不存在的元素插入到La中,时间复杂度为`O(ListLength(La)*ListLength(Lb))`。而在例2-2中,`purge`函数通过遍历Lb,检查并删除与La中已存在的元素相同的元素,直到Lb为空,从而实现构建纯集合的目标。
总结来说,双向链表作为线性表的一种存储结构,提供了方便的元素访问和插入删除操作,是数据结构和算法设计中的重要工具。通过理解并熟练运用这些基本操作,可以高效地处理各种与线性表相关的计算问题。