자료구조 공부
-
[자료구조]CH7. 트리(이진 탐색 트리)자료구조 공부 2021. 3. 21. 23:57
참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부날짜 : 2021.02.18 이진 탐색 트리 1. 이진 탐색 트리의 개념 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것이다. 탐색을 위해서는 찾을 자료를 식별할 수 있는 유일한 값이 필요한데, 이것을 키(key)라고 한다. 1) 모든 원소는 서로 다른 유일한 키를 갖는다. 2) 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다. 3) 오른쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 크다. 4) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다. 2. 이진 탐색 트리의 탐색 연산 searchBST(bsT , x) p ← bsT; //포인터 p if (p = NULL) then return ..
-
[자료구조]CH7. 트리 (트리의 이해~이진트리의 순회)자료구조 공부 2021. 3. 21. 23:12
참조 : C로 배우는 쉬운 자료구조 공부날짜 : 2021.02.17 트리의 이해 트리는 1:n 관계의 비선형 자료구조이자 계층 관계로 만들어진 계층형 자료구조이다. 트리를 구성하는 원소(자료)를 노드(Node) 라고 하고, 노드를 연결하는 선을 간선(Edge)이라고 한다. 트리의 시작노드, 가장 위의 0레벨의 노드를 루트(Root) 노드라고 한다. 부모 노드(상위 레벨)와 자식 노드(하위 레벨)는 간선으로 이어져 있고, 같은 부모를 가진 자식 노드들은 형제 노드가 된다. 한 노드에서 간선을 따라 루트 노드까지 이르는 경로의 모든 노드는 그 노드의 조상 노드이다. 각 노드의 자식 노드 수만큼 서브 트리를 가지며 이를 노드의 차수(Degree)라 한다. 차수가 0인 노드는 단말노드 또는 리프 노드라고 하고 ..
-
[자료구조]CH6. 큐자료구조 공부 2021. 2. 9. 20:46
참조 : C로 배우는 쉬운 자료구조 (이지영 저) 공부날짜 : 2021.02.07 큐의 이해 1. 큐의 개념과 구조 큐는 삽입과 삭제가 위치와 방법이 제한된 유한 순서 리스트라는 점은 스택과 같지만, 리스트의 한 쪽 끝에서는 삽입 작업만 이루어지고 반대쪽 끝에서는 삭제 작업만 이루어진다는 점이 스택과 다르다. 먼저 삽입된 데이터가 먼저 삭제되는 선입선출(First In First Out) 구조로 운영된다. 한쪽 끝을 front(머리)라고 하고 삭제 연산만 수행하고, 다른 한 쪽은 rear(꼬리)로 삽입 연산만 이루어진다. front는 가장 먼저 큐에 삽입된 첫 번째 원소이고 rear는 가장 늦게 삽입된 마지막 원소이다. 2. 큐의 추상 자료형 front와 rear를 -1로 초기 상태를 설정한다. fron..
-
[자료구조]CH5. 스택자료구조 공부 2021. 2. 3. 19:10
참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부날짜 : 2021.01.31 스택의 이해 1. 스택의 개념과 구조 스택은 데이터를 차곡차곡 쌓아올린 형태로 자료를 구성한다. 스택은 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있고, top으로 정한 한 곳으로만 접근이 가능하다. 즉 top을 통해 들어온 데이터가 일정한 방향, 즉 bottom에서 위로 차곡차곡 쌓인다. 스택에서 top은 삽입과 삭제가 일어나는 곳으로, 현재 스택의 가장 위에 있는 데이터 위치가 된다. top으로 정한 곳에서만 삽입과 삭제가 이루어진다는 원리에 따라, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 구조적 특징을 가진다. 이러한 동작 구조를 LIFO(Last In First Out)라고 한다. 스택에서..
-
[자료구조]CH4. 연결 자료구조와 연결 리스트(~연결 리스트의 응용 및 구현)자료구조 공부 2021. 2. 3. 13:31
참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부날짜 : 2021.01.30 원형 연결 리스트 1. 원형 연결 리스트의 개념 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트 구조를 원형으로 만든 연결 리스트가 원형 연결 리스트(Circular Linked List)이다. 2. 원형 연결 리스트의 알고리즘 2.1 리스트에 첫 번째 노드로 삽입하는 알고리즘 insertFirstNode(CL , x) new ← getNode(); new.data ← x; // 노드의 데이터 필드에 x라는 값을 넣음 if (CL = NULL) then { // 공백 리스트인 경우 CL ← new; // 포인터 CL에 새로운 노드의 주소를 넣음 new.link ← new; // 삽입할 노드의 링크 필드에 본인 주..
-
[자료구조]CH4. 연결 자료구조와 연결 리스트(단순 연결 리스트)자료구조 공부 2021. 1. 28. 14:54
참조 : C로 배우는 쉬운 자료구조 (이지영 저) 공부날짜 : 2021.01.27 단순 연결 리스트 1. 단순 연결 리스트의 개념 단순 연결 리스트는 노드의 링크 필드가 하나이고, 링크 필드는 다음 노드와 연결되는 구조이다. 연결 리스트, 선형 연결 리스트, 단순 연결 선형 리스트라고도 한다. 2. 단순 연결 리스트에서의 삽입 연산 1) 삽입할 노드 준비 삽입할 새 노드로 만들 공백 노드를 메모리에서 할당받는다. 지정한 포인터 변수(이하 new)가 새 노드를 가리키게 한다. 2) 새 노드의 데이터 필드값 저장 new노드의 데이터 필드에 값을 저장한다. 3) 새 노드의 링크 필드값 지정 new노드를 삽입할 자리의 바로 앞 노드의 링크 필드값을 new 노드의 링크 필드값에 저장한다. 4) 리스트의 앞 노드에..
-
[자료구조]CH3. 순차 자료구조와 선형리스트(행렬~) - CH4. 연결 자료구조와 연결리스트(~연결 자료구조와 연결 리스트의 이해)자료구조 공부 2021. 1. 26. 20:48
참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부 날짜 : 2021.01.24 2. 행렬의 선형 리스트 표현 행렬은 행과 열로 이루어진 자료구조이다. 행렬에서 행의 개수와 열의 개수가 같은 행렬을 정방행렬이라고 하며, 행렬의 행과 열을 서로 바꿔 구상한 행렬을 전치행렬이라고 한다. m*n 행렬 A를 2차원 배열 A[m][n]으로 표현할 수 있다. 하지만 대부분의 원소 값이 0인 희소행렬의 경우에는 기억 공간의 활용도가 떨어진다. 그러므로 0이 아닌 원소들에 대한 의 쌍을 구해 2차원 배열에 저장한다. 이때 이 2차원 배열의 첫번째 행은 이다. CH4. 연결 자료구조와 연결 리스트 연결 자료구조와 연결 리스트의 이해 1. 연결 자료구조의 개념 순차 자료구조의 연산 시간과 저장 공간에 대한 문제를 개선한..
-
[자료구조]CH3. 순차 자료구조와 선형 리스트(~다항식의 선형 리스트 표현)자료구조 공부 2021. 1. 23. 23:04
참조 : C로 배우는 쉬운 자료구조(이지영 저) 공부날짜 : 2021.01.23 순차 자료구조와 선형 리스트의 이해 1. 순차 자료구조의 개념 순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식이다. 따라서 논리적 순서와 물리적 순서가 항상 일치한다. 이러한 방식의 프로그램 기법은 배열을 이용하여 구현한다. 2. 선형 리스트의 표현과 연산 2.1 선형 리스트의 표현 자료를 구조화하는 가장 기본적인 방법은 나열이다. 이런 나열한 목록을 리스트라고 한다. 이때 원소들을 순서대로 나열한 리스트를 선형 리스트 또는 순서 리스트라고 한다. 나열된 순서가 원소의 순서이며, 원소가 하나도 없는 리스트는 공백 리스트라고 한다. 선형 리스트(선형 순차 리스트)는 논리적 순서와 물리적 ..