본문 바로가기
삽질/Com

이중연결리스트

by 푸딩s 2009. 12. 6.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

 

typedef struct _dnode
{
    int key;
    struct _dnode *next;
    struct _dnode *prev;
}DNODE;

 

DNODE *start = NULL;
DNODE *cur = NULL;

 

void insert(void);
void print(void);
void del_node(void);
void delete_node(void);

 

void main()
{
    int no;
   
    while(1)
    {
        system("cls");
        puts("*** MENU ***");
        puts("1. INSERT");
        puts("2. PRINT");
        puts("3. DELETE");
        puts("4. END");
        printf("choice : ");
        scanf("%d", &no);
        fflush(stdin);
       
        switch(no)
        {
        case 1 : insert(); break;
        case 2 : print(); break;
        case 3 : delete_node(); break;
            //del_node(); break;
        case 4 : exit(1);
        }
        getch();
    }
}

void insert(void)
{
    DNODE *newnode;
   
    newnode = (DNODE*)malloc(sizeof(DNODE));
   
    if(cur != NULL)
        printf("\n\tCUR->KEY : %d\n", cur->key);
   
    printf("\n\t삽입할 정수를 입력 : ");
    scanf("%d", &newnode->key);
    newnode->next = newnode->prev = NULL;
   
    if(start == NULL)
    {
        start = newnode;
        cur = newnode;
        printf("\n\t배열이 비어있을 때 삽입...\n");
        return;
    }
   
    if(cur->key > newnode->key) // NEXT... 중간삽입 or 맨 끝삽입...
    {
        while(cur->next != NULL)
        {
            //   20     10(cur)    [8(newnode)]     5(cur->next)    3
            if(cur->next->key < newnode->key)
            {
                newnode->next = cur->next;
                newnode->prev = cur;
                cur->next->prev = newnode;
                cur->next = newnode;
                printf("\n\tNEXT... 중간삽입...\n");
                return;
            }
            cur = cur->next;
        }
        // 5(cur)    [3(newnode)]   NULL
        newnode->prev = cur;
        cur->next = newnode;
        printf("\n\tNEXT... 맨끝삽입...\n");
    }
    else // PREV.. 중간삽입 or 맨앞삽입.
    {
        while(cur->prev != NULL)
        {
            //  22    20(cur->prev)   [15(newnode)]   10(cur)    8
            if(cur->prev->key > newnode->key)
            {
                newnode->next = cur;
                newnode->prev = cur->prev;
                cur->prev->next = newnode;
                cur->prev = newnode;
                printf("\n\tPREV... 중간삽입...\n");
                return;
            }
            cur = cur->prev;
        }
        // NULL  [20(newnode)]  10(cur)
        newnode->next = cur;
        cur->prev = newnode;
        start = newnode;
        printf("\n\tPREV... 맨앞삽입...\n");
    }
}

void print(void)
{
    DNODE *cur;
   
    if(start == NULL)
    {
        printf("\n\t연결리스트가 구성되어있지 않아 출력할 수 없습니다...\n");
        return;
    }
   
    printf("\n< 내림차순 >\n");
    cur = start;
    while(cur->next != NULL)
    {
        printf("%d -> ", cur->key);
        cur = cur->next;
    }
    printf("%d\n", cur->key);
   
    printf("\n< 오름차순 >\n");
    while(cur->prev != NULL)
    {
        printf("%d -> ", cur->key);
        cur = cur->prev;
    }
    printf("%d\n", cur->key);
}

void del_node(void)
{
    int k;
    DNODE *del;
   
    if(start == NULL)
    {
        printf("\n\t연결리스트가 비어있어서 삭제할 수 없습니다...\n");
        return;
    }
   
    printf("\n\tCUR->KEY : %d\n", cur->key);
   
    printf("\n\t삭제할 정수를 입력 : ");
    scanf("%d", &k);
    fflush(stdin);
   
    if(cur->key == k)
    {
        //                   del
        // cur->prev(6)     cur(4)      cur->next(1)
       
        del = cur;
       
        if(cur->next != NULL && cur->prev != NULL)
        {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            cur = cur->next;
        }
        else if(cur->next == NULL && cur->prev != NULL)
        {
            cur->prev->next = NULL;
            cur = cur->prev;
        }
        else if(cur->next != NULL && cur->prev == NULL)
        {
            cur->next->prev = NULL;
            start = start->next;
            cur = cur->next;
        }
        else // cur->next == NULL && cur->prev == NULL
            start = cur = NULL;
       
        printf("\n\tCUR... delete... [%d]\n", del->key);
        free(del);
    }
    else if(cur->key > k) // NEXT...
    {
        while(cur->next != NULL)
        {
            //                 del             del->next
            //  cur(10)    cur->next(5)     cur->next->next(3)
            if(cur->next->key == k)
            {
                del = cur->next;
                cur->next = del->next;
                if(del->next != NULL)
                    del->next->prev = cur;
                printf("\n\tNEXT... delete... [%d]\n", del->key);
                free(del);
                return;
            }
            cur = cur->next;
        }
    }
    else // PREV...
    {
        while(cur->prev != NULL)
        {
            //     del->prev               del
            // cur->prev->prev(10)      cur->prev(5)       cur(3)
            if(cur->prev->key == k)
            {
                del = cur->prev;
                if(del->prev != NULL)
                    del->prev->next = cur;
                else
                    start = start->next;
                cur->prev = del->prev;
                printf("\n\tPREV... delete... [%d]\n", del->key);
                free(del);
                return;
            }
            cur = cur->prev;
        }
    }
}

void delete_node(void)
{
    int k;
    DNODE *del;
   
    if(start == NULL)
    {
        printf("\n\t연결리스트가 비어있어서 삭제할 수 없습니다...\n");
        return;
    }
   
    printf("\n\tCUR->KEY : %d\n", cur->key);
   
    printf("\n\t삭제할 정수를 입력 : ");
    scanf("%d", &k);
    fflush(stdin);
   
    del = cur;
    if(cur->key > k)
    {
        while(cur != NULL && cur->key != k)
            cur = cur->next;
    }
    else if(cur->key < k)
    {
        while(cur != NULL && cur->key != k)
            cur = cur->prev;
    }
   
    if(cur == NULL)
    {
        printf("\n\t입력하신 정수 [%d]는 존재하지 않습니다.\n", k);
        cur = del;
        return;
    }
   
    //  del->prev      del      del->next
    //  cur->prev      cur      cur->next
   
    del = cur;
   
    if(del->prev != NULL)
    {
        del->prev->next = del->next;
        cur = cur->prev;
    }
    else
    {
        start = start->next;
        cur = cur->next;
    }
    if(del->next != NULL)
        del->next->prev = del->prev;
   
    printf("\n\tdelete... [%d]\n", del->key);
    free(del);
}


 

'삽질 > Com' 카테고리의 다른 글

하위디렉토리의 종류 및 기능  (0) 2009.12.06
트리  (0) 2009.12.06
빙고게임  (1) 2009.12.06
주석 삭제 프로그램  (0) 2009.12.06
행맨게임  (0) 2009.10.24

댓글