이번 글에는 Do it C언어 입문(김성엽)
퀴즈 중 18-4번을 푸는 과정에 있었던 고민들을 담으려고 한다.
퀴즈 내용
연결 리스트를 사용하여 성적 처리 프로그램을 만들기
-
연결 리스트의 개념을 사용해 학생 수에 제한이 없도록 한다.
-
1번을 선택할 시 이름과 국어, 영어, 수학 점수를 각각 받아 입력하도록 한다.
-
2번을 선택할 시 저장 된 학생들의 이름과 각 과목의 점수와 총점 평균 그리고 등수까지 출력한다.
-
3번을 선택할 시 프로그램이 종료 되도록 한다.
실행 예시
[MENU]
1. 성적 입력
2. 성적 확인
3. 종료
-----------
선택(1 ~ 3) :
// '1'
1 번째 학생 이름 : 김길동
국어 점수 : 10
영어 점수 : 20
수학 점수 : 30
// '2'
--------------------------------------------------------
이름 국어 영어 수학 총점 평균 등수
--------------------------------------------------------
김길동 10 20 30 60 20.00 1등
처음 작성하던 코드
#include <malloc.h>
#include <stdio.h>
typedef char (*NAME)[14];
typedef struct node {
NAME p_name;
int p_korean;
int p_english;
int p_math;
struct node *next;
} NODE;
void AddNode(NODE **pp_head, NODE **pp_tail, NAME name, int korean, int english,
int math) {
if (NULL != *pp_head) {
(*pp_tail)->next = (NODE *)malloc(sizeof(NODE));
*pp_tail = (*pp_tail)->next;
} else {
*pp_head = (NODE *)malloc(sizeof(NODE));
*pp_tail = *pp_head;
}
(*pp_tail)->p_name = name;
(*pp_tail)->p_korean = korean;
(*pp_tail)->p_english = english;
(*pp_tail)->p_math = math;
(*pp_tail)->next = NULL;
}
void main() {
NODE *p_head = NULL, *p_tail = NULL, *p;
NAME name; // char (*name)[14]
int korean, english, math, index, count = 1;
while (1) {
printf("[MENU]\n");
printf("1. 성적 입력\n");
printf("2. 성적 확인\n");
printf("3. 종료\n");
printf("-----------\n");
printf("선택(1 ~ 3) : ");
scanf("%d", &index);
if (index == 1) {
name = (NAME)malloc(sizeof(char) * 14);
printf("\n%d 번째 학생 이름 : ", count);
scanf("%s", *name);
printf("국어 점수 : ");
scanf("%d", &korean);
printf("영어 점수 : ");
scanf("%d", &english);
printf("수학 점수 : ");
scanf("%d", &math);
AddNode(&p_head, &p_tail, name, korean, english, math);
count++;
} else if (index == 2) {
printf("\n--------------------------------------------------------\n");
printf("이름 국어 영어 수학 총점 평균 등수\n");
printf("\n--------------------------------------------------------\n");
p = p_head;
while(NULL != p){
int local_sum;
local_sum = p->p_korean + p->p_english + p->p_math;
printf("%s %3d %3d %3d %3d %3.2f\n\n", *p->p_name, p->p_korean, p->p_english, p->p_math, local_sum, (double)local_sum / 3);
p = p->next;
} else if (index == 3){
break;
} else{
printf("\n없는 숫자입니다.\n")
}
}
}
free(name);
}미완성 상태라 메모리 해제 기능도 제대로 구현 되있지 않았고 그 외에도 기능적으로도 문제가 많았다.
지난 게시글과 같은 방법으로 연결 리스트를 사용하고 일단 학생 정보를 받는대로 연결 리스트에 저장하고 이를 출력하려고 했었다.
하지만 문제는 등수를 출력하는 순간부터 생겼다.
연결 리스트에 이미 학생들이 대입 된 순간부터 저장된 학생들을 반복문으로 꺼내가면서 비교하기엔
코드가 너무 복잡해지고 ranking만 구하면 되는 퀴즈에서 정렬된 것들을 출력하여 ranking을 매겨주기에는 오히려 비효율적인 코드를 짜고 있다는 생각이 들었다.
이때 해결 방법을 고민하며 CS50 강의에서 봤던 여러 정렬 알고리즘도 생각해봤고 버블 정렬을 복습하며 관련 포스트를 게시하기도 하였다.
그러다 접근 방법을 바꾸게 되었다.
연결 리스트에 대입을 해놓고 정렬하는 방법을 고민하는 것이 아니라, 임시 자료형에 값을 저장하고 이를 대입하기 전에 대입된 값들과 비교하면서 대입하는 것이다.
학생의 순서는 상관이 없었고 등수만 출력하면 됐었기에 간단하게 해결하고자 ranking이라는 변수를 추가해 해결할 수 있었다.
등수 알고리즘
모든 학생들의 ranking을 1로 시작하고 점수를 비교하여 점수가 낮은 학생의 ranking을 1씩 높이는 것이다.
등수 알고리즘 작동 예시
기존 연결 리스트 : 김길동 1등 총점 300점 / 홍길동 2등 총점 200점
->박길동 1등(모든 학생들의 ranking = 1로 시작) 총점 250점이 추가시키려한다
->노드를 돌며 박길동 보다 낮은 사람의 등수++ or 박길동이 낮을시 박길동.등수++
->김길동보다 낮으니 박길동.등수++ -> 다음 노드 : 홍길동보다 높으니 홍길동.등수++
새로운 연결 리스트 : 김길동 1등 총점 300점 / 홍길동 3등 총점 200점 / 박길동 2등 총점 250점
이러한 알고리즘을 사용하여 문제를 해결할 수 있었다.
또한 점수가 같을시에 별다른 행동을 취하지않음으로써 공동 등수도 자동으로 적용되었다.
(공동 1등 2명이 앞에 있을시 다음 등수는 1등 두명을 거치며 1 -> ++ -> ++ -> 3등)
또한 코드를 무작정 작성하다보니, 가독성이 떨어지고 재사용될 수 있을 부분들이 보였다.
그러하여 이를 함수화 시켜 main 함수를 간략화 시킬 필요가 있다고 생각해 함수를 최대한 활용했다.
완성된 코드
#include <malloc.h>
#include <stdio.h>
typedef struct Data {
char name[14];
int korean, english, math;
int ranking;
int total;
float average;
} DATA;
//데이터 저장용
typedef struct node {
DATA data;
struct node *next;
} NODE;
//연결리스트 저장용
void AddNode(NODE **pp_head, NODE **pp_tail, DATA *p_data) {
if (*pp_head == NULL) {
*pp_head = (NODE *)malloc(sizeof(NODE));
*pp_tail = *pp_head; //주소만 다루는거라 1차원으로 접근
} else {
(*pp_tail)->next = (NODE *)malloc(sizeof(NODE)); // tail은 자료형에 접근하는거라 2차원으로 접근
*pp_tail = (*pp_tail)->next;
}
(*pp_tail)->data = *p_data;
(*pp_tail)->next = NULL;
}
void FreeNode(NODE **pp_head, NODE **pp_tail){
NODE *p = *pp_head, *save_next; //주소값 임시 저장용 save_next
while(p != NULL){
save_next = p->next;
free(p);
p = save_next;
}
*pp_head = *pp_tail = NULL; //메모리 할당 해제 후 head, tail 포인터 초기화
}
void UpdateRanking(NODE *pp_head, DATA *p_data){
NODE *p = pp_head;
while(p != NULL){
if(p_data->total < p->data.total){
p_data->ranking++;
}else if(p_data->total > p->data.total){
p->data.ranking++;
}//점수가 같을 경우 둘다 냅두기위해 else가 아니라 elseif를 사용 냅두면 다음 추가될때 공동 1등일 경우 2등이 반복문 돌면서 자동으로 3등처리 됌
p = p->next;
}
}
void InputData(DATA *p_data, int count){
printf("\n%d 번째 학생 이름 : ", count);
scanf("%s", p_data->name);
printf("국어 점수 : ");
scanf("%d", &p_data->korean);
printf("영어 점수 : ");
scanf("%d", &p_data->english);
printf("수학 점수 : ");
scanf("%d", &p_data->math);
printf("\n\n");
p_data->ranking = 1;
p_data->total = p_data->korean + p_data->english + p_data->math;
p_data->average = p_data->total / 3.0f;
}
void CheckData(NODE *p_head){
NODE *p = p_head;
printf("\n--------------------------------------------------------\n");
printf("이름 국어 영어 수학 총점 평균 등수\n");
printf("\n--------------------------------------------------------\n");
while (p != NULL) {
printf("%s %3d %3d %3d %3d %3.2f %2d등\n\n", p->data.name, p->data.korean,
p->data.english, p->data.math, p->data.total, p->data.average, p->data.ranking);
p = p->next;
}
}
void main() {
NODE *p_head = NULL, *p_tail = NULL;
DATA temp;
int index, count = 0;
while (1) {
printf("[MENU]\n");
printf("1. 성적 입력\n");
printf("2. 성적 확인\n");
printf("3. 종료\n");
printf("-----------\n");
printf("선택(1 ~ 3) : ");
scanf("%d", &index);
if (index == 1){
InputData(&temp, ++count); //1을 추가한상태로 count를 매개변수에 대입
UpdateRanking(p_head, &temp); //연결리스트에 집어넣고 정렬하는 방식의 어려움에서 벗어나기 위해 temp에 임시로 저장해놓고 UpdataRanking 함수를 추가할때마다 사용해 등수를 작거나 크면 ++하는 방식으로 정렬 시킨 상태로 연결리스트에 추가하는 방식을 사용
AddNode(&p_head, &p_tail, &temp);
}else if (index == 2) {
CheckData(p_head);
}else if (index == 3) {
break;
}
else {
printf("\n없는 숫자입니다.\n");
}
}
FreeNode(&p_head, &p_tail);
}실행 결과
[MENU]
1. 성적 입력
2. 성적 확인
3. 종료
-----------
선택(1 ~ 3) : 1
1 번째 학생 이름 : 김길동
국어 점수 : 10
영어 점수 : 20
수학 점수 : 30
[MENU]
1. 성적 입력
2. 성적 확인
3. 종료
-----------
선택(1 ~ 3) : 박길동
2 번째 학생 이름 : 국어 점수 : 20
영어 점수 : 30
수학 점수 : 40
[MENU]
1. 성적 입력
2. 성적 확인
3. 종료
-----------
선택(1 ~ 3) : 이길동
3 번째 학생 이름 : 국어 점수 : 40
영어 점수 : 50
수학 점수 : 60
[MENU]
1. 성적 입력
2. 성적 확인
3. 종료
-----------
선택(1 ~ 3) : 홍길동
4 번째 학생 이름 : 국어 점수 : 10
영어 점수 : 20
수학 점수 : 30
[MENU]
1. 성적 입력
2. 성적 확인
3. 종료
-----------
선택(1 ~ 3) : 2
--------------------------------------------------------
이름 국어 영어 수학 총점 평균 등수
--------------------------------------------------------
김길동 10 20 30 60 20.00 3등
박길동 20 30 40 90 30.00 2등
이길동 40 50 60 150 50.00 1등
홍길동 10 20 30 60 20.00 3등코드 설계시 참고한 구조도
코드를 짜기 전 쉽게 짜기 위해 작성한 코드의 틀이다. 지운 내용도 많지만 대충 틀은 이렇다.
-
헤드에 아무것도 없으면 헤드에 노드 및 데이터 추가 후 테일 포인터에 헤드 주소 넣기
-
헤드에 뭐 있으면 테일로 가서 노드 및 데이터 추가 후 테일 포인터 다음 주소로 넣고 다음 주소에 NULL 넣기
-
메인 함수에선 변수에 받아서 함수 사용해서 입력
-
출력할때는 시작 노드 위치 안 잃어버리도록 p에다가 옮겨서 NULL일때까지 p=p->next; 이용해서 출력 이번 코드 등수를 못구함 -> 함수 최대한 활용하기
-
출력 함수
-
input 함수 -> temp에 저장 후 연결리스트와 비교해서 비교하고 나중에 연결리스트에 추가
-
비교함수 -> temp와 안에 모든 걸 비교하면서 크거나 작으면 1 더하기
-
free 함수
포인터를 사용할일이 많다보니 다중 포인터의 주소 등 헷갈리던 개념들이 좀 정리된 기분이고
노드의 사용도 처음엔 너무 어려워서 포인터와 메모리 할당의 개념들을 복습해야 했지만 좀 익은 것 같다.
파일 입출력으로 넘어가기 전에 연결 리스트를 버블 정렬로 정렬하는 방법과 크기를 비교한 후에 원하는 위치에 노드를 추가하는 방법 등도 다뤄보려고 한다.
나중에 자료구조 책에서도 나올 개념이지만 미리 공부해서 나쁠건 없으니 !
여기서 포스트를 마친다.
