기존의 트리 순회 알고리즘(중위, 전위, 후위) 은 모두 순환호출(=스택)을 이용한 알고리즘이었습니다.

순환의 특성 상 트리의 높이가 커질수록 순환의 깊이가 깊어져서 상당히 비효율적일 수 있습니다.

쓰레드 이진트리는 노드의 NULL링크를 활용하여 순환 호출없이, 즉 반복문으로 순회할 수 있는 방법입니다.


선행 노드인 중위 선행자나 중위 순회 시 후속노드인 중위 후속자를 저장 시켜놓은 트리가 쓰레드 이진트리입니다.


중위 순회를 한다고 가정하여 중위 후속자를 저장한 쓰레드 이진트리를 구현해 보겠습니다.

일단 treeNode구조체에 쓰레드 정보를 가질 is_thread변수를 추가합니다. 값이 1이면 쓰레드를 가지고, 0이면 일반적인 트리입니다.


구현 함수는 2가지가 있습니다.

1. 쓰레드 중위순회 함수

후속자를 찾아 순서대로 출력합니다.


2. 중위 후속자를 찾는 함수( 중위 후속자를 반환)

=> 노드가 쓰레드를 가지면(is_thread==1) 오른쪽 자식을 반환합니다.

위 트리를 구성하는 과정에서 A와 C, B와G, D와F를 연결시켜놨기 때문에 쓰레드를 갖는 노드의 오른쪽 자식은 후속자가 됩니다.

현재 노드의 오른쪽자식 노드가 NULL이거나 p가 쓰레드를 가지면 q를 반환합니다.

(NULL일경우 1번함수에서 걸러지고, p가 쓰레드를 가지면 오른쪽 자식노드가 있음을 알기 때문)

그리고 G나 F같은 일반 노드 같은경우, 중위순회를 위해 서브 트리의 가장 왼쪽으로 가는 연산식이 필요합니다.


순회 순서는 순환방법과 똑같기 때문에 후속자를 찾는 포인트만 알고 있으면 구현이 어렵지 않습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<stdio.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define size 10
typedef struct treeNode
{
    int data;
    struct treeNode* left, * right;
    int is_thread;
}treeNode;
 
treeNode n1 = { 'A',NULL,NULL,1 };
treeNode n2 = { 'B',NULL,NULL,1 };
treeNode n3 = { 'C',&n1,&n2,0 };
treeNode n4 = { 'D',NULL,NULL,1 };
treeNode n5 = { 'E',NULL,NULL,0 };
treeNode n6 = { 'F',&n4,&n5,0 };
treeNode n7 = { 'G',&n3,&n6,0 };
treeNode* exp = &n7;
void thread_inorder(treeNode* t);
treeNode* find_successor(treeNode* p);
int main()
{
    //쓰레드를 설정한다.
    n1.right = &n3;
    n2.right = &n7;
    n4.right = &n6;
    thread_inorder(exp);
}
void thread_inorder(treeNode* t)
{
    treeNode* q;
    q = t;
    while (q->left)q = q->left;
    do {
        printf("%c ", q->data);
        q = find_successor(q);
    } while (q);
    puts("");
}
treeNode* find_successor(treeNode* p)
{
    treeNode* q = p->right;
    //q가 NULL일 때도 반환(어짜피 중위순회 함수에서 NULL을 받아 걸러짐
    //p가 (q의 오른쪽자식이) 쓰레드면 바로 반환
 
    if (q == NULL || p->is_thread == TRUE)
        return q;
    //G, F 같은 일반 노드의 경우 중위순회를 위해 맨 왼쪽노드를 찾음
    while (q->left != NULL)q = q->left;
    return q;
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


트리를 이용한 순회기법들을 알아봤고 그 외에 더 몇가지 살펴볼만한 트리의 연산 몇가지를 구현해보았습니다.

노드의갯수+ 단말노드의갯수+ 트리의 높이를 구하는 3가지 연산인데, 각 연산이 순환 호출이 주된 연산이므로

코드를 잘 살펴보고 이해해야합니다. 각 연산의 핵심 키워드는 아래와 같습니다.


1. 노드의 갯수

각 노드를 전체적으로 순회하여 각 서브트리에 대해 순환호출 한 뒤 반환되는 값에 1을 더하여 반환합니다.

(반환된 서브트리의 갯수와 루트노드의 갯수1을 더한값을 반환해야합니다.) 


2. 단말 노드의 갯수

역시 각 노드를 전체적으로 순회하면서 만약 왼쪽, 오른쪽 자식이 동시에 0이면 단말노드이므로 1을 반환합니다.

그렇지않으면 더 깊게 내려가 서브트리에 대해 순환 호출하여 단말노드를 탐색합니다.


*3. 트리의 높이

전체 순회하되 1,2처럼 반환된 값을 단순히 더하는게 아니라 서브트리에서 반환된 서브트리의 높이 중  최댓값을 구하여 반환합니다.

1,2 번에 비해 약간 까다로운 편인데 노드의 갯수가 작은 경우를 직접그려서 이해해보면 쉽게 이해할 수 있습니다.

주의: 매크로함수 정의 시 괄호를 잘 설정해야합니다.(괄호 설정 오류 시 높이 0출력)

수식 사이에는 괄호를 하나씩 더 쳐주는게 좋습니다. 


계산할 수식트리는 아래와 같습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a,b) (((a)>(b))?(a):(b))//괄호를 무조건 둘러싸자
 
//#define max(a,b) (((a)>(b))?(a):(b)) => 오류발생 
typedef struct treeNode
{
    int  data;
    struct treeNode* left, * right;
}treeNode;
 
treeNode n1 = { 0,NULL,NULL };
treeNode n2 = { 1,NULL,NULL };
treeNode n3 = { 3,&n1,&n2 };
treeNode n4 = { 2,NULL,NULL };
treeNode n5 = { 4,&n3,&n4 };
treeNode* root = &n5;
int calc_node_count(treeNode* root)
{
    int cnt = 0;
    if (root != NULL)
    {
        cnt = 1 + calc_node_count(root->left) + calc_node_count(root->right);
    }
    return cnt;
}
int calc_leaf_count(treeNode* root)
{
    int cnt = 0;
    if (root != NULL)
    {
        if (root->left == NULL && root->right == NULL)//단말 노드이면
        {
            return 1;
        }
        else
        {
            cnt = calc_leaf_count(root->left) + calc_leaf_count(root->right);
        }
    }
    return cnt;
}
int calc_height(treeNode* root)
{
    int height = 0;
    if (root != NULL)
    {
        height = 1 + max(calc_height(root->left), calc_height(root->right));
    }
    return height;
}
int main()
{
    printf("트리의 전체노드 갯수는 %d개입니다.\n",calc_node_count(root));
    printf("트리의 단말노드 갯수는 %d개입니다.\n",calc_leaf_count(root));
    printf("트리의 높이는 %d입니다.\n", calc_height(root));
}
cs



결과







저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


왼쪽자식+오른쪽 자식+루트 순으로 탐색하는 후위순회를 이용해 트리구조처럼 되어있는 컴퓨터의 디렉토리 용량을 계산할 수 있습니다.

단, 이진트리임을 가정하므로 각 디렉토리안에 2개를 초과하는 디렉토리 존재X


루트 디렉토리의 왼쪽 서브 디렉토리의 총 디렉토리 용량과 오른쪽 서브 디렉토리의 총 디렉토리의 용량을 구하고

그 두개의 용량합에 루트디렉토리의 용량을 합하면 총 디렉토리의 용량이 계산됩니다.

후위순회를 약간 응용하여 쉽게 구현할 수 있습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
typedef struct treeNode
{
    int data;
    struct treeNode* left, * right;
}treeNode;
 
int calc(treeNode* root)
{
    int left_size, right_size;
    if (root == NULL)return 0;
    else
    {
        left_size = calc(root->left);//후위
        right_size = calc(root->right);//후위
        return left_size + right_size + root->data;//계산한 용량값을 리턴한다.
    }
}
int main()
{
    treeNode n4 = { 500,NULL,NULL };
    treeNode n5 = { 200,NULL,NULL };
    treeNode n3 = { 100,&n4,&n5 };
    treeNode n2 = { 50,NULL,NULL };
    treeNode n1 = { 0,&n2,&n3 };
    printf("디렉토리의 총 용량은 %d입니다.\n", calc(&n1));
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


순환을 이용한 트리의 순회방법에는 3가지(전위,중위,후위) 순회 기법이있었습니다.

이런 표준적인 순회방법 외에도 레벨 순회가 많이 사용되는데, 레벨순회는 각 노드를 레벨순으로 검사하는 순회방법입니다.

위에서 부터 아래로 내려가면서 동일한 레벨의 경우 좌에서 우로 방문하며 순회를 진행합니다.


저번에 살펴본 순회기법들은 순환기법, 즉 스택구조를 이용했습니다.(순환호출==간접적인 스택의사용)

이번에 알아볼 레벨순회기법들은 큐를 이용합니다. 이 방식은 나중에 배울 그래프 파트의 BFS탐색과 거의 동일한 기법입니다.

즉 First-in First-out 속성을 이용하여 먼저 들어온 데이터를 먼저 출력하게끔 하기위해 큐를 사용합니다.


먼저, 큐에 있는 노드를 꺼내어 방문하고 그 노드의 자식노드를 큐에 삽입하는 작업을 큐에 더 이상의 노드가 없을 때 까지 반복합니다.


루트노드 큐에 삽입-> 큐가 empty하지 않을 때 까지 꺼내고 출력하고 자식노드를 큐에 삽입하는 연산 반복


결국, while(is_empty(&q)) 함수를 빠져나오게되면 최종적인 레벨순회가 끝나게됩니다.


구현을 위해 원형큐를 사용했고, 큐에 담겨지는 데이터는 트리노드이므로 큐의 데이터 타입을 treeNode*로 지정해야합니다.

결국 큐에 삽입되는 것은 트리노드가 되고 큐에담겨진 트리의 정보를 이용하여 순회를 진행합니다. 


아래의 수식트리를 이용하여 레벨순회를 구현해보았습니다.




코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_QSIZE 10
typedef struct treeNode
{
    char data;
    struct treeNode* left, * right;
}treeNode;
typedef treeNode* element;
typedef struct QType
{
    element queue[MAX_QSIZE];
    int front, rear;
}QType;
treeNode n1 = { 'A',NULL,NULL };
treeNode n2 = { 'B',NULL,NULL };
treeNode n3 = { 'C',NULL,NULL };
treeNode n4 = { 'D',NULL,NULL };
treeNode n5 = { '*',&n1,&n2 };
treeNode n6 = { '/',&n3,&n4 };
treeNode n7 = { '+',&n5,&n6 };
treeNode* root = &n7;
 
 
void init(QType* q)
{
    q->front = 0, q->rear = 0;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int is_full(QType* q)
{
    return (q->rear + 1) % MAX_QSIZE == q->front;
}
void enqueue(QType* q, element item)
{
    if (is_full(q))
    {
        printf("요소가 꽉 찼습니다.\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QSIZE;
    q->queue[q->rear] = item;
}
treeNode* dequeue(QType* q)
{
    if (is_empty(q))
    {
        printf("요소가 비었습니다.\n");
        exit(1);
    }
    else
    {
        q->front = (q->front + 1) % MAX_QSIZE;
        return q->queue[q->front];
    }
}
void level_order(treeNode* root)
{
    QType q;
    init(&q);
    if (root == NULL)return;
    enqueue(&q, root);
    while (!is_empty(&q))
    {
        root = dequeue(&q);
        printf("%c ", root->data);
        if (root->left)//왼쪽 자식이 존재하면
            enqueue(&q, root->left);
        if (root->right)//오른쪽 자식이 존재하면
            enqueue(&q, root->right);
    }puts(" ");
}
int main()
{
    level_order(root);
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
이진트리의 순회 (전위,중위,후위) 구현하기  (0) 2020.05.16


이진트리의 순회방법에는 전위순회, 중위순회, 후위순회의 3가지 방법이 있습니다.

이는 루트와 왼쪽 서브트리, 오른쪽 서브 트리 중에서 루트를 언제 방문 하느냐에 따라 구분할 수 있습니다.

기본적으로 트리의 순회는 순환구조를 이용합니다. 즉, 문제의 구조는 같고 크기만 작아지는 경우 순환을 적용할 수 있습니다.

루트:V, 왼쪽 서브 트리:L, 오른쪽 서브트리:R 이라고 할 때 순회과정은 아래와 같습니다.


V->L->R : 전위순회(preorder traversal)

L->V->R : 중위순회(inorder traversal)

L->R->V : 후위순회(postoreder traversal)


트리를 보고 각 순회방법에 따라 순회방법을 나열할 경우 아래처럼 순회방법을 적어놓고 생각하면 편합니다.



1. 전위 순회

 1) 루트 노드를 방문한다.

 2) 왼쪽 서브 트리를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.


2. 중위 순회

 1) 왼쪽 서브 트리를 방문한다.

 2) 루트 노드를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.


3. 후위 순회

 1) 왼쪽 서브 트리를 방문한다.

 2) 루트 노드를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.


트리의 순회과정을 코드를 보고 분석 할 때는 직접 작은 단위(예를들어 높이2의 노드가3인 간단한 트리구조)부터 직접 손으로 그려가며

이해하는게 편합니다. (노드갯수가 조금만 많아져도 복잡해짐) 


이제 아래와 같은 트리를 이용해 각 순회방법을 적용해 보겠습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
typedef struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
}treeNode;
 
treeNode n1 = { 1,NULL,NULL };
treeNode n2 = { 4,&n1,NULL };
treeNode n3 = { 16,NULL,NULL };
treeNode n4 = { 25,NULL,NULL };
treeNode n5 = { 20,&n3,&n4 };
treeNode n6 = { 15,&n2,&n5 };
treeNode* root = &n6;
void preorder(treeNode* root)
{
    //루트가 존재할 때
    if (root)
    {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
void inorder(treeNode* root)
{
    if (root)
    {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
void postorder(treeNode* root)
{
    if (root)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}
int main()
{
    printf("전위순회: ");
    preorder(root); puts(" ");
    printf("중위순회: ");
    inorder(root); puts(" ");
    printf("후위순회: ");
    postorder(root); puts(" ");
 
}
cs


결과




저작자표시

'자료구조 > 트리' 카테고리의 다른 글

쓰레드 이진트리를 이용한 중위 순회  (0) 2020.05.26
이진 트리의 연산(노드개수+단말노드개수+높이)  (0) 2020.05.16
후위순회를 이용한 디렉토리 용량 계산  (0) 2020.05.16
큐를 이용한 트리의 레벨순회  (0) 2020.05.16


저번에 살펴본 헤드노드를 이용한 이중연결리스트의 구현 프로그램은 헤드노드(더미노드)를 이용하여 편리하게 구현할 수 있었으나

구현의 로직이 지금껏 단순연결리스트, 원형리스트의 구현의 로직과는 조금 다르고 헤드포인터를 사용하지않고 헤드노드를 사용한다는점에서  

구현 시 오류의 발생확률과 삽입 시 정렬되는 노드가 역순이되므로 이를 정방향으로 정렬시켜줄 연산의 수정이 필요합니다.

(0,1,2,3,4 삽입 시 4->3->2->1->0)

따라서 지금껏 해온 표현방법대로 이중연결리스트를 구현하는게 더 편할 수 있기 때문에 이를 구현해봤습니다.

헤드노드를 이용한 방법과의 차이점은 일단 헤드노드 대신 헤드포인터를 사용하고, 삽입 되는 맨 첫 노드와 맨 끝 노드의 링크가 헤드노드를 

가리키지않고 NULL을 가리킨다는 점입니다.


*visual studio 2019의 경우 "월","수" 등의 데이터를 함수에서 char형 포인터로 받을 때 char*x로 선언하면 에러가 뜹니다.

(고정된 값 이므로 수정할 수 없기 때문에 (상수처리되기때문) const char*x로 선언해야합니다.)

어려운점은 딱히 없고 노드의 링크를 주고받는 연산만 잘 이해하면 될 것 같습니다.

이번 코드 역시 head의 변경이 생길 수 있는 함수(insert,delete함수)는 2차원포인터를 이용했습니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
typedef struct listNode
{
    char data[4];
    struct listNode* left;
    struct listNode* right;
}listNode;
void printList(listNode* head)
{
    listNode* temp;
    printf("DL=(");
    temp = head;
    while (temp != NULL)
    {
        printf("%s", temp->data);
        temp = temp->right;
        if (temp != NULL)printf(",");
    }
    printf(")\n");
}
void insertNode(listNode** head, listNode* pre, const char* x)
{
    listNode* newNode = (listNode*)malloc(sizeof(listNode));
    strcpy(newNode->data, x);
    if (*head == NULL)
    {
        newNode->left = NULL;
        newNode->right = NULL;
        *head = newNode;
    }
    else
    {
        newNode->right = pre->right;
        pre->right = newNode;
        newNode->left = pre;
        //삽입한 노드의 right에 노드가 있다면 newNode의 오른쪽 노드가 newNode를 가리킴
        if (newNode->right != NULL)
            newNode->right->left = newNode;
        //else의 경우 그대로 놔둠(newNode의 오른쪽링크로 통하는 노드가 없기때문)
    }
}
listNode* searchNode(listNode* head, const char* x)
{
    listNode* temp;
    temp = head;
    while(temp != NULL)
    {
        if (strcmp(temp->data, x) == 0)return temp;
        else temp = temp->right;
    }
    //이 경우 NULL반환(없으므로)
    return temp;
}
void deleteNode(listNode** head, listNode* removed)
{
    if (head == NULL)return;
    else
    {
        removed->left->right = removed->right;
        removed->right->left = removed->left;
        free(removed);
    }
}
int main()
{
    listNode* head = NULL;
    listNode* p;
    printf("이중연결리스트 생성하기\n");
    printList(head);
    printf("이중연결리스트에 [월]노드 삽입하기\n");
    insertNode(&head, NULL, "월");
    printList(head);
    printf("이중 연결리스트의 [월]노드 뒤에 [수]노드 삽입하기.\n");
    p = searchNode(head, "월"); 
    if(p!=NULL)
        insertNode(&head, p, "수");
    printList(head);
    printf("이중 연결리스트의 [수] 노드 뒤에 [금]노드 삽입하기.\n");
    p = searchNode(head, "수");
    if (p != NULL)
        insertNode(&head, p,"금");
    printList(head);
    printf("이중 연결리스트에서 [수]노드 삭제하기\n");
    if(p!=NULL)
    p = searchNode(head, "수"); deleteNode(&head, p);
    printList(head);
    return 0;
 
}
cs


결과




저작자표시

'자료구조 > 리스트' 카테고리의 다른 글

헤드노드를 이용한 이중연결리스트의 구현  (0) 2020.05.16
원형연결리스트 삽입 구현하기(맨앞,중간,맨뒤)  (0) 2020.04.29
단순 연결리스트에서 정렬된 값 찾기  (0) 2020.04.22
학생정보를 담은 단순연결리스트 구현하기  (0) 2020.04.22


헤드노드를 이용한 간단한 이중연결리스트의 구현프로그램입니다.

헤드노드는 구현의 편의를 위해 사용하는 것으로, 헤드노드를 이용해 이중연결리스트를 원형리스트와 결합된 형태로 사용할 수 있습니다. 


헤드노드는 리스트의 첫 번 째 노드를 가리키는 포인터로써, 아무런 데이터도 갖지않습니다. 주의해야 할 것은 헤드노드는 헤드포인터가 아니며 

원형리스트의 첫번째 삽입 연산처럼 본인의 left,right링크를 본인으로 설정해주는 초기화연산을 해야합니다. 

그러므로 헤드노드를 이용한 이중연결리스트의 구현에서 헤드 포인터는 필요가 없습니다.


또한 주의해야 할것은 헤드노드를 이용하여 삽입 할 때는 삽입한 노드를 맨 앞 노드로(헤드노드의 바로 뒤 노드) 설정하기 때문에

헤드노드의 left는 항상 맨 끝 노드를, right은 항상 맨 첫번 째 노드를 가리킵니다.  이 것이 원형리스트와 다른 유일한 점입니다. 

즉, 아래와 같은 구조를 가집니다.



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct DlistNode
{
    int data;
    struct DlistNode* left;
    struct DlistNode* right;
}DlistNode;
void init(DlistNode* head)
{
    //원형 연결리스트처럼 최초의 링크주소는 본인가리킴
    head->left = head;
    head->right = head;
}
void insert_node(DlistNode* before, DlistNode* newNode)
{
    newNode->left = before;
    newNode->right = before->right;
    //주의)헤드노드의 left는 맨 뒤 노드를 가리킴
    before->right->left = newNode;
    before->right = newNode;
    //결과: 0,1,2,3,4 삽입 후 출력:4,3,2,1,0
}
 void remove_node(DlistNode* before, DlistNode* removed)
{
    //헤드노드는 지워지면안됨
    if (removed == before)
        return;
    removed->left->right = removed->right;
    removed->right->left = removed->left;
    free(removed);
}
void display(DlistNode* head)
{
    DlistNode* temp;
    for (temp = head->right; temp != head; temp = temp->right)
    {
        printf("%d \t", temp->data);
    }puts(" ");
}
int main()
{
    DlistNode head_node;
    DlistNode* p[5];
    init(&head_node);
    //5개의 노드 삽입//0~4
    for (int i = 0; i < 5; i++)
    {
        p[i] = (DlistNode*)malloc(sizeof(DlistNode));
        p[i]->data = i;
        insert_node(&head_node, p[i]);
    }
    remove_node(&head_node, p[4]);
    display(&head_node);
}
cs


결과




저작자표시

'자료구조 > 리스트' 카테고리의 다른 글

헤드노드를 이용하지않는 이중연결리스트의 구현  (0) 2020.05.16
원형연결리스트 삽입 구현하기(맨앞,중간,맨뒤)  (0) 2020.04.29
단순 연결리스트에서 정렬된 값 찾기  (0) 2020.04.22
학생정보를 담은 단순연결리스트 구현하기  (0) 2020.04.22


원형연결리스트의 삽입의 3가지 경우(맨 앞, 중간, 맨 뒤)에 대해 간단하게 구현해봤습니다.


원형연결리스트에서는 head 노드를 항상 맨 뒤 노드를 가리키게 해야 삽입/삭제 구현 시 계산이 편리합니다.

head를 단순연결리스트 처럼 맨 앞 노드를 가리키게 한다면 삽입 시에 맨 앞 노드의 앞에 삽입해야 하므로 

맨 뒤 노드까지 탐색하는 번거로움이 있습니다. 그 이유는 맨 뒤 노드 다음 노드가 맨 처음 노드가 되기 때문입니다. 


head가 항상 맨 뒤 노드를 가리키게 한다면 맨 뒤 노드를 이용해서 삽입 후 head가 newNode를 가리키면 insert_last, 

아니면 insert_first가 되기 때문에 매우 간편하게 구현 할 수 있습니다. 


삽입함수에서 중간삽입의 경우는 "중간에 삽입한다."는 의미가 무조건 앞(pre)노드가 있어야 가능하므로 

pre가 없을 경우는 고려하지않았습니다.  그렇기 때문에 이에대한 오류처리는 하지않았습니다.

실제로 pre노드의 검색이 실패 할 경우(없는 값 뒤에 insert_middle할 경우) 프로그램은 무한루프에 빠집니다. 



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
 
typedef int element;
typedef struct ListNode {     // 노드 타입
    element data;
    struct ListNode* link;
} ListNode;
 
// 리스트의 항목 출력
void print_list(ListNode* head)
{
    ListNode* p;
 
    if (head == NULL) return;
    p = head->link;
    do {
        printf("%d->", p->data);
        p = p->link;
    } while (p != head);
    printf("%d\n", p->data); // 마지막 노드 출력
}
 
ListNode* insert_first(ListNode* head, element data)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    if (head == NULL) {
        head = node;
        node->link = head;
    }
    else {
        node->link = head->link;    // (1)
        head->link = node;        // (2)
    }
    return head;    // 변경된 헤드 포인터를 반환한다. 
}
 
ListNode* insert_last(ListNode* head, element data)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    if (head == NULL) {
        head = node;
        node->link = head;
    }
    else {
        node->link = head->link;    // (1)
        head->link = node;        // (2)
        head = node;        // (3)
    }
    return head;    // 변경된 헤드 포인터를 반환한다. 
}
ListNode* searchNode(ListNode* head, int data)
{
    ListNode* temp;
    temp = head;
    while (temp != NULL)
    {
        if (temp->data == data)return temp;
        else
            temp = temp->link;
    }
    return temp;
}
ListNode* insert_middle(ListNode* head, int pre_data, int data)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    if (head == NULL)
    {
        head = newNode;
        newNode->link = newNode;
    }
    else
    {
        ListNode* pre = searchNode(head, pre_data);
        
            newNode->link = pre->link;
            pre->link = newNode;
            head = newNode;
    }
    return head;
}
// 원형 연결 리스트 테스트 프로그램
int main(void)
{
    ListNode* head = NULL;
 
    // list = 10->20->30->35->40
    head = insert_last(head, 20);
    head = insert_last(head, 30);
    head = insert_middle(head, 30, 35);
    head = insert_last(head, 40);
    head = insert_first(head, 10);
    print_list(head);
    return 0;
}
 
cs


결과




저작자표시

'자료구조 > 리스트' 카테고리의 다른 글

헤드노드를 이용하지않는 이중연결리스트의 구현  (0) 2020.05.16
헤드노드를 이용한 이중연결리스트의 구현  (0) 2020.05.16
단순 연결리스트에서 정렬된 값 찾기  (0) 2020.04.22
학생정보를 담은 단순연결리스트 구현하기  (0) 2020.04.22

+ Recent posts

티스토리툴바