C++ 模板类实现循环链表结构

C++ 模板类实现循环链表结构

运行环境：CodeBlocks

本程序基与本博客C++ 模板类链表迭代器与list.h迭代器基本介绍修改实现。

主程序 main.cpp

//Written by Xuebi
//本程序使用模板类创建循环链表，本链表带有一个空表头ListNode结构，就是说无任何data数据，初始化的时候，空表头ListNode的指针指向它本身。
//本程序实现了相对应的迭代器
#include <iostream>
#include "List.h"
#include <list>
using namespace std;
int main()
{
    List<int> st;
    st.Insert(10);
    st.Insert(20);
    st.Insert(30);
    st.Insert(40);
    //这是循环链表st的迭代器，用来历遍链表或者对链表的元素进行操作。
    Iterator<int> Iterator_st(st);
    cout<<"The data in the first Node in st: "<<*Iterator_st.First()<<endl;
    //本质上这不是first，因为本循环链表第一个ListNode是空表头，此Iterator_st.First()，返回的是空表头后的ListNode结构中的data数据的指针。
    cout<<"In the following, use the iterator to show the list st ："<<endl;
    if(Iterator_st.IfNonNull())
    {
        cout<<*Iterator_st.First();//试试改成：cout<<10*(*Iterator_st.First()); 修改后能体现出迭代器对链表的数据域函数进行修改的功能
        while(Iterator_st.IfNextNonNull())
        {
            cout<<"->";
            cout<<*Iterator_st.Next();//试试改成：cout<<10*(*Iterator_st.Next());
        }
    }
    else
    {
        return 0;
    }
    cout<<endl;
    //以上是历遍链表。本质上链表是 ListNode(空)->ListNode(40)->ListNode(30)->ListNode(20)->ListNode(10)
    cout<<"In the following, by means of the Next() function, it is showed that it is a real circle list ."<<endl;
    cout<<*Iterator_st.Next()<<"    ";//输出的应该是40
    cout<<*Iterator_st.Next()<<"    ";//输出的应该是30
    cout<<*Iterator_st.Next()<<"    ";//输出的应该是20
    cout<<*Iterator_st.Next()<<"    ";//输出的应该是10
    cout<<endl;
    cout<<"A new circle, it will obtain 40 again. "<<endl;
    cout<<*Iterator_st.Next()<<"    ";//输出的应该是40
    return 0;
}
           

头文件 List.h

#ifndef LIST_H
#define LIST_H
#include <iostream>
template<class T> class List;//声明List，方便ListNode声明为友元函数
template<class T> class Iterator;
template<class T>
class ListNode//链表节点
{
friend class Iterator<T>;//友元函数
friend class List<T>;//友元函数，List可以访问ListNode的私有成员 反思声明友元函数friend class List会报错
private:
    T data;//数据域
    ListNode*p;//ListNode类型指针
    ListNode(T element);//带参构造函数，为Insert服务
    ListNode(){};//构造函数，为初始化first(空表头)服务
};
template<class T>
class List
{
friend class Iterator<T>;
private:
    ListNode<T>*first;//List私有成员只有链表的头部
public:
    List();
    void Insert(T element);
    void Delete(T element);
};
template<class T>
class Iterator//新增加迭代器，
{
private:
    const List<T>&Li_st;//引用传入一个List类
    ListNode<T>*current;//当前的指向的ListNode
public:
    Iterator(const List<T>&I):Li_st(I),current(I.first->p){};
    bool IfNonNull();//判断当前Node是不是空（空指针）
    bool IfNextNonNull();
    T*First() ;
    T*Next();
};
template<class T>
List<T>::List()//初始化链表时，为空链表,另外空链表的指针指向它自己
{
    first=new ListNode<T>;
    first->p=first;
}
template<class T>
ListNode<T>::ListNode(T element)
{
    data=element;
    p=0;
}
template<class T>
void List<T>::Insert(T element)
{
    ListNode<T>*A=new ListNode<T>(element);//动态创建一个ListNode类型指针A
    A->p=first->p;//这两步目的是插入一个ListNode<T>(element)链表
    first->p=A;
}
template<class T>
void List<T>::Delete(T element)
{
    ListNode<T>*current=first->p;
    ListNode<T>*previous=first;
    //向下搜索所要删除的ListNode，循环结束条件：1.搜索成功 2.历遍链表后，重新到达first空表头。
    //第一种情况满足执行具体的从循环链表中删除该ListNode的操作，第二种不需要执行操作。
    for(current;current!=first&&((current->data)!=element);previous=current,current=current->p)
    {
        ;
    }
    if(current!=first)
    {
        previous=current->p;
        delete current;
    }
}
template <class  T>
bool Iterator<T>::IfNonNull()//此函数主要判断本ListNode是不是first(空表头)
{
    if(current!=Li_st.first)
        return 1;
    else return 0;
}
template <class T>
bool Iterator<T>::IfNextNonNull()//此函数主要判断下一个ListNode是不是first(空表头)
{
    if(current->p!=Li_st.first)
        return 1;
    else
        return 0;
}
template <class T>
T*Iterator<T>::First()
{
    if(Li_st.first->p!=Li_st.first)
        return &Li_st.first->p->data;//返回的是first节点后面节点的data的地址
    else
     std::cout<<"No first data in this list"<<std::endl;
}
template <class T>
T*Iterator<T>::Next()
{
    if(IfNextNonNull()!=1)//如果下一个ListNode是first(空表头)，则跳过此空表头，取下一个ListNode结构
    {
        current=current->p;
    }
    current=current->p;
    return &current->data;
}
#endif // LIST_H
           

输出结果：

本程序仅供学习参考之用，如若转载，请注明出处。

如果你对本程序感到满意，可点击关注本博客！！

Moi, je ne suis qu’un programmeur.