자료 구조

1. 배열, 구조체, 포인터

배열: 타입이 같은 데이터를 하나로 저장하는 구조

구조체: 타입이 서로 달라도 데이터를 하나로 저장할 수 있는 구조

 포인터

• &연산자: 데이터의 주소를 추출
• *연산자: 포인터가 가리키는 곳의 데이터를 추출

동적 메모리 할당: 프로그램이 실행되는 도중 메몰 할당. 필요한 만큼 사용하고 다시 되돌림. 메모리 효율성 증가.

ex) 

int *p;

p=(int*) malloc(sizeof(int));

...

free(p);

자료구조 개요

자료구조: 데이터를 효율적으로 사용하기 위해 체계적으로 관리하는 방법

 

자료구조의 분류

• 선형 구조: 데이터들이 한 줄로 늘어선 자료구조.
• 비선형 구조: 하나의 자료 뒤에 여러 개의 자료가 존재하는 구조.

알고리즘: 적합한 순서를 통해 제한된 시간 내에 문제를 해결하는 명령어들의 집합.

배열

배열에서의 데이터 추가

연결 리스트

연결 리스트: 데이터들이 데이터 주소에 따라 연결된 방식. 물리적 순서는 일치하지 않아도 됨.

 

연결 리스트 구조

• 노드: 연결 리스트는 <원소(데이터), 주소> 단위로 구성. 다음에 이어질 데이터에 대한 주소 포함.
• 노드의 구조: 데이터 필드& 링크 필드

 

연결 리스트의 분류

• 단순 연결 리스트: 노드와 링크 필드가 하나임. 링크 필드는 다음 노드와 연결되는 가장 기본적인 구조.
• 이중 연결 리스트: 양쪽으로 모두 순회할 수 있음. 

연결 리스트 추가 & 삭제

구분	배열	연결 리스트
데이터 검색 기능	인덱스를 알면 쉽게 찾을 수 있음	첫 노드부터 순차적으로 탐색함
메모리 공간	자료를 위한 메모리 공간이 필요	자료를 위한 공간 이외에 링크 필드의 포인터를 위한 메모리 공간도 필요
메모리 사용	정적 메모리를 사용하기에 최대 자료 개수를 미리 알아야함	프로그램 실행 도중에도 메모리 공간을 할당 받을 수 있음
데이터 추가 및 삭제	시간이 오래 걸림	시간이 적게 걸림

스택

스택: 데이터를 일렬로 쌓아둔 형태의 자료 구조

 

스택의 구조

• 스택에서는 톱으로 맨 위의 부분에 데이터를 추가하거나 데이터를 삭제함.(중간에 데이터 추가 및 삭제 불가능)
• LIFO: last in first out 마지막에 들어간 데이터가 제일 먼저 나옴!

 

스택 데이터 추가 및 삭제

• 푸시(push): 데이터를 추가
• 팝(pop): 데이터 삭제

 

큐

큐

• 데이터가 한 방향에서 삽입되고 반대 방향으로만 삭제되는 자료 구조.
• 한쪽 끝을 front 다른 쪽을 rear로 정의하여 삽입 연산을 수행.  
• FIFO: first in first out. 먼저 삽입된 데이터가 먼저 삭제됨

큐에서 데이터 추가 및 삭제

 

원형 큐

원형 큐:선형 큐의 비효율적인 메모리 사용으로 인해 만들어짐.

 

큐의 전단과 후단을 관리하기 위해서 2개의 변수 사용.

front: 첫 번째 요소 하나 앞의 인덱스

rear: 마지막 요소의 인덱스

 

front와 rear 가 같은 경우는 공백 상태이거나 포화 상태인 경우.

공백 상태와 포화상태 구분을 위해 하나의 공간을 비워 둠.