원형연결리스트의 삽입의 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


문제

단순연결리스트를 이용해서 숫자를 삽입할 때 마다 오름차순으로 정렬되게 끔 하는 간단한 프로그램을 만드시오.

조건: 아래의 추상 자료형(ADT) 함수를 모두 이용하여 5개이상의 원소를 삽입할 것



풀이

중요한 부분이 총 3가지라고 생각합니다. (글로는 설명이 힘들어서 소스코드만 올립니다..)

1. 삽입함수

정확한 이해가 필요했습니다. 삽입할 때 마다 정렬되게끔 하려면 몇가지 경우를 고려해야하는데 ,

작은 단위( 원소가 하나일 때, 두개 일 때, 3개일 때 ..) 부터 노트에 그려서 규칙을 찾아보면 의외로 간단합니다.

2. 삭제함수

Delete함수는 대충 책에서도 비슷하게 설명이 되있기 때문에 조금만 생각해보면 되지만 Clear함수는 원소를 삭제하면서 

그 위치를 기억하는 temp변수가 필요하다는 아이디어를 구현하는데 시간을 많이 썼습니다. 

단순히 removed함수만을 이용해서 삭제과정을 거치면 free하는 과정에서 연결리스트가 끊겨버리므로 실행 시 오류가 뜹니다.


3. 리스트의 원소갯수 반환 함수

원소갯수를 필요로하는 함수에 인자로 len을 추가시켜서 즉각즉각 갱신하도록했습니다.

ListNode 구조체에 len변수를 추가하여 사용해보려고 했는데 잘 안풀려서 다시 한번 고민을 해봐야겠습니다.



코드

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct ListNode
{
    double data;
    struct ListNode* link;
}ListNode;
void Add(ListNode**list,double item)
{
    ListNode* temp = (ListNode*)malloc(sizeof(ListNode));
    temp->data = item; temp->link = NULL;
    ListNode* pos = *list;
    if (*list == NULL) {
        *list = temp;
    }
    //같은것도 삽입해야하므로"="붙여야함!
    else if (temp->data <= (*list)->data)
        {
        temp->link = *list;
        *list = temp;
        }
    else
    {
        while (1)
        {
             if (pos->link == NULL)
            {
                pos->link = temp;break;
            }
            else if (temp->data < pos->link->data)
            {
                temp->link = pos->link;
                pos->link = temp;
                break;
            }
            //어떤 경우도 아닐 때 ex) 3 4 5 7일때 6삽입
            pos = pos->link;
        }
    }
}
void Delete(ListNode** list, double item,int len)
{
    ListNode* removed;
    if ((*list)->link == NULL)
    {
        free((*list));
        *list = NULL;
    }
    else if ((*list)->data == item)
    {
        removed = *list;
        *list = (*list)->link;
        free(removed);
    }
    else {
        ListNode* pre = *list;
        for (pre; pre->link->data != item; pre = pre->link);
         removed = pre->link;
        pre->link = removed->link;
        free(removed);
    }
    len--;
    
}
void Clear(ListNode** list, int len)
{
    ListNode* removed;
        ListNode* temp = *list;
        while (1)
        {
            removed = temp;
            if (removed == NULL)break;
            *list = (*list)->link;
            temp = temp->link;
            free(removed);
            
        }
}
ListNode* is_in_list(ListNode* list, double item)
{
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        if (temp->data == item)
            return temp;
 
        return temp;
}
int get_length(ListNode* list)
{
    int len = 0;
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        len++;
    return len;
}
int is_empty(ListNode* list)
{
    return list == NULL;
}
void display(ListNode* list)
{
    ListNode* temp = list;
    for (temp; temp != NULL; temp = temp->link)
        printf("%.0lf ", temp->data);
        printf("\n");
}
int main()
{
    double item;
    int len = 0;
    ListNode* head = NULL;
    ListNode* temp = NULL;
    //비었는지 검사, 1:비어있음 0:비어있지않음
    printf("리스트가 비었는지 검사: %d\n", is_empty(head));
    //최초에 무작위숫자 7개를 오름차순으로삽입시킴
    printf("7개의 원소를 삽입합니다.\n");
    for (int i = 0; i < 7; i++) {
        scanf("%lf", &item);
        Add(&head, item);
    }
    printf("리스트의 길이를 출력합니다.%d\n",get_length(head));
    printf("리스트의 모든 요소를 출력합니다.\n");
    display(head);
    //특정 값이 리스트에 있는지 탐색해본다.
        printf("리스트에 존재하는지 조사할 숫자: ");
        scanf("%lf", &item);
        temp = is_in_list(head,item);
        if (temp == NULL)printf("없음\n");
        else printf("%.0lf이(가)있습니다.\n", temp->data);
    
    //리스트에있는 원소중 한개 제거
        printf("리스트의 원소 중 제거하고 싶은 숫자: ");
        scanf("%lf", &item);
        temp = is_in_list(head, item);
        if (temp == NULL)printf("없음\n");
        else
        {
            Delete(&head, temp->data,len);
            printf("제거되었습니다.\n");
        }
        //삭제하고 나서 요소 확인
        printf("리스트의 모든 요소를 출력합니다.\n");
        display(head);
        printf("남아있는 원소의 갯수는 %d개입니다.\n", get_length(head));
        //모두 제거하기 
        printf("리스트의 원소를 모두 제거하겠습니다.\n");
        Clear(&head,len);
        printf("리스트에 남아있는 원소를 출력합니다.\n");
        display(head);
        
        printf("리스트가 비었는지 검사: %d\n", is_empty(head));
}
cs


결과




저작자표시

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

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#4. 수식을 후위식으로 변환하고 계산하기  (2) 2020.04.11
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25


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


제가갖고있는 2권의 자료구조책에서는 오로지 리스트로만 구현한 덱 밖에없었습니다.

현재 수강중인 자료구조에서는 교수님께서 원형큐를 응용한 덱구현 프로그램을 올려주셨는데 

확실히 리스트로 구현한 것보다 연산이 헷갈리고 어려운 것 같습니다.(이 이유때문에 책에 내용이없는것 아닐까 싶습니다.)


원형큐를 이용한 덱은 기존의  큐에서 아주 살짝만 응용하면 됩니다.

front 와 rear는 똑같이 0부터 시작하고 연산은 다음과 같습니다.

add_front: 꽉찼는지 확인 후 front 자리에 삽입 후 front=(front-1+MAX_SIZE)%MAX_SIZE;

add_rear:  꽉찼는지 확인 후 원형 큐의 enqueue와 동일

delete_front: 원형큐의 dequeue와 동일

delelte_rear: 현재 rear자리의 값 임시 저장 후 rear=(rear-1+MAX_SIZE)%MAX_SIZE 연산 후 임시 저장했던 rear자리 값 반환



즉, 한칸을 비워놓는것은 똑같고 add_front연산 후 front의 위치는 삽입한 자리 한칸 앞을 가리킵니다.



코드

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
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
/*
add_front로 1~3까지 삽입 후 각각 출력하고 
delete_rear로 모두 삭제하고 출력하기
//front 와 rear 위치 잘 보기
rear 1삽입
*/
#define MAX_SIZE 5
typedef struct
{
    int Dqueue[MAX_SIZE];
    int front, rear;
}DQType;
void init(DQType* q)
{
    q->front = q->rear = 0;
}
int is_full(DQType* q)
{
    return ((q->rear + 1) % MAX_SIZE == q->front);
}
 
int is_empty(DQType* q)
{
    return q->front == q->rear;
}
void add_front(DQType* q, int data)
{
    if (is_full(q))
    {
        fprintf(stderr, "요소가 꽉 찼습니다.\n");
        return;
    }
    q->Dqueue[q->front] = data;
    q->front = (q->front - 1+MAX_SIZE) % MAX_SIZE;
}
void delete_rear(DQType* q)
{
    if (is_empty(q))
    {
        fprintf(stderr, "요소가 없습니다.\n");
        return;
    }
    int now = q->rear;
    q->rear = (q->rear - 1+MAX_SIZE) % MAX_SIZE;
    //반환형 사용시 q->DQeue[now] 반환
}
void deque_print(DQType* q)
{
    if (!is_empty(q))
    {
        printf("DEQUE연산: (front=%d rear=%d)= ", q->front, q->rear);
        int i = q->front;
        do {
            i = (i + 1) % MAX_SIZE;
            //한번은 출력 하고 empty여부판단해야됨
            printf("%d |  ", q->Dqueue[i]);
            //비어있으면 탈출해야됨
            if (i == q->rear)break;
            //모든원소를 출력할 때 까지
        } while (i != q->front);
    }
    printf("\n");
}
int main(void) {
    DQType q;
    init(&q);
    for (int i = 0; i < 3; i++) {
        add_front(&q, i+1);
        deque_print(&q);
    }
    for (int i = 0; i < 3; i++) {
        delete_rear(&q);
        deque_print(&q);
    }
    return 0;
}
cs



결과





저작자표시


사이즈5인 큐에 1->2->3->4순으로 삽입후 

5번째 요소를 넣을 때 정상적으로 삽입됨을 확인하고 모든 원소 삭제를 삭제 후 현재 front와 rear변수 위치 확인하기 


핵심

1.원형큐는 최초의 한칸 (0번째 배열인덱스자리)을 비워둔다.

최초의 front ,rear 위치

선형큐: front==rear==-1

배열큐: front==rear==0


3. 사소한 실수 조심하기

선형큐 때는 연산 시 return 문을 한줄로 표현할 수 있었는데 

원형큐에서 삽입/삭제 연산 시 아래와 같이 작성하면 어떻게될까요?

q->Queue[(q->rear + 1) % MAX_SIZE]=data;

=> rear는 증가하지않고 1번 째 자리에 원소를 대입합니다.

결국에는 이러한 연산을 100번해도 1번째 자리에 원소를 100번 연산하는 꼴이됩니다.

그렇기 때문에  2줄로 나눠서 코드를 작성해야합니다.


q->rear=q->(rear+1)%MAX_SIZE;

q->Queue[q->rear]=data;



코드

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
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
/*사이즈5인 큐에 1->2->3->4순으로 삽입후
5번째 요소를 넣을 때 정상적으로 삽입됨을 확인하고 모든 원소 삭제를 삭제 후 현재 front와 rear변수 위치 확인하기*/
#define MAX_SIZE 5
typedef struct
{
    int Queue[MAX_SIZE];
    int front, rear;
}QType;
void init(QType* q)
{
    q->front = q->rear = 0;
}
int is_full(QType* q)
{
    return ((q->rear + 1) % MAX_SIZE == q->front);
}
void enQueue(QType* q, int data)
{
    if (is_full(q))
    {
        fprintf(stderr, "꽉 차서 원소를 삽입할 수 없어요..\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->Queue[q->rear]=data;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int deQueue(QType* q)
{
    if (is_empty(q))
    {
        fprintf(stderr, "큐가 비어서 삭제할 수 없습니다..\n");
        exit(1);
    }
    q->front = (q->front + 1) % MAX_SIZE;
    return q->Queue[q->front];
}
int main()
{
    QType q;
    int data;
    init(&q);
    //5개 요소를 꽉차지않을 때 까지(5개)삽입하기
    int i = 1;
    while (!is_full(&q))
    {
        printf("%d번째 원소를 삽입합니다.\n", i++);
        scanf("%d", &data);
        enQueue(&q, data);
    }
    //5번째 원소삽입-> 오류
    enQueue(&q, data);//-> 오류메시지출력
    while (!is_empty(&q))
        printf("%d을 삭제합니다.\n", deQueue(&q));
    
    printf("현재 front와 rear의 위치는(인덱스 자리는) 각각 %d %d입니다.\n", q.front, q.rear);
    return 0;
}
cs



결과


저작자표시

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

선형 큐(배열 큐) 구현하기  (0) 2020.04.16


사이즈5인 큐에 1->2->3->4->5순으로 삽입후  6번째 요소를 넣을 때 오류메시지를 출력하고

1,2 원소 삭제 후 남아있는 모든원소를 출력하기



핵심

1. 큐 사이즈 만큼 입력받을 때 

큐사이즈만큼 데이터를 입력받을 때 아래 코드에 나와있는 반복문처럼 원소를 삽입하면 됩니다.


2. 불필요한 코드 줄이기

모든 연산 함수의 return문을 보면 두번, 세번 쓸 코드를 한 코드로 표현할 수 있음을 알 수 있습니다.


코드

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
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
 
//    사이즈5인 큐에 1->2->3->4->5순으로 삽입후 
//  6번째 요소를 넣을 때 오류메시지 출력하고 1,2 원소 삭제 후 남아있는 원소 출력
#define MAX_SIZE 5
typedef struct
{
    int Queue[MAX_SIZE];
    int front, rear;
}QType;
void init(QType* q)
{
    q->front = q->rear = -1;
}
int is_full(QType* q)
{
    return q->rear == MAX_SIZE - 1;
}
void enQueue(QType* q, int data)
{
    if (is_full(q))
    {
        fprintf(stderr, "꽉 차서 원소를 삽입할 수 없어요..\n");
        return;
    }
    q->Queue[++(q->rear)] = data;
}
int is_empty(QType* q)
{
    return q->front == q->rear;
}
int deQueue(QType* q)
{
    if (is_empty(q))
    {
        fprintf(stderr, "큐가 비어서 삭제할 수 없습니다..\n");
        exit(1);
    }
    return q->Queue[++(q->front)];
}
int main()
{
    QType q;
    int data;
    init(&q);
    //5개 요소를 꽉차지않을 때 까지(5개)삽입하기
    int i = 1;
    while (!is_full(&q))
    {
        printf("%d번째 원소를 삽입합니다.\n", i++);
        scanf("%d", &data);
        enQueue(&q, data);
    }
    //6번째 원소삽입-> 오류
    enQueue(&q, data);//-> 오류메시지출력
    printf("삭제한 원소는 %d입니다.\n", deQueue(&q));
    printf("삭제한 원소는 %d입니다.\n", deQueue(&q));
    for (int i = q.front+1; i <= q.rear; i++)
    {
        printf("큐에 남아있는 원소는%d\n",q.Queue[i]);
    }
    return 0;
}
cs



결과




저작자표시

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

원형 큐 구현하기  (0) 2020.04.17

문제

main문에서 주어진 수식을 후위식으로 변환 후 변환 된 수식을 후위계산하여 값을 출력하시오


풀이

수식을 후위식으로 변환하는 함수부터 진행하기 때문에 스택의 요소는 char형 입니다.

일반적인 후위변환식을 작성하고, push,pop,peek등의 스택의 기본적인 연산 함수를 그대로 이용하여 후위계산을 하려면

스택의 요소를 int형으로 바꿔주어야하는데(숫자가 스택에 push되므로) 

스택에 push할 때 char형을 int형으로 형변환하여  push하는 것 외에 일반적인 수식계산 함수와 다를 게 없습니다.


코드

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
// C program to convert infix expression to postfix  
#pragma warning(disable:4996)
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
 
// Stack type 
struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};
 
// Stack Operations 
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
 
    if (!stack)
        return NULL;
 
    stack->top = -1;
    stack->capacity = capacity;
 
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
 
    return stack;
}
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
char peek(struct Stack* stack)
{
    return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
    if (!isEmpty(stack))
        return stack->array[stack->top--];
    return '$';
}
void push(struct Stack* stack, char op)
{
    stack->array[++stack->top] = op;
}
 
 
// A utility function to check if the given character is operand 
int isOperand(char ch)
{
  
    return (ch >= '0' && ch <= '9');
}
 
// A utility function to return precedence of a given operator 
// Higher returned value means higher precedence 
int Prec(char ch)
{
    switch (ch)
    {
    case '+':
    case '-':
        return 1;
 
    case '*':
    case '/':
        return 2;
 
    case '^':
        return 3;
    }
    return -1;
}
 
 
// The main function that converts given infix expression 
// to postfix expression.  
void infixToPostfix(char* exp)
{
    int i, k;
 
    // Create a stack of capacity equal to expression size  
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) // See if stack was created successfully  
        return;//오류 
 
    for (i = 0, k = -1; exp[i]; ++i)
    {
        // If the scanned character is an operand, add it to output. 
        if (isOperand(exp[i]))
            exp[++k] = exp[i];
 
        // If the scanned character is an ‘(‘, push it to the stack. 
        else if (exp[i] == '(')
            push(stack, exp[i]);
 
        // If the scanned character is an ‘)’, pop and output from the stack  
        // until an ‘(‘ is encountered. 
        else if (exp[i] == ')')
        {
            while (!isEmpty(stack) && peek(stack) != '(')
                exp[++k] = pop(stack);
            if (!isEmpty(stack) && peek(stack) != '(')
                return; // invalid expression         //오류      
            else
                pop(stack);
        }
        else // an operator is encountered 
        {
            while (!isEmpty(stack) && Prec(exp[i]) <= Prec(peek(stack)))
                exp[++k] = pop(stack);
            push(stack, exp[i]);
        }
 
    }
 
    // pop all the operators from the stack 
    while (!isEmpty(stack))
        exp[++k] = pop(stack);
 
    exp[++k] = '\0';
    printf("%s\n", exp);
    
 
}
int eval(char* exp)
{
    struct Stack* stack = createStack(strlen(exp));
    if (!stack) // See if stack was created successfully  
        exit(1);
    int op1, op2, n;
    char ch;
    n = strlen(exp);
    for (int i = 0; i < n; i++)
    {
        ch = exp[i];
        //숫자일 떄
        if (ch != '+' && ch != '-' && ch != '*' && ch != '/')
            push(stack, ch-'0');
        else
        {
            op2 = pop(stack);
            op1 = pop(stack);
            switch (ch)
            {
            case '+': push(stack, op1 +op2); break;
            case '-':push(stack, op1 -op2); break;
            case '*':push(stack, op1 *op2); break;
            case '/':push(stack, op1 /op2); break;
            }
        }
    }
    return pop(stack);
}
// Driver program to test above functions 
int main()
{
    int result;
    char exp[] = "3+4/4*3-2*2";
    infixToPostfix(exp);
    
    result=eval(exp);
    printf("결과값은 %d입니다.\n", result);
    return 0;
}
 
 
cs


결과





저작자표시

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

#6. 학생 정보를 관리하는 이진 탐색트리 구현  (0) 2020.05.26
#5. 단순연결리스트를 이용한 정렬리스트 만들기  (0) 2020.04.22
#3. 구조체,배열을 이용해 성적정렬하기  (6) 2020.04.01
#2. 순환함수를 이용한 코드 완성  (0) 2020.03.25
#1.수행시간을 측정해 결과값 제출  (0) 2020.03.25

+ Recent posts

티스토리툴바