6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립 예 : 0 4, 3 1, 6 10, 8 9, 7 4, 6 8, 3 5, 2 11, 11 0 동치클래스 : {0, 2, 4, 7, 11; {1, 3, 5; {6, 8, 9, 10 4 장. 리스트 (Page 1)
동치클래스검색알고리즘 1. 동치항 <i, j> 를입력한후저장 2. 원소 0 부터시작하여 0 의동치항 <0, j> 항들을검색한후, j 를 0 과동일한클래스에포함 Transitivity 속성에의해 <j, k> 항의원소 k 도 0 과동일한클래스에포함됨 이과정을반복하여 0 을포함하는모든원소를발견 3. 클래스에포함되지않은다른원소들에대해단계 2 를반복 4 장. 리스트 (Page 2)
동치클래스검색을위한자료구조 (1) 변수선언 m: 입력된동치항의수 n: 원소의수 동치항의구현방법 배열 : pairs[n][n] <i, j> 가입력될경우, pairs[i][j] 와 pairs[j][i] 를 1 로설정 원소의수에비해동치항의수가적을경우, 메모리낭비 n 개의연결리스트 : seq[n] <i, j> 가입력될경우 노드 j 를 seq[i] 가가리키는리스트에추가 노드 i 는 seq[j] 가가리키는리스트에추가 4 장. 리스트 (Page 3)
예 : 동치항의입력이완료된후의리스트 seq [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] data link 11 3 11 5 7 3 8 4 6 8 6 0 ^ ^ ^ ^ ^ ^ data link 4 1 0 10 9 2 ^ ^ ^ ^ ^ ^ 4 장. 리스트 (Page 4)
동치클래스검색을위한자료구조 (2) 일차원 boolean 배열 out[n] out[i] = TRUE: 원소 i 를출력하여야함. ( 초기값 ) out[i] = FALSE: i 가이미출력되어다시출력할필요없음. 리스트표현을이용한동치클래스검색 Step 1: 동치항을입력받아 seq[] 를이용한리스트구성 Step 2: out[i] = TRUE 인첫번째원소 i, 0 i < n, 를선택하여 seq[i] 리스트를스캔하면서리스트의원소들을출력 seq[i] 의원소중에서 out[] 배열의값이 TRUE 인원소들의리스트들을현재스캔을완료한후스캔하여야함. (Stack 이필요 ) Stack 을구현하기위하여해당노드의 link 필드를 stack 의다음원소를가리키는포인터로변경 4 장. 리스트 (Page 5)
Program 4.21: 초기동치알고리즘 void equivalence ( ) { initialize; while (there are more pairs) { read the next pair < i, j >; process this pair; initialize the output; do output a new equivalence class; while ( not done ); 4 장. 리스트 (Page 6)
Program 4.22: 수정된동치알고리즘 void equivalence() { initialize seq[] to NULL and out[] to TRUE; while ( there are more pairs ) { read the next pair < i, j >; put j on the seq[i] list; put i on the seq[j] list; for (i = 0; i < n; i++) if (out[i]) { out[i] = FALSE; output this equivalence class; 4 장. 리스트 (Page 7)
Program 4.23: 최종동치알고리즘 (1) #include <stdio.h> #include <alloc.h> #define MAX_SIZE 24 #define IS_FULL(ptr) (!(ptr)) #define FALSE 0 #define TRUE 1 struct node { int data; struct node *link; ; // 정수형의데이터가입력된다고가정 void main(void) { short int out[max_size]; struct node *seq[max_size], *x, *y, *top; int i, j, n; printf("enter the size (<= %d) ", MAX_SIZE ); scanf("%d", &n); 4 장. 리스트 (Page 8)
Program 4.23: 최종동치알고리즘 (2) for (i = 0; i < n; i++) // seq[] 와 out[] 배열을초기화 { out[i] = TRUE; seq[i] = NULL; /* Phase 1: Input the equivalence pairs: */ printf("enter a pair of numbers (-1-1 to quit): "); scanf("%d%d", &i, &j); while (i >= 0) { // 음수가입력되면리스트생성종료 x = (struct node *) malloc(sizeof(struct node)); if (x == NULL) { fprintf(stderr, "The memory is full"); exit(1); x data = j; x link = seq[i]; seq[i] = x; // j를 i 리스트의앞에추가 x = (struct node *) malloc(sizeof(struct node)); if (x == NULL) { fprintf(stderr, "The memory is full"); exit(1); x data = i; x link = seq[j]; seq[j] = x; // i를 j 리스트의앞에추가 printf("enter a pair of numbers (-1-1 to quit): "); scanf("%d%d", &i, &j); 4 장. 리스트 (Page 9)
Program 4.23: 최종동치알고리즘 (3) for (i = 0; i < n; i++) /* Phase 2: output the equivalence classes */ if (!out[i]) continue; printf(" \ n New class: %5d ", i ); // 새로운클래스출력시작 out[i] = FALSE; // i를출력하였음. x = seq[i]; top = NULL; // 스택초기화 for ( ; ; ) { // 클래스의나머지원소를찾자 while (x) { // 리스트를스캔 j = x data; if (out[j]) { // j가아직출력되지않았다면 printf("%5d", j ); out[j] = FALSE; // j를출력한후, y = x link; x link = top; top = x; x = y; // push() else x = x link; if (!top) // 현재클래스의모든원소를출력하였음. break; x = seq[top data]; top = top link; // pop() 4 장. 리스트 (Page 10)
예 : 스택의삽입과삭제과정 seq [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] top y data link data link 11 3 11 5 7 3 8 4 6 8 6 0 ^ ^ ^ ^ ^ ^ ^ top 4 1 0 10 9 2 ^ ^ ^ ^ ^ ^ top 4 장. 리스트 (Page 11)
동치알고리즘의분석 m: 입력된동치항의수, n: 원소의수 초기화및동치항의입력단계 : O(m+n) 동치클래스출력단계 : O(m+n) 각노드는기껏해야한번스택에저장 2*m 개의노드가존재하며, for loop 는 n 번실행 O(2m) O(n) 전체적인시간복잡도 = O(m+n) 4 장. 리스트 (Page 12)
문제 1 data 필드와 link 필드를갖는노드들로구성된아래연결리스트에서 data 필드가 b 인노드를삭제하는 C 프로그램의부분은? 단, first 는리스트를가리키는포인터이며, temp 는 first 와동일한타입의포인터이다. [10] 1 temp = first; first = first->link; free(temp); 2 first = first link; temp = first; free(temp); 3 temp = first link; first link = first link link; free(temp); 4 first link = first link link; temp = first link; free(temp); 5 temp = first link; free(temp); first link = first link link; 13
문제 2 다음은원형연결리스트 (circular linked list) 에서 data 필드값이 0 보다작은노드들의개수를반환하는함수이다. A 와 B 에들어갈내용은무엇인가? [10] struct node { intdata; struct node *next; ; int compute_sum(struct node *ptr) { struct node *p = ptr next; int count = (ptr data < 0)? 1 : 0; for ( A ) if ( B ) count++; return count; 4 장. 리스트 (Page 14)
문제 3 다음은이중연결리스트 (doubly linked list) 에서 temp 가가리키는노드를 ptr 이가리키는노드의왼쪽에삽입하는알고리즘의일부이다. A 와 B 에들어갈문장은무엇인가? 단, ptr 의이전노드와다음노드는 NULL 이아니다. [10] before next 100 200 temp 150 ptr temp next = ptr; A ; B ; ptr before = temp; 4 장. 리스트 (Page 15)
문제 4 이중연결리스트에서노드 p 의다음 (next) 노드가 q 이고노드 q 의이전 (prev) 노드가 p 인경우, 인접한 p, q 노드의위치를서로바꾸기위하여아래연산들이필요하다. 어떤순서로실행되어야하는가? ( 단, p, q 노드는모두연결리스트의처음노드나마지막노드가아니라고가정한다 ) [10] 1 p prev = q; 2 p prev next = q; 3 p next = q next; 4 q next = p; 5 q next prev = p; 6 q prev = p prev; 4 장. 리스트 (Page 16)
문제 5 두개의단순연결리스트 x, y 의후위노드 ( 음영부분 ) 들을서로스왑 (swap) 하고자한다. 후위노드들의 next 는 NULL 이아니라고가정할때, 아래 A 와 B 의 box 를채우시오. [10] x... x... y... y... struct node { int data; struct node *next; ; struct node *swap_next_node(struct node *x, struct node *y) { struct node *tmp; tmp = x next next; A ; tmp = x next; B ; 4 장. 리스트 (Page 17)