대학교 과제/자료구조 [ 2 - 1 ] (4) 썸네일형 리스트형 [자료구조 과제] - 12주차 수식트리 (후위표기식) 1. 과제안내문 이번 과제는 후위 표기식 형식으로 수식을 입력하여 수식트리를 만들고, 이 트리를 중위로 순회하면서 중위 표기식을 출력하고, 수식을 계산한 결과를 출력한다. 수식트리에서 노드는 연산자 또는 피연산자 노드로 구성되는데, 내부 노드는 연산자 노드이고, 외부 노드는 피연산자 노드가 된다. 피연산자 노드는 노드의 데이터는 피연산자가 되고 자식 노드는 없다. 연산자 노드는 노드의 데이터는 연산자가 되고, 피연산자들은 연산자 노드의 자식 노드로 연결된다. 이진연산자는 두 자식을 가지지만, 단일연산자는 왼쪽 자식은 없고 오른쪽 자식만 가진다. 수식트리를 만드는 방식은 후위 표기식을 계산하는 방식과 비슷하다. 피연산자는 피연산자 노드를 만들어 그 노드를 스택에 Push 한다. 연산자는 연산자 노드를 만들.. [자료구조 과제] - 11주차 완전 이진 트리 1. 과제 안내문 이번 과제는 노드 번호가 nMaxNo까지 노드를 가지는 완전 이진트리를 생성하고, 노드 번호를 부여하는 규칙에 의하여 노드 번호가 nNo인 노드를 찾는 과제이다. 이진트리를 레벨 순회로 노드의 번호를 출력하면 트리의 모습을 쉽게 알 수 있다. 왜냐 하면 1 레벨은 노드가 1, 2 레벨은 노드가 2개, 일반적으로 n 레벨은 노드가 2n-1개이기 때문에 앞에서 레벨에 따라 개수를 분리하여 생각하면 그 구조를 쉽게 알 수 있다. 이 과제는 번호가 nMaxNo까지 가지는 완전 이진트리를 생성하고, 이 트리를 레벨 순회에 따라 노드 번호를 출력한다. 그리고 노드 번호 nNo를 가지는 노드를 찾아 올바르게 찾았는지를 확인한다. 수업시간에 실습을 통하여 마지막 노드를 가리키는 원형 리스트를 사용하여.. 자료구조 10주차 과제 - 이중 원형 연결리스트 1. 과제 안내문 이번 과제는 이중 연결 리스트에 대한 과제입니다. 이중 연결 리스트에서 앞/뒤로 이동하는 것과 삽입/삭제에 대한 연산입니다. 이중 연결 리스트는 원하는 대로 앞/뒤로 이동이 가능하기 때문에 꼭 첫 노드만 가리킬 필요가 없습니다. 어느 한 노드만 알고 있으면 원하는 대로 이동 가능하기 때문입니다. 이번 과제에는 이중 연결 리스트에 새로운 노드를 삽입하고, 기존의 노드를 삭제하고, 앞뒤로 이동하면서 data를 출력하는 내용입니다. 이번 과제에는 앞/뒤로 이동이 가능한 이중 연결 리스트이고, 또한 마지막 노드가 첫 노드를 가르키는 원형 연결 리스트이고, 헤드 노드는 없는 연결 리스트입니다. 아래의 연산자들을 완성하기 바랍니다. 다음은 명령에 대한 설명이다. L ;; pList를 왼쪽으로 움직.. 자료구조 9주차 과제 - 원형 리스트 1. 과제 안내문 이번 과제는 목걸이 문제를 프로그래밍 한다. 목걸이 문제는 목걸이에서 스킵/삭제를 반복하여 최종적으로 남는 구슬을 찾는 문제이다. 목걸이는 1부터 n까지 번호가 부여된 구슬들로 구성되고, 1번부터 스킵과 삭제를 반복하여 마지막까지 남은 구슬의 번호를 찾는다. 다시 말해 1번 구슬은 건너뛰고, 2번 구슬은 삭제되고, 3번 구슬은 건너뛰고, 4번 구슬은 삭제되는 방식으로 구슬이 하나만 남을 때까지 반복된다. 이렇게 반복하여 마지막까지 남은 구슬의 번호를 찾는다. 목걸이 문제를 해결하는 방식은 2 가지 해결책이 있다. 첫째로 1부터 n까지 데이터를 가지는 노드들을 원형 연결 리스트로 만든 목걸이에서 1부터 시작하여 스킵과 삭제를 반복하는 방식으로 시물레이션에 의하여 답을 찾는다. 둘째로 일반.. 이전 1 다음
