C语言循环单链表实现一元多项式相加算法

简介

本文将介绍如何使用C语言的循环单链表结构来实现一元多项式的相加。循环单链表是一种特殊类型的链表，它的最后一个节点指向头节点，形成一个环。这种结构可以方便地进行遍历和操作。

代码实现c#include <stdio.h>#include <stdlib.h>

// 定义循环单链表节点结构typedef struct Node { int coefficient; // 系数 int exponent; // 指数 struct Node* next; // 指向下一个节点的指针} Node;

// 定义循环单链表结构typedef struct LinkedList { Node* head; // 头节点} LinkedList;

// 初始化循环单链表void initLinkedList(LinkedList* list) { list->head = NULL;}

// 在循环单链表尾部插入一个节点void insertNode(LinkedList* list, int coefficient, int exponent) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->coefficient = coefficient; newNode->exponent = exponent; newNode->next = NULL;

if (list->head == NULL) {        list->head = newNode;        newNode->next = newNode; // 将尾节点的next指针指向头节点，构成循环    } else {        Node* temp = list->head;        while (temp->next != list->head) {            temp = temp->next;        }        temp->next = newNode;        newNode->next = list->head;    }}

// 打印循环单链表void printLinkedList(LinkedList* list) { if (list->head == NULL) { printf('The list is empty. '); return; }

Node* temp = list->head;    do {        printf('%dx^%d ', temp->coefficient, temp->exponent);        temp = temp->next;    } while (temp != list->head);    printf('

');}

// 一元多项式相加LinkedList addPolynomials(LinkedList* poly1, LinkedList* poly2) { LinkedList result; initLinkedList(&result);

Node* temp1 = poly1->head;    Node* temp2 = poly2->head;

do {        if (temp1->exponent == temp2->exponent) {            int sum = temp1->coefficient + temp2->coefficient;            if (sum != 0) {                insertNode(&result, sum, temp1->exponent);            }            temp1 = temp1->next;            temp2 = temp2->next;        } else if (temp1->exponent > temp2->exponent) {            insertNode(&result, temp1->coefficient, temp1->exponent);            temp1 = temp1->next;        } else {            insertNode(&result, temp2->coefficient, temp2->exponent);            temp2 = temp2->next;        }    } while (temp1 != poly1->head && temp2 != poly2->head);

while (temp1 != poly1->head) {        insertNode(&result, temp1->coefficient, temp1->exponent);        temp1 = temp1->next;    }

while (temp2 != poly2->head) {        insertNode(&result, temp2->coefficient, temp2->exponent);        temp2 = temp2->next;    }

return result;}

int main() { LinkedList poly1, poly2, result; initLinkedList(&poly1); insertNode(&poly1, 3, 2); insertNode(&poly1, 4, 1); insertNode(&poly1, 2, 0); initLinkedList(&poly2); insertNode(&poly2, 2, 3); insertNode(&poly2, 5, 1); insertNode(&poly2, 1, 0);

printf('Polynomial 1: ');    printLinkedList(&poly1);

printf('Polynomial 2: ');    printLinkedList(&poly2);

result = addPolynomials(&poly1, &poly2);

printf('Result: ');    printLinkedList(&result);

return 0;}

代码解释

• Node 结构体表示循环单链表中的一个节点，包含系数 coefficient、指数 exponent 以及指向下一个节点的指针 next。- LinkedList 结构体表示循环单链表，包含指向头节点的指针 head。- initLinkedList() 函数用于初始化一个空的循环单链表。- insertNode() 函数用于在循环单链表的尾部插入一个新的节点。- printLinkedList() 函数用于打印循环单链表的内容。- addPolynomials() 函数用于将两个一元多项式相加，返回一个新的循环单链表表示结果。

总结

本文介绍了如何使用C语言循环单链表结构实现一元多项式的相加算法，并提供了详细的代码示例和解释。该算法利用循环单链表的结构特点，实现了高效的多项式相加操作。