728x90 정글 2기/자료구조(C언어)5 [C언어] 이중포인터를 이용하여 배열을 교환하는 방법 [C언어] 이중포인터를 이용하여 배열을 교환하는 방법 배열 A와 배열 B를 바꾸고 싶은 경우를 생각해보자. 배열을 일일히 바꿔주는 것은 너무나 번거로운 일이다. 쉽게 바꾸기 위해 포인터가 기리키는 값만 바꾸어 주면 되는데, 이 때 함수를 사용하고자 한다면 이중포인터를 사용해야 한다. '함수에서 굳이 왜 이중포인터를 사용해야 될까?'를 고민한 끝에 얻은 결론은 dereference(역참조)를 해야 함수 밖 값의 변화를 줄 수 있기 떄문이다. 자 먼저 더 쉬운 예를 보자. 변수 값 서로 바꾸기 #include void swapNumber(int first, int second) // 반환값 없음, int형 매개변수 두 개 지정 { int temp; // 임시 보관 변수 temp = first; first =.. 2021. 9. 14. [C언어] 레드-블랙 트리(Red-black Tree, RB Tree) [C언어] 레드-블랙 트리(Red-black Tree, RB Tree) 트리 구조 중 가장 복잡한 구조인 레드-블랙 트리에 대해 배워보자. RBT는 자가 균형 이진 탐색 트리로서 실 사용에서 효율적이고 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. Red-black tree 의 특징 RBT의 특징 모든 노드는 빨강이거나 검정이다. 루트는 검정이다. (검정으로 변환) 모든 리프(NIL)는 검정이다. 노드가 빨간색이면 그 노드의 자식은 모두 검정이다. (연속 빨간 노드는 회전 필요) 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 검정 노드를 포함한다. 부모노드는 왼쪽 서브트리보다 크고.. 2021. 9. 9. [C언어] 이진 탐색 트리(Binary Search Tree, BST) [C언어] 이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 트리란 이진 탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조의 일종이다. 이진 탐색의 효율적인 탐색 능력(O(log n)은 유지하면서 자료 입력과 삭제가 효율적으로(O(1)) 가능하다. 이진 탐색 트리 특징 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. 이진 탐색 트리 기능 검색, 추가, 삭제, 최솟값 찾기 코드 #include #include typedef i.. 2021. 9. 7. [C언어] 연결 리스트(Linked list) 구현 [C언어] 연결 리스트(Linked list) 구현 연결리스트는 복잡한 트리 구조를 구현하기 위해 사용되기 때문에 꼭 알고 넘어가야 한다. 이를 위해 구조체, 포인터, 동적 메모리 할당 등의 개념이 사용된다. 연결 리스트 연결 리스트란 데이터가 담긴 노드(메모리 공간)를 일렬로 연결하여 리스트화 한 것이다. 연결 리스트 특징 리스트의 중간 지점에서 노드를 손쉽게 추가하거나 삭제할 수 있다. 특정 노드를 찾으려면 노드를 모두 검색해야 한다.(최악의 경우) -> 하나씩 찾아봐야 하기 때문에 원하는 노드를 찾는데 오래 걸린다. 크기가 고정되어 있지 않다. 연결 리스트 기능 연결 리스트에서는 다음이 가능하다. 추가 삭제 찾기 노드 간 연결 새 노드 추가 노드 삭제 연결 리스트 코드 연결 리스트 코드 구현 #in.. 2021. 9. 5. [C언어] 구조체 포인터 사용하기 [C언어] 구조체 포인터 사용하기 다른 자료형과 마찬가지로 구조체도 포인터를 선언할 수 있으며, malloc 함수를 이용하여 동적 메모리를 할당할 수 있다. #define _CRT_SECURE_NO_WARNINGS // strcpy 보안 경고로 인한 컴파일 에러 방지 #include #include // strcpy 함수가 선언된 헤더 파일 #include // malloc, free 함수가 선언된 헤더 파일 struct Person { // 구조체 정의 char name[20]; // 구조체 멤버 1 int age; // 구조체 멤버 2 char address[100]; // 구조체 멤버 3 }; int main() { struct Person *p1 = malloc(sizeof(struct Perso.. 2021. 9. 4. 이전 1 다음 728x90
