반응형 코딩테스트 및 개인공부/자료구조10 [자료구조] [5] 포인터, 연결리스트 * 포인터는 내가 중요하다고 생각되거나, 까먹었거나, 확실하게 알지 못했던 부분만 정리. 포인터 - 포인터의 활용 void* p; // 임의 자료형의 주소를 저장하기 위한 포인터 void* p는 아무것도 가리키지 않는 포인터를 의미. void 포인터는 필요할 때 마다 다음과 같이 다른 포인터로 바꾸어서 사용한다. void* p; int* pi; pi = (int*)p; // p를 정수 포인터로 변경해 pi로 대입 - 포인터 연산 다음의 문장들을 잘 구분하여 사용하여야 한다. p : 포인터 *p : 포인터가 가리키는 값 *p++ : 포인터가 가리키는 값을 가져온 다음, 포인터를 한 칸 증가 *p-- : 포인터가 가리키는 값을 가져온 다음, 포인터를 한 칸 감소 (*p)++ : 포인터가 가리키는 값을 증가시.. 2021. 12. 8. [자료구조] [4] 큐 , 덱 큐(queue) 먼저 들어온 데이터가 먼저 나가는 자료구조. 선입선출(FIFO). 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조. -> 스택은 삽입/삭제가 같은 쪽에서 일어나지만 큐는 다른 쪽에서 일어난다. 큐에서 삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)라고 한다. - 큐의 추상 자료형 init() : 큐를 초기화 enqueue(e) : 요소 e를 큐의 맨 뒤에 추가한다. dequeue() : 큐의 맨 앞 요소를 삭제하고 반환한다. is_empty() : 큐가 비어있으면 TRUE, 아니면 FALSE 반환 peek() : 큐의 맨 앞 요소를 삭제하지 않고 반환. is_full() : 큐가 가득 차있으면 TRUE, 아니면 FALSE 반환 si.. 2021. 12. 7. [자료구조] [3] 스택 스택 스택은 자료의 입출력이 후입선출(LIFO)의 형태로 일어나는 자료 구조. 스택은 가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다. - 스택의 연산 init() : 스택을 초기화 is_empty() : 스택이 비어있으면 TRUE, 아니면 FALSE 반환 is_full() : 스택이 가득 차 있으면 TRUE, 아니면 FALSE 반환 size(): 스택 내의 모든 요소들의 개수를 반환 push(x) : 주어진 요소 x를 스택의 맨 위에 추가 pop() : 스택 맨 위에 있는 요소를 삭제하고 반환 peek() : 스택 맨 위에 있는 요소를 삭제하지 않고 반환 - .. 2021. 12. 1. [자료구조] [2] 배열과 구조체 배열 - 배열의 직접 접근 방식 k번째 항목을 참조할 때 이 항목의 위치(주소)가 바로 계산되어 항목을 참조할 수 있다. 이것을 직접 접근 방식이라고 한다. 항목 접근의 시간 복잡도는 O(1). * 연결리스트의 접근 방식과 비교 연결 리스트에서는 k번째 항목을 참조할 때 맨 처음 항목부터 k번을 반복적으로 찾아가야 한다. 이것을 순차 접근 방식이라고 한다. 항목 접근의 시간 복잡도는 O(n). 하지만 다른 장점이 있다. - 1차원 배열 - 배열에서는 모든 요소들이 메모리의 연속된 공간에 저장된다. 아래와 같은 정수 배열을 선언한다면, int A[6]; A는 배열이 저장된 공간의 시작 주소(또는 기본주소)가 된다. 배열의 요소들은 메모리의 연속된 공간에 저장되어 있기 때문에 각 항목들의 주소가 기본 주소로.. 2021. 11. 29. [자료구조] [1] 자료구조와 알고리즘의 개념, 알고리즘의 복잡도 분석 자료구조의 분류 -단순 자료구조 : 정수, 실수, 문자와 같이 대부분의 프로그래밍 언어에서 기본적으로 제공하는 것. -복합 자료구조 여러 개의 자료들을 모은 창고와 같다. 자료에 접근하는 방법이 있어야 하는데 크게 직접 접근과 순서 접근으로 나눌 수 있다. 배열은 대표적인 직접 접근 방법. 인덱스 i를 이용해 i번째 요소 A[i]에 한 번 만에 접근. 연결 리스트는 대표적인 순서 접근 방법. 원하는 자료를 찾기 위해 시작 노드에서 부터 다음 노드로 하나씩 이동하면서 찾아야 한다. 복합 자료구조는 창고의 형태에 따라 선형 구조와 비선형 구조로 나누어진다. -선형 자료구조 기본적으로 자료들이 순서적으로 나열된다. 스택,큐,덱은 자료의 접근이 맨 앞과 맨 뒤 항목으로 제한. 리스트는 임의의 위치에 있는 항목의.. 2021. 11. 29. 이전 1 2 다음 반응형
