[자료구조] 체인

Sequential Representation

succesive element is stored at fixed distance apart

Linked representation

 eash element is places anywhere in memory

 

---

Chain representation in C++

 

1. 체인 노드 클래스

template <class T>
class ChainNode {
    friend class Chain<T>;
private:
    T data;
    ChainNode<T> *link;
public:
    ChainNode(T value = "", ChainNode<T> *_link = NULL) { //생성자
        data = value;
        link = _link;
    }
};

 

2. 체인 클래스 데이터 멤버

template <class T>
class Chain {
private:
    ChainNode<T> *first;
    ChainNode<T> *second;
    ChainNode<T> *last;

 

3. 체인의 끝에 노드 삽입

void insertBack(const T& e){
    if(first) {
        last->link = new ChainNode<T>(e);
        last = last->link;
    }
    else makeChainNode(e);
}

 

4. 노드 삭제

void deleteChainNode(const T& e) {
    ChainNode<T> *cur = first;
    if(first->data == e) {
        if(first->link != NULL)
            first = new ChainNode<T>(first->link->data,first->link->link);
        else
            first = NULL;
    }
    while (cur->link != NULL) {
        if(cur->link->data) {
            cur->link = cur->link->link;
            return;
        }
    }
}

 

5. 전체 체인 클래스

template <class T>
class Chain {
private:
    ChainNode<T> *first;
    ChainNode<T> *second;
    ChainNode<T> *last;
 
public:
    Chain() { // 생성자
        first = NULL;
        second = NULL;
        last = NULL;
    }
    void makeChainNode(T value) {
        second = new ChainNode<T>(0, NULL);
        first = last = new ChainNode<T>(value, second);
    }
    void insert(const T& e, ChainNode<T> *x) {
        if(first)
            x->link = new ChainNode<T>(e,x->link);
        else
            makeChainNode(e);
    }
    void insertBack(const T& e){
        if(first) {
            last->link = new ChainNode<T>(e);
            last = last->link;
        }
        else makeChainNode(e);
    }

    void deleteChainNode(const T& e) {
        ChainNode<T> *cur = first;
        if(first->data == e) {
            if(first->link != NULL)
                first = new ChainNode<T>(first->link->data,first->link->link);
            else
                first = NULL;
        }
        while (cur->link != NULL) {
            if(cur->link->data) {
                cur->link = cur->link->link;
                return;
            }
        }
    }
    void print() {
        ChainNode<T> *cur = first;
        if(!first){
            cout << "노드를 생성하시오."<< endl;
            return;
        }
        while (cur!= last) {
            cout << cur->data << " ";
            cur = cur->link;
        }
        cout << last-> data << endl;
    }
    ChainNode<T>* getFirst(){ return first;}
    ChainNode<T>* getLink(ChainNode<T> *x){ return x->link;}
};

 

6. 전체 코드

#include <iostream>
 
using namespace std;

template <class T> class Chain;

template <class T>
class ChainNode {
    friend class Chain<T>;
private:
    T data;
    ChainNode<T> *link;
public:
    ChainNode(T value = "", ChainNode<T> *_link = NULL) { //생성자
        data = value;
        link = _link;
    }
};

template <class T>
class Chain {
private:
    ChainNode<T> *first;
    ChainNode<T> *second;
    ChainNode<T> *last;
 
public:
    Chain() { // 생성자
        first = NULL;
        second = NULL;
        last = NULL;
    }
    void makeChainNode(T value) {
        second = new ChainNode<T>(0, NULL);
        first = last = new ChainNode<T>(value, second);
    }
    void insert(const T& e, ChainNode<T> *x) {
        if(first)
            x->link = new ChainNode<T>(e,x->link);
        else
            makeChainNode(e);
    }
    void insertBack(const T& e){
        if(first) {
            last->link = new ChainNode<T>(e);
            last = last->link;
        }
        else makeChainNode(e);
    }

    void deleteChainNode(const T& e) {
        ChainNode<T> *cur = first;
        if(first->data == e) {
            if(first->link != NULL)
                first = new ChainNode<T>(first->link->data,first->link->link);
            else
                first = NULL;
        }
        while (cur->link != NULL) {
            if(cur->link->data) {
                cur->link = cur->link->link;
                return;
            }
        }
    }
    void print() {
        ChainNode<T> *cur = first;
        if(!first){
            cout << "노드를 생성하시오."<< endl;
            return;
        }
        while (cur!= last) {
            cout << cur->data << " ";
            cur = cur->link;
        }
        cout << last-> data << endl;
    }
    ChainNode<T>* getFirst(){ return first;}
    ChainNode<T>* getLink(ChainNode<T> *x){ return x->link;}
};
 
int main() {
    Chain<int> a;
    int value;
    int num;
 
    while(1) {
        cout << "노드 생성(1), 노드 삽입(2), 노드 확인(3), 노드 삭제(4), 종료(5)" << endl;
        cout << "번호 입력: ";
        cin >> num;
 
        switch(num) {
            case 1:
                cout << "노드 값 입력: ";
                cin >> value;
                a.makeChainNode(value);
                break;
            case 2:
                cout << "노드 값 입력: ";
                cin >> value;
                a.insertBack(value);
                break;
            case 3:
                a.print();
                break;
            case 4:
                cout << "어떤 노드?: ";
                cin >> value;
                a.deleteChainNode(value);
                break;
            case 5:
                return 0;
                break;
        }
    }
}