[자료구조]단일 연결 리스트(C++ 재귀)

간단한 자료구조라서 짜는데 별로 오래 안걸릴 줄 알았지만 최소 12시간 붙잡고 구현했다.

모든 자료형에 대해 처리 해주고 싶었는데 C++은 정적언어라 불가능했다. 템플릿을 쓰던, auto를 쓰던 입력값에 대해 자료형을 알아내는 문법은 없더라..(이것땜에 하루 새벽 보내버렸고)

일단 포기하고 int형만 받도록 했다. 아마 모든 자료형에 대해 처리하려면 오버로딩이나 자료형 테이블을 만들어서 테이블을 통해 연결리스트의 노드들을 이어줘야 할 듯 하다. (파이썬 쓰는게 답이다)

컴파일 환경: g++ -std=c++11

#include<iostream>
#include<string>
using namespace std;
 
template<typename T>
class Type{
private:
    T data;
public:
    Type(){}
    ~Type(){}
};
 
class Node{
private:
    Node *next; //다음 노드
    int d; //데이터 
    int v; //데이터 존재 여부 d에 NULL이 안들어가서 0으로 초기화하면 확인 과정에서 문제가 생김 
public:
    Node() :d(0),v(0){
        next=nullptr;
    }
    void Linking(Node& n){ //n은 this 객체의 next노드  따라서 this객체를 next객체로 바꿔야함 
        this->d=n.d;
        this->v=n.v;
        if(n.v==1)  
            this->next=n.next; 
        n.next=nullptr;  //두 번 해제 방지 
        delete &n; //다 정리해주고 메모리 해제 
    }
    Node& operator=(Node& n){
        Linking(n);
        return *this;
    }
    void Insert(int &f){
        if(v==1)
            next->Insert(f);
        else{
            d=f;
            v=1;
            next=new Node;
        }
    }
    void Insert(int& f,int n){
        if(n>0 && v==1){  //값이 있으면 새로 노드 만듬 
            n-=1;
            next->Insert(f,n);
        }
        else{  //값 없으면 대입     
            if(n==0 && v==1){   //중간에 껴 넣을 경우
                Node *Ln=new Node;
                Ln->Linking(*this);
                next=new Node;
                Insert(f);
                next->Linking(*Ln);
            }
            else{  //맨 마지막 노드 
                next=new Node;
                next->Insert(f);
                Linking(*next);
            }
        }
    }
    void Find(int& f){
        if(v==0)
            cout <<"찾는 데이터가 없습니다.\n";
        else if(d==f)
            cout <<"찾았습니다. data: " << d << '\n';
        else
            next->Find(f);
    }
    
    void Remove(int& f){
        if(v==0)
            cout<<"지울 데이터가 없습니다.\n";
        else if(d==f && this->next==nullptr) //맨 끝 노드 일 때 
            delete this;
        else if(d==f && this->next!=nullptr)
             Linking(*next);
        else
            next->Remove(f);
    }
    
    void Change(int& f1,int& f2){
        if(v==0)
            cout<<"교체할 데이터가 없습니다.\n";
        else if(d!=f1)
            next->Change(f1,f2);
        else{
            cout <<"교체완료 " << d <<" -> " << f2 << '\n';
            d=f2;
        }
    }
    void List(){
        if(v==1){
            cout <<"data: " << d <<'\n';
            if(next!=nullptr)
                next->List();
        }
    }
    ~Node(){
        if(next!=nullptr){
            delete next;
        }
    }    
 
};
 
const int Info() {
    cout << "\n\n\n***번호 입력***\n";
    cout << "1.데이터 삽입 2.데이터 삭제 3.데이터 찾기 4.데이터 교체 5.데이터 목록-종료는 아무키\n";
    return 1;
}
 
enum {ins=1,del,fin,cha,lis};
 
int main(void)
{
    Node *n=new Node;
    int value,d,select;
    while(Info()){
        cout<<"\n\n***메뉴선택 : ";
        cin >> select;
        
        switch(select){
            cout <<"select : "<<select<<endl;
            case ins:
                cout <<"저장할 데이터: "; cin >> d;
                cout <<"위치(자동 삽입은 0이하 : "; cin >> value;
                if(value < 1)
                    n->Insert(d); 
                else 
                    n->Insert(d,value); 
                cout << "***삽입됨***\n";
                break;
            case del:
                cout <<"지울 데이터: "; cin >> d; 
                n->Remove(d);
                break;
            case fin:
                cout <<"찾을 데이터: "; cin >> d;
                n->Find(d); break;
            case cha:
                cout <<"교체할 데이터: "; cin >> d;
                cout <<"교체 값: "; cin >> value;
                n->Change(d,value); break;
            case lis:
                cout <<"***데이터 목록***\n";
                n->List();
                cout <<"*****************\n";
                break;
            default : cout << "종료\n"; delete n; return 0;
        }
    }
}
 
 

메모리 하도 터져가지고 메모리 가지고 불꽃놀이 했는데 정말 끔찍하더라.. 큰 프로그램이면 어떻게 될지;; 모든 자료형에 대한 처리는 추후 추가 해야겠다.