언제나 휴일

7.5 진입 차수, 진출 차수이번에는 그래프에서 중요하게 생각하는 특징 중에 진입 차수와 진출 차수를 알아보아요. 특정 점정으로 갈 수 있는 간선의 수를 해당 정점의 진입차수(In degree)라고 불러요. 그리고 특정 정점에서 갈 수 있는 간선의 수를 진출차수(Out degree)라고 부르죠. 이번에는 그래프의 이와 같은 정보를 확인하는 기능을 구현해 보아요. 그래프 구현은 앞에서 소개한 것을 참고하세요. 이번에 추가할 기능은 진입 차수와 진출 차수를 확인하는 기능이예요. void ViewIndegree(Graph *g);//진입차수 확인 void ViewOutdegree(Graph *g);//진출차수 확인 먼저 진입 차수를 구하는 기능을 작성하기로 해요. 진입 차수는 상대 정점에서 자신의 정점으로 올..

7.3 인접 행렬로 방향성 있는그래프방향성 있는 그래프는 간선의 출발지와 목적지가 정해져 있는 그래프를 말해요. 방향성 있는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 먼저 그래프 형식을 정의하기로 해요. 그래프 형식은 방향성 없는 그래프와 차이가 없어요. 정점의 개수와 인접 행렬을 멤버를 추가하세요. typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 } Graph; 그래프를 생성하고 소멸, 추가, 정보 출력하는 기능을 제공하기로 해요. Graph *NewGraph(int max_vertex);//그래프 동적 생성 void DeleteGraph(Graph *graph);//그래프 소멸 void AddE..

[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언어 자료구조] 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 스택 구현 스택 구현은 큐 구현과 매우 흡사합니다. 먼저 동적으로 스택을 생성하는 함수와 소멸하는 함수는 큐 구현처럼 래퍼 함수로 구현합니다. 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 스택 설계 스택도 연결리스트를 래핑하여 만들게요. 연결리스트 형식을 스택 형식으로 타입 재지정합니다. #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);

[C언어 자료구조] 5. 스택(Stack) 스택은 큐와 달리 가장 최근에 보관한 자료를 먼저 꺼내는 후입선출(LIFO, Last In First Out)형태로 동작하는 자료구조입니다. 스택은 배열이나 연결리스트로 구현할 수 있어요. 여기에서는 배열로 구현하는 것을 먼저 해 본 후에 미리 만든 연결리스트를 래핑하는 방법을 살펴보아요. 먼저 스택 구조체를 정의하세요. 스택에는 저장소와 가장 최근에 보관한 위치를 멤버로 갖고 있어야 해요. #define STACK_SIZE 10 typedef struct Stack //Stack 구조체 정의 { int buf[STACK_SIZE];//저장소 int top; //가장 최근에 보관한 인덱스 }Stack; 스택에는 보관하는 동작을 Push라 부르고 꺼내는 동작을 P..

[C언어 자료구조] 4.3 큐 테스트 큐를 테스트하는 코드를 작성합시다. int main() { EHQueue *ehq = 0; Book *book = 0; 먼저 동적으로 큐를 생성합니다. ehq = New_EHQueue(); 그리고 큐에 자료를 보관합니다. EHQueue_Put(ehq,New_Book("C언어","홍길동",10)); EHQueue_Put(ehq,New_Book("C++언어","강감찬",20)); EHQueue_Put(ehq,New_Book("자료구조","김구",5)); 이 상태에서 꺼내면 가장 먼저 보관한 "C언어" 제목의 도서여야 합니다. 이를 확인해 봅시다. book = (Book *)EHQueue_Get(ehq); if(book) { Book_View(book); Delete_Bo..

[C언어 자료구조] 4.2 큐 구현 먼저 동적으로 큐를 생성하는 함수를 작성합시다. EHQueue *New_EHQueue() { 여기서 설계한 큐는 연결 리스트이므로 연결리스트를 동적으로 생성하여 반환합니다. 이처럼 이미 작성한 기능을 이용하여 전달하는 역할만 하는 함수를 래퍼(Wrapper) 함수라고 부릅니다. return New_LinkedList(); } 동적으로 생성한 큐를 소멸하는 함수도 래퍼 함수로 작성합니다. void Delete_EHQueue(EHQueue *ehq) { Delete_LinkedList(ehq); } 큐에 자료를 보관하는 함수도 연결리스트에 순차 보관하는 함수를 호출하는 래퍼 함수로 작성합니다. void EHQueue_Put(EHQueue *ehq, Element data)..

[C언어 자료구조] 4.1 큐 설계 여기에서는 연결리스트를 큐로 감싸(Wrapping)하여 선입선출(FIFO, First In First Out)방식으로 자료를 보관 및 꺼내기 동작을 제공하도록 설계할게요. #include "LinkedList.h" typedef LinkedList EHQueue; 큐를 설계할 때 내부에 자료를 보관하는 저장소를 배열로 만드는 방법도 있는데 이미 만들어진 연결리스트를 이용하여 자료를 보관하게 정의하면 저장소의 한계가 없는 큐를 만들 수 있습니다. 물론 메모리의 한계까지 없는 것은 아닙니다. 일반적으로 대학에서 배우는 큐는 자료를 보관하는 저장소를 정적 크기의 배열로 정의하는 큐를 배우고 꽉 찼을 때의 처리에 관한 고민을 합니다. 특히 이 문제를 원형 큐 형태로 만들어 문..