阅读量:0
前言
"打牢基础,万事不愁" .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; else std::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->next findNode(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.结点指针生成链表.
链表是一个结点指针的集合,指针元素之间用结点指针相连接.头结点是链表的入口.
链表的难点是区分指针变量和指针常量.
链表里的元素是结点指针,他们是常量,要访问他们或者修改他们用的是指针变量.常见的指针变量有头结点,尾结点.他们时刻要保证逻辑正确,也是算法的保证.
后记
一天更了两篇,大热天还觉得挺兴奋.数据结构应该算是编程的分水岭,如果真的喜欢会享受代码和写作的过程.如果一时学不进去也挺难受,但也不要着急慢慢来,许多人也经历过那个过程.一起加油.
