[C / 자료구조] 6주차 과제 - 대기줄 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode {	// 노드 타입
	char name;				// 승객명
	int arrive_time;		// 도착시간
	int company;			// 동승인원
	struct ListNode* link;
} ListNode;

typedef struct ListType {		// 리스트 헤더 타입
	int size;					// 현재 리스트의 노드 개수
	int num_aboard;				// 현재 리스트의 전체 인원
	char name[10];				// 리스트(그룹)의 이름
	ListNode* head;
	ListNode* tail;
	struct ListType* link;
} ListType;


void error(char* message);
ListType* create(char* name);
void generate_q(ListType* list, char name);
void insert_last(ListType* plist, ListNode* p);
void delete_node(ListType* plist1, ListNode* p);
void poly_print(ListType* plist);
void merge_q(ListType* plist1, ListType* plist2, ListType* plist3);
ListType* next_bus(ListType* list3, int capa, char* name);


int main(void)
{
	// 기본 단계
	ListType* list1, * list2, * list3;

	// 연결 리스트 헤더 생성 - 이름 추가할 수 있게 create 확장
	list1 = create("list1"); generate_q(list1, 'A');
	list2 = create("list2"); generate_q(list2, 'a');
	list3 = create("merged");

	poly_print(list1);  // 고객수와 인원을 출력
	poly_print(list2);

	// 다항식 3 = 다항식 1 + 다항식 2
	merge_q(list1, list2, list3);  // 대기줄을 하나로 합침
	poly_print(list3);

	printf("\n\n=== 도전 단계 ===\n\n");
	char busname[5] = "ABus";

	// 각 버스에는 승차한 고객리스트, bushead는 버스들의 연결리스트 헤더
	ListType* bus = NULL, * bushead = NULL;
	while (list3->size > 0) {
		bus = next_bus(list3, 5, busname); // 5명까지 승차
		busname[0]++;
		bus->link = bushead;
		bushead = bus;
	}
	bus = bushead;
	while (bus != NULL) {
		poly_print(bus);
		bus = bus->link;
	}
	return 0;
}

// user input function
void generate_q(ListType* list, char name)
{
	int n = 0;
	ListNode node;					// 새로 만들 노드의 값을 전달하는 객체 지역변수
	while (1) {
		scanf_s("%d %d", &node.company, &node.arrive_time);
		if (node.company == 0) break;
		node.name = name++;
		insert_last(list, &node);	// 함수에서 생성해서 복사
	}
}

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

// 헤더 초기화 함수
ListType* create(char* name) {
	ListType* tmp = (ListType*)malloc(sizeof(ListType));
	strcpy_s(tmp->name, 10, name);
	tmp->size = 0;
	tmp->num_aboard = 0;
	tmp->link = NULL;		// merge할 리스트의 링크
	tmp->head = NULL;
	tmp->tail = NULL;
	return tmp;
}

void insert_last(ListType* plist, ListNode* p) {
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));
	if (new_node == NULL) error("Memoey empty");
	*new_node = *p;								// 포인터로 들어온 파라미터의 값은 해당 방식으로 복사 가능
	//new_node->arrive_time = p->arrive_time;
	//new_node->company = p->company;
	//new_node->name = p->name;
	new_node->link = NULL;
	if (plist->head == NULL && plist->tail == NULL) {
		plist->head = new_node; plist->tail = new_node;
	}
	else {
		plist->tail->link = new_node;
		plist->tail = new_node;
	}
	plist->size++;
	plist->num_aboard += new_node->company;
}

void poly_print(ListType* plist) {
	int n = 0;
	ListNode* tmp = plist->head;
	printf("%s", plist->name);
	for (; tmp != NULL; tmp = tmp->link) {
		printf("\t%c/%d ( %d) ", tmp->name, tmp->company, tmp->arrive_time);
		n += 1;
		if (n % 5 == 0) printf("\n");
	}
	printf("[%d팀/%d명]\n", plist->size, plist->num_aboard);
}

void merge_q(ListType* plist1, ListType* plist2, ListType* plist3) {
	ListNode* tmp1 = plist1->head; ListNode* tmp2 = plist2->head;
	while (tmp1 && tmp2) {
		if (tmp1->arrive_time == tmp2->arrive_time) {
			if (tmp1->company == tmp2->company) {
				insert_last(plist3, tmp1);
				tmp1 = tmp1->link;
			}
			else if (tmp1->company < tmp2->company) {
				insert_last(plist3, tmp1);
				tmp1 = tmp1->link;
			}
			else {
				insert_last(plist3, tmp2);
				tmp2 = tmp2->link;
			}
		}
		else {
			if (tmp1->arrive_time < tmp2->arrive_time) {
				insert_last(plist3, tmp1);
				tmp1 = tmp1->link;
			}
			else {
				insert_last(plist3, tmp2);
				tmp2 = tmp2->link;
			}
		}
	}
	// remainder
	for (; tmp1 != NULL; tmp1 = tmp1->link) {
		insert_last(plist3, tmp1);
	}
	for (; tmp2 != NULL; tmp2 = tmp2->link) {
		insert_last(plist3, tmp2);
	}
}

void delete_node(ListType* plist1, ListNode* p) {
	ListNode* tmp = plist1->head;
	// case1 p is head
	if (tmp == p) {
		plist1->head = tmp->link;
	}
	// case2
	else {
		while (tmp->link != NULL) {
			if (tmp->link == p) {
				tmp->link = p->link;
				if (plist1->tail == p) {
					plist1->tail = tmp;
				}
				break;
			}
			tmp = tmp->link;
		}
	}
	plist1->num_aboard -= p->company;
	plist1->size--;
	free(p);
}

ListType* next_bus(ListType* list3, int capa, char* name) {
	ListType* new_bus = create(name);
	ListNode* checker = list3->head;		// 순회용 포인터
	while (checker != NULL) {
		if ((new_bus->num_aboard + checker->company) <= capa) {
			insert_last(new_bus, checker);
			ListNode* removed = checker;
			if (checker->link == NULL) {
				delete_node(list3, removed);
				break;
			}
			checker = checker->link;
			delete_node(list3, removed);
			if (new_bus->num_aboard >= capa) break;
		}
		else {
			if (checker->link == NULL) {
				break;
			}
			checker = checker->link;
		}
	}
	return new_bus;
}


/*
2 4 1 13 1 21 1 23 1 28 2 29 0 0
2 1 2 3 2 9 2 13 1 16 1 18 2 24 1 29 2 35 2 43 2 45 2 54 0 0
list1     A/2( 4) B/1(13) C/1(21) D/1(23) E/1(28) F/2(29)
list2     a/2( 1) b/2( 3) c/2( 9) d/2(13) e/1(16) f/1(18) g/2(24) h/1(29) i/2(35) j/2(43) k/2(45) l/2(54)
merged    a/2( 1) b/2( 3) A/2( 4) c/2( 9) B/1(13) d/2(13) e/1(16) f/1(18) C/1(21) D/1(23) g/2(24) E/1(28) h/1(29) F/2(29) i/2(35) j/2(43) k/2(45) l/2(54)


=== 2단계 ===

GBus      l/2(54)
FBus      j/2(43) k/2(45)
EBus      F/2(29) i/2(35)
DBus      g/2(24) E/1(28) h/1(29)
CBus      d/2(13) f/1(18) C/1(21) D/1(23)
BBus      A/2( 4) c/2( 9) e/1(16)
ABus      a/2( 1) b/2( 3) B/1(13)
*/