Programming/DS SorceCode 썸네일형 리스트형 랜덤 함수를 이용한 함수, 배열을 출력하는 함수 // 랜덤 함수를 이용하여 int 배열을 0~max-1 의 값으로 무작위로 채우는 함수static void initRandom(int list[], int n, int max = 100) {for (int i = 0; i < n; i++)list[i] = rand() % max;} // 배열을 화면에 보기 좋게 출력하는 함수. 디폴트 매개변수 사용static void printArray(int arr[], int n, const char *str = "Array") {printf("%s = ", str);for (int i = 0; i < n; i++)printf("%3d", arr[i]);printf("\n");} 더보기 선택정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 //두 정수를 교환하는 함수 : inline 함수. 매개변수로 레퍼런스형 사용.inline void swap(int& x, int& y) {int t = x;x = y;y = t;} //선택정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수void selectionSort(int A[], int n) {for (int i = 0; i < n - 1; i++) {// n-1번만 반복int least = i;for (int j = i + 1; j < n; j++)//최솟값 탐색if (A[j] < A[least]) least = j;swap(A[i], A[least]);}} 더보기 WGraphFloyd.h : Floyd 알고리즘의 최단 경로 탐색 기능이 추가된 그래프 #pragma once#ifndef ___WGraphFloyd#define ___WGraphFloyd//WGraphFloyd.h : Floyd 알고리즘의 최단 경로 탐색 기능이 추가된 그래프#include "WGraph.h"class WGraphFloyd : public WGraph{int A[MAX_VTXS][MAX_VTXS];// 최단 경로 거리public:void ShortestPathFloyd() {for (int i = 0; i < size; i++)for (int j = 0; j < size; j++)A[i][j] = getEdge(i, j); for (int k = 0; k < size; k++) {for (int i = 0; i < size; i++)for (int j = 0; j < si.. 더보기 WGraphDijkstra.h : Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프 #pragma once#ifndef ___WGraphDijkstra#define ___WGraphDijkstra//WGraphDijkstra.h : Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프#include "WGraph.h" class WGraphDijkstra : public WGraph {int dist[MAX_VTXS];// 시작노드로부터의 최단경로 거리bool found[MAX_VTXS];// 방문한 정점 표시public://방문하지 않은 정점들 중에서 최단경로 거리가 가장 작은 정점을 찾아 반환int chooseVertex() {int min = INF;int minpos = -1;for(int i=0;i 더보기 WGraphMST.h : 최소 신장 트리(MST) 기능이 추가된 가중치 그래프 클래스 #pragma once#ifndef ___WGraphMST#define ___WGraphMST//WGraphMST.h : 최소 신장 트리(MST) 기능이 추가된 가중치 그래프 클래스#include "MinHeap.h"#include "WGraph.h"#include "VertexSets.h" class WGraphMST : public WGraph {public :void Kruskal() {// kruskal 의 최소 비용 신장 트리 프로그램MinHeap heap;// 힙에 모든 간선 삽입for (int i = 0; i < size; i++)for (int j = i + 1; j < size; j++)if (hasEdge(i, j))heap.insert(getEdge(i, j), i, j); Verte.. 더보기 MInHeap.h : 최소 힙 클래스 + Kruskal 알고리즘 구현을 위한 함수 추가 ... // 코드 동일 void insert(int key, int u, int v) {if (isFull()) return;int i = ++size;while (i != 1 && key < getParent(i).getKey()) {node[i] = getParent(i);i /= 2;}node[i].setKey(key, u, v);} ... // 코드 동일 더보기 HeapNode : 힙에 저장할 노드 클래스 / Kruskal의 최소 비용 신장 트리 프로그램을 위한 노드 클래스 #pragma once#ifndef ___HeapNode#define ___HeapNode//HeapNode : 힙에 저장할 노드 클래스//Kruskal의 최소 비용 신장 트리 프로그램을 위한 노드 클래스#include class HeapNode {int key;//key값int v1;//정점 1int v2;//정점 2public:HeapNode(int k = 0) : key(k) {}HeapNode(int k, int u, int v) : key(k), v1(u), v2(v) {}void setKey(int k) { key = k; }void setKey(int k, int u, int v) { key = k; v1 = u; v2 = v; }int getKey() { return key; }int ge.. 더보기 VertexSet.h : Union-Find 연산을 위한 정점 집합 클래스 구현 #pragma once#ifndef ___VertexSets#define ___VertexSets//VertexSet.h : Union-Find 연산을 위한 정점 집합 클래스 구현#define MAX_VTXS 256class VertexSets {int parent[MAX_VTXS];//부모 정점의 idint nSets;//집합의 개수public:VertexSets(int n) : nSets(n) {for (int i = 0; i < nSets; i++)parent[i] = -1;//모든 정점이 고유의 집합에 속함}bool isRoot(int i) { return parent[i] < 0; }int findSet(int v) {while (!isRoot(v)) v = parent[v];return v;}.. 더보기 이전 1 2 3 4 5 6 ··· 8 다음