자료구조6 [자료구조] 해시 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 해시(Hash) 해시법은 기존 배열을 이용한 데이터 관리를 좀더 효율적으로 관리하기위해 임의의 길이(Prime Number)의 테이블을 이용하여 매핑하는 방법이다. 배열을 이용할때는 삭제하기 위해서는 시간복잡도가 O(n)만큼 들지만 해시법을 이용하면 O(1)만큼 들다. 해싱 key값을 임의의 수로 만들어주는 함수("GetKey()")를 이용하여 해시값을 구한다. 해시값에 해당하는 주소가 가리키는 노드의 가장 끝단까지 이동한다. 이동하면서 중복된 key값이 있는지 확인한다. 가장 끝단에 노드를 만들어 Key, Daata값을 저장한.. 2020. 11. 1. [자료구조] 큐 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 큐(Que) 큐는 기본적으로 선입선출(First In First Out)을 따른다. 큐라는 배열에 Enque()를 통해 데이터를 입력하고 Deque()를 통해 먼저 들어온 값부터 출력하는 구조이다. Enque rear가 가리키는 위치에 데이터를 입력한다. rear를 1증가시킨다. 만일 rear가 큐의 max보다 크면 0으로 초기화한다. Deque front가 가리키는 위치의 데이터를 출력한다. front를 1증가시킨다. 만일 front가 큐의 max보다 크면 0으로 초기화한다. 소스코드 #define __main #ifdef _.. 2020. 11. 1. [자료구조] 스택 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 스택(Stack) 스택은 기본적으로 후입선출(Last In First Out)을 따른다. 스택이라는 배열에 Push()를 통해 차곡차곡 쌓아올리고 Pop()을 통해 가장 늦게 들어온 값부터 출력하는 구조이다. Push() 배열에서 ptr위치에 값을 넣는다. ptr을 1증가시킨다. Pop() ptr를 1감소시킨다. 배열에서 ptr위치의 값을 출력한다. 소스 코드 #define __main #ifdef __main #include typedef struct __Stack{ int* stk; // 스택 int max; // 스택의 최.. 2020. 10. 30. [자료구조] 이진 트리 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 이진트리(Binary Tree) 이전에 배웠던 연결 리스트는 각 노드에 Data와 다음 노드를 가리키는 포인터변수가 있었다. 하지만 이진트리는 각 노드에 Data와 왼쪽, 오른쪽 노드를 가리키는 포인터변수가 있는 구조로 되어있다. 또한 같은 깊이에 있는 노드들을 Level이라고 한다. 이진트리 삽입 첫 노드는 그냥 입력한다. 첫 노드(Root)를 시작으로 각 노드와 비교하여 작으면 왼쪽, 크면 오른쪽 노드로 간다. 노드가 NULL이면 입력한다. NULL이 아니면 "2번"으로 간다. 2번과 3번을 반복한다. 이진트리 삭제 자식 노.. 2020. 10. 29. 이전 1 2 다음
