#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"); } }
'DataStructure/Algorithm'에 해당되는 글 5건
- 2009.08.04 Simple Linked-List 전체 소스 및 결과
- 2009.08.04 key값을 기준으로 삽입과 삭제
- 2009.08.03 노드 삽입과 삭제, 출력
- 2009.08.03 Linked-List 초기화, 모든노드 삭제, 노드찾기
- 2009.07.31 Simple Linked-list 구현 명세서?
int insert_key( node *head, int f_key, int i_key )
삽입노드 선언
탐색노드 선언 및 head다음노드로 설정
key값을 찾거나 꼬리에 도달할때까지 반복
탐색노드를 다음노드로 이동
if( key값을 찾으면 )
삽입노드 할당 및 key값 설정 ( 할당에 실패하면 함수 종료 )
삽입노드 다음을 탐색노드 다음으로 설정
탐색노드 다음을 삽입노드로 설정
success 반환
else if( 꼬리라면 )
에러메세지 출력
fail 반환
- 성공시
- success반환
- 실패시
- fail 반환
- 인자값
- head : head 주소값
- i_key : 삽입할 노드의 key 값
int delete_key( node *head, int d_key )
탐색노드 선언 및 head 다음노드로 설정
탐색노드를 따라갈 이전노드 선언
탐색노드가 key값을 찾거나 꼬리에 도달할때까지 반복
이전노드를 탐색노드로 설정
탐색노드는 다음노드로 이동
if( key값을 찾았으면 )
이전노드 다음노드를 탐색노드 다음노드로 설정
탐색노드 해제
success 반환
else if( 꼬리라면 )
에러메세지 출력
fail 반환
- 성공시
- success반환
- 실패시
- fail 반환
- 인자값
- head : head 주소값
- int d_key : 삭제할 노드의 key 값
int insert_node( node *head, int i_key )
{
삽입노드 선언 및 할당
if( 할당에 실패할경우 )
fail 반환
삽입노드 다음노드를 head노드 다음노드로 설정
head노드 다음노드를 삽입노드로 설정
success 반환
}
성공시
success반환
실패시
fail 반환
인자값
head : head 주소값
i_key : 삽입할 노드의 key값
int delete_node( node *node_next ) {
삭제노드 선언
삭제노드를 node_next 다음노드로 설정
if( 삭제노드가 꼬리일 경우 )
에러문장 출력fail 반환
node_next의 다음노드를 삭제노드 다음노드로 설정
삭제노드 할당해제
success 반환
}
성공시
success반환
실패시
fail 반환
인자값
node_next : 삭제할노드의 전노드
void print_node( node *head ) {
탐색노드 선언
꼬리에 도착할때까지 반복
key 값 출력
다음노드로
}
성공시
없음
실패시
없음
인자값
head : head 주소값
node *init_node( void )
{
head node 선언 및 할당
head node 할당 실패 시
에러처리
tail node의 선언 및 할당
tail node 할당 실패 시
head 할당해제
에러처리
head와 tail 연결 및 tail next 처리
head 주소 값 반환
}
성공시
head 주소 반환
실패시
NULL 반환
인자값
없음.
tail->next의 처리는 3가지정도의 방법이 있다.
1. 자기자신을 가르키게 하는경우
2. head를 가르키게 하는경우
3. NULL을 가르키게 하는 경우
일단 NULL을 가르키게 하는 방식으로 code 를 작성.
node *delete_all( node *head )
{
순회노드 선언 및 head노드 다음으로 설정
해제노드 선언
순회노드가 tail에 이를 때까지 반복
해제노드는 순회노드로 설정
순회노드는 다음노드로 설정
해제노드 할당해제
head노드 다음노드를 tail(순회노드)로 설정
head노드 주소값 리턴
}
성공시
head 주소값 반환
실패시
NULL 반환
인자
head : head 주소
node *find_key( node *head, int s_key )
{
탐색노드 선언 및 head->next로 설정
탐색노드가 key값을 찾거나 꼬리에 이를때까지 반복
다음노드로 이동
if( key값을 찾았을경우 )
현재위치의 탐색노드 주소 반환
else if( 꼬리일경우 )
NULL 반환
}
성공시
현재위치의 탐색노드주소 반환
실패시
NULL 반환
인자값
head : head 주소값
s_key : 찾을 key값
{
head node 선언 및 할당
head node 할당 실패 시
에러처리
tail node의 선언 및 할당
tail node 할당 실패 시
head 할당해제
에러처리
head와 tail 연결 및 tail next 처리
head 주소 값 반환
}
성공시
head 주소 반환
실패시
NULL 반환
인자값
없음.
tail->next의 처리는 3가지정도의 방법이 있다.
1. 자기자신을 가르키게 하는경우
2. head를 가르키게 하는경우
3. NULL을 가르키게 하는 경우
일단 NULL을 가르키게 하는 방식으로 code 를 작성.
node *delete_all( node *head )
{
순회노드 선언 및 head노드 다음으로 설정
해제노드 선언
순회노드가 tail에 이를 때까지 반복
해제노드는 순회노드로 설정
순회노드는 다음노드로 설정
해제노드 할당해제
head노드 다음노드를 tail(순회노드)로 설정
head노드 주소값 리턴
}
성공시
head 주소값 반환
실패시
NULL 반환
인자
head : head 주소
node *find_key( node *head, int s_key )
{
탐색노드 선언 및 head->next로 설정
탐색노드가 key값을 찾거나 꼬리에 이를때까지 반복
다음노드로 이동
if( key값을 찾았을경우 )
현재위치의 탐색노드 주소 반환
else if( 꼬리일경우 )
NULL 반환
}
성공시
현재위치의 탐색노드주소 반환
실패시
NULL 반환
인자값
head : head 주소값
s_key : 찾을 key값
구조체 정의
typedef struct _node { int key; // key값을 저장 struct _node *next; // 다음 node의 주소 } node;
return Value definition.
#define success 1 #define fail 0성공할 경우 1을 return
실패할 경우 0을 return
Function List
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() 내림차순 정렬※ init_node를 제외한 모든 함수는 첫번째 인자로 head node를 요구한다.