网站谁做的比较好看的,优秀设计案例,联联周边游官网app下载,郑州建站模板搭建前言 打牢基础,万事不愁 .C的基础语法的学习
引入 序列容器的学习.以C Prime Plus 6th Edition(以下称本书)内容理解 本书中容器内容不多只有几页.最好是有数据结构方面的知识积累,如果没有在学的同时补上. 序列容器回顾:序列容器内元素按严格…前言 打牢基础,万事不愁 .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应用场景,切记 ----代码和解读: 注意:下列代码为了练手,试图重现逻辑,不保证准确.
templateclass T
class list{enum{MAX10}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 numMAX); //构造函数 void add(Node* n,T t); //添加元素t到结点n后面T remove(Node* n); //删除地址为n的结点
} 1构造函数,建立初始的list 说明:first按照头结点定义,数据域为空的结点,初始化时没有元素,所以last也指向头结点.
templateclass T
list::list(int numMAX):lsize(num){ //初始化list,没有元素时的情况items0; //初始时元素个数为0Node *newNodenew Node; //创建数据域为空的结点firstnewNode; //头结点指向空结点;lastnewNode; //末结点指向空结点;// last-nextfirst; //如果加上这句,末结点后面的结点指向头结点,形成环状list//这里不加,仍然是一根链条似的list,加了变复杂用处也不大,不加
} 2添加元素 把结点地址作为参数,作为插入元素的条件,向序列要求函数中的迭代器靠拢.
templateclass T
void listT::add(Node* n,T t){Node* newNodenew Node(t); //生成新结点,传入数据
/*新结点后面是谁*/newNode-nextn-next;n-next-frontnewNode;
/*新结点在谁后面*/n-nextnewNode;newNode-frontn;
/*第一次插入后,新结点成为尾结点,并在头结点后面*/if(items0){ //第一次插入时情况:区分first和lastnewNode-nextnullptr; //新结点后面指空lastnewNode; //新结点成了尾结点first-nextnewNode; //first当上了头结点newNode-frontfirst; //两个方向说明first当上了头结点}
// if(nfirst)
// first-nextnewNode; //插入在头结点之后,前面代码已符合不用重复if(nlast) lastnewNode; //如果在末尾插入,尾结点指向新结点仍是尾结点items; //list元素个数加1
} 3删除某个位置的结点
templateclass T
T listT::remove(Node* n){Node* tmpn; //标识要删除的结点/*把要删除的结点从list里面剥离出来*/n-next-frontn-front; //该结点后面结点的front指向该结点前面那个结点n-front-nextn-next; //该结点前面那个结点的next指向该结点后面if(nlast) //如果删除的是尾结点lastn-front; //尾结点指向删除结点的前一个结点T ttmp-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(items0){ //第一次插入时情况:区分first和lastnewNode-nextnullptr; //新结点后面指空lastnewNode; //新结点成了尾结点first-nextnewNode; //first当上了头结点newNode-frontfirst; //两个方向说明first当上了头结点} 参照本书P614,链队列的入队算法enque,开始时first和last都指向同一个空结点,将第一次插入和其他次插入分开,才可以在逻辑上区分first和last,保证后面的程序正确. 5.程序中的一般和特别 add中的部分代码
// if(nfirst)
// first-nextnewNode; //插入在头结点之后,前面代码已符合不用重复if(nlast) lastnewNode; //如果在末尾插入,尾结点指向新结点仍是尾结点 当写完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双向链表的一些理解.
