[C/자료구조] 연결 리스트 다항식 덧셈

연결 리스트를 이용하여 희소 다항식을 표현

동적 메모리를 이용한 단순 연결 리스트로 표현하였음

 

• 한 개의 노드는 data / link 2가지의 값을 가짐 (data는 현재 노드의 값, link는 다음 노드의 주소)
• 노드의 data는 '계수(coef)'와 '차수(expn)'값을 가짐
• 이때, 연결 리스트는 '차수' 내림차순 정렬된 형태를 가짐

 

두 다항식을 더하는 add_poly 함수 구현

• 두 리스트 list1, list2 를 인자로 받음
• 두 다항식을 더한 결과 리스트 ListType* new_poly 생성 및 초기화
• 두 리스트의 감시할 노드를 가르키는 ListNode* h1, *h2 생성, 각 리스트의 head로 초기화
• h1 또는 h2 가 하나라도 NULL 값이 아니면 반복
• h1이 NULL인 경우, h2 노드에 연결된 모든 노드를 new_poly에 추가(insert)
• h2가 NULL인 경우, h1 노드에 연결된 모든 노드를 new_poly에 추가(insert)
• 두 감시 노드 모두 NULL이 아닌 경우

        - h1 노드와 h2 노드의 data.expon 값을 비교

        - 두 노드의 차수가 같은 경우

               - 두 노드의 계수(data.coef)를 더한 값을 new_poly 에 추가, 더한 값이 0이면 추가하지 않음

               - 두 노드를 각 노드의 링크로 변경

        - 한쪽 노드의 차수가 다른 노드의 차수보다 더 큰 경우

               - 큰쪽 노드의 계수와 차수를 new_poly에 추가, 큰쪽 노드를 큰쪽 노드의 링크로 변경

 

- 소스코드

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

#pragma region ListADTCode

typedef struct {
	int coef;
	int expon;
} element;

typedef struct _ListNode {
	element data; struct _ListNode* link;
} ListNode;

typedef struct _ListType {
	int size;
	ListNode* head;
} ListType;

// 리스트 생성
ListType* create_list() {
	ListType* list = (ListType*)malloc(sizeof(ListType));
	if (list == NULL) {
		fprintf(stdout, "리스트 동적 메모리 할당 실패");
		exit(1);
	}
	list->size = 0;
	list->head = NULL; return list;
}

// 리스트 해제
void free_list(ListType* list) {
	ListNode* node = list->head; ListNode* temp; while (node != NULL) {
		temp = node->link; free(node); node = temp;
	}
	free(list);
}

// 노드 생성
ListNode* create_node(int coef, int expon) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL) {
		fprintf(stdout, "노드 동적 메모리 할당 실패");
		exit(1);
	}
	element data;
	data.coef = coef;
	data.expon = expon;
	node->data = data;
	node->link = NULL;

	return node;
};

// 리스트에 값 추가
ListType* insert(ListType* list, int coef, int expon) {
	// 현재 노드
	ListNode* node = list->head; // 이전 노드
	ListNode* prev = NULL;
	
	// 새로운 node 를 넣을 위치를 갱신
	// 현재 노드가 존재하고, (새로운 차수값 < 현재 차수 값) 이면 다음 위치로 이동
	// 다음 위치로 이동
	// expon : 현재 추가하고자 하는 차수값
	// node->data.coef : 계수
	// node->data.expon : 차수
	while (node != NULL && expon < node->data.expon) {
		prev = node; node = node->link;
	}ListNode* new_node = create_node(coef, expon);
	// 이전 노드 값이 없는 경우
	// => 노드가 없거나, 첫 노드의 값이 더 큰 경우
	if (prev == NULL) {
		// list 맨 앞에 new_node 를 추가
		new_node->link = list->head;
		list->head = new_node;
	}
	// 이전 노드 값이 있는 경우
	else {
		// prev 다음에 new_node 를 추가
		new_node->link = prev->link;
		prev->link = new_node;
	}
	// 리스트 크기를 1 증가
	list->size++;
	return list;
}

// 리스트 출력
void print_list(ListType* list) {
	ListNode* node = list->head; //printf("\n");
	printf("List Size : %d\n", list->size); while (node != NULL) {
		printf("%dx^%d %c", node->data.coef, node->data.expon, (node->link == NULL || (node->link->data.coef < 0)) ?
			'\0' : '+'); node = node->link;
	}
	printf("\n\n");
}
#pragma endregion

// 두개의 다항식을 더하는 함수
ListType* add_poly(ListType* list1, ListType* list2) {
	// 두개의 다항식을 더한 새로운 리스트
	ListType* new_poly = create_list();
	// list1, list2 의 감시 노드
	ListNode* h1 = list1->head; ListNode* h2 = list2->head;
	// h1 또는 h2 가 하나라도 NULL값이 아니면 반복
	// h1이 NULL인 경우
	// h2의 연결된 모든 (계수, 차수)쌍을 new_poly에 추가
	// h2가 NULL인 경우
	// h1의 연결된 모든 (계수, 차수)쌍을 new_poly에 추가
	// h1, h2 모두 NULL이 아닌 경우
	// h1 노드의 차수와 h2 노드의 차수를 비교
	// h1 노드의 차수 == h2 노드의 차수 (h1, h2 차수가 같은 경우)
	// h1 노드의 계수 + h2 노드의 계수가 0이 아닌 경우 new_poly에 추가
	// h1, h2 감시노드 링크로 이동
	// h1 노드의 차수 > h2 노드의 차수
	// h1 노드의 (계수, 차수)쌍을 new_poly에 추가
	// h1 노드를 링크로 이동
	// h2 노드의 차수 > h1 노드의 차수
	// h2 노드의 (계수, 차수)쌍을 new_poly에 추가
	// h2 노드를 링크로 이동
	while (h1 != NULL || h2 != NULL) {
		if (h1 == NULL) {
			while (h2 != NULL) {
				insert(new_poly, h2->data.coef, h2->data.expon); h2 = h2->link;
			}
		}
		else if (h2 == NULL) {
			while (h1 != NULL) {
				insert(new_poly, h1->data.coef, h1->data.expon); h1 = h1->link;
			}
		}
		else {
			if (h1->data.expon == h2->data.expon) {
				int coef = h1->data.coef + h2->data.coef;
				if (coef != 0) {
					insert(new_poly, coef, h1->data.expon);
				}h1 = h1->link; h2 = h2->link;
			}
			else if (h1->data.expon > h2->data.expon) {
				insert(new_poly, h1->data.coef, h1->data.expon); h1 = h1->link;
			}
			else {
				insert(new_poly, h2->data.coef, h2->data.expon); h2 = h2->link;
			}
		}
	}
	return new_poly;
}
int main(void) {
	// 리스트 사용을 위한 준비
	ListType* list1 = create_list();
	ListType* list2 = create_list();

	insert(list1, -7, 10);
	insert(list1, 5, 12);
	insert(list1, 6, 5);
	print_list(list1);

	insert(list2, 5, 10);
	insert(list2, -4, 5);
	insert(list2, 5, 3);
	insert(list2, 3, 2);
	insert(list2, 1, 0);
	print_list(list2);

	ListType* list3 = add_poly(list1, list2);
	print_list(list3);

	free_list(list1);
	free_list(list2);
	free_list(list3);

	return 0;
}

- 실행화면