DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 1

C언어로 쉽게 풀어쓴 자료구조

4장 Exercise 문제들이다.

필자가 학교 다니면서 자료구조론 수업을 들었는데,

과제로 제출했던 것들이고,

난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.

자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다.

23번. 두 개의 다항식이 다음과 같이 주어졌다. 이들을 연결 리스트를 이용하여 나타내고 본문의 프로그램을 이용해 두 다항식의 합을 구해보라.

24번. 다항식을 연결 리스트로 표현할 수 있음을 보였다. 다항식이 연결 리스트로 표현되어 있고, p를 다항식을 가리키는 포인터라고 할 때, 어떤 실수 x에 대해 이 다항식의 값을 계산하는 함수 poly_eval을 작성하라.

25번. 다항식이 연결 리스트로 표현되어 있는 경우, 두 개의 다항식을 받아 다항식의 뺄셈을 수행하는 함수 poly_sub를 작성하라. 

<LinkedList.h>

#ifndef __LINKED_LIST_H__
#define __LINKED_LIST_H__
typedef int element;
typedef struct ListNode {
	element expon; // 지수
	element coef; // 계수
	struct ListNode* link;
} ListNode;
// phead: 리스트의 헤드 포인터의 포인터
// p : 선행 노드
// new_node : 삽입될 노드
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node);
// phead : 헤드 포인터에 대한 포인터
// p: 삭제될 노드의 선행 노드
// removed: 삭제될 노드
void remove_node(ListNode** phead, ListNode* p, ListNode* removed);
// 다항식 출력
void display(ListNode* const head);
// 차수 순서가 뒤집어진 항을 정상적으로 출력되게
void display_reverse(ListNode* head);
// 노드를 동적으로 생성
ListNode* create_node(element expon, element coef, ListNode* link);
// 헤드포인터 위치 바꾸기
ListNode* reverse(ListNode* head);
/* 23번 */
ListNode* poly_add(ListNode *list1, ListNode *list2);
/* 24번 */
float poly_eval(ListNode* p, float x);
/* 25번 */
ListNode* poly_sub(ListNode* list1, ListNode* list2);
#endif

<LinkedList.c>

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "LinkedList.h"
// phead: 리스트의 헤드 포인터의 포인터
// p : 선행 노드
// new_node : 삽입될 노드
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node)
{	if (*phead == NULL) {	// 공백리스트인 경우
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) { // p가 NULL이면 첫번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else {			 // p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}
// phead : 헤드 포인터에 대한 포인터
// p: 삭제될 노드의 선행 노드
// removed: 삭제될 노드
void remove_node(ListNode** phead, ListNode* p, ListNode* removed)
{	if (p == NULL)
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
}
// 다항식 출력
void display(ListNode* head)
{	ListNode* p = head;
	// 첫번째 항 출력
	if (p->coef != 1)
		printf("%dX^%d ", p->coef, p->expon);
	else
		printf("X^%d ", p->expon);
	// 두번째 항 이후로
	p = p->link;
	while (p != NULL) {
		// 차수가 0이 아니면
		if (p->expon != 0)
		{
			if (p->coef > 1)
				printf("+%dX^%d ", p->coef, p->expon);
			else if (p->coef == 1)
				printf("+X^%d ", p->expon);
			else
				printf("%dX^%d ", p->coef, p->expon);
		}
		// 차수가 0, 상수항이면
		else
		{
			if (p->coef > 0)
				printf("+%d", p->coef, p->expon);
			else
				printf("%d", p->coef, p->expon);
		}
		p = p->link;
	}
	printf("\n");
}
// 차수 순서가 뒤집어진 식을 정상적으로 출력되게
void display_reverse(ListNode* head)
{	ListNode *newhead;
	newhead = reverse(head);
	display(newhead);
	reverse(newhead);
}
// 노드를 동적으로 생성
ListNode* create_node(element expon, element coef, ListNode* link)
{	ListNode* new_node;
	new_node = (ListNode *)malloc(sizeof(ListNode));
	if (new_node == NULL) {
		fprintf(stderr, "메모리 할당 에러\n");
		exit(1);
	}
	new_node->expon = expon;
	new_node->coef = coef;
	new_node->link = link;
	return(new_node);
}
// 노드 헤드포인터 위치 바꾸기
ListNode* reverse(ListNode* head)
{	ListNode *p, *q, *r;
	p = head;
	q = NULL;
	while (p != NULL)
	{
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	return q;
}
/* 23번 */
ListNode* poly_add(ListNode* list1, ListNode* list2)
{	ListNode* list3 = NULL;
	// 두 리스트가 존재하면
	while (list1 != NULL || list2 != NULL)
	{
		// 만약 첫 번째 식의 차수가 높으면,
		if (list1->expon > list2->expon)
		{
			insert_node(&list3, NULL, create_node(list2->expon, list2->coef, NULL));
			list2 = list2->link;
		}
		// 만약 두 번째 식의 차수가 높으면,
		else if (list1->expon < list2->expon)
		{
			insert_node(&list3, NULL, create_node(list1->expon, list1->coef, NULL));
			list1 = list1->link;
		}
		// 만약 항의 차수가 같으면,
		else
		{
			// 두 항의 계수의 합이 0이면 패스
			if ((list1->coef) + (list2->coef) == 0)
				continue;
			insert_node(&list3, NULL, create_node(list1->expon, (list1->coef) + (list2->coef), NULL));
			list1 = list1->link;
			list2 = list2->link;
		}
	}
	return list3;
}
/* 24번 */
float poly_eval(ListNode* p, float x)
{	float sum = 0.0;
	while (p != NULL)
	{
		sum += (p->coef)*pow(x, p->expon); // 대입 값 계산
		p = p->link;
	}
	return sum;
}
/* 25번 */
ListNode* poly_sub(ListNode* list1, ListNode* list2)
{	ListNode* list3 = NULL;
	// 두 리스트가 존재하면
	while (list1 != NULL || list2 != NULL)
	{
		// 만약 첫 번째 식의 차수가 높으면,
		if (list1->expon > list2->expon)
		{
			insert_node(&list3, NULL, create_node(list2->expon, -(list2->coef), NULL));
			list2 = list2->link;
		}
		// 만약 두 번째 식의 차수가 높으면,
		else if (list1->expon < list2->expon)
		{
			insert_node(&list3, NULL, create_node(list1->expon, list1->coef, NULL));
			list1 = list1->link;
		}
		// 만약 항의 차수가 같으면,
		else
		{
			// 두 항의 계수의 합이 0이면 패스
			if ((list1->coef) + (list2->coef) == 0)
				continue;
			insert_node(&list3, NULL, create_node(list1->expon, (list1->coef) - (list2->coef), NULL));
			list1 = list1->link;
			list2 = list2->link;
		}
	}
	return list3;
}

<main.c>

#include <stdio.h>
#include "LinkedList.h"
int main()
{	ListNode* list1 = NULL;
	ListNode* list2 = NULL;
	ListNode* list3 = NULL;
	ListNode* list4 = NULL;
	ListNode* test = NULL;
	// list1 = 3x^6 +7x^3 -2x^2 -9
	insert_node(&list1, NULL, create_node(6, 3, NULL));
	insert_node(&list1, NULL, create_node(3, 7, NULL));
	insert_node(&list1, NULL, create_node(2, -2, NULL));
	insert_node(&list1, NULL, create_node(0, -9, NULL));
	printf("A(X) : list1\n");
	display_reverse(list1);
	printf("\n");
	// list2 = -2x^6 -4x^4 +6x^2 +6x +1
	insert_node(&list2, NULL, create_node(6, -2, NULL));
	insert_node(&list2, NULL, create_node(4, -4, NULL));
	insert_node(&list2, NULL, create_node(2, 6, NULL));
	insert_node(&list2, NULL, create_node(1, 6, NULL));
	insert_node(&list2, NULL, create_node(0, 1, NULL));
	printf("B(X) : list2\n");
	display_reverse(list2);
	printf("\n");
	// test = x^3 +2x +6
	insert_node(&test, NULL, create_node(3, 1, NULL));
	insert_node(&test, NULL, create_node(1, 2, NULL));
	insert_node(&test, NULL, create_node(0, 6, NULL));
	/* 23번 */
	// list3 = list1 + list2
	printf("23번. C(X) = A(X) + B(X) : list3\n");
	list3 = poly_add(list1, list2);
	display(list3);
	float x, fx;
	printf("X를 입력하세요 : ");
	scanf_s("%f", &x);
	fx = poly_eval(list3, x);
	printf("X=%.1f, C(X) = %f\n\n", x, fx);
	printf("24번. X=2, ");
	display_reverse(test);
	float fy = poly_eval(test, 2);
	printf("답 : %f\n\n",fy);
	/* 25번 */
	// list4 = list1 - list2;
	list4 = poly_sub(list1, list2);
	printf("25번. D(X) = A(X) - B(X) : list4\n");
	display(list4);
	float fz;
	printf("X를 입력하세요 : ");
	scanf_s("%f", &x);
	fz = poly_eval(list4, x);
	printf("X=%1.f, D(X) = %f\n\n", x, fz);
	return 0;
}