欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c语言单链表实现多项式计算

程序员文章站 2024-01-02 14:43:22
多项式链表的结构和接口均参考严蔚敏老师的(版)《数据结构》。 加法的实现: 假设指针pa,pb分别指向多项式a和b当前进行比较的某个结点,则比较这两个结点的指数项,有下列三种情况: 指针pa所指...

多项式链表的结构和接口均参考严蔚敏老师的(版)《数据结构》。

加法的实现:

假设指针pa,pb分别指向多项式a和b当前进行比较的某个结点,则比较这两个结点的指数项,有下列三种情况:

指针pa所指结点的指数值 < 指针pb所指结点的指数值:则应摘取pa指针所指结点插入到“和多项式”链表中去 指针pa所指结点的指数值 < 指针pb所指结点的指数值:则应摘取pb指针所指结点插入到“和多项式“链表中去 指针pa所指结点的指数值 = 指针pb所指结点的指数值:则两个结点中的系数相加,若和数部位零,pa所指结点的系数值,同时释放pb所指的结点;反之,从多项式链表中删除相应的结点,同时释放pa和pb所指向的结点。

减法的实现:

简单的思路:先把减数多项式的系数一一取相反数,然后调用加法函数即可实现。

乘法的实现:

m (x) = a(x) x b(x) 
    = a(x) x [b1xe1+b2xe2+...+bnxen]
    =∑ni=1bia(x)xei

所以,乘法也可以转换成加法实现。

对于链表的操作有几点需要牢记:

需要对链表进行有效性判断

对于链表的操作过程中,首先要创建一个节点,并将头结点复制给新节点

如果要构建新的链表是,表头需要单独保存;同时每个节点需要创建新节点,完成赋值、指针操作;组后需要一个游标节点,负责将各个节点串联起来。 对于尾节点,最后一定要将其next指向null。 若在对链表操作时不想改变链表的值,则需要使用malloc函数重新定义一个链表,并把 原链表的内容赋给新链表。此时切记,不要把原链表的指针赋给新生成的结点,否则,在使用的过程中依旧会改变原链表,这是因为指针的特性。

c语言代码实现

/* 接口声明和数据结构声明头文件 */

/* 项的表示 
 * 多项式的项作为单链表的数据元素
*/
typedef struct{
    /* 系数 */
    int coef;
    /* 指数 */
    int expn;
}datatype;

/* 线性单链表的存储结构 */
typedef struct l_node{
    /* 数据域表示多项式的项 */
    datatype data;
    /* 指针域 */
    struct l_node *next;
}l_node,*link_list;

/* 用带头结点的有序链表表示多项式 */
typedef link_list polynomial;

#define true 1
#define false 0

/* 定义ccompare函数的返回值 */
#define a_e_b 0  //a = b
#define a_g_b 1  //a > b
#define a_s_b -1 //a < b


/* 定义polyn_locate函数的返回值 */
#define prior -1  //要找元素值不存在且小于链表中的某些结点
#define curor 0   //要找元素存在
#define nextor 1  //要找元素值不存在且大于链表中的结点


/* -------------------基本操作的函数原型说明------------------- */



/* 比较两个类型为datatype的变量
 * 若a = b,返回a_e_b
 * 若a > b,返回a_g_b
 * 若a < b,返回a_s_b
*/
int compare(datatype a, datatype b);


/* 定义polyn_locate函数的返回类型 */
typedef struct{
    /* 指向某结点的指针 */
    polynomial p;
    /* 类型 */
    int type;
}locate;

/* 若有序链表中head中存在与e满足判定函数compare()取值为a_e_b的元素
 则p为指向head中第一个值为e的结点的指针,并返回curor

 *若有序链表中head中存在与e满足判定函数compare()取值为a_g_b的元素
 则p为指向head中最后一个结点的指针,并返回nextor

 *若有序链表中head中存在与e满足判定函数compare()取值为a_s_b的元素
 则p为指向head中第一个大于e的结点的指针,并返回prior
*/
locate polyn_locate(polynomial head, datatype e, int(*compare)(datatype, datatype));

/* 按有序判定函数compare()的约定,将值为e的结点插入到有序链表的适当位置
*/
void polyn_order_insert(polynomial head, datatype e, int(*compare)(datatype, datatype));

/* 输入m项的系数和指数,建立表示一元多项式的有序链表 
 * head为链表的头指针
*/
void polyn_create(polynomial head);

/* 销毁一元多项式 */
void polyn_destroy(polynomial head);

/* 打印输出一个一元多项式 */
void polyn_print(polynomial head);

/* 返回一元多项式的项数 */
int polyn_length(polynomial head);

/* 完成多项式的相加
 * pa = pa + pb
 * 然后销毁一元多项式pb
*/
polynomial polyn_add(polynomial pa, polynomial pb);

/* 完成多项式的相减
 * pa = pa -pb
 * 并销毁一元多项式pb
*/
polynomial polyn_subtract(polynomial pa, polynomial pb);

/* 完成多项式的相乘
 * pa = pa * pb
 * 并销毁一元多项式pb
*/
polynomial polyn_multiply(polynomial pa, polynomial pb);



/* 复制一个单链表 */
polynomial polyn_clone(polynomial head);




/* 接口的实现文件 */
#include
#include
#include"polynomial.h"




int compare(datatype a, datatype b)
{
    if(a.expn == b.expn)
        return a_e_b;
    if(a.expn > b.expn)
        return a_g_b;
    if(a.expn < b.expn)
        return a_s_b;
}


void polyn_print(polynomial head)
{
    /* p指向第一个结点 */
    polynomial p = head -> next;
    if(!p)
        printf("此链表为空\n");
    else
    {
        while(p -> next)
        {
            if (p -> next -> data.coef >= 0)
                printf("%dx^%d + ",p -> data.coef,p -> data.expn);
            else
                printf("%dx^%d ",p -> data.coef,p -> data.expn);   

            p = p -> next;
        }
        printf("%dx^%d\n",p -> data.coef,p -> data.expn);
    }

}


locate polyn_locate(polynomial head, datatype e, int(*compare)(datatype, datatype))
{
    /* 初始化ptr指向头指针 */
    locate ptr; 
    ptr.p = head;
    while((ptr.p) -> next)
    {
        if(compare( (ptr.p -> next -> data), e) == a_e_b)
        {
            ptr.p = ptr.p -> next;
            ptr.type = curor;
            return ptr;
        }
        if(compare( ptr.p -> next -> data, e) == a_g_b)
        {
            ptr.type = prior;
            return ptr;
        }
        if(compare( ptr.p -> next -> data, e) == a_s_b)
        {
            ptr.p = ptr.p -> next;
        }
    }
    ptr.type = nextor;
    return ptr;
}




void polyn_order_insert(polynomial head, datatype e, int(*compare)(datatype, datatype))
{

    locate ptr = polyn_locate(head, e, compare);
    if (ptr.type == nextor)
    {
        /* 新建结点 */
        polynomial new_node = (polynomial)malloc(sizeof(l_node));
        new_node -> data = e;
        /* 修改指针域 */
        ptr.p -> next = new_node;
        new_node -> next = null;
    }
    if (ptr.type == prior)
    {
        /* 新建结点 */
        polynomial new_node = (polynomial)malloc(sizeof(l_node));
        new_node -> data = e;
        /* 修改指针域 */
        new_node -> next = ptr.p -> next;
        ptr.p -> next = new_node;
    }
    /* 若该项已存在 */
    if (ptr.type == curor)
    {
        (ptr.p -> data).coef += e.coef;
    }
}


void polyn_create(polynomial head)
{
    /* 初始化头指针 */
    head -> next = null;
    datatype temp;
    scanf("%d %d",&(temp.coef), &(temp.expn));
    /* 系数为零,指数为任意值时退出 */
    while(temp.coef != 0)
    {
        /* 建立新结点 */
        polyn_order_insert(head, temp, compare);
        scanf("%d %d",&(temp.coef), &(temp.expn));
    }
}

void polyn_destroy(polynomial head)
{
    while(head)
    {
        polynomial p = head;
        head = head -> next;
        free(p);
    }
}


int polyn_length(polynomial head)
{
    polynomial p = head -> next;
    int i = 0;
    while(p)
    {
        i += 1;
        p = p -> next;
    }
    return i;

}

polynomial polyn_add(polynomial pa, polynomial pb)
{ 
    /* 和链表的头结点 */
    polynomial hc = pa;
    /* 指向和链表的最后一个结点 */
    polynomial pc = hc;
    /* hb为链表b的头结点 */
    polynomial hb = pb;
    /* 当前结点 */
    pb = pb -> next;
    /* 当前结点 */
    pa = pa -> next;
    int type;
    while(pa && pb)
    {
        type = compare(pa -> data, pb -> data);
        if (type == a_e_b)
        {
            /* 指数相同,系数相加 */
            (pa -> data).coef = (pa -> data).coef + (pb -> data).coef;
            if (pa -> data.coef == 0)
            {
                /* 删除pa的当前结点 */
                pc -> next = pa;
                pa = pa -> next;
                free(pc -> next);
                pc -> next = null;
                /* 删除pb的当前结点 */
                hb -> next = pb -> next;
                free(pb);
                pb = hb -> next;

            }
            else
            {
                /* 将结点存至和链 */
                pc -> next = pa;
                pc = pa;
                /* 改变b的头结点 */
                hb -> next  = pb -> next;
                /* 释放当前结点 */
                free(pb);
                /* 下一个结点 */
                pb = hb -> next; 
                /* 下一个结点 */
                pa = pa -> next;
            }
        }
        if (type == a_s_b)
        {
            /* 将结点存至和链 */
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;
        }
        if (type == a_g_b)
        {
            /* 将b链的当前结点存至和链 */
            pc -> next = pb;
            pc = pb;
            pb = pb -> next;
            hb -> next = pb;
        }
    }

    if(pa == null)
    {
        if(pb == null)
            free(hb);
        else
        {
            pc -> next = pb;
            free(hb);
        }
    }
    else
    {
        free(hb);
        pc -> next = pa;
    }
    return hc;

}

polynomial polyn_subtract(polynomial pa, polynomial pb)
{
    /* 先把pb链(减数)取负,然后调用加法函数即可 */
    polynomial hb = pb -> next;
    while(hb)
    {
        hb -> data.coef = 0 - (hb -> data.coef);
        hb = hb -> next;     
    }
    polynomial pc = polyn_add(pa, pb);
    return pc;
}

polynomial polyn_multiply(polynomial pa, polynomial pb)
{
    /* 积的头结点 */
    polynomial p =(polynomial)malloc(sizeof(l_node));
    p -> next = null;
    /* 被乘数的当前结点 */
    polynomial pac = pa -> next;
    /* 乘数的当前结点 */
    polynomial pbc = pb -> next;
    while(pbc)
    {
        /* 中间链的头结点 */
        polynomial pc = polyn_clone(pa);
        /* 中间链的当前结点 */
        polynomial pcc = pc -> next;
        while(pac)
        {
            pcc -> data.coef = (pac -> data.coef) * (pbc -> data.coef);
            pcc -> data.expn = (pac -> data.expn) + (pbc -> data.expn);
            pcc = pcc -> next;
            pac = pac -> next;
        }
        pac = pa -> next;
        p = polyn_add(p, pc);
        pbc = pbc -> next;
    }
    polyn_destroy(pa);
    polyn_destroy(pb);
    return p;
}


polynomial polyn_clone(polynomial head)
{
    /* 源链的当前结点 */
    polynomial pnode  = head;
    /* 目的链的头结点和当前结点 */
    polynomial pclone_head,pclone_node;
    if(pnode != null)
    {
        pclone_head = (polynomial)malloc(sizeof(l_node));
        pclone_head -> data = pnode -> data;
        pclone_head -> next = null;
        pclone_node = pclone_head;
        pnode = pnode -> next;
    }
    while(pnode != null)
    {
        polynomial temp_node = (polynomial)malloc(sizeof(l_node));
        temp_node -> data = pnode -> data;
        temp_node -> next = null;
        pclone_node -> next = temp_node;
        pclone_node = pclone_node -> next;
        pnode = pnode -> next;
    }
    return pclone_head;
}

int main()
{
    /* 创建pa链表 */
    polynomial pa = (polynomial)malloc(sizeof(l_node));
    polyn_create(pa);
    /* 打印pa链表 */
    polyn_print(pa);
    /* 创建pb链表 */
    polynomial pb = (polynomial)malloc(sizeof(l_node));
    polyn_create(pb);
    /* 打印pb链表 */
    polyn_print(pb);
    /* 两个多项式相乘 */
    polynomial p = polyn_multiply(pa, pb);
    /* 打印结果 */
    polyn_print(p);
    /* 乘积的长度 */
    printf("length=%d\n", polyn_length(p));
    return 0;
}

上一篇:

下一篇: