c语言数据结构之实现一元多项式的加减运算

实现结构：单项链表

思路：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去，减法亦然。

main.c

#include <stdio.h>
#include <malloc.h>
#include "poly.h"
#include "lArray.h"

void printInfo();
void eatline();
void choose_option();

void poly_exp_add(polyLinkList *ptr);

void poly_exp_view(polyLinkList *ptr);

void poly_exp_del(polyLinkList *ptr);

void poly_addition(polyLinkList *ptr);

void poly_sub(polyLinkList *ptr);

int main() {
    printInfo();
    choose_option();
    return 0;
}

void printInfo()
{
    printf("一元多项式的运算-----------------------\n");
    printf("0.添加一元表达式.\n");
    printf("1.查看表达式列表.\n");
    printf("2.删除一个表达式.\n");
    printf("3.一元多项式的加法.\n");
    printf("4.一元多项式的减法.\n");
    printf("6.退出.\n");
    printf("-------------------------------------\n");
}

void choose_option()
{

    polyLinkList Poly_Link_List;

    initPolyLinkList(&Poly_Link_List);


    int d;

    do{
        scanf("%d",&d);
        eatline();
        switch(d)
        {
            case 0://添加一元表达式
                poly_exp_add(&Poly_Link_List);
                break;
            case 1://查看表达式列表
                poly_exp_view(&Poly_Link_List);
                break;
            case 2://删除一个表达式
                poly_exp_del(&Poly_Link_List);
                break;
            case 3://一元多项式的加法
                poly_addition(&Poly_Link_List);
                break;
            case 4://一元多项式的减法
                poly_sub(&Poly_Link_List);
                break;
            case 6://退出
                break;
            default:
                break;
        }

        printf("->");
    }while(d != 6);
}

void poly_sub(polyLinkList *ptr) {
    int id1;
    int id2;
    char strExp[100] = "\0";

    poly_exp_view(ptr);
    printf("\n");
    printf("请输入要进行减法运算的id1和id2，以\",\"隔开,并按下回车键\n");

    printf("例子:1,2\n");
    printf("->");
    while(scanf("%d,%d",&id1,&id2) == 2)
    {
        struct polyNode * p1 = findById(ptr,id1);
        struct polyNode * p2 = findById(ptr,id2);
        if(p1 && p2)
        {
            subtractPoly(p1->linkList,p2->linkList);
            printPolyn(p1->linkList,strExp);
            printf("结果:%s\n",strExp);
            printf("要退出请按任意键并敲下回车，不退出请继续输入表达式的id,eg:1,2\n");
            printf("->");
            strExp[0] = '\0';
        }else{
            printf("两个表达式有一个id不存在，请重新输入.\n");
            printf("->");
        }
        eatline();
    }
    eatline();
    printf("操作取消.\n");

}

void poly_addition(polyLinkList *ptr) {
    int id1;
    int id2;
    char strExp[100]="\0";
    poly_exp_view(ptr);
    printf("\n");
    printf("请输入要进行加法运算的id1和id2，以\",\"隔开，并按下回车键\n");

    printf("例子:1,2\n");
    printf("->");
    while(scanf("%d,%d",&id1,&id2) == 2)
    {
        struct polyNode * p1 = findById(ptr,id1);
        struct polyNode * p2 = findById(ptr,id2);

        if(p1 && p2)
        {
            addPolyn(p1->linkList,p2->linkList);
            printPolyn(p1->linkList,strExp);
            printf("结果:%s\n",strExp);
            printf("要退出请按任意键并敲下回车，不退出请继续输入表达式的id,eg:1,2\n");
            printf("->");
            strExp[0] = '\0';
        }else{
            printf("两个表达式有一个id不存在，请重新输入.\n");
            printf("->");
        }

        eatline();
    }
    eatline();
    printf("操作取消.\n");
}

void poly_exp_del(polyLinkList *ptr) {
    int id;
    printf("请输入要删除节点的id:");
    if(scanf("%d",&id) == 1)
    {
        polyLinkList_remove(ptr,id);
    }
    eatline();
}

void poly_exp_view(polyLinkList *ptr) {
    struct polyNode ** pnList = findAll(ptr);
    int i = 0;
    printf("------------------------------------\n");
    printf("|   id   |           表达式         |\n");//36-2-(id)-(表达式) = 29
    char strExp[100]="\0"; //表达式空间
    for(;i<ptr->length;i++)
    {
        printPolyn(pnList[i]->linkList,strExp);
        printf("|%8d|%23s  |\n",pnList[i]->id,strExp);
        strExp[0]='\0';

    }

    printf("------------------------------------\n");
}

//表达式添加
void poly_exp_add(polyLinkList *ptr) {

    struct polyNode * pnode = (struct polyNode * )malloc(sizeof(struct polyNode));

    LinkList * linkList = (LinkList * )malloc(sizeof(LinkList));


    Term term;
    int j = 1;

    printf("请输入表达式的系数n和指数e并以逗号\",\"隔开,格式:n,e\n");
    printf("结束输入请输入任意数字并回车.\n");
    printf("请输入%d项:",j);;

    while(scanf("%d,%d",&term.n,&term.e) == 2)
    {
        eatline();
        createPolyn(linkList,term);
        printf("请输入%d项:",++j);
    }
    if(j!=1)//至少输入了一项
    {

        pnode->id = ptr->length+1;
        pnode->linkList = linkList;

        polyLinkList_add(ptr,pnode);
    }

    eatline();
}


void eatline()
{
    while(getchar() != '\n')
        continue;
}

poly.h

#ifndef _POLY_H_
#define _POLY_H_

#include <stdbool.h>
typedef struct{
    int n;//系数
    int e;//指数
}Term;

typedef struct node{
    Term term;
    struct node * next;//下一节点
}Node;

typedef struct{
    int length;
    Node * head;
}LinkList;

void createPolyn(LinkList * pLinkList,Term term);
void destroyPolyn(LinkList * pLinkList);
void printPolyn(LinkList * pLinkList,char * strExp);
int polynLength(LinkList * pLinkList);
void addPolyn(LinkList * pa,LinkList * pb);
void subtractPoly(LinkList * pa,LinkList * pb);
void multiplyPolyn(LinkList * pa,LinkList * pb);
int cmpTerm(Node * pa,Node *pb);
#endif

poly.c

#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "poly.h"

/**
 * 创建一元多项式
 * @param pLinkList
 * @param term
 */
void createPolyn(LinkList *pLinkList,Term term) {

    Node * pn = NULL;
    if(pLinkList->head)
    {
        pn = pLinkList->head;

        while(pn->next)
            pn = pn->next;

        pn->next = (Node *)malloc(sizeof(Node));
        pn->next->term = term;
    }else{
        pn = (Node *)malloc(sizeof(Node));
        pLinkList->head = pn;
        pn->term = term;
    }

     pLinkList->length++;
}

/**
 * 销毁一元多项式
 * @param pLinkList
 */
void destroyPolyn(LinkList *pLinkList) {
    Node * pn = pLinkList->head;
    Node * ptemp;
    while(pn)
    {
        ptemp = pn;
        pn = pn->next;
        free(ptemp);
    }
}

/**
 * 打印表达式
 * @param pLinkList
 */
void printPolyn(LinkList *pLinkList,char * strExp) {
    Node * pn = pLinkList->head;
    char strTemp[50];
    bool isFirstPlus = true;//去除表达式第一个加号

    while(pn)
    {
        if(pn->term.e == 0){
            if(pn->term.n != 0){
                if(pn->term.n > 0){
                    if(isFirstPlus){
                        sprintf(strTemp,"%d",pn->term.n);
                    }
                    else{
                        sprintf(strTemp,"+%d",pn->term.n);
                    }
                }
                else if(pn->term.n < 0){
                    sprintf(strTemp,"%d",pn->term.n);
                }
                isFirstPlus = false;
                strcat(strExp,strTemp);
            }
        }else{
            if(pn->term.n < 0){
                if(pn->term.e == 1)
                    sprintf(strTemp,"%dX",pn->term.n);
                else
                    sprintf(strTemp,"%dX^%d",pn->term.n,pn->term.e);
                isFirstPlus = false;
                strcat(strExp,strTemp);
            }else if(pn->term.n > 0) {
                if(pn->term.n == 1)
                    if(pn->term.e == 1)
                        if(isFirstPlus)
                            sprintf(strTemp, "X");
                        else
                            sprintf(strTemp, "+X");
                    else
                        if(isFirstPlus)
                            sprintf(strTemp, "X^%d", pn->term.e);
                        else
                            sprintf(strTemp, "+X^%d", pn->term.e);
                else
                    if(pn->term.e == 1)
                        if(isFirstPlus)
                            sprintf(strTemp, "%dX", pn->term.n);
                        else
                            sprintf(strTemp, "+%dX", pn->term.n);
                    else
                        if(isFirstPlus)
                            sprintf(strTemp, "%dX^%d", pn->term.n, pn->term.e);
                        else
                            sprintf(strTemp, "+%dX^%d", pn->term.n, pn->term.e);
                isFirstPlus = false;
                strcat(strExp,strTemp);
            }
        }
        pn = pn->next;
    }
}

/**
 * 获取表达式项数
 * @param pLinkList
 * @return
 */
int polynLength(LinkList *pLinkList) {
    if(pLinkList)
        return pLinkList->length;
    else
        return 0;
}

/**
 * 一元多项式的加法运算
 * @param pa
 * @param pb
 * @return 将pa = pa + pb,pa、pb无用的释放掉.
 */
void addPolyn(LinkList *pa, LinkList *pb) {
    Node *na,*nb,*temp,*pre=NULL;
    na = pa->head;
    nb = pb->head;

    while(na && nb)
    {
        if(cmpTerm(na,nb) == -1) {
            pre = na;
            na = na->next;
        }
        else if(cmpTerm(na,nb) == 0)
        {
            if(na->term.n + nb->term.n != 0)
            {
                na->term.n+=nb->term.n;
                temp = nb;
                nb = nb->next;
                pre = na;
                na = na->next;
                free(temp);
            }else{
                temp = na;
                na = na->next;
                if(!pre)//当位于第一个节点时候
                    pa->head = na;
                else
                    pre->next = na;
                free(temp);
                temp = nb;
                nb = nb->next;
                free(temp);
            }
        }else{
            temp = nb->next;
            nb->next = na;
            if(!pre)
                pa->head = nb;
            else
                pre->next = nb;
            nb = temp;
        }
    }

    if(nb)//如果b还有剩余节点
    {
        pre->next = nb;//链接剩余节点
    }
}


/**
 * 一元多项式的减法运算
 * @param pa
 * @param pb
 * @return
 */
void subtractPoly(LinkList * pa,LinkList * pb)
{
    Node *na,*nb,*temp = NULL, *pre = NULL;
    na = pa->head;
    nb = pb->head;

    while(na && nb)
    {
        if(cmpTerm(na,nb) == -1)
        {
            pre = na;
            na = na->next;
        }else if(cmpTerm(na,nb) == 0)
        {
            if(na->term.n - nb->term.n != 0)
            {
                na->term.n -= nb->term.n;
                temp = nb;
                nb = nb->next;
                free(temp);
                pre = na;
                na = na->next;
            }else{

                if(!pre)
                    pa->head = na->next;
                else
                    pre->next = na->next;

                temp = na;
                na = na->next;
                free(temp);

                temp = nb;
                nb = nb->next;
                free(temp);
            }
        }else{
            nb->term.n = -nb->term.n;
            temp = nb->next;
            nb->next = na;
            if(!pre)
                pa->head = nb;
            else
                pre->next = nb;
            nb = temp;
        }
    }


    if(nb)
    {
        pre->next = nb;
        while(nb)
        {
            nb->term.n = -nb->term.n;
            nb = nb->next;
        }
    }
}

/**
 * 一元多项式的乘法运算
 * @param pa
 * @param pb
 * @return
 */
void multiplyPolyn(LinkList * pa,LinkList * pb)
{

}

/**
 * 比较ta 和 tb 指数的大小关系，分别返回 1,0,-1
 * @param ta
 * @param tb
 * @return
 */
int cmpTerm(Node * pa,Node *pb)
{
    if(pa->term.e > pb->term.e)
        return 1;
    else if(pa->term.e == pb->term.e)
        return 0;
    else
        return -1;
}

lArray.h

#ifndef _L_ARRAY_H_
#define _L_ARRAY_H_
#include "poly.h"

struct polyNode{
    int id;
    LinkList * linkList;
    struct polyNode * next;
};

typedef struct{
    struct polyNode * head;
    int length;
    struct polyNode * tail;//当前链表的尾节点
}polyLinkList;

void initPolyLinkList(polyLinkList * pll);
void polyLinkList_add(polyLinkList * pll,struct polyNode * pnode);
void polyLinkList_remove(polyLinkList * pll,int id);
void polyLinkList_update(polyLinkList * pll, struct polyNode * pnode);
struct polyNode * findById(polyLinkList * pll, int id);

/**
 * 查找数组内所有节点
 * @param pll
 * @return 返回首节点指针
 */
struct polyNode ** findAll(polyLinkList * pll);

#endif

lArray.c

#include "lArray.h"
#include <stdlib.h>

void initPolyLinkList(polyLinkList * pll)
{
    pll->tail = NULL;
    pll->length = 0;
    pll->head = NULL;
}

void polyLinkList_add(polyLinkList * pll,struct polyNode * pnode)
{
    if(!pll->tail)//如果尾部指针为空，说明链表没有元素
    {
        pll->head = pnode;
        pll->tail = pnode;
    }else{
        pll->tail->next = pnode;
        pll->tail = pnode;
    }
    pll->length++;
}

void polyLinkList_remove(polyLinkList * pll,int id)
{
    struct polyNode * node = pll->head;
    if(node)
    {
        if(node->id == id)//首节点即是需要删除的节点
        {
            pll->head = node->next;
            free(node);
            pll->length--;
        }else{
            while(node->next)
            {
                if(node->next->id == id)
                {
                    free(node->next);
                    node->next = node->next->next;
                    pll->length--;
                    break;
                }
                node = node->next;
            }
        }

    }
}

/**
 * 根据节点的id来更新
 * @param pll
 * @param pnode
 */
void polyLinkList_update(polyLinkList * pll, struct polyNode * pnode)
{
    if(pnode){
        struct polyNode * node = findById(pll,pnode->id);
        node->linkList = pnode->linkList;
    }
}
struct polyNode * findById(polyLinkList * pll, int id)
{
    struct polyNode * node = pll->head;
    while(node)
    {
        if(node->id == id)
            return node;
        node = node->next;
    }

    return NULL;
}

/**
 * 查找数组内所有节点
 * @param pll
 * @return 返回首节点指针,用完记得释放
 */
struct polyNode ** findAll(polyLinkList * pll)
{
    if(pll){
        if(pll->length != 0)
        {
            struct polyNode ** pnArray = (struct polyNode **)malloc(sizeof(struct polyNode *)*pll->length);
            struct polyNode * node = pll->head;
            int i = 0;
            while(node)
            {
                *(pnArray+i) = node;
                node = node->next;
                i++;
            }
            return pnArray;
        }
    }

    return NULL;
}

测试用例： 12X^12+12X^14+12X^17

21X^12+243X^14+1223X^123321

进行减法操作：-9X^12-231X^14+12X^17-1223X^123321

因为时间比较紧张，所以只是实现了一元多项式的加减法运算，乘除法运算没有实现。

原文链接：https://blog.csdn.net/a1135004584/article/details/79302671

你可能也喜欢