구현

• 단순 연결 리스트(Singly Linked List) 활용
• 항이 같은 노드의 계수끼리 더한 새 노드를 만들어서 연결

구조체와 함수 원형

typedef struct ListNodeType
{
	float				coef;
	int					degree;
	struct ListNodeType	*pLink;
}	ListNode;

typedef struct LinkedListType
{
	int			currentElementCount; // 현재 저장된 원소의 개수
	ListNode	headerNode;	 // 헤더 노드(Header Node)
}	LinkedList;

int			addPolyElement(LinkedList* pList, ListNode element);	// 다항식 노드 추가
LinkedList	*addPolyLists(LinkedList *list1, LinkedList *list2);	// 다항식 덧셈
void		displayPolyList(LinkedList *list);						// 다항식 출력

함수 정의

노드 추가

int	addPolyElement(LinkedList* pList, ListNode element)
{
	ListNode	*curr;
	int			position;

	if (pList == NULL)
		return (FALSE);
	curr = pList->headerNode.pLink;
	position = 0;
	while (curr)
	{
    	// 인자로 받은 노드의 차수(element)가 현재 탐색 중인 노드(curr)보다 크면 현재 위치에 노드 삽입
		if (element.degree > curr->degree)
			break ;
        // 차수가 같으면 계수끼리 더한 후 기존 차수 노드는 제거한 뒤 현재 위치에 노드 삽입
		if (element.degree == curr->degree)
		{
			element.coef += curr->coef;
			removeLLElement(pList, position);
			break ;
		}
		position++;
		curr = curr->pLink;
	}
	return (addLLElement(pList, position, element));
}

다항식 덧셈

두 다항식을 더한 새로운 리스트를 만들어서 반환

LinkedList	*addPolyLists(LinkedList *list1, LinkedList *list2)
{
	LinkedList	*new_list;
	ListNode	element;
	ListNode	*ptr1;
	ListNode	*ptr2;

	if (list1 == NULL || list2 == NULL)
		return (NULL);
	new_list = (LinkedList *)malloc(sizeof(LinkedList));
	if (new_list == NULL)
		return (NULL);
	ptr1 = list1->headerNode.pLink;
	ptr2 = list2->headerNode.pLink;
    // 두 다항식 리스트 중 하나를 끝까지 탐색할 때까지 반복
	while (ptr1 && ptr2)
	{
    	// 새로 추가할 노드를 일단 A로 세팅
		element = *ptr1;
        // 현재 탐색 중인 A의 차수가 B의 차수보다 크면 A의 포인터를 다음 노드로 옮기기
		if (ptr1->degree > ptr2->degree)
			ptr1 = ptr1->pLink;
        // 현재 탐색 중인 A와 B의 차수가 같으면 두 항의 계수를 더하고 두 리스트의 포인터를 다음 노드로 옮기기
		else if (ptr1->degree == ptr2->degree)
		{
			element.coef += ptr2->coef;
			ptr1 = ptr1->pLink;
			ptr2 = ptr2->pLink;
		}
        // 현재 탐색 중인 B의 차수가 A의 차수보다 크면 새로 추가할 노드를 B의 노드로 세팅하고 B의 포인터를 다음 노드로 옮기기
		else
		{
			element = *ptr2;
			ptr2 = ptr2->pLink;
		}
        // 세팅된 노드를 새 리스트에 삽입
		addLLElement(new_list, new_list->currentElementCount, element);
	}
    // 리스트 A나 B 중 탐색하지 않은 노드가 남았으면 새 리스트에 모두 삽입
	while (ptr1)
	{
		element = *ptr1;
		addLLElement(new_list, new_list->currentElementCount, element);
		ptr1 = ptr1->pLink;
	}
	while (ptr2)
	{
		element = *ptr2;
		addLLElement(new_list, new_list->currentElementCount, element);
		ptr2 = ptr2->pLink;
	}
	return (new_list);
}

다항식 출력

void	displayPolyList(LinkedList *list)
{
	ListNode	*curr;

	if (list == NULL)
		return ;
	curr = list->headerNode.pLink;
	if (curr == NULL)
		printf("empty list");
	while (curr)
	{
		printf("%.1f", curr->coef);
		if (curr->degree)
			printf("x^%i", curr->degree);
		curr = curr->pLink;
		if (curr)
			printf(" + ");
	}
	printf("\n");
}

🔗 연결 리스트 전체 코드