数据结构CC++版本-循环链表

Source

本文链接： https://blog.csdn.net/AdrianAndroid/article/details/100762228

list_cycle.h

#ifndef LIST_CYCLE_H_INCLUDED
#define LIST_CYCLE_H_INCLUDED
#include <string>
#include <iostream>

#pragma once

#define status bool
#define OK true
#define ERROR false
#define YES true
#define NO false

using namespace std;

void runCycleList();

template <typename DType>
class Node
{
        public:
                DType data;
                Node * pnext;
};

template <typename DType>
class CCircleLinkList
{
        private:
                Node<DType> *phead;
        public:
                CCircleLinkList();
                ~CCircleLinkList();
        public:
                // 初始化链表
                status InitCList();
                // 获取链表长度
                int GetCListLength();
                // 增加一个节点 前插法
                status AddCListNodeFront(DType idata);
                // 增加一个节点 后插法
                status AddCListNodeBack(DType idata);
                // 判断链表是否为空
                status IsCListEmpty();
                // 获取指定位置节点值（注意，本程序规定0号为节点，e获取删除元素）
                status GetCListIndexNode(DType *e, int index);
                // 删除指定位置节点（e获取删除元素）
                status DeleteCListIndexNode(DType *e, int index);
                // 查找和链表中指定值(pindex获取位置0==>not found)
                status SearchCListNode(DType SData, int *pindex);
                // 指定位置前插
                status InsertCListNodeFront(DType IData, int index);
                //  指定位置后插
                status InsertCListNodeBack(DType IData, int index);
                // 清空链表（保留跟节点）
                status ClearCList();
                // 销毁链表（all delete）
                status DestroyCList();
                // 尾部删除一个元素
                status DeleteCListNohdeBack();
                // 打印链表 此函数根据实际情况而定
                void PrintCList();
};



//循环链表的节点
class ListCycleNode{
	public:
		int tag; //方便打印的时候指导末尾
		string name;
		ListCycleNode* next;

		bool hasNext(){
			return this->next  != NULL;
		}
};








#endif // LIST_CYCLE_H_INCLUDED

list_cycle.cpp

#include "list_cycle.h"
#include "tools.h"

#define TLDType  template <typename DType>

template <typename DType>
CCircleLinkList<DType>::CCircleLinkList()
{
    cout << "链表创建" << endl;
    InitCList();
}

template <typename DType>
CCircleLinkList<DType>::~CCircleLinkList()
{
    cout << "销毁链表" << endl;
    DestroyCList();
}

//初始化链表
template <typename DType>
status CCircleLinkList<DType>::InitCList()
{
        Node<DType> *ph = new Node<DType>;
        if(ph != NULL) {
                ph->pnext = ph; //尾指向头
                this->phead = ph;// 头节点
                return OK;
        }
        return ERROR;
}

//获取链表长度（head_node is not  include）
template <typename DType>
int CCircleLinkList<DType>::GetCListLength()
{
        int length = 0;
        Node<DType> *ph = this->phead;
        while(ph->pnext != this->phead)
        {
                length ++;
                ph = ph->pnext;
        }
        return length;
}

// 增加一个节点 前插法
template <typename DType>
status CCircleLinkList<DType>::AddCListNodeFront(DType idata)
{
        Node<DType> * pnode = new Node<DType>;
        if(pnode != NULL) {
                pnode->data = idata;
                pnode->pnext = this->phead->pnext;
                this->phead->pnext = pnode;//挂载

                return OK;
        }
        return ERROR;
}

// 增加一个节点 尾插法
TLDType
status CCircleLinkList<DType>::AddCListNodeBack(DType idata)
{
        Node<DType> * pnode = new Node<DType>;
        Node<DType> * ph = this->phead;
        if(pnode!=NULL) {
                while(ph->pnext != this->phead)
                {
                        ph = ph->pnext;
                }
                pnode->data = idata;
                pnode->pnext = this->phead;
                ph->pnext = pnode;//挂载
                return OK;
        }
        return ERROR;
}

// 判断链表是否为空
TLDType
status CCircleLinkList<DType>::IsCListEmpty(){
        if(this->phead->pnext == this->phead) {
                return YES;
        }
        return NO;
}

// 获取指定位置节点值(注意，本程序规定0为头节点，e获取节点的值）
TLDType
status CCircleLinkList<DType>::GetCListIndexNode(DType *e, int index)
{
        Node<DType> * ph = this->phead;
        int i = 0; //计数器
        if(ph->pnext == this->phead || index < 1 || index>GetCListLength()) {
                return ERROR;
        }
        while(ph->pnext != this->phead) {
                i++;
                ph = ph->pnext;
                if(i == index) {
                        *e = ph->data;
                        return OK;
                }
        }
        return ERROR;
}

//删除指定位置节点
TLDType
status CCircleLinkList<DType>::DeleteCListIndexNode(DType *e, int index)
{
        Node<DType> * ph = this->phead;
        int i = 0; //计数器
        Node<DType> *q = nullptr;
        if(ph->pnext == this->phead || index < 1 || index > GetCListLength()) {
                return ERROR;
        }
        while(ph->pnext != this->phead){
                i++;
                q = ph;//保存备用
                ph = ph->pnext;
                if(i == index)
                {
                        *e = ph->data;
                        q->pnext = ph->pnext;
                        delete ph;
                        return OK;
                }
        }
        return ERROR;
}

// 查找链表中指定值（pindex获取位置 0===>not found)
TLDType
status CCircleLinkList<DType>::SearchCListNode(DType SData, int *pindex)
{
        Node<DType> *ph = this->phead;
        int iCount = 0; //计数器
        while(ph->pnext != this->phead) {
                iCount++;
                ph = ph->pnext;
                if(ph->data == SData)
                {
                        *pindex = iCount;
                        return YES;
                }
        }
        *pindex = 0;
        return NO;
}

// 指定位置前插
TLDType
status CCircleLinkList<DType>::InsertCListNodeFront(DType IData, int index){
        Node<DType> * ph = this->phead;
        if(ph->pnext == this->phead || index < 1 || index > GetCListLength()) {
                return ERROR;
        }
        int iCount = 0; //计数器
        Node<DType> *q = nullptr;//备用
        while(ph->pnext != this->phead)
        {
                iCount++;
                q = ph;
                ph = ph->pnext;
                if(iCount == index) {
                        Node<DType> * p = new Node<DType>;
                        p->data = IData;
                        q->pnext = ph;
                        q->pnext = p;//前插
                        return OK;
                }
        }


        return ERROR;
}

TLDType
 status  CCircleLinkList<DType>::InsertCListNodeBack(DType IData, int index){
        Node<DType> * ph =  this->phead;
        if(ph->pnext == this->phead || index < 1 || index > GetCListLength()) {
                return ERROR;
        }
        int iCount = 0; //计数器
        Node<DType> * q = nullptr;//备用
        while(ph->pnext != this->phead)
        {
                iCount ++;
                q = ph;
                ph = ph->pnext;
                if(iCount == index) {
                        Node<DType> *p = new Node<DType>;
                        q = ph;
                        ph = ph->pnext; //后插就是后一个节点前插
                        p->data=IData;
                        p->pnext = ph;
                        q->pnext=p;
                        return OK;
                }
        }
        return ERROR;
 }

 // 清空链表（保留根节点）
 TLDType
status  CCircleLinkList<DType>::ClearCList(){
        Node<DType> *ph = this->phead;
        Node<DType> *q = nullptr;//防止那啥，野指针
        ph = ph->pnext; //保留头节点
        while(ph != this->phead){
                q = ph;
                ph = ph->pnext;
                delete q;
        }
        this->phead->pnext = this->phead;
        return OK;
}

//销毁链表
TLDType
status CCircleLinkList<DType>::DestroyCList(){
        ClearCList();
        delete this->phead;
        return OK;
}

TLDType
status  CCircleLinkList<DType>::DeleteCListNohdeBack(){
        Node<DType> *ph = this->phead;
        Node<DType> * q = nullptr;
        if(ph->pnext ==  this->phead) {
                return ERROR; // 链表都空了还删啥
        }
        while(ph->pnext != this->phead)
        {
                q = ph;
                ph = ph->pnext;
        }
        q->pnext = this->phead;
        delete ph;
        return OK;
}

TLDType
void CCircleLinkList<DType>::PrintCList(){
        Node<DType> *ph = this->phead;
        if(ph->pnext == this->phead) {
                cout << "链表为空，打印鸡毛" << endl;
        }
        int i = 1;
        cout << "==========print list===========" << endl;
        while(ph->pnext!=this->phead)
        {
                ph = ph->pnext;
                cout << "node["<< i++ << "] = "<< ph->data  << endl;
        }
}

// 运行循环list
void runCycleList()
{
        cout<<"Hello World!"<<endl;
        CCircleLinkList<int>  * pMySList = new CCircleLinkList<int>;
        cout << pMySList->IsCListEmpty() << endl;
        pMySList->AddCListNodeFront(111);
        pMySList->AddCListNodeFront(222);
        pMySList->AddCListNodeFront(333);

        cout << "链表长度" << pMySList->GetCListLength() << endl;
        pMySList->PrintCList();

        pMySList->AddCListNodeBack(444);
        pMySList->AddCListNodeBack(555);
        pMySList->AddCListNodeBack(666);

        pMySList->PrintCList();

        cout << pMySList->IsCListEmpty() << endl;
        cout << "链表长度" << pMySList->GetCListLength() << endl;

        int GetElem, GetIndex;
        pMySList->GetCListIndexNode(&GetElem, 2);
        cout << "Got Elem = " << GetElem << endl;

        pMySList->GetCListIndexNode(&GetElem, 6);
        cout << "Got Elem=" << GetElem << endl;

        pMySList->GetCListIndexNode(&GetElem, 4);
        cout<<"Got Elem"<<GetElem<<endl;

        pMySList->DeleteCListIndexNode(&GetElem, 1);
        cout << "del Elem = " << GetElem<<endl;
        pMySList->DeleteCListIndexNode(&GetElem, 3);
        cout<<"dle Elem="<<GetElem<<endl;

        pMySList->PrintCList();

        pMySList->SearchCListNode(555, &GetIndex);
        cout<<"Search Index ="<<GetIndex<<endl;
        pMySList->SearchCListNode(111, &GetIndex);
        cout<<"Search Index ="<<GetIndex<<endl;
        pMySList->SearchCListNode(666, &GetIndex);
        cout<<"Search Index="<<GetIndex<<endl;

        pMySList->InsertCListNodeFront(333,1);
        pMySList->InsertCListNodeBack(444,4);

        pMySList->PrintCList();

        pMySList->InsertCListNodeBack(777,3);
        pMySList->InsertCListNodeBack(888,3);

        pMySList->PrintCList();

        pMySList->DeleteCListNohdeBack();
        pMySList->PrintCList();
        pMySList->DeleteCListNohdeBack();
        pMySList->PrintCList();
        pMySList->DeleteCListNohdeBack();
        pMySList->PrintCList();



}