자료구조 실습 (03분반) 09. 04. 07.

Presentation on theme: "자료구조 실습 (03분반) 09. 04. 07."— Presentation transcript:

1 자료구조 실습 (03분반)

2 Today… 행렬의 전치 Stack Queue

3 행렬의 전치 행에 의한 전치 행에 대해 원소<i, j, value> 가져와서 다른 행렬 원소<j, i, value>로 저장 C(n) = O(rows*cols) 새 원소 삽입 시 기존 원소는 이동하게 됨 열에 의한 전치 행에 의한 전치의 단점을 보완하고자 원소의 위치를 결정할 때 열 인덱스를 사용 열에 대해 원소<i, j, value> 가져와서 다른 행렬 원소<j, i, value>로 저장 C(n) = O(cols*elements) 최악의 경우 C(n) = O(clos2*rows)

4 스택 Top 이라고 하는 한 끝에서 모든 삽입과 삭제 가 일어나는 순서 리스트
LIFO(Last-in-First-out ; 후입선출 ) 제일 마지막에 삽입된 원소가 가장 먼저 삭제 10원 100원 500원 500원 100원 10원

5 스택(cont’) 데이터의 출력순서 E,D,C,B,A 데이터의 입력순서 A,B,C,D,E 초기상태 A입력 B입력 … E입력
삭제 top E top D D C C top B B B top A A A A top

6 스택(cont’) 스택의 삽입 연산 void add(int *top, element item) {
/* 전역 stack에 item을 삽입 */ if (*top >= MAX_STACK_SIZE-1) { stack_full(); return; } stack[++*top] = item; top A

7 스택(cont’) 스택의 삭제 연산 element delete(int *top) { /* stack의 최상위 원소를 반환 */
if (*top == -1) return stack_empty(); /* 오류 key를 반환 */ return stack[(*top)--]; } top E top D D C C B B A A

8 큐 한쪽 끝에서 데이터가 삽입되고 그 반대쪽 끝에서 삭제가 일어나는 순서리스트
한쪽 끝에서 데이터가 삽입되고 그 반대쪽 끝에서 삭제가 일어나는 순서리스트 FIFO(First-in-First-out) 선입선출리스트 제일 처음에 삽입된 원소가 가장 먼저 삭제 3 2 1 입구 1 2 3 출구

9 큐(cont’) 데이터의 입력순서 A,B,C,D,E 데이터의 출력순서 A,B,C,D,E 초기상태 A입력 B입력 … E입력 삭제
rear E rear D D C C B rear B B A rear A A A front rear front front front front

10 큐(cont’) 큐의 삽입연산 void addq(int *rear, element item) {
/* queue에 item을 삽입 */ if (*rear == MAX_QUEUE_SIZE-1) queue_full(); return; } queue[++*rear] = item; A rear front

11 큐 (cont’) 큐의 삭제연산 element deleteq(int *front, int rear) {
/* queue의 앞에서 원소를 삭제 */ if (*front == rear) return queue_empty(); /* 에러 key를 반환 */ return queue[++*front]; } E rear D C B A front

12 문제 교재에 있는 희소 행렬의 빠른 전치 함수 (fast_transper 함수)를 이용하여 프로그램을 완 성하시오.
희소행렬을 텍스트 파일에서 읽을 수 있도록 하세요. 희소행렬을 행렬값쌍(구조체 배열)으로 표현하세요. 행렬값쌍을 구현한 빠른 전치 함수로 전치합니다. 교재에 있는 스택 삽입/삭제 함수(add / delete 함 수)를 이용하여 프로그램을 완성하시오. 교재에 있는 큐 삽입/삭제 함수(addq / deleteq 함 수)를 이용하여 프로그램을 완성하시오.