[자료구조] 스택, 큐, 트리, 검색, 정렬을 사용한 코인 노래방 프로그램

development activity/C Language

[자료구조] 스택, 큐, 트리, 검색, 정렬을 사용한 코인 노래방 프로그램

Choi Hyun Seok 2016. 6. 30. 13:13

C언어 자료구조 스택과 큐, 트리, 검색 2개, 정렬 3개를 이용하여

코인노래방 프로그램 작성하기

* 검색 2개 사용 : 이진트리검색, 순차검색

* 정렬 3개 사용 : 버블정렬, 트리정렬, 선택정렬

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

typedef char element; //스택 element
typedef int qelement; //큐 element

/*----------------------------------------스택----------------------------------------*/

typedef struct stackNode {
	element data;
	struct stackNode *link;
} stackNode ;

stackNode *top;

element push(element item) {
	stackNode *new;
	new = (stackNode*)malloc(sizeof(stackNode));

new->data=item;
	new->link=top;
	top=new;
}

element pop() {
	element temp;
	stackNode *old = top;
	if(top == NULL) {
		return 0;
	} else {
		temp=old->data;
		top=old->link;
		free(old);
		return temp;
	}
}

int infix_to_postfix(element *exp1) { //후위표기법으로 변환
	int i=0;
	int j=0;
	element symbol;
	element *exp2 = (element*)malloc(sizeof(element));

while(1) {

symbol=exp1[i++];

switch(symbol) {
			case '+' : push(symbol); break;
			case '\0' : while(top != NULL) {
				exp2[j++] = pop(); }
				printf("\n\n\t******************************************\n");
				printf("\t\t     코인 : %d개 입니다!\n", evalPostfix(exp2));
				printf("\t\t     %d곡 선택해 주세요.\n", evalPostfix(exp2));
				printf("\t******************************************\n\n\n");
				music_choice(evalPostfix(exp2)); //Queue 로 보냄
				return 0;
			default : exp2[j++] = symbol; break;
		}
	}
}

int evalPostfix(element *exp) { //후위표기법으로 변환한 식 계산
	int i = 0;
	int j = -1;
	int opr1, opr2;

element symbol, temp;
	element *exp2 = (element*)malloc(sizeof(element));

while(1) {
		symbol = exp[i++] ;
		switch(symbol) {
			case '+' :
				opr1 = pop();
				opr2 = pop();
				push(opr2 + opr1); break;
			case '\0' : return pop(); break;
			default : push(symbol - '0'); break;
		}
	}
}

/*----------------------------------------큐----------------------------------------*/

typedef struct QNode {
	qelement data;
	struct QNode *link;
} QNode;

typedef struct LQType {
	QNode *front;
	QNode *rear;
} LQType;

LQType *creatLinkedQueue() {
	LQType *LQ = (LQType*)malloc(sizeof(LQType));
	LQ->front = NULL;
	LQ->rear = NULL;
	return LQ;
}

int isEmpty(LQType *LQ) { //데이터가 없는지 확인
	if(LQ->front == NULL) return 1;
	else return 0;
}

void enQueue(LQType *LQ, int menu) { //메뉴 번호 입력
	QNode *new = (QNode*)malloc(sizeof(QNode));

new->data = menu;
	new->link = NULL;

if(isEmpty(LQ)) {
		LQ->front = new;
		LQ->rear = new;
	} else {
		LQ->rear->link = new;
		LQ->rear = new;
	}

printf("\n\n\t------------------------------------------\n");
	printf("\t\t곡 번호 %d번이 예약돼었습니다!\n", menu);
	printf("\t------------------------------------------\n\n\n");

}

int deQueue(LQType *LQ) {
	QNode *old;

if(isEmpty(LQ)) {
		printf("\n\n\t------------------------------------------\n");
		printf("\t\t예약된 곡이 없습니다.\n");
		printf("\t------------------------------------------\n\n\n");
		return 0;
	} else { //처리된 메뉴 번호
		old = LQ->front;
		printf("\n\n\t------------------------------------------\n");
		printf("\t\t 시작 곡 번호 : %d\n", LQ->front->data);
		printf("\t------------------------------------------\n\n\n");

LQ->front = LQ->front->link;

if(isEmpty(LQ)) {
			LQ->rear = NULL;
		}

free(old);

}

int peek_music(LQType *LQ) { // 현재 제일 앞번째 예약 곡 및 남은 예약 곡
	QNode *temp = LQ->front;

if(isEmpty(LQ)) {
		printf("\n\n\t------------------------------------------\n");
		printf("\t\t예약된 곡이 없습니다.\n");
		printf("\t------------------------------------------\n\n\n");
		return 0;
	} else {
		printf("\n\n\t------------------------------------------\n");
		printf("\t 다음에 시작할 곡 번호 : %d\n", LQ->front->data);
		printf("\t 남은 예약 곡 번호 [");
		while(temp) {
			printf(" %d", temp->data);
			temp = temp->link;
		} printf(" ]\n");
		printf("\t------------------------------------------\n\n\n");
	}
}

/*----------------------------------------트리----------------------------------------*/

typedef struct TreeNode {
	int key;
	struct TreeNode *left;
	struct TreeNode *right;
} TreeNode;

TreeNode *insertBST(TreeNode *BST, int x) {
	TreeNode *p, *q, *new;
	p = BST;

while(p != NULL) {
		if(x == p->key) return 0;
		else q=p;
		if(x < p->key) p = p->left;
		else p = p->right;
	}

new = (TreeNode*)malloc(sizeof(TreeNode));
	new->key = x;
	new->left = NULL;
	new->right = NULL;

if(BST == NULL) BST = new;
	else if(x < q->key) q->left = new;
	else q->right = new;
}

/*------------------------------------이진트리검색-------------------------------------*/

TreeNode *searchBST(TreeNode *BST, int x) {
	TreeNode *p = BST;

if(p == NULL) return NULL;
	else if(x == p->key) {
		return p;
	} else if(x < p->key) {
		return searchBST(p->left, x);
	} else {

return searchBST(p->right, x);

}

/*--------------------------------------선택정렬---------------------------------------*/

void selectionSort(int music_chart[], int size) {
	int i, j, min, temp;
	for(i=0 ; i<size-1 ; i++) {
		min = i;
		for(j = i+1 ; j<size ; j++) {
			if(music_chart[j]<music_chart[min]) min = j;
		}
		temp = music_chart[i];
		music_chart[i] = music_chart[min];
		music_chart[min] = temp;
	}
}

/*--------------------------------------순차검색---------------------------------------*/

int music_search() {
	int music_chart[] = {23,46,22,45,58,12,11,65,53,10};
	int size = 10;
	int i = 0;
	int number;

selectionSort(music_chart, size); // 선택정렬사용

printf("\n\t[-------------노래-가수 확인--------------]\n\n");
	printf("\t\t검색 번호 입력 >>  ");
	scanf("%d", &number);

while(i<size && music_chart[i] != number) i++; //순차검색
		if(i<size) {
			printf("\n\n\t------------------------------------------\n");
			printf("\t 순차적으로 %d 번째 곡입니다.\n", i+1);

switch(number) {
				case 23 : printf("\t 23. 나팔바지 - 싸이\n"); break;
				case 46 : printf("\t 46. DADDY - 싸이\n"); break;
				case 22 : printf("\t 22. 북두칠성 - 로이킴\n"); break;
				case 45 : printf("\t 45. 또 다시 사랑 - 임창정\n"); break;
				case 58 : printf("\t 58. 꿀잼 - 다이나믹듀오\n"); break;
				case 12 : printf("\t 12. 바람이나 좀 쐐 - 개리\n"); break;
				case 11 : printf("\t 11. 니가 모르게 - 로꼬\n"); break;
				case 65 : printf("\t 65. 맙소사 - 황태지\n"); break;
				case 53 : printf("\t 53. 위잉위잉 - 혁오\n"); break;
				case 10 : printf("\t 10. 흉터 - 조형우\n"); break;
				default : printf("\n\n\t------------------------------------------\n");
					printf("\t\t      %d번 곡은 없습니다.\n", number);
					break;
			}
		} else { printf("\n\n\t------------------------------------------\n");
		printf("\t\t      %d번 곡은 없습니다.\n", number);
	}
	printf("\t------------------------------------------\n\n\n");
	return 0;
}

/*--------------------------------------트리정렬---------------------------------------*/

void inorder(TreeNode *BST) { //중위순회표기법
	if(BST) {
		inorder(BST->left);
		if(BST->key == 0) {}
		else printf("%d ", BST->key);
		inorder(BST->right);
	}
}

int music_allsearch(TreeNode *BST) {
	int number;

insertBST(BST, 23);
	insertBST(BST, 46);
	insertBST(BST, 22);
	insertBST(BST, 45);
	insertBST(BST, 58);
	insertBST(BST, 12);
	insertBST(BST, 11);
	insertBST(BST, 65);
	insertBST(BST, 53);
	insertBST(BST, 10);

while(1) {
		printf("\n\t[--------------곡 유무 확인---------------]\n");
		printf("\t 0. 돌아가기\n\n");
		printf("\t\t검색 번호 입력 >>  ");
		scanf("%d", &number);

switch(number) {
			case 0 : return 0;
			default : if(searchBST(BST, number) != NULL) { //이진트리검색사용
					printf("\n\n\t------------------------------------------\n");
					printf("\t\t      %d번 곡은 있습니다.\n", number);
					printf("\t------------------------------------------\n\n\n");
				} else {
					printf("\n\n\t------------------------------------------\n");
					printf("\t\t      %d번 곡은 없습니다.\n", number);
					printf("\t------------------------------------------\n\n\n");
					printf("\t 곡 번호는 [ ");
					inorder(BST); //트리정렬사용
					printf("]가 있습니다.\n\n\n");
				}
				break;
		}
	}
}

/*--------------------------------------버블정렬---------------------------------------*/

void music_num(LQType *LQ) {
	int a[10] = {23,46,22,45,58,12,11,65,53,10};
	int n = 10;
	int i, j, k, temp, menu;

for(i=n-1 ; i>0 ; i--) {
		for(j=0;j<=i;j++) {
			if(a[j-1]>a[j]) {
				temp = a[j-1];
				a[j-1] = a[j];
				a[j] = temp;
			}
		}
	}

printf("\n\t[----------------번호 순서---------------]\n");

for(k=0 ; k<n ; k++) {
		if(a[k] == 23) printf("\t\t23. 나팔바지 - 싸이\n");
		else if(a[k] == 46) printf("\t\t46. DADDY - 싸이\n");
		else if(a[k] == 22) printf("\t\t22. 북두칠성 - 로이킴\n");
		else if(a[k] == 45) printf("\t\t45. 또 다시 사랑 - 임창정\n");
		else if(a[k] == 58) printf("\t\t58. 꿀잼 - 다이나믹듀오\n");
		else if(a[k] == 12) printf("\t\t12. 바람이나 좀 쐐 - 개리\n");
		else if(a[k] == 11) printf("\t\t11. 니가 모르게 - 로꼬\n");
		else if(a[k] == 65) printf("\t\t65. 맙소사 - 황태지\n");
		else if(a[k] == 53) printf("\t\t53. 위잉위잉 - 혁오\n");
		else printf("\t\t10. 흉터 - 조형우\n");
	}
	printf("\t------------------------------------------\n\n");
}

int music_choice(int coin) { //infix_to_Postfix에서 eval_Postfix 함수로 계산하여 코인 갯수를 넘겨받음
	LQType *LQ = creatLinkedQueue();
	int p, menu;
	p = 1;

printf("\n\t[----------------노래 선택---------------]\n");
	printf("\t\t23. 나팔바지 - 싸이\n");
	printf("\t\t46. DADDY - 싸이\n");
	printf("\t\t22. 북두칠성 - 로이킴\n");
	printf("\t\t45. 또 다시 사랑 - 임창정\n");
	printf("\t\t58. 꿀잼 - 다이나믹듀오\n");
	printf("\t\t12. 바람이나 좀 쐐 - 개리\n");
	printf("\t\t11. 니가 모르게 - 로꼬\n");
	printf("\t\t65. 맙소사 - 황태지\n");
	printf("\t\t53. 위잉위잉 - 혁오\n");
	printf("\t\t10. 흉터 - 조형우\n");
	printf("\t------------------------------------------\n");
	printf("\t\t 0. 번호 순서대로 보기\n\n");

while(p<=coin) { //코인 수만큼

printf("\t\t노래를 선택해주세요 >>  ");
		scanf("%d", &menu);

switch(menu) {
			case 23 :
			case 46 :
			case 22 :
			case 45 :
			case 58 :
			case 12 :
			case 11 :
			case 65 :
			case 53 :
			case 10 :
				enQueue(LQ, menu); break;
			case 0 : music_num(LQ); continue; //버블정렬사용
			default : printf("\n\n\t------------------------------------------\n");
				printf("\t\t 메뉴를 잘못 선택하셨습니다.\n");
				printf("\t------------------------------------------\n\n");
				continue; //코인 빠짐 방지
		}
		p++;
	}

printf("\n\n\t------------------------------------------\n");
	printf("\t\t    노래를 시작해주세요.\n");
	printf("\t------------------------------------------\n\n");

song_start(LQ, coin); //노래 시작
}

int song_start(LQType *LQ, int coin) {
	TreeNode *BST = (TreeNode*)malloc(sizeof(TreeNode));
	int menu;

while(1) {
		printf("\n\t[---------------코인 노래방--------------]\n");
		printf("\t    1. 노래 시작\n");
		printf("\t    2. 다음 곡 & 예약 곡 보기\n");
		printf("\t    3. 곡 번호 검색(곡 유무 확인)\n");
		printf("\t    4. 곡 번호 검색(곡 노래-가수 확인)\n");
		printf("\t    5. 코인 노래방 나가기\n\n");

printf("\t\t 메뉴를 입력주세요 >>  ");
		scanf("%d", &menu);
		switch(menu) {
			case 1 : deQueue(LQ); break;
			case 2 : peek_music(LQ); break;
			case 3 : music_allsearch(BST); break;
			case 4 : music_search(); break;
			case 5 : return 0;
			default :  printf("\n\n\t------------------------------------------\n");
				printf("\t\t 메뉴를 잘못 선택하셨습니다.\n");
				printf("\t------------------------------------------\n\n");
				break;
		}
	}
}

int music_room() {
	element *exp = (element*)malloc(sizeof(element));
	int i;
	int start = 1;
	int j = 0;

while(1) {
		printf("\n\t[---------------코인넣기----------------]\n");
		printf("\t\t      1. 500원(1곡)\n");
		printf("\t\t      2. 1000원(3곡)\n");
		printf("\t\t      3. 노래방 입장\n");
		printf("\t\t      4. 노래방 퇴장\n\n");

printf("\t\t 코인을 넣어주세요 >>  ");
		scanf("%d", &i);

if(start == 1) {
			if(i == 3) {
				printf("\n\n\t------------------------------------------\n");
				printf("\t    코인을 안 넣고 입장할 순 없습니다.\n");
				printf("\t------------------------------------------\n\n");
				continue;
			} else start = start+1;
		}

switch(i) {
			case 1 : exp[j] = '1'; exp[j+1] = '+'; break;
			case 2 : exp[j] = '3'; exp[j+1] = '+'; break;
			case 3 : exp[j] = '0'; infix_to_postfix(exp); return 0;
			case 4 : return 0;
			default : printf("\n\n\t------------------------------------------\n");
				printf("\t\t 메뉴를 잘못 선택하셨습니다.\n");
				printf("\t------------------------------------------\n\n");
				break;
		} j+=2;
	}
}

int main() {
	printf("-------------------------------------------------------\n");
	printf("\t     [자료구조 실습 프로그램]\n\n");
	printf("\n스택, 큐, 트리, 검색 2개, 정렬 3개 이용\n");
	printf("\t프로그램명 : 코인 노래방 프로그램\n");
	printf("-------------------------------------------------------\n");

printf("\t+++++++++++++++++++++++++++++++++++++++++\n\t+\t\t\t\t\t+\n");
	printf("\t+\t\t코인 노래방\t\t+\n\t+\t\t\t\t\t+\n");
	printf("\t+++++++++++++++++++++++++++++++++++++++++\n");

music_room();

// 500원 또는 1000원을 넣어서 코인으로 변환하여 코인 수 만큼 곡 선택 할 수 있음
	// 곡 선택 후 노래를 시작하여 처음 예약된 것 부터 시작해 곡이 지워짐
	// 남은 예약 곡 번호들을 볼 수 있고, 시작될 곡 번호도 볼 수 있음
	// 곡 번호를 검색하여 유, 무를 판단할 수 있음
	// 곡 번호를 검색하여 노래제목-가수 도 알 수 있음
	// 곡 번호를 검색했을 때 없는 번호를 검색하면, 전체 곡 번호를 나열해서 보여줌
	// 곡 번호 순으로 정리하여 볼 수 있음

}

3번의 수정 걸쳐 코인 노래방 완성!

------------------1차 초기 파일------------------

music_room_modify1.c

------------------2차 수정 파일------------------

music_room_modify2.c

------------------3차 최종 파일------------------

music_room.c

저작자표시 비영리 변경금지