기억의 조각

#include <stdio.h>
#include <stdlib.h>
typedef struct _node
{
 int key;
 struct _node *next;
}node;
node *head,*tail;
void init_list(void) //초기화
{
 head=(node*)malloc(sizeof(node)); // 메모리 할당.
 tail=(node*)malloc(sizeof(node)); // 메모리 할당.
 head->next=tail; // 머리다음 꼬리.
 tail->next=tail; // 꼬리 다음 꼬리.
}
node *insert_after(int k,node *t) // 새 노드를 추가한 후 거기에 키값을 입력하고 그 노드의 주소를 반환.
{
 node *s; // 새노드 생성
 s=(node*)malloc(sizeof(node)); // 메모리 할당.
 s->key=k; // 새로 넣을 값을 넣고.
 s->next=t->next; // t가 가리키는 노와 s가 가리키는 노드를 같게 만들고
 t->next=s; // t가 가리키는 노드가 s를 가리키게 한다.
 return s; // s의 주소를 반환.
}
int delete_next(node *t) // 주소를 받아서 그 주소의 노드 다음노드를 지우는 함수.
{
 node *s; // 빈노드를 하나 만들고
 if(t->next == tail) // 다음노드가 꼬리이면 그냥 0리턴하고 종료.
  return 0;
 s=t->next; // 빈노드가 지울노드를 가리키게 하고
 t->next = t->next->next; // 빈노드 전의 노드는 다음다음 노드를 가리킨다.
 free(s); // 지울 노드가 들어가있는 s를 메모리 해제한다.
 return 1; // 제대로 지웠으면 1을 반환.
}
node *find_node(int k) // 키값을 받아서 그 키값이 어디있는지 주소를 반환하는 함수.
{
 node *s; // 빈노드를 생성.
 s=head->next; // 빈노드가 머리 다음을 가리키게 함.

  while(s->key!=k&&s!=tail) // s의 키값이 k 가 아니거나 s가 꼬리에 도달하기 전까지 반복.
  s=s->next; // s의 다음 노드를 계속 검색.
 return s; // 찾은 s의 주소값을 반환.
}
int delete_node(int k) // 키값을 찾아서 그 키값이 있는 노드를 삭제하는 함수.
{
 node *s; // 빈노드 생성
 node *p; // 빈노드 생성
 p=head; // 머리 노드
 s=p->next; // 머리의 바로 다음 노드
 while(s->key!=k&&s!=tail) // 키값을 찾거나 꼬리가 되기전까지 루프
 {
  p=p->next; // p는 다음노드를 가리키게.
  s=p->next; // s는 위 p의 다음노드를 가리키게. 엇갈리게 가는거다.
 }
 if(s!=tail) // 꼬리가 아니면 키값을 획득.
 {
  p->next=s->next; // 지우려는 노드가 s이기 때문에 p에게 s의 다음노드를 가리키게 한다.
  free(s); // s가 잡고있던 메모리를 반환.
  return 1; // 성공적으로 끝나면 1을 반환.
 }
 else return 0; // 꼬리면 0을 반환.
}
node *insert_node(int t,int k) // k앞에 t를 삽입.
{
 node *s; // 키값을 찾는 노드
 node *p; // s노드 앞의 노드
 node *r; // 값을 끼워넣기 위해 만든 빈노드.
 p=head; // delete_node 와 같은 기법. 머리노드 설정후
 s=p->next; // s는 p의 다음노드.
 while(s->key !=k && s!=tail) // 키값을 찾거나 꼬리가 되기전까지 루프
 {
  p=p->next; // p는 다음노드를 가리키게.
  s=p->next; // s는 p의 다음노드를 가리키게.
 }
 if(s!=tail) // 키값을 찾으면
 {
  r=(node *)malloc(sizeof(node)); // 빈노드에 메모리를 할당하고.
  r->key = t; // 키값을 빈노드에 집어넣고
  p->next=r; // p노드가 새 노드를 가리키게 하고.
  r->next=s; // 새노드는 찾은 키값의 앞에 둔다.

 }
 return p->next; // 새 키값의 주소를 반환 return r 해도 될듯.
}

node *ordered_insert(int k) // 검색해서 넣는 함수.
{
 node *s; // 머리 다음노드
 node *p; // 머리노드
 node *r; // 빈노드
 p=head; // 머리로 지정
 s=p->next; // 머리 다음으로 지정
 while(s->key<=k&&s!=tail) // 입력받은 k보다 s가 커질때까지
 {
  p=p->next; //p는 다음노드로.
  s=p->next; //s는 위의 p 다음노드로.
 }
 r=(node *)malloc(sizeof(node)); // 메모리 할당.
 r->key=k; // 새노드에 키값 입력
 r->next=s; // 다음노드가 s
 p->next = r; // p 다음노드는 새 노드 r
 return r; // r값 리턴.
}
void printnode(){
 node *p;
 p=head->next;
 while(p->next != tail)
 {
  printf("%d  ",p->key);
  p=p->next;
 }
}

void main()
{
 init_list();
 *ordered_insert(5);
 *ordered_insert(10);
 *ordered_insert(3);
 *ordered_insert(75);
 *ordered_insert(2);
 *ordered_insert(6);
 *ordered_insert(7);
 *ordered_insert(23);
 printnode();
}

기본적인 역할을 하는 단일 연결 리스트이다. 내용자체는 매우 쉬운데
구현하는건 역시 어렵다. 이재규님의 C로 배우는 알고리즘 예제코드 짜집기해서
만든 단일연결 리스트.

주말에 단일연결리스트를 확장해서 환형과 이중연결리스트를 만들어봐야겠다.
개념이 약간 다르지만 그럭저럭 할만할 듯 하다.

또.. 위의 ordered_insert 라는 함수는 순서를 오름차순으로 집어넣는데
저것도 응용이 가능할듯하다. 내림차순이라던가.

눈여겨볼만한 기법은 노드를 생성하거나 찾아서 지우거나 할때
찾는 키값을 지닌 곳의 노드 이외에 그 노드 바로앞을 가리키는 노드를
같이 가지고 두개가 나란히 검색하면 매우 편리하다라는 것.