[C言語]接続リストで多項式の加算を実現



インプリメンテーション

  • による単純接続リスト
  • 項は、同じノードのカウント間に新しいノードを追加し、
  • に接続する.

    構造体と関数のプロトタイプ

    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));
    }

    たこうしきかさん


    新しいリストを作成し、2つの多項式を返します.
    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");
    }

    🔗 接続リストの完全なコード