자료구조 - 배열, 연결리스트, 스택, 큐 관련 프로그램들

소개글

대학 학부과정 자료구조 - 배열, 연결리스트, 스택, 큐 관련 프로그램들 입니다.

컴파일 실행환경

모든 소스는 jdk 1.3을 이용하여 제작했으며
hello world를 컴파일하고 실행시키는 정도면
충분합니다

본문내용

1. n차원 배열을 열우선 순위로 기억장소에 저장할 때 각각의 주소를 구할 수 있는 식을 유도하라.

2. 다항식과 관련하여 주어진 두 개의 다항식들을 더한 결과와 곱한 결과를 보여주는 프로그램을 작성하시오.

3. 두 개의 스택을 운용하는 알고리즘을 작성하시오.

4. n개의 스택을 한 개의 배열에서 운용하는 알고리즘을 작성하시오.

5. 10X10 배열을 나선형으로 세팅하는 프로그램을 작성하시오.

6. 수식표기상 괄호가 올바로 중첩되었는지 확인하기 위해 스택을 사용할 수 있다. 이러한 기능을 하는 java프로그램을 작성하라.

7. 스택과 큐의 각 연산을 환형 연결 리스트를 사용하여 완성하라.

8. 단순 연결 리스트는 왼쪽에서 오른쪽으로 방문해 나가는 동안 링크를 반대 방향으로 연결시킴으로써 양방향으로 방문이 가능하다. 리스트의 구성은 아래 그림과 같다. 즉 p는 현재 참조되는 노드를 가리키고 l은 그 왼쪽 노드를 가리킨다.
(1) p를 현재 위치에서 오른쪽으로 하나 아동 시키는 알고리즘을 작성하라
(2) p를 주어진 임의의 위치에서 왼쪽으로 하나 이도시키는 알고리즘을 작성하라.
(3) 위의 (1), (2)를 아용하여 단순 연결리스트를 도치시키는 알고리즘을 완성하라.

9. 다항식을 위한 연결 할당 시스템을 구축하고자 할 때 head 노드를 가진 환형 연결 리스트를 이용할 수 있다. 각 노드는 아래와 같은 구조로 표현한다. 다항식을 효과적으로 다루기 위해, avail 리스트와 이에 관련된 다음과 같은 함수들을 사용할 수 있다.
(1) pread : 다항식의 표현으로 계수와 차수들의 열을 받아서 연결리스트로 표현하고 그 head노드의 포인터를 반환한다.
(2) pwrite : 일반적인 다항식의 형태를 반환한다.
(3) padd : 두 다항식의 덧셈을 계산한다.
(4) psub : 두 다항식의 뺄셈을 계산한다.
(5) pmul : 두 다항식의 곱셈을 계산한다.
(6) eval : 다항식에 실수형 변수 x에 주어진 값에 대하여 계산한다.
(7) perase : 환형 연결 리스트로 표현된 다항식을 avail에 반환한다.
위의 모든 함수들을 포함하는 프로그램을 작성하고 각 함수에 대한 시간 복잡도를 나타내라.

10. 10X10인 행렬 A, B가 있다. 이 행렬들의 곱을 C행렬이라고 할 때 행렬 A와 B를 초기화한 뒤, 행렬 C값을 구하는 프로그램을 작성하시오.

참고 자료

없음