解决C语言运行超时：高效的多项式加法链表实现

解决C语言运行超时：高效的多项式加法链表实现

你是否因为C语言程序运行超时而苦恼？很多时候，传统的数组实现方式会遇到数据量过大导致的超时问题。本文将介绍一种使用链表表示多项式的方法，该方法更加高效，能够有效避免数组大小的限制，帮助你解决运行超时难题。

以下是使用链表实现多项式加法的C语言代码示例：

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

typedef struct Node {
    int coefficient;
    int exponent;
    struct Node* next;
} Node;

Node* create_node(int coefficient, int exponent) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->coefficient = coefficient;
    newNode->exponent = exponent;
    newNode->next = NULL;
    return newNode;
}

void add_term(Node** polynomial, int coefficient, int exponent) {
    Node* newTerm = create_node(coefficient, exponent);

    if (*polynomial == NULL) {
        *polynomial = newTerm;
    } else {
        Node* temp = *polynomial;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newTerm;
    }
}

void destroy_poly(Node* polynomial) {
    Node* temp;
    while (polynomial != NULL) {
        temp = polynomial;
        polynomial = polynomial->next;
        free(temp);
    }
}

void add_polynomials(Node* polyA, Node* polyB, Node** result) {
    Node* tempA = polyA;
    Node* tempB = polyB;
    Node* tempResult = NULL;
    Node** resultTail = &tempResult;

    while (tempA != NULL && tempB != NULL) {
        if (tempA->exponent > tempB->exponent) {
            add_term(resultTail, tempA->coefficient, tempA->exponent);
            tempA = tempA->next;
        } else if (tempA->exponent < tempB->exponent) {
            add_term(resultTail, tempB->coefficient, tempB->exponent);
            tempB = tempB->next;
        } else {
            int newCoefficient = tempA->coefficient + tempB->coefficient;
            if (newCoefficient != 0) {
                add_term(resultTail, newCoefficient, tempA->exponent);
            }
            tempA = tempA->next;
            tempB = tempB->next;
        }
        resultTail = &((*resultTail)->next);
    }

    while (tempA != NULL) {
        add_term(resultTail, tempA->coefficient, tempA->exponent);
        tempA = tempA->next;
        resultTail = &((*resultTail)->next);
    }

    while (tempB != NULL) {
        add_term(resultTail, tempB->coefficient, tempB->exponent);
        tempB = tempB->next;
        resultTail = &((*resultTail)->next);
    }

    *result = tempResult;
}

void print_poly(Node* polynomial) {
    Node* temp = polynomial;
    while (temp != NULL) {
        printf('%d,%d ', temp->coefficient, temp->exponent);
        temp = temp->next;
    }
    printf('
');
}

int main() {
    Node* polyA = NULL;
    Node* polyB = NULL;
    Node* result = NULL;

    int coefficient, exponent;

    while (1) {
        scanf('%d,%d', &coefficient, &exponent);
        if (coefficient == 0 && exponent == 0) {
            break;
        }
        add_term(&polyA, coefficient, exponent);
    }

    while (1) {
        scanf('%d,%d', &coefficient, &exponent);
        if (coefficient == 0 && exponent == 0) {
            break;
        }
        add_term(&polyB, coefficient, exponent);
    }

    add_polynomials(polyA, polyB, &result);
    print_poly(result);

    destroy_poly(polyA);
    destroy_poly(polyB);
    destroy_poly(result);

    return 0;
}

这段代码使用链表来表示多项式，并通过指针操作实现多项式的加法运算。其优势在于不会受到数组大小的限制，可以处理更大规模的数据，有效避免运行超时问题。

希望这段代码能够帮助你解决C语言程序运行超时的问题，并顺利完成多项式加法的计算！