Computer Science/Data Structure, Algorithm

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 3

TwinParadox 2017. 4. 3. 08:02
728x90

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 3



C언어로 쉽게 풀어쓴 자료구조

4장 Exercise 문제들이다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.


29. 이중 연결 리스트를 이용하여 숫자들을 항상 정렬된 상태로 유지하는 리스트 SortedList를 구현하여보라.

앞의 문제의 연산들을 구현하면 된다.

 


<SortedList.h>


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
#ifndef __SORTED_LIST_H__
#define __SORTED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int element;
typedef struct ListNode
{
    element data;
    struct ListNode* rlink;
    struct ListNode* llink;
} ListNode;
// 노드 초기화
void Init(ListNode* head);
// 노드 개수 카운트
int get_length(ListNode* const head);
// item이 리스트 안에 있는지 검사
int is_in_list(ListNode* const head, int item);
// 리스트 비었는지 확인
int is_empty(ListNode* const head);
// 정렬된 리스트에 추가
void AddNode(ListNode* head, int item);
// 리스트에서 삭제
void DeleteNode(ListNode* head, int item);
// 출력
void display(ListNode* const head);
// 동적 노드 생성
ListNode* CreateNode(int item);
// 리스트 클리어
void Clear(ListNode* head);
#endif
cs



<SortedList.cpp>


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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <stdlib.h>
#include "SortedList.h"
// 노드 초기화
void Init(ListNode* head)
{
    head->llink = head;
    head->rlink = head;
}
// 노드 개수 카운트
int get_length(ListNode* const head)
{
    ListNode* p = head;
    int cnt = 0;
    while (p->rlink != head)
    {
        cnt++;
        p = p->rlink;
    }
    return cnt;
}
// item이 리스트 안에 있는지 검사
int is_in_list(ListNode* const head, const int item)
{
    ListNode* p = head;
    while (p->rlink != head)
    {
        if (p->rlink->data == item)
            return TRUE;
        p = p->rlink;
    }
    return FALSE;
}
// 리스트 비었는지 확인
int is_empty(ListNode* const head)
{
    return (head == head->rlink) && (head==head->rlink);
}
// 정렬된 리스트에 추가
void AddNode(ListNode* head, int item)
{
    ListNode* p = head;
    ListNode* new_node = CreateNode(item);
    // 리스트에 아무것도 없을 때
    if (is_empty(p))
    {
        new_node->rlink = p;
        new_node->llink = p;
        p->rlink = new_node;
        p->llink = new_node;
        return;
    }
    // 리스트에 노드가 하나 이상 있을 때,
    p = p->rlink;
    while (p != head)
    {
        if (p->data >= item)
        {
            new_node->rlink = p;
            new_node->llink = p->llink;
            p->llink->rlink = new_node;
            p->llink = new_node;
            return;
        }
        p = p->rlink;
    }
    // 추가되는 노드가 리스트의 어느 값들보다 클 경우(말단에 추가)
    new_node->rlink = p;
    new_node->llink = p->llink->rlink;
    p->llink->rlink = new_node;
    p->llink = new_node;
}
// 리스트에서 삭제
void DeleteNode(ListNode* head, int item)
{
    ListNode* p = head;
    ListNode* pn;
    
    if (is_empty(p))
        return;
    pn = p->rlink;
    while (pn != head)
    {
        if (pn->data == item)
        {
            pn->llink->rlink = pn->rlink;
            pn->rlink->llink = pn->llink;
            free(pn);
            return;
        }
        pn = pn->rlink;
    }
}
void display(ListNode* const head)
{
    ListNode* p = head;
    if (is_empty(p))
        printf("Empty Node\n");
    while (p->rlink != head)
    {
        printf(" <- %d -> \n", p->rlink->data);
        p = p->rlink;
    }
}
ListNode* CreateNode(int item)
{
    ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
    new_node->data = item;
    new_node->llink = new_node;
    new_node->rlink = new_node;
    return new_node;
}
// 리스트 클리어
void Clear(ListNode* head)
{
    ListNode* pn;
    ListNode* p = head;
    if (head == head->rlink)
        return;
    p = p->rlink;
    pn = p;
    while (1)
    {
        p->llink->rlink = p->rlink;
        p->rlink->llink = p->llink;
        pn = p->rlink;
        free(p);
        p = pn;
        if (p == head)
            break;
    }
}
cs



<main.cpp>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include "SortedList.h"
int main(void)
{
    ListNode list1;
    Init(&list1);
    AddNode(&list1, 50);
    AddNode(&list1, 60);
    AddNode(&list1, 30);
    AddNode(&list1, 20);
    AddNode(&list1, 10);
    AddNode(&list1, 40);
    AddNode(&list1, 70);
    display(&list1);
    printf("%d\n", get_length(&list1));
    printf("%d", is_in_list(&list1, 10));
    DeleteNode(&list1, 30);
    printf("\n");
    display(&list1);
    Clear(&list1);
    printf("%d\n", get_length(&list1));
    display(&list1);
}
 
cs


728x90