Programing/C- programing

링크드리스트 :: 추가,삭제,출력,찾기,값변경,위치변경,종료

sosal 2010. 8. 22. 23:40
반응형

/*
 http://sosal.tistory.com/
 * made by so_Sal
 */


추가된것은 값 변경, 위치변경 정도? 입니다.

단순히 복사생성자를 사용하여
node끼리 swap을 하는것입니다.
node a(1),b(2);
a = b; (는 불가능)





#include<iostream>
using namespace std;

class node{
private:
    int value;
public:

    node(int a){          // 생성자 함수를 이용하여 value 초기화
        value = a;
    }
    node(node &a){
        value = a.value;  // 복사생성자를 이용해 노드 초기화
    }
    int getValue(){       // 값을 얻어오기 위한 함수
        return value;
    }
    void getNode(node &a){
        value = a.value;  // set value를 노드로 대신함.
    }
    void setValue(int val){
        value = val;
    }
    node *prev;
    node *next;          // 다음 노드를 가리킬 포인터
};

node* first; // 첫번째 노드
node* newNode;
int count=0;   // 노드의 숫자를 관리할 conter

node* CreateNode(int val);
void AppendNode(node** first, node* newNode);
void find(int val);
void PrintNode();
void DeleteNode(int num);
void ChangeNode(int val,int val2);
void swap(int b,int a);
void sort_up();

int menu();

int main(){
    int a=1;
    int val;
    int val2;
    while(1){                    // 무한루프 돌리면서 메뉴와 인풋을 받아서~
        a = menu();
        if(a==1){
            cout<<"input : ";
            cin>>val;
            newNode = CreateNode(val);  //노드 추가!
            AppendNode(&first,newNode);
        }
        else if(a==2)
            PrintNode();        // 노드 출력~
        else if(a==3){
            cout<<"삭제하고자 하는 노드의 번호 : ";
            cin>>val;
            DeleteNode(val);
        }
        else if(a==4){
            cout<<"찾고자 하는 value를 입력하세요 : ";
            cin>>val;
            find(val);
        }
        else if(a==5){
            cout<<"바꾸고자 하는 노드의 번호 : ";
            cin>>val;
            cout<<"바꾸고자 하는 값을 입력하시오 : ";
            cin>>val2;
            ChangeNode(val,val2);
        }
        else if(a==6){
            cout<<"두개의 노드 번호를 입력하시오 : ";
            cin>>val;
            cin>>val2;
            swap(val,val2);

        }
        else if(a==7){
            sort_up();
        }
        else if(a==8)
            break;
    }

    return 0;
}

node* CreateNode(int val){
    node *myNode = new node(val);    // 새로운 노드 new 를 이용하여 생성 및 value 초기화
    myNode->next=NULL;                 // next 노드 포인터에 NULL값 삽입.
    myNode->prev=NULL;
    count++;
    return myNode;                           // 새로 만들어진 노드를 리턴
}


void AppendNode(node** first, node* newNode){
    if( (*first) == NULL)
        *first = newNode;                      // 첫번째 노드가 비어있을땐, 바로 first에 삽입!
    else{
        node *last = *first;
        while(last->next != NULL){         // 노드 마지막에 삽입하는것이므로.. 마지막까지 이동
            last = last->next;
        }
        last->next = newNode;               // 연결!
        newNode->prev = last;
    }
}

void PrintNode(){
    node* print = first;
    int num=1;
    while(print != NULL){
        if(print->next == NULL)
            cout<<"["<<num<<"] :: "<<print->getValue()<<endl;  // 마지막 노드는 숫자만
        else
            cout<<"["<<num<<"] :: "<<print->getValue()<<endl; 
        print = print->next;                      // 마지막 노드가 아니면 화살표 ㅎㅎ
        num++;
    }
    return;
}
void DeleteNode(int num){
    node* cur = first;
    node* del;
    if(num<0 || count<num)
        cout<<"숫자를 잘못 입력하셨습니다."<<endl;
    else{
        for(int i=2;i<num;i++){
            cur = cur->next;
        }                                         //삭제하기 전의 노드까지 도착
        del = cur->next;                    //삭제하기 위한 노드를 del이 가리킴
        cur->next = cur->next->next; //노드 한칸 건너뛰기
        cur->next->prev=cur;
        delete del;                            //건너뛰어진 노드 삭제
        count--;
    }
    return;
}

int menu(){
    int num;
    cout<<"[1]추가  [2]출력  [3]삭제  [4]찾기  [5]값변경 [6]위치변경  [7] 정렬  [8]종료"<<endl;
    cin>>num;
    return num;
}

void find(int val){
    node* cur = first;

    for(int i=0;i<count;i++){
        if(cur->getValue() == val)
            printf("%d번째 노드의 value는 %d입니다.\n",i+1,val);
        cur = cur->next;
    }
}

void ChangeNode(int val,int val2){
    node* cur = first;
    for(int i=1;i<val;i++){
        cur=cur->next;     //바꾸고자 하는 노드 도착
    }
    cur->setValue(val2);
    return;
}

void swap(int a,int b){

    int tmp;
    node* cur1 = first;
    node* cur2 = first;
   
    if(a<b){
        tmp =a;
        a=b;
        b=tmp;
    }

    for(int i=1;i<a;i++){
        cur1=cur1->next;     //바꾸고자 하는 노드 도착
    }
    for(int i=1;i<b;i++){
        cur2=cur2->next;     //바꾸고자 하는 노드 도착
    }
   
    node tmp_node = *cur1;
    cur1->getNode(*cur2);
    cur2->getNode(tmp_node);
}

void sort_up()
{
    node* cur;
    for(int i=0;i<count-1;i++){
        cur=first;
        for(int j=0;j<count-(i+1);j++){
            if(cur->getValue() > cur->next->getValue()){
                swap(j+1,j+2);
            }
            cur=cur->next;
        }
    }
}