자료구조(Data Structure의 개념
- 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것.
일상생활과 자료구조의 유사성
| 일상생활에서의 예 | 해당하는 자료구조 |
| 그릇을 쌓아서 보관 | 스택 |
| 마트 계산대의 줄 | 큐 |
| 버킷 리스트 | 리스트 |
| 영어사전 | 사전 |
| 지도 | 그래프 |
| 컴퓨터의 디렉토리 구조 | 트리 |
자료의 형태에 따른 분류
- 단순 구조 : 정수, 실수, 문자, 문자열, 등의 기본 자료형
- 선형 구조
- 자료들 사이의 관계가 1:1 관계
- 순차 리스트, 연결 리스트, 스택, 큐, 데크 등
- 비선형 구조
- 자료들 사이의 관계가 1:다, 또는 다:다 관계
- 트리, 그래프 등
- 파일 구조
- 서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조
- 순차 파일, 색인 파일, 직접 파일 등
컴퓨터에서의 자료 표현
- 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료를 2진수 코드로 표현하여 저장 및 처리
- 2진수 코드 : 1과 0, On과 Off, 참과 거짓
1비트
4비트 = 1니블
8비트 = 2니블 = 1바이트
n개의 비트로 2^n개의 상태 표현
컴퓨터의 모든 데이터는 bit 조합
- 컴퓨터 프로그램은 컴퓨터 상의 메모리에 어떤 데이터가 어떤 위치에 있는 지를 파악하고 있어야 함.
프로세서는 유한한 크기의 데이터를 가지고 작업함.
모든 데이터는 bit sequence로 표현됨.
- bit = 0 or 1
- 전류의 충전 수준에 따라 0 또는 1로 표시됨.
Byte = 8bits
Word = 프로세서가 다루는 가장 큰 단위의 데이터
- 32bits = 대부분의 오래된 컴퓨터들
- 64bits = 대부분의 최근 컴퓨터들
C언어에서의 데이터 타입
- 실질적인 데이터 타입 4종류
- char
- int (short, long, long long, unsigned)
- float
- double
머신 내에서 각 데이터 타입의 크기는 명확하지만, 각 데이터 타입의 크기는 머신마다 다름.
| Type | Size(bytes) |
| char | 1 |
| int | 4 |
| short | 2 |
| long | 8 |
| long long | 8 |
| float | 4 |
| double | 8 |
10진수의 표현
- Zone 형식의 표현
- 10진수 한 자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식
- 존 영역
- 상위 4비트
- 1111로 표현
- 수치 영역
- 하위 4비트
- 표현하고자 하는 10진수 한 자리 값에 대한 2진수 값을 표시
- 여러 자리의 10진수를 표현하는 방법
- 10진수의 자릿수만큼 존 형식을 연결하여 사용
- 양수 : 1100 - 음수 : 1101
- Pack 형식의 표현
- 존 영역 없이 4비트를 사용하는 형식
- 최하위 4비트에 부호를 표시
- n비트의 부호 절댓값 형식
- 최상위 1비트 : 부호 표시
- 양수(+) : 0
- 음수(-) : 1
- 나머지 n-1 비트 : 이진수 표시
2진수의 정수 표현
- 1의 보수(1' Complement) 형식
음수 표현에서 부호 비트를 사용하는 대신 1의 보수를 사용하는 방법
- n비트의 2진수를 1의 보수로 만드는 방법
- n비트를 모두 1로 만든 이진수에서 변환하고자 하는 이진수를 뺌
ex) 4 = 100
111 - 100 = 011
100 -> 011 : 원래와 반대로 쓰면 1의 보수
- 2의 보수 형식
1의 보수에 1을 더함.