[자료구조론]Queue를 이용한 미로찾기 과제

소개

"[자료구조론]Queue를 이용한 미로찾기 과제"에 대한 내용입니다.

목차

1. 문제정의
2. 문제해결
3. 결과창
4. 소스
5. 결론 및 느낀 점

본문내용

1. 문제정의
※ 미로에서 시작점에서 목적지로 가는 최단 경로의 길이와 최단 경로를 구하는 프로그램을 작성하시오. 미로에서 어떤 점에서 위/아래/오른쪽/왼쪽의 막혀있지 않은 점으로 갈 수 있다.
(1) QueType을 정의하고, 이를 배열로 구현
(2) 클래스 Maze를 정의하고 구현, 클래스 Maze의 member 함수들 구현
. 만약 클래스 Maze를 정의하지 않을 경우에는 (예를 들어, 견본 프로그램) 감점 있음
. 만약 최단경로의 길이만 출력할 경우 감점 있음

2. 문제해결
※ Queue를 사용한 프로그램이므로 Class로 QueType을 생성한다. QueType.h에는 나중에 Enqueue와 Dequeue를 struct형으로 받아올것이기 때문에 template를 해준다. 클래스의 이름위와 각각의 메소드 위에는 template<class ItemType> 문장을 써주고 Generic Date Type를 각각의 메소드에 써준다. QueType에는 생성자와 소멸자, MakeEmpty() 함수와 IsEmpty()함수, IsFull()함수와 Enqueue(), Dequeue()함수가 있다.
- QueType생성자 에서는 변수 maxQue에 max+1 을 대입한다. front와 rear는 0으로 초기화 하고 items에는 ItemType[maxQue]를 할당해 준다.
- IsEmpty()함수는 Q가 비었나 확인하는 함수로써 front와 rear가 동일하면 참을 반환하고 아닐경우 거짓을 반환한다.
- Enqueue()함수는 items[rear] 즉, 배열 items의 뒤에서부터 넣겠다는 개념으로 먼저 큐가 가득찼는지를 IsFull()함수로 검사한다. 가득 찼으면 예외 처리로 “Queue is full” 을 출력하고 아닐경우에는 items배열의 뒤에서부터 newitem을 넣는다. 그후 rear의 값은 (rear+1)% maxQue 해준다. 환형큐를 만들기 위함이다.
- ~QueType()소멸자에서는 delete[]items로 items에 들어간 값들을 반환해줌으로써 메모리 leak가 생기지 않도록 한다.
- IsFull()함수는 큐가 가득찼는지를 확인하는 함수로써 front 값과 (rear+1)%maxQue가 같다면 참을 반환하고 아니면 거짓을 반환한다.

참고자료

· 없음