【C 数据结构】用单链表存储一元多项式，并实现两个多项式相加运算。

桃扇骨 2024-04-03 12:16 64阅读 0赞

**本次代码纯c语言，可以支持输入两个多项式的项式、系数、指数。**

实验目的：  
1 掌握[单链表][Link 1]的基本工作原理;  
2 实现链式存储下的两个[多项式][Link 2]的相加。  
实验步骤  
1 定义链式存储的[数据结构][Link 3]  
2 完成多项式的初始化，即给多项式赋初值  
3 完成多项式的输出  
4 实现多项式的相加及结果输出。

/* 采用CLion的外部控制台运行*/
    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include <windows.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    #define MAXSIZE 100    //最大长度
    
    
    // 单链表的定义
    typedef struct PNode {
        int coef;           //系数
        int expn;           //指数
        struct PNode *next; //节点的指针域
    } PNode, *Polynomial;
    
    void greatePolyn(Polynomial p, int num);            // 链表的初始化
    void printout(Polynomial p, char num[]);            // 打印多项式
    Polynomial AddPolyn(Polynomial ha, Polynomial hb);  //多项式相加
    void returnMenu();                                  // 返回主界面
    int menu();
    
    PNode L1, L2;
    
    
    // 链表的初始化
    void greatePolyn(Polynomial p, int num) {
        Polynomial s;
        Polynomial pre, q;
        int n;
        printf("请输入第%d个多项式的项数：", num);
        scanf("%d", &n);
        p->next = NULL;
        pre = p;
        // 依次输入n个非零项
        for (int i = 1; i <= n; ++i) {
            s = (Polynomial) malloc(sizeof(PNode));
            s->next = NULL;
            printf("输入系数与指数");
            scanf("%d%d", &s->coef, &s->expn);
    
            q = p->next;
            while (q && q->expn < s->expn) {
                //通过比较指数找到第一个大于输入项指数的项*q
                pre = q;
                q = q->next;
            }
            s->next = q; //将输入项插入*q和其前驱节点pre之间
            pre->next = s;
            pre = s;
        }
        printf("第%d个多项式输入结束\n\n", num);
    }
    
    
    // 打印多项式
    void printout(Polynomial p, char num[]) {
        int n = 0;
        Polynomial t = p;
        printf("\n%s\n", num);
        while ((t = t->next)) {
            n++;
        }
        p = p->next;
        for (int i = 1; i < n; i++) {
            if (p->coef != 0 && p->expn == 0)
                printf("%d+", p->coef);
            else if (p->coef < 0) {
                printf("\b%dx^%d+", p->coef, p->expn);
            } else
                printf("%dx^%d+", p->coef, p->expn);
            p = p->next;
        }
    
        if (p->coef < 0) {
            printf("\b%dx^%d", p->coef, p->expn);
        } else
            printf("%dx^%d", p->coef, p->expn);
    
        printf("\n");
    }
    
    
    // 两个多项式相加
    Polynomial AddPolyn(Polynomial ha, Polynomial hb) {
        int c;
        Polynomial pa = ha->next, pb = hb->next, s, tc, hc;//将两个指针指向两个链表
        hc = (Polynomial) malloc(sizeof(PNode));//创建个新链表
        hc->next = NULL;
        tc = hc;//指针指向新链表
        while (pa != NULL && pb != NULL) {
            if (pa->expn > pb->expn) {
                s = (Polynomial) malloc(sizeof(PNode));
                s->expn = pb->expn;
                s->coef = pb->coef;
                tc->next = s;
                tc = s;
                pb = pb->next;
            } else if (pa->expn < pb->expn) {
                s = (Polynomial) malloc(sizeof(PNode));
                s->expn = pa->expn;
                s->coef = pa->coef;
                tc->next = s;
                tc = s;
                pa = pa->next;
            } else//遇到相同的指数，开始运算
    
            {
                c = pa->coef + pb->coef;
                if (c != 0) {
                    s = (Polynomial) malloc(sizeof(PNode));
                    s->expn = pa->expn;
                    s->coef = c;
                    tc->next = s;
                    tc = s;
                }//c=0，就是直接跳下去
                pa = pa->next;
                pb = pb->next;
            }
        }
        if (pb != NULL)pa = pb;
        while (pa != NULL) {
            s = (Polynomial) malloc(sizeof(PNode));
            s->expn = pa->expn;
            s->coef = pa->coef;
            tc->next = s;
            tc = s;
            pa = pa->next;
        }
        tc->next = NULL;
        return hc;
    }
    
    // 返回主界面
    void returnMenu() {
        printf("\n\n是否返回主界面？(y/n)\n");
        getchar();
        if (getchar() == 'y') {
            system("cls");
            menu();
        }
    }
    
    
    int menu() {
        Polynomial L;
        printf("\t多项式相加运算\t\n");
        printf("\t     1.多项式的创建\t\n");
        printf("\t     2.多项式的打印 \t\n");
        printf("\t     3.多项式的相加 \t\n");
        printf("=================================\n");
        printf("请输入要执行的操作: ");
        int l;
        scanf("%d", &l);
        switch (l) {
            case 1:
                system("cls");
                printf("请输入分别输入两个多项式：\n\n");
                for (int i = 1; i < 3; i++) {
                    if (i == 1)
                        greatePolyn(&L1, i);
                    else
                        greatePolyn(&L2, i);
                }
                returnMenu();
                break;
            case 2:
                system("cls");
                for (int i = 1; i < 3; i++) {
                    if (i == 1)
                        printout(&L1, "第1个多项式如下");
                    else
                        printout(&L2, "第2个多项式如下");
                }
                returnMenu();
                break;
            case 3:
                system("cls");
                L = AddPolyn(&L1, &L2);
                printout(L, " 相加后的多项式如下");
                returnMenu();
                break;
            default:
                printf("[输入错误]请重新输入有效数字!\n");
                Sleep(1000);
                system("cls");
                menu();
                break;
        }
    }
    
    int main() {
        menu();
    }

![0b255e2e9fc843968ff7bab0638dda60.png][]

**多项式的创建**

![f8a02a3c8025417ca3f0ba41be3e8756.png][]

**多项式的打印**

![a964428bb2514023858ec13d045fe214.png][]

多项式的相加

![f776d43054e14eac898f3403db0b8574.png][]

[Link 1]: https://so.csdn.net/so/search?q=%E5%8D%95%E9%93%BE%E8%A1%A8&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E5%A4%9A%E9%A1%B9%E5%BC%8F&spm=1001.2101.3001.7020
[Link 3]: https://so.csdn.net/so/search?q=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&spm=1001.2101.3001.7020
[0b255e2e9fc843968ff7bab0638dda60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/975e7d83a2f94e47a9a8428e0c0f88f1.png
[f8a02a3c8025417ca3f0ba41be3e8756.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3ee7ba7518cc4cf2b885558ebac536e2.png
[a964428bb2514023858ec13d045fe214.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/6f2836a411ae4844ba9ae269ec99a9f0.png
[f776d43054e14eac898f3403db0b8574.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/a1812a96b3d4446f88b7eca9614cf0f2.png