'Study/자료구조'에 해당되는 글 6건

  1. 2007/12/05 Red/Black Tree
  2. 2007/11/30 Pattern Matching
  3. 2007/11/27 hash 기본 구현.
  4. 2007/11/27 환형 리스트를 범용적으로 구현..
  5. 2007/04/29 퍼즐게임은 random으로 설정하면 안된다.
  6. 2007/04/09 힙 정렬 (1)

Red/Black Tree

from Study/자료구조 2007/12/05 10:46 view 27616
Red/Black를 자바로 구현해 놓은곳 최최고~~( 자바 최신 버젼을 깔아야 한다. http://java.com )
http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

1. RedBlack.c( http://lxr.linux.no/linux-old+v2.4.20/lib/rbtree.c )

more..

Pattern Matching

from Study/자료구조 2007/11/30 11:45 view 21278
모든소스 : http://www-igm.univ-mlv.fr/~lecroq/string/ ( string 알고리즘 이라는 책 사고싶네... )
1. Brute Force Text Search ( n*n 비효휼적 )

more..


2. Karp-Rabin Text Search

more..


3. Shift Or Text Search

more..


4. Morris_Pratt Text Search

more..


5. Knuth_Morris_Pratt Text Search

more..


6. Boyer - Moore Text Search

more..

hash 기본 구현.

from Study/자료구조 2007/11/27 19:19 view 25922
해쉬 구조를 알기 위해선 아래 문서를 읽어 보고...c로 해쉬를 구성해보자.
http://lxr.linux.no/source/include/linux/hash.h


1. 해쉬 함수는 여러가지 알고리즘이 있으나 커널에서는 간단하면서도 우수한 folding exclusive 방식을 사용.

#define PIDHASH_SZ  16
#define
pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

pid_hashfn(777)

( ( 777 >> 8 ) ^ 777 ) & ( 16 - 1 )

777                                           => 1100001001
777 >> 8                                   => 0000000011
( 777 >> 8 ) ^ 777                      => 1100001010
16 - 1                                       => 0000001111
( ( 777 >> 8 ) ^ 777 ) & ( 16 - 1 )  => 0000001010

2. 해쉬는 탐색을 위한 자료구조라고도 할 수 있다. 자료를 효율적으로 분산하여 저장할 수 있게 된다.
사용자 삽입 이미지
사용자 삽입 이미지


전체 소스~

more..

List를 C로만 구성하기 위해서 공개된 list 를 참고해 본다.
일단  http://lxr.linux.no/source/include/linux/list.h 를 참조.

1. 보통 리스트를 구현할 때 리스트와 자료형을 같이 사용하지만 이런 구현은 매번 리스트를 따로 구현해야하는 아픔이 있다.
사용자 삽입 이미지


2. 그래서 리스트의 구조를 구조체를 만들때 그 밑에 구현 해 놓는 방식을 사용하도록 한다.
3. 이렇게 되면 리스트를 포함 시켜놓으면 헤더 파일을 중심으로 리스트를 가질수 있다.

사용자 삽입 이미지

4. 리스트의 추가는 앞뒤의 객체에게 알려주면 된다.
void __list_add(struct list_head *new=0x3004,

            struct list_head *prev=0x1000,

            struct list_head *next=0x2004)

{

  next->prev = new;

  new->next = next;

  new->prev = prev;

  prev->next = new;

}


5. 구조체의 내용을 읽기 위해선 시작위치를 0으로 시작한다는 개념을 잡아야 한다. 

#define  list_entry( temp, type, list ) \

((type *)((char*)temp (unsigned long)(&((type *)0)->list)))

TASK *p = list_entry( temp, TASK, list );

p->pid;


전체 소스 ~

more..


http://www.devpia.com/Maeul/Contents/Detail.aspx?BoardID=50&MAEULNo=20&no=614873&ref=614868

http://kldp.org/node/25255      //Good Thread(깊이우선알고리즘)

-_-..아나 시방 계속 삽질했네..

완성된 상태에서 역순으로 섞어야 하는 거가 맞는거지..

예전에 퍼즐게임 뽑아서 맘대로 조립하면 안되는거랑 같은 원리 였군..OTL

조잡한 나의 알고리즘-_-...

more..


 

힙 정렬

from Study/자료구조 2007/04/09 23:16 view 34019

■ 힙 정렬 

힙정렬의 `힙(Heap)`인 이유는 힙(Heap)이라는 자료구조를 사용하기 때문이다. 힙은 기본적으로 이진트리 구성이며, 이 이진트리에 몇 가지 속성을 부여한 것이 힙이 된다. 

다음은 힙의 한 예로서 배열과 이진트리의 관계를 보여준다. 

 

사용자 삽입 이미지

  힙을 정의하자면 자식노드의 값보다 부모노드의 값이 같거나 큰, 완전 이진트리를 말한다. 즉 어떤 리스트가 힙으로 구성될 수 있다면 배열 상에서 인덱스 1에 해당하는 값인 뿌리노드의 값은 전체 노드의 값들보다 큰 특징을 갖는다.

 힙 정렬의 과정을 요약하면 다음과 같다. 

1. 리스트[배열]를 힙(Heap)으로 만든다.

2. 힙 상에서 정렬을 수행한다. 

우선 리스트를 힙으로 만드는 과정에서는 좌 하위트리와 우 하위트리가 각각 힙인 경우에 뿌리 노드의 재귀적인 이동을 통해 전체 트리를 힙으로 만드는 알고리즘이 사용된다. 즉, 끝 노드들은 그 자체로 힙이기 때문에 끝 노드를 자식노드로 가지는 노드들로부터 위의 알고리즘을 사용해 힙으로 만들면서 차례로 위로 올라오면서 전체가 힙의 구성이 완성 되어진다. 

그림으로 도식하면 다음과 같다.

사용자 삽입 이미지

 다음으로 힙 구조상에서 정렬하는 방법을 살펴보면, 힙은 뿌리노드의 값이 가장 크기때문에, 일단 정렬의 가장 기본이 되는 사항이 완성되어 있는 셈이다. 이 뿌리노드를 저장하고, 리스트 상의 맨 마지막 노드를 뿌리노드로 옮긴다. 이렇게 하면 이 노드는 뿌리노드만 힙이 아니고 좌 하위트리나 우 하위트리가 모두 힙이 된다.    여기에 힙 구조로 만드는 알고리즘을 적용하면 다시 뿌리노드의 값이 가장 큰 값이 된다. 그렇게 되면 이 뿌리노드의 값을 저장하고 다시 마지막 원소를 뿌리노드로 옮긴다. 이 과정을 반복하면 가장 큰 값부터 차례대로 찾아낼 수 있다. 

다음은 처음 두 개의 원소만 찾아내는 과정을 보인다.

사용자 삽입 이미지


 다음은 전체적으로 힙정렬되는 과정을 예를 보인다. 

   

사용자 삽입 이미지


  힙 정렬은 퀵 정렬과는 달리 수행성능이 매우 나빠지는 입력형태가 없으며, 합병정렬과는 달리 별도의 기억공간을 필요로 하지 않는다.[평균 수행시간 n log n 을 갖는다] 

void adjust(int *list, int i, int n)

/* i : adjust 알고리즘을시작하는노드의인덱스*/

/* n : 전체노드의개수*/

{

     int j, k, done;

     done = 0; // 아직끝나지않았음을표시

     k = list[i]; // 뿌리노드값, 즉옮겨야할원소의값

     j = 2 * i; // i 노드의좌자식노드

     while(( j <= n ) && (!done)) // 자식노드가있고not done 일때까지반복

     {

          if ( j < n )  // j + 1 < = n 과마찬가지로우자식노드의존재를검사

             if (list[j] < list[j+1])

                j = j + 1;  // 자식노드들중큰노드를선택

          if ( k >= list[j] )

             done = 1; // 자식노드보다크므로수행을중단

          else {

             list[j / 2] = list[j]; // 자식노드를부모노드로끌어올림

                                      // 자식노드에k값을쓰지않는이유는나중에

                                     // 수행이다끝난다음에쓰기때문

             j = 2 * j;

          }

     }

     list[ j / 2] = k; // 수행이끝나면찾아낸위치에맨처음저장한뿌리노드의값을저장

}

 

 void heap_sort(int *list, int n)

{

     int i, temp;

     for ( i = (n / 2) ; i >= 1 ; i-- ) // 초기힙만들기

         adjust(list, i, n);

     for ( i = (n - 1) ; i >= 1 ; i-- ) // 힙정렬의두번째단계

     {

         temp = list[i + 1];  // 마지막노드와뿌리노드의교환

         list[i + 1] = list[1];

         list[1] = temp;

         adjust(list, 1, i);  // i개의키에대하여adjust 적용

     }
}

이상으로 자주 사용되는 정렬법들을 알아보았는데 알고리즘별 속도를 간략히 도시하면 다음과 같다.

 

사용자 삽입 이미지

Tag |