C++/Fundamentals of Data Structures in C++(Horowitz) 47

C++ Fundamentals of Data Structures(C++ 자료구조론) 7.2 QuickSort(퀵 정렬) 예제

/* Quick Sort 퀵 소트 */ #include #include using namespace std; //재귀 퀵소트 template void QuickSort(T *a, const int left, const int right) { //a[left:right]를 오름차순으로 정렬 //a[left]는 pivot이다. if (left < right) { int i = left, j = right + 1, pivot = a[left]; do { do { i++; } while (a[i] < pivot); do { j--; } while (a[j] > pivot); if (i < j) swap(a[i], a[j]); } while (i < j); swap(a[left], a[j]); QuickSort(..

C++ Fundamentals of Data Structures(C++ 자료구조론) 7.2 InsertionSort(삽입정렬) 예제+Exercises

[삽입정렬 예제]/*Insertion Sort Example삽입 정렬 예시*/#include using namespace std; /*Insertion into a sorted list*/template void Insert(const T &e, T *a, int i){ a[0] = e; while (e < a[i]) { a[i + 1] = a[i]; i--; } a[i + 1] = e;} /*Insertion Sort*/template void InsertionSort(T *a, const int n){ for (int j = 2; j < n; j++) { T temp = a[j]; Insert(temp, a, j - 1); }} int main(void){ //책의 간단한 예시를 참고한 코드 int ..

C++ Fundamentals of Data Structures(C++ 자료구조론) 7.1 Sorting(정렬) 예제

/*Fast Verifications of two lists리스트끼리의 비교(빠른 버젼)*/#include #include #include using namespace std; //순차적 탐색/*template int SeqSearch(E *a, const int n, const K &k){ int i; for (i = 1; i n) return 0; return i;}*/ //Verify2와 동일한 역할을 하는 함수/*void Verify1(Element *l1, Element *l2, const int n, const int m){ bool *marked = new bool[m + 1]; fill(marked + 1, marked + m + 1, false); for (i = 1; i

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.5 TopologicalOrder(위상정렬) 예제

/*AOV Topological, 위상정렬*/#include #include #include using namespace std; class Graph{ int vertices; //정점의 개수 list *adj; void topologicalSortUtil(int v, bool visited[], stack &Stack)//위상정렬에서 쓰이는 함수 { visited[v] = true; //현재 노드를 방문했다고 표시 //정점에 연결되어있는 모든 정점에 대해 재귀 list::iterator i; for (i = adj[v].begin(); i != adj[v].end(); i++) if (!visited[*i]) topologicalSortUtil(*i, visited, Stack); Stack.push..

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.4 Shortest Paths(최단 거리) 예제

#include #include // printf의 %-10s 같이 동일한 간격 출력 위해#include #include using namespace std; class MatrixWDigraph{private: string cityName[8]; int length[8][8]; //인접 도시와의 비용 int dist[8]; //시작 정점에서의 최단 경로 bool s[8]; //최단 경로를 찾으면 s[i]는 true //갱신된 정점의 비용 출력 void displayValues(int u) { char before; cout

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.3 Prim's Algorithm 예제

/*Prim's Algorithm, 프림 알고리즘*/#include using namespace std; class Prim{private: typedef struct _graph { int v1; //정점 1 int v2; //정점 2 int weight; //가중치 }Graph; Graph g[20]; int total_edges, total_vertexes; //전체 간선, 정점 int visited[20]; //방문했는가 int temp[20]; //임시로 g[i].weight를 저장하여 min을 찾게 도와주는 배열public: Prim() { //Default } void Initialize() { cout > g[i].v1 >> g[i].v2; cout > g[i].weight; } for (..

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.3 Kruskal's Algorithm 예제

/*Kruskal's Algorithm using disjoint set집합을 이용한 크루스칼 알고리즘*/#include using namespace std; int Find(int v2, int parent[]) //최종부모 찾기{ while (parent[v2] != v2) { v2 = parent[v2]; } return v2;} void Union(int i, int j, int parent[]) //집합{ if (i < j) parent[j] = i; //j의 부모는 i else parent[i] = j; //i의 부모는 j} class Kruskal{private: typedef struct _graph { int v1; //정점 1 int v2; //정점 2 int weight; //가중치 ..

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.2 Elementary Graph Operations(기본적인 그래프 연산들) 예제

/*Elementary Graph Operations, 기본적인 그래프 연산들(DFS, BFS, Components, DfnLow)*/#include #include //BFS 위해using namespace std; class Chain;class ChainIterator; class ChainNode{private: int data; ChainNode *link;public: ChainNode(int num) :data(num) { link = NULL; } friend Chain; friend ChainIterator;}; class Chain{private: ChainNode *first;public: Chain() { first = NULL; } void Insert(int num) { Chai..

C++ Fundamentals of Data Structures(C++ 자료구조론) 6.1 AdjacencyList Graph(인접리스트 그래프) 예제

/*간단한 인접리스트 그래프, Simple AdjacencyList Graph*/#include using namespace std; class ChainNode{private: int data; ChainNode *link;public: ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next) { } int getData() { return data; } ChainNode *Link() { return link; } friend class AdjList; friend class LinkedGraph; friend ostream &operator

C++ Fundamentals of Data Structures(C++ 자료구조론) 5.10 DisjointSets(집합) 예제

/*DisjointSets, 집합수정날짜:9/8*/#include using namespace std; class Sets{private: int *parent; int n; //집합의 요소 수public: Sets(int size = 10) { n = size; parent = new int[size + 1]; //[0]은 사용하지 않는다 for (int i = 1; i parent[j]) //i가 더 적은 노드를 갖고 있을 때(음수이므로 이렇게 계산) { parent[i] = j; parent[j] = temp; } else { parent[j] = i; parent[j] = temp; } } int CollapsingFind(int i) //i를 포함하는 집합의 루트를 찾는다(SimpleFind의 ..