릴렉스

한쪽끝에서 항목이 삭제되고 반대편 끝에서는 항목이 삽입되는 선형리스트이다.
선입선출(FIFO : first-in first-out)리스트라고 부른다.

- 원형 큐
큐의 배열을 선형으로 표현하지 않고 원형으로 표현하는 방법이다.

데크는 삽입과 삭제가 양쪽 끝에서 모두 허용될 수 있는 선형 리스트이다.

- 데크의 종류
입력제한 데크 : 입력이 한쪽 끝으로만 제한되는 경우이다.
출력제한 데크 : 출력이 한쪽 끝으로만 일어날 수 있도록 제한하는 경우이다.

선형 리스트 구조의 특별한 형태로 리스트내의 데이타의 삽입과 삭제가 '탑(TOP)'이라
불리는 한쪽 끝에서만 일어난다.
푸시다운 리스트 (pushdown list) 또는 후입 선출 (LIFO : last-in first-out)리스트라고 부른다.

스택의 중요한 연산으로는 스택에 데이타를 삽입하고 삭제하는 연산이 있다.
삽입연산은 푸시(push), 삭제연산은 팝(pop)이라고 부른다.

- 다중스택
하나의 기억장소블록에 2개의 스택을 보관하는것과 하나의기억장소 블록에 n개의 스택을
보관하는 방법이 있다. 가용공간의 이동으로 처리한다.

스택의 응용분야로는 수식의 계산, 서브루틴 호출과 수놘, 미로실험, 푸시다운 오토마타,
퀵 정렬등이 있다.

레코드를 이질적 데이터 구조라고 부르듯이 레코드의 원소는 배열로 저장되지 않는다.

1. 고정 길이 레코드
일정한 길이를 가지고 있는 레코드이다.
삽입과 삭제가 간단하다.

2. 가변길이 레코드
- 한 파일내에 여러 유형의 레코드 저장
- 한 파일내에 가변 필드를 허용하는 레코드 저장
- 반복적 필드를 허용하는 레코드 저장
2-1. 바이트 스트링 표현
각 레코드 끝에 레코드 끝 기호를 첨가하는 가변 길이 레코드를 사용한다.
단점 : 삭제된 레코드의 기억 장소의 재사용이 쉽지 않다.
         크기가 증가하는 레코드는 기억 장소를 할당하기 어렵다.

2-2. 고정 길이 레코드
- 예약장소 기법 : 가장 큰 기억 장소를 차지하는 최대 레코드 길이가
존재하면 그 길이만큼의 고정 길이 레코드를 사용한다. 사용하지 않는
기억 장소는 의미없는 값이나 레코드 끝 기호를 채운다.
- 포인터 기법 : 포인터를 통하여 연결되는 고정길이 레코드의 리스트로
가변 길이 레코드를 표현한다.

스트링

1. 스트링의 표현 방법

1-1. 비압축 스트링

문자 코드들을 연속적인 워드에 나타내며, 한 워드에 한 개의 문자 코드를
나타낸다. 처리 속도는 빠르지만 기억장소 활용도가 낮으므로 좋지 않다.

1-2. 압축 스트링

워드단위로 사용하는 기계에서 문자 코드를 이용하여 한 위드에 많은 문자를
나타내어 기억 장소의 효율적 사용을 가능하게 한다.

1-3. 연결 리스트

기억장소를 고정 길이로 분할하고, 데이타 저장부와 연결 저장부의 두 부분으로
나눈다. 연결 저장 부는 다음 문자를 포함하는 블록의 위치를 가리키고 있다.
삽입, 삭제 서브스트링 연산등에서 이점이 있다.

1-4. 가변길이 스트링

크기를 예측할 수 없을때 가변길이 스트링을 사용하여 변화에 대처한다.

2. 스트링의 연산

2-1. 결합 연산 : 새로운 스트링을 생성하기 위하여 두 개 이상의 스트링을 연결하는것이다.

2-2. 서브스트링 연산 : 스트링에서 일부를 추출한다.

2-3. 삽입 연산 : 스트링 구성문자사이에 새로운 스트링을 삽입한다.

2-4. 삭제 연산 : 스트링 구성문자중 하나 이상의 문자를 삭제한다.

2-5. 패턴 매칭 연산 : 스트링중 지정된 서브스트링을 찾아서 불린값을 리턴한다.

2-6. 인덱싱 연산 : 스트링 내에서 어떤 문자 또는 서브스트링의 위치를 정수로 나타낸다.

배열

- 배열은 동일한 형의 데이타형을 갖는 원소들이 장방형 구조에 놓여 있는 집합체이다.
  배열은 1차월 배열과 다차원 배열 (2차원 이상)으로 나눌 수 있다.

정의
데이타 : 컴퓨터 시스템에 의해 처리하려는 대상
정보 : 문제를 해결하기 위해 컴퓨터 시스템에 의해 처리된 데이타 또는 의미가 있는 데이타

데이타는 프로그램과 협의의 데이타(수치 데이타, 문자 데이타, 논리 데이타)로 나뉜다.

1. 수치 데이터

종류 : 정수, 실수, 배정도(double precision) 실수, 복소수

1-1. 정수

정수중 최상위 비트는 부호비트
정수표현법은 부호있는 절대치 표현, 부호있는 1의보수, 부호있는 2의 보수가 있다.
각각의 표현법은 양수는 모두 동일하게 표현되지만, 0과 음수는 다르다.
10 ( 00001010 ) 을 예로 들면
부호있는 절대치 : 10001010  => 부호비트만 양수와 보수관계
1의 보수        : 11110101  => 양수에서 1을 0으로 0을 1로 변환
2의 보수        : 11110110  => 1의 보수 + 1

1-2. 실수

표현법은 고정소수점 방식과 부동소수점 방식

고정소수점 방식은 비트중에서 소수점위와 아래의 갯수가 정해진것
부동소수점 방식은 지수를 사용함으로써 소수점을 옮겨서 저장하는 방식

부동소수점은 0.10 * 10^-5 는 지수 -5와 가수 0.10으로 이루어진다.
가수 m은 언제나 0<= m < 1 을 만족하므로 소수점밑 첫째자리가 0이 아닌
수가 나오도록 정렬시키는것이 효과적이다.
지수부를 표현할때는 편중값(biased value)를 이용하여 표현한다.
1000000 을 0으로 간주하면 이 값이 편중값이 된다.
따라서 실제 지수=지수부분의 값 - 편중값이다.

1-3. 기타 수치데이타

배정도 실수 : 기억공간을 2개를 묶어서 하나의 실수로 표현한다.
복소수      : z = x+yi 이므로 하나의 복소수를 나타내기 위해 2개의 실수룰 사용한다.
BCD (Binary coded decimal) : 10진 숫자 10개를 코드로 규정하여 저장하여 진법변환없이
처리한다.
BCD의 종류 : BCD8421, BCD2421, Excess-3, Gray, Excess-3 Gray, Hamming

2. 비수치 데이타

2-1. 문자 데이타

7비트 ASCII와 8비트 EBCDIC

2-2. 논리 데이타

참 거짓을 표현

3. 데이타 구조의 종류

3-1. 광의의 데이타 구조 : 기초 데이타 형태, 협의의 데이타 구조, 화일 구조
3-1-1. 기초 데이타 형태 : 정수형, 실수형, 문자형, 논리형, 포이터형
3-1-2. 협의의 데이타 구조 : 단순 형태, 복합 형태(선형), 복합 형태(비선형)
3-1-2-1. 단순형태 : 스트링, 배열, 레코드
3-1-2-2. 복합형태(선형) : 스택, 큐, 리스트
3-1-2-3. 복합형태(비선형) : 그래프, 일반 트리, 이진 트리, 특수 트리