C++基础语法:STL之容器(5)--序列容器中的list(二)
前言
"打牢基础,万事不愁" .C++的基础语法的学习
引入
序列容器的学习.以<C++ Prime Plus> 6th Edition(以下称"本书")内容理解
本书中容器内容不多只有几页.最好是有数据结构方面的知识积累,如果没有在学的同时补上
接上一篇C++基础语法:STL之容器(4)--序列容器中的list(一)-CSDN博客
list(双向链表)
本书内容解读
第3部分: 除序列和可反转容器的函数外,list模板类还包含了链表专用的成员函数。表16.9列出了其中一些（有关STL方法和函数的完整列表，请参见附录G）。通常不必担心Alloc模板参数，因为它有默认值。
----看见了STL中的list,发现和自己写的不太一样,他有两个参数,表示为list<T,Alloc>,不过感觉问题也不是很大,代码主要说的是思路.
照着成员函数的说明当成需求,前面是给出的函数原型,试着写一写算法.
merge()合并算法看起来有点复杂,不写;remove前面有个相同名称的函数,因为想要调用之前的remove()函数,所以把他改为removeValue;splice()要用到迭代器,不写.把前面的容器类定义拿过来
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的结点//下面三个是将要实现的函数void removeValue(const T& val); //删除val的所有实例void sort(); //使用<运算符对链表进行排序Node* findNode(const T& t); //排序中用到的函数void unique(); //将连续的相同元素压缩成单个元素
}
注意:下列代码为了练手,试图重现逻辑,不保证准确.
1>删除val的所有实例
思路:遍历list,找到一个删一个.因为已定义了remove(Node* n),所以省事一些.
template<class T>
void list<T>::removeValue(const T& val){if(items==0){ //空链表直接返回std::cout<<"链表内没有数据"<<std::endl;return;}list<T>::Node* p=first; //声明指针指向链表头结点bool flag=false; //声明标志位; while(p){ //遍历链表if(p->t==val){remove(p); //调用删除结点函数flag=true; //标志位改变}p=p->next; //指针指向下一个结点}if(flag==true)std::cout<<"数据已全部删除"<<std::endl; elsestd::cout<<"链表内没有您想删除的数据"<<std::endl;
}2>sort排序,从小到大排序,最小的放链表前面
思路:要排序,我只知道冒泡排序,链表排序可以仿照冒泡排序算法吗?
把链表"打散"成数组,然后给数组排序,接着把排好序后的结点重新找出来,依次挂到first后面.
问题来了,现在的函数只能从结点访问到数据t,还没有从数据t访问到结点的函数,加一个呗
template<class T>
Node* list<T>::findNode(const T& t){ //结点查找函数list<T>::Node * p=first;while(p){if(p->t==t)std::cout<<"您查找的数据已找到"<<std::endl;return p;p=p->next; //指向下一个结点}std::cout<<"您查找的数据不存在"<<std::endl;return nullptr;
}接下来按照冒泡排序的思路,把数据从小到大排列
template<class T>
void list<T>::sort(){ //排序算法vector<T> a;List<T>::Node* p=first;while(p){a.push_back(p->t); //元素取出来放进vector里p=p->next; //指针指向下一个结点}/*以下是冒泡排序*/for(int i=0;i<items-1;i++){for(int j=0;j<items-i-1;j++){if(a[j]>=a[j+1]){T tmp;tmp=a[j+1];a[j+1]=a[j];a[j]=tmp;}}}//到这里排序完成,从小到大,从a[0]到a[items-1]/*还原成结点,并依次挂到first后面*/Node* tmp=first; //声明临时结点tmp帮first整理,用上面的p也行for(int i=0;i<items;i++){
//两句说明结点后面是tmp->nextfindNode(a[i])->next=tmp->next; tmp->next->front=findNode(a[i]);
//两句说明结点前面是tmp; tmp->next=findNode(a[i]); findNode(a[i])->front=tmp;
//tmp结点指向新结点,为下次整理做准备;tmp=findNode(a[i]); } last=tmp; //最后让last指向tmp;
}----然而问题又来了,list并不检查两个相同的值,上面的findNode函数有bug该怎么办?想解决肯定是有办法的,比如给Node结点来个编号(题外话:黑皮书上有讲,那是本好书但是挺难)
class Node{ //声明结点类static int num; //静态变量,给对象编号用public: //结点数据向外部类公开int id;T t;Node *front;Node *next;Node(T val):t(val),front(0),next(0),id(num++){}Node():id(num++){} //默认构造函数,为初始化时使用}但这样要耗费空间,查找结点代码也要改动,比较麻烦.所以我建议在排序之前先把多余的重复值去掉,也就是先调用下面要写的的unique()函数.
----除了这个问题还有个问题:让类型T的元素怎么比较?重载运算符吗?
/*???????????*/
bool operator<(T& t){ //起不了作用return *this < t
}如果从完全泛型的角度来讲,不可能成立.只能在调用时做出约束,如int,char,double等类型自带大小判断的才可以调用sort().
如果对象中有部分元素是可以排序的,如有一个int属性,那么按照前面的思路,让其反向查找排序,这不是容器的事,应该在外面定义函数来解决.
class Person{int age; //这个可以排序string name;
}3>压缩链表,去掉多余元素
思路:用一个集合a存储链表里的数据,遍历链表的同时,遍历集合a.当新元素在集合a里找到时,删除,当没有找到时,加入集合a.
template<class T>
void list<T>::unique(){ //将连续的相同元素压缩成单个元素list<T>::Node* p=first;vector<T> a;while(p){for(pt=a.begin();pt!=a.end();pt++){if(p->t==*pt){remove(p); //调用删除结点函数}a.push_back(p->t); //元素取出来放进vector里}p=p->next; //指针指向下一个结点}
} 此外本书P699举了个例子,讲几种api的使用,看看即可.
链表梳理
链表的定义和使用流程:数据→结点→链表.1.把数据放入结点;2.结点指针生成链表.
链表是一个结点指针的集合,指针元素之间用结点指针相连接.头结点是链表的入口.
链表的难点是区分指针变量和指针常量.
链表里的元素是结点指针,他们是常量,要访问他们或者修改他们用的是指针变量.常见的指针变量有头结点,尾结点.他们时刻要保证逻辑正确,也是算法的保证.
后记
一天更了两篇,大热天还觉得挺兴奋.数据结构应该算是编程的分水岭,如果真的喜欢会享受代码和写作的过程.如果一时学不进去也挺难受,但也不要着急慢慢来,许多人也经历过那个过程.一起加油.