전체 글 썸네일형 리스트형 SrchALGraph.h ; 탐색 기능이 추가된 인접 리스트 기반 그래프 클래스 #pragma once#ifndef ___SrchALGraph#define ___SrchALGraph//SrchALGraph.h ; 탐색 기능이 추가된 인접 리스트 기반 그래프 클래스#include "AdjListGraph.h"#include "CircularQueue.h" class SrchALGraph : public AdjListGraph {bool visited[MAX_VTXS];//정점의 방문 정보public:void resetVisited() {//모든 정점을 방문하지 않았다고 설정for (int i = 0; i .. 더보기 SrchAMGraph : 탐색 기능이 추가된 행렬 기반 그래프 클래스 #pragma once#ifndef ___SrchAMGragh#define ___SrchAMGraph//SrchAMGraph : 탐색 기능이 추가된 행렬 기반 그래프 클래스#include "AdjMatGraph.h"#include "CircularQueue.h"class SrchAMGraph : public AdjMatGrapgh {bool visited[MAX_VTXS];//정점의 방문 정보public:void resetVisited() {//모든 정점을 방문하지 않았다고 설정for (int i = 0; i < size; i++)visited[i] = false;}bool isLinked(int u, int v) { return getEdge(u, v) != 0; } //깊이 우선 탐색 함수void D.. 더보기 AdjListGraph.h : 인접 리스트를 이용한 그래프 클래스 #pragma once#ifndef ___AdjListGraph#define ___AdjListGraph//AdjListGraph.h : 인접 리스트를 이용한 그래프 클래스#include "Node_Adj.h"//연결 리스트를 위한 노드 그래프 클래스 포함#define MAX_VTXS256class AdjListGraph {protected:int size;//정점의 개수char vertices[MAX_VTXS];//정점 정보(응용에 따라 확장 필요)Node* adj[MAX_VTXS];//각 정점의 인접 리스트public:AdjListGraph() : size(0) {}~AdjListGraph() { reset(); }void reset(void) {for (int i = 0; i < size; i++).. 더보기 Node.h : 인접 리스트를 이용한 그래프를 위한 노드 클래스 #pragma once#ifndef ___Node_Adj#define ___Node_Adj//Node.h : 인접 리스트를 이용한 그래프를 위한 노드 클래스#include class Node {protected:int id;//정점의 idNode* link;//다음 노드의 포인터public:Node(int i, Node* l=NULL) : id(i), link(l){}~Node() { if (link != NULL) delete link; }int getId() { return id; }Node* getLink() { return link; }void setLink(Node* l) { link = l; }}; #endif // !___Node_Adj 더보기 AdjMatGraph.h : 인접 행렬을 위한 그래프 클래스 #pragma once#ifndef ___AdjMatGraph#define ___AdjMatGraph//AdjMatGraph.h : 인접 행렬을 위한 그래프 클래스#include #define MAX_VTXS 256//표현 가능한 최대 정점의 개수 class AdjMatGrapgh {protected:int size;//정점의 개수char vertices[MAX_VTXS];//정점의 이름int adj[MAX_VTXS][MAX_VTXS];//인접 행렬public:AdjMatGrapgh() { reset(); }char getVertex(int i) { return vertices[i]; }int getEdge(int i, int j) { return adj[i][j]; }void setEdge(int i,.. 더보기 MaxHeap.h : 배열을 이용한 최대 힙 클래스 #pragma once#ifndef ___MaxHeap#define ___MazHeap//MaxHeap.h : 배열을 이용한 최대 힙 클래스#include "HeapNode.h"#define MAX_ELEMENT 200class MaxHeap {HeapNode node[MAX_ELEMENT];//요소의 배열int size;//힙의 현재 요소의 개수public:MaxHeap() : size(0) {}bool isEmpty() { return size == 0; }bool isFull() { return size == MAX_ELEMENT - 1; } HeapNode& getParent(int i) { return node[i / 2]; }HeapNode& getLeft(int i) { return node.. 더보기 HeapNode : 힙에 저장할 노드 클래스 #pragma once#ifndef ___HeapNode#define ___HeapNode//HeapNode : 힙에 저장할 노드 클래스#include class HeapNode {int key;//key값public:HeapNode(int k = 0) : key(k) {}void setKey(int k) { key = k; }int getKey() { return key; }void display() { printf("%4d", key); }};#endif // !___HeapNode 더보기 DataStructure - 힙(heap) 힙 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말한다.힙(heap)은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 힙은 일종의 반 정렬 상태를 유지한다. 즉, 요소들이 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 것도 아닌 상태를 이용해 우선순위 큐를 구현한다. 힙의 시간 복잡도는 삽입과 삭제 모두 으로 다른 방법보다 상당히 유리하다. 여기서 다시 한 번 과 은 큰 차이가 있다는 것을 유념해야 한다. 만약 n 이 1024이고 알고리즘이 1024초가 걸린다면 알고리즘은 10초에 불과하다.표현 방법 삽입 삭제 순서 없는 배열 순서 없는 연결 리스트 정렬된 배열 정렬된 열결 리스트 힙 더보기 이전 1 ··· 15 16 17 18 19 20 21 ··· 39 다음