表：c++ 数组和链表（图解）

1表 是什么？

表中的第一个元素是A，而最后一个元素是Ax-1。我们将不定义A的前驱元，也不定义Ax-;的后继元。元素A,在表中的位置( position)为i。为了简单起见，我们在讨论中将假设表中的元素是整数，但一般说来任意的复杂元素也是允许的（而且很容易由类模板来处理)。

1.1表 由数组实现

一片连续的储存空间实现 表 如图：

 优点：

1.数组实现使得printList以线性时间执行，而findxth则花费常数时间，这是最好的结果

缺点

2.插入和删除的花费却有可能是昂贵的，这取决于插入和删除发生的位置。在最坏的情况下，在位置0（换句话说是在表的前面)插入需要将整个数组后移--个位置以空出空间来;而删除第-一个元素则需要将表中的所有元素前移·个位置，因此这两种操作的最坏情况为O(N)。平均来看，这两种运算都需要移动表的一半的元素，因此仍然需要线性时间。另-方面，如果所有的操作都发生在表的末尾,就不需要移动任何元素，那么添加和删除的操作都花费O(1)的时间。

1.2表 由链表实现

链表不是一个连续的储存空间

 缺点：

为了执行printList ()或find(x)，我们只要从表的第一个结点开始然后用next链遍历该表即可。与数组实现--样,这种操作显然是花费线性时间的,但是这个常数可能比用数组实现时要大。findKth操作不如数组实现时的效率高; findKth(i)花费O(i)的时间并以明显的方式遍历链表而完成。
优点：

删除：修改一个next就行啦

 插入：

 假设链接到链表前面的链接存在，那么，添加或删除第一项的特殊情况对应常量的时间。至于在链表的末尾添加(在最后一项后添加新项)的特殊情况，如果链接到最后项的链接存在的话，也是消耗常量的时间。这样，典型的链表保持至表的两端的链接。删除最后一项有点麻烦，因为必须找到最后项前面的项，更改其next链接到nullptr，然后更新这个保持为最后一项的链接。在经典的链表里每个结点存储指向下一结点的链接，但是没有提供关于上一个结点的任何信息。

双向链表：

 

2.STL中的向量和表

表（Abstract Data Type）ADT有两个流行的实现。

vector给出了表ADT的可增长的数组实现。使用vector的优点在于其在常量的时间里是可索引的。缺点是插入新项或删除已有项的代价是昂贵的，除非是这些操作发生在vector的末尾。

list提供了表ADT的双向链表实现。使用list的优点是，如果变化发生的位置已知的话，插入新项和删除已有项的代价是很小的。缺点是list不容易索引。

vector和list两者在查找时效率都很低

int size() const;//返回容器元素个数
void clear();//删除
bool empty();//判断容器没有元素
 
void push_back(const object& x)
void pop_back();
 
const object &back() const;
const object &front() const;
 
//list 实现的是双向链表 允许在前端
 
void pop_front()
void push_front()
 
//
object& operator[](int ind)//不包含边界检测
object& at(ind)//包含边界检测
int capacity()//返回容量
void reserve(int new capacity)

2.1迭代器

一些表的操作，例如那些在表的中部进行插入和删除的操作，需要位置标记。

在STL中，通过内置类型iterator来给出位置

2.1.1获取迭代器

iterator begin();//返回第一个

iterator end() //返回第二个
 

2.1.2迭代器方法

itr++和++itr:推进迭代器itr至下一个位置。前缀和后缀两种形式都是允许的。

*itr:返回存储在迭代器itr指定位置的对象的引用。返回的引用或许能、或许不能被修改（后面我们将讨论这些细节)。

itrl==itr2:如果itr1和itr2都指向同一个位置就返回true，否则，返回false。

itr1 !=itr2:如果itr1和itr2都指向不同位置就返回true，否则，返回false。

2.1.3需要迭代器的操作

iterator insert( iterator pos，const object & x):添加x到表中迭代器pos所指向的位置之前的位置。这对list是常量时间操作，但是对vector则不是。返回值是一个指向插入项位置的迭代器。

iterator erase( iterator pos):删除迭代器所给出位置的对象。这对list来说是常量时间操作,但对vector则不是。返回值是调用之前pos所指向元素的下一个元素的位置。这个操作使pos失效。pos不再有用，因为它所指向的容器变量已经被删除了。

iterator erase( iterator start, iterator end):删除所有的从位置start开始、直到位置end（但是不包括end）的所有元素。注意，整个表的删除可以调用c.erase( c.begin( ) . c.end ( ) ) .

 2.1.4 const_iterator

*itr的结果不只是迭代器指向的项的值，也是该项本身。

template<typename Container,typename object>
void change(Container &c,const Object& newValue)
{
  using auto itr=c.begin();
  while(itr!=c.end())
   *itr++=newValue;
}

如果这段代码是合法的话，那么list的定常性就完全没有任何意义了，因为改变起来太容易了。这段代码是非法的，并且不会被编译。STL提供的解决方案是每一个集合不仅包含嵌套的iterator类型，也包含嵌套的const_iterator类型。iterator和const_iterator之间的主要区别是: const_iterator的operator*返回常量引用，这样const_iterator的*itr就不能出现在城值语句的左边。
 

template<typename Container>
void  removeEveryOtherItem(Container& lst)
{
 auto itr=lst.begin();
 while(itr!=lst.end())
{
  itr=lst.earse(itr);
  if(itr!=erase())
   ++itr;
}
}

3.4 数组的实现 -vector

3.4.1c++的数组特性

数组就是指向块内存的指针变量;实际的数组的大小必须由程序员单独确定。

内存块可以通过new[]来分配，但是相应地也就必须用delete[]来释放。

内存块的大小不能改变（但是可以定义一个新的具有更大内存块的数组，并且用原来的数组来将其初始化，然后原来的内存块就可以释放了)。

3.4.2 vetcor

(1) vector将仍然是基本数组（通过一个指针变量来指向分配的内存块)。数组的容量和当前的数组项数目存储在vector里。

(2) vector将通过实现“三大函数”，为复制构造函数和operator=提供深复制，同时也提供析构函数来回收基本数组。

(3) vector将提供resize例程来改变vector的大小(通常是更大的数);提供reserve例程来改变vector的容量（通常是更大的数)。容量的改变是通过为基本数组分配一个新的内存块，然后复制旧内存块的内容到新块中，再释放旧块的内存来实现的。（）

(4) vector将提供operator[]的实现（正如1.7.2节中所提到的，operator[]典型的实现有访问函数和修改函数两个版本)。

(5) vector将提供基本的例程，例如size、empty、clear(它们是典型的一行例程)、back、pop_back和push_back。如果大小和容量都是一样的话，push_back例程将调用reserve来增大vector的容量。

(6) vector将支持嵌套的iterator和const_iterator类型，并且提供关联的begin和end方法。

3 表   链表的实现

(1) List类本身。包含连接到表两端的链接、表的大小以及-一系列的方法。

(2) Node类。该类看起来像是私有的嵌套类。一个结点包含数据和用来指向其前和其后的结点的指针，以及适当的构造函数。

(3) const_iterator类。该类抽象了位置的概念，是一个公有的嵌套类。const_iterator存储指向当前结点的指针，并且提供基本迭代器操作的实现，以及所有的重载操作符，例如=、==、!=和++。

(4) iterator类。该类抽象了位置的概念，是一个公有的嵌套类。除了operator*操作返回所指向项的引用，而不是该项的常量引用的功能外，iterator具有与const_iterator相同的功能。--个重要的技术点是iterator可以用于任何需要使用const_iterator的例程里，反之则不是。换句话说，iterator就是const_iterator。

插入：

template<typename object>
struct Node
{
 object data;
 Node* prev;
 Node* next;
 Node( const object & d = object(),
 Node *p = NULL，
 Node *n = NULL ): data (d),  prev(p) ,next(n)
 { }
};
 
 
iterator insert(iterator itr,const Object& x)
{
   Node *p=itr.current;//确定位置
   theSize++;
   return iterator(p->pre=p->pre->next=new Node(x,p->pre,p));
 
   
}

 Node* newnode=new Node(x,p->prev,p)//1,2

p->prev=p->prev->next=newnode//;

删除:

 p->prev->next=p->next;

p->next->prev=p->prev