Adventurer on ClipperShip

#include <stdio.h>
#include <stdlib.h>
typedef struct  _node
{
    int             key;
    struct _node    *next;
} node;
#define success 1
#define fail    0
node    *init_node( void );     //head와 tail node의 초기화
node    *delete_all( node *head );      // head와 tail을 제외한 모든 node 삭제
node    *find_key( node *head, int s_key ); // 주어진 key값으로 node탐색
int     insert_node( node *head, int i_key );   // head와 첫번째 node사이 삽입
int     delete_node( node *node_n );    // 주어진 node의 다음 node 삭제
int     insert_key( node *head, int f_key, int i_key ); // 주어진 key값의 node 새로운 node 삽입
int     delete_key( node *head, int d_key );    // 주어진 key값의 노드삭제
void    print_node( node *head );   // node 출력

//  구현해야할 함수
//  oscending_node()   오름차순정렬
//  descending_node()   내림차순 정렬
int main( int argc, char **argv )
{
    int     result  =   0;
    node    *temp   =   NULL;
    node    *head   =   init_node();
    fputs( "Insert Node 1 to 10\n", stdout );
    insert_node( head, 10 );
    insert_node( head, 9 );
    insert_node( head, 8 );
    insert_node( head, 7 );
    insert_node( head, 6 );
    insert_node( head, 5 );
    insert_node( head, 4 );
    insert_node( head, 3 );
    insert_node( head, 2 );
    insert_node( head, 1 );
    print_node( head );
    fputs( "Finding key 5\n", stdout );
    temp    =   find_key( head, 5 );
    printf( "Finding 5 is %ssuccessful\n", temp == NULL ? "un" : "" );
    fputs( "Insert key 11 after 3\n", stdout );
    insert_key( head, 3, 11 );
    print_node( head );
    fputs( "Delete key 10\n", stdout );
    delete_key( head, 10 );
    print_node( head );
    fputs( "Finding key 3 and Delete next node\n", stdout );
    temp    =    find_key( head, 3 );
    delete_node( temp );
    print_node( head );
    fputs( "Delete key 7\n", stdout );
    delete_key( head, 7 );
    print_node( head );
    fputs( "Delete all node\n", stdout );
    delete_all( head );
    print_node( head );
    return 0;
}
node    *init_node( void )
{
    node    *head   =   (node *)malloc( sizeof(node) ); // head node initialization
    node    *tail   =   (node *)malloc( sizeof(node) ); // tail node initialization
    if( head == NULL ) // Head Node에 대해 할당에 실패했을때
    {
        fputs( "Failed to allocate for Head node\n", stdout );
        return  NULL;
    }
    if( tail == NULL ) // Tail Node에 대해 할당에 실패했을때
    {
        fputs( "Failed to allocate for tail node\n", stdout );
        free( head );  // Tail Node에 대해 할당에 실패했을 땐, Head Node를 해제
        return NULL;
    }
    head->next  =   tail;
    tail->next  =   NULL;
    return  head;
}

node    *delete_all( node *head )
{
    node    *navi_node  =   head->next; // 순회노드 선언 및 head 다음으로 설정
    node    *free_node  =   NULL;          // 해제노드 선언
    while( navi_node->next != NULL ) // 순회노드가 tail에 이를때까지
    {
        free_node   =   navi_node;
        navi_node   =   navi_node->next;
        free( free_node );
    }
    head->next  =   navi_node; // navi_node 가 성공적으로 루프를 종료했다면 tail
    return head;
}
node    *find_key( node *head, int s_key )
{
    node    *navi_node =   head->next; // head 다음노드로 설정
    while( navi_node->key != s_key && navi_node->next != NULL ) // key값을 찾거나 꼬리에 이를때까지
        //
    {
        navi_node   =   navi_node->next;
    }
    if( navi_node->key == s_key ) // key값을 찾았을경우
    {
        return navi_node;
    }
    else if( navi_node->next == NULL ) // 꼬리일경우
    {
        fputs( "Node is tail\n", stdout );
        return NULL;
    }
}
int     insert_node( node *head, int i_key)
{
    node    *i_node =   NULL;  // 삽입노드 선언
    i_node          =   (node *)malloc( sizeof(node) ); // 삽입노드 할당
    if( i_node == NULL )
    {
        fputs( "Failed to allocate for Insert Node\n", stdout );
        return fail;
    }
    i_node->key     =   i_key;
    i_node->next    =   head->next;
    head->next      =   i_node;
    return success;
}
int     delete_node( node *node_d)
{
    node        *delete_node    =   node_d->next; // 삭제노드 선언 및 node_next다음노드로 설정
    if( delete_node->next == NULL )
    {
        fputs( "Next node is tail.\n", stdout );
        return fail;
    }
    node_d->next    =   delete_node->next;
    free( delete_node );
    return success;
}
int     insert_key( node *head, int f_key, int i_key )
{
    node    *i_node     =   NULL;
    node    *s_node     =   head->next; // 탐색노드
    while( s_node->next != NULL && s_node->key != f_key ) // key값을 찾거나 꼬리에 도달할때까지
    {
        s_node  =   s_node->next;
    }
    if( s_node->key == f_key ) // key값일경우
    {
        i_node          =   (node *)malloc( sizeof(node) );
        if( i_node == NULL ) // 할당에 실패했을때
        {
            fputs( "Failed to allocate for Insert node\n", stdout );
            return fail;
        }
        i_node->next    =   s_node->next;
        i_node->key     =   i_key;
        s_node->next    =   i_node;
        return success;
    }
    else if( s_node->next == NULL ) // 꼬리일경우
    {
        fputs( "Search node is tail.\n", stdout );
        return fail;
    }
}
int     delete_key( node *head, int d_key )
{
    node    *s_node =   head->next; // 탐색노드
    node    *p_node =   head; // 탐색노드를 따라갈 이전노드
    while( s_node->next != NULL && s_node->key != d_key ) // key값을 찾거나 꼬리에 도달할때까지
    {
        s_node  =   s_node->next;
        p_node  =   p_node->next;
    }
    if( s_node->key == d_key ) // key값일경우
    {
        p_node->next    =   s_node->next;
        free( s_node );
        return success;
    }
    else if( s_node->next == NULL ) // 꼬리일경우
    {
        fputs( "Search node is tail.\n", stdout );
        return fail;
    }
}
void    print_node( node *head )
{
    node    *c_node =   head->next; // 탐색노드
    int     index_node  =   0; // 노드 개수
    printf("--------------------------------------------------\n");
    while( c_node->next  != NULL )
    {
        index_node++;
        fprintf(stdout, "%2dth Node key value : %2d\n", index_node, c_node->key );
        c_node  =   c_node->next;
    }
    printf("--------------------------------------------------\n");
}
}

int insert_key( node *head, int f_key, int i_key )

삽입노드 선언

탐색노드 선언 및 head다음노드로 설정

key값을 찾거나 꼬리에 도달할때까지 반복

탐색노드를 다음노드로 이동

if( key값을 찾으면 )

삽입노드 할당 및 key값 설정 ( 할당에 실패하면 함수 종료 )

삽입노드 다음을 탐색노드 다음으로 설정

탐색노드 다음을 삽입노드로 설정

success 반환

else if( 꼬리라면 )

에러메세지 출력

fail 반환

1. 성공시
• success반환
2. 실패시
• fail 반환
3. 인자값
• head : head 주소값
• i_key : 삽입할 노드의 key 값
  

int     insert_key( node *head, int f_key, int i_key )
{
    node    *i_node     =   NULL;
    node    *s_node     =   head->next; // 탐색노드

    while( s_node->next != NULL && s_node->key != f_key ) // key값을 찾거나 꼬리에 도달할때까지
    {
        s_node  =   s_node->next;
    }

    if( s_node->key == f_key ) // key값일경우
    {
        i_node          =   (node *)malloc( sizeof(node) );
        if( i_node == NULL ) // 할당에 실패했을때
        {
            fputs( "Failed to allocate for Insert node\n", stdout );
            return fail;
        }
        i_node->next    =   s_node->next;
        i_node->key     =   i_key;
        s_node->next    =   i_node;
        return success;
    }
    else if( s_node->next == NULL ) // 꼬리일경우
    {
        fputs( "Search node is tail.\n", stdout );
        return fail;
    }
}

int  delete_key( node *head, int d_key )

탐색노드 선언 및 head 다음노드로 설정

탐색노드를 따라갈 이전노드 선언

탐색노드가 key값을 찾거나 꼬리에 도달할때까지 반복

이전노드를 탐색노드로 설정

탐색노드는 다음노드로 이동

if( key값을 찾았으면 )

이전노드 다음노드를 탐색노드 다음노드로 설정

탐색노드 해제

success 반환

else if( 꼬리라면 )

에러메세지 출력

fail 반환

1. 성공시
• success반환
2. 실패시
• fail 반환
3. 인자값
• head : head 주소값
• int d_key : 삭제할 노드의 key 값

int     delete_key( node *head, int d_key )
{
    node    *s_node =   head->next; // 탐색노드
    node    *p_node =   head; // 탐색노드를 따라갈 이전노드

    while( s_node->next != NULL && s_node->key != d_key ) // key값을 찾거나 꼬리에 도달할때까지
    {
        s_node  =   s_node->next;
        p_node  =   p_node->next;
    }

    if( s_node->key == d_key ) // key값일경우
    {
        p_node->next    =   s_node->next;
        free( s_node );
        return success;
    }

    else if( s_node->next == NULL ) // 꼬리일경우
    {
        fputs( "Search node is tail.\n", stdout );
        return fail;
    }
}

typedef struct  _node
{
    int             key;       // key값을 저장
    struct _node    *next;       // 다음 node의 주소
} node;

#define success 1
#define fail   0

node    *init_node( void );     //head와 tail node의 초기화
node    *delete_all( node *head );      // head와 tail을 제외한 모든 node 삭제
node    *find_key( node *head, int s_key ); // 주어진 key값으로 node탐색
int     insert_node( node *head, int i_key );   // head와 첫번째 node사이 삽입
int     delete_node( node *node_n );    // 주어진 node의 다음 node 삭제
int     insert_key( node *head, int f_key, int i_key ); // 주어진 key값의 node 새로운 node 삽입
int     delete_key( node *head, int d_key );    // 주어진 key값의 노드삭제
void    print_node( node *head );   // node 출력
//  구현해야할 함수
//  oscending_node()   오름차순정렬
//  descending_node()   내림차순 정렬

◎ Analysis of Algorithm

○ Empirical analysis(경험적 분석)     : 알고리즘을 프로그래밍 언어로 구현을 한 뒤, 이를 실행시켜 실시간을 비교해 보는 것

○ Mathematical analysis(수학적 분석) : 알고리즘을 프로그래밍 언어로 구현하지 않고, 단지 알고리즘 자체만으로 수학적 분석을 하는 것

● Best case and Worst case

○ Bast case  : 가장 작은 시간과 공간을 필요로 하는 경우

○ Worst case : 가장 많은 시간과 공간을 필요로 하는 경우

- 어떠한 알고리즘의 일반적인 경우 다른 알고리즘에 비해 매우 성능이 뛰어나나 최악의 경우에 많은 시간과 공간을 필요로 할 수 있는 현상이 있고, 어떤 알고리즘의 일반적인 경우는 다른 알고리즘에 비해 성능은 떨어지나 최악의 경우에도 일반적인 경우와 별 차이가 없는 현상이 있다.

- 최악의 경우는 알고리즘의 성능을 표현하는데 많이 쓰인다. 알고리즘의 속도를 표현할 때, 아무리 많은 시간과 공간이 필요한다 해도 최악의 경우를 넘지 않는다는 것을 보증할 때 쓰인다.

● 알고리즘의 분석의 단계

1. 알고리즘을 판단할 수 있는 입력자료 결정
2. 알고리즘을 구성하는 동작들을 추상적이고 기본적인 동작들로 분해하여 동작들의 수행시간을 계산
3. 수학적인 알고리즘 분석

● 알고리즘의 유형

알고리즘의 분석 결과는 입력되는 자료의 수 N에 대한 수행시간을 함수 관계로 표현

★ 1

입력자료 수에 관계없이 일정한 실행시간을 갖는 알고리즘

★ log N

입력자료 수에 따라 실행시간이 조금씩 늘어남. 주로 커다란 문제를 일정한 크기를 갖는 작은 문문제 쪼갤 때 나타는 유형

★ N

입력 자료수에 따라 선형적으로 실행시간이 걸리는 경우.

★ N log N

커다란 문제를 독립적인 작은 문제로 쪼개어 각각 해결하고 나중에 다시 하나로 합치는 경우.

★ N²

이중 루프 내에서 입력자료를 처리하는 경우.

★ N³

삼중 루프 내에서 입력자료를 처리하는 경우.

★ 2^N

 입력자료의 수가 늘어남에 따라 급격한 실행시간의 증가.