제2장 배열과구조.

Slides:



Advertisements
Similar presentations
1 08 배열. 한국대학교 객체지향연구소 2 C 로 배우는 프로그래밍 기초 2 nd Edition 배열  동일한 자료유형의 여러 변수를 일괄 선언  연속적인 항목들이 동일한 크기로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는.
Advertisements

1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
스택 스택 추상자료형 스택 스택의 구현 스택의 응용 한빛미디어(주).
제 2 장 : 배열과 구조 이 형 원 강릉대학교 컴퓨터공학과
배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합
Chapter 2 배열과 구조 (Arrays and Structures)
제 5 장 stack and queue.
쉽게 풀어쓴 C언어 Express 제11장 포인터 C Express Slide 1 (of 27)
3 장 stack and queue.
희소 행렬(sparse matrix) mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
제2장 배열과구조.
5 순차 자료구조 방식.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
자료구조 실습 (03분반)
자료구조 김현성.
Internet Computing KUT Youn-Hee Han
Internet Computing KUT Youn-Hee Han
자료 구조: Chapter 3 배열(1) 순천향대학교 컴퓨터공학과 하 상 호.
제3장 스택과 큐.
4장 스택.
자료 구조: Chapter 3 (2)구조체, 포인터
7장 배열 ②.
스택(stack) SANGJI University Kwangman Ko
Chapter 4 스택, 큐, 데크.
강의 #6 큐(Queue).
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 27).
다음 주 과제 7장 읽어오기 숙제 해서 다음 주(11월 12일) 제출하기. 큐(Queue) E304호,
자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호.
제 5 장. 스택(Stack).
Chapter 06. 스택.
제3장 스택과 큐.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
스택 (1) 스택(stack)과 큐(queue) 스택(stack) 순서 리스트(ordered list)의 특별한 경우
SqlParameter 클래스 선문 비트 18기 발표자 : 박성한.
Javascript Basic Sample Programs
자료구조: CHAP 5 스택 순천향대학교 컴퓨터공학과 하 상 호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
CHAP 6:큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
2.3 제한 조건을 가진 자료구조 1. 스택(STACK) 1) 스택의 개념 - 삽입과 제거 작업이 리스트의 한쪽 끝에서만 수행
제 4 장 스택과 큐 4.1 스택(stack) 4.2 스택의 활용 4.3 큐 4.4 데큐.
11장. 1차원 배열.
Introduction To Data Structures Using C
CHAP 10:그래프 (2) 순천향대학교 하상호.
자바 5.0 프로그래밍.
프로그래밍 개요
자기참조 구조체(1) 먼저 자신과 같은 형의 구조체를 포인트하는 포인터 멤버 필드를 갖는 구조체를 정의한다.
배열과 연결리스트 연결리스트 배열 메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
4th HomeWork Guide (ver2.0)
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
쉽게 풀어쓴 C언어 Express 제14장 포인터 활용 C Express Slide 1 (of 22)
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
제 3 강.
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
데이터 동적 할당 Collection class.
자료구조론 8장 큐(queue).
Chapter 10 데이터 검색1.
Summary of Pointers and Arrays
컴퓨터 개론 √ 원리를 알면 IT가 맛있다 쉽게 배우는 컴퓨터 기본 원리 한빛미디어 교재출판부.
제 4 장 Record.
C++ Espresso 제15장 STL 알고리즘.
Presentation transcript:

제2장 배열과구조

2.4 희소행렬 추상데이터타입 희소 행렬(Sparse matrix) 0 1 0 0 0 0 0 1 2 3 4 5 0  1    0  0   0   0          0 11  3  0  0   0 0  0  0 -6  0   0 0  0  0  0  0   0 91  0  0  0  0   0 0  0 28  0  0    0 0 1 2 3 4 5 1 2 3 4 5

2.4 희소행렬 추상데이터타입 • m × n matrix A ≡ A[MAX_ROWS][MAX_COLS] # of non-zero elements            --------------------- <<  small # of total elements        

2.4 희소행렬 추상데이터타입 Structure Sparse_Matrix Objects : 3원소쌍 <행,열,값>의 집합이다. 여기서, 행과 열은 정수이고 이 조합은 유일하며, 값은 item 집합의 한 원소이다. Functions : 모든 a,b∈Sparse_Matrix, x∈item, i , j, max_col, max_row ∈index에 대해 Sparse_Matrix Create(max_row, max_col)  ::= return max_items 까지 저장할 수 있는 Sparse_matrix, 여기서 최대 행의 수는 max_row이고 최대 열의 수는 max_col이라 할 때 max_items=max_row*max_col이다. Sparse_Matrix Transpose(a)   ::= return 모든 3원소쌍의 행과 열의 값을 교환하여 얻은 행렬

2.4 희소행렬 추상데이터타입 Sparse_Matrix Add(a,b) ::= if a와 b의 차원이 같으면 return 대응항들, 즉 똑같은 행과 열의 값을 가진 항 들을 더해서 만들어진 행렬 else return 오류 Sparse_Matrix Multiply(a,b)   ::= if a의 열의 수와 b의 행의 수가 같으면 return 다음 공식에 따라 a와 b를 곱해서 생성 된 행렬 d:d[i][j]=(a[i][j] *b[i][j]), 여기서 d[i][j]는 (i,j)번째 요소이다      else return 오류 end Sparse_Matrix

2.4 희소행렬 추상데이터타입 효율적 기억장소 사상 <i, j, value> : 3-tuples (triples)  효율적 기억장소 사상 <i, j, value> : 3-tuples (triples) no. of rows no. of columns no. of non-zero elements ordering(column major or row major)

2.4 희소행렬 추상데이터타입 희소 행렬 0  1 0 0 0 0       0 11  0  0  0   0 0  0  0 -6  0   0 0  0  0  0  0   0 91  0  0  0  0   0 0  0 28  0  0    0 row col value   6 6 5 0 1 1 1 1 11 2 3 -6 4 0 91 5 2 28 0 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2.4 희소행렬 추상데이터타입 행렬을 위한 연산 행렬의 생성 덧셈 곱셈 전치

2.4 희소행렬 추상데이터타입 행렬의 전치(Matrix Transpose) for j← 1 to n do for i←1 to m do           B(j, i) ← A(i, j)            end                        end

2.4 희소행렬 추상데이터타입           1    2      3               1    2      3  A(0,    6,   6,     8         B(0,   6,   6,     8      (1,    0,   0,     15          (1,   0,   0,     15 (2,    0,   3,     22          (2,   0,    4,     91 (3,    0,   5,     -15        (3,   1,   1,     11 (4,    1,   1,     11         (4.   2,   1,     3 (5,    1,   2,     3          (5,   2,   5,     28 (6,    2,   3,     -6          (6,   3,   0,     22 (7,    4,   0,     91         (7,   3,   2,     -6 (8,    5,   2,     28         (8,   5,   0,     -15 행내에서 => 행우선, 열내에서 => 열우선

2.4 희소행렬 추상데이터타입 희소 행렬의 전치 각 행 i에 대해서 원소 <i, j, 값>을 가져와서 전치행렬의 원소 <j, i, 값>으로 저장

procedure TRANSPOSE(A,B) //A is a matrix represented in sparse form// //B is set to be its transpose// 1   (m,n,t)←(A(0,1),A(0,2),A(0,3)) 2   (B(0,1),B(0,2),B(0,3))←(n,m,t) 3   if t<0 then return //check for zero matrix// 4   q←1      //q is position if next term in B// 5   for col←1 to n do  //transpose by columns// 6     for p←1 to t do //for all nonzero terms do// 7       if A(p,2)=col       //correct column// 8         then[(B(q,1),B(q,2),B(q,3)) ← //insert// 9              (A(p,2),A(p,1),A(p,3)) //next term//   10                 q←q+1  ]                  11   end 12  end 13 end TRANSPOSE

void transpose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int n, i, j, currentb; n = a[0].value;     /* 총 원소 수 */ b[0].row = a[0].col; /* b의 행 수 = a의 열 수 */  b[0].col = a[0].row; /* b의 열 수 = a의 행 수 */  b[0].value = n;    if (n > 0) { /* 0이 아닌 행렬 */    currentb = 1; for (i =0; i = a[0].col; i++) /* a에서 열별로 전치*/ for (j = 1; j <= n; j++) /* 현재의 열로부터 원소를 찾는다. */ if (a[j].col ==i { /* 현재 열에 있는 원소를 b에 첨가 */ b[currentb].row = a[j].col; b[currentb].col = a[j].row; b[currentb].value = a[j].value; currentb++; } O(columns * elements)

void fast_transpose(term a[], term b[]) { /* a를 전치시켜 b에 저장 */ int row_terms[MAX_COL], starting_pos[MAX_COL]; int i,j, num_col = a[0].col, num_terms = a[0].value; b[0].row = num_cols; b[0].col = a[0].row; b[0].value = num_terms; if (num_terms > 0) { /* 0이 아닌 행렬 */ for(i = 0; i < num_cols; i++) row_terms[i] = 0; for(i = 1; i <= num_terms; i++) row_terms[a[i].col]++; starting_pos[0] = 1; for(i = 1; i < num_cols; i++) starting_pos[i] = starting_pos[i-1] + row_terms[i-1]; for(i = 1; i <= num_terms; i++) { j = starting_pos[a[i].col]++; b[j].row = a[i].col;  b[j].col = a[i].row; b[j].value = a[i].value; }                 } O(columns + elements)

2.5 다차원 배열의 표현 배열의 원소 수 : a[upper0][upper1]....[uppern-1] =  ∏i=0,n-1 upperi  -  a[10][10][10] ⇨ 10・10・10 = 1000

2.5 다차원 배열의 표현 다차원 배열 표현 방법 - 행 우선 순서(row major order) 3,2 3,2 2.5 다차원 배열의 표현 다차원 배열 표현 방법 - 행 우선 순서(row major order)   row0            row1       rowupper0-1 - 열 우선 순서(column major order) col0                col1    colupper1-1 A[0][0] A[0][1] … A[0][upper1-1] A[1][0] … A[0][0] A[1][0] … A[upper1-1][0] A[1][1] …

2.5 다차원 배열의 표현 주소 계산 (2차원 배열 - 행우선 표현) α = A[0][0]의 주소 3,2 2.5 다차원 배열의 표현 주소 계산 (2차원 배열 - 행우선 표현) α = A[0][0]의 주소 A[i][0]의 주소 = α + i・upper1 A[i][j]의 주소 = α + i・upper1 + j

2.5 다차원 배열의 표현 주소 계산 (3차원 배열) : A[upper0][upper1][upper2] 3,2 주소 계산 (3차원 배열) : A[upper0][upper1][upper2] - 2차원 배열 upper1×upper2 ⇨ upper0 개 a[i][0][0] 주소 = α+i・upper1・upper2 a[i][j][k] 주소 = α+i・upper1・upper2+j・ upper2 + k

2.5 다차원 배열의 표현 A[upper0][upper1]...[uppern-1] α = A[0][0]...[0]의 주소 a[i0][0]...[0] 주소 = α + i0upper1upper2...uppern-1 a[i0][i1][0]...[0] 주소  = α+ i0upper1upper2...uppern-1 + i1upper2upper3...uppern-1 a[i0][i1]...[in-1] 주소 = α + i0upper1upper2...uppern-1 + i1upper2upper3...uppern-1 + i2upper3upper4...uppern-1 ⋮ + in-2uppern-1 + in-1

제3장 스택과 큐

3.1 스택 추상 데이터 타입 스택(Stack) : 가장 마지막에 입력된 데이터가 가장 먼저 출력되는 후입선출 자료구조 LIFO(Last-in-First-out) 후입선출 : 한 끝에서 모든 삽입과 삭제가 일어나는 구현원리 응용) Subroutine or recursive call

3.1 스택 추상 데이터 타입 데이터의 입력순서 A,B,C,D,E 데이터의 출력순서 E,D,C,B,A 초기상태 A입력 삭제 top E top D D C C top B B B top A A A A top

structure Stack objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 stack∈ Stack, item∈ element, max_stack_size∈ positive integer Stack CreateS(max_stack_size) ::= 최대 크기가 max_stack_size인 공백 스택을 생성 Boolean IsFull(stack, max_stack_size) ::= if (stack의 원소수 == max_stack_size) return TRUE else return FALSE Stack Add(stack, item) ::= if (IsFull(stack)) stack_full else stack의 톱에 item을 삽입하고 return Boolean IsEmpty(stack) ::= if (stack == CreateS(max_stack_size)) return TRUE Element Delete(stack) ::= if (IsEmpty(stack)) return else 스택 톱의 item을 제거해서 반환

3.1 스택 추상 데이터 타입 top Stack CreateS(max_stack_size) ::= #define MAX_STACK_SIZE 100 /*최대스택크기*/ typedef struct { int key; /* 다른 필드 */ } element; element stack[MAX_STACK_SIZE]; int top = -1; Boolean IsEmpty(top) ::= top < 0; Boolean IsFull(top) ::= top >= MAX_STACK_SIZE-1; MAX_STACK_SIZE top

3.1 스택 추상 데이터 타입 스택의 삽입 연산 void add(int *top, element item) { /* 전역 stack에 item을 삽입 */ if (IsFull(*top)) { stack_full(); return; } stack[++*top] = item; top A

3.1 스택 추상 데이터 타입 스택의 삭제 연산 element delete(int *top) { /* stack의 최상위 원소를 반환 */ if (IsEmpty(*top)) return stack_empty(); /* 오류 key를 반환 */ return stack[(*top)--]; } top D C B A

3.1 스택 추상 데이터 타입 스택의 예 택시의 동전통 10원 500원 100원 100원 500원 10원

3.2 큐 추상 데이터 타입 Queue : 가장 먼저 입력된 데이터가 가장 먼저 출력되는 선입선출 자료구조 FIFO(First-in-First-out) 선입선출리스트 : 한쪽 끝에서 데이터가 입력되고 그 반대쪽 끝에서 출력이 일어나는 구현원리 응용) Job scheduling

3.2 큐 추상 데이터 타입 데이터의 입력순서 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

structure Queue objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 queue∈Queue, item∈element, max_queue_size∈positive integer Queue CreateQ(max_queue_size) ::= 최대 크기가 max_queue_size인 공백 큐를 생성 Boolean IsFullQ(queue, max_queue_size ) ::= if (queue의 원소수 == max_queue_size) return TRUE else return FALSE Queue AddQ(queue, item) ::= if (IsFull(queue)) queue_full else queue의 뒤에 item을 삽입하고 이 queue를 반환 Boolean IsEmptyQ(queue) ::= if (queue == CreateQ(max_queue_size)) return TRUE Element DeleteQ(queue) ::= if (IsEmpty(queue)) return else queue의 앞에 있는 item을 제거해서 반환

3.2 큐 추상 데이터 타입 Queue CreateQ(max_queue_size) ::= #define MAX_QUEUE_SIZE 100 /* 큐의 최대크기 */ typedef struct { int key; /* 다른 필드 */ } element; element queue[MAX_QUEUE_SIZE]; int rear = -1; int front = -1; Boolean IsEmptyQ(front, rear) ::= front == rear Boolean IsFullQ(front, rear) ::= rear == MAX_QUEUE_SIZE-1 rear front

3.2 큐 추상 데이터 타입 큐의 삽입연산 void addq(int front, int *rear, element item) { /* queue에 item을 삽입 */ if (IsFullQ(front, *rear)) queue_full(); return; } queue[++*rear] = item; A rear front

3.2 큐 추상 데이터 타입 큐의 삭제연산 element deleteq(int *front, int rear) { /* queue의 앞에서 원소를 삭제 */ if (IsEmptyQ(*front, rear)) return queue_empty(); /* 에러 key를 반환 */ return queue[++*front]; } E rear D C B A front

3.2 큐 추상 데이터 타입 터널 터널, 줄서기 3 2 1 1 2 3

3.2 큐 추상 데이터 타입 큐의 예 작업 스케쥴링 운영체제에 의한 작업 큐의 생성 시스템에 진입한 순서대로 처리 front rear Q[0] Q[1] Q[2] Q[3] 설명 -1 -1 공백큐 -1 0 J1 Job1의 진입 -1 1 J1 J2 Job2의 진입 -1 2 J1 J2 J3 Job3의 진입 0 2 J2 J3 Job1의 진출 1 2 J3 Job2의 진출

3.2 큐 추상 데이터 타입 문제점 입력시 rear 값의 증가, 출력시 front 값의 증가 => Queue가 full될 경우 전체를 왼쪽으로 이동하여 front 값을 조정해야 함 E rear D front C B A

3.2 큐 추상 데이터 타입 해결책 : Circular queue를 사용 [7] [0] [6] [1] [5] [2] [4] [3] rear=0 front=0 rear front

3.2 큐 추상 데이터 타입 해결책 : Circular queue를 사용 front : 첫 번째 원소의 하나 앞을 가리킴 rear : 입력된 원소의 마지막 위치 Modular 연산자를 이용 *rear = (*rear+1) % Max_Queue_Size *front = (*front+1) % Max_Queue_Size rear front

3.2 큐 추상 데이터 타입 [0] [7] [6] [1] [2] [5] [3] [4] 환형큐의 추가연산 void addq(int front, int *rear, element item) { /* queue에 item을 입력 */ *rear = (*rear+1) % MAX_QUEUE_SIZE; if (front == *rear) { queue_full(rear); /* rear를 리세트시키고 에러를 프린트 */ return; } queue[*rear] = item; rear=0 front=0

3.2 큐 추상 데이터 타입 환형큐의 삭제연산 element deleteq(int *front, int rear) { [0] [7] [6] [1] [2] [5] [3] [4] 환형큐의 삭제연산 element deleteq(int *front, int rear) { element item; /* queue의 front 원소를 삭제하여 그것을 item에 놓음 */ if (*front == rear) return queue_empty(); /* queue_empty는 에러 키를 반환 */ *front = (*front+1) % MAX_QUEUE_SIZE; return queue[*front]; } rear=0 front=0

공백큐 [0] [7] [6] [1] [2] [5] [3] [4] rear=0 front=0 [0] [7] [6] [1] [2] [5] [3] [4] rear=3 front=0 J1 J2 J3 포화큐 포화큐 [0] [7] [6] [1] [2] [5] [3] [4] rear=7 front=0 [0] [7] [6] [1] [2] [5] [3] [4] rear=2 front=3 J7 J7 J8 J6 J6 J9 J1 J5 J2 J5 J10 J4 J3 J4

Stack Ordered list in which all insertions and deletions are made at one end (top pointer) LIFO(Last-In-First-Out) 제일 마지막에 입력된 데이터가 가장 먼저 출력 (응용) Subroutine or recursive call Queue Ordered list in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front. FIFO(First-In-First-Out) 제일 처음에 입력된 데이터가 가장 먼저 출력 (응용) Job scheduling

3.3 미로문제 입구 막힌경로 통행경로 출구

3.3 미로문제 경로표현 ? 경계표현 ? 입구 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 막힌경로 1 1 1 1 1 1 통행경로 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 출구

3.3 미로문제 입구 1 1 1 1 1 1 1

3.3 미로문제 여덟방향이동을 위한구조 typedef struct { short int vert; [row-1] [col-1] [row-1] [col] [row-1] [col+1] 3.3 미로문제 1 [row] [col-1] [row] [col+1] 여덟방향이동을 위한구조      typedef struct  { short int vert; short int horiz; } offsets; offsets move[8]; [row+1] [col-1] [row+1] [col] [row+1] [col+1]

3.3 미로문제 현재의 위치 다음 이동할 위치? maze[row][col] NW=7 N=0 NE=1 3.3 미로문제 [row-1] [col-1] [row-1] [col] [row-1] [col+1] 1 [row] [col-1] [row] [col+1] W=5 E=2 현재의 위치 maze[row][col] 다음 이동할 위치? next_row = row + move[dir].vert; next_col  = col + move[dir].horiz; [row+1] [col-1] [row+1] [col] [row+1] [col+1] SW=4 SE=3

3.3 미로문제 경로의 탐색 현위치 저장후 방향 선택 : N에서 시계방향 잘못된 경로의 선택시는 backtracking후 다른 방향 시도 시도한 경로의 재시도 방지 mark[m+2][n+2] : 초기치 0 mark[row][col] = 1 /* 한번 방문한 경우 */ 경로 유지를 위해서 스택 사용

3.3 미로문제 경로 유지위한 스택 #define MAX-STACK-SIZE 100 /*스택의 최대크기*/ [row-1] [col-1] [col] [col+1] [row] [row+1] N=0 NE=1 E=2 NW=7 SE=3 SW=4 W=5 3.3 미로문제 경로 유지위한 스택 #define MAX-STACK-SIZE 100 /*스택의 최대크기*/ typedef struct { short int row; short int col; short int dir; } element; element stack[MAX_STACK_SIZE];

initiallize a stack to the maze's entrance coordinates and direction to north; while (stack is not empty) { /* 스택의 톱에 있는 위치로 이동*/ <row, col, dir> = delete from top of stack; while (there are more moves from current position) { <next_row, next_col> = coordinate of next move; dir = direction of move; if ((next_row == EXIT_ROW) && (next_col == EXIT_COL)) success; if (maze[next_row][next_col] == 1) && mark[next_row][next_col] == 0) { /* 가능하지만 아직 이동해보지 않은 이동 방향 */ mark[next_row][next_col] = 1; /* 현재의 위치와 방향을 저장 */ add <row, col, dir> to the top of the stack; row = next_row; col = next_col; dir = north; } printf("No path found\n");

3.3 미로문제 이동테이블 Name dir move[dir].vert move[dir].horiz N 0 -1 0 [row-1] [col-1] [col] [col+1] [row] [row+1] N=0 NE=1 E=2 NW=7 SE=3 SW=4 W=5 3.3 미로문제 이동테이블 Name dir move[dir].vert move[dir].horiz N 0 -1 0 NE 1 -1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1 -1 W 6 0 -1 NW 7 -1 -1

void path(void) { /* 미로를 통과하는 경로가 있으면 그 경로를 출력한다. */ int i, row, col, next_row, next_col, dir, found=FALSE; element position; mark[1][1]=1; top=0; stack[0].row=1; stack[0].col=1; stack[0].dir=1; while (top>-1 && !found) { position = delete(&top); row = position.row;      col = position.col; dir = position.dir; while (dir<8 && !found) { next_row = row + move[dir].vert;  /* dir 방향으로 이동 */ next_col = col + move[dir].horiz; if (next_row==EXIT_ROW && next_col==EXIT_COL) found = TRUE; else if (maze[next_row][next_col] && !mark[next_row][next_col]) { mark[next_row][next_col]) = 1; position.row = row; position.col = col; position.dir = ++dir;  add(&top, position); row = next.row; col = next.col; dir = 0; } else ++dir;

최악의 경우 연산시간 = O(mp) m : 행의 수 p : 열의 수 if (found) { printf("The path is:\n"); printf("row  col\n"); for (i=0; i<=top; i++) printf("%2d%5d", stack[i].row, stack[i].col"); printf("%2d%5d\n", row, col); printf("%2d%5d\n", EXIT_ROW, EXIT_COL); } else printf("The maze does not have a path\n"); 최악의 경우 연산시간 = O(mp) m : 행의 수 p : 열의 수

과제물 배열의 전치를 위한 두가지 알고리즘 P/G 다섯개의 입력 : A,B,C,D,E 에 해당하는 입력과 출력의 과정을 각각 Stack과 Queue, 그리고 환형 Queue를 이용하여 프로그래밍 미로찾기 프로그램 프로그래밍