자료구조 이것저것 정리

Hash Table - map으로 구현한답니다. 배울때 해쉬브라운 생각밖에 안했는데 지금도 ュ...ユ...그렇네

Map- key, value로 이루어진. . . 이건 중복으로 오류는 안되는데 카운트 안되고, 갱신은 된다

#include<iostream>
#include<map>
#include<vector>
using namespace std;

//key로 정렬
int main(){

map<string, int> m;
map<string, int> ::iterator it;

m.insert(make_pair("a",1));

m.insert(make_pair("c",3));
m.insert(make_pair("d",4));
m.insert(make_pair("e",5));
m["f"] = 6;
m["b"]=2;
//m["a"] = 7; a가 7로 갱신 됨.


if(!m.empty())
cout <<"size  : " << m.size()<<endl;

cout <<m.find("a")->first<<"  " <<m.find("a")->second<<endl;
cout <<"a 몇개 " << m.count("a")<<endl;


for( it = m.begin(); it != m.end(); it++){
	cout << "key : " << it->first << " " << "value : " << it->second << '\n';
 }

}

 

BST(Binary Search Tree)

검색하려는 키 값이 루트보다 크면 오른쪽 작으면 왼쪽! 

AVL Tree

균형이진 트리 균형맞는 이진트리 . .  균형인수= |왼쪽자식 높이 - 오른쪽 자식 높이|>2 이면 문제있음

과제였던 힙솔트 다운힙 업힙, ,  민힙으로 구현하는거, , , 다시 해보랬는데 그럴 필요 없을거 같아서 그냥 코드만 이해하고 이제 그래프로 넘어갈란다..~

#include <iostream>
using namespace std;

class Heap {
private:
	int* arr;
	int capacity;
	int currentSize;

	void swap(int *a, int *b) {
		int t = *a;
		*a = *b;
		*b = t;
	}

public:
	Heap(int Capacity) : capacity(Capacity) {
		arr = new int[Capacity + 1];
		currentSize = 0;
	}

	~Heap() {
		delete[] arr; //�����Ҵ� �Ѱ� �����
	}

	// upheap
	void Insert(int val) {
	 
		//heap size check
		if (currentSize >= capacity)
			return;

		
		int i = ++currentSize; //�������� ���� ����
		arr[i] = val;

		//�θ𰪺��� �ڽ��� ũ�� ��ȯ ���
		int x = (i) / 2;
		while (arr[i] < arr[x])
		{
			swap(&arr[i], &arr[x]);
			i = x;
			x = (i) / 2;
		}
	}

	// down heap
	void ExtractMin() {

		if (currentSize <= 0)
			return;

		// root
		int v = arr[1];

		swap(&arr[1], &arr[currentSize]);


		arr[currentSize] = NULL;

		--currentSize; 
		int root = 1;

		while (root <= currentSize)
		{
			int left = 2 * root;

			int right = left + 1;

			if (left >= currentSize)
			{
				break;  

			}
			else if (right >= currentSize) 
			{
				if (arr[left] < arr[root])
				{
					swap(&arr[left], &arr[root]);
					root = left;
				}
				else
					break;


			}

			else
			{
				if (arr[left] < arr[root] && arr[right] < arr[root])
				{
					if (arr[left] < arr[right])
					{
						swap(&arr[left], &arr[root]);
						root = left;
					}
					else
					{
						swap(&arr[right], &arr[root]);
						root = right;

					}
				}
				else if (arr[left] < arr[root])
				{
					swap(&arr[left], &arr[root]);
					root = left;
				}
				else if (arr[right] < arr[root])
				{
					swap(&arr[right], &arr[root]);
					root = right;
				}
				else {
					break;
				}

			}
		}
		return;
	}


	int GetTop() {
		if (currentSize >= 1) return arr[1];
		else return -1;
	}



	// Traversal 
	void InorderT(int x)
	{
		if (arr[x] == NULL)  //�迭�� �ΰ��̸� return
			return;

		if (x * 2 <= currentSize) InorderT(x * 2);  //���� ����Ʈ��
		cout << arr[x] << " ";
		if (x * 2 + 1 <= currentSize) InorderT(x * 2 + 1);//�����ʳ��

	}


	void PreorderT(int x)
	{
		if (arr[x] == NULL) //�迭�� �ΰ��̸� return
			return;
		cout << arr[x] << " ";
		if (x * 2 <= currentSize) PreorderT(x * 2); //���� ����Ʈ��
		if (x * 2 + 1 <= currentSize) PreorderT(x * 2 + 1);//�����ʳ��



	}

	void PostorderT(int x)
	{
		if (arr[x] == NULL) //�迭�� �ΰ��̸� return
			return;
		if (x * 2 <= currentSize) PostorderT(x * 2);//�����ʳ��
		if (x * 2 + 1 <= currentSize) PostorderT(x * 2 + 1);//�����ʳ��
		cout << arr[x] << " ";
	}
};

int main() {
	int size = 0;

	int num = 0;


	cin >> size;

	Heap h = Heap(size);

	for (int i = 1; i <= size; i++) {
		cin >> num;
		h.Insert(num);
	}

	char c = ' ';

	while (c != 'X')
	{
		cin >> c;
		switch (c) {
		case 'E':
			h.ExtractMin();
			break;
		case 'P':
			h.PreorderT(1);
			break;
		case 'I':
			h.InorderT(1);
			break;
		case 'T':
			h.PostorderT(1);
			break;
		default:
			break;
		}
	}



}