dew's CSE Studying

11.1 최소 비용 신장 트리신장 트리신장 트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리 1.모든 정점들이 연결되어 있어야 하고2.사이클을 포함해서는 안된다=>그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다 -깊이우선/너비우선 탐색 도중 사용된 간선들만 표시하면 만들 수 있다-그래프의 최소 연결 부분 그래프최소: 간선의 수가 가장 적다(최소 n-1개의 간선)-통신 네트워크 구축에 많이 사용-각 링크의 구축 비용이 같지 않기 때문에 가장 적은 링크만 사용한다고 해서 최소 비용이 얻어지는 것은 아니다  최소 비용 신장 트리최소 비용 신장 트리(MST: minimum spanning tree): 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 ..

5.1 큐 추상 데이터 타입큐(queue): 먼저 들어온 애가 먼저 나가는 선입선출(FIFO:First In First Out)구조의 자료구조마트에서 줄 서는 거를 생각하자!!계속 쌓이는 스택의 경우 데이터의 추가와 삭제가 같은 쪽에서 일어났지만 큐는 전단(front)에서 삭제가, 후단(rear)에서 삽입이 일어난다! 큐의 ADT:-객체: 0개 이상의 요소들로 구성된 선형 리스트-연산: create(max_size) ::= 최대 크기가 max_size인 공백큐를 생성 init(q) ::= 큐를 초기화 is_empty(q) ::= if(size==0) return TRUE; else return FALSE; is_full(q) ::= ..

//허프만 코드 프로그램 #include #include #define MAX_ELEMENT 200 typedef struct TreeNode { int weight; char ch; struct TreeNode* left; struct TreeNode* right; }TreeNode; typedef struct { TreeNode* ptree; char ch; int key; }element; typedef struct { element heap[MAX_ELEMENT]; int heap_size; }HeapType; //생성함수 HeapType* create() { return (HeapType*)malloc(sizeof(HeapType)); } //초기화함수 void init(HeapType* h) ..

#include #include #define MAX_ELEMENT 200 typedef struct { int key; }element; typedef struct { element heap[MAX_ELEMENT]; int heap_size; }HeapType; //초기화 함수 void init(HeapType* h) { h->heap_size = 0; } //생성함수 HeapType* create() { return (HeapType*)malloc(sizeof(HeapType)); } //heap의 삽입함수 void insert_max_heap(HeapType* h, element item) { int i; //i는 인덱스 번호 i = ++(h->heap_size); //트리를 거슬러 올라가면서 부모..

//이진탐색트리 #include #include typedef int element; typedef struct TreeNode { element key; struct TreeNode* left, * right; }TreeNode; TreeNode* new_node(int item) { TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode)); //동적으로 메모리를 할당하여 새로운 노드를 생성 temp->key = item; temp->left = temp->right = NULL; return temp; } //순환적인 탐색함수 TreeNode* search(TreeNode* node, int key) { if (node == NULL) return NULL; if..

//스레드 이진 트리 순회 프로그램 #include #define TRUE 1 #define FALSE 0 typedef struct TreeNode { int data; struct TreeNode* left, * right; int is_thread; //만약 오른쪽 링크가 스레드이면 TRUE }TreeNode; // G // C F // A B D E TreeNode n1 = { 'A',NULL,NULL, 1}; TreeNode n2 = { 'B',NULL,NULL, 1}; TreeNode n3 = { 'C',&n1,&n2,0}; TreeNode n4 = { 'D',NULL,NULL,1}; TreeNode n5 = { 'E',NULL,NULL,0 }; TreeNode n6 = { 'F',&n4,&n..

[순회 프로그램] //순회 프로그램 #include #include #include typedef struct TreeNode { int data; struct TreeNode* left, * right; }TreeNode; // 15 // 4 20 // 1 16 25 TreeNode n1 = { 1,NULL,NULL }; TreeNode n2 = { 4,&n1,NULL }; TreeNode n3 = { 16,NULL,NULL }; TreeNode n4 = { 25,NULL,NULL }; TreeNode n5 = { 20,&n3,&n4 }; TreeNode n6 = { 15,&n2,&n5 }; TreeNode* root = &n6; inorder(TreeNode* root) {//중위순회 if (root..

#10 배열에 들어 있는 정수의 순서를 거꾸로 하는 프로그램을 작성해보자. 스택을 사용한다. //스택코드 #define _CRT_SECURE_NO_WARNINGS #include #include #define MAX_STACK_SIZE 100 typedef int element; typedef struct { element data[MAX_STACK_SIZE]; int top; } StackType; //스택초기화 함수 void init_stack(StackType* s) { s->top = -1; } //공백상태 검출함수 int is_empty(StackType* s) { return (s->top == -1); } //포화상태 검출함수 int is_full(StackType* s) { return (..

LAB 1: 단어들을 저장하는 연결리스트 #define _CRT_SECURE_NO_WARNINGS #include #include #include typedef struct { char name[100]; }element; typedef struct ListNode { element data; struct ListNode* link; }ListNode; //오류처리함수 void error(char* message) { fprintf(stderr, "%s\n", message); exit(1); } //INSERT_FIRST ListNode* insert_first(ListNode* head, element value) { ListNode* p = (ListNode*)malloc(sizeof(ListNod..