一元多项式C语言链表

### 使用C语言链表实现一元多项式的表示和运算

#### 1. 定义节点结构体
为了存储一元多项式的每一项，定义一个包含系数(coefficient)和指数(exponent)以及指向下一个节点指针(next)的结构体。

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

#### 2. 创建新节点函数
编写一个辅助函数来分配内存给新的节点，并初始化其成员变量。

Node* create_node(int coef, int expn) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (!new_node) exit(-1); // 如果分配失败则退出程序
    
    new_node->coefficient = coef;
    new_node->exponent = expn;
    new_node->next = NULL;

    return new_node;
}

#### 3. 输入并建立一元稀疏多项式
设计一个接口让用户可以输入多项式的各项参数，之后调用`create_node()`创建对应的节点并将它们链接起来形成完整的表达式[^2]。

void input_polynomial(Polynomial* poly_ptr) {
    char ch;
    while ((ch=getchar()) != '\n') { /*略过空白字符*/
        ungetc(ch, stdin);
        
        Polynomial temp=(*poly_ptr), prev=NULL;
        scanf("%d",&temp->coefficient);
        getchar();/*读取中间可能存在的空格或其他分隔符*/

        if(scanf("x^%d", &temp->exponent)==EOF){
            temp->exponent=0; // 默认常数项的指数为零
        }
        else{
            getchar();
        }

        (*poly_ptr)=temp=(Node *)malloc(sizeof(struct Node));

        if(prev!=NULL)
           prev->next=temp;
        prev=temp;
     }
     
     prev->next=NULL;
}

注意上述代码片段中的逻辑可能存在一些简化处理，在实际应用中应当更加严谨地解析用户的输入字符串。

#### 4. 输出所建的一元多项式
遍历整个单向链表打印出各个节点的信息即可得到最终的结果形式。

void output_polynomial(const Polynomial p) {
    printf("The polynomial is:\n");
    
    for (;p;p=p->next){
         if(p->coefficient>0 && p!=(*poly)){
             putchar('+');
          } 
          
          if(abs(p->coefficient)!=1 || !p->exponent )
              printf("%dx",abs(p->coefficient));  
              
          if(p->exponent==1)
               putchar('x');   
               
          if(p->exponent>=2)
               printf("x^%d",p->exponent);
      }
      
      puts("");
}

此部分同样进行了适当简化以便于理解核心概念。

#### 5. 实现两个多项式相加运算
当执行加法时，需要比较当前正在访问的两项的指数大小。如果相同，则将这两个位置上的数值求和作为结果的一部分；如果不一致的话就直接复制较小的那个加入到目标列表里去直到其中一个序列结束为止最后再把剩下的另一串全部追加上面提到的过程可以通过下面这段伪码描述出来：

// 假设pa 和 pb 是待相加的两个多项式的头部指针
while(pa != NULL && pb != NULL) {
    if (pa->exponent == pb->exponent) {
        sum_coefficient = pa->coefficient + pb->coefficient;
        if(sum_coefficient != 0){ // 只有非零才插入
            result_tail->next = create_node(sum_coefficient, pa->exponent);
            result_tail = result_tail->next;
        }
        pa = pa->next;
        pb = pb->next;
    } else if (pa->exponent > pb->exponent) {
        copy_to_result(&result_tail, pa);
        pa = pa->next;
    } else {
        copy_to_result(&result_tail, pb);
        pb = pb->next;
    }
}

// 将剩余的部分附加到结果后面
append_remaining_terms(result_tail, pa ? pa : pb);

/// ...省略具体细节...

这里假设存在名为 `copy_to_result` 的方法用来简单拷贝源节点至目的链表末端，还有另一个叫做 `append_remaining_terms` 方法负责处理未被完全迭代过的那一侧多出来的那些元素[^1][^3]。