보고서 #5 (기한: 5/17)

보고서 #5 (기한: 5/17)



제출 방법:

 대학 학습플랫폼(Lms)에 명시된 기간내 제출해야 한다.

 설정된 제출 기간 5/17이며, 기한이 지나면 제출할 수 없음에 유의하 기 바랍니다.

1

문제 #1



2개의 큐, q1, q2를 이용하여 스택을 구현하고자 한다. 방법은 다 음과 같다: q1에 삽입된 항목들이 역순으로 저장되게 한다. 즉, 1, 2, 3, 4의 4개 항목이 순차적으로 삽입되었을 때 다음은 q1의 상 태이다. 이를 위해서 q2를 이용하라.



다음 순서대로 문제를 해결하라.

 q1, q2를 전역적으로 생성하고, 초기화하라.

 push(item) 연산을 작성하라. item은 정수이다.

 pop() 연산을 작성하라.

 다음 main() 함수를 작성하여 테스트하라.

4 2 3

1

rear front

q1

main() {

int a[] = {1,2,3,4,5};

// 배열 a에 포함된 모든 수를 순서대로 스택에 저장하라.

// 스택에 포함된 모든 수를 꺼내어 출력하라.

}

Solution: 문제 1

push(item) {

// 모든 항목을 q1으로부터 q2로 이동 while !is_empty(q1) do

enqueue(q2, dequeue(q1));

repeat

// item을 q1에 삽입 enqueue(q1, item);

// q2에 포함된 모든 항목을 q1으로 다시 이동 while !is_empty(q2) do

enqueuer(q1, dequeue(q2));

repeat }

pop() {

// q1에서 한 개의 항목을 삭제하여 반환 if !is_empty(q1) then

return dequeue(q1) else

error();

}

Solution: 문제 1



큐에 다음 순서로 삽입하였을 경우에: 1, 2, 3, 4 q1, q2의 상태는 다음과 같다.

1 2 3 4

q1

q2

문제 #2

 한 개의 문자열을 매개변수로 전달받고, 이 문자열이 앞 에서부터 읽으나 뒤에서부터 읽으나 같은지를 판단하여 true 또는 false를 반환하는 is_palin() 알고리즘을 작성 하라. 가령, is_palin()은 문자열이 “madam”이면 true를 반환하고, “data”이면 false를 반환하다. 단, 덱을 이용 하라.

 위에서 작성한 알고리즘을 C 함수로 작성하고, 또한 main() 함수를 작성하여 테스트하라.



main()에서는 사용자로부터 문자열 s를 입력받아서,

is_palin()에 전달하고, 그 결과에 따라서 다음과 같이 출력 한다: “s is Palindrome” 또는 “s is NOT palindrome”



위 과정을 사용자가 원할 때까지 반복하라.

5

Sol: 문제#2

init_deque(&dq); // 덱 초기화 // s에 포함된 문자들을 dq에 저장 for i<- 0 to strlen(s)-1 do

add_rear(&dq, s[i]) repeat

while !is_empty(dq) do

first = delete_front(&dq); //앞에서 문자를 가져오고

if is_empty(dq) then // dq에 한 개의 문자만 남아 있으면 return true;

else

last = delete_rear(&dq); // 뒤에서 문자를 가져오고

if first != last then // 앞, 뒤 문자가 일치하지 않으면 return false

end if end if repeat

return true }