[자료구조] 2020.07.20

1. 배열을 이용한 성적 입력 프로그램

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

typedef struct student {
	char name[10];
	int score;
	int num;
}S;

void f1(S *s, int index, int num) {
	printf("이름입력: ");
	scanf("%s", s[index].name);
	printf("성적입력: ");
	scanf("%d", &s[index].score);
	s[index].num = num;
}

void f3(S *s, int index) {
	for (int i = 0; i < index; i++) {
		printf("%d. %s : %d\n", s[i].num, s[i].name, s[i].score);
	}
}

void f4(S *s, int index, int x) {
	for (int i = 0; i < index; i++) {
		if (s[i].num == x) {
			// 성적수정진행
			printf("%s학생의 성적재입력: ", s[i].name);
			scanf("%d", &s[i].score);
			return;
		}
	}
	printf("일치하는 번호가 없습니다!\n");
}

int main() {

	int n;
	scanf("%d", &n); // 학생수
	S *stu = (S *)malloc(n * sizeof(S));
	int index = 0; // 수위,인덱스번호
	int act;
	int num = 1001;
	while (1) {
		printf("1.입력 2.삭제 3.출력 4.수정 5.종료\n");
		printf("수행할번호입력: ");
		scanf("%d", &act);
		if (act == 1) {
			// 최초생성한 학생수보다 더많이 입력할수없음!
			if (index == n) {
				printf("더이상입력불가!\n");
				continue;
			}
			f1(stu, index, num);
			index++;
			num++;
		}
		else if (act == 2) {
			// 가장마지막에 추가한학생 삭제
			// -1명은 불가능!
			if (index == 0) {
				printf("더이상삭제불가!\n");
				continue;
			}
			index--;
		}
		else if (act == 3) {
			f3(stu, index);
		}
		else if (act == 4) {
			printf("수정할학생번호입력: ");
			int x;
			scanf("%d", &x);
			f4(stu, index, x);
			// 수정할학생의 번호입력->성적수정가능
		}
		else {
			printf("프로그램종료\n");
			break;
		}
	}


	return 0;
}

 

 

2. 지금까지는 배열과 구조체 배열을 이용했다.
   배열은 삭제와 삽입(특히 중간에 데이터를 삽입하는것), 크기가 고정되어 있다는 점이 불편하다.

   

   이럴 때, 리스트 == 연결리스트 == 선형리스트 == Linked List를 이용하면 편리하다는 장점이 있으나
   리스트를 사용하면 공간 효율이 좋아지나 구현하기 어렵다는 단점이 있다.

   데이터 필드와 링크 필드 == 노드, NODE

 

 

3. 조세퍼스 순열(요세퍼스 순열)
 : 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수K(<=N)가 주어진다.
   이제 순서대로 K번째 사람을 제거한다.
   한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
   이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
   원에서 사람들이 제거되는 순서를 (N, K)-조세퍼스 순열이라고 한다.

   조세퍼스 순열을 구하는 프로그램을 작성해라 

   ** 입력 
       : 첫째줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다
         (1 <= K <= N <= 5,000)
   
   ** 출력

** 배열 버전

#include<stdio.h>
#include<stdlib.h>
int check(int *d, int a) {
	for (int i = 0; i < a; i++) {
		if (d[i] != 0) {
			return 1;
		}
	}
	return 0;
}
int main() {

	int a, b;
	scanf("%d%d", &a, &b); // 7 3
	int *data = (int *)malloc(a * sizeof(int));
	// [1 0 0 4 5 0 0]
	// "절대 사용하지않을 데이터"
	for (int i = 0; i < a; i++) {
		data[i] = i + 1;
	}
	int i = 0;
	int cnt = 0;
	while (check(data, a)) {
		if (data[i] == 0) {
			i++;
			if (i == a) {
				i = 0;
			}
			continue;
		}
		cnt++;
		if (cnt == b) {
			cnt = 0;
			printf("%d ", data[i]);
			data[i] = 0;
		}
		i++;
		if (i == a) {
			i = 0;
		}
	}

	printf("\n");
	return 0;
}

 

 

4. 리스트

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

typedef struct NODE {
	int data;					// 데이터부, 데이터필드
	struct NODE* next;	// 주소부, 주소필드, 링크필드
}N; // 자기참조 구조체

int main() {

	N *head = (N*)malloc(sizeof(N));

	N *node1 = (N*)malloc(sizeof(N));
	node1->data = 100;
	head->next = node1;

	// 포인터에는 ->, 실제 데이터에는 .을 이용

	N *node2 = (N*)malloc(sizeof(N));
	node2->data = 200;
	node1->next = node2;
	node2->next = NULL;

	// 방문용 포인터 == 순회용 포인터
	N *p = head->next; // node1
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->next;
	}

	printf("\n");

	return 0;
}

 

 

5. 리스트 연습하기

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

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

int main() {

	N* head = (N*)malloc(sizeof(N));

	N* node1 = (N*)malloc(sizeof(N));
	node1->data = 11;
	head = node1;

	N* node2 = (N*)malloc(sizeof(N));
	node2->data = 12;
	node1->next = node2;


	N* node3 = (N*)malloc(sizeof(N));
	node3->data = 13;
	node2->next = node3;

	N* node4 = (N*)malloc(sizeof(N));
	node4->data = 14;
	node3->next = node4;
	node4->next = NULL;

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

	printf("\n");

	return 0;
}

 

 

6. 리스트를 이용하여 학생 성적 프로그램 만들기
** 못한 부분은 다음 시간에 하기로 함

// 1. 삽입
// 2. 삭제
// + 없는 데이터 삭제 못하게 처리
// 3. 출력
// + 중복 없이 오름차순

#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] 작성!!!
		p = p->next;
		printf("%d ", p->data);
	}
	p->next = node;
	printf("\n----------\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) {

		}
		else if (act == 3) {

		}
		else {
			printf("프로그램종료\n");
			break;
		}
	}

	return 0;
}