首页 > 代码库 > 单向链表实现多项式加和乘--自己写数据结构
单向链表实现多项式加和乘--自己写数据结构
用单项链表实现多项式数据结构和代码如下（由于时间原因多项式乘法的函数没用实现，读者可以在自己完善）：
存放结构体的头文件polylist.h
#ifndef _H_POLYLIST_#define _H_POLYLIST_typedef struct _Poly_Node{ int ratio; //系数 int power; //幂 struct _Poly_Node* next; }Node,*pNode;typedef struct _Poly_List{ struct _Poly_Node* next; }PolyList,*pPolyList;pPolyList init_list_header(void);pNode poly_add_node(pPolyList plist,int ratio,int power);int poly_delete_node(pPolyList plist,int power);int print_poly(pPolyList plist);int poly_bubble_sort(pPolyList plist);pPolyList poly_addcat(pPolyList pfir,pPolyList psec);pPolyList poly_add(pPolyList pfir,pPolyList psec);#endif
数据结构函数实现文件polylist.c如下：
/**************************************时间：2014.12.11作者：XIAO_PING_PING内容：单向链表表示多项式的加法和乘法 功能：学习写数据结构 ***************************************/#include <string.h>#include <stdlib.h>#include "polylist.h"/*创建一个多项式链表头*/pPolyList init_list_header(void){ pPolyList phead; phead = (PolyList *)malloc(sizeof(PolyList)); phead->next = NULL; return phead; } /*往多项式里面添加项*/pNode poly_add_node(pPolyList plist,int ratio,int power){ pNode ptail,pre,p; ptail = (Node *)malloc(sizeof(Node)); ptail->ratio = ratio; ptail->power = power; ptail->next = NULL; if(NULL == plist->next) { plist->next = ptail; printf("多项式链表插入点：系数=%d，幂值=%d\n",ptail->ratio,ptail->power); return ptail; } pre = plist->next; while(pre) { p = pre; pre = pre->next; } p->next = ptail; printf("多项式链表插入点：系数=%d，幂值=%d\n",ptail->ratio,ptail->power); return ptail; }/*删除多项式中对应幂值的项*/int poly_delete_node(pPolyList plist,int power){ pNode pre,p; if(NULL == plist->next) { printf("多项式链表为空"); return -1; } pre = plist->next; p = pre; while(NULL != p->next) { pre = p; if(power == pre->next->power) { pre = pre->next; p->next = pre->next; free(pre); printf("删除多项式链表中幂值为%d的项\n",power); } p = p->next; } if(power == plist->next->power) { p = plist->next; plist->next = plist->next->next; free(p); printf("删除多项式链表中幂值为%d的项\n",power); } return 0; }/*打印多项式*/int print_poly(pPolyList plist){ pNode p; p = plist->next; if(NULL == p) { printf("该多项式为空。\n"); return -1; } printf("遍历输出多项式:\n"); printf("Y = "); while(NULL != p) { printf("%d X%d + ",p->ratio,p->power); p = p->next; } return 0;} /*多项式排序*/int poly_bubble_sort(pPolyList plist){ int tpower,tratio; pNode p,pre,ptemp; if(NULL == plist->next) { printf("多项式链表为空\n"); return -1; } if(NULL == plist->next->next) { printf("多项式链表只有一项\n"); return -2; } p = plist->next; pre = p; while(p) { pre = p; while(pre->next) { // ptemp = pre; if(pre->next->power == p->power) { ptemp = pre->next; p->ratio += pre->next->ratio; pre->next = pre->next->next ; free(ptemp); if(NULL == pre->next) { break; } } else if(pre->next->power < p->power) { tpower = p->power; tratio = p->ratio; p->power = pre->next->power; p->ratio = pre->next->ratio; pre->next->power = tpower; pre->next->ratio = tratio; //ptemp = p; //p = pre->next; //pre->next = ptemp; // } else { } pre = pre->next; } p = p->next; } }/*合并两个多项式，把第二个多项式的全部节点添加到第一个多项式后面*/pPolyList poly_addcat(pPolyList pfir,pPolyList psec){ PolyList *p = pfir; //ptotal = (PolyList *)malloc(sizeof(PolyList)); Node *pre = pfir->next; //p = pfir->next; if(NULL == pre) { pfir->next = psec->next; } else { while(pre->next) { //pre = p; pre = pre->next; } pre->next = psec->next; } free(psec); return pfir; }/*多项式加法*/pPolyList poly_add(pPolyList pfir,pPolyList psec){ PolyList *p = pfir; //ptotal = (PolyList *)malloc(sizeof(PolyList)); p = poly_addcat(pfir,psec); poly_bubble_sort(p); //return poly_bubble_sort(poly_addcat(pfir,psec)); return p; }
测试文件test.c如下
#include <string.h>#include <conio.h>#include "polylist.h"int main(){ pPolyList polyone,polytwo,polyadd; printf("多项式一：\n"); polyone = init_list_header(); poly_add_node(polyone,2,11); poly_add_node(polyone,3,7); poly_add_node(polyone,23,11); poly_add_node(polyone,1,13); poly_add_node(polyone,32,45); poly_add_node(polyone,23,32); poly_add_node(polyone,3,343); poly_add_node(polyone,34,414); poly_add_node(polyone,23,7); poly_add_node(polyone,12,44); print_poly(polyone); printf("\n"); printf("\n"); printf("多项式二：\n"); polytwo = init_list_header(); poly_add_node(polytwo,2,11); poly_add_node(polytwo,44,13); poly_add_node(polytwo,23,34); poly_add_node(polytwo,43,32); poly_add_node(polytwo,32,45); poly_add_node(polytwo,23,32); poly_add_node(polytwo,3,343); poly_add_node(polytwo,34,44); poly_add_node(polytwo,23,7); poly_add_node(polytwo,12,464); print_poly(polytwo); printf("\n"); printf("\n"); //polyadd = init_list_header(); // polyadd = poly_addcat(polyone,polytwo); //polyadd = init_list_header(); printf("合并多项式一和二：\n"); polyadd = poly_add(polyone,polytwo); print_poly(polyadd); //poly_bubble_sort(polyone); //poly_delete_node(polyone,2); //poly_delete_node(polyone,4); //poly_delete_node(polyone,2); //poly_delete_node(polyone,3); // getch();}
以上文件运行结果如下：
单向链表实现多项式加和乘--自己写数据结构
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。