다항식의 덧셈을 할 수 있는 poly linked list를 구현해 보자.
#ifndef _LINKEDLIST_
#define _LINKEDLIST_
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct ListNodeType
{
float coef;
int degree;
struct ListNodeType* pLink;
} ListNode;
typedef struct LinkedListType
{
int currentElementCount; // ���� ����� ������ ����
ListNode headerNode; // ��� ���(Header Node)
} LinkedList;
LinkedList* createLinkedList();
int addLLElement(LinkedList* pList, int position, ListNode element);
int removeLLElement(LinkedList* pList, int position);
ListNode* getLLElement(LinkedList* pList, int position);
void clearLinkedList(LinkedList* pList);
int getLinkedListLength(LinkedList* pList);
void deleteLinkedList(LinkedList* pList);
int addPolyNodeLast(LinkedList* pList, float coef, int degree);//다항식 추가
LinkedList* polyAdd(LinkedList* pListA, LinkedList* pListB);//추가
void displayPolyList(LinkedList* pList);//추가
#endif
#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_
#define TRUE 1
#define FALSE 0
#endif
polyLinkedList는 linked list에 비해 3개의 함수가 추가되었다. addPolyNodeLast함수와 polyAdd함수, displayPolyNode함수가 그것이다. 또 linked list와는 다르게 ListNode 구조체의 멤버 변수가 float coef, int degree, struct ListNodeType* pLink로 바뀌었다. 따라서 linked list를 이루는 함수들의 코드가 달라졌을 거라고 우려할 수 있으나 나는 memset등을 이용해 한번에 구조체 멤버변수를 초기화해 주었기 때문에 바뀌지 않았다. 깃허브 코드를 참고해 보자.
int addPolyNodeLast(LinkedList* pList, float coef, int degree)
{
int ret = FALSE;//처음에 0들어있음
ListNode node = {0, };//node 초기화
node.coef = coef;
node.degree = degree;
if (pList != NULL)
{
int length = getLinkedListLength(pList);//pList의 길이 == 추가할 번지
ret = addLLElement(pList, length, node);//addLLElement를 이용해 노드 추가
}
return ret;//addLLEment 성공 시 1, 실패 시 0 들어있음
}
addPolyNodeLast함수의 기능 : 파라미터로 전달받은 coef와 degree를 멤버 변수로 하는 노드를 만들고, 이 노드를 pList의 마지막에 삽입하는 함수. linked list때 구현했던 addLLEment를 이용하면 편하다.
ListNode 변수 node를 만들고, 여기에 coef와 degree를 넣자. 그리고 addLLEmemt를 이용해 node를 pList의 마지막 번지에 넣으면 된다.
LinkedList* polyAdd(LinkedList* pListA, LinkedList* pListB)
{
LinkedList* pResult = NULL;
ListNode* pNodeA = NULL;
ListNode* pNodeB = NULL;
pResult = createLinkedList();
if (pResult == NULL)
{
return (NULL);//malloc 실패
}
pNodeA = pListA->headerNode.pLink;
pNodeB = pListB->headerNode.pLink;
while (pNodeA != NULL && pNodeB != NULL)//case가 3개로 나뉨.
{
if (pNodeA->degree > pNodeB->degree)//A가 B보다 차수가 클때
{
addPolyNodeLast(pResult, pNodeA->coef, pNodeA->degree);
pNodeA = pNodeA->pLink;
}
else if (pNodeA->degree < pNodeB->degree)//B가 A보다 차수가 클 때
{
addPolyNodeLast(pResult, pNodeB->coef, pNodeB->degree);
pNodeB = pNodeB->pLink;
}
else//A와 B가 차수가 같을 때
{
addPolyNodeLast(pResult, pNodeA->coef + pNodeB->coef, pNodeA->degree);
pNodeA = pNodeA->pLink;
pNodeB = pNodeB->pLink;
}
}
while (pNodeA != NULL)//pNodeA만 현재 남아있음 남은 노드 처리 부분.
{
addPolyNodeLast(pResult, pNodeA->coef, pNodeA->degree);
pNodeA = pNodeA->pLink;
}
while (pNodeB != NULL)
{
addPolyNodeLast(pResult, pNodeB->coef, pNodeB->degree);
pNodeB = pNodeB->pLink;
}
return (pResult);
}
polyAdd 함수 기능 : 전달받은 pListA와 pListB에 노드로 이루어진 다항식이 있고, 이 노드들을 이용해 pListA와 pListB를 더해 결과 노드에 저장하는 다항식의 덧셈 기능을 수행하는 함수. 덧셈을 할 때, 3가지의 case가 있을 수 있다.
<case 종류>
1 ) pListA의 노드가 pListB의 노드보다 차수가 큰 경우
2 ) pListB의 노드가 pListA의 노드보다 차수가 큰 경우
3 ) pListA의 노드와 pListB의 노드가 차수가 같은 경우
차수를 비교하기 위해 저번과 같이 노드를 나타낼 구조체 변수 pNodeA와 pNodeB를 선언한다.
pNodeA와 pNodeB가 NULL이 아닐 때까지 위의 case에 맞추어 덧셈을 진행하고, 둘 중 하나라도 NULL이면 덧셈을 할 필요가 없으므로 남은 노드를 처리하는 구문으로 넘어간다. 남은 노드를 결과 LinkedList에 addPolyNodeLast로 집어넣으면 남은 노드 처리가 가능해진다.
pNodeA와 pNodeB를 한 칸 씩 이동하며 차수가 같은지를 비교해 결과 노드에 집어넣으면 된다. 이 때, 차수가 같은 것 끼리는 coef만 더하고 degree는 더하지 않는다는 것에 유의하자.