这是数据结构类重新复习笔记的第 一 篇，同专题的其他文章可以移步：https://www.jianshu.com/nb/39256701

抽象数据类型（abstract data type，ADT）是带有一组操作的一些对象的集合。An abstract data type (ADT) is a set of objects together with a set of operations.

标准模板库（Standard Template Library，SLT）。实现了ADT等数据结构，这些数据结构被称为集合（collection）或者容器（container）

表（List）

表的实现方式

• 静态表：利用数组实现
• 动态表：利用链表实现

表的常用操作

• printList：遍历、打印整个表
• makeEmpty：将整个表清空
• find：在表中查找某个元素
• insert：向表中插入某个元素
• remove：从表中移除某个元素
• findKth：查找表中的第k个元素
• next：返回某个元素的下一个元素
• previous：返回某个元素的上一个元素

表的两种简单形式

简单链表实现

简单链表

双向链表

双向链表

表的两种重要操作

链表的插入

链表的插入

链表的删除

链表的删除

时间复杂度

基本操作	静态 数组实现	动态 链表实现
printList	O(n)	O(n)
makeEmpty	O(n)	O(1)
find	O(1)	O(i)
insert	O(n)	O(1)
remove	O(n)	O(1)
findKth	O(1)	O(i)
next	O(1)	O(1)
previous	O(1)	O(i)

STL中的向量和表

表AST的实现方式

表ADT有两种流行的实现：

• vector：给出了表ADT的可增长的数组实现

  • 优点：利于索引（常量时间）
  • 缺点：插入新项或删除已有项代价昂贵（除非操作发生在vector的末尾）；查找效率低

• list：提供了表ADT的双向链表实现

  • 优点：如果发生变化的位置已知，插入新项和删除已有项代价很小
  • 缺点：不容易索引；查找效率低

方法

• 所有STL容器都适用的方法
  • int size() const：返回容器内的元素个数
  • void clear()：删除容器中所有的元素
  • bool empty()：如果容器没有元素，返回 true，否则返回 false
• vector 和 list 同时支持的方法
  • void push_back(const Object & x)：在表的末尾添加 x
  • void pop_back( )：删除表的末尾的对象
  • const Object & back( ) const：返回表的末尾的对象（也提供返回引用的修改函数）
  • const Object & front( ) const：返回表的前端的对象（也提供返回引用的修改函数）
• vector 单独支持的方法
  • Object & operator [ ] (int idx)：返回 vector 中 idx 索引位置的对象，不包含边界检测（也提供返回常量引用的访问函数）
  • Object & at (int iax)：返回 vector 中 i 索引位置的对象，包含边界检测（也提供返回常量引用的访问函数）
  • int capacity( ) const：返回 vector 的内部容量
  • void reserve(int new Capacity)：设定 vector 的新容量。如果已有良好的估计的话，这可以避免对 vector 进行扩展
• list 单独支持的方法
  • void push_front(const Object & x)：在list的前端添加x
  • void pop_front()：在list的前端删除对象

迭代器

在STL中，使用迭代器（内置类型 iterator）给出数据在表中的位置。通常可以使用对应的模板来声明 iterator：

STLType<dataType>::iterator

获得迭代器

SLT的所有容器都拥有如下的方法可以获得容器中指向的第一个和终止标志的迭代器：

• iterator begin()：返回指向容器的第一项的一个适当的迭代器
• iterator end()：返回指向容器的终止标志（容器中最后一项的后面的位置）的一个适当的迭代器。（这里比较特殊，是指向的容器的“边界之外”）

两种方法均可以根据所指向的容器类型返回一个恰当的迭代器，所以可以使用 auto 来声明它们，当你不知道应该如何声明的时候：

auto myIterator = STLCollection.begin();

迭代器方法

迭代器很多方法都来自于运算符的重载

• =：赋值
• itr++和++itr：推进迭代器itr至下一个位置，前缀和后缀两种形式都允许
• *itr：返回存储在迭代器itr指定位置的对象的引用。
• itx1==itx2：如果itr1和itr2都指向同一个位置就返回true，否则，返回fa1se
• itr1!=itr2：如果ix1和itr2都指向不同位置就返回true，否则，返回fase

从而，利用迭代器打印STL容器的方式如下：

for(vector<int>::iterator itr=v.begin(); itr != v.end(); ++itr)
  cout<<*itr<<endl;

vector<int>::iterator itr=v.begin();
while(itr!=v.end())
  cout<<*itr<<endl;

需要迭代器的表方法

一些表中常用的需要使用迭代器的容器方法：

• iterator insert(iterator pos, const Object & x)：添加x到表中迭代器pos所指向的位置之前的位置。对1ist是常量时间操作，对vector则不是。返回值是一个指向插入项位置的迭代器
• iterator erase(iterator pos)：删除迭代器所给出位置的对象。对1ist是常量时间操作，对vector不是。返回值是调用之前pos所指向元素的下一个元素的位置。这个操作使pos失效。pos不再有用，因为它所指向的容器变量已经被删除了
• iterator erase(iterator start, iterator end)：删除所有的从位置start开始直到位置end(但是不包括end)的所有元素

迭代器的分类

• 正向迭代器：containerType::iterator itr;
• 常量正向迭代器（不可更改）：containerType::const_iterator itr;
• 反向迭代器：containerType::reverse_iterator itr;
• 常量反向迭代器：containerType::const_reverse_iterator itr;

迭代器的参考：http://www.cplusplus.com/reference/iterator/

---

转载请注明出处，本文永久更新链接：https://blogs.littlegenius.xin/2019/08/08/【数据结构】一表与迭代器/