-
자료구조 개념 정리프로그래밍 기초/자료구조 2020. 9. 27. 21:02
자료구조 개요
자료구조란?
데이터를 효율적으로 접근 및 사용이 가능하도록 하는 데이터의 조직, 저장, 관리 방법을 말한다.
자료 구조의 분류
- 선형 구조 자료 간 연결 관계가 1:1 관계인 구조
- 스택, 큐, 덱
- 배열과 연결 리스트가 포함되기도 한다.
- 비선형 구조 계층 구조 혹은 망 구조
- 트리, 그래프
자료구조의 표현
자료의 표현 방법
컴퓨터는 0과 1로 구성된 2 진수를 사용하며 n 개의 비트로 2ⁿ 개의 상태를 표현 가능하다.
1 개의 비트 → 2¹ = 2 개의 상태 표현 (0, 1)
2 개의 비트 → 2² = 4 개의 상태 표현 (00, 01, 10, 11)
3 개의 비트 → 2³ = 8 개의 상태 표현 (000, 001, 010, 011, 100, 101, 110, 111)
º
º
º
n 개의 비트 → 2ⁿ 개의 상태 표현
자료형
- 정수 자연수, 자연수의 음수, 0을 표현한다.
- 10진수
- 존 방식 한 자리를 표현할 때 8비트를 사용하며 부호를 표현하는 상위 4비트와 값을 표현하는 하위 4비트로 구성된다.
- 팩 방식 한 자리를 표현할 때 4비트를 사용하며 값의 마지막에 4비트를 추가하여 부호를 표현할 때 사용한다.
- 2진수
- 부호절대값 최상위 1비트를 부호를 표현할 때 사용한다. 덧셈기와 뺄셈기를 따로 구현해야 한다.
- 1의 보수 양수는 부호절대값 형식으로 표현하고 음수는 2진수의 1의 보수로 사용한다. +0와 -0이 따로 존재한다.
- 2의 보수 양수는 부호절대값 형식으로 표현하고 음수는 2진수의 2의 보수로 사용한다.
- 10진수
- 실수 0보다 큰 양수, 0보다 작은 음수, 0으로 구분되며 소수점을 표현한다.
- 고정소수점 최상위 비트 왼쪽에 소수점이 고정된 것으로 취급하여 값을 표현한다. 표현 범위의 제약이 크다.
- 부동소수점 비트를 부호와 지수, 소수로 구분하여 표현 범위가 매우 넓다. 정확한 값이 아닌 근삿값으로 표현된다.
- 논리 참과 거짓만을 가진다.
- 문자 인간이 사용하는 문자를 표현한다.
- 문자열 문자 혹은 기호의 순차 수열을 말하며 문자를 연속적으로 연결해 표현한다.
추상 자료형
자료의 형태와 관계된 연산을 수학적으로 정의한 것을 말하며 구체적인 구현을 포함하지 않는다.
이러한 추상화를 통해 알고리즘 정의를 단순화할 수 있다.
자료 연산 추상화 추상 자료형 알고리즘 정의 구체화 자료형 프로그램 구현 자료구조 구현을 위한 프로그래밍 언어의 요소
- 배열 같은 타입의 데이터를 메모리에 연속적으로 저장하여 인덱스를 통해 접근할 수 있도록 만든 자료구조
- 포인터 저장된 데이터의 메모리 주소를 가리키는 변수
- 구조체 여러 타입의 데이터를 묶어 사용하는 사용자 정의 자료형
배열
- 1차원 배열 동일한 타입의 데이터가 선형으로 나열된 배열
- 문자열 문자 타입의 데이터로 이루어진 1차원 배열
- 다차원 배열 동일한 타입의 데이터가 2차원 이상으로 나열된 배열
순서대로 1차원 배열, 2차원 배열, 3차원 배열 포인터
자료구조 작성에 포인터를 사용할 때의 이점은 다음과 같다.
- 주소를 저장하는 값이기 때문에 크기가 일정하다. 32비트 빌드 환경 4 bytes, 64비트 빌드 환경 8 bytes
- 자료구조를 수정하는 경우 메모리 수정 없이 포인터가 가리키는 주소의 변경 만으로 처리가 가능하다.
- 선형 구조 자료 간 연결 관계가 1:1 관계인 구조