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

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

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

(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


10개의 임의의 정수를 단순 연결리스트의 리스트에 담고 최솟값과 최댓값을 찾는 간단한 문제입니다.

최솟값과 최댓값을 찾는 pivot(시작 비교 할 값)을 리스트의 첫번째 원소로 지정하여 리스트를 탐색하여 값을 반환합니다.


코드

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
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct ListNode {     // 노드 타입
    int data;
    struct ListNode* link;
} ListNode;
 
// 오류 처리 함수
void error(char* message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
void insert_last(ListNode** head, int value)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    if (p == NULL)return;
    p->data = value; p->link = NULL;
    if (*head == NULL)
        *head = p;
    else
    {
        ListNode* temp = *head;
        while (temp->link != NULL)
            temp = temp->link;
 
        temp->link = p;
    }
}
int check_minval(ListNode*head)
{
    ListNode* temp = head;
    int min_val = temp->data;
    for (temp; temp != NULL; temp = temp->link)
        if (min_val > temp->data)
            min_val = temp->data;
    return min_val;
}
int check_maxval(ListNode*head)
{
    ListNode* temp = head;
    int max_val = temp->data;
    for (temp; temp != NULL; temp = temp->link)
        if (max_val < temp->data)
            max_val = temp->data;
    return max_val;
}
 
// 테스트 프로그램
int main(void)
{
    ListNode* head = NULL;
    int data;
    int max_val, min_val;
    //10개의 숫자를 넣기
    for (int i = 0; i < 10; i++)
    {
        scanf("%d", &data);
        insert_last(&head, data);
    }
    min_val = check_minval(head);
    max_val = check_maxval(head);
    printf("최솟값은 %d, 최댓값은 %d입니다.\n", min_val, max_val);
    return 0;
}
 
cs


결과


저작자표시

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

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


5명의 학생 정보를 저장하는 단순연결리스트를 구현해봤습니다.

첫노드, 특정 노드의 앞,뒤, 맨 끝 노드 삽입 등의 경우를 고려하지않고 단순히 입력데이터를 맨 끝에 추가하였습니다.


주의

아래 코드와 같은 구현의 insert함수에서 이중 포인터가 아닌 단순1차원 포인터를 사용하면 정답이 출력되지않습니다.

이유는 1차원 포인터 사용 시 insert함수 내부에서 main문의 head가 아닌 새로운 head변수를 이용하므로

즉, 주소값이 아닌 값을 이용한 call by value 형식이므로 함수내부에서 함수내부의 새로운 head로 연산이 진행될 뿐

main문의 head에는 영향이 없습니다.

즉, 최초에 비어있는 리스트에 1차원포인터로 insert함수에 인자를 넘겨주면 연산 후 main문의 head는 여전히 NULL상태가 됩니다. 

따라서 2차원 포인터로 주소값을 받아 함수 내부에서 head를 변경 시킬 수 있도록 해야합니다.

1차원 포인터를 쓰고싶다면 insert 함수에서 사용한 head를 ListNode*형으로 반환하여 main문에서 사용하면됩니다.


코드

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
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    char name[10];
    int age;
    int height;
} element;
 
typedef struct ListNode {     // 노드 타입
    element data;
    struct ListNode* link;
} ListNode;
 
// 오류 처리 함수
void error(char* message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
void insert_last(ListNode** head, element value)
{
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    if (p == NULL)return;
    p->data = value; p->link = NULL;
    if (*head == NULL)
        *head = p;
    else
    {
        ListNode* temp = *head;
        while (temp->link != NULL)
            temp = temp->link;
 
        temp->link = p;
    }
}
 
void print_list(ListNode* head)
{
    for (ListNode* p = head; p != NULL; p = p->link)
        printf("이름:%s 나이:%d 키%d \n", p->data.name, p->data.age, p->data.height);
}
 
// 테스트 프로그램
int main(void)
{
    ListNode* head = NULL;
    element data;
    //5명의 학생 정보 입력받기
    for (int i = 0; i < 5; i++)
    {
        scanf("%s %d %d", data.name, &(data.age), &(data.height));
        insert_last(&head, data);
    }
    print_list(head);
    return 0;
}
 
cs


결과





저작자표시

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

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

+ Recent posts

티스토리툴바