C++基础语法:STL之容器(4)--序列容器中的list(一)

前言

       "打牢基础,万事不愁" .C++的基础语法的学习

引入

        序列容器的学习.以<C++ Prime Plus> 6th Edition(以下称"本书")内容理解

        本书中容器内容不多只有几页.最好是有数据结构方面的知识积累,如果没有在学的同时补上.

        序列容器回顾:序列容器内元素按严格线性顺序排列,至少是正向迭代器(含以上).序列容器包括deque(双端队列),forward_list(单链表),list(双向链表),queue(队列),priority_queue(优先队列),stack(栈),vector(动态数组),array(替代数组的容器

list(双向链表) 

        list所占篇幅相对其他容器类算比较大的,而且有专属的api介绍.

        list双向链表,和单链表比较起来,在结点上多了个指向前面一个元素的指针.

        本书内容解读 

        第1部分:  list模板类（在list头文件中声明）表示双向链表。除了第一个和最后一个元素外，每个元素都与前后的元素相链接,这意味着可以双向遍历链表。list和vector之间关键的区别在于，list在链表中任一位置进行插入和删除的时间都是固定的（vector模板提供了除结尾处外的线性时间的插入和删除,在结尾处,它提供了固定时间的插入和删除）。因此,vector强调的是通过随机访问进行快速访问,而list强调的是元素的快速插入和删除 (本书原话)

         ----蓝色部分是list应用场景,切记

         ----代码和解读:

        注意:下列代码为了练手,试图重现逻辑,不保证准确.          

template<class T>
class list{enum{MAX=10}int lsize;                //list最大元素数量int items;                //list内当前的元素个数class Node{               //声明结点类public:                   //结点数据向外部类公开T t;Node *front;Node *next;Node(T val):t(val),front(0),next(0){}Node(){}              //默认构造函数,为初始化时使用}Node* first;Node* last;
public:list(int num=MAX);        //构造函数   void add(Node* n,T& t);   //添加元素t到结点n后面T remove(Node* n);        //删除地址为n的结点
}

        1>构造函数,建立初始的list

        说明:first按照"头结点"定义,数据域为空的结点,初始化时没有元素,所以last也指向头结点.

template<class T>
list::list(int num=MAX):lsize(num){ //初始化list,没有元素时的情况items=0;                        //初始时元素个数为0Node *newNode=new Node;         //创建数据域为空的结点first=newNode;                  //头结点指向空结点;last=newNode;                   //末结点指向空结点;//  last->next=first;               //如果加上这句,末结点后面的结点指向头结点,形成环状list//这里不加,仍然是一根链条似的list,加了变复杂用处也不大,不加
}

        2>添加元素

        把结点地址作为参数,作为插入元素的条件,向序列要求函数中的迭代器靠拢.

template<class T>
void list<T>::add(Node* n,T& t){Node* newNode=new Node(t);    //生成新结点,传入数据
/*新结点后面是谁*/newNode->next=n->next;n->next->front=newNode;
/*新结点在谁后面*/n->next=newNode;newNode->front=n;
/*第一次插入后,新结点成为尾结点,并在头结点后面*/if(items==0){                //第一次插入时情况:区分first和lastnewNode->next=nullptr;   //新结点后面指空last=newNode;            //新结点成了尾结点first->next=newNode;     //first当上了头结点newNode->front=first;    //两个方向说明first当上了头结点}            
//  if(n==first)
//      first->next=newNode;     //插入在头结点之后,前面代码已符合不用重复if(n==last)                 last=newNode;            //如果在末尾插入,尾结点指向新结点仍是尾结点items++;                     //list元素个数加1
}

        3>删除某个位置的结点 

template<class T>
T list<T>::remove(Node* n){Node* tmp=n;                //标识要删除的结点/*把要删除的结点从list里面剥离出来*/n->next->front=n->front;    //该结点后面结点的front指向该结点前面那个结点n->front->next=n->next;     //该结点前面那个结点的next指向该结点后面if(n==last)                 //如果删除的是尾结点last=n->front;         //尾结点指向删除结点的前一个结点T t=tmp->t;                 //标识结点的数据取出来delete tmp;                 //删除标识结点items--;                    //删除结点,元素个数减1return t;                   //返回原结点内数据
}        

================================内容分割线=================================

做几个小分析:

        1.构造函数用了两个,如果只有下面这个,建立空结点不知道能不能成功,笔者未尝试.

          在C语言中,声明一个结构体并且malloc,好像不用给数据也没错,C++的检查更严格.

Node(T val):t(val),front(0),next(0){}

        2.关于环状list

          如果采用"环状"list,那么后面的代码中last不能指空,而要指向first.其他算法可能会有区别

           在插入,删除或者查找中,环状list未必能达到好的效果.考虑到一种场景:list很长,查询数据时查一半不找了,往回查找走,这时考虑用环状list.如图:

     有兴趣可以尝试做个环状list,再写个查找算法.

     不过数据多了有更好的选择,比如二叉树等,所以感觉实用性不大.

        3. 头结点  

        头结点实际上是"人造"的.他的用途是方便元素在头部插入和删除.是否选择用头结点在于程序员.如果不做头结点,让头部插入的结点成为首个结点,那么代码要做一些修改,代码要多一点.

        4.第一次插入时的描述

        以下是函数add里的部分代码:

/*第一次插入后,新结点成为尾结点,并在头结点后面*/if(items==0){                //第一次插入时情况:区分first和lastnewNode->next=nullptr;   //新结点后面指空last=newNode;            //新结点成了尾结点first->next=newNode;     //first当上了头结点newNode->front=first;    //两个方向说明first当上了头结点}

        参照本书P614,链队列的"入队"算法enque,开始时first和last都指向同一个空结点,将第一次插入和其他次插入分开,才可以在逻辑上区分first和last,保证后面的程序正确. 

        5.程序中的"一般"和"特别"

        add中的部分代码 

//  if(n==first)
//      first->next=newNode;     //插入在头结点之后,前面代码已符合不用重复if(n==last)                 last=newNode;            //如果在末尾插入,尾结点指向新结点仍是尾结点

        当写完add后,如果想在头结点后插入元素,代入first,发现逻辑仍成立,所以注释部分属于多余描述;而当在末尾结点插入元素,代入last,函数执行完毕后发现尾结点位置没变,所以给了if做补充. 

        函数代入的形参可以被看作是所有可能的组合 ,表示"一般"性.当一般性不能满足所有情况,需要用"特殊"的描述做补充,这也是程序调试的重要性所在.

        6.尾结点last为什么有时候需要有时候不需要?

        对比以前的数据结构单链表C++基础语法:链表和数据结构-CSDN博客和链队列,他们一个没有尾结点,一个有尾结点,list也有尾结点.而链队列和list的共同特征是需要在"尾部"插入和删除元素,因此定义了尾结点last并实现了他.而使用"头插法"的单链表既没有"尾部"的概念,也没有"尾结点"存在.与此相对应的,头结点(指向首个元素的结点)是必须存在的,因为靠他遍历到容器内所有数据.

        同时定义了list的最大元素个数items,但并没有使用他,所以本例的链表可以无限长 

        结论:容器里的属性是根据需要定义并实现的

        7.迭代器

        此前迭代器让人挠头,迭代器类里的属性复刻了容器里的数据(因为容器里都是数据集合,所以属性是容器集合的指针),所以迭代器实际上是对数据的二重访问和修改.提升了"同一性"(每个容器里都有个迭代器类).在容器类里对元素的增删改搬到迭代器里去了,然后做接口被容器类对象访问.

        迭代器做参数,先转化成对应的指针即可.本例的指针做参数和迭代器做参数已非常接近 

        8.函数的"冗余"

        在序列函数中,有push_front()函数,为了在容器头部插入数据,有了add()函数也一样可以实现.为什么要这样做呢?

        原因和"迭代器"一样,他是为了同属于序列容器的"同一性"提供的api,而且也容易实现,把参数传给add()就行了. 

================================内容分割线================================ 

         第2部分:与vector相似,list也是可反转容器。与vector不同的是,list不支持数组表示法和随机访问。与矢量迭代器不同,从容器中插入或删除元素之后,链表迭代器指向元素将不变。我们来解释一下这句话。例如,假设有一个指向vector容器第5个元素的迭代器,并在容器的起始处插入一 个元素。此时,必须移动其他所有元素,以便腾出位置,因此插入后,第5个元素包含的值将是以前第4个元素的值。因此,迭代器指向的位置不变，但数据不同。然后,在链表中插入新元素并不会移动已有的元素，而只是修改链接信息。指向某个元素的迭代器仍然指向该元素，但它链接的元素可能与以前不同。

        ----解读:这段比较容易理解:如果支持随机访问,那么两次访问到的数据不能改变.而list(包括其他链表)在插入和删除后,原数据的位置发生改变,再次用位置访问到的数据和之前不一样了,所以不能随机查找,而只能通过遍历来搜寻.

小结

        list双向链表的一些理解.