[C언어로 쉽게 풀어쓴 자료구조] 연습문제 4강

01 (1)

 

02 (2)

 

03 10, 20

 

04 (4)

 

05 (1)일 때 공백상태, (3)일 때 포화상태

 

06 (3)

 

07 (1)

 

08   1  →  1, 2 →  1, 2, 3  → 1, 2 →  1, 2, 4 →  1, 2, 4, 5  →  1, 2, 4

 

09  A  a, b, c    B  d  →  A  a, b    B   d, c  →   A  a, b, c    B d  →  A  a, b, c    B 'empty'

 

10

#include <stdio.h>
#include <stdlib.h>
#define MAX_ARR_SIZE 6

typedef int element;
typedef struct{
	element *data;
	int capacity;
	int top;
}StackType;

void init_stack(StackType *s){
	s->top=-1;
	s->capacity = 1;
	s->data=(element*)malloc(s->capacity*sizeof(element));
}

int is_empty(StackType *s){
	if(s->top == -1){
		return 1;
	}
	else return 0;
}

int is_full(StackType *s){
	if(s->top == (s->capacity-1)){
		return 1;
	}
	else return 0;
}

void push(StackType *s,element item){
	if(is_full(s)){
		s->capacity *=2;
		s->data =(element*)realloc(s->data,s->capacity*(sizeof(element)));
	}
	s->top ++;
	s->data[s->top]=item;
}

element pop(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	return s ->data[(s->top)--];
}

int main(){
	StackType *s;
	s= (StackType*)malloc(sizeof(StackType));
	init_stack(s);
	
	printf("정수 배열의 크기: %d\n",MAX_ARR_SIZE);
	printf("정수를 입력하시오: ");
	for(int i=0; i<MAX_ARR_SIZE; i++){
		int tmp;
		scanf("%d",&tmp);
		push(s,tmp);
	}
	printf("\n");
	printf("반전된 정수 배열: ");
	for(int i=0;i<MAX_ARR_SIZE;i++){
		printf("%d ",pop(s));
	}
	printf("\n");
	free(s);
	
	return 0;
}

11

#include <stdio.h>
#include <stdlib.h>
#include <string.h> // 코드 10에서 추가

// 스택 코드는 코드10과 동일

int main(){
	StackType *s;
	s= (StackType*)malloc(sizeof(StackType));
	init_stack(s);
	
	int count=0;
	char exp[100];
	char ch;
	scanf("%s",exp);
	for(int i=0;i<strlen(exp);i++){
		ch=exp[i];
		if(ch=='('){
			count++;
			push(s,count);
			printf("%d ",count);
		}
		else if(ch==')'){
			printf("%d ",pop(s));
		}
	}
	printf("\n");
    free(s);
	return 0;
}

12

//위는 10번 문제 스택 코드와 동일

element peek(StackType *s){
	if(is_empty(s)){
		fprintf(stderr,"스택 빔");
		exit(1);
	}
	else return s ->data[(s->top)];
}


int main(){
	StackType *s;
	s= (StackType*)malloc(sizeof(StackType));
	init_stack(s);
	
	int countA=0; 
	int countB=0;
	char exp[100];
	char ch;
	scanf("%s",exp);
	for(int i=0;i<strlen(exp);i++){
		ch=exp[i];
		push(s,ch);
		if(peek(s)=='a'||peek(s)=='A'){
			countA++;	
		}
		else if(peek(s)=='b'||peek(s)=='B'){
			countB++;
		}
	}
	printf("%d%c%d%c",countA,'a',countB,'b');
	printf("\n");
    free(s);
	return 0;
}

13

int main(){
	StackType *s, *s2;
	s= (StackType*)malloc(sizeof(StackType));
	s2= (StackType*)malloc(sizeof(StackType));
	init_stack(s);
	init_stack(s2);
	
	char exp[100];
	char ch;
	scanf("%s",exp);
	push(s,exp[0]); // 첫 숫자는 중복이 없으므로 무조건 스택에 넣는다
	for(int i=1;i<strlen(exp);i++){
		ch=exp[i];
		if(ch!=peek(s)){
			push(s,ch);
		}
	}
	while(!is_empty(s)){
		push(s2,pop(s));
	}
	while(!is_empty(s2)){
		printf("%c ",pop(s2));
	}
	printf("\n");
	free(s);
	free(s2);
	return 0;
}

14

int size(Stacktype *s){
	return s->top + 1;
}

15

for(int i=0;i<MAZE_SIZE;i++){
	for(int j=0; j<MAZE_SIZE;j++){
		if(maze[i][j]=='.'){
			printf("(%d, %d)",i,j);
		}
	}
}

16

int main(){
	StackType *s;
	s= (StackType*)malloc(sizeof(StackType));
	init_stack(s);
	StackType *s2;
	s2= (StackType*)malloc(sizeof(StackType));
	init_stack(s2);
	StackType *s3;
	s3= (StackType*)malloc(sizeof(StackType));
	init_stack(s3);
	
	char exp[100];
	scanf("%[^\n]s",exp);   // 공백을 포함해서 문자열을 입력받기 위해 [^/n]추가
	char ch;
	
	for(int i=0;i<strlen(exp);i++){
		ch=exp[i];
		if(ch<='Z'&&ch>='A'){
			ch = ch+('a'-'A');
			exp[i]=ch;
		}
	}
	for(int i=0;i<strlen(exp);i++){
		ch=exp[i];
		if(ch<='z'&&ch>='a'){
			push(s,ch);
			push(s2,ch);
		}
	}
	while(!is_empty(s2)){
		push(s3,pop(s2));
	}
	
	for(int i=0;i<s3->capacity;i++){
		if(pop(s)!=pop(s3)){
			printf("회문 아님\n");
			break;
		}
		else{
			printf("회문임\n");
			break;
		}
	}
	
	free(s);
	free(s2);
	free(s3);
	
	return 0;
}