C++单链表对环的操作

发布时间：2020-12-16 07:43:03 所属栏目：百科来源：网络整理

导读：今天PHP站长网 52php.cn把收集自互联网的代码分享给大家，仅供参考。 #include iostream using namespace std; templatetypename _Ty class Node { public: Node(_Ty _X=_Ty()):_Data(_X),_Next(NULL){} int _Data; Node_

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

    #include <iostream>  
    using namespace std;  
      
    template<typename _Ty>  
    class Node  
    {  
        public:  
        Node(_Ty _X=_Ty()):_Data(_X),_Next(NULL){}  
        int _Data;  
        Node<_Ty> *_Next;  
    };  
      
    template<typename _Ty>  
    class List  
    {  
        public:  
        List()  
        {  
            _First = new Node<_Ty>();  
        }  
        void Insert(int _X)  
        {  
            Node<_Ty> *_S = new Node<_Ty>(_X);  
            _S->_Next = _First->_Next;  
            _First->_Next = _S;  
        }  
        Node<_Ty>* IsCircle()//判断是否是环，并且返回第一次相遇节点地址  
        {  
            Node<_Ty> *_P= _First;  
            Node<_Ty> *_Q= _First;  
            while(_P!=NULL && _P->_Next!=NULL)  
            {  
                _P=_P->_Next->_Next;  
                _Q=_Q->_Next;  
                if(_P==_Q)  
                      return _P;  
            }  
            return NULL;  
        }  
        void SetCircle(int _X)//设置环的位置。  
        {  
            Node<_Ty>* _P = _First;  
            Node<_Ty>*_Q = _First;  
            while(_Q->_Next!=NULL)  
            {  
                _Q=_Q->_Next;  
            }  
            for(int _I=0;_I<_X;_I++)  
            {  
                _P=_P->_Next;  
            }  
            _Q->_Next=_P;  
        }  
        int GetCircleLength()//找环的大小  
        {  
            Node<_Ty> *_P = _First;  
            Node<_Ty> *_Q = _First;  
            int _A=0;  
            while(1)  
            {     
                _P=_P->_Next->_Next;  
                _Q=_Q->_Next;  
                _A++;  
                if(_P==_Q)  
                    break;    
            }  
            return 2*_A-_A;  
        }  
        int GetCircle()//得到环点到开始节点的节点个数.。  
        {  
            Node<_Ty> *_P = IsCircle();  
            Node<_Ty> *_Q = _First;  
            int _A=0;  
            while(_P!=_Q)  
            {  
                _P=_P->_Next;  
                _Q=_Q->_Next;  
                _A++;  
            }  
            return _A;  
        }  
    /*   
    void Show() 
        { 
            Node<_Ty> *_P = _First; 
            while(_P->_Next!=NULL) 
            { 
                cout<<_P->_Next->_Data<<"  "; 
                _P=_P->_Next; 
            } 
            cout<<endl; 
        }*/  
        private:  
        Node<_Ty> *_First;  
    };  
    int main()  
    {  
            List<int> list;  
            for(int i=0;i<20;i++)  
            {  
                list.Insert(i);  
            }  
            list.SetCircle(10);//设置环的位置  
            if(list.IsCircle())  
            {  
                cout<<"有环！"<<endl;  
            }  
            else  
            {  
                cout<<"无环"<<endl;  
            }  
         cout<<"环的位置是:"<<list.GetCircle()<<endl;    
         cout<<"环的长度是:"<<list.GetCircleLength()<<endl;  
         return 0;  
    }

?????????? 3.环的长度就是第一次快慢指针相遇时慢指针所走过的节点数，因为快指针速度是慢指针的2倍，快指针路程-慢指针路程=环大小。

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!