Data Structure

◆ 그래프 관련 기초 함수를 구현 ■ 그래프를 인접 행렬로 표현하고 각 정점의 차수를 계산 ● void ADJ_Degree(int adj_mat[][MAX_VERTICES], int n); ■ 인접 행렬로 표현된 그래프를 인접 리스트로 변환 ● void ADJ_Insert(G_Node** List, int i, int j); ● void ADJ_Mat2List(int adj_mat[][MAX_VERTICES], int n, G_Node** List); ■ 인접 리스트로 표현된 그래프를 순회하여 각 정점을 방문 ● void Graph_DFS(G_Node** List, int v); ● void Graph_DFS_Recursive(G_Node** List, int v); ■ 코드: (1) 헤더파일 (2) 메..

실습과제 8.1 ◆ 연결리스트 기반의 이진탐색트리를 구현해 보자. ■ 이진 탐색 트리를 위한 기본 연산 1) 가장 작은 값 탐색 : int BST_Min(BT_Node* root) 2) 가장 큰 값 탐색 : int BST_Max(BT_Node* root) 3) 주어진 키 값을 가진 노드 탐색 : BT_Node* BST_Search(BT_Node* root, int target) 4) 새로운 키 값을 삽입 : void BST_Insert(BT_Node** root, int key) 5) 주어진 키 값을 삭제 : void BST_Delete(BT_Node** root, int key) ■ 코드: (1) 헤더파일 (2) 메인 함수 ■ 실행결과: ■ 과제에 대한 고찰: 이진 탐색 트리에 대한 개념과 알고리즘을 ..

실습과제 7.3 ◆ 연결리스트 기반의 이진트리를 구현해 보자. ■ 1. 연결 리스트를 이용한 이진트리의 구성 1) 노드 생성 : BT_Node* BT_Create_Node(int newData) 2) 노드 소멸 : void BT_Destroy_Node(BT_Node* node) 3) 왼쪽 자식으로 연결 : void BT_Make_Left_Sub_Tree(BT_Node* parent, BT_Node* sub) 4) 오른쪽 자식으로 연결 : void BT_Make_Right_Sub_Tree(BT_Node* parent, BT_Node* sub) ■ 2. 이진 트리의 순회(전위, 중위, 후위) 알고리즘 1) 전위 순회 : void BT_Preorder_Traversal(BT_Node* node); 2) 중위 ..

실습과제 7.2 ◆ 최대 힙 트리의 삽입/삭제 함수를 구현해 보자. ■ 최대 힙 트리의 삽입 함수 ● void Max_Heap_Insert(int* heap, int* h_size, int key); ■ 최대 힙 트리의 삭제 함수 ● int Max_Heap_Remove(int* heap, int* h_size); ■ 코드: (1) 헤더파일 (2) 메인 함수 ■ 실행결과: ■ 과제에 대한 고찰: 이번 과제를 하면서 처음에는 이진트리 출력 함수를 이해하는 데 어려움을 겪었습니다. 다음으로는 최대 힙 트리에서 삽입과 삭제를 수행하는 함수를 구현하는 것이었습니다. 특히, 힙의 성질을 유지하기 위해 부모와 자식 노드 간의 크기 비교와 위치 교환을 하는 부분에서 어려움을 겪었습니다. 인덱스 계산과 반복문 조건 설정..

실습과제 7.1 ◆ 완전 이진트리가 주어졌을 때, 다음과 같은 함수를 구현해 보자. ■ i 번째 노드의 모든 조상 노드를 출력하는 함수 ● void PrintAncestor (int* bTree, int size, int idx); ■ i 번째 노드의 모든 왼쪽 후손 노드들을 출력하는 함수 ● void PrintLeftDescendant (int* bTree, int size, int idx); ■ i 번째 노드의 모든 오른쪽 후손 노드들을 출력하는 함수 ● void PrintRightDescendant (int* bTree, int size, int idx); ■ 해당 값을 가진 노드의 인덱스를 반환하는 함수 ● int FindNode(int* bTree, int size, int data); ■ 코드..

실습과제 6.1 ◆ 배열을 활용한 원형 큐를 구현해 보자. ■ 아래 함수들을 구현 ● bool IsEmpty(); // 큐가 비어 있는지 확인 (true or false) ● bool IsFull(); // 큐가 가득 차 있는지 확인 (true or false) ● bool Enqueue(T item); // 큐에 데이터를 삽입하는 연산 ● T Dequeue(); // 큐에서 데이터를 꺼내는 연산 ● T Peek(); // 최상단 데이터를 확인하는 연산 ■ 코드: (1) 함수 기능 구현 파일 (2) 메인 함수 ■ 실행결과: ■ 과제에 대한 고찰: 배열을 사용하여 원형 큐를 설계하는 과제였다. 단순 배열의 문제점을 원행 배열을 사용하여 해결하였으며 원형 배열에서 큐의 기본 연산을 구현하였다. 배열 큐의 단..