C++基础语法:STL之容器(6)--序列容器中的forward_list

前言

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

引入

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

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

上一篇C++基础语法:链表和数据结构-CSDN博客中有对单链表做过分析,当时没用类模板,用普通类实现的容器,方法都一样(那边内容还多一点)所以可以结合看.

forward_list(单链表)

本书就一段话描述单链表.因为内容相对偏少.正如上一篇所说,就算只是链表,也有很多算法可以设计的.而且正因为基础,不要小看了他.

本书内容解读

C++11新增了容器类forward_list,它实现了单链表。在这种链表中,每个节点都只链接到下一个节点,而没有链接到前一个节点。因此 forward_list只需要正向迭代器,而不需要双向迭代器。因此,不同于 vector和list,forward_list是不可反转的容器。相比于list,forward_list更简单、更紧凑，但功能也更少。(本书原话)

----解读:最基本的链表

注意:以下代码已测试,但不要让插入个数超过允许范围,会产生异常

定义了构造函数,插入元素,弹出元素,打印链表,反转单链表的算法.

Single.h //容器定义

#include<iostream>
using namespace std;template<class T>
class SingleChain {                         //容器类定义enum { MAX = 20 };class Node {							//结点类public:									//特别注意声明为public,否则作用域无法被访问T t;Node* next;Node(T val) :t(val), next(0) {};Node() { next = 0; };				//默认构造函数};int items;								//当前元素个数int size;								//最大个数Node* head;								//头结点
public:SingleChain(int s = MAX) ;				//默认最大为20void insert(T t);						//插入元素bool pop();								//删除元素void print();							//打印链表void reverse(SingleChain<T>& t);		//反转容器
};template<class T>
SingleChain<T>::SingleChain(int s) {		//构造函数Node* newNode = new Node;				//head是头结点head = newNode;items = 0;size = s;
}template<class T>
void SingleChain<T>::insert(T t) {			//头插法插入元素Node* newNode = new Node(t);newNode->next = head->next;head->next = newNode;items++;
}template<class T>
bool SingleChain<T>::pop() {				//弹出if (items == 0)return false;Node* tmp = head->next;					//标记弹出结点,最后一个插入的结点head->next = head->next->next;			//剥离和链表的关系items--;delete tmp;								//释放结点return true;							//返回
}template<class T>
void SingleChain<T>::print() {				//打印链表值Node* p = head->next;					//头结点不打印while (p) {cout << p->t << endl;p = p->next;}
}template<class T>							//反转单链表
void SingleChain<T>::reverse(SingleChain<T>& t) {Node* p = (t.head)->next;while (p) {this->insert(p->t);p = p->next;}
}

main.cpp //测试代码

#include<iostream>	
#include"Single.h"int main(void) {SingleChain<int> a(5);a.insert(1);a.insert(2);a.insert(3);a.insert(4);cout << "添加元素后的链表为:" << endl;a.print();a.pop();cout << "弹出一个元素后的链表为:" << endl;a.print();SingleChain<int> b(5);b.reverse(a);cout << "反转后的链表为:" << endl;b.print();return 0;
}

运行结果:

添加元素后的链表为:
4
3
2
1
弹出一个元素后的链表为:
3
2
1
反转后的链表为:
1
2
3

反转单链表

内容介绍中原话"不同于vector和list，forward_list是不可反转的容器",但可以自己实现他.STL是伟大的发明,但他不是万能的.在发明了"迭代器"这一概念,给迭代器分功能后并应用到各种容器上以后,方便使用的同时也有不足的地方.比如这里的不可反转,可由程序员自己实现就是一例证.而且代码也不复杂

template<class T>							//反转单链表
void SingleChain<T>::reverse(SingleChain<T>& t) {Node* p = (t.head)->next;while (p) {this->insert(p->t);p = p->next;}
}

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

以下代码不可用

/*下列代码和下一行作用相同,报异常,原因未明*/
//template<class T>
//T SingleChain<T>::pop() {					//弹出
//	Node* tmp = head->next;					//标记弹出结点,最后一个插入的结点
//	head->next = head->next->next;			//剥离和链表的关系
//	T t = tmp->t;							//取出结点值
//	items--;
//	delete tmp;								//释放结点
//	return t;								//返回
//}

在设计弹出的时候,开始想把弹出结点值返回,结果出了异常,也找不到原因,有知道的朋友请帮忙,谢谢

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