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; 
    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.结点指针生成链表.

        链表是一个结点指针的集合,指针元素之间用结点指针相连接.头结点是链表的入口.

        链表的难点是区分指针变量和指针常量.

        链表里的元素是结点指针,他们是常量,要访问他们或者修改他们用的是指针变量.常见的指针变量有头结点,尾结点.他们时刻要保证逻辑正确,也是算法的保证. 

后记

        一天更了两篇,大热天还觉得挺兴奋.数据结构应该算是编程的分水岭,如果真的喜欢会享受代码和写作的过程.如果一时学不进去也挺难受,但也不要着急慢慢来,许多人也经历过那个过程.一起加油.