[TOC]

写在前面

本篇文章整理《数据结构（C++语言版）》关于列表这种线性结构知识点。
整个数据结构部分章节列表如下:
1 向量
-- 1.1 遍历
-- 1.2 唯一化
-- 1.3 查找
2 列表
-- 2.1 列表节点
---- 2.1.1前插入算法
-- 2.2 列表模板类
---- 2.2.1 列表初始化
3 栈
--3.1 栈应用
---- 3.1.1 括号匹配
---- 3.1.2 栈混洗甄别
---- 3.1.3 中缀表达式
4 队列

2 列表

在数据结构1——向量中介绍了线性表的两种形式：其一是物理地址与逻辑地址均连续，典型示例向量（Vector）结构；另一种是逻辑地址连续而物理地址不一定连续，典型示例列表（List）结构。
列表结构的基本组成单位是节点（node），各节点通过指针或引用彼此连接，构成逻辑连续的序列。

列表结构
正因为列表这一特性，一些静态操作，如寻秩访问、find等方法无法高效完成（物理地址不连续）；而相反的动态操作，如插入、删除等方法无须对后续元素一次进行移位，故可以高效完成。

2.1 列表节点

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

列表节点

#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) {}即为成员初始化列表。【注意：成员初始化顺序应按照类成员声明顺序】

2.1.1 前插入算法

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

前插入流程图

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;
}

2.2 列表模板类

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

列表结构

#include "ListNode.h"  //引入列表节点类

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

2.2.1 列表初始化

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

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;
}

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

列表初始化