数据结构c语言实现构造两个按指数递增的有序链表，实现两个一元多项式相加的代码及注释

在C语言中，我们可以使用链表数据结构来存储多项式的系数和指数。由于多项式的指数递增，我们可以使用两个单链表分别存储正指数和负指数的部分。下面是一个简单的实现，包括了构造链表、插入节点以及多项式相加。

首先，我们需要定义一个结构体来存储链表节点，包含系数和指数：

#include <stdio.h>
#include <stdlib.h> // 包含malloc和free函数

// 定义链表节点结构体
typedef struct Node {
    int coefficient;
    int exponent;   // 正数表示正指数，负数表示负指数
    struct Node* next; // 指向下一个节点的指针
} ListNode;

// 创建一个新的链表节点
ListNode* createNode(int coefficient, int exponent) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->coefficient = coefficient;
    newNode->exponent = exponent;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到链表中，保持指数递增
void insertSortedList(ListNode** head, int coefficient, int exponent) {
    ListNode* newNode = createNode(coefficient, exponent);
    
    if (*head == NULL || (*head)->exponent != exponent) {
        *head = newNode;
    } else {
        ListNode* current = *head;
        while (current->next && (current->next->exponent > exponent)) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

接下来，编写两个链表来存储两个多项式的部分，并合并它们：

// 用于存储正指数的链表
ListNode* positiveList;

// 用于存储负指数的链表
ListNode* negativeList;

// 将两个多项式的正负指数部分合并成一个新的链表
void combineLists(ListNode** positiveHead, ListNode** negativeHead) {
    // 首先合并正指数部分
    ListNode* newPositiveHead = positiveList;
    if (*positiveHead) {
        ListNode* current = *positiveHead;
        while (current->next) {
            current = current->next;
        }
        current->next = *negativeHead;
    }

    // 接着合并负指数部分
    ListNode* newNegativeHead = *negativeHead;
    if (*negativeHead) {
        ListNode* current = *negativeHead;
        while (current->next) {
            current = current->next;
        }
        current->next = positiveList;
    }

    // 更新正负链表头指针
    positiveList = newPositiveHead;
    negativeList = newNegativeHead;
}

// 两个多项式相加
ListNode* addPolynomials(ListNode* poly1Positive, ListNode* poly1Negative, ListNode* poly2Positive, ListNode* poly2Negative) {
    combineLists(&positiveList, &poly1Negative);
    combineLists(&negativeList, &poly2Positive);

    return positiveList;
}

// 打印链表表示的多项式
void printPolynomial(ListNode* list) {
    if (!list) return;
    ListNode* temp = list;
    while (temp) {
        printf("%+d*x^%d ", temp->coefficient, abs(temp->exponent)); // 用绝对值打印负指数
        temp = temp->next;
    }
}

int main() {
    // 初始化链表并插入元素（这里仅举个例子）
    // 实际上应从用户输入或其他方式获取多项式的系数和指数

    // ... （此处省略创建链表的部分）

    printf("多项式1: ");
    printPolynomial(positiveList);
    printf(" + ");
    printPolynomial(negativeList);
    printf("\n");

    printf("多项式2: ");
    // ...（同理）

    ListNode* result = addPolynomials(positiveList, negativeList, /* 加上poly2Positive和poly2Negative */);

    printf("它们的和: ");
    printPolynomial(result);

    return 0;
}

注意：这个实现仅适用于整数系数的多项式，并假设用户提供的输入是有效的。实际应用中，可能还需要考虑错误处理和输入验证。此外，这个实现并未将结果分解为正负指数链表，而是直接输出整个合并后的链表。如果你想保持这种形式，你需要在`printPolynomial`函数里处理合并后的链表。