참고자료
Program to Create a Circular Linked List of N Nodes and Count the Number of Nodes - javatpoint
Program to Create a Circular Linked List of N Nodes and Count the Number of Nodes on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.
www.javatpoint.com
circular linked list 를 다이아그램으로 표현하면 아래와 같다.
|
1
2
3
4
|
struct node{
int data;
struct node *next'
};
|
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void add(int data){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
if(head==NULL){
head=tail=newNode;
}
else{
tail->next = newNode;
tail = newNode;
}
tail->next = head;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
여기서 이 linked list를 print하거나 node의 수를 count할 때 기존의 방식으로 하면 문제가 생긴다.
tail에 해당하는 node가 next로 head를 point하고 있기 때문에 next point로 circulation이 존재한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void display() {
struct node *current = head;
if(head == NULL) {
printf("List is empty\n");
return;
}
while(current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
따라서 current 값은 항상 NULL이 아니게 되고 무한loop를 돌게된다.
이 점을 해결하기 위해서 나는 아래와 같이 코드를 짰다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void display(){
struct node *current = head;
if(head==NULL){
printf("The list is empty");
}
else{
printf("%d ",current->data);
current = current->next;
}
while(current!=NULL&¤t!=head){
printf("%d ",current->data);
current = current->next;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
head가 NULL이면 예외로 처리하고 NULL이 아니면 else문에서 head를 한번 출력하고 current=current->next를 해주고,
다음 while 문에서 current가 NULL이 아니고 head가 아닐 때 라는 조건으로 loop를 돌리는 것이다.
이렇게 되면 current는(head가 NULL이 아닐 때)
1. else문에서 head부분이 한번 출력되고
2. while문에서 head->next부터 tail까지 한번씩 출력된다.
단순하게 논리구조를 생각하니 이렇게 짜게 됐는데 원문의 코드를 참고하니 Do-while loop를 이용하여 코드를 더 간단하게 짰다.
사실 c를 공부하면서 do-while을 배우긴 했는데 실제로 사용해본 적이 적어서 이 알고리즘에 내가 적용하지 못했던 것 같다. 이 상황에서는 do-while을 활용하는 것이 좋아 보인다.
실제 실행 부분에서 복잡성에 관하여 차이가 없어 보이긴 하는데 사실 잘 모르겠다. 나중에 알아보자,
코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
|
void display() {
struct node *current = head;
do{
printf("%d",current);
current = current->next;
}while(current != head);
printf("Count of nodes present in circular linked list: %d",count);
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
count 부분도 동일하다.
|
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
|
//내가 짠 코드
void count(){
int i;
struct node *current = head;
if(head==NULL){
i=0;
}
else{
i=1;
current = current->next;
}
while(current!=NULL&¤t!=head){
i++;
current = current->next;
}
printf("\nThe number of nodes is : %d",i);
}
}
|
//참고자료의 코드 Do-while void countNodes() { struct node *current = head; do{ count++; current = current->next; }while(current != head); printf("Count of nodes present in circular linked list: %d",count); |
Do-while
do{
loop
}while(조건);
댓글