C++ 数据结构与算法（四）线性表之循环链表

迷南。 2021-11-26 08:44 254阅读 0赞

上一篇写了 双向链表，今天复习了循环链表，就写了个带有头结点的循环链表。具体实现如下：

**结点类文件（ListNode.h）：**

template<typename T> class CircularList;
    
    template<typename T>
    class ListNode
    {
    public:
        friend class CircularList<T>;
        ListNode():m_pnext(NULL)
        {
    
        }
        ListNode(const T data, ListNode<T>* pnext = NULL):m_data(data),m_pnext(pnext)
        {
    
        }
        ~ListNode()
        {
            m_pnext = NULL;
        }
    
    private:
        T m_data;
        ListNode<T>* m_pnext;
    };

**循环链表类文件（CircularList.h）：**

#include "ListNode.h"
    
    template<typename T>
    class CircularList
    {
    public:
        CircularList():head(new ListNode<T>())
        {
            head->m_pnext = head;
        }
        ~CircularList()
        {
            EmptyList();
            delete head;
        }
    public:
        void EmptyList();//清空链表
        int Length();//计算链表长度
        bool Insert(T item, int n = 0);//插入元素
        ListNode<T>* Find(int n);//查找第n个元素
        T Delete(int n);//删除第n个元素
        T GetData(int n);//获取第n个元素项
        void Print();//输出链表
    private:
        ListNode<T>* head;
    };
    template<typename T>
    void CircularList<T>::EmptyList()
    {
         //清空链表
        ListNode<T>* p = head, *pdel;
        while (p->m_pnext != head)
        {
            pdel = p->m_pnext;
            p->m_pnext = pdel->m_pnext;
            delete pdel;
        }
    }
    template<typename T>
    int CircularList<T>::Length()
    {
         //计算链表长度
        int count = 0;
        ListNode<T>* p = head;
        while (p->m_pnext  != head)
        {
            count ++ ;
            p = p->m_pnext;
        }
        return count;
    }
    template<typename T>
    bool CircularList<T>::Insert(T item, int n = 0)
    {
         //插入元素
        if(n < 0 || n > Length())
            return false;//n出界
        ListNode<T>* p = head;
        ListNode<T>* pnewnode = new ListNode<T>(item);
        if(pnewnode == NULL)
            return false;
        for(int i = 0 ;i< n;i ++)
        {
            p = p->m_pnext;
            if(p == head)
                return false;//n出界
        }
        pnewnode->m_pnext = p->m_pnext;
        p->m_pnext = pnewnode;
        return true;
    }
    template<typename T>
    ListNode<T>* CircularList<T>::Find(int n)
    {
         //查找第n个元素
        if(n < 0 || n > Length())
            return false;
        ListNode<T>* p = head;
        while(p != head)
        {
            p = p->m_pnext;
        }
        if(p == head)
            return NULL;
        return p;
    }
    template<typename T>
    T CircularList<T>::Delete(int n)
    {
         //删除第n个元素
        if(n < 0 || n > Length())
            return NULL;
        ListNode<T>* p  = head,*pdel;
        for(int i =0 ;i < n; i ++)
        {
            p = p->m_pnext;
        }
        pdel = p->m_pnext;
        p->m_pnext = pdel->m_pnext;
        T data = pdel->m_data;
        delete pdel;
        return data;
    }
    template<typename T>
    T CircularList<T>::GetData(int n)
    {
         //获取第n个元素项
        if(n < 0 || n > Length())
            return NULL;
        ListNode<T>* p = head;
        for(int i = 0; i< n ;i ++)
        {
            p = p->m_pnext;
        }
        return p;
    }
    template<typename T>
    void CircularList<T>::Print()
    {
        ListNode<T>* p = head;
        cout << "head" ;
        while(p->m_pnext != head)
        {
            p = p->m_pnext;
            cout << "-->" << p->m_data;
        }
        cout << "-->" << endl;
    }

**测试类文件（Circularlist.h）：**

// Circularlist.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include "CircularList.h"
    #include <iostream>
    using namespace std;
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    
        CircularList<int> circularlist;
        for(int i = 0; i< 15; i ++)
            circularlist.Insert(i * 3,i);
        circularlist.Print();
        cout << "the length of list is: " << circularlist.Length() << endl;
        int del = circularlist.Delete(3);
        cout << del <<"is deleted " << endl;
        circularlist.Print();
        cout << "the length of list is: " << circularlist.Length() << endl;
        
        cin.get();
        return 0;
    }

**测试截图：**

![25214353-507cd6a2b7f44e18b4a6652e6d0f61e4.jpg][]

转载于:https://www.cnblogs.com/JczmDeveloper/archive/2013/03/25/2981530.html

[25214353-507cd6a2b7f44e18b4a6652e6d0f61e4.jpg]: /images/20211126/12d2a136e11f4cb4980c6b8a2f6de048.png