자료구조의 정의와 컴퓨터에서의 자료표현

 

▶ 자료구조

 

자료를 효율적으로 표현, 저장, 처리할 수 있도록 정리하는 것을 의미합니다.

예) 도서관에서의 도서 분류에 따른 자료구조, 편의점에서의 음료 및 과자 등의 품목 별 자료구조

 

 

▶ 왜 자료구조를 알아야 할까?

 

컴퓨터의 자료를 효과적으로 관리하기 위해 효율적으로 저장하고 처리할 수 있도록 논리적인 구조를 만들어 프로그램적으로 처리합니다.
예) 편의점에 갔는데 음료의 종류별로 한 곳에 있으면 구매자는 음료 선택하는 시간과 노력을 비교적 단축시킬 수 있습니다.

 

 

▶ 자료의 형태에 따른 분류

1. 단순 구조

 

  1) 자료 값을 사용하기 위한 기본형태
  2) 프로그래밍 언어에서 제공하는 정수, 실수, 문자, 문자열 등의 데이터 타입에 해당

 

2. 선형 구조

  1) 자료들간의 관계가 1:1일 경우
  2) 순차 리스트, 연결 리스트, 스택, 큐, 데크 등이 있음

 

3. 비선형 구조

  1) 자료들간의 관계가 1:다 또는 다:다일 경우
  2) 계층구조나 망구조를 갖는 자료구조로 트리, 그래프 등이 있음

 

4. 파일 구조

  1) 서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조로 보조기억장치에 데이터가 실제 기록        되는 형태
  2) 파일 구성방식에 따라 순차 파일, 색인 파일, 직접 파일 등이 있음

 

 

▶ 컴퓨터에서의 자료표현

 

컴퓨터는 숫자, 문자, 그림, 소리, 기호 등 자료 형식이 다양해도 1과 0을 조합한 2진수 코드의 형태로 저장 및 처리합니다.

 

2진수 코드 = 비트(bit) 단위

 

n개의 비트로 2^n개의 상태 표현

예) 2^2 = 4  00, 01, 10, 11      2^4 = 16 0000, 0001 ~ 1110, 1111

 

 

▶ 컴퓨터에서의 자료표현의 종류

 

1. 수치자료

 

  · 10진수 => 183⑽ = (1 X 10^2) + (8 X 10^1) + (3 X 10^0)

  · 2진수 => 1010⑵ = (1 X 2^3) + (0 X 2^2) + (1 X 2^1) + (0 X 2^0)

  · 8진수 => 1010⑻ = 001 010(8진수는 한 자리당 3bit, 자리수가 모자르면 0으로 채움)

                    = (0 X 2^2) + (0 X 2^1) + (1 X 2^0), (0 X 2^2) + (1 X 2^1) + (0 X 2^0) = 12

  · 16진수 => 1010 = 10⑽ = a

 

  1) 10진수

 

    1.1) 존(Zone) 형식 : 10진수 한 자리를 표현하기 위해서 8비트를 사용하는 형식.

      - 존 영역 : 상위 4비트로 1111로 표현.

      - 수치 영역 : 하위 4비트로 표현하고자 하는 10진수 한 자리 값에 대한 2진수 값을 표시.

      => 여러 자리의 10진수를 표현하는 방법. 마지막 자리의 존 영역에 부호를 표시. 양수 1100, 음수 1101

출처:https://dudri63.github.io/2019/02/10/ds1/

    1.2) 팩(Pack) 형식 : 10진수 한 자리를 표현하기 위해서 존영역 없이 4비트를 사용하는 형식.

출처:https://slidesplayer.org/slide/17324499/

 

  2) 2진수

      2.1) 절대값형식 : 최상위 1비트를 부호 표시에 사용한 정수 표현. 양수 0, 음수 1

      2.2)  1의 보수 형식 : 1을 0으로 0을 1로 변경한 정수 표현.

         예) 21⑽ 1의 보수 : 11101010⑵

      2.3) 2의 보수 형식: 1의 보수에 1을 더한 정수 표현.

         예) 21⑽ 2의 보수 : 11101011⑵

      2.4) 부동 소수점 형식 : 실수를 표현하기 위해 부호, 지수, 가수 영역을 사용.

        2.4.1) 정규화 : 정수부가 1이 되도록 소수점을 이동하여 과학적 표기로 변환.

                                예) 100010.101 => 1.00010101 X 2^5

        2.4.2) 부호 : 양수 0 음수 1

                             예) 100010.101은 양수이므로 최상위 1비트를 0으로 채움.

        2.4.3) 가수부 : 정규화하면 정수부는 항상 1이 되므로 정수부를 생략하고 소수부만 저장

                                예) 00010101은 가수부(소수 부분), 5가 지수부

        2.4.4) 지수부 : 정규화에서 구한 지수와 바이어스를 더한 값을 저장.(바이어스 값은 지수의 양수음수 부                                  호를 표현하기 위한 방법으로 단정밀도 127, 배정밀도 1023 값으로 사용.

                                예) 단정밀도 : 부호(1비트) => 0

                                                       지수부(8비트) => 5 + 127 = 132 = 10000100⑵

                                                       가수부(23비트) => 0010101이후 0

                                      배정밀도 : 부호(1비트) => 0

                                                        지수부(11비트) => 5 + 1023 = 1027 = 10000000100⑵

                                                        가수부(52비트) => 0010101 이후 0

                             

 

2. 문자자료 

 

  1) BCD(Binary Coded Decimal Code) 코드 : 6bit(존 비트 2bit + 숫자 비트 4bit)를 사용하여 문자(숫자,

                                                                           영어 대문자)를 표현.

    1.1) 존 비트 AB의 값  00 : 숫자 0 , 1 ~ 9(1010, 0001 ~ 1001)

                                       01 : 문자 A ~ I (0001 ~ 1001) => 9개

                                       10 : 문자 J ~ R (0001 ~ 1001) => 9개

                                       11 : 문자 S ~ Z (0010 ~ 1001) => 8개이기 때문에 0001부터 시작하지 않음.

출처 : https://dudri63.github.io/2019/02/10/ds1/

 

  2) EBCDIC(Extended Binary Coded Decimal Interchange Code) 코드 : 8bit(존 비트 4bit + 숫자 비트                                                                                                                                 4bit)를 사용하여 문자 표현.

    1.1) 존 비트 AB의 값 00 : 여분                             존비트 DB의 값  00 : 문자 A ~ I (0001 ~ 1001) => 9개

                                      01 : 특수문자                                                 01 : 문자 J ~ R(0001 ~ 1001) => 9개

                                      10 : 영어 소문자                                            10 : 문자 S ~ Z(0010 ~ 1001) => 8개

                                      11 : 영어 대문자                                             11 : 숫자 0 ~ 9(0000 ~ 1001) => 10개

출처 : https://slidesplayer.org/slide/16065377/

 

  3) ASCII(American Standard Code for Infotmation Interchange) 코드 :  7bit(존 비트 3bit + 숫자 비트                                                                                                                               4bit)를 사용하여 문자 표현

    3.1) ASCII코드를 데이터 통신용으로 사용할 때는 최상위 비트에 패리티비트를 추가하여 8bit 형식으로

          사용.

    3.2) 대문자 A는 65, 소문자 a는 97

출처 : https://dudri63.github.io/2019/02/10/ds1/

 

  4) 유니코드 : 세계 여러 나라의 언어를 통일된 방법으로 표현할 수 있도록 정의한 국제 표준 코드.

 

 

3. 논리자료 : 논리값을 표현하기 위한 자료 형식으로 참(true)은 1, 거짓(False)은 0으로 표현.

 

  1) 1바이트를 사용하여 논리자료를 표현하는 방법

    1.1) 방법1 =>   참 : 최하위 비트를 1로 표시              거짓 : 전체 비트를 0으로 표시

           방법2 =>   참 : 전체 비트를 1로 표시                  거짓 : 전체 비트를 0으로 표시

           방법3 =>   참 : 하나 이상의 비트를 1로 표시      거짓 : 전체 비트를 0으로 표시.

 

 

4. 포인터 자료 : 메모리의 주소를 표현하기 위한 자료 형식. 포인터는 자료형에 상관 없이 메모리 주소 한 개                              를 저장하는 변수이므로 2byte를 사용. 포인터를 사용하면 메모리를 직접 엑세스 할 수 있음.

 

 

5. 문자열 자료 : 한 글자로만 표현할 수 있는 문자 자료와 달리 여러 문자로 이루어진 문자의 그룹을 하나의                              자료로 취급하여 메모리에 연속적으로 저장하는 자료 형식.

 

  1) 하나의 문자열 자료에 포함된 부분 문자열을 표현하는 방법

    1.1) 방법1 => 부분 문자열 사이에 구분자를 사용하여 저장

            장점 : 메모리 이용률이 효율적(OVERHEAD가 생기지 않음) 

            단점 : 문자 비교와 구분자 식별 시간을 모두 계산해야 하기 때문에 탐색 시간이 비효율적

       예) {COM PUTER, MO NITOR, MOU SE}

             COM PUTER;MO NITOR;MOU SE

 

           방법2 => 가장 긴 문자열의 길이에 맞춰 고정 길이로 저장.

           장점 : 메모리 낭비가 생길 수 있다

           단점 : 처리 방식은 가장 빠르다

       예) {COM PUTER, MO NITOR, MOU SE}

             COM PUTER <ㅡㅡ 이 문자의 길이에 맞춰 고정 길이 저장

             MO NITOR

             MOU SE

 

           방법3 => 부분 문자열을 연속하여 저장하고 각 부분 문자열에 대한 포인터를 사용,

           장점 : 메모리 이용률, 탐색 시간 효율적.

        예) {COM PUTER, MO NITOR, MOU SE}

              COM PUTERMO NITORMOU SE

              메모리 주소 : 100~ 122, COM PUTER => 100 ~ 108

                                                     MO NITOR => 109 ~ 116

                                                     MOU SE => 117 ~ 122

               HEAD : 100, 109, 117