자 료 구 조

목차

데이터 구조의 정의
포인터가 데이터를 참조하는 방식
좋은 알고리즘
스트링을 정의
배열을 정의
정보구성 단위의 계층
연결 리스트를 사용한 스택과 큐의 구성
스택에서 수식 표기법
후위 표기식의 장점
선형리스트
기억 장소 관리 시 연결된 기억장소를 할당할 때 두 가지 문제점
원형 연결 리스트의 정의
이중 연결 리스트의 정의

본문내용

ORD
4 Byte(32Bit) = FULL WORD
8 Byte(64Bit) = DOUBLE WORD
FIELD(=ITEM)
어떤 의미를 갖는 자료 값으로 정보를 전달할 수 있는 논리적인 개념을 위한 단위로 프로그램의 처리 단위
ex) 'KOREA'는 5Byte로 이루어진 1FIELD이다
RECORD
연관성 있는 FIELD들의 모임으로 프로그램에서 취급되는 자료처리 단위
논리적 레코드(LOGICAL RECORD)
- 프로그램에서 처리되는 사용자가 정의하는 단위 레코드
물리적 레코드(PHYSICAL RECORD)
- 보조기억 장치와 중앙처리 장치간의 자료 입출력 기본 단위로서 1개 이상의 논리레코드로 구성되며 블록(BLOCK)이라고도 한다.
FILE
프로그램에서 취급되는 하나의 작업처리 단위인 연관성 있는 레코드들의 집합
매체에 의한 분류 FILE
편성방식
DATABASE
여러 개의 FILE의 중복성을 최소화 하기위해서 DATABASE에서 제어로 관리되는 단위
7. 연결 리스트를 사용한 스택과 큐의 구성을 보이시오.
8 . 스택에서 수식 표기법을 말하시오.
중위(infix) 표기 방법
일반적인 표기 방식
<피연산자-연산자-피연산자> 예) A + B
전위(prefix) 표기 방법
<연산자-피연산자-피연산자> 예) + A B
중위 표기 -> 전위 표기 방법으로의 전환
예) (((((-A) / B) * C) + (D * E)) - (A * C))
⇒ - + * / - A B C * D E * A C
후위(postfix or reverse polish) 표기 방법
<피연산자-피연산자-연산자> 예) A B +
컴퓨터가 수식을 계산하기에 가장 적합한 방법
컴파일러
- 중위표기 수식을 후기 표기 방법으로 변환한 후 스택을 이용 수식 계산
9. 후위 표기식의 장점은?
후위 표기식의 장점
괄호를 필요로 하지 않는다.
연산자들의 우선순위가 필요 없게 된다.
스택을 사용하면 식을 왼쪽에서 오른쪽으로 읽어 가면서 쉽게 계산할 수 있다.
10. 선형리스트란?
정의
가장 단순한 데이터 구조중의 하나.
각 데이터가 배열과 같이 연속되는 기억장소에 저장되는 리스트를 선형 리스트(linear list), 또는 순서 리스트 (ordered list) 라고 한다.
A = (a1, a2, . . . ai, ai+1, . . ., an) 로 표시.
특성
가장 보편적인 표현 방법(배열)을 가짐
임의적인 원소를 삽입 할 때 연속적인 사용 구역이 있어야함
메모리의 사용 효율성이 높고, 일괄처리 작업이나 순서적으로 생성할 때 효과적으로 사용되는 구조
자주 변하지 않는 데이터 저장에 유리
삽입과 삭제 연산시 데이터 이동이 많고 연속적인 메모리의 여유분이 필요
순차적 사상 (sequential mapping)
- 선형 리스트의 i 번째 항목은 i 번째에 저장
인덱스를 사용하여 각각의 항목에 접근한다.
- 포인터가 필요 없다.
기억장소를 최대한 이용할 수 있다.
항목에 대한 삽입, 삭제, 교환 등의 연산이 복잡하다.
장점
가장 간단한 데이터 구조이다.
메모리 밀도(memory density)가 1이므로 다른 데이터구조보다 뛰어나다.
단점
항목 삽입 시 연속적인 기억장소를 요구한다.
삽입, 삭제 시 선형구조를 유지해야 하므로 많은 데이터의 이동으로 인한 속도의 저하가 발생한다.
11. 기억 장소 관리 시 연결된 기억장소를 할당할 때 두 가지 문제점은?
어떻게 노드를 구성해야 하는가?
처리해야 할 작업에 따라 데이터 크기와 개수가 다르다
링크 필드의 수도 데이터나 처리할 특성에 따라 한 개 이상일 수 있다
어떤 노드가 가용 기억 공간으로 반납되어야 하는가?
더 이상 필요 없는 자료는 가용 기억 공간으로 반납한다.
12. 원형 연결 리스트의 정의하시오.
원형 연결 리스트의 정의
마지막 노드의 포인터를 null이 아닌 첫 번째 노드의 주소를 가리키도록 구성하는 연결 리스트
원형 연결 리스트의 구조
13. 이중 연결 리스트의 정의하시오.
이중 연결 리스트의 정의
오른쪽과 왼쪽 링크를 두고 양방향으로 탐색이 가능하도록 만든 연결 리스트
새로운 로드를 어떤 로드의 앞에 삽입을 하거나 삭제가 불가능한 단점을 보완하기 위해 제안된 리스트
임의의 로드를 중심으로 해서 앞쪽로드와 뒤쪽로드의 위치를 가리키기 위해서 두개의 링크필드를 사용하는 리스트
이중 연결 리스트의 구조
이중 원형 연결 리스트의 정의
오른쪽과 왼쪽 링크를 두고 양방향으로 탐색이 가능하도록 만든 원형 연결 리스트
이중 원형 연결 리스트의 구조

키워드

데이터 구조의 정의,   포인터가 데이터를 참조하는 방식,   좋은 알고리즘,   스트링을 정의,   배열을 정의,   정보구성 단위의 계층,   연결 리스트를 사용한 스택과 큐의 구성,   스택에서 수식 표기법