c语言单链表实现多项式计算
程序员文章站
2024-01-02 14:43:22
多项式链表的结构和接口均参考严蔚敏老师的(版)《数据结构》。
加法的实现:
假设指针pa,pb分别指向多项式a和b当前进行比较的某个结点,则比较这两个结点的指数项,有下列三种情况:
指针pa所指...
多项式链表的结构和接口均参考严蔚敏老师的(版)《数据结构》。
加法的实现:
指针pa所指结点的指数值 < 指针pb所指结点的指数值:则应摘取pa指针所指结点插入到“和多项式”链表中去 指针pa所指结点的指数值 < 指针pb所指结点的指数值:则应摘取pb指针所指结点插入到“和多项式“链表中去 指针pa所指结点的指数值 = 指针pb所指结点的指数值:则两个结点中的系数相加,若和数部位零,pa所指结点的系数值,同时释放pb所指的结点;反之,从多项式链表中删除相应的结点,同时释放pa和pb所指向的结点。假设指针pa,pb分别指向多项式a和b当前进行比较的某个结点,则比较这两个结点的指数项,有下列三种情况:
减法的实现:
简单的思路:先把减数多项式的系数一一取相反数,然后调用加法函数即可实现。
乘法的实现:
m (
= a(
=
所以,乘法也可以转换成加法实现。
对于链表的操作有几点需要牢记:
需要对链表进行有效性判断
对于链表的操作过程中,首先要创建一个节点,并将头结点复制给新节点
如果要构建新的链表是,表头需要单独保存;同时每个节点需要创建新节点,完成赋值、指针操作;组后需要一个游标节点,负责将各个节点串联起来。 对于尾节点,最后一定要将其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; }