문득 자료구조를 다시 공부해야한다는 생각이 든다.
 
기초를 단단히 하자...

참고문헌 - C 로 배우는 알고리즘 1



/************************************************************************/
/* 파일명 : LinkedList.cpp : 자료구조 링크드 리스트                              */
/* 작성일 : 2007. 1. 17
/* 작성자 : 박상현
/* 참고서적 : C 로 배우는 알고리즘
/************************************************************************/

#include <stdio.h>
#include <MALLOC.H>

typedef struct _node
{
 int key;
 struct _node *next;
} node;

node *head, *tail;

/************************************************************************/
/* 함수명 : init_list                                                  */
/* head, tail 초기화             */
/************************************************************************/
void init_list(void)
{
 head = (node*)malloc(sizeof(node));
 tail = (node*)malloc(sizeof(node));
 head->next = tail;
 tail->next = tail;
}

/************************************************************************/
/* 함수명 : delete_next                                                 */
/* t 의 next 노드를 삭제한다.           */
/************************************************************************/
int delete_next(node *t)
{
 node *s;
 if(t->next == tail)
 {
  return 0; // 꼬리는 지울 수 없음
 }
 s = t->next; // 삭제할 노드
 t->next = t->next->next; // 다음 노드로 연결
 free(s);  // 메모리 해제
 return 1;
}

/************************************************************************/
/* 함수명 : insert_after                                                */
/* t 의 next 에 노드를 삽입한다.          */
/************************************************************************/
node *insert_after(int k, node* t)
{
 node *s;
 s = (node*)malloc(sizeof(node));
 s->key = k;
 s->next = t->next;
 t->next = s;
 return s;
}

/************************************************************************/
/* 함수명 : find_node                                                   */
/* k 를 키로 갖는 노드를 찾는다.          */
/************************************************************************/
node *find_node(int k)
{
 node *s;
 s = head->next;
 while(s->key != k && s!= tail)
  s = s->next;
 return s;
}

/************************************************************************/
/* 함수명 : delete_node                                                 */
/* k 를 키로 갖는 노드를 삭제한다.
/************************************************************************/
int delete_node(int k)
{
 node *s;
 node *p;
 p = head;
 s = p->next;
 while(s ->key != k && s != tail)
 {
  p = p->next;
  s = p->next;
 }

 if(s != tail) // 찾았다면
 {
  p->next = s->next;
  free(s);
  return 1;
 }
 else
 {
  return 0;
 }
}

/************************************************************************/
/* 함수명 : insert_node                                                 */
/* k 를 키로 갖는 노드 앞에 t 를 키로 갖는 노드를 삽입한다.    */
/************************************************************************/
node *insert_node(int t, int k) // k 앞에 t 삽입
{
 node *s;
 node *p;
 node *r;
 p = head;
 s = p->next;
 while(s->key != k && s != tail)
 {
  p = p->next;
  s = p->next;

 }
 if(s != tail) // 찾았다면
 {
  r = (node*)malloc(sizeof(node));
  r->key = t;
  p->next = r;
  r->next = s;
 }
 return p->next;
}

/************************************************************************/
/* 함수명 : ordered_insert                                              */
/* 키로 정렬하여 삽입             */
/************************************************************************/
node *ordered_insert(int k)
{
 node *s;
 node *p;
 node *r;
 p = head;
 s = p->next;
 while(s->key <= k && s != tail)
 {
  p = p->next;
  s = p->next;
 }
 r = (node*)malloc(sizeof(node));
 r->key = k;
 p->next = r;
 r->next = s;
 return r;
}

/************************************************************************/
/* 함수명 : print_list                                                  */
/* t 노드부터 리스트를 출력해준다.          */
/************************************************************************/
void print_list(node *t)
{
 printf("\n");
 while(t != tail)
 {
  printf("%-8d", t->key);
  t = t->next;
 }
}

/************************************************************************/
/* 함수명 delete_all                                                    */
/* 리스트를 삭제한여 head 와 tail 만 남겨준다.       */
/************************************************************************/
node *delete_all(void)
{
 node *s;
 node *t;
 t = head->next;
 while(t != tail)
 {
  s = t;
  t = t->next;
  free(s);
 }
 head->next = tail;
 return head;
}

/************************************************************************/
/* 함수명 : main                                                        */
/* main function              */
/************************************************************************/
void main(void)
{
 node *t;

 init_list();

 // 순서를 유지하며 삽입
 ordered_insert(50);
 ordered_insert(60);
 ordered_insert(20);
 ordered_insert(40);
 ordered_insert(140);
 ordered_insert(50);
 ordered_insert(350);
 ordered_insert(3);
 ordered_insert(570);
 ordered_insert(860);

 printf("\nInitial Linked list is ");
 print_list(head->next);
 
 printf("\nFilding 570 is %ssuccessful", find_node(570) == tail ? "un" : "");

 t = find_node(3);
 printf("\nFilding 3 is %ssuccessful", t == tail ? "un" : "");

 printf("\nInserting 9 after 3");
 insert_after(9, t);
 print_list(head->next);

 t = find_node(60);
 printf("\nDeleting next last node");
 delete_next(t);
 print_list(head->next);

 printf("\nInsert node 2 before 3");
 insert_node(330, 350);
 print_list(head->next);

 printf("\nDeleting node 140");
 if(!delete_node(140))
  printf("\n deleting 140 is unsuccessful");
 print_list(head->next);

 printf("\nDeleting node 3");
 delete_node(3);
 print_list(head->next);

 printf("\nDeleting all node");
 delete_all();
 print_list(head->next);
 
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요