[C++] C++ 알고리즘 - 데쓰노트

C++ 알고리즘에 나와 있는 예제를 기반으로 작성 하였습니다. 

 

1. 9명이 사람이 있다. 

2. 9명이 손을 잡고 있다. 

    ( 1번이라는 Adam 부터 시작 하여 Zdam 까지의 사람이 손을 잡고 있다. ) 

char *saram[] = {"Adam","Bdam","Cdam","Ddam","Edam","Fdam","Gdam","Fdam","Zdam"};

3. 5번째의 사람으로 순차적으로 빠진다. 

4. 처음 5번째는 Edam 이다. 

5. 그 다음의 5번째는 빠진 자리부터 시작 하여 5번째의 사람이 빠진다. 

 

원형의 형태를 유지 한다. 

 

링크드 리스트의 기본 구조로 진행이 된다. 

#include <iostream>

struct node
{
	int key;
	char *delSaram;
	struct node *next;
};

char *saram[] = {"Adam","Bdam","Cdam","Ddam","Edam","Fdam","Gdam","Fdam","Zdam"};

 

초기화를 시작 한다. 

node의 구조체는 링크를 만들기 위한 부분이다. 

main의 전체 소스 입니다. 

int main(int argc, char** argv) {
	
	int i, N = 9, M = 5;
	struct node *t, *x;
	
	t = new node;
	t->key = 1;
	t->delSaram = saram[0]; 
	x = t; 
    
    printf("i %d %s\r\n",t->key,t->delSaram);
	
	for ( i = 2; i <=N; i++)
	{
		t->next = new node;
		t = t->next;
		t->key = i;
		t->delSaram = saram[i-1];
		
		printf("i %d %s\r\n",t->key,t->delSaram);
	}
	
	t->next = x;
	
	while( t != t->next )
	{
		for( i = 1; i < M; i++)
		{
			t = t->next;
		}
		
		printf("\r\n");
		
		printf("%d %s",t->next->key, t->next->delSaram );
		x = t->next;
		t->next = x->next;
		delete x;
	}
	
	printf("\r\n%d %s\r\n",t->key,t->next->delSaram);
		
	return 0;
}

 

링크에 값을 저장 합니다. 

초기의 1의 값은 for문 전에 입력을 합니다. 

	for ( i = 2; i <=N; i++)
	{
		t->next = new node;
		t = t->next;
		t->key = i;
		t->delSaram = saram[i-1];
		
		printf("i %d %s\r\n",t->key,t->delSaram);
	}

 

5번째의 사람을 찾습니다. 마지막 사람이 자기 자신을 가리킬 때까지 찾습니다. 

	while( t != t->next )
	{
		for( i = 1; i < M; i++)
		{
			t = t->next;
			//printf("# %d ",t->next->key );
		}
		
		printf("\r\n");
		
		printf("%d %s",t->next->key, t->next->delSaram );
		x = t->next;
		t->next = x->next;
		delete x;
	}
	
	printf("\r\n%d %s\r\n",t->key,t->next->delSaram);

 

출력을 하게 되면? 

이렇게 나오게 됩니다. 

 

여기서 new와 delete는 C++의 동적 메모리 할당을 위해서 사용되는 연산자 입니다. 

new로 할당된 메모리는 delete를 통해서 해제를 해야 합니다. 

 

C++를 C로 변경 하려면 

new 대신 malloc() 을 delete는 free() 함수를 사용합니다. 

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int key;
    char *delSaram;
    struct node *next;
};

char *saram[] = {"Adam", "Bdam", "Cdam", "Ddam", "Edam", "Fdam", "Gdam", "Fdam", "Zdam"};

int main(int argc, char** argv) 
{
    int i, N = 9, M = 5;
    struct node *t, *x;

    t = (struct node*)malloc(sizeof(struct node));
    t->key = 1;
    t->delSaram = saram[0];
    x = t;

    printf("i %d %s\r\n", t->key, t->delSaram);

    for (i = 2; i <= N; i++)
    {
        t->next = (struct node*)malloc(sizeof(struct node));
        t = t->next;
        t->key = i;
        t->delSaram = saram[i - 1];

        printf("i %d %s\r\n", t->key, t->delSaram);
    }

    t->next = x;

    while (t != t->next)
    {
        for (i = 1; i < M; i++)
        {
            t = t->next;
        }

        printf("\r\n");
        printf("%d %s", t->next->key, t->next->delSaram);
        
        x = t->next;
        t->next = x->next;
        free(x); 
    }

    printf("\r\n%d %s\r\n", t->key, t->delSaram);

    return 0;
}