자료구조

○ 자료구조란?
자료를 효율적으로 표현, 저장, 처리하여 사용할 수 있도록 하는 것


○ 형태에 따른 자료구조의 분류
1. 단순구조
: 정수, 실수, 문자, 문자열 등의 데이터 타입에 해당
2. 선형구조
: 자료들간의 앞뒤 관계가 일대일로 고정되어 있는 구조
- 리스트(list) : 자료의 논리적 순서와 기억장소에 저장되는 물리적 순서가 일치하는 구조
- 연결 리스트(linked list) : 물리적 순서에 상관없이 포인터를 사용하여 순서를 갖는 구조
- 스택(stack), 큐(queue), 덱(deque) : 자료의 삽입, 삭제 위치에 대해 조건이 있는 구조
3. 비선형구조
: 자료들간에 계층 구조나 망 구조를 갖는 자료구조
- 트리, 그래프
4. 파일구조
: 보조기억장치에 데이터가 실제로 기록되는 구조
- 순차 파일, 색인 파일, 직접 파일 등


○ 자료의 표현
컴퓨터는 이진수 코드를 사용하여 자료를 표현함
비트(bit) : 한자리의 1, 0 을 표현하는 단위
              : 디지털 시스템에서 자료를 표현하는 최소 단위
              : 니블(nibble) - 4개의 비트 그룹
                바이트(Byte) - 8개의 비트 그룹

1. 수치 자료의 표현
ⓐ 10진수의 표현
    i. 존(Zone) 형식
      - 10진수 한자리를 표현하기 위해 1바이트를 사용
      - 상위 4비트의 존 영역과 하위 4비트의 수치 영역으로 이루어짐
      - 존 영역은 항상 1111로 표시
      - 수치 영역은 표현하고자 하는 10진수 한자리의 값에 대한 2진수 값
      - 부호는 최하위 바이트의 존 영역에 나타냄(양수:1100, 음수:1101)
       ex) +213, -213을 존 형식으로 나타내보면?
            1111 0010 | 1111 0001 | 1100 0011
              F      2        F     1      C(+)   3
            1111 0010 | 1111 0001 | 1101 0011
              F      2        F     1      D(-)   3
    ii. 팩(Pack) 형식
       - 10진수 두자리를 표현하기 위해 1바이트를 사용
       - 부호는 최하위 바이트의 하위 4비트에 표시함
        ex) +213, -213을 팩 형식으로 나타내보면?
             0010 0001 | 0011 1100
               2      1        3   C(+) 
             0010 0001 | 0011 1101
               2      1        3   C(-)
 
ⓑ 2진수의 표현
   i. 정수 표현
    - 음수 표현 방법 : 2진수를 2의 보수로 변환함(1의 보수로 변환 후 1을 더함)
    ex) 00010101   : +21 (MSB는 부호를 나타냄 - 0은 양수)
         11101010   : 1의 보수로 변환
         11101011   : -21 (MSB는 부호를 나타냄 - 1은 음수)
   ii. 실수 표현
     * 고정 소수점 형식
        - 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어 있는 것으로 취급함
     * 부동 소수점 형식
        - 표현 가능한 값의 범위가 큼(아주 작거나 아주 큰 값)
        - 실수 자료형은 4바이트나 8바이트로 표현됨

2. 문자 자료의 표현
ⓐ BCD 코드
- 6비트를 사용하며 상위 2비트의 존 비트와 하위 4비트의 숫자 비트로 구성
| 존 비트 | 숫자 비트 | 
    A  B       8  4  2  1
    x  x        x  x  x  x
- 존 비트 AB의 값
00 : 0, 1~9(1010, 0001~1001)
01 : 문자 A~I(0001~1001)
10 : 문자 J~R(0001~1001)
11 : 문자 S~Z(0001~1001)

ⓑ EBCDIC 코드
- 8비트를 사용하며 상위 4비트의 존 비트와 하위 4비트의 숫자 비트로 구성
- 0~9, 영어 대문자와 소문자, 특수문자까지 나타냄
|   존 비트  |  숫자 비트  |  
   A  B  C D    8  4  2  1
   x   x  x  x    x  x  x  x
- 존 비트 AB의 값                                  - 존 비트 CD의 값
00 : 여분                                               00 : 문자 A~I(0001~1001)
01 : 특수 문자                                        01 : 문자 J~R(0001~1001)
10 : 영어 소문자                                     10 : 문자 S~Z(0001~1001)
11 : 영어 대문자                                     11 : 0~9(0000~1001)

ⓒ ASCII 코드
- 7비트를 사용하며 상위 3비트의 존 비트와 하위 4비트의 숫자 비트로 구성
| 존 비트  |  숫자 비트 |  
                   8  4  2  1
   x  x  x       x  x  x  x

3. 논리 자료의 표현
- 논리값을 표현하기 위한 자료 형식
- 참과 거짓의 두 가지 상태 중에서 하나를 표시하기 때문에 1비트로 표현이 가능

4. 포인터 자료의 표현
- 메모리의 주소를 표현하기 위한 자료 형식

5. 문자열 자료의 표현
- 여러 문자로 이루어진 문자 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장



*출처 - C로 배우는 쉬운 자료구조(이지영 저, 한빛미디어)