c++中的链表

建议阅览本篇前先看看C语言中的链表操作及内存问题，本篇将直接从内存与指针方面摄入c++链表；

动态数据结构

指针常量&&常量指针

（链表，递归类型定义，哈希表，数组与指针）
以上数据结构是创建更多复杂对象的基石，
c++中，一个动态数组称作一个矢量；其中也有一个列表，字符串等。

大致规划：动态数组（实际是一个动态堆栈）->链表及字符缓冲器->哈希表->字符串表（有效保存和读取字符串的数据结构）

今天，先谈谈对其中 “链表” 的理解与感悟：

链表是一种针对快速定时，预先挂起及线性时间（与列表大小成正比）检索的动态数据结构。链表中包含链接（个人认为，就是C语言中常说的：节点）。假如我们想在列表中保存一些整数ID，链接将包含ID的字段及指向下一个链接的指针。

列表中的最后一个链接包含NULL（0）指针_pNext，这是列表的终止符。一个NULL指针永远不会是一个有效指针，也就是说，它不能反作用。但是，它可检查是否为0.

list

下面是类Link：

class Link
{
public:
    Link(Link* pNext,int id)
    :_pNext(pNext),_id(id){}
    Link * Next() const { return _pNext; }
    int Id() const { return _id; }
private:
    int _id;
    Link *_pNext;
};

注意，这里Link的定义为自引用——一个Link包含一个指向Link的指针。编译器唯一需要的就是类型的声明。在这里是第一行：

class Link;

正作为这样的一个声明。
链表保存指向第一个链接的指针。从概念上讲，列表是一个与链接不同的对象。首先，它们的借口不一样。程序员可以给列表进行添加，删除，查找等操作，但这些对于Link的方法来说都是没有意义的。在OOP模式中要尽量避免某些递归概念。

从_pHead指向的第一个连接开始，我们可以跟随指针_pNext遍历整个列表。
在起始时，列表为空切指针初始化为0.

class List
{
public:
    List():_pHead(0) {}
    ~List();
    void Add(int id);
    Link const * GetHead() const { return _pHead; }
private:
    Link* _pHead;
};

通过分配一个新链接并且用ID和指向下一个项目的指针初始化给列表添加一个新的ID。下一个项目为先前位于列表起始处的链接（_pHead指向它）。新链接变成了列表的头，而且_pHead指向它（指针赋值），此过程称作预先挂起

void List::Add(int id)
{
    //添加在列表头
    Link * pLink=new Link(_pHead,id);
    _pHead=pLink;
}

因为列表动态增长，所以，每个新链接必须使用运算符new来分配。当分配一个新对象时，它的构造函数被自动调用。这就是为什么我们再new Link(_pHead,id)中传递构造函数参数的原因。
列表迭代，即逐个元素经过整个列表。

bool List::Find(int id) const
{
    for(Link const * pLink=GetHead();
        pLink!=0;
        pLink=pLink->Next())
    {
        if(pLink->Id()==id)
            return true;
    }
    return false;
}

此列表有一个构析函数，其中释放了所有的链接。此列表拥有此链接。

List::~List()
{
    //释放列表
    while(_pHead!=0)
    {
        Link* pLinkTmp=_pHead;
        _pHead=_pHead->Next();   //取消链接pLink
        delete pLinkTmp;
    }
}

这里要再次说明，有一些事是不能用引用完成的。
有一种链表析构函数的更简单，递归性实现的方式：

List::~List()
{
    delete _pHead;
}
Link::~Link()
{
    delete _pNext;
}

当销毁一个链表是时，它删除了它的后续者，后续者又会删除它的后续者，如此，当它到达终止空指针时，递归会自动停止，因为对于一个空指针而言没有任何析构函数可调用。
这里插一句，由上可见，递归解决方案的优点其简单性。

我们顺便来看一下以上内容中的const：
对于指向常量的指针有一个等价语法：

const Link * pLink;   //指向常量的指针

而且当然有：

const Link * const pLink=pInitPtr;     //指向常量的常量指针ptr

产生如此混淆的原因是我们品势从左至右的阅读文本习惯，而C语言等是写给计算机的，我们可以这样理解：
如下：

Link const * pLink;

同样，

Link * const pLink;

好吧，先告辞了诸位，我要消化会儿去。。。