[자료구조] 2020.07.22

1. 리스트를 이용하여 학생 성적 프로그램 만들기

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

typedef struct NODE {
	int data;
	struct NODE* next;
}N;

void add(N* root, int data) {
	N* node = (N *)malloc(sizeof(N));
	node->data = data;
	node->next = NULL;
	
	// 노드 생성
	// 마지막노드의 next가 매번 새로운 노드를 가리킬수있도록 해야함!
	N *p = root;
	while (p->next != NULL) { // 마지막노드를 찾기위해 [p->next] 작성!!!
		if (p->next->data == data) {
			printf("%d는 이미 존재합니다.\n", data);
			return;
		}
		else if (p->next->data > data) {
			node->next = p->next;
			break;
		}
		p = p->next;
	}

	p->next = node;

}
void nodeRemove(N *root, int data) {
	N *p = root;

	while (p->next != NULL) {
		if (data == p->next->data) {
			p->next = p->next->next;
			return;
		}
		p = p->next;
	}

	printf("%d는 존재하지않는 데이터입니다.\n", data);

}
void show(N *root) {
	printf("show(): ");

	N *p = root->next;

	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
		if (p != NULL) {
			printf("-> ");
		}
	}

	printf("\n");

}
int main() {

	N * head = (N*)malloc(sizeof(N));
	head->next = NULL;

	int act;
	while (1) {
		printf("1.삽입 2.삭제 3.출력 4.종료\n");
		printf("번호입력: ");
		scanf("%d", &act);
		if (act == 1) {
			int data;
			printf("데이터입력: ");
			scanf("%d", &data);
			add(head, data);
		}
		else if (act == 2) {
			int data;
			printf("데이터입력: ");
			scanf("%d", &data);
			nodeRemove(head, data);
		}
		else if (act == 3) {
			show(head);
		}
		else {
			printf("프로그램종료\n");
			break;
		}
	}

	return 0;
}

 

 

2. 팽이팽이달팽이 문제(백준 알고리즘 문제)

 : 영진이는 달팽이를 좋아한다.

   달팽이를 너무너무 좋아하기 때문에 특정한 모양의 단방향 연결리스트에 달팽이 리스트라는 이름을 붙여주었다.
   
   일반적인 선형 단방향 연결리스트의 각 노드 번호를 연결된 순서대로 1, 2, ..., N이라 하자.

   이때 N번 노드는 아무 노드도 가리키지 않는데, 여기서 N번 노드가 1번 노드를 제외한 임의의 노드를

   가리켜 사이클을 이루게 되는 리스트를 달팽이 리스트라고 한다.

   달팽이 리스트는 각 노드당 하나의 정수를 저장한다.
   
   즉, 달팽이 리스트는 다음과 같이 생긴 연결리스트이다. 노드 안의 수는 저장된 값을 뜻한다.
   
   "달팽아 달팽아 1번 노드부터 한 칸씩 총 K번 이동해 도착한 노드엔 어떤 값이 있을까?"
   영진이는 어두운 방 안에서 달팽이 리스트 하나를 쓱쓱 그리더니, 같은 말을 K만 바꿔가며 계속 중얼거렸다.
   영진이의 상태가 심상치 않아 보인다... 상황이 더 악화되기 전에 영진이의 모든 질문에 대답해주도록 하자.

   [입력] 
   첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000),

   질문의 횟수 M(1 ≤ M ≤ 200,000),

   N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다.
   둘째 줄에 N개의 정수 C1, C2, …, CN이 공백으로 구분되어 주어진다.

   이때 Ci는 i번 노드에 저장된 값을 뜻한다. (1 ≤ Ci ≤ 1,000,000)
   셋째 줄부터 M개의 줄에 걸쳐 각 질문에 해당하는 K(1 ≤ K ≤ 109)가 주어진다.
   
   [출력] 
   M개의 줄에 걸쳐 각 질문의 답을 출력한다.

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

typedef struct NODE {
	int data;
	struct NODE* next;
}N;
void add(N* root, int data) {
	N* node = (N*)malloc(sizeof(N));
	node->data = data;
	node->next = NULL;

	N* p = root;
	while (p->next != NULL) {
		p = p->next;
	}

	p->next = node;
}
void addd(N* root, int data, int c) {
	N* node = (N *)malloc(sizeof(N));
	node->data = data;
	node->next = NULL;
	N* p = root;

	while (p->next != NULL) {
		c--;
		if (c == 0) {
			node->next = p->next;
		}
		p = p->next;
	}

	p->next = node;
}
void show(N* root) {
	printf("show(): ");
	N* p = root->next;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
		if (p != NULL) {
			printf("-> ");
		}
	}
	printf("\n");
}

int main() {

	N* head = (N*)malloc(sizeof(N));
	head->next = NULL;

	int n, c;
	scanf("%d%d", &n, &c);
	for (int i = 0; i < n - 1; i++) {
		int data;
		scanf("%d", &data);
		add(head, data);
	}
	int data;
	scanf("%d", &data);
	addd(head, data, c);
	show(head);

	return 0;
}

3. 자료구조 
1) 스택 vs 큐 
   [스택] FIFL 선입후출
            ex) 최근 방문한 웹 페이지, 실행 취소
            -> push(), pop(), peek(), isEmpty(), full(), size()

   [큐] FIFO 선입선출
        ex) 예약, 대기열
        -> Enqueue(), Dequeue(), isEmpty(), isFull(), size()
        -> front(), back() == rear()

2) 트리 
 : 노드 이용하여 구현(주소부가 2개인 노드 -> 이진트리)


4. 알고리즘
** 탐색(=검색) > 탐색(=검색)을 빠르게 하기 위해서는 정렬이 필요
** [정렬] -> [버블], [삽입, 선택], 합병, [퀵], 도수, 셀...

                   └ 이번 수업을 통해 버블, 삽입, 선택, 퀵까지 배울 예정

 

 

5. 배열을 이용하여 스택 구현

** 못한 부분은 다음 시간에 배울 예정

#include <stdio.h>
#define MAX 5

int stack[MAX];
int index = -1;	// 인덱스는 0번째부터 시작하기 때문에 -1을 index에 저장
						// 책에 따라, 상황에 따라 index 시작점은 다를 수 있다

int isFull() {
	if (index == MAX - 1) {	// MAX-1을 하는 이유는 검사 후 저장해야하기 때문에
										// MAX로 한다면 이미 꽉 찬 상태에서 저장을 하려고 하기 때문에 문제가 생김
		return 1;	// 스택이 가득차 있을 때 1을 리턴!
	}
	return 0;
}
void push(int data) {
	if (isFull()) {		// 위에서 아래로 읽기 때문에 push보다 위에 isFull 함수가 있어야 함
		printf("가득차서 입력 불가합니다!\n");
		return;
	}
	index++;
	stack[index] = data;
}
int size() {
	return index + 1;
}

int main() {
	int act;

	while (1) {
		printf("1. push() 2. pop() 3. peek() 4. size() 5. 종료\n");
		printf("번호 입력 : ");
		scanf("%d", &act);

		if (act == 1) {
			// 데이터를 스택에 입력하는 액션

			if (isFull()) {
				// 데이터를 입력하기도 전에 꽉 차 있다는 경고창과 함께
				// 입력을 스킵하고 싶다면
				// 여기에 isFull하면 된다
				printf("가득차서 입력 불가합니다!\n");
				continue;
			}

			printf("데이터 입력 : ");
			int data;
			scanf("%d", &data);
			push(data);
		}
		else if (act == 2) {

		}
		else if (act == 3) {

		}
		else if (act == 4) {
			// 스택에 들어있는 데이터의 개수
			// 수위, LEVEL, 높이
			printf("데이터 개수는 %d개 입니다.\n", size());
		}
		else {
			printf("종료\n");
			break;
		}
	}

	return 0;
}