Circular Linked List in C++

Circular Linked List 跟一般的 Double linked list 幾乎一模一樣，

不同之處在於第一個節點的左 link 並非指向null，而是改成指向最後一個節點，

而同樣的最後一個節點之右 link 也並非指向null，而是改成指向第一個節點，

這樣就形成了一個循環的鏈結串列，稱之 Circular Linked List !

如下圖所示:

加入與刪除都如同前一篇，但是頭端與尾端會有所不同，因為其 link 不再是 null

http://vi-ctor.blogspot.tw/2013/01/double-linked-list-using-c.html

or

http://dsapn.blogspot.tw/2013/01/double-linked-list-using-c.html

接下來不囉嗦直接看Code吧!!  我覺得我好像寫得太麻煩了，應該可以寫得更簡單

，有問題還請指教!

///CLL.h///

#ifndef CLL_H
#define CLL_H
#include <iostream>

class CLL{
private:
    struct DataNode *head;
    struct DataNode *tail;
    struct DataNode *current;
    struct DataNode *ptr;
    struct DataNode *clear;
    char DeleteData;
    char InsertData;
public:
    CLL();
    ~CLL();
    void Add();
    void Insert();
    void List();
    void Delete();
};
#endif

///CLL.cpp///

#include "CLL.h"
using namespace std;
struct DataNode{
    char CharData;
    struct DataNode *Llink;
    struct DataNode *Rlink;
};

CLL::CLL(){
    head=new DataNode;
    current=new DataNode;
    tail=new DataNode;
    head->Llink=NULL;
    head->Rlink=NULL;
    tail->Llink=NULL;
    tail->Rlink=NULL;
    current->Llink=NULL;
    current->Rlink=NULL; 
}

CLL::~CLL(){
    if(head->Rlink==NULL){
        delete head;
        delete tail;
        delete current;
    }else{
        (tail->Rlink)->Rlink=NULL;
        delete tail;
        current=head;
        while(current!=NULL){
            clear=current;
            current=current->Rlink;
            delete clear;
        }
        delete current;
    }
    cout<<"已經清除記憶體..."<<endl;
    system("Pause");
}

void CLL::Add(){
    ptr=new DataNode;
    cout<<"請輸入資料"<<endl;
    cin>>ptr->CharData;
    if(head->Rlink==NULL){
        head->Rlink=ptr;
        tail->Rlink=ptr;        //將頭與尾端指向第一節點
        ptr->Llink=ptr;        //指回自己
        ptr->Rlink=ptr;
    }else{
        current=head->Rlink;    
        current->Llink=ptr;
        ptr->Rlink=current;
        ptr->Llink=tail->Rlink;
        (tail->Rlink)->Rlink=(head->Rlink)->Llink;
        head->Rlink=ptr;
    }
}

void CLL::Insert(){
     if(head->Rlink==NULL){
        cout<<"linklist為空，無法插入"<<endl;
    }else{
        ptr=new DataNode;
        cout<<"請輸入資料"<<endl;
        cin>>ptr->CharData;
        List();
        cout<<"想在哪筆資料的左邊插入資料?:"<<endl;
        cin>>InsertData;
        current=head->Rlink;
        if(current->CharData==InsertData){    //先處理頭端
            current->Llink=ptr;
            ptr->Rlink=current;
            ptr->Llink=tail->Rlink;
            (tail->Rlink)->Rlink=(head->Rlink)->Llink;
            head->Rlink=ptr;
        }
        current=current->Rlink;
        while(current!=head->Rlink){        //處理非頭端
            if(current->CharData==InsertData){
                (current->Llink)->Rlink=ptr;
                ptr->Llink=current->Llink;
                current->Llink=ptr;
                ptr->Rlink=current;
                break;
            }else{
                current=current->Rlink;    //前進
            }
        }
     }
}

void CLL::Delete(){
    List();
    cout<<"請輸入欲刪除資料:"<<endl;
    cin>>DeleteData;
    current=head->Rlink;
    if(current->CharData==DeleteData&&current->Rlink!=current){        //處理頭端且為單一節點
        (current->Rlink)->Llink=tail->Rlink;
        head->Rlink=current->Rlink;
        (tail->Rlink)->Rlink=head->Rlink;
        clear=current;
        delete clear;
    }else if(current->CharData==DeleteData){    //處理頭端且非單一節點
        head->Rlink=NULL;
        clear=current;
        delete clear;
    }else {
        current=current->Rlink;
        while(current!=head->Rlink){
            if(current->CharData==DeleteData){
            if(current==tail->Rlink){        //處理尾端
                (current->Llink)->Rlink=head->Rlink;
                (head->Rlink)->Llink=current->Llink;
                tail->Rlink=current->Llink;
                clear=current;
                current=current->Rlink;
                delete clear;
            }else{        //處理非頭非尾端
                (current->Llink)->Rlink=current->Rlink;
                (current->Rlink)->Llink=current->Llink;
                clear=current;
                current=current->Rlink;
                delete clear;
            }
            }else{
                current=current->Rlink;
            }
        }
    }

}

void CLL::List(){
    if(head->Rlink==NULL){
        cout<<"linklist為空"<<endl;
    }else{
        current=head->Rlink;
        cout<<"目前資料有:"<<endl;
        cout<<(tail->Rlink)->CharData<<" ";
        cout<<"<-"<<current->CharData<<"->";
        current=current->Rlink;
        while(current!=head->Rlink){
            cout<<" <- "<<current->CharData<<" -> ";
            current=current->Rlink;
        }
        cout<<(head->Rlink)->CharData<<endl;
    }
}

///main///

#include <iostream>
#include "CLL.h"
using namespace std;

int main()
{
    char option;
    CLL cll;
    while(1){
        cout<<"======"<<endl;
        cout<<"1.依序新增資料"<<endl;
        cout<<"2.在某筆資料前插入資料"<<endl;
        cout<<"3.刪除"<<endl;
        cout<<"4.顯示"<<endl;
        cout<<"5.結束"<<endl;
        while(cin.get(option)&&option=='\n');
        switch(option){
            case '1':cll.Add();
                break;
            case '2':cll.Insert();
                break;
            case '3':cll.Delete();
                break;
            case '4':cll.List();
                break;
            case '5':cout<<"程式結束"<<endl;
                return 0;
        }
    }
}

By Victor