반응형

자료구조 53

[C언어 자료구조] 7.1 인접 행렬로 방향성 없는그래프

7.1 인접 행렬로 방향성 없는그래프방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요. 방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠. 먼저 그래프 형식을 정의하기로 해요. 인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠. typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 }Graph; 여기에서는 그래프 생성, 소멸, 간선 추가, 이웃 정점을 보여주는 기능을 제공하기로 해요. Graph *M..

[C언어 자료구조] 7. 그래프(Graph)

7. 그래프(Graph)이번에는 그래프를 알아보기로 해요. 그래프는 정점과 간선으로 구성하는 자료구조예요. 그래프를 표현하는 방법은 여러가지가 있어요. 여기에서는 인접 행렬을 이용하는 방법과 연결리스트를 이용하는 방법을 알아볼게요.[C언어 자료구조] 7.1 인접 행렬로 방향성 없는그래프[C언어 자료구조] 7.2 인접 행렬로 방향성 없는그래프 소스 코드[C언어 자료구조] 7.3 인접 행렬로 방향성 있는그래프[C언어 자료구조] 7.4 인접 행렬로 방향성 있는 그래프 소스 코드[C언어 자료구조] 7.5 진입 차수, 진출 차수[C언어 자료구조] 7.6 진입 차수, 진출 차수 소스 코드

[C언어 자료구조] 6.3 이진 탐색 트리 소스 코드

[C언어 자료구조] 6.3 이진 탐색 트리 소스 코드 테스트 로직을 구현합시다. 테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다. 이 부분에 관한 별도의 설명은 생략할게요. //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LE..

[C언어 자료구조] 6.2 이진 탐색 트리 구현

[C언어 자료구조] 6.2 이진 탐색 트리 구현 동적으로 노드를 생성하는 함수를 구현합시다. 여기에서는 Node 형식 크기의 메모리를 할당받은 후 입력 인자로 받은 도서 정보를 설정하고 나머지 멤버는 0으로 초기화합니다. Node *New_Node(Book *data) { Node *node = 0; node = (Node *)malloc(sizeof(Node)); node->book = data; node->lch = node->rch = node->pa = 0; return node; } 동적으로 이진 탐색 트리를 생성하는 함수를 구현합시다. 생성할 때 root는 비어있는 상태이고 보관하고 있는 도서 개수는 0입니다. BST *New_BST() { BST *bst = 0; bst = (BST *)ma..

[C언어 자료구조] 6.1 이진 탐색 트리 설계

[C언어 자료구조] 6.1 이진 탐색 트리 설계 이제 이진 탐색 트리를 설계합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요. 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다. typedef struct _Node Node; struct _Node { Book *book; Node *lch; Node *rch; Node *pa; }; Node *New_Node(Book *data); 이진 탐색 트리에는 root 노드..

[C언어 자료구조] 6. 이진 탐색 트리(Binary Search Tree)

[C언어 자료구조] 6. 이진 탐색 트리(Binary Search Tree) 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리는 노드와 서브 트리의 집합으로 서브 트리도 이진 탐색 트리입니다. 그리고 부모 노드는 두 개의 자식 노드를 가질 수 있고 왼쪽 서브 트리에는 부모보다 작은 값들이 오른쪽 서브 트리에는 부모보다 큰 값들이 있습니다. [그림 6.1] 이진 탐색 트리 이진 탐색 트리에서 데이터를 추가하거나 검색할 때 재귀적인 방법으로 찾을 수 있습니다. 검색 (key:키, sroot: 서브 트리의 루트노드) rkey:= sroot.key gap: = rkey - key 조건(gap IsEqual 0) sr..

[C언어 자료구조] 5.4 스택 소스 코드

[C언어 자료구조] 5.4 스택 소스 코드//common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LEN 20 typedef struct _Book Book; struct _Book { char title[MAX_TIT_LEN+1]; char author[MAX_AUT_LEN+1]; int num; }; Book *New_Book..

[C언어 자료구조] 5.3 스택 테스트

[C언어 자료구조] 5.3 스택 테스트 스택을 테스트하는 코드를 작성합시다. int main() { EHStack *ehs = 0; Book *book = 0; 먼저 스택을 동적으로 생성합니다. ehs = New_EHStack(); 적당히 자료를 스택에 보관합니다. 여기에서는 세 개의 도서를 보관할게요. EHStack_Push(ehs,New_Book("C언어","홍길동",10)); EHStack_Push(ehs,New_Book("C++언어","강감찬",20)); EHStack_Push(ehs,New_Book("자료구조","김구",5)); 이제 하나의 자료를 꺼내어 봅시다. 가장 최근에 보관한 자료는 "자료구조"입니다. book = (Book *)EHStack_Pop(ehs); if(book) { Book..

[C언어 자료구조] 5.2 스택 구현

[C언어 자료구조] 5.2 스택 구현 스택 구현은 큐 구현과 매우 흡사합니다. 먼저 동적으로 스택을 생성하는 함수와 소멸하는 함수는 큐 구현처럼 래퍼 함수로 구현합니다. EHStack *New_EHStack() { return New_LinkedList(); } void Delete_EHStack(EHStack *ehs) { Delete_LinkedList(ehs); } 스택에 자료를 보관하는 함수도 연결리스트에 순차 보관하는 함수를 호출하는 래퍼 함수입니다. void EHStack_Push(EHStack *ehs, Element data) { LinkedList_PushBack(ehs,data); } 스택에서 가장 최근에 보관한 자료를 꺼내는 함수를 작성합시다. 이 부분이 큐와 차이가 있는 부분입니다...

[C언어 자료구조] 5.1 스택 설계

[C언어 자료구조] 5.1 스택 설계 스택도 연결리스트를 래핑하여 만들게요. 연결리스트 형식을 스택 형식으로 타입 재지정합니다. #include "LinkedList.h" typedef LinkedList EHStack; 동적으로 스택을 생성하는 함수와 소멸하는 함수를 제공합시다. EHStack *New_EHStack(); void Delete_EHStack(EHStack *ehs); 스택에 자료를 보관하는 함수와 꺼내는 함수를 제공합시다. void EHStack_Push(EHStack *ehs, Element data); Element EHStack_Pop(EHStack *ehs); 스택이 빈 상태인지 확인하는 함수도 제공합시다. int EHStack_IsEmpty(EHStack *ehs);

반응형