20230320线性表-链式存储（编程题） 显示答案 一.论述题（共1题，100.0分） 1. 1)用单链表表示一元多项式，并实现一元多项式的输入和输出。 如：A(x)=5x9+8x7+3x2-12 2)在1)的基础上，建立一个函数，计算井返回一元多项式中一共有多少项数据， 3)在1)的基础上，建立一个函数，可以得到一元多项式中指数最大的系数并打印输出. 4)在1)的基础上，建立一个函数，输入系数和指数，如果元素存在，则册除之，否则打印出错信息 要求： 1)用C语言编写程序 2)上交运行结果界面截图。源代码的.c文件作为附件提交， 答案： 答案解折： 难度： 中 知识点： 线性表的链式存储

答案：

1) 单链表表示一元多项式，并实现输入输出功能：

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

typedef struct Node{ //链表结点
    int coef; //系数
    int expn; //指数
    struct Node *next; //指向下一个结点的指针
}Node, *PtrToNode;

PtrToNode CreateList(){ //创建新链表
    PtrToNode L = (Node*)malloc(sizeof(Node)); //头结点，不存储数据
    L->next = NULL;
    return L;
}

void Insert(PtrToNode L, int coef, int expn){ //在链表中插入新结点
    PtrToNode p = L;
    while(p->next != NULL && p->next->expn > expn){ //找到插入位置
        p = p->next;
    }
    if(p->next != NULL && p->next->expn == expn){ //指数相同时合并同类项
        p->next->coef += coef;
    }
    else{
        PtrToNode new_node = (Node*)malloc(sizeof(Node)); //新结点
        new_node->coef = coef;
        new_node->expn = expn;
        new_node->next = p->next;
        p->next = new_node;
    }
}

void Print(PtrToNode L){ //输出链表
    PtrToNode p = L->next;
    while(p != NULL){
        printf("%dx^%d ", p->coef, p->expn);
        p = p->next;
        if(p != NULL){
            printf("+ ");
        }
    }
    printf("\n");
}

void Input(PtrToNode L){ //输入链表
    int coef, expn;
    printf("Input a polynomial (enter 0 0 to end the input):\n");
    while(1){
        scanf("%d %d", &coef, &expn);
        if(coef == 0 && expn == 0){
            break;
        }
        Insert(L, coef, expn);
    }
}

int Length(PtrToNode L){ //计算链表长度
    PtrToNode p = L->next;
    int cnt = 0;
    while(p != NULL){
        cnt++;
        p = p->next;
    }
    return cnt;
}

int MaxCoef(PtrToNode L){ //求最大系数并输出
    PtrToNode p = L->next;
    int max_coef = p->coef;
    while(p != NULL){
        if(p->coef > max_coef){
            max_coef = p->coef;
        }
        p = p->next;
    }
    printf("The maximum coefficient is %d\n", max_coef);
    return max_coef;
}

void Delete(PtrToNode L, int coef, int expn){ //删除结点
    PtrToNode p = L->next, pre = L;
    while(p != NULL){
        if(p->coef == coef && p->expn == expn){
            pre->next = p->next;
            free(p);
            printf("Successfully delete %dx^%d\n", coef, expn);
            return;
        }
        pre = p;
        p = p->next;
    }
    printf("Element %dx^%d does not exist.\n", coef, expn);
}

int main(){
    PtrToNode L = CreateList();
    Input(L);
    printf("The polynomial entered is: ");
    Print(L);
    printf("The number of polynomial terms is: %d\n", Length(L));
    MaxCoef(L);
    int del_coef, del_expn;
    printf("Enter the coefficient and exponent of the element to be deleted:\n");
    scanf("%d %d", &del_coef, &del_expn);
    Delete(L, del_coef, del_expn);
    printf("The polynomial now is: ");
    Print(L);
    return 0;
}

2) 计算并返回一元多项式中一共有多少项数据：

int Length(PtrToNode L){
    PtrToNode p = L->next;
    int cnt = 0;
    while(p != NULL){
        cnt++;
        p = p->next;
    }
    return cnt;
}

3) 得到一元多项式中指数最大的系数并打印输出：

int MaxCoef(PtrToNode L){
    PtrToNode p = L->next;
    int max_coef = p->coef;
    while(p != NULL){
        if(p->coef > max_coef){
            max_coef = p->coef;
        }
        p = p->next;
    }
    printf("The maximum coefficient is %d\n", max_coef);
    return max_coef;
}

4) 输入系数和指数，如果元素存在，则删除之，否则打印出错信息：

void Delete(PtrToNode L, int coef, int expn){
    PtrToNode p = L->next, pre = L;
    while(p != NULL){
        if(p->coef == coef && p->expn == expn){
            pre->next = p->next;
            free(p);
            printf("Successfully delete %dx^%d\n", coef, expn);
            return;
        }
        pre = p;
        p = p->next;
    }
    printf("Element %dx^%d does not exist.\n", coef, expn);
}