<repo_name>paparoni95/DataStructure<file_sep>/Doit/Array/chap02-8.cpp
/* 정수를 2진수 ~ 36진수로 기수 변환 */
#include <stdio.h>

/* 정수 값 x를 n진수로 변환하여 배열d에 아랫자리부터 저장 */
int card_convr(unsigned x, int n, char d[])
{
	char dchar[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int digits = 0;
	if (x == 0)
		d[digits++] = dchar[0];
	else
	{
		while (x)
		{
			d[digits++] = dchar[x % n];
			x /= n;
		}
	}
	return digits;
}

int main()
{
	int i;
	unsigned no;   // 변환하는 정수
	int cd;        // 기수
	int dno;       // 변환 후 자릿수
	char cno[512]; // 변환한 값의 각 자리의 숫자를 저장하는 문자 배열
	int retry;
	puts("10진수를 기수 변환");
	do
	{
		printf("변환하는 음이 아닌 정수 : ");
		scanf_s("%u", &no);
		do
		{
			printf("어떤 진수로 변환할까?(2-36) : ");
			scanf_s("%d", &cd);
			dno = card_convr(no, cd, cno); // no를 cd진수로 변환
			printf("%d진수로는", cd);
			for (i = dno - 1; i >= 0; --i)
				printf("%c", cno[i]);
			printf("입니다.\n");
			printf("한 번 더 할까요?(1 ... 예/0 ... 아니오) : ");
			scanf_s("%d", &retry);
		} while (cd < 2 || cd > 36);
	} while (retry == 1);
	return 0;
}<file_sep>/열혈자료구조/Tree/ListBaseTree/BinaryTree.h
#pragma once

typedef int BTData;

typedef struct _bTreeNode {
	BTData data;
	struct _bTreeNode* left;
	struct _bTreeNode* right;
}BTreeNode;

BTreeNode* MakeBTreeNode(void);                         // 이진 트리 생성 및 주소 값을 반환
BTData GetData(BTreeNode* bt);                          // 노드에 저장된 데이터를 반환
void SetData(BTreeNode* bt, BTData data);               // 노드에 데이터를 저장

BTreeNode* GetLeftSubTree(BTreeNode* bt);               // 왼쪽 서브 트리의 주소 값을 반환
BTreeNode* GetRightSubTree(BTreeNode* bt);              // 오른쪽 서브 트리의 주소 값을 반환

void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub);  // 왼쪽 서브 트리를 연결
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub); // 오른쪽 서브 트리를 연결<file_sep>/Doit/List/SingleLinkedList/LinkedList.h
#ifndef ___LinkedList
#define ___LinkedList

#include "Member.h"

typedef struct
{
	Member data;
	struct __node* next;
}Node;

typedef struct
{
	Node* head; // 머리 노드에 대한 포인터
	Node* crnt; // 선택한 노드에 대한 포인터
}List;

void Initialize(List* list);
// 함수 compare로 x와 같은 노드를 검색
Node* search(List* list, const Member* x, int compare(const Member* x, const Member* y));
void InsertFront(List* list, const Member* x);
void InsertRear(List* list, const Member* x);
void RemoveFront(List* list);
void RemoveRear(List* list);
void RemoveCurrent(List* list);
// 모든 노드 삭제
void Clear(List* list);
// 선택한 노드의 데이터 출력
void PrintCurrent(const List* list);
void PrintLnCurrent(const List* list);
// 모든 노드의 데이터를 리스트 순서대로 출력
void Print(const List* list);
// 연결 리스트 종료
void Terminate(List* list);
#endif<file_sep>/Doit/Array/chap02-10.cpp
/* 1000 이하의 소수를 나열한다. */
#include <stdio.h>

int main()
{
	int i, n;
	int prime[500];
	int ptr = 0;
	unsigned long counter = 0;
	prime[ptr++] = 2;
	for (n = 3; n <= 1000; n += 2) // 홀수만 대상으로
	{
		for (i = 1; i < ptr; ++i)
		{
			++counter;
			if (n % prime[i] == 0)
				break;
		}

		if (ptr == i)
			prime[ptr++] = n;
	}
	for (i = 0; i < ptr; ++i)
		printf("%d\n", prime[i]);
	printf("나눗셈을 실행한 횟수 : %d\n", counter);
	return 0;
}
<file_sep>/Doit/Hash/OpenAddressing/ClosedHash.h
// 오픈 주소법으로 구현한 해시
#ifndef ___ClosedHash
#define ___ClosedHash

#include "Member.h"

typedef enum
{
	Occupied, Empty, Deleted
}Status;

typedef struct
{
	Member data; // 데이터
	Status stat; // 요소의 상태
}Bucket;

typedef struct
{
	int size;
	Bucket* table;
}ClosedHash;

int Initialize(ClosedHash* h, int size);

Bucket* Search(const ClosedHash* h, const Member* x);

int Add(ClosedHash* h, const Member* x);

int Remove(ClosedHash* h, const Member* x);

void Dump(const ClosedHash* h);

void Clear(ClosedHash* h);

void Terminate(ClosedHash* h);
#endif<file_sep>/Doit/Recursive/queen_b.c
/* 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열 */
#include <stdio.h>

int pos[8];
int counter;

void print()
{
	int i;
	for (i = 0; i < 8; ++i)
		printf("%2d", pos[i]);
	putchar('\n');
}

void set(int i)
{
	int j;
	// 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 = 16,777,216 가지
	for (j = 0; j < 8; ++j)
	{
		pos[i] = j;
		if (i == 7)
		{
			print();
			++counter;
		}
			
		else
			set(i + 1);
	}
}

int main()
{
	set(0);
	printf("출력횟수 : %d\n", counter); // 16,777,216가지
	return 0;
}<file_sep>/Doit/Sorting/bubble3.c
/* 버블 정렬 */
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do {type t = x; x = y; y = t;}while(0)

int counter;

// 비교, 교환을 하다가 어떤 시점 이후에 교환이 없다면,
// 그보다 앞쪽의 요소는 이미 정렬을 마친 상태
void bubble(int a[], int n)
{
	int k = 0; // a[k]보다 앞쪽의 요소는 정렬을 마친 상태
	while (k < n - 1)
	{
		++counter;
		int j;
		int last = n - 1; // 마지막으로 교환을 수행한 위치를 저장한다.
		for (j = n - 1; j > k; --j)
		{
			if (a[j - 1] > a[j])
			{
				swap(int, a[j - 1], a[j]);
				last = j;
			}
		}
		k = last;
	}
}

int main()
{
	int i, nx;
	int* x;

	puts("버블 정렬");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));

	for (i = 0; i < nx; ++i)
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]);
	}

	bubble(x, nx);

	puts("오름차순으로 정렬한 결과");
	for (i = 0; i < nx; ++i)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);

	printf("성능 척도 : %d\n", counter);
	return 0;
}<file_sep>/열혈자료구조/Graph/DFS/ArrayBaseStack.h
#pragma once

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

// 배열 기반 스택 구현

typedef int Data;

typedef struct _arrayStack {
	Data stackArr[STACK_LEN];
	int topIndex;
}ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack* pstack);         // 스택의 초기화
int SIsEmpty(Stack* pstack);           // 스택이 비어있는지 확인

void SPush(Stack* pstack, Data data);  // 스택의 push 연산
Data SPop(Stack* pstack);              // 스택의 pop 연산
Data SPeek(Stack* pstack);             // 스택의 peek 연산
<file_sep>/열혈자료구조/Search/BinarySearch/BinarySearch.c
#include <stdio.h>

//이진 탐색
//조건, 데이터가 정렬되어있어야 한다.
//시간복잡도 O(logN)
int BSearch(int ar[], int len, int target) {
	int first = 0;
	int last = len - 1;
	int mid;

	while (first <= last) {
		mid = (first + last) / 2;

		if (target == ar[mid]) {
			return mid;
		}
		else {
			if (target < ar[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}
	}
	return -1;
}

int main() {
	int arr[] = { 1,3,5,7,9 };
	int idx;

	idx = BSearch(arr, sizeof(arr) / sizeof(int), 7);
	if (idx == -1)
		printf("탐색 실패\n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);
	return 0;
}<file_sep>/열혈자료구조/ArrayList/ArrayList.h
#pragma once
//#include "Point.h"
#include "NameCard.h"
#define TRUE 1
#define FALSE 0

#define LIST_LEN 100
//typedef int LData;
//typedef Point * LData;
typedef NameCard * LData;

typedef struct __ArrayList {  //배열기반 리스트를 정의한 구조체
	LData arr[LIST_LEN];  //리스트의 저장소인 배열
	int numOfData;        //저장된 데이터의 수
	int curPosition;      //데이터 참조위치를 기록
}ArrayList;

typedef ArrayList List;

void ListInit(List * plist); //초기화
void LInsert(List * plist, LData data); //데이터 저장

int LFirst(List * plist, LData * pdata);//첫 데이터 참조
int LNext(List * plist, LData * pdata); //두 번째 이후 데이터 참조

LData LRemove(List * plist); //참조한 데이터 삭제
int LCount(List * plist);    //저장된 데이터의 수 반환
<file_sep>/Doit/String/Boyer-Moore.cpp
// 참고 : https://greatzzo.tistory.com/8?category=662568
#include <stdio.h>
#include <string.h>
// Boyer-Moore 알고리즘의 
// Bad Character Heuristic의 예시

/*
1. 패턴의 현재 비교 문자와 일치하지 않는 텍스트의 문자를 bad character라고 부른다.
   이런 bad character가 등장하면 패턴에서 이 bad character가 마지막으로 등장했던 위치로 패턴을 이동시킨다.

2. 전처리 과정에서 256의 배열을 만들고 패턴에 등장한 모든 문자의 마지막 위치를 저장한다.

3. 만약 전혀 나타나지 않는 어떤 문자를 만난다면 패턴은 패턴의 길이인 m만큼 이동할 수 있다.
   따라서 BM방식의 best case는 O(N/M)이다.
   패턴의 길이만큼 JUMP하므로

4. 하지만 BM의 worst case는 O(NM), 예를 들어서
   txt[] = "AAAAAAAAAAAAAAA"
   pat[] = "AAAAA"라고 하면,
   Bad character가 등장하지 않으니 매번 일일이 다 검사한다.
*/

#define NUM_OF_CHARS 256

int max(int a, int b) { return (a > b) ? a : b; }

// The preprocessing function for Boyer Moore's bad Character heuristic
int* createBC(char* pat, int M)
{
	int* bc = new int[NUM_OF_CHARS];

	// Initialize all occurrences as -1
	// 처음에는 -1로 초기화
	for (int i = 0; i < NUM_OF_CHARS; ++i)
		bc[i] = -1;

	// Fill the actual value of last occurrence of a character
	// 마지막으로 등장한 문자의 실제 값으로 채운다.
	for (int i = 0; i < M - 1; ++i)
		bc[(int)pat[i]] = i;

	for (int i = 65; i < 66; ++i)
		printf("%d\n", bc[i]);

	return bc;
}

void searchBM(char* pat, char* txt)
{
	int N = strlen(txt);
	int M = strlen(pat);
	int* bc = createBC(pat, M);
	int s = 0; // 패턴의 첫 인덱스 위치
	int j = 0; // 패턴의 현재 비교 위치

	// 0 1 2 3 4 5 6 7 8
	// A B A B B B A C A B A A B  [txt]
	// A B A A B                  [pat]
	//                 A B A A B  [pat]
	// s는 N - M = 8까지만 확인해보면 된다.
	// 이 이상 넘어가면 해당 패턴이 txt에 없다는 뜻
	while (s <= (N - M))
	{
		j = M - 1;

		// txt에 해당 pat을 뒤에서 부터 하나씩 비교해가면서 j를 감소시킨다.
		// 일치한다면 계속해서 j가 감소하지만, 일치하지 않는다면 j를 감소하지 않고
		// 빠져나오게 된다.
		while (j >= 0 && pat[j] == txt[s + j])
			j--;

		// 모든 패턴이 txt와 일치했더라면 j는 0보다 작으므로
		if (j < 0)
		{
			// 해당 패턴이 일치하는 첫 번째 인덱스를 출력
			printf("Pattern found at index %d \n", s);

			// Shift the pattern so that the next character in text
			// aligns with the last occurence of it in pattern.
			// 해당 패턴이 일치한 것만 출력하는 것이 아닌, 또 있을 수 있으므로
			// 계속해서 조사해보기 위해 s의 값을 변경해준다.
			// 여기서는 s + M이 txt의 길이를 넘지 않는다면, s + M의 문자를 확인해서
			// 얼만큼 패턴을 넘길지 조사한다음 s의 값을 수정한다.
			s += (s + M < N) ? M - bc[txt[s + M]] : 1;
		}
		else
		{
			// 일치하지 않는 문자가 있을 때,
			// 이 때 bad character인 bc 배열 값을 보고 패턴을 그 만큼 이동시킨다.
			// 예를 들어 j = 3에서 문자가 일치하지 않는다면,
			// bc[txt[s + j]] = 1이므로,
			// j - 1 = 3 - 1 = 2
			// 따라서 해당 패턴을 2칸 이동시켜서 다시 비교한다.
			// 경우에 따라서 음수가 나올 수 있으므로, 이럴 때는 1칸 이동시켜 다시 비교시킨다.
			s += max(1, j - bc[txt[s + j]]);
		}
	}

	delete bc;
}

int main()
{
	//            0123456789
	//char txt[] = "ABABBBACABAAB";
	//char pat[] = "ABAAB";
	//            0123456789
	char txt[] = "AAAAAAAAAA";
	char pat[] = "AAAAA";

	searchBM(pat, txt);

	return 0;
}<file_sep>/열혈자료구조/Graph/BFS/CircularQueue.h
#pragma once

#define TRUE 1
#define FALSE 0

#define QUE_LEN 100
typedef int Data;

// 배열 기반의 원형 큐 구현
// Circular Queue
typedef struct _cQueue {
	int front;  // front 멤버
	int rear;   // rear 멤버
	Data queArr[QUE_LEN];
}CQueue;

typedef CQueue Queue;

void QueueInit(Queue* pq);
int QIsEmpty(Queue* pq);

void Enqueue(Queue* pq, Data data);
Data Dequeue(Queue* pq);
Data QPeek(Queue* pq);<file_sep>/Doit/Array/chap02-6.cpp
/* 배열 요소의 최댓값을 구한다.(값을 난수로 생성) */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// const int a[] = const int* a
// 읽기만 가능하도록
int maxof(const int a[], int n)
{
	int i;
	int max = a[0];
	for (i = 1; i < n; ++i)
		if (a[i] > max) max = a[i];
	return max;
}

int main()
{
	int i;
	int* height;
	int number;
	printf("사람 수 : ");
	scanf_s("%d", &number);
	height = (int*)calloc(number, sizeof(int));
	srand(time(NULL)); // 시간으로 난수의 seed를 초기화
	for (i = 0; i < number; ++i)
	{
		height[i] = 100 + rand() % 90; // 100 + 0 ~ 89 => 100 ~ 189
		printf("height[%d] : %d\n", i, height[i]);
	}
	printf("최댓값은 %d\n", maxof(height, number));
	free(height);
	return 0;
}<file_sep>/열혈자료구조/Tree/AVLTree/AVLRebalance.c
#include <stdio.h>
#include "BinaryTree3.h"

// LL회전
BTreeNode* RotateLL(BTreeNode* bst) {
	BTreeNode* pNode;  // parent node
	BTreeNode* cNode;  // child node

	pNode = bst;
	cNode = GetLeftSubTree(pNode);

	// 실제 LL회전을 담당하는 코드
	ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
	ChangeRightSubTree(cNode, pNode);

	// LL회전으로 인해서 변경된 루트 노드의 주소 값을 반환
	return cNode;
}
// RR회전
BTreeNode* RotateRR(BTreeNode* bst) {
	BTreeNode* pNode;  // parent node
	BTreeNode* cNode;  // child node

	pNode = bst;
	cNode = GetRightSubTree(pNode);

	// 실제 RR회전을 담당하는 코드
	ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
	ChangeLeftSubTree(cNode, pNode);

	// RR회전으로 인해서 변경된 루트 노드의 주소 값을 반환
	return cNode;
}
// RL회전
BTreeNode* RotateRL(BTreeNode* bst) {
	BTreeNode* pNode;  // parent node
	BTreeNode* cNode;  // child node

	pNode = bst;
	cNode = GetRightSubTree(bst);

	// 실제 RL회전을 담당하는 코드
	ChangeRightSubTree(pNode, RotateLL(cNode)); // 부분적 LL회전
	return RotateRR(pNode);

}
// LR회전
BTreeNode* RotateLR(BTreeNode* bst) {
	BTreeNode* pNode; // parent node
	BTreeNode* cNode; // child node

	pNode = bst;
	cNode = GetLeftSubTree(bst);

	// 실제 LR회전을 담당하는 코드
	ChangeLeftSubTree(pNode, RotateRR(cNode)); // 부분적 RR회전
	return RotateLL(pNode);
}
// 트리의 높이를 계산하여 반환
int GetHeight(BTreeNode* bst) {
	int leftH;  // left height
	int rightH; // right height

	if (bst == NULL)
		return 0;

	leftH = GetHeight(GetLeftSubTree(bst));   // 왼쪽 서브 트리 높이 계산
	rightH = GetHeight(GetRightSubTree(bst)); // 오른쪽 서브 트리 높이 계산

	// 큰 값의 높이를 반환한다.
	if (leftH > rightH)
		return leftH + 1;
	else
		return rightH + 1;
}
// 두 서브 트리의 높이의 차를 반환
int GetHeightDiff(BTreeNode* bst) {
	int lsh;  // left sub tree height
	int rsh;  // right sub tree height

	if (bst == NULL)
		return 0;

	lsh = GetHeight(GetLeftSubTree(bst));  // 왼쪽 서브 트리의 높이
	rsh = GetHeight(GetRightSubTree(bst)); // 오른쪽 서브 트리의 높이
	return lsh - rsh; // 균형 인수 계산결과 반환
}
// 트리의 균형을 잡는다.
BTreeNode* Rebalance(BTreeNode** pRoot) {
	int hDiff = GetHeightDiff(*pRoot); // 균형 인수 계산

	// 균형 인수가 +2 이상이면 LL상태 또는 LR상태이다.
	if (hDiff > 1) { // 왼쪽 서브 트리 방향으로 높이가 2 이상 크다면
		if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0) {
			*pRoot = RotateLL(*pRoot);
		}
		else {
			*pRoot = RotateLR(*pRoot);
		}
	}

	// 균형 인수가 -2 이하이면 RR상태 또는 RL상태이다.
	if (hDiff < -1) { // 오른쪽 서브 트리 방향으로 높이가 2 이상 크다면
		if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0) {
			*pRoot = RotateRR(*pRoot);
		}
		else {
			*pRoot = RotateRL(*pRoot);
		}
	}

	// 회전 과정에서 루트 노드가 변경될 수 있기 때문에, 루트 노드의 주소 값을 반환
	return *pRoot;
}<file_sep>/Doit/Recursive/hanoi.c
/* 하노이의 탑 */
#include <stdio.h>

// no개의 원반을 1 -> 3으로 옮기고 싶을 때
// no-1의 원반을 1 -> 2로 옮기고,
// no의 원반을 1 -> 3으로 옮긴다.
// no-1의 원반을 2 -> 3으로 옮긴다.
void move(int no, int x, int y)
{
	if (no > 1)
		move(no - 1, x, 6 - x - y); // 그룹을 시작 기둥에서 중간 기둥으로

	printf("원반[%d]을 %d기둥에서 %d기둥으로 옮김\n", no, x, y);

	if (no > 1)
		move(no - 1, 6 - x - y, y); // 그룹을 중간 기둥에서 목표 기둥으로
}

int main()
{
	int n;
	printf("하노이의 탑\n원반 개수 : ");
	scanf_s("%d", &n);
	move(n, 1, 3);
	return 0;
}<file_sep>/Doit/Sorting/heap.c
/* 힙 정렬 */
#include <stdio.h>
#include <stdlib.h>

#define swap(type, x, y) do{type t = x; x = y; y = t;} while(0)

// 1. downheap 사용해서 배열 a를 heap으로 만들어준다.
// 2. 루트에 있는 가장 큰 값을 빼내어 배열 마지막 요소와 바꾸고,
//    배열의 나머지 부분을 다시 힙으로 만들어주는 과정을 반복하여 정렬을 수행한다.

// a, 4, 9
static void downheap(int a[], int left, int right)
{
	int temp = a[left]; // 루트(여기의 값이 그 자리에 있을지, 아니면 자리를 변경해야 하는지 저장하는 값)
	int child;
	int parent;
	// 부모가 될 수 있는 조건은 parent < (right + 1) / 2까지만이다. (자식이 있어야 가능)
	for (parent = left; parent < (right + 1) / 2; parent = child)
	{
		int cl = parent * 2 + 1; // 왼쪽 자식
		int cr = cl + 1;         // 오른쪽 자식
		child = (cr <= right && a[cr] > a[cl]) ? cr : cl;  // 왼쪽 vs 오른쪽
		if (temp >= a[child])    // 가장 큰 값과 루트를 비교해서, 루트가 크면 종료
			break;
		a[parent] = a[child];    // 아니라면, 부모에 자식을 넣어주고, 이어간다.
	}
	a[parent] = temp;
}

void heapsort(int a[], int n)
{
	int i;
	// 주어진 배열 a를 heap으로 구성해준다.
	// 아랫부분의 작은 부분트리부터 시작해 올라가는 방식이다.
	for (i = (n - 1) / 2; i >= 0; --i)
		downheap(a, i, n - 1);

	for (i = n - 1; i > 0; --i)
	{
		// 루트를 가장 맨 뒤의 값과 swap해서 정렬해준다.
		swap(int, a[0], a[i]);
		// 루트를 없애고 힙 상태를 유지하기 위해서 downheap을 한다.
		downheap(a, 0, i - 1);
	}
}

int main()
{
	int i, nx;
	int* x;
	puts("힙 정렬");
	printf("요소 개수 : "); scanf_s("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));
	for (i = 0; i < nx; ++i)
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]);
	}
	heapsort(x, nx);
	puts("오름차순으로 정렬");
	for (i = 0; i < nx; ++i)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);
	return 0;
}<file_sep>/열혈자료구조/Graph/LinkedListBasedGraph/ALGraph.c
#include <stdio.h>
#include <stdlib.h>
#include "ALGraph.h"
#include "DLinkedList.h"

int WhoIsPrecede(int data1, int data2) {
	if (data1 < data2)
		return 0;
	else
		return 1;
}

void GraphInit(ALGraph* pg, int nv) {
	int i;

	// 정점의 수에 해당하는 길이의 리스트 배열을 생성한다.
	pg->adjList = (List*)malloc(sizeof(List) * nv);

	pg->numV = nv;  // 정점의 수는 nv에 저장된 값으로 결정
	pg->numE = 0;   // 초기의 간선 수는 0개

	// 정점의 수만큼 생선된 리스트들을 초기화한다.
	for (i = 0; i < nv; i++) {
		ListInit(&(pg->adjList[i])); // 인접리스트는 인덱스의 시작이 0부터
		SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
	}
}

void GraphDestroy(ALGraph* pg) {
	if (pg->adjList != NULL)
		free(pg->adjList);     // 동적으로 할당된 연결 리스트의 소멸
}

void AddEdge(ALGraph* pg, int fromV, int toV) {
	// 구현은 무방향 그래프이므로 양쪽 모두 연결해준다.
	// 정점 fromV의 연결 리스트에 정점 toV의 정보 추가
	LInsert(&(pg->adjList[fromV]), toV);
	// 정점 toV의 연결 리스트에 정점 fromV의 정보 추가
	LInsert(&(pg->adjList[toV]), fromV);
	pg->numE += 1;
}

void ShowGraphEdgeInfo(ALGraph* pg) {
	int i;
	int vx;

	for (i = 0; i < pg->numV; i++) {
		printf("%c와 연결된 정점: ", i + 65);
		
		if (LFirst(&(pg->adjList[i]), &vx)) {
			printf("%c ", vx + 65);

			while (LNext(&(pg->adjList[i]), &vx)) {
				printf("%c ", vx + 65);
			}
		}
		printf("\n");
	}
}<file_sep>/열혈자료구조/Tree/AVLTree/AVLRebalance.h
#pragma once

#include "BinaryTree3.h"

// 트리의 균형을 잡는다.
BTreeNode* Rebalance(BTreeNode** pRoot);<file_sep>/README.md
# DataStructure
자료구조에 대해서 공부 및 적용

* 참고한 책

  * 열혈 자료구조 (저자 윤성우)
  * 자료구조와 함께 배우는 알고리즘 입문(C 언어편)
<file_sep>/Doit/Set/IntSet/IntSet.h
#ifndef ___IntSet
#define ___IntSet

typedef struct
{
	int max;
	int num;
	int* set;
}IntSet;

int Initialize(IntSet* s, int max);

// 집합 s에 n이 들어 있는지 확인
int IsMember(const IntSet* s, int n);

// 집합 s에 n 추가
void Add(IntSet* s, int n);

// 집합 s에 n을 삭제
void Remove(IntSet* s, int n);

int Capacity(const IntSet* s);

int Size(const IntSet* s);

// 집합 s2를 s1에 대입
void Assign(IntSet* s1, const IntSet* s2);

int Equal(const IntSet* s1, const IntSet* s2);

// 집합 s2와 s3의 합집합을 s1에 대입
IntSet* Union(IntSet* s1, const IntSet* s2, const IntSet* s3);

// 집합 s2에서 s3를 뺀 차집합을 s1에 대입
IntSet* Intersection(IntSet* s1, const IntSet* s2, const IntSet* s3);

// 집합 s2에서 s3을 뺀 차집합을 s1에 대입
IntSet* Difference(IntSet* s1, const IntSet* s2, const IntSet* s3);

void Print(const IntSet* s);

void PrintLn(const IntSet* s);

void Terminate(IntSet* s);
#endif<file_sep>/열혈자료구조/Stack/Calculator/InfixToPostfix.h
#pragma once

void ConvToRPNExp(char exp[]); // 중위 표기법 -> 후위 표기법<file_sep>/Doit/String/strary2.c
/*  문자열을 초기화하며 선언하는 방법 */
#include <stdio.h>

int main()
{
	//char st[10] = { 'A','B','C','D', '\0' };
	char st[10] = "ABCD"; // 가장 많이 쓰이는 방식
	printf("문자열 st에는 %s가 들어있다.\n", st);
	return 0;
}<file_sep>/열혈자료구조/Hash/Chaining(LinkedList)/Table2.h
#pragma once

#include "Slot2.h"
#include "DLinkedList.h"

#define MAX_TBL  100

typedef int HashFunc(Key k);

typedef struct _table {
	List tbl[MAX_TBL];
	HashFunc* hf;
}Table;

void TBLInit(Table* bt, HashFunc* f);
void TBLInsert(Table* bt, Key k, Value v);
Value TBLDelete(Table* bt, Key k);
Value TBLSearch(Table* bt, Key k);<file_sep>/Doit/Tree/BinarySearchTree/BinTree.h
#ifndef ___BinTree
#define ___BinTree

#include "Member.h"

typedef struct __bnode
{
	Member data;
	struct __bnode* left;
	struct __bnode* right;
}BinNode;

BinNode* Search(BinNode* p, const Member* x);
BinNode* Add(BinNode* p, const Member* x);
int Remove(BinNode** root, const Member* x);
void PrintTree(const BinNode* p);
void FreeTree(BinNode* p);
#endif<file_sep>/열혈자료구조/Sorting/HeapSort/UsefulHeap.c
#include "UsefulHeap.h"

void HeapInit(Heap* ph, PriorityComp pc) {
	ph->numOfData = 0;
	ph->comp = pc; // 함수 등록
}

int HIsEmpty(Heap* ph) {
	if (ph->numOfData == 0)
		return TRUE;
	else
		return FALSE;
}

int GetParentIDX(int idx) {  // 부모 노드의 인덱스 값 반환
	return idx / 2;
}

int GetLChildIDX(int idx) {  // 왼쪽 자식 노드의 인덱스 값 반환
	return idx * 2;
}

int GetRChildIDX(int idx) {  // 오른쪽 자식 노드의 인덱스 값 반환
	return idx * 2 + 1;
}

// 두 개의 자식 노드 중 높은 우선순위 자식 노드 인덱스 값을 반환
int GetHiPriChildIDX(Heap* ph, int idx) {
	// 자식 노드가 존재하지 않는다면,
	if (GetLChildIDX(idx) > ph->numOfData)
		return 0;
	// 자식 노드가 왼쪽 자식 노드 하나만 존재한다면,
	else if (GetLChildIDX(idx) == ph->numOfData)
		return GetLChildIDX(idx);
	// 자식 노드가 둘 다 존재한다면,
	else {
		// 오른쪽 자식 노드의 우선순위가 높다면
		if(ph->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0)
			return GetRChildIDX(idx);
		else
			return GetLChildIDX(idx);
	}
}

// 힙에 데이터 저장
void HInsert(Heap* ph, HData data) {
	int idx = ph->numOfData + 1;

	// 새 노드가 루트 노드의 위치가 아니라면 반복
	while (idx != 1) {
		// 새 노드와 부모 노드의 우선순위 비교
		if (ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0) {
			// 새 노드가 부모 노드의 우선순위보다 높다면
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
			break;
	}

	ph->heapArr[idx] = data;
	ph->numOfData += 1;
}

// 힙에서 데이터 삭제
// 핵심은 마지막 노드가 있어야 할 위치를 parentIdx에 저장된 인덱스 값을
// 갱신해가며 찾는다
HData HDelete(Heap* ph) {
	HData retData = ph->heapArr[1];
	HData lastElem = ph->heapArr[ph->numOfData];

	int parentIdx = 1;
	int childIdx;

	while (childIdx = GetHiPriChildIDX(ph, parentIdx)) {
		if (ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
			break;

		ph->heapArr[parentIdx] = ph->heapArr[childIdx];
		parentIdx = childIdx;
	} // 반복문 탈출하면 parentIdx에 마지막 노드의 위치정보가 저장

	// 그 위치에 마지막 노드의 정보를 넣는다
	ph->heapArr[parentIdx] = lastElem;
	ph->numOfData -= 1;
	return retData;
}<file_sep>/Doit/String/str_len3.c
/* 문자열의 길이를 구해보자. */
#include <stdio.h>

int str_len(const char* s)
{
	const char* p = s;
	while (*s)
		s++;
	return s - p;
}

int main()
{
	char str[256];
	printf("문자열 : ");
	scanf_s("%s", str, 256);
	printf("이 문자열의 길이는 %d이다.\n", str_len(str));
	return 0;
}<file_sep>/열혈자료구조/Search/InterpolSearch/InterpolSearch.c
#include <stdio.h>

// 보간 탐색의 구현
// 이진 탐색의 비효율성을 개선시킨 알고리즘이다.
// 단점은 정수형 나눗셈이 아닌 실수형 나눗셈을 진행 -> 이는 오차가 발생할 수 있음.
int ISearch(int ar[], int first, int last, int target) {
	
	int mid;

	if (ar[first] > target || ar[last] < target)
		return -1;     // -1의 반환은 탐색의 실패를 의미

	// 이진 탐색과의 차이점을 반영한 문장
	mid = ((double)(target - ar[first]) / (ar[last] - ar[first]) * 
		(last - first)) + first;

	if (ar[mid] == target)
		return mid;    // 탐색된 타겟의 인덱스 값 반환
	else if (target < ar[mid])
		return ISearch(ar, first, mid - 1, target);
	else
		return ISearch(ar, mid + 1, last, target);
}

int main() {
	int arr[] = { 1,3,5,7,9 };
	int idx;

	idx = ISearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 2);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스 : %d \n", idx);

	return 0;
}<file_sep>/열혈자료구조/Hash/SimpleHash/Slot.h
#pragma once

#include "Person.h"

typedef int Key;   // 주민등록번호(ssn)
typedef Person* Value;

enum SlotStatus {EMPTY, DELETED, INUSE};

typedef struct _slot {
	Key key;
	Value val;
	enum SlotStatus status;
}Slot;
<file_sep>/Doit/String/strary1.c
/* 배열에 문자열 저장하기 */
#include <stdio.h>

// 문자열 값을 char형 배열에 저장하면 자유롭게 값을 꺼내고 쓸 수 있다.

int main()
{
	char st[10];
	st[0] = 'A';
	st[1] = 'B';
	st[2] = 'C';
	st[3] = 'D';
	st[4] = '\0'; // 문자열의 끝을 의미하는 널 문자
	st[5] = 'T';
	printf("문자열 st에는 %s가 들어있다.\n", st);
	return 0;
}<file_sep>/열혈자료구조/Graph/Kruskal/ALEdge.h
#pragma once

typedef struct _edge {
	int v1;
	int v2;
	int weight; // 가중치 정보
}Edge;
<file_sep>/Doit/Stack&Queue/ArrayQueue(RingBuffer)/queueMain.c
#include <stdio.h>
#include "IntQueue.h"

int main()
{
	IntQueue que;

	if (Initialize(&que, 64) == -1)
	{
		puts("큐의 생성에 실패");
		return 1;
	}
	while (1)
	{
		int m, x;

		printf("현제 데이터 수 : %d / %d\n", Size(&que), Capacity(&que));
		printf("(1)인큐 (2)디큐 (3)피크 (4)출력 (5)검색 (0)종료 : ");
		scanf_s("%d", &m);

		if (m == 0) break;
		switch (m)
		{
		case 1:
			printf("데이터 : ");
			scanf_s("%d", &x);
			if (Enque(&que, x) == -1)
				puts("오류 : 인큐에 실패");
			else
				printf("디큐한 데이터는 %d\n", x);
			break;
		case 2:
			if (Deque(&que, &x) == -1)
				puts("오류 : 디큐에 실패");
			else
				printf("디큐한 데이터는 %d\n", x);
			break;
		case 3:
			if (Peek(&que, &x) == -1)
				puts("오류 : 피크에 실패");
			else
				printf("피크한 데이터는 %d\n", x);
			break;
		case 4:
			Print(&que);
			break;
		case 5:
			printf("검색할 데이터 : ");
			scanf_s("%d", &x);
			if (Search2(&que, x) == -1)
				puts("오류 : 검색 실패");
			else
				printf("찾은 데이터는 front에서 %d만큼 떨어져있다.\n", Search2(&que, x));
			break;
		}
	}
	Terminate(&que);
	return 0;
}<file_sep>/Doit/Recursive/euclid.c
/* 유클리드 호제법에 의해 최대공약수를 구한다. */
#include <stdio.h>

int gcd(int x, int y)
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}

int main()
{
	int x, y;
	puts("두 정수의 최대공약수를 구해보자.");
	printf("정수를 입력 : ");
	scanf_s("%d", &x);
	printf("정수를 입력 : ");
	scanf_s("%d", &y);
	printf("최대공약수는 %d\n", gcd(x, y));
	printf("최대공약수는 %d\n", gcd(y, x));
	return 0;
}<file_sep>/Doit/String/strstr_test.c
/* strstr 함수를 사용한 프로그램 */
#include <stdio.h>
#include <string.h>

int main()
{
	char s1[256], s2[256];
	char* p;
	puts("strstr함수");
	printf("텍스트 : "); scanf_s("%s", &s1, 256);
	printf("패턴 : "); scanf_s("%s", &s2, 256);
	p = strstr(s1, s2); // 문자열 s1에서 문자열 s2 검색
	if (p == NULL)
		printf("텍스트에 패턴이 없다.\n");
	else
	{
		int ofs = p - s1;
		printf("\n%s\n", s1);
		printf("%*s|\n", ofs, "", s2);
		printf("%*s%s\n", ofs, "", s2);
	}

	return 0;
}<file_sep>/열혈자료구조/Tree/ExpressionTree/ListBaseStack.h
#pragma once

#define TRUE 1
#define FALSE 0
#include "BinaryTree2.h"

// 연결 리스트 기반 스택 구현

typedef BTreeNode* Data;

typedef struct _node {    // 연결 리스트의 노드를 표현한 구조체
	Data data;
	struct _node* next;
}Node;

typedef struct _listStack {  // 연결 리스트 기반 스택을 표현한 구조체
	Node* head;
}ListStack;

typedef ListStack Stack;

void StackInit(Stack* pstack);        // 스택 초기화
int SIsEmpty(Stack* pstack);         // 스택이 비어있는지 확인

void SPush(Stack* pstack, Data data); // 스택 push 연산
Data SPop(Stack* pstack);             // 스택 pop 연산
Data SPeek(Stack* pstack);            // 스택 peek 연산<file_sep>/열혈자료구조/Stack/Calculator/InfixCalculator.c
#include <string.h>
#include <stdlib.h>
#include "InfixToPostfix.h" // ConvRPNExp 함수 호출을 위해
#include "PostCalculator.h" // EvalRPNExp 함수 호출을 위해

int EvalInfixExp(char exp[]) {
	int len = strlen(exp);
	int ret;
	char* expcpy = (char*)malloc(len + 1);
	strcpy(expcpy, exp);

	ConvToRPNExp(expcpy); // 중위 표기법 -> 후위 표기법
	ret = EvalRPNExp(expcpy); // 후위 표기법 수식 계산

	free(expcpy);
	return ret;
}<file_sep>/Doit/String/strncmp_test.c
/* 문자열을 비교하는 프로그램(strncmp 함수 사용) */
#include <stdio.h>
#include <string.h>

int main()
{
	char st[128];
	puts("STRING의 처음 3개의 문자와 비교");
	puts("XXXX를 입력하면 종료");
	while (1)
	{
		printf("문자열 st : ");
		scanf_s("%s", st, 128);
		if (strncmp("XXXX", st, 3) == 0)
			break;
		printf("strncmp(\"STRING\",st, 3) = %d\n", strncmp("STRING", st, 3));
	}

	return 0;
}<file_sep>/Doit/String/swap_ptr.c
/* 두 포인터 값을 서로 교환하는 함수 */
#include <stdio.h>

// 이 함수가 s1, s2의 주소를 받아야 하기 때문에 char**형으로 받아야 한다.
void swap_ptr(char** x, char** y)
{
	char* tmp = *x;
	*x = *y;
	*y = tmp;
}

int main()
{
	char* s1 = "ABCD";
	char* s2 = "EFGH";

	printf("포인터 s1 : %s\n", s1);
	printf("포인터 s2 : %s\n", s2);

	swap_ptr(&s1, &s2);

	puts("\n포인터 s1과 s2의 값을 서로 교환\n");

	printf("포인터 s1 : %s\n", s1);
	printf("포인터 s2 : %s\n", s2);
	return 0;
}<file_sep>/Doit/Array/chap02-7.cpp
/* 배열 요소를 역순으로 정렬한다. */
#include <stdio.h>
#include <stdlib.h>

#define swap(type, x, y) do{ type t = x; x = y; y = t;} while(0)

void ary_reverse(int a[], int n)
{
	int i;
	for (i = 0; i < n / 2; ++i)
		swap(int, a[i], a[n - i - 1]); // ;(세미콜론) 전까지 치환된다.
}

int main()
{
	int i;
	int* x;
	int nx;

	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = (int*)calloc(nx, sizeof(int));
	for (i = 0; i < nx; ++i)
	{
		printf("x[%d] : ", i);
		scanf_s("%d", &x[i]);
	}
	ary_reverse(x, nx);
	printf("배열의 요소를 역순으로 정렬한다.\n");
	for (i = 0; i < nx; ++i)
		printf("x[%d] = %d\n", i, x[i]);
	free(x);
	return 0;
}<file_sep>/열혈자료구조/Graph/Kruskal/ALGraphKruskal.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraphKruskal.h"
#include "DLinkedList.h"
#include "ArrayBaseStack.h"

int WhoIsPrecede(int data1, int data2) {
	if (data1 < data2)
		return 0;
	else
		return 1;
}

int PQWeightComp(Edge d1, Edge d2) {
	return d1.weight - d2.weight;
}

void GraphInit(ALGraph* pg, int nv) {
	int i;

	// 정점의 수에 해당하는 길이의 리스트 배열을 생성한다.
	pg->adjList = (List*)malloc(sizeof(List) * nv);

	pg->numV = nv;  // 정점의 수는 nv에 저장된 값으로 결정
	pg->numE = 0;   // 초기의 간선 수는 0개

	// 정점의 수만큼 생선된 리스트들을 초기화한다.
	for (i = 0; i < nv; i++) {
		ListInit(&(pg->adjList[i])); // 인접리스트는 인덱스의 시작이 0부터
		SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
	}

	pg->visitInfo = (int*)malloc(sizeof(int) * pg->numV);
	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);

	// 우선순위 큐 초기화
	PQueueInit(&(pg->pqueue), PQWeightComp);
}

void GraphDestroy(ALGraph* pg) {
	if (pg->adjList != NULL)
		free(pg->adjList);     // 동적으로 할당된 연결 리스트의 소멸

	if (pg->visitInfo != NULL)
		free(pg->visitInfo);
}

void AddEdge(ALGraph* pg, int fromV, int toV, int weight) {

	Edge edge = { fromV, toV, weight };  // 간선의 가중치 정보를 담는다.


	// 구현은 무방향 그래프이므로 양쪽 모두 연결해준다.
	// 정점 fromV의 연결 리스트에 정점 toV의 정보 추가
	LInsert(&(pg->adjList[fromV]), toV);
	// 정점 toV의 연결 리스트에 정점 fromV의 정보 추가
	LInsert(&(pg->adjList[toV]), fromV);
	pg->numE += 1;

	// 간선의 가중치 정보를 우선순위 큐에 저장
	PEnqueue(&(pg->pqueue), edge);
}

void RecoverEdge(ALGraph* pg, int fromV, int toV, int weight) {
	LInsert(&(pg->adjList[fromV]), toV);
	LInsert(&(pg->adjList[toV]), fromV);
	(pg->numE)++;
}

// 한쪽 방향의 간선 소멸
void RemoveWayEdge(ALGraph* pg, int fromV, int toV) {
	int edge;

	if (LFirst(&(pg->adjList[fromV]), &edge)) {
		if (edge == toV) {
			LRemove(&(pg->adjList[fromV]));
			return;
		}

		while (LNext(&(pg->adjList[fromV]), &edge)) {
			if (edge == toV) {
				LRemove(&(pg->adjList[fromV]));
				return;
			}
		}
	}
}

// 간선의 소멸
void RemoveEdge(ALGraph* pg, int fromV, int toV) {
	RemoveWayEdge(pg, fromV, toV);
	RemoveWayEdge(pg, toV, fromV);
	(pg->numE)--;
}

void ShowGraphEdgeInfo(ALGraph* pg) {
	int i;
	int vx;

	for (i = 0; i < pg->numV; i++) {
		printf("%c와 연결된 정점: ", i + 65);

		if (LFirst(&(pg->adjList[i]), &vx)) {
			printf("%c ", vx + 65);

			while (LNext(&(pg->adjList[i]), &vx)) {
				printf("%c ", vx + 65);
			}
		}
		printf("\n");
	}
}

int VisitVertex(ALGraph* pg, int visitV) {
	if (pg->visitInfo[visitV] == 0) {
		pg->visitInfo[visitV] = 1; // 방문했다고 체크
		return TRUE;
	}
	return FALSE;
}

void DFShowGraphVertex(ALGraph* pg, int startV) {
	Stack stack;
	int visitV = startV;
	int nextV;

	StackInit(&stack);          // DFS을 위한 스택의 초기화
	VisitVertex(pg, visitV);    // 시작 정점을 방문
	SPush(&stack, visitV);      // 시작 정점의 정보를 스택으로 넣는다.

	// visitV에 담긴 정점과 연결된 정점의 방문을 시도하는 while문
	// visitV와 인접한 정점 중에서 찾아서 방문하지 않았다면 방문한다.
	while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) {

		// visitV와 연결된 정점의 정보가 nextV에 담긴 상태에서 이하를 진행한다.
		int visitFlag = FALSE;

		if (VisitVertex(pg, nextV) == TRUE) {
			SPush(&stack, visitV);
			visitV = nextV;
			visitFlag = TRUE;
		}
		else {
			while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) {
				if (VisitVertex(pg, nextV) == TRUE) {
					SPush(&stack, visitV);
					visitV = nextV;
					visitFlag = TRUE;
					break;
				}
			}
		}

		if (visitFlag == FALSE) { // 추가로 방문한 정점이 없었다면

			// 스택이 비면 탐색의 시작점으로 되돌아 온 것이다.
			if (SIsEmpty(&stack) == TRUE)
				break;
			else
				visitV = SPop(&stack);  // 길을 되돌아 간다.
		}
	}

	// 이후의 다른 탐색을 위해서 방문 배열을 다시 초기화 시킨다.
	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

// 간선의 가중치 정보 출력
void ShowGraphEdgeWeightInfo(ALGraph* pg) {
	PQueue copyPQ = pg->pqueue;
	Edge edge;

	while (!PQIsEmpty(&copyPQ)) {
		edge = PDequeue(&copyPQ);
		printf("(%c-%c), w:%d \n", edge.v1 + 65, edge.v2 + 65, edge.weight);
	}
}

// 인자로 전달된 두 정점이 연결되어 있다면 TRUE, 아니면 FALSE
int IsConnVertex(ALGraph* pg, int v1, int v2) {
	Stack stack;
	int visitV = v1;
	int nextV;

	StackInit(&stack);
	VisitVertex(pg, visitV);
	SPush(&stack, visitV);

	while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) {
		int visitFlag = FALSE;

		// 정점을 돌아다니는 도중에 목표를 찾는다면 TRUE반환
		if (nextV == v2) {
			// 함수가 반환하기 전에 초기화를 진행
			memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
			return TRUE;
		}

		if (VisitVertex(pg, nextV) == TRUE) {
			SPush(&stack, visitV);
			visitV = nextV;
			visitFlag = TRUE;
		}
		else {
			while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) {
				
				if (nextV == v2) {
					memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
					return TRUE;
				}

				if (VisitVertex(pg, nextV) == TRUE) {
					SPush(&stack, visitV);
					visitV = nextV;
					visitFlag = TRUE;
					break;
				}
			}
		}

		if (visitFlag == FALSE) {
			if (SIsEmpty(&stack) == TRUE)
				break;
			else
				visitV = SPop(&stack);
		}
	}

	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
	return FALSE;
}

void ConKruskalMST(ALGraph* pg) {  // 크루스칼 간선의 정보 저장
	Edge recvEdge[20];
	Edge edge;
	int eidx = 0;
	int i;

	// MST를 형성할 때까지 반복
	while (pg->numE + 1 > pg->numV) { // MST 간선의 수 + 1 == 정점의 수

		// 우선순위 큐에서 가중치가 제일 높은 간선의 정보를 꺼낸다.
		edge = PDequeue(&(pg->pqueue));
		RemoveEdge(pg, edge.v1, edge.v2); // 그래프에서 간선을 삭제

		// 간선을 삭제하고 나서도 두 정점을 연결하는 경로가 있는지 확인
		if (!IsConnVertex(pg, edge.v1, edge.v2)) { // 두 정점이 연결되어 있는지 확인

			// 경로가 없으면 삭제한 간선을 다시 복원
			RecoverEdge(pg, edge.v1, edge.v2, edge.weight); // 삭제된 간선을 다시 삽입

			// 복원한 간선의 정보를 별도로 저장한다.
			recvEdge[eidx++] = edge;
		}
	}

	// 우선순위 큐에서 삭제된 간선의 정보를 회복
	for (i = 0; i < eidx; i++)
		PEnqueue(&(pg->pqueue), recvEdge[i]);
}<file_sep>/열혈자료구조/LinkedList/Double_Linked_List/DBLikedList.h
#pragma once

#define TRUE 1
#define FALSE 0

// 양방향 연결 리스트의 구현
// double linked list

typedef int Data;

typedef struct _node {
	Data data;
	struct _node* next;
	struct _node* prev;
}Node;

typedef struct _DLinkedList {
	Node* head;
	Node* cur;
	int numOfData;
}DBLinkedList;

typedef DBLinkedList List;

void ListInit(List* plist);				 // 리스트 초기화
void LInsert(List* plist, Data data);    // 새 노드 추가

int LFirst(List* plist, Data* pdata);    // 데이터 조회 (첫 번째 노드의 데이터 조회)
int LNext(List* plist, Data* pdata);     // 두 번째 이후의 노드 데이터 조회
int LPrevious(List* plist, Data* pdata); // LNext의 반대 방향으로 데이터 조회
int LCount(List* plist);                 // 리스트에 있는 노드의 개수 반환<file_sep>/열혈자료구조/LinkedList/Circular_Linked_List/CLinkedList.c
/* Circular Linked List */
#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"

void ListInit(List* plist) {
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

// 새 노드를 head에서 추가하는 함수
void LInsertFront(List* plist, Data data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->tail == NULL) {
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
	}

	(plist->numOfData)++;
}

// 새 노드를 tail에 추가하는 함수
void LInsert(List* plist, Data data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->tail == NULL) {
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}

	(plist->numOfData)++;
}

// 데이터 조회 ( 머리 부분을 시작으로 가리킨다.)
int LFirst(List* plist, Data* pdata) {
	if (plist->tail == NULL)
		return FALSE;

	plist->before = plist->tail;
	plist->cur = plist->tail->next;

	*pdata = plist->cur->data;
	return TRUE;
}

// 다음 데이터 조회
int LNext(List* plist, Data* pdata) {
	if (plist->tail == NULL)
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

// 노드 삭제
Data LRemove(List* plist) {
	Node* rpos = plist->cur;
	Data rdata = rpos->data;

	if (rpos == plist->tail) {
		if (plist->tail == plist->tail->next)
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

// 남은 노드의 수 반환
int LCount(List* plist) {
	return plist->numOfData;
}<file_sep>/Doit/Array/chap02-4.cpp
/* int형 배열을 동적으로 생성하고 해제한다. */
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int i;
	int* a;
	int na;
	printf("요소 개수 : ");
	scanf_s("%d", &na);
	a = (int*)calloc(na, sizeof(int));

	if (a == NULL)
		puts("메모리 할당에 실패");
	else
	{
		printf("%d개의 정수를 입력.\n", na);
		for (i = 0; i < na; ++i)
		{
			printf("a[%d] : ", i);
			scanf_s("%d", &a[i]);
		}
		printf("각 요소의 값은 다음과 같다.\n");
		for (i = 0; i < na; ++i)
			printf("a[%d] = %d\n", i, a[i]);

		free(a);
	}

	return 0;
}

<file_sep>/열혈자료구조/Recursive/RecursiveFunc.c
#include <stdio.h>

void Recursive(int num) {
	if (num <= 0) return;
	printf("Recursive call! %d\n", num);
	Recursive(num - 1);
}

int main() {
	Recursive(3);
	return 0;
}<file_sep>/공부한것들/SegmentTree.c
#include <stdio.h>
#define NUMBER 7

int a[] = { 7,1,9,5,6,4,1 };
int tree[4 * NUMBER]; // 4를 곱하면 모든 범위가 커버 가능하다.

int init(int start, int end, int node)
{
	if (start == end) return tree[node] = a[start]; // 리프 노드인 경우 배열의 값이 그대로 들어간다.
	int mid = (start + end) / 2;
	// 재귀적으로 두 부분으로 나눈 뒤에 그 합을 자기 자신으로 한다. (왼쪽 자식 합 + 오른쪽 자식 합)
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

// start : 시작, end : 끝
// left, right : 구간의 합을 구하고자 하는 범위
// node : 노드 인덱스
int sum(int start, int end, int node, int left, int right)
{
	// 범위 밖에 있는 경우
	if (left > end || right < start) return 0;
	// 범위 안에 있는 경우
	if (left <= start && end <= right) return tree[node];
	// 그렇지 않다면 두 부분으로 나누어 합 구하기
	int mid = (start + end) / 2;
	return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

// start : 시작, end : 끝
// index : 구간 합을 수정하고자 하는 노드
// dif : 수정할 값
void update(int start, int end, int node, int index, int dif)
{
	// 범위 밖에 있는 경우
	if (index < start || index > end) return;
	// 범위 안에 있으면 내려가며 다른 원소도 갱신
	tree[node] += dif;
	// 리프 노드이면
	if (start == end) return;
	int mid = (start + end) / 2;
	update(start, mid, node * 2, index, dif);
	update(mid + 1, end, node * 2 + 1, index, dif);
}

int main()
{
	// 구간 합 트리 생성하기
	init(0, NUMBER - 1, 1);
	// 구간 합 구하기
	printf("0부터 6까지의 구간 합: %d\n", sum(0, NUMBER - 1, 1, 0, 6));
	// 구간 합 갱신하기
	printf("인덱스 5의 원소를 +3만큼 수정\n");
	update(0, NUMBER - 1, 1, 5, 3);
	// 구간 합 다시 구하기
	printf("3부터 6까지의 구간 합: %d\n", sum(0, NUMBER - 1, 1, 3, 6));
	printf("0부터 6까지의 구간 합: %d\n", sum(0, NUMBER - 1, 1, 0, 6));
	return 0;
}<file_sep>/Doit/Array/chap02-9.cpp
/* 1000 이하의 소수를 나열한다. */
#include <stdio.h>

int main()
{
	int i, n;
	unsigned long counter = 0;
	for (n = 2; n <= 1000; ++n)
	{
		for (i = 2; i < n; ++i)
		{
			++counter;
			if (n % i == 0)
				break;
		}

		if (n == i)
			printf("%d\n", n);
	}
	printf("나눗셈을 실행한 횟수 : %lu\n", counter);
	return 0;
}<file_sep>/Doit/Stack&Queue/RingBuffer.c
/* 원하는 개수만큼 데이터를 입력하고, 요소의 개수가 n인 배열에는 최근에 입력한 n개만 저장 */
#include <stdio.h>

#define N 10

int main()
{
	int i;
	int a[N];
	int cnt = 0;
	int retry;
	puts("정수를 입력하세요.");
	do
	{
		printf("%d번째 정수 : ", cnt + 1);
		scanf_s("%d", &a[cnt++ % N]);
		printf("계속할까요?(Yes ... 1 / No ... 0) : ");
		scanf_s("%d", &retry);
	} while (retry == 1);
	i = cnt - N;
	if (i < 0) i = 0;
	for (; i < cnt; ++i)
		printf("%2d번째 정수 = %d\n", i + 1, a[i % N]);

	return 0;
}<file_sep>/Doit/Array/chap02-3.cpp
/* int형 객체를 동적으로 생성하고 해제한다. */
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int* x;
	x = (int*)calloc(1, sizeof(int));
	if (x == NULL)
		puts("메모리 할당에 실패");
	else
	{
		*x = 57;
		printf("*x = %d\n", *x);

		free(x);
	}

	return 0;
}<file_sep>/열혈자료구조/ArrayList/NameCard.h
#pragma once
#define NAME_LEN 30
#define PHONE_LEN 30

typedef struct __namecard {
	char name[NAME_LEN];
	char phone[PHONE_LEN];
}NameCard;

//NameCard 구조체 변수의 동적 할당 및 초기화 후 주소 값 반환
NameCard * MakeNameCard(const char * name, const char * phone);

//NameCard 구조체 변수의 정보 출력
void ShowNameCardInfo(NameCard * pcard);

//이름이 같으면 0, 다르면 0이 아닌 값 반환
int NameCompare(NameCard *pcard, const char * name);

//전화번호 정보를 변경
void ChangePhoneNum(NameCard * pcard, const char * phone);<file_sep>/Doit/String/strptr.c
/* 문자열을 포인터를 사용해서 출력 */
#include <stdio.h>

int main()
{
	char* pt = "12345"; // 포인터 pt는 문자열 리터널 "12345"의 첫 번째 문자 '1'를 가리킨다.
	printf("포인터 pt는 %s를 가리킨다.\n", pt);
	return 0;
}<file_sep>/Doit/Array/chap02-12.cpp
/* 한 해의 지난 날 수를 구한다. */
#include <stdio.h>

int mdays[][12] = {
	{31,28,31,30,31,30,31,31,30,31,30,31},
	{31,29,31,30,31,30,31,31,30,31,30,31}
};

// 윤년인지?
// 4로 나누어 떨어지는 년도는 윤년이다.
// 그 중 100으로 나누어 떨어지는 년도는 윤년이 아니다.
// 400으로 나누어 떨어지는 년도는 무조건 윤년이다.
int isleap(int year)
{
	return year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
}

int dayofyear(int y, int m, int d)
{
	int i;
	int days = d;
	for (i = 1; i < m; ++i)
		days += mdays[isleap(y)][i - 1];
	return days;
}

int main()
{
	int year, month, day;
	int retry;
	do
	{
		printf("년 : "); scanf_s("%d", &year);
		printf("월 : "); scanf_s("%d", &month);
		printf("일 : "); scanf_s("%d", &day);
		printf("%d년의 %d일째입니다.\n", year, dayofyear(year, month, day));
		printf("다시 할까요?(1... 예/0 ... 아니오) : ");
		scanf_s("%d", &retry);
	} while (retry == 1);
	return 0;
}<file_sep>/Doit/String/bf_match.c
/* 브루트-포스법으로 문자열 검색 */
#include <stdio.h>

//int bf_match(const char txt[], const char pat[])
int bf_match(const char* txt, const char* pat)
{
	int pt = 0; // text 인덱스
	int pp = 0; // pattern 인덱스
	while (txt[pt] != '\0' && pat[pp] != '\0')
	{
		if (txt[pt] == pat[pp])
		{
			pt++;
			pp++;
		}
		// 중간에 일치하지 않는 부분이 나오면
		else
		{
			pt = pt - pp + 1;
			pp = 0;
		}
	}

	if (pat[pp] == '\0')
		return pt - pp;
	return -1;
}

int main()
{
	int idx;
	char s1[256]; // text
	char s2[256]; // pattern
	puts("bruteforce");
	printf("text : "); scanf_s("%s", s1, 256);
	printf("pattern : "); scanf_s("%s", s2, 256);
	idx = bf_match(s1, s2);
	if (idx == -1)
		puts("text에 pattern이 없다.");
	else
		printf("%d번째 문자부터 match하다.\n", idx + 1);

	return 0;
}<file_sep>/열혈자료구조/Graph/BFS/ALGraphBFS.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraphBFS.h"
#include "DLinkedList.h"
#include "CircularQueue.h"

int WhoIsPrecede(int data1, int data2) {
	if (data1 < data2)
		return 0;
	else
		return 1;
}

void GraphInit(ALGraph* pg, int nv) {
	int i;

	// 정점의 수에 해당하는 길이의 리스트 배열을 생성한다.
	pg->adjList = (List*)malloc(sizeof(List) * nv);

	pg->numV = nv;  // 정점의 수는 nv에 저장된 값으로 결정
	pg->numE = 0;   // 초기의 간선 수는 0개

	// 정점의 수만큼 생선된 리스트들을 초기화한다.
	for (i = 0; i < nv; i++) {
		ListInit(&(pg->adjList[i])); // 인접리스트는 인덱스의 시작이 0부터
		SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
	}

	pg->visitInfo = (int*)malloc(sizeof(int) * pg->numV);
	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

void GraphDestroy(ALGraph* pg) {
	if (pg->adjList != NULL)
		free(pg->adjList);     // 동적으로 할당된 연결 리스트의 소멸

	if (pg->visitInfo != NULL)
		free(pg->visitInfo);
}

void AddEdge(ALGraph* pg, int fromV, int toV) {
	// 구현은 무방향 그래프이므로 양쪽 모두 연결해준다.
	// 정점 fromV의 연결 리스트에 정점 toV의 정보 추가
	LInsert(&(pg->adjList[fromV]), toV);
	// 정점 toV의 연결 리스트에 정점 fromV의 정보 추가
	LInsert(&(pg->adjList[toV]), fromV);
	pg->numE += 1;
}

void ShowGraphEdgeInfo(ALGraph* pg) {
	int i;
	int vx;

	for (i = 0; i < pg->numV; i++) {
		printf("%c와 연결된 정점: ", i + 65);

		if (LFirst(&(pg->adjList[i]), &vx)) {
			printf("%c ", vx + 65);

			while (LNext(&(pg->adjList[i]), &vx)) {
				printf("%c ", vx + 65);
			}
		}
		printf("\n");
	}
}

int VisitVertex(ALGraph* pg, int visitV) {
	if (pg->visitInfo[visitV] == 0) {
		pg->visitInfo[visitV] = 1;
		printf("%c ", visitV + 65);
		return TRUE;
	}
	return FALSE;
}

void BFShowGraphVertex(ALGraph* pg, int startV) {
	Queue queue;
	int visitV = startV;
	int nextV;

	QueueInit(&queue);
	VisitVertex(pg, visitV); // 시작 정점을 탐색한다.

	// 아래의 while문에서는 visitV와 연결된 모든 정점에 방문한다.
	while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) {
		if (VisitVertex(pg, nextV) == TRUE) {
			Enqueue(&queue, nextV); // nextV에 방문했으니 큐에 저장한다.
		}

		while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE) {
			if (VisitVertex(pg, nextV) == TRUE) {
				Enqueue(&queue, nextV);
			}
		}

		if (QIsEmpty(&queue) == TRUE) // 큐가 비면 BFS 종료
			break;
		else
			visitV = Dequeue(&queue); // 큐에서 하나 꺼내어 while문 다시 시작
	}

	memset(pg->visitInfo, 0, sizeof(int) * pg->numV); // 탐색 정보 초기화
}<file_sep>/Doit/Stack&Queue/ArrayStack/stack.h
#ifndef ___IntStack // ___IntStack를 define 하지 않았다면, (if not defined)
#define ___IntStack // endif가 나오기 전까지 이 부분을 포함시켜라

typedef struct
{
	int max;
	int ptr;
	int* stk;
}IntStack;

int Initialize(IntStack* s, int max);
int Push(IntStack* s, int x);
int Pop(IntStack* s, int* x);
int Peek(const IntStack* s, int* x);
void Clear(IntStack* s);
int Capacity(const IntStack* s);
int Size(const IntStack* s);
int IsEmpty(const IntStack* s);
int IsFull(const IntStack* s);
int Search(const IntStack* s, int x);
void Print(const IntStack* s);
void Terminate(IntStack* s);
#endif<file_sep>/Doit/String/str_len2.c
/* 문자열의 길이를 구해보자. */
#include <stdio.h>

int str_len(const char* s)
{
	int len = 0;

	while (*s++)
		len++;	
	return len;
}

int main()
{
	char str[256];
	printf("문자열 : ");
	scanf_s("%s", str, 256);
	printf("이 문자열의 길이는 %d이다.\n", str_len(str));
	return 0;
}<file_sep>/Doit/Recursive/eight_queen.c
/* 8퀸 문제 풀이 */
#include <stdio.h>

int flag_a[8];  // 각 행에 퀸을 배치했는지 체크하는 배열
int flag_b[15]; // 대각선 ↗에 퀸을 배치했는지 체크하는 배열
int flag_c[15]; // 대각선 ↘에 퀸을 배치했는지 체크하는 배열
int pos[8];
int counter;

void print()
{
	int i;
	for (i = 0; i < 8; ++i)
		printf("%2d", pos[i]);
	putchar('\n');
}

void set(int i)
{
	int j;
	for (j = 0; j < 8; ++j)
	{
		if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7])
		{
			pos[i] = j; // i열 j행에 퀸을 배치
			if (i == 7)
			{
				print();
				++counter;
			}
				
			else
			{
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 1;
				set(i + 1);
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 0;
			}
		}
	}
}

int main()
{
	int i;
	for (i = 0; i < 8; ++i)
		flag_a[i] = 0;
	for (i = 0; i < 15; ++i)
		flag_b[i] = flag_c[i] = 0;
	set(0);
	printf("출력횟수 : %d\n", counter); // 92 가지
	return 0;
}