[230602] 자료구조 과제6: 연결 리스트와 힙

※문제설명

데이터가 뒤죽박죽 섞여있는 리스트 세 개가 주어지고 이를 category와 data를 기준으로 정렬하는 과제

※구현할 클래스

LinkedNode
LinkedList
HeapNode
MinHeap

※구현할 함수

void sortThreeListsByCategory(LinkedList* list1, LinkedList* list2, LinkedList* list3) : 매개 변수인 세 개의 연결 리스트를 모두 각 category에 맞게 합친 후 오름차순으로 정렬한다.
LinkedList* sortThreeListsByDataOnly(LinkedList* list1, LinkedList* list2, LinkedList* list3) : 매개 변수인 세 개의 연결 리스트를 한꺼번에data를 기준으로 오름차순으로 정렬 후 새롭게 정렬된 리스트로 반환한다.

※출력 화면

전체 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT	100

inline void error(char* str) {
	fprintf(stderr, "%s\n", str);
	exit(1);
};

class LinkedNode {
	LinkedNode* link;
	int data;
	char category;
public:
	LinkedNode(char c = NULL, int d = 0) : link(NULL), data(d) { category = c; }
	LinkedNode* getLink() { return link; }
	void setLink(LinkedNode* next) { link = next; }
	char getCategory() { return category; }
	void setCategory(char c) { category = c; }
	void displayCatAndData() { printf("<%c %d> ", category, data); }
	void displayData() { printf("<%d> ", data); }
	int getData() { return data; }

	void insertNext(LinkedNode *n) { 
		if (n != NULL) {
			n->link = link;
			link = n;
		}
	}
	LinkedNode* removeNext() { 
		LinkedNode* removed = link;
		if (removed != NULL) link = removed->link;
		return removed;
	}
};

class LinkedList {
public:
	LinkedNode org;

	LinkedList() : org(0, NULL) { }
	~LinkedList() { clear(); }

	void clear() { while (!isEmpty()) delete remove(0); }
	LinkedNode* getHead() { return org.getLink(); }
	bool isEmpty() { return getHead() == NULL; }

	LinkedNode* getEntry(int pos) { 
		LinkedNode* n = &org;
		for (int i = -1; i < pos; i++, n = n->getLink())
			if (n == NULL) break;
		return n;
	}

	void insert(int pos, LinkedNode *n) {
		LinkedNode* prev = getEntry(pos - 1);
		if (prev != NULL) prev->insertNext(n);
	}

	LinkedNode* remove(int pos) {
		LinkedNode* prev = getEntry(pos - 1);
		return prev->removeNext();
	}

	int size() {
		int count = 0;
		for (LinkedNode* p = getHead(); p != NULL; p = p->getLink()) count++;
		return count;
	}

	void displayCatAndData(const char* str = "List" ) { 
		printf("%s [list size %d] : ", str, size());
		for (LinkedNode* p = getHead(); p != NULL; p = p->getLink()) p->displayCatAndData();
		printf("\n");
	}

	void displayData(const char* str = "List" ) { 
		printf("%s [list size %d] : ", str, size());
		for (LinkedNode* p = getHead(); p != NULL; p = p->getLink()) p->displayData();
		printf("\n");
	}
};

class HeapNode {
public:
	int		key;

	HeapNode(int k = 0) : key(k) { }
	bool hasKey(int val) { return key == val; }
	void setKey(int k) { key = k; }
	int getKey() { return key; }
};

class MinHeap {
public:

	HeapNode node[MAX_ELEMENT];
	int size;
	MinHeap() : 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[i * 2]; }
	HeapNode& getRight(int i) { return node[i * 2 + 1]; }

	void insert(int key) {
		if (isFull()) return;
		int i = ++size;
		while (i != 1 && key < getParent(i).getKey()) {
			node[i] = getParent(i);
			i /= 2;
		}
		node[i].setKey(key);
	}

	HeapNode remove() {
		if (isEmpty()) return NULL;
		HeapNode item = node[1];
		HeapNode last = node[size--];
		int parent = 1;
		int child = 2;
		while (child <= size) {
			if (child < size && getLeft(parent).getKey() > getRight(parent).getKey()) child++;
			if (last.getKey() <= node[child].getKey()) break;
			node[parent] = node[child];
			parent = child;
			child *= 2;
		}
		node[parent] = last;
		return item;
	}

	HeapNode find() { return node[1]; }

};


void sortThreeListsByCategory(LinkedList* list1, LinkedList* list2, LinkedList* list3) { 
	LinkedList* listA = new LinkedList();
	LinkedList* listB = new LinkedList();
	LinkedList* listC = new LinkedList();
	LinkedList* list_lp[3] = { list1, list2, list3 };
	LinkedList* list_ap[3] = { listA, listB, listC };
	
	//같은 category끼리 분류
	for (int i = 0; i < 3; i++) {
		for (LinkedNode* p = list_lp[i]->getHead(); p != NULL; p = p->getLink()) {
			LinkedNode* tmp = new LinkedNode(p->getCategory(), p->getData());
			if (p->getCategory() == 'A') listA->insert(0, tmp);
			else if (p->getCategory() == 'B') listB->insert(0, tmp);
			else if (p->getCategory() == 'C') listC->insert(0, tmp);
		}
	}

	//같은 category끼리 정렬
	list1->clear(); list2->clear(); list3->clear();
	for (int i = 0; i < 3; i++) {
		MinHeap* heap = new MinHeap();
		for (LinkedNode* p = list_ap[i]->getHead(); p != NULL; p = p->getLink()) 
			heap->insert(p->getData());

		char tmpCategory = list_ap[i]->getHead()->getCategory(); int n = heap->size;
		for (int j = 0; j < n; j++) 
			list_lp[i]->insert(list_lp[i]->size(), new LinkedNode(tmpCategory, heap->remove().key));
		delete heap;
	}
}


LinkedNode* SrchCategory(LinkedList* list1, LinkedList* list2, LinkedList* list3, int SrchData) {
	LinkedList* list_lp[3] = { list1, list2, list3 };
	LinkedNode* tmp = new LinkedNode;

	for (int i = 0; i < 3; i++) {
		for (LinkedNode* prev = &list_lp[i]->org, *curr = prev->getLink(); curr != NULL; prev = prev->getLink(), curr = curr->getLink()) {
			if (curr->getData() == SrchData) {
				tmp = prev->removeNext();
				return tmp;
			}
		}
	}

}

LinkedList* sortThreeListsByDataOnly(LinkedList* list1, LinkedList* list2, LinkedList* list3) { 
	LinkedList* list4 = new LinkedList();
	LinkedList* list_lp[3] = { list1, list2, list3 };
	MinHeap* heap = new MinHeap();

	for (int i = 0; i < 3; i++) {
		for (LinkedNode* p = list_lp[i]->getHead(); p != NULL; p = p->getLink())
			heap->insert(p->getData());
	}

	int n = heap->size;
	for (int j = 0; j < n; j++) 
		list4->insert(list4->size(), SrchCategory(list1, list2, list3, heap->remove().key));

	return list4;
}



int main()
{
	LinkedList *list1 = new LinkedList();
	LinkedList *list2 = new LinkedList();
	LinkedList *list3 = new LinkedList();

	list1->insert(0, new LinkedNode('A', 331));
    list1->insert(0, new LinkedNode('C', 79));
    list1->insert(0, new LinkedNode('A', 21));
    list1->insert(0, new LinkedNode('C', 87));
    list1->insert(0, new LinkedNode('B', 471));
    list1->insert(0, new LinkedNode('C', 130));
    list1->insert(0, new LinkedNode('A', 27));
    list1->insert(0, new LinkedNode('B', 93));


	list2->insert(0, new LinkedNode('C', 103));
    list2->insert(0, new LinkedNode('A', 421));
    list2->insert(0, new LinkedNode('C', 112));
    list2->insert(0, new LinkedNode('A', 336));
    list2->insert(0, new LinkedNode('B', 421));
    list2->insert(0, new LinkedNode('C', 331));
    list2->insert(0, new LinkedNode('A', 521));
    list2->insert(0, new LinkedNode('B', 31));


	list3->insert(0, new LinkedNode('C', 93));
    list3->insert(0, new LinkedNode('B', 189));
    list3->insert(0, new LinkedNode('A', 66));
    list3->insert(0, new LinkedNode('B', 672));
    list3->insert(0, new LinkedNode('B', 79));
    list3->insert(0, new LinkedNode('A', 81));
    list3->insert(0, new LinkedNode('C', 303));
    list3->insert(0, new LinkedNode('B', 269));

	printf("Unsorted and mixed lists\n");
	list1->displayCatAndData();
	list2->displayCatAndData();
	list3->displayCatAndData();
	printf("\n\n");

	sortThreeListsByCategory(list1, list2, list3);
	printf("Sorting three lists based data and category\n");
	list1->displayCatAndData();
	list2->displayCatAndData();
	list3->displayCatAndData();	
	printf("\n\n");

	printf("Sorting three lists based data only\n");
	LinkedList* list4 = sortThreeListsByDataOnly(list1, list2, list3);
	list4->displayData();
	//list4->displayCatAndData();


	return 0;
}

**void sortThreeListsByCategory(LinkedList* list1, LinkedList* list2, LinkedList* list3)**

void sortThreeListsByCategory(LinkedList* list1, LinkedList* list2, LinkedList* list3) { 
	LinkedList* listA = new LinkedList();
	LinkedList* listB = new LinkedList();
	LinkedList* listC = new LinkedList();
	LinkedList* list_lp[3] = { list1, list2, list3 };
	LinkedList* list_ap[3] = { listA, listB, listC };
	
	//같은 category끼리 분류
	for (int i = 0; i < 3; i++) {
		for (LinkedNode* p = list_lp[i]->getHead(); p != NULL; p = p->getLink()) {
			LinkedNode* tmp = new LinkedNode(p->getCategory(), p->getData());
			if (p->getCategory() == 'A') listA->insert(0, tmp);
			else if (p->getCategory() == 'B') listB->insert(0, tmp);
			else if (p->getCategory() == 'C') listC->insert(0, tmp);
		}
	}

	//같은 category끼리 정렬
	list1->clear(); list2->clear(); list3->clear();
	for (int i = 0; i < 3; i++) {
		MinHeap* heap = new MinHeap();
		for (LinkedNode* p = list_ap[i]->getHead(); p != NULL; p = p->getLink()) 
			heap->insert(p->getData());

		char tmpCategory = list_ap[i]->getHead()->getCategory(); int n = heap->size;
		for (int j = 0; j < n; j++) 
			list_lp[i]->insert(list_lp[i]->size(), new LinkedNode(tmpCategory, heap->remove().key));
		delete heap;
	}
}

서로 다른 리스트들을 합치고 분류하는 과정에서 다른 리스트들이 같은 과정을 반복하게 되는데 코드의 효율성을 위해서 배열에 미리 필요한 리스트들을 넣어놓고 배열의 인덱스를 포인터로 쓰는 반복문을 작성해보았다.

**LinkedList* sortThreeListsByDataOnly(LinkedList* list1, LinkedList* list2, LinkedList* list3)**

//데이터 값으로 카테고리를 찾는 함수

LinkedNode* SrchCategory(LinkedList* list1, LinkedList* list2, LinkedList* list3, int SrchData) {
	LinkedList* list_lp[3] = { list1, list2, list3 };
	LinkedNode* tmp = new LinkedNode;

	for (int i = 0; i < 3; i++) {
		for (LinkedNode* prev = &list_lp[i]->org, *curr = prev->getLink(); curr != NULL; prev = prev->getLink(), curr = curr->getLink()) {
			if (curr->getData() == SrchData) {
				tmp = prev->removeNext();
				return tmp;
			}
		}
	}
}

문제의 요구사항에는 데이터만을 정렬하는 것이기때문에 이런 함수가 필요없지만 데이터만 정렬후엔 리스트의 특성을 잃어버릴 수 있기때문에 데이터 정렬후에도 노드가 유지되도록 하였다.

LinkedList* sortThreeListsByDataOnly(LinkedList* list1, LinkedList* list2, LinkedList* list3) { 
	LinkedList* list4 = new LinkedList();
	LinkedList* list_lp[3] = { list1, list2, list3 };
	MinHeap* heap = new MinHeap();

	for (int i = 0; i < 3; i++) {
		for (LinkedNode* p = list_lp[i]->getHead(); p != NULL; p = p->getLink())
			heap->insert(p->getData());
	}

	int n = heap->size;
	for (int j = 0; j < n; j++) 
		list4->insert(list4->size(), SrchCategory(list1, list2, list3, heap->remove().key));

	return list4;
}

'학교생활!' 카테고리의 다른 글

[231111] 고급 자료구조 과제3: 그래프 (1)	2023.11.15
[231104] 고급 자바프로그래밍 과제: Puzzle (1)	2023.11.13
[230520] 고급C++프로그래밍: 과제3 (0)	2023.05.31
[230503] 자료구조 과제5: 순환(recursion) (0)	2023.05.07
[230414] 자료구조 과제4: LinkedList클래스 (0)	2023.04.17