연결리스트 활용 문제
[2] 임의 수의 학생명과 학과명(각 5자 미만)을 하나씩 입력받아 학과명에 “IS” 가 포함되는 그룹과 그렇지 않은 2개 그룹의 연결리스트를 각각 생성한 후 다음을 차례로 수행하는 프로그램을 작성
① 각 그룹을 학과 이름순(동일 학과내에서는 학생명 순)으로 정렬하여 출력
② 2그룹이 정렬되어 있다는 사실을 이용하여 1개의 연결리스트로 변환한 후 출력(추가적인 연결리스트 사용하지 말고 2개의 그룹 연결리스트만 사용)
먼저 굳노트에 끄적여본 생각들...
이문제에서 제일 고민한 부분은 정렬!이다. 먼저 학과명을 입력받아 연결리스트에 추가하는 과정에서 정렬을 동시에 진행할 것이지, 아니면 일단 연결리스트를 다 만들어 놓고 정렬을 진행할 것인지를 한참 고민했다. 배열을 이용해서 비슷한 과제를 받았을 때는 전자의 방법으로 가능했었다. 일단 후자로 코드를 만들었고 전자는 더 고민해봐야겠다!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#define SIZE 5
typedef struct element{
char stu[SIZE];
char dept[SIZE];
}element;
typedef struct listnode{
element data;
struct listnode *link;
}listnode;
int main(){
listnode *is=(listnode*)malloc(sizeof(listnode));
listnode *nis=(listnode*)malloc(sizeof(listnode));
listnode *pre, *pre2;
listnode *result;
element input;
int size_is=0, size_nis=0; //리스트 사이즈
is->link=NULL;
nis->link=NULL;
|
c |
연결리스트는 다음과 같이 구현했다. 학생이름과 학과명을 element라는 구조체로 묶었다. main에 정의되어있는 is는 is가 들어있는 학과의 헤드이고 nis는 is가 들어있지 않은 학과의 연결리스트 헤드이다. 두개의 연결리스트의 첫번째 노드는 dummy가 들어간다. insert()를 사용하기 위해서이다.
//main함수
pre=is;
pre2=nis;
//입력
while(scanf("%s-%s",input.stu, input.dept)!=EOF){
if(strstr(input.dept, "is")!=NULL){ //학과이름에 is 값 있을때
pre=insert(pre, input);
size_is++;
}
else{
pre2=insert(pre2, input);
size_nis++;
}
}
//insert함수
listnode* insert(listnode *pre, element value){
listnode *p=(listnode*)malloc(sizeof(listnode));
p->data=value;
p->link=pre->link;
pre->link=p;
return p;
}strstr을 이용해서 is의 유무를 파악하고 각각의 연결리스트에 노드를 추가해주었다. 누누이 말했듣이 insert함수는 노드가 추가되어야할 위치의 전 노드와 요소값을 인수로 보낸다.
//main함수
bubblesort(is, size_is);
bubblesort(nis, size_nis);
//1번 출력
for(listnode *i=is->link;i!=NULL;i=i->link){
printf("%s-%s\n", i->data.stu, i->data.dept);
}
printf("=================\n");
for(listnode *i=nis->link;i!=NULL;i=i->link){
printf("%s-%s\n", i->data.stu, i->data.dept);
}
//bubblesort함수
void bubblesort(listnode *head, int size){
listnode *p, *q;
int i,j;
p=head;
p=p->link;
for(i=0;i<size-1;i++){
q=p->link;
for(j=i+1;j<size;j++){
if(strcmp(p->data.dept, q->data.dept)>0){
swap(p,q);
}
else if(strcmp(p->data.dept, q->data.dept)==0){
if(strcmp(p->data.stu, q->data.stu)>0){
swap(p, q);
}
}
q=q->link;
}
p=p->link;
}
}bubblesort함수로 연결리스트의 노드들을 학과이름 올림차순으로 정렬해주었다. bubblesort 함수에서 p=p->link로 시작하는 이유는 넘겨준 연결리스트의 첫번째 노드에는 dummy값이 들어있기 때문이다. 첫번째 for문으로 p는 연결리스트의 맨마지막 노드를 제외한 모든 노드를 가르키게 된다. 두번째 for문으로는 q가 p가 가르키는 노드 이후의 노드들을 순차적으로 p와 비교하면서 strcmp값이 0보다 크면 즉시 노드의 element값만 교환한다. element 값만 교환하는 함수가 swap이다.
void swap(listnode *node1, listnode *node2){
element temp;
temp = node1->data;
node1->data = node2->data;
node2->data = temp;
}이렇게 하면 1번이 출력된다.
//main함수
result=merge(is->link, size_is, nis->link, size_nis);
//2번 출력
printf("==================\n");
for(listnode *i=result->link;i!=NULL;i=i->link){
printf("%s-%s\n", i->data.stu, i->data.dept);
}
//merge함수
listnode* merge(listnode *node1, int size1, listnode *node2, int size2){
listnode *r=(listnode*)malloc(sizeof(listnode));
listnode *pre;
int pa=0, pb=0;
r->link=NULL;
pre=r;
while(pa<size1&&pb<size2){
if(strcmp(node1->data.dept, node2->data.dept)<0){
pre=insert(pre, node1->data);
node1=node1->link;
pa++;
}
else{
pre=insert(pre, node2->data);
node2=node2->link;
pb++;
}
}
while(pa<size1){
pre=insert(pre, node1->data);
node1=node1->link;
pa++;
}
while(pb<size2){
pre=insert(pre, node2->data);
node2=node2->link;
pb++;
}
return r;
}2번에서 하나의 연결리스트로 만들기 위해 mergesort, 합병정렬을 사용했다. 정리하는 이시점에서 생각난 것인데, 교수님이 추가적인 연결리스트를 사용하지 말고 합병하라고 하셨는데 이것도 추가적인 연결리스트를 만든것인지 아닌지 모르겠다. 아예 is나 nis에 결과를 저장할 수 있도록 하나 더 만들어야겠다. 일단 합병정렬을 이용하면 결과는 잘 나온다.
추가한다! 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
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
|
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 5
typedef struct element{
char stu[SIZE];
char dept[SIZE];
}element;
typedef struct listnode{
element data;
struct listnode *link;
}listnode;
listnode* insert(listnode *pre, element value){
listnode *p=(listnode*)malloc(sizeof(listnode));
p->data=value;
p->link=pre->link;
pre->link=p;
return p;
}
void swap(listnode *node1, listnode *node2){
element temp;
temp = node1->data;
node1->data = node2->data;
node2->data = temp;
}
void sort(listnode *head, int size){
listnode *p=head;
listnode *q;
int i,j;
p=p->link;
for(i=0;i<size-1;i++){
q=p->link;
for(j=i+1;j<size;j++){
if(strcmp(p->data.dept, q->data.dept)>0){
swap(p,q);
}
else if(strcmp(p->data.dept, q->data.dept)==0){
if(strcmp(p->data.stu, q->data.stu)>0){
swap(p, q);
}
}
q=q->link;
}
p=p->link;
}
}
listnode* merge(listnode *node1, int size1, listnode *node2, int size2){
listnode *head=node1;
listnode *pre=node1;
int pa=0, pb=0;
while(pa<size1&&pb<size2){
if(strcmp(node1->data.dept, node2->data.dept)<0){
pre=node1;
node1=node1->link;
pa++;
}
else{
pre=insert(pre, node2->data);
node2=node2->link;
pb++;
}
}
while(pb<size2){
pre=insert(pre, node2->data);
node2=node2->link;
pb++;
}
return head;
}
int main(){
listnode *is=(listnode*)malloc(sizeof(listnode));
listnode *nis=(listnode*)malloc(sizeof(listnode));
listnode *pre, *pre2;
listnode *result;
element input;
int size_is=0, size_nis=0; //리스트 사이즈
is->link=NULL; //첫번째 노드 dummy
nis->link=NULL;
pre=is;
pre2=nis;
//입력
printf("입력\n");
while(scanf("%s-%s",input.stu, input.dept)!=EOF){
if(strstr(input.dept, "is")!=NULL){ //학과이름에 is 값 있을때
pre=insert(pre, input);
size_is++;
}
else{
pre2=insert(pre2, input);
size_nis++;
}
}
sort(is, size_is);
sort(nis, size_nis);
//1번 출력
printf("1번 출력\n");
for(listnode *i=is->link;i!=NULL;i=i->link){
printf("%s-%s\n", i->data.stu, i->data.dept);
}
printf("=================\n");
for(listnode *i=nis->link;i!=NULL;i=i->link){
printf("%s-%s\n", i->data.stu, i->data.dept);
}
strcpy(is->data.dept,"00");
result=merge(is, size_is, nis->link, size_nis);
//2번 출력
printf("==================\n");
printf("2번 출력\n");
for(listnode *i=result->link;i!=NULL;i=i->link){
printf("%s-%s\n", i->data.stu, i->data.dept);
}
}
|
cs |
강의 후..
이번 과제는 직접 발표하게 되는 영광을 얻었다. 그래서 직접 발표하고 교수님께서 코멘트해주셨다. 일단 나는 sorting하는 과정중 swap에서 노드들의 데이터만 교환하였는데 교수님이 그렇게 구현하면 배열과 차이점이 무엇이냐고 지적하셨다. 그래서 swap과정을 단순히 데이터가 아닌 노드들간의 swap으로 다시 바꾸어 보았다.
|
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
|
void swap(listnode *node1, listnode *node2){
listnode *temp;
temp=node1->link;
node1->link=node2->link;
node2->link=temp;
temp=node1->link->link;
node1->link->link=node2->link->link;
node2->link->link=temp;
}
void sort(listnode *head, int size){
listnode *p=head;
listnode *q;
int i,j;
for(i=0;i<size-1;i++){
q=p->link;
for(j=i+1;j<size;j++){
if(strcmp(p->link->data.dept, q->link->data.dept)>0){
swap(p, q);
}
else if(strcmp(p->link->data.dept, q->link->data.dept)==0){
if(strcmp(p->link->data.stu, q->link->data.stu)>0){
swap(p, q);
}
}
q=q->link;
}
p=p->link;
}
}
|
cs |
일단 노드들끼리 swap교환하려면 바꾸려고 하는 노드의 이전 노드에 대한 정보도 필요하다 그래서 애초에 sort할때 이전노드를 p,q라고 하고 직접적인 교환대상이 되는 노드를 p->link, q->link로 작성하였다. swap함수에서 temp를 하나만 사용하여 구현하였지만 외관상 link가 계속 이어지는 것이 보기 좋지 않으니 temp2를 사용하여 정리하는 것이 좋겠다.
이번 과제를 계기로 연결리스트를 조금 더 직감적으로 이해하게 된 것 같다...나름의 이점을 잘 파악하여 유용하게 써야겠다.