Data Structure - 노드와 연결리스트의 이해(3)

Data Structure(자료 구조)를 주제로 한 여섯번째 포스팅은 연결 리스트 중에서도 포인터 두개를 사용하여 링크를 앞뒤로 시키는 이중연결리스트에 대하여 다루어보겠습니다.

 

 

간단하게 이중연결리스트로 리스트를 하나 구성하고 이를 리버스로 출력하는 예제를 다루며 알아보겠습니다.

 

 

"이중 연결리스트를 구성하고 출력할때 리버스 출력하라"

 

해결과정)

 

출력부분에서 rlink와 llink를 바꾼 출력함수를 두가지 코딩하여 메인에서 불러왔습니다.

//리버스 출력

void print_dlist(DListNode* phead)

{

    DListNode* p;

    for (p = phead->rlink; p != phead; p = p->rlink)

    {

        printf(" %s ", p->data);

    }

    printf("\n");

}

 

//정방향 출력, 연결링크의 포인터 주소만 rlink에서 llink로 바꾸어 주었습니다.

 

void Rprint_dlist(DListNode* phead)

{

    DListNode* p;

    for (p = phead->llink; p != phead; p = p->llink)

    {

        printf(" %s ", p->data);

    }

    printf("\n");

}

 

정수 i를 선언하고 scanf로 입력받아 이중연결리스트 안에 넣을 단어의 개수를 설정해주도록한후

 

반복문 속에 gets함수를 사용하여 단어를 i번 입력받을수 있게 했습니다.

 

printf("입력 단어의 수 :");

    scanf("%d",&j);

 

 

    for (i = 0; i <= j; ++i) {

        if (i != 0) {

            printf("#%d의 노드에 데이터를 입력하시오 : ", i);

        }

        gets(ch);

        dinsert(head, ch);

 

        }

또 반복문 속에 dinsert함수를 불러와서 i번 연결리스트 속에 입력할수 있도록 하였습니다.

 

   

마지막으로

정방향, 역방향 출력함수를 호출하여 콘솔에 출력될수 있도록 했습니다

Rprint_dlist(head);

    printf("\n");

    printf("역방향\n");

    print_dlist(head);

 

 

 

 

 

 

 

 

 

전체 코드)

 

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

 

typedef char element[100];

typedef struct DListNode    //이중연결 노드 타입

{

    element data;

    struct DListNode* llink;

    struct DListNode* rlink;

}DListNode;

 

DListNode* current;

 

//이중 연결 리스트를 초기화

void init(DListNode* phead)

{

    phead->llink = phead;

    phead->rlink = phead;

}

 

//리버스 출력

void print_dlist(DListNode* phead)

{

    DListNode* p;

    for (p = phead->rlink; p != phead; p = p->rlink)

    {

        printf(" %s ", p->data);

    }

    printf("\n");

}

 

//정방향 출력, 연결링크의 포인터 주소만 rlink에서 llink로 바꾸어 주었습니다.

 

void Rprint_dlist(DListNode* phead)

{

    DListNode* p;

    for (p = phead->llink; p != phead; p = p->llink)

    {

        printf(" %s ", p->data);

    }

    printf("\n");

}

 

 

//노드 newnode를 노드 before의 오른쪽에 삽입한다.

void dinsert(DListNode* before, element data)

{

    DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));

    strcpy(newnode->data, data);

    newnode->llink = before;

    newnode->rlink = before->rlink;

    before->rlink->llink = newnode;  //중요

    before->rlink = newnode;  //중요

}

 

//노드 removed를 삭제한다.

void ddelete(DListNode* head, DListNode* removed)

{

    if (removed == head)return;

    removed->llink->rlink = removed->rlink;

    removed->rlink->llink = removed->llink;

    free(removed);

}

 

 

//이중 연결 리스트 테스트 프로그램

int main(void)

{

    int i;

    int j;

 

    char ch[100];

 

    DListNode* head = (DListNode*)malloc(sizeof(DListNode));

    init(head);

 

    printf("입력 단어의 수 :");

    scanf("%d",&j);

 

 

    for (i = 0; i <= j; ++i) {

        if (i != 0) {

            printf("#%d의 노드에 데이터를 입력하시오 : ", i);

        }

        gets(ch);

        dinsert(head, ch);

 

    }

 

 

    current = head->rlink;

 

 

    printf("정방향\n");

    Rprint_dlist(head);

    printf("\n");

    printf("역방향\n");

    print_dlist(head);

 

 

}

 

 

 

 

 

 

 

 

 

 

결과 콘솔)