단순 연결 리스트 순차(sequential) 표현 연결된(linked) 표현 연속된 원소들이 일정한 거리만큼 떨어져서 저장

Presentation on theme: "단순 연결 리스트 순차(sequential) 표현 연결된(linked) 표현 연속된 원소들이 일정한 거리만큼 떨어져서 저장"— Presentation transcript:

1 단순 연결 리스트 순차(sequential) 표현 연결된(linked) 표현 연속된 원소들이 일정한 거리만큼 떨어져서 저장
테이블에서 임의 원소 접근, 스택이나 큐의 원소 삽입/삭제에 적합 순서 리스트에서 임의 원소의 삽입/삭제 비용 큼 연결된(linked) 표현 순차 표현에서 제기된 데이터 이동 문제점을 해결 각 원소들이 메모리 내의 어떤 곳에나 위치 가능 노드 0개 이상의 데이터 필드 하나 이상의 링크(link) 또는 포인터(pointer) 다음 원소를 가리킴

2 비순차 리스트 표현 first = 8 data[8] = BAT : 데이터 link[8] = 3 : 주소
data[3] = CAT : 데이터 link[3] = 4 : 주소 data[link[3]] = EAT

3 연결 리스트를 그리는 일반적인 방법 first BAT CAT EAT WAT

4 노드 삽입 (1) 삽입 절차 (예: GAT 삽입) 삽입할 때 리스트에 있는 다른 원소들의 이동이 불필요
노드 a의 data 필드에 GAT 설정 a의 link 필드가 FAT 다음 노드, 즉 HAT를 가리키도록 FAT를 포함한 노드의 link 필드가 a를 가리키도록 삽입할 때 리스트에 있는 다른 원소들의 이동이 불필요 link 필드를 위한 저장 공간이 추가로 사용

5 노드 삽입 (2) HAT CAT EAT GAT WAT BAT FAT VAT 15 4 9 1 3 5 7 2 6 8 10 11
3 5 7 2 6 8 10 11 data link (a) Data[5]에 GAT 삽입 (b) 리스트에 노드 GAT 삽입 first BAT CAT EAT FAT HAT a GAT

6 노드 삭제 GAT 바로 앞에 있는 원소 FAT 찾기 FAT의 link를 HAT의 위치로 설정 리스트에서 GAT 삭제 first
BAT CAT EAT FAT GAT HAT WAT 리스트에서 GAT 삭제

7 C에서의 체인 표현 (1) C에서의 노드 정의 리스트를 위한 노드 구조 새로운 공백 리스트 생성
listPointer first = NULL; first는 리스트의 시작 주소를 포함 공백 리스트인지 검사하는 매크로 IS_EMPTY #define IS_EMPTY(first)(!(first)) 새로운 노드를 생성하기 위한 매크로 MALLOC MALLOC(first, sizeof(*first)); typedef struct listNode *listPointer typedef struct listNode { char data[4]; listPointer link; };

8 C에서의 체인 표현 (2) C에서의 노드 정의 (계속) 노드의 필드들에 값을 지정 : -> 연산자 사용
bat이란 단어를 리스트에 넣을 때 strcpy(first->data, “bat”); first->link = NULL; *first first→data B A T \ NULL first first→link first→data[0] first→data[1] first→data[2] first→data[3] 노드의 필드 참조

9 C에서의 체인 표현 (3) 2-노드 연결 리스트 정수들의 연결 리스트를 위한 노드 구조의 정의
두 개의 노드를 가진 연결 리스트를 생성 첫번째 노드와 두번째 노드의 data필드엔 각각 10, 20을 넣음 typedef struct listNode *listPointer typedef struct listNode { int data; listPointer link; }; listPointer create2() { /* 두 개의 노드를 가진 연결 리스트의 생성 */ listPointer first, second; MALLOC(first, sizeof(*first)); MALLOC(second, sizeof(*second)); second->link = NULL; second->data = 20; first->data = 10; first->link = second; return first; } 2-노드 리스트의 생성

10 C에서의 체인 표현 (4) 2-노드 연결 리스트 (계속) 2-노드 리스트 10 20 first

11 C에서의 체인 표현 (5) 리스트 삽입 임의의 노드 뒤에 데이터 필드 값이 50인 노드를 삽입
void insert(listPointer *frist, listPointer x) { /* data=50인 새로운 노드를 리스트 first의 node 뒤에 삽입 */ listPointer temp; MALLOC(temp, sizeof(*temp)); temp->data = 50; if(*first) { temp->link = x->link; x->link = temp; } else { temp->link = NULL; *first = temp; 리스트의 앞에 단순 삽입

12 C에서의 체인 표현 (6) 리스트 삽입 (계속) 공백 리스트와 공백이 아닌 리스트에서의 노드 삽입 first first x
50 50 (a) (b)

13 C에서의 체인 표현 (7) 리스트의 삭제 노드의 위치에 따라 삭제하는 방법이 다름
first : 리스트의 시작을 가리키는 포인터 x : 삭제하고자 하는 노드를 가리키는 포인터 trail : 삭제할 노드의 선행 노드를 가리키는 포인터 삭제하려는 노드가 리스트의 첫번째 노드일 경우 first, x trail = NULL first 10 50 20 50 20 (a) 삭제 전 (b) 삭제 후 함수 호출 delete(&first, NULL, first) ; 전과 후의 리스트

14 C에서의 체인 표현 (8) 리스트의 삭제 (계속) 삭제하려는 노드가 첫 번째 노드가 아닌 경우
trail의 링크 필드가 x의 링크 필드가 되도록 변경 first, trail y first 10 50 20 10 20 (a) 삭제 전 (b) 삭제 후 함수 호출 delete(&first, y, y->link) ; 뒤의 리스트

15 C에서의 체인 표현 (9) 리스트의 삭제 (계속) 리스트의 출력
void delete(listPointer *first, listPointer trail, listPointer x) { /* 리스트로부터 노드를 삭제, trail은 삭제될 x의 선행 노드이며 first는 리스트의 시작 */ if (trail) trail->link = x->link; else *first = (*first)->link; free(x); } 리스트에서의 삭제 리스트의 출력 void printList(listPointer first) { printf("The list contains: "); for (; first; first = first->link) printf("%4d",first->data); printf("\n"); }

16 연결 스택과 큐 (1) 여러 개의 스택이나 큐가 동시에 있을 때 순차적 표현 방법 대신 연결된 스택과 큐를 이용
여러 개의 스택이나 큐가 동시에 있을 때 순차적 표현 방법 대신 연결된 스택과 큐를 이용 링크의 화살표 방향 : 노드의 삽입과 삭제가 편리하게 만들어 줌 연결 스택 톱에서 노드 삽입/삭제 용이 연결 큐 뒤에선 노드를 쉽게 삽입 / 앞에선 노드를 쉽게 삭제 data link top data link front rear (a) 연결 스택 (b) 연결 큐

17 연결 스택과 큐 (2) 연결 스택 n ≤ MAX_STACKS 개의 스택을 동시에 나타내려면 스택의 초기 조건 경계조건
#define MAX_STACKS 10 /* 스택의 최대 수 */ typedef struct { int key; /* 기타 필드 */ } element; typedef struct stack *stackPointer; typedef struct stack { element data; stackPointer link; }; stackPointer top[MAX_STACKS]; 스택의 초기 조건 top[i] = NULL, 0≤i<MAX_STACKS 경계조건 top[i]=NULL, i번째 스택이 공백이면 (그 역도 성립)

18 연결 스택과 큐 (3) 연결 스택에 삽입 연결 스택에서의 삭제 void push(int i, element item)
stackPointer temp; MALLOC(temp, sizeof(*temp)); temp->data = item; temp->link = top[i]; top[i] = temp; } element pop(int i) { /* i번째 스택으로부터 톱 원소를 삭제 */ stackPointer temp = top[i]; element item; if(!temp) return stackEmpty(); item = temp->data; top[i] = temp->link; free(temp); return item; }

19 연결 스택과 큐 (4) 연결 큐 n ≤ MAX_QUEUE 개의 스택을 동시에 나타내려면 큐의 초기 조건 경계조건
#define MAX_QUEUE /* 큐의 최대 수 */ typedef struct queue *queuePointer; typedef struct queue { element data; queuePointer link; }; queuePointer front[MAX_QUEUES], rear[MAX_QUEUES]; 큐의 초기 조건 front[i] = NULL, 0≤i<MAX_QUEUES 경계조건 front[i]=NULL, i번째 큐가 공백이면 (그 역도 성립)

20 연결 스택과 큐 (5) 연결 큐의 뒤에 삽입 큐가 공백인지 조사해야 함
공백이면, front를 새로운 노드를 가리키도록 변경시킴 그렇지 않으면, rear의 링크 필드를 새로운 노드를 가리키도록 변경시킴 void addq(i, item) { /* 큐 i의 뒤에 원소를 삽입 */ queuePointer temp; MALLOC(temp, sizeof(*temp)); temp->data = item; temp->link = NULL; if(front[i]) rear[i]->link = temp; else front[i] = temp; rear[i] = temp; } 연결 큐의 뒤에 삽입

21 연결 스택과 큐 (6) 연결 큐의 앞으로부터 삭제 리스트의 현재 시작 노드를 삭제 element deleteq(int i)
queuePointer temp = front[i]; element item; if(!temp) return queneEmpty(); item = temp->link; free(temp); return item; } 연결 큐의 앞으로부터 삭제

22 다항식 (1) 다항식의 표현 리스트를 사용해서 다항식을 표현 ai : 0이 아닌 계수 ei : 음수가 아닌 정수 지수
em-1>em-2> ... >e1>e0≥ 0 리스트를 사용해서 다항식을 표현 계수, 지수, 다음 항을 가리키는 포인터 등 3개의 필드로 구성되는 노드로 표현 계수가 정수라고 가정 typedef struct polyNode *polyPointer; typedef struct polyNode { int coef; int expon; polyPointer link; }; polyPointer a,b; coef exp link polyNode

23 다항식 (2) 다항식의 표현 (계속) a = 3x14+2x8+1 b = 8x14-3x10+10x6 3x14+ 2x8 +1

24 다항식 (3) 다항식의 덧셈 포인터 a와 b가 가리키는 노드에서 시작되는 항들을 비교
b가 가리키는 항의 지수보다 a가 가리키는 항의 지수가 작으면, b의 항과 같은 항을 만들어 결과 다항식 d에 첨가시키고 포인터 b를 다음 노드로 이동 반대의 경우(a->expon > b->expon)는 a에 대해 수행

25 다항식 (4) 다항식의 덧셈 (계속) c=a+b의 처음 세 항을 생성 a->expon == b->expon

26 다항식 (5) polyPointer padd(polyPointer a, polyPointer b)
{ /* a와 b가 합산된 다항식을 반환 */ polyPointer c, rear, temp; int sum; MALLOC(rear, sizeof(*rear)); c= rear; while(a && b) switch(COMPARE(a->expon, b->expon)) { case -1: /* a->expon < b->expon */ attach(b->coef, b->expon, &rear); b = b->link; break; case 0 : /* a->expon = b->expon */ sum = a->coef + b->coef; if(sum) attach(sum, a->expon, &rear); a = a->link; b = b->link; break; case 1: /* a->expon > b->expon */ attach(a->coef, a->expon, &rear); a = a->link; } /* 리스트 a와 리스트 b의 나머지를 복사 */ for(; a; a=a->link) attach(a->coef, a->expon, &rear); for(; b; b=b->link) attach(b->coef, b->expon, &rear); rear->link = NULL; /* 필요 없는 초기 노드를 삭제 */ temp = c; c= c->link; free(temp); return c;

27 다항식 (6) 다항식의 덧셈 (계속) padd의 분석 고려 요소
void attach(float coefficient, int exponent, polyPointer *ptr) { /* coef=coefficient 이고 expon=exponent인 새로운 노드를 생성하고, 그것을 ptr에 의해 참조되는 노드에 첨가한다. ptr을 갱신하여 이 새로운 노드를 참조하도록 한다. */ polyPointer temp; MALLOC(temp, sizeof(*temp)); temp->coef = coefficient; temp->expon = exponent; (*ptr)->link = temp; *ptr = temp; } 리스트의 끝에 노드를 첨가 padd의 분석 고려 요소 (1) 계수 덧셈 (2) 지수 비교 (3) c를 위한 새로운 노드 생성 a와 b가 각각 m개와 n개의 항을 가지고 있을 때 연산시간 : O(m+n) 계수 덧셈 : 0≤계수 덧셈의 횟수 ≤ min{m,n} 지수 비교 : while 루프 한번 반복될 때 마다 한번씩 while루프 수행 횟수는 m+n을 넘을 수 없음 최대 m+n개의 새로운 노드가 만들어짐

28 다항식 (7) 다항식의 삭제 더 이상 사용하지 않는 노드는 반환 함수 erase : temp에 있는 노드들을 하나씩 반환
void erase(polyPointer *ptr) { /* ptr에 의해 참조되는 다항식을 제거 */ polyPointer temp; while(*ptr) { temp = *ptr; *ptr = (*ptr)->link; free(temp); } 다항식의 삭제

29 다항식 (8) 다항식의 원형 리스트(circular list) 표현 마지막 노드가 리스트의 첫 번째 노드를 가리키도록 함
(cf) 체인(chain) - 마지막 노드의 링크 필드 값이 NULL인 단순 연결 리스트 3x14+2x8+1의 원현 리스트 표현 제로 다항식(zero polynomial)을 특별한 경우로 처리해야 함 해방된 노드를 체인 형태의 리스트로 유지 가용 공간 리스트(available space list) 혹은 avail 리스트 avail : 해방된 노드들의 리스트에서 첫번째 노드를 가리키는 포인터 초기에 avail은 NULL 새로운 노드가 필요하면 이 리스트를 조사 malloc이나 free를 사용하는 대신 getNode, retNode를 사용 3 14 2 8 1 last

30 다항식 (9) 다항식의 원형 리스트 표현 (계속) polyPointer getNode(void)
{ /* 사용할 노드를 제공 */ polyPointer node; if (avail) { node = avail; avail = avail->link; } else MALLOC(node, sizeof(*node)); return node; 함수 getNode void retNode(polyPointer node) { /* 가용 리스트에 노드를 반환 */ node->link = avail; avail = node; } 함수 retNode

31 다항식 (10) 다항식의 원형 리스트 표현 (계속)
함수 cerase : 리스트의 노드 수에 관계 없이 일정 시간에 원형 리스트를 제거 void cerase(polyPointer *ptr) { /* ptr가 가리키는 원형 리스트를 제거 */ polyPointer temp; if (*ptr) { temp = (*ptr)->link; (*ptr)->link = avail; avail = temp; *ptr = NULL; } 원형 리스트의 제거

32 다항식 (11) 다항식의 원형 리스트 표현 (계속) 헤더 노드(header node) 사용 -
제로 다항식에 대한 특별한 경우를 만들지 않기 위해 각 다항식은 헤더 노드를 갖도록 함 header - - (a) 제로 다항식 header - - 3 14 2 8 1 (b) 3x + 2x + 1 14 8 헤더 노드를 가진 다항식 예

33 헤더 노드를 가진 원형 리스트로 표현된 두 다항식의 덧셈
polyPointer cpadd(polyPointer a, polyPointer b) { /* 다항식 a와 b는 헤더 노드를 가진 단순 연결 원형 리스트이고, a와 b가 합산된 다항식을 반환한다. */ polyPointer startA, c, lastC; int sum, done = FALSE; startA = a; a = a->link; b = b->link; c = getNode(); c->expon = -1; lastC = c; do { switch(COMPARE(a->expon, b->expon)) { case -1: /* a->expon < b->expon */ attach(b->coef, b->expon, &lastC); b = b->link; break; case 0: /* a->expon = b->expon */ if(startA == a) done = TRUE; else { sum = a->coef + b->coef; if(sum) attach(sum, a->expon, &lastC); a = a->link; b = b->link; } break; case 1: /* a->expon > b->expon */ attach(a->ceof, a->expon, &lastC); a = a->link; }while(!done); lastC->link = c; return c;

34 추가 리스트 연산 (1) 체인 연산 체인을 역순으로 만드는(inverting) 연산
3개의 포인터를 적절히 이용하여 제자리(in place)에서 문제를 해결 연산 시간 – O(length) typedef struct listNode *listPointer; typedef struct listNode { char data; listPointer link; }; listPointer invert(listPointer lead) { /* lead가 가리키고 있는 리스트를 역순으로 만든다. */ listPointer middle, trail; middle = NULL; while (lead) { trail = middle; middle = lead; lead = lead->link; middle->link = trail; } return middle; 단순 연결 리스트를 역순으로 만드는 함수

35 추가 리스트 연산 (2) 체인 연산 (계속) 두 개의 체인 ptr1과 ptr2를 연결(concatenation)하는 연산
listPointer concatenate(listPointer ptr1, listPointer ptr2) { /* 리스트 ptr1 뒤에 리스트 ptr2가 연결된 새로운 리스트를 생성한다. ptr1이 가리키는 리스트는 영구히 바뀐다. */ listPointer temp; /* check for empty lists */ if(!ptr1) return ptr2; if(!ptr2) return ptr1; /* neither list is empty, find end of first list */ for(temp = ptr1; temp->link; temp = temp->link) ; /* link end of first to start of second */ temp->link = ptr2; } 단순 연결 리스트의 연결

36 추가 리스트 연산 (3) 원형 연결 리스트 연산 리스트의 마지막 노드에 대한 포인터 last를 유지함으로써 앞이나 뒤 양쪽에 쉽게 원소를 삽입 가능 리스트의 앞에 삽입 void insertFront(listPointer *last, listPointer node) { /* 리스트의 마지막 노드가 last인 원형 리스트의 앞에 노드를 삽입한다. */ if (IS_EMPTY(*first)) { /* 리스트가 공백일 경우, last이 새로운 항목을 가리키도록 변경시킨다. */ *last = node; node->link = node; } else { /* 리스트가 공백이 아닌 경우, 리스트의 앞에 새로운 항목을 삽입시킨다. */ node->link = (*last)->link; (*last)->link = node;

37 추가 리스트 연산 (4) 원형 연결 리스트 연산 (계속) 원형 리스트의 길이 계산
int length(listPointer last) {/* 원형 리스트 last의 길이를 계산한다. */ listPointer temp; int count = 0; if (last) { temp = last; do { count++; temp = temp->link; } while (temp != last); } return count;

38 동치 부류 (1) 동치 관계(equivalence relation),  의 특성
(1) 반사적(reflexive) : 어떤 다각형 x에 대해서, x≡x가 성립 (2) 대칭적(symmetric) : 어떤 두 다각형 x,y에 대해서, x≡y이면 y≡x (3) 이행적(transitive): 어떤 세 다각형 x, y, z에 대해서, x≡y이고 y≡z이면 x≡z 동치 관계(equivalence relation)의 정의 집합 S에 대하여 관계 ≡ 가 대칭적, 반사적, 이행적이면 관계 ≡를 집합 S에 대해 동치 관계라 함. 그 역도 성립. 동치부류(equivalence class) S의 두 원소 x,y에 대하여 x≡y이면 x, y는 같은 동치부류 (역도 성립) ex) 0≡4, 3≡1, 6≡10, 8≡9, 7≡4, 6≡8, 3≡5, 5≡11, 11≡0 { 0, 2, 4, 7, 11}; {1, 3, 5}; {6, 8, 9, 10}

39 동치 부류 (2) 동치 결정 알고리즘 동치 쌍(equivalence pair) <i,j>를 읽어 기억
0에서부터 시작해서 <0,j> 형태의 모든 쌍을 찾는다. <j,k>가 있으면 k도 0과 같은 동치부류에 포함시킨다. 0이 포함된 동치 부류의 모든 객체를 찾아 표시하고 출력 남은 동치 부류에 대해서도 같은 방법으로 계속한다.

40 동치 부류 (3) 배열을 사용 한 동치 알고리즘 m : 동치 쌍의 수, n : 객체 수
쌍 <i, j> 를 나타내기 위해 배열 pairs[i][j] 사용 배열의 극히 일부 원소만 사용 : 기억 장소 낭비 새로운 쌍 <i,k>를 i행에 넣기 위해 i행 내의 빈 공간을 찾거나 추가 공간을 사용해야 하므로 많은 시간 소모 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); 1차 버전의 동치 알고리즘

41 동치 부류 (4) 연결 리스트를 사용한 동치 알고리즘 seq[n] : n개의 리스트 헤더 노드 저장
i번째 행에 대한 임의 접근을 위해 필요 out[n] , 상수 TRUE, FALSE : 이미 출력된 객체 표시 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; 보다 정제된 동치 알고리즘

42 동치 부류 (5) 쌍들이 입력된 뒤의 리스트 0≡4, 3≡1, 6≡10, 8≡9, 7≡4, 6≡8, 3≡5, 5≡11, 11≡0 while 루프가 끝난 뒤의 리스트 관계 i≡j에 대해 두 개의 노드를 사용 11 3 5 7 8 4 6 1 10 9 2 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] first data link

43 동치 부류 (6) O(n) 동치 부류를 찾는 프로그램 #include <stdio.h>
#inlcude <alloc.h> #define MAX_SIZE 24 #define IS_FULL(first) (!(first)) #define FALSE 0 #define TRUE 1 typedef struct node *nodePointer; typedef struct node { int data; nodePointer link; }; void main(void) { short int out[MAX_SIZE]; nodePointer seq[MAX_SIZE]; nodePointer x,y,top; int i,j,n; printf("Enter the size (<= %d) ", MAX_SIZE); scanf("%d", &n); for (i = 0; i < n; i++) { /* seq와 out을 초기화 */ out[i] = TRUE; seq[i] = NULL; } 동치 부류를 찾는 프로그램 O(n)

44 O(n+m) O(m+n) 시간 복잡도 : O(m+n) 공간 복잡도 : O(m+n) /* 1 단계: 동치 쌍들을 입력 */
printf("Enter a pair of numbers (-1 -1 to quit): "); scanf("%d%d", &i, &j); while (i >= 0) { MALLOC(x, sizeof(*x)); x->data = j; x->link = seq[i]; seq[i] = x; x->data = i; x->link = seq[j]; seq[j] = x; printf(“Enter a pair of numbers (-1 -1 to quit) : “); scanf(“&d&d”, &i, &j); } /* 2 단계: 동치 부류들을 출력 */ for (i = 0; i < n; i++) if (out[i]) { printf("\nNew class: %5d", i); out[i] = FALSE; /* 부류들을 FALSE로 함 */ x = seq[i]; top = NULL; /* 스택을 초기화 */ for (;;) { while (x) { /* 리스트 처리 */ j = x->data; if (out[j]) { printf(%5d", j); out[j] = FALSE; y = x->link; x->link = top; top = x; x = y; else x = x->link; if (!top) break; x = seq[top->data]; top = top->link; /* 스택에서 제거 */ O(n+m) O(m+n) 시간 복잡도 : O(m+n) 공간 복잡도 : O(m+n)

45 희소 행렬 (1) 희소 행렬의 연결 리스트 표현 희소 행렬의 각 열과 행을 헤더 노드가 있는 원형 연결 리스트로 표현
각 노드에는 헤더노드와 엔트리 노드를 나타내기 위한 tag 필드가 있음 헤더 노드 down : 열 리스트로 연결하는데 사용 right : 행 리스트로 연결하는데 사용 next : 헤드 노드들을 서로 연결하는데 사용 헤더 노드의 총 수 : max{행의 수, 열의 수} 엔트리 노드 Tag필드 외에 5개의 필드(row, col, down, right, value)가 있음 down: 같은 열에 있는 0이 아닌 다음 항 연결 right : 같은 행에 있는 0이 아닌 다음 항 연결

46 희소 행렬 (2) 5*4 희소 행렬 a 필요한 노드 수 numTerms개의 0이 아닌 항을 가진 numRows * numCols 희소 행렬이라면 max{numRows, numCols}+numTerms+1개

47 희소 행렬 a의 연결 표현 (노드의 tag필드는 생략되어 있음)

48 희소 행렬 (4) 희소 행렬의 표현을 위한 자료 구조 정의 #define MAX_SIZE 50 /* 최대 행렬 크기 */
typedef enum {head,entry} tagfield; typedef struct matrixNode *matrixPointer; typedef struct entryNode { int row; int col; int value; }; typedef struct matrixNode { matrixPointer down; matrixPointer right; tagfield tag; union { matrixPointer next; entryNode entry; } u; matrixPointer hdnode[MAX_SIZE];

49 희소 행렬 (5) 희소 행렬 입력 (1) 첫번째 입력 라인 다음 numTerms개의 입력 라인
행의 수(numRows), 열의 수(numCols), 0이 아닌 항의 수(numTerms) 다음 numTerms개의 입력 라인 row, col, value의 형태로 구성되었다고 가정 행 우선으로, 행 내에서는 열 우선으로 정렬되어 있다고 가정 [0] [1] [2] [0] [1] [2] [3] [4] 희소 행렬의 입력 예

50 희소 행렬 (6) 희소 행렬 입력 (2) 입력을 위해 보조 배열 hdnode를 사용
적어도 입력될 행렬의 가장 큰 차원의 크기라고 가정 변수 hdnode[i]는 열 i와 행 i에 대한 헤더 노드를 가리키는 포인터 입력 행렬을 구성하는 동안 임의의 열을 효과적으로 접근할 수 있게 함 matrixPointer mread(void) { /* 행렬을 읽어 연결 표현으로 구성한다. 전역 보조 배열 hdnode가 사용된다. */ int numRows, numCols, numTerms, numHeads, i; int row, col, value, currentRow; matrixPointer temp,last,node; printf("Enter the number of rows, columns, and number of nonzero terms: " scanf("%d%d%d", &numRows, &numCols, &numTerms); numHeads = (numCols > numRows) ? numCols : numRows; /* 헤더 노드 리스트에 대한 헤더 노드를 생성한다. */ node = newNode(); node->tag = entry; node->u.entry.row = numRows; node->u.entry.col = numCols; if (!numHeads) node->right = node; else { /* 헤더 노드들을 초기화한다. */ for (i = 0; i < numHeads; i++) { temp = newNode; hdnode[i] = temp; hdnode[i]->tag = head; hdnode[i]->right = temp; hdnode[i]->u.next = temp; }

51 - mread의 분석 총 연산 시간 O(max{numRows, numCols} + numTerms)
currentRow = 0; last = hdnode[0]; /* 현재 행의 마지막 노드 */ for (i = 0; i < numTerms; i++) { printf("Enter row, column and value: "); scanf("%d%d%d", &row,&col,&value); if (row > currentRow) { /* 현재 행을 종료함 */ last->right = hdnode[currentRow]; currentRow = row; last = hdnode[row]; } temp = newNode(); temp->tag = entry; temp->u.entry.row = row; temp->u.entry.col = col; temp->u.entry.value = value; last->right = temp; /* 행 리스트에 연결 */ last = temp; /* 열 리스트에 연결 */ hdnode[col]->u.next->down = temp; hdnode[col]->u.next = temp; /* 마지막 행을 종료함 */ /* 모든 열 리스트를 종료함 */ for (i = 0; i < numCols; i++) hdnode[i]->u.next->down = hdnode[i]; /* 모든 헤더 노드들을 연결함 */ for (i = 0; i < numHeads-1; i++) hdnode[i]->u.next = hdnode[i+1]; hdnode[numHeads-1]->u.next = node; node->right = hdnode[0]; return node; - mread의 분석 총 연산 시간 O(max{numRows, numCols} + numTerms) = O(numRows + numCols + numTerms) - 2차원 배열을 사용한 numRows * numCols 행렬의 입력 시간인 O(numRows x numCols)보다는 좋음 - 순차적 방법보다는 나쁨

52 희소 행렬 (8) 희소 행렬의 출력 mwirte의 분석: 연산 시간은 O(numRows + numTerms)
void mwrite(matrixPointer *node) { /* 행렬을 행 우선으로 출력한다. */ int i; matrixPointer temp, head = node->right; /* 행렬의 차원 */ printf("\n numRows = %d, numCols = %d \n", node->u.entry.row, node->u.entry.col); printf(" The matrix by row, column, and value: \n\n"); for (i = 0; i < node->u.entry.row; i++) { /* 각 행에 있는 엔트리들을 출력 */ for (temp = head->right; temp != head; temp = temp->right) printf("%5d%5d%5d \n", temp->u.entry.row, temp->u.entry.col, temp->u.entry.value); head - head->u.next; /* 다음 행 */ } mwirte의 분석: 연산 시간은 O(numRows + numTerms)

53 희소 행렬 (9) 희소 행렬 삭제 함수 free를 사용하여 한번에 한 노드씩 반환
void merase(matrixPointer *node) {/* 행렬을 삭제하고, 노드들을 히프로 반환한다. */ matrixPointer x,y, head = (*node)->right; int i, numHeads; /* 엔트리 노드와 헤더 노드들을 행 우선으로 반환한다. */ for (i = 0; i < (*node)->u.entry.row; i++) { y = head->right; while (y != head) { x = y; y = y->right; free(x); } x = head; head = head->u.next; free(x); /* 나머지 헤더 노드들을 반환한다. */ y = head; while (y != *node) { x = y; y = y->u.next; free(x); free(*node); *node = NULL; merase의 분석 : 연산 시간은 O(numRows + numCols + numTerms)

54 이중 연결 리스트 (1) 이중 연결 리스트(doubly linked list) 포인터를 양방향으로 이동해야 할 필요가 있거나
임의의 노드를 삭제해야 되는 문제에 적합 각 노드는 전방과 후방을 가리키는 두개의 링크를 가짐 typedef struct node *nodePointer; typedef struct node { nodePointer llink; element data; nodePointer rlink; } - Left data Right 헤더노드 헤더 노드가 있는 이중 연결 원형 리스트

55 이중 연결 리스트 (2) 이중 연결 리스트에서 ptr이 임의의 노드를 가리키고 있다면 이중 연결 원형 리스트에 삽입 -
ptr = ptr->llink->rlink = ptr->rlink->llink 성립 전위 노드나 후위 노드로 쉽게 이동할 수 있음 이중 연결 원형 리스트에 삽입 - first 헤더 노드를 가진 공백 이중 연결 원형 리스트 void dinsert(nodePointer node, nodePointer newnode) { /* newnode를 node의 오른쪽에 삽입 */ newnode->llink = node; newnode->rlink = node->rlink; node->rlink->llink = newnode; node->rlink = newnode; }

56 이중 연결 리스트 (3) 이중 연결 원형 리스트로부터 삭제
void ddelete(nodePointer node, nodePointer deleted) { /* 이중 연결 리스트에서 삭제 */ if (node == deleted) printf("Deletion of head node not permitted.\n"); else { deleted->llink->rlink = deleted->rlink; deleted->rlink->llink = deleted->link; free(deleted); } - first x Before After