*정렬(sorting) : 물건을 크기순으로 오름차순이나 내림차순으로 나열하는 것을 의미 정렬의 대상은 레코드 (recode) -> 레코드는 필드(field)라고 하는 단위로 구성되어 있음. EX) 학생 레코드 : [school-num][name][age][address][p-num] -> 5개의 필드로 구성되어 있는 레코드 여기서 다른 레코드와 차별되는, 레코드를 특정해주는 필드를 키(key)값 이라고 한다. 즉, 정렬은 레코드를 키값을 기준으로 배열하는 것이다. 1. 선택 정렬 (selection sort) // selection sort #include #include // 배열 크기 지정 #define MAX_SIZE 10 // SWAP 함수를 정의 , x와 y값을 바꾸어줌 #define SWAP..
Data structure
그래프(graph) : 객체 사이의 연결 관계를 표현할 수 있는 자료구조 그래프를 표현하는 방법 1. 인접행렬 : 2차원 배열을 사용하여 그래프를 표현 2. 인접리스트 : 연결 리스트를 사용하는 그래프를 표현 // 인접 행렬을 이용한 그래프 구현 #include #include #define MAX_VERTICES 50 // 정점의 개수 최대값 typedef struct GraphType { int n;// 정점의 개수 int adj_mat[MAX_VERTICES][MAX_VERTICES]; } GraphType; // 그래프 초기화 void init(GraphType* g) { int r, c; g->n = 0; for (r = 0; rn) + 1) > MAX_VERTICES) { fprintf(std..
/* 우선순위 큐 : 우선순위의 개념을 큐에 적용한 것 기존의 큐는 삽입 순서에 따라 순서대로 삭제가 일어났다. 즉, 우선순위가 삽입 순서에 국한되었다. 그러나 우선순위 큐는 삽입순서 뿐만 아니라 다양한 요소들을 우선순위로 설정하여 삭제 순서를 정한다. 우선순위 큐 표현 방법 1. 배열을 사용하는 방법 2. 연결리스트를 사용하는 방법 3. 히프를 사용하는 방법 (히프 heap : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리(완전 이진 트리)) */ // 히프 트리 테스트 프로그램 #include #include #define MAX_ELEMENT 200 typedef struct { int key; } element; typedef struct { element heap[MAX_ELE..
선형 자료 구조 (linear data structure) : 리스트, 스택, 큐, ... 계층적인 자료 구조 (hierarchical structure) : 트리 , ... 이진 트리의 표현 방법 1. 배열을 이용하는 방법 : 완전 이진 트리임을 가정하고, 노드번호에 따라서 배열에 할당, 이때 인덱스 0은 편의를 위해서 비움. 단점 : 완전 이진 트리가 아닐 경우 메모리 낭비가 심함. 2. 포인터를 이용하는 방법 (링크 표현법) :[ [left link][data][right link] ] 와 같은 형태. 각 링크 필드는 왼쪽/오른쪽 자식 필드와 연결 // 링크법으로 생성된 이진 트리 // 링크법으로 생성된 이진트리 #include #include #include typedef struct TreeNo..
// 원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 것 // 장점 : 하나의 노드에서 다른 모든 노드로의 접근이 가능 // 원형 연결 리스트 테스트 프로그램 #include #include typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; // 원형 연결 리스트 처음에 삽입하는 함수 ListNode* insert_first(ListNode* head, element data) { // 노드에 동적 메모리 할당 ListNode *node = (ListNode *)malloc(sizeof(ListNode)); node->data = data; if (head == NULL)..
// 배열로 리스트 구현하기 // 배열로 구현한 리스트 #include #include #define MAX_LIST_SIZE 100 typedef int element; // 리스트 요소 선언 typedef struct { element array[MAX_LIST_SIZE]; // 배열 선언 int size; // 리스트 크기 } ArrayListType; // 오류처리 함수 void error(char *message) { fprintf(stderr, "%s\n", message); exit(1); } // 리스트 초기화 함수 void init(ArrayListType *L) { L->size = 0; } // 리스트 공백 상태 함수 , 리스트가 비어있다면 1을 반환 , 그렇지 않다면 0을 반환 in..
