数据结构-列表

本篇文章整理《数据结构(C++语言版)》关于列表这种线性结构知识点。

列表

数据结构1——向量中介绍了线性表的两种形式:其一是物理地址与逻辑地址均连续,典型示例向量(Vector)结构;另一种是逻辑地址连续而物理地址不一定连续,典型示例列表(List)结构。
列表结构的基本组成单位是节点(node),各节点通过指针或引用彼此连接,构成逻辑连续的序列。
列表结构
正因为列表这一特性,一些静态操作,如寻秩访问、find等方法无法高效完成(物理地址不连续);而相反的动态操作,如插入、删除等方法无须对后续元素一次进行移位,故可以高效完成。

列表节点

一个节点的形式如下图所以,包括节点具体数值data,以及它的前驱指向pred,后继指向succ。
列表节点

1
2
3
4
5
6
7
8
9
10
11
12
#define Posi(T) ListNode<T>*
template <typename T>
struct ListNode {
T data; //数值
Posi(T) pred; //前驱
Posi(T) succ; //后继
ListNode() {} //针对header与trailer的构造,默认构造函数
ListNode(T e, Posi(T) p = NULL, Posi(T) s = NULL)
: data(e), pred(p), succ(s) {} //默认构造器,成员初始化列表
Posi(T) insertAsPred(T const& e); //前插入
Posi(T) insertAsSucc(T const& e); //后插入
}

TIPS:成员初始化列表
在上述代码段中,ListNode(T e, Posi(T) p = NULL, Posi(T) s = NULL) : data(e), pred(p), succ(s) {}即为成员初始化列表。【注意:成员初始化顺序应按照类成员声明顺序】

前插入算法

在当前节点前插入一个新的节点作为当前节点的前驱,需要修改原前驱的后继指向新节点等一系列如下图的操作。
前插入流程图

1
2
3
4
5
template<typename T>
Posi(T) ListNode<T>::insertAsPred(T const& e) {
Posi(T) x = new ListNode(e, pred, this); //初始化新节点data=e,pred=pred,succ=this,如上图(b)
pred->succ = x; pred = x; return x;
}

列表模板类

在列表中,预先定义了头、尾哨兵元素,并默认为不可见节点。
列表结构

1
2
3
4
5
6
7
8
9
10
11
12
#include "ListNode.h"  //引入列表节点类

template<typename T>
class List {
private:
int _size;
Posi(T) header; Posi(T) trailer; //头、尾哨兵
protected:
/*...内部函数 */
public:
/*...构造函数、析构函数等...*/
}

列表初始化

列表初始化,即创建头尾哨兵节点。具体代码实现如下

1
2
3
4
5
6
7
8
9
template<typename T>
void List<T>::init() {
header = new ListNode<T>;
trailer = new ListNode<T>;
//到目前为止,头尾哨兵节点只调用ListNode结构中的默认构造方法,即设置其前驱pred与后继succ均为空,data也为空。
header->succ = trailer; hdader->pred = NULL;
trailer->pred = header; trailer->succ = NULL;
_size = 0;
}

初始化列表后,头尾哨兵节点创建完成,但默认为不可见,内部可见元素通过其他方法进行插入补充。
列表初始化

本文标题:数据结构-列表

文章作者:Lumo Wang

发布时间:2018年03月05日 - 14:03

最后更新:2019年04月17日 - 20:04

原始链接:https://luameows.github.io/2018/03/05/学习笔记-数据结构-列表/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~