数据结构(C语言)用单链表存储一元多项式,并实现两个多项式的相加运算

C语⾔单链表实现多项式相加本⽂实例为⼤家分享了C语⾔单链表实现多项式相加的具体代码，供⼤家参考，具体内容如下//多项式的相加和相乘#include<stdio.h>#include<stdlib.h>#pragma warning(disable:4996)//兼容scanftypedef struct node {int coef;int expon;struct node* link;}Polynode,*Polynomial;Polynomial InsertPolyLinklist(Polynomial in,Polynomial Pread) {Pread->link = in;Pread = in;in->link = NULL;return Pread;}Polynomial ReadPoly(void) {Polynomial Pread = (Polynomial)malloc(sizeof(Polynode));Pread->link = NULL;Polynomial H = Pread;int N;scanf("%d ", &N);while (N--) {Polynomial p = (Polynomial)malloc(sizeof(Polynode));scanf("%d %d", &p->coef, &p->expon);Pread= InsertPolyLinklist(p,Pread);}Polynomial F;F = H->link;free(H);return F;}void PrintPoly(Polynomial F) {while(F != NULL) {printf("%d %d ", F->coef, F->expon);F = F->link;}printf("\n");}Polynomial Add(Polynomial p1, Polynomial p2) {Polynomial t1=p1,t2=p2;Polynomial p=(Polynomial)malloc(sizeof(Polynode));p->link = NULL;Polynomial q = p;Polynomial read;while (t1&&t2) {if (t1->expon == t2->expon) {if (t1->coef + t2->coef) {t1->coef = t1->coef + t2->coef;t1->expon = t1->expon;read = t1;q->link = read;q = read;t1 = t1->link;t2 = t2->link;}}else {if (t1->expon > t2->expon){read = t1;q->link = read;q = read;t1 = t1->link;}else {if (t1->expon < t2->expon) {read = t2;q->link = read;q = read;t2 = t2->link;}}}}if (t1) {q->link = t1;}if (t2) {q->link = t2;}Polynomial F = p->link;free(p);return F;}int main(void) {Polynomial p1, p2, pp, ps;p1 = ReadPoly();PrintPoly(p1);p2 = ReadPoly();PrintPoly(p2);pp = Add(p1, p2);PrintPoly(pp);// ps = Mult(p1, p2);// PrintPoly(ps);return 0;}参考MOOC 浙⼤数据结构以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

数据结构C语⾔描述——⽤单链表实现多项式的相加#include <stdio.h>#include <stdlib.h>typedef DataType;typedef struct Node2{DataType xishu;DataType zhisu;struct Node2 *Next;}Node2;typedef struct Node2* PNode2;//多项式按照指数⼤⼩排序void insertNewPoint_link(PNode2 head,PNode2 qNode){PNode2 p=head;while (p->Next!=NULL){if (p->Next->zhisu>qNode->zhisu){qNode->Next=p->Next;p->Next=qNode;break;}p=p->Next;}if (p->Next==NULL){p->Next=qNode;}}//打印多项式void printLinkeLink(PNode2 head){PNode2 temp=head->Next;while (temp!=NULL){printf("%d %d",temp->xishu,temp->zhisu);printf("\n");temp=temp->Next;}}//多项式的加法计算void add_poly(Node2 *pa,Node2 *pb){Node2 *p=pa->Next;Node2 *q=pb->Next;Node2 *pre=pa;Node2 *u;while (p!=NULL&&q!=NULL){if (p->zhisu<q->zhisu){pre=p;p=p->Next;}else if(p->zhisu==q->zhisu){float x=p->xishu+q->xishu;if (x!=0){p->xishu=x;pre=p;}else{pre->Next=p->Next;//指向下⼀个结点free(p);}p=pre->Next;u=q;q=q->Next;free(u);}else{u=q->Next;q->Next=p;pre->Next=q;pre=q;q=u;}}if (q){pre->Next=q;}free(pb);}void main( ){int zhishu;float xishu;PNode2 head1=(PNode2)malloc(sizeof(struct Node2));PNode2 head2=(PNode2)malloc(sizeof(struct Node2));PNode2 tem=NULL;head1->Next=NULL;head2->Next=NULL;printf("输⼊链表⼀的系数和指数，如：3,2 以0,0结束输⼊：\n"); scanf("%f,%d",&xishu,&zhishu);while (xishu!=0||zhishu!=0){tem=(PNode2)malloc(sizeof(struct Node2));tem->xishu=xishu;tem->zhisu=zhishu;tem->Next=NULL;insertNewPoint_link(head1,tem);scanf("%f,%d",&xishu,&zhishu);}printf("链表⼀按指数升序排序后的多项式为：\n");printLinkeLink(head1);printf("\n");printf("输⼊链表⼀的系数和指数，如：3,2 以0,0结束输⼊：\n"); scanf("%f,%d",&xishu,&zhishu);while (xishu!=0||zhishu!=0){tem=(PNode2)malloc(sizeof(struct Node2));tem->xishu=xishu;tem->zhisu=zhishu;tem->Next=NULL;insertNewPoint_link(head2,tem);scanf("%f,%d",&xishu,&zhishu);}printf("链表⼆按指数升序排序后的多项式为：\n");printLinkeLink(head2);printf("\n");add_poly(head1,head2);printf("多项式相加后的结果为：\n");printLinkeLink(head1);}。

数据结构-单链表-多项式相加【问题描述】编写⼀个程序⽤单链表存储多项式，并实现两个⼀元多项式A与B相加的函数。

A，B刚开始是⽆序的，A与B之和按降序排列。

例如：多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10多项式A与B之和：5.4X^10 6.4X^3 5X^1【输⼊形式】任意两个多项式A和B的项数及对应的系数和指数，要查询的第⼏项【输出形式】多项式中某⼀项的系数与指数，系数保留⼀位⼩数【输⼊样例】4 1.2 0 2.5 1 3.2 3 -2.5 55 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 102【输出样例】6.4 31 #include<bits/stdc++.h>2 #include<stdlib.h>3using namespace std;4 typedef long long ll;56struct node{7double data;8int index;9 node* next;10 node():index(0){}11 node* operator [] (int n){12 node* end=next;13while(end&&n--)end=end->next;14return end;15 }16bool operator < (const node &t) const {17return index>t.index;18 }19 node operator * (node& t);20 };2122void newList(node & head,int length){23 node *a=new node[length];//这是这个函数的解释node* operator [] (int n)P11⾏申请空间的⽅式 new int[10]申请10个int类型的空间再返回node指针类型24for(int i=0;i<length;++i)cin>>a[i].data>>a[i].index;25//a是node类型数组啊26 sort(a,a+length);//p16⾏的函数解释27 node* end=&head;28for(int i=0;i<length;++i){29 node* t=new node;30 t->data=a[i].data;31 t->index=a[i].index;32 end->next=t;33 end=t;34 }//他这好像就特别简单 end=xx 之后就申请了新节点赋值然后挂上去35delete[] a;36 }37void show(node& head){//传递的这个是引⽤38 node* end=head.next;//就还是这个类型所以⽤的是.39while(end){40if(end->index==1) cout<<end->data<<"X^"<<(end->next?" + ":"\n");41else cout<<end->data<<"X^"<<end->index<<(end->next?" + ":"\n");//末尾加的这个的意思是如果下⼀个节点还有就+上如果没有就换⾏42 end=end->next;43 }44 }4546///多项式相加：47void combine(node& a, node& b){//传递的是引⽤48 node* p,*q,*tail,*temp;49double s;50 p=a.next;51 q=b.next;52 tail=&a;//就直接修改a链表了53while(p&&q){54if(p->index>q->index){55 tail->next=p;tail=p;p=p->next;56 }else if(p->index==q->index){57 s=p->data+q->data;58if(s){59 p->data=s;60 tail->next=p; tail=p;p=p->next;61 temp=q;q=q->next;delete temp;62 }else{63 temp=p;p=p->next;delete temp;64 temp=q;q=q->next;delete temp;65 }//删除没有⽤的节点这点甚是符合朕⼼厉害66 }else{67 tail->next=q; tail=q; q=q->next;68 }69 }70if(p)tail->next=p;71else tail->next=q;72 }7374int main(){75 node a,b;76int n1,n2;cin>>n1;77 newList(a,n1);78 cin>>n2;79 newList(b,n2);80 combine(a,b);8182 cin>>n1;83 cout<<fixed<<setprecision(1)<<a[n1-1]->data<<""<<a[n1-1]->index<<endl;//这⾥可以这么骚也是因为p11⾏⽜逼84 show(a);//给引⽤传参数就是传本⾝不是传指针85 }。

北京理工大学珠海学院《数据结构》课程设计报告题目：用重概念的单链表存储一元多项式，并实现两个多项式的相加运算所在学院：运算机科学技术学院专业班级：学生姓名：指导教师：2010年月日目录１．前言 (5)2．概要设计 (5)数据结构设计 (5)３．详细设计 (6)３.1 算法设计 (6)3.1.1 成立链表的算法 (6)3.1.2 链表插入一个元素的算法 (6)3.1.3 一元多项式的相加 (6)ADT描述 (7)功能模块分析 (7)数据存储结构设计： (8)主要算法流程图（流程图在下一页） (8)3．软件测试 (10)5．设计体会 (15)致谢: (16)参考文献： (16)附录： (16)１．前言数据结构是运算机程序设计的重要理论技术基础，它不仅是运算机学科的核心课程，学会分析研究运算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构及其相应的算法并初步掌握算法的时刻分析和空间分析的技术。

在许多类型的程序的设计中，数据结构的选择是一个大体的设计考虑因素。

许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严峻的依赖于是不是选择了最优的数据结构。

许多时候，肯定了数据结构后，算法就容易患到了。

有些时候情形也会反过来，咱们按照特定算法来选择数据结构与之适应。

不论哪一种情形，选择适合的数据结构都是超级重要的。

2．概要设计数据结构设计数据的链接存储表示又被称为链接表。

当链接表中的每一个结点只含有一个指针称为单链表。

在数据的顺序存储中，由于每一个元素的存储位置都能够通过简单计算取得，所以元素的时刻都相同；而在数据的链接存储中，由于每一个元素的存储位置是保留在它的{或后继结点中的，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到自访问任一元素的时刻与该元素结点在链接存储中的位置有关。

线性表是最大体、最简单、也是最常常利用的一种数据结构。

线性表中数据元素之间的关系是一对一的关系，即除第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

（链表实现）写出两个⼀元多项式相加的算法int c, e;head=new node; //⽣成头结点head->next=NULL;cout<<"请分别输⼊新的⼀项的系数、指数(以输⼊9999作为结束):"<<endl;cin>>c>>e;while(c!=9999 && e!=9999) //输⼊并检测结束{s=new node; //⽣成新结点s->co = c; //装⼊数据s->exp = e;p=head;while(p->next!=NULL){p=p->next;}p->next = s; //插到最后⼀个结点后s->next = NULL;cout<<"请分别输⼊新的⼀项的系数、指数(以输⼊9999作为结束):"<<endl;cin>>c>>e;}return head;}void Display(node * head){if(head==NULL){cout<<"多项式不存在！"<<endl;return ;}node* p;p=head->next;while(p!=NULL){if(p->co>0)cout<<p->co<<"x^"<<p->exp;elsecout<<"("<<p->co<<")"<<"x^"<<p->exp;if(p->next!=NULL)cout<<"+";p=p->next;}cout<<endl<<endl;}node* Add(node * A, node * B){node * C=new node;C->next=NULL;node * p1=A->next;node * p2=B->next;node * p3;node * rearC=C;while(p1!=NULL && p2!=NULL){。

南昌航空大学实验报告课程名称：数据结构实验名称：实验二线性表的链式存储结构班级：080611 学生姓名：学号：08指导教师评定：签名:题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析1.用户可以根据自己的需求分别输入两个一元多项式，并且能够实现输入的一元多项式的显示。

2.能够完成两个一元多项式的相加功能，而且还能显示相加后的逆置的一元多项式。

3.程序执行的命令包括：（1）构造链表A （2）构造链表B （3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表（6）将已相加的链表进行逆序排列二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Polynomial {数据对象：D={a i:|a i∈TermSet,i=1…n,n≥0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={<a i-1,a i>|a i-1,a i∈D,且a i-1中的指数值< a i中的指数值i=2,…n≥0}基本操作:initlink(& L)操作结果：构造一个空的链表L。

Creatlink(&L,n)操作结果：输入n项的系数和指数，建立一个非空的一元多项式L。

LinkLength(L)初始条件：链表L已经存在。

操作结果：返回一元多项式L中的项数。

Displaylink（L）初始条件：链表L已经存在。

操作结果：打印输出一元多项式L。

Addpolyn(A,B,&C)初始条件：一元多项式A和B已存在。

操作结果：完成多项式相加运算，即：C=A+B，并且带回C。

subtracypolyn(&La,&Lb,)初始条件：一元多项式La和Lb已存在。

操作结果：完成多项式的相减运算La=La+Lb，并且销毁多项式Lb。

上机实习三一，实验题目：单链表多项式加法算法实现二，实验目的：结合实际问题掌握线性表链式存储结构的C语言描述及运算算法的实现。

设计一个一元多项式加法器，界面为菜单形式。

程序功能：1、（菜单）主程序2、输入并建立多项式3、多项式a和b相加，建立多项式a＋b。

4、输出多项式，输出形式为整数序列n,c1,e1,c2,e2,…,cn,en。

n是多项式的项数，ci、ei分别是第i项的系数和指数。

三，功能层次图主函数调用创建函数创建A和B多项式调用加多项式函数加A和B调用输出函数程序结束四，运行结果创建A表创建B表加两个A，B的多项赋给C式A，B，C的结果五，小结在做这个程序的时候，虽然遇到一些问题，但最后都被我解决，自信心上得到比较大的提升，这也是这次实践最大的收获。

同时，知识上的收获也是不可忽视的，亲手解决问题的过程也是很好的学习过程，并且积累了一些经验，相信会为以后的学习发展带来非常积极的帮助。

源代码：#include<stdio.h>#include<conio.h>#include<alloc.h>#include<stdlib.h>typedef struct pnode{float coef; /* xishu */int exp; /* zhishu */struct pnode *next;}polynode;polynode *createList(){float xishu;int zhishu;polynode *head,*r;r=malloc(sizeof(polynode));r->coef=0;r->exp=-1;r->next=r;head=r;printf("<<Input XiShu 111 to stop>>\n");printf("Input XiShu:");scanf("%f",&xishu);printf("Input ZhiShu:");scanf("%d",&zhishu);while(1){r->next=malloc(sizeof(polynode));r=r->next;r->coef=xishu;r->exp=zhishu;printf("Input XiShu:");scanf("%f",&xishu);if(xishu==111) break;printf("Input ZhiShu:");scanf("%d",&zhishu);}r->next=head;return head;}void display(polynode *head){int i=1;polynode *t;if(head==NULL){printf("List is empty\n");return;}t=head->next;printf("[%0.0f][%d]\t",head->coef,head->exp);while(1){printf("[%0.0f][%d]\t",t->coef,t->exp);t=t->next;i++;if(t==head) break;}}polynode *POLYADD(polynode *A,polynode *B) {int i,j,k;polynode *ptr,*q,*q1,*q2;float x;q1=A;q2=B;q=malloc(sizeof(polynode));q->coef=0;q->exp=-1;q->next=q;ptr=q;q1=q1->next;q2=q2->next;while((q1!=A)&&(q2!=B)){if(q1->exp==q2->exp){x=q1->coef+q2->coef;if(x!=0){q->next=malloc(sizeof(polynode));q=q->next;q->coef=x;q->exp=q1->exp;}q1=q1->next;q2=q2->next;}else{q->next=malloc(sizeof(polynode));q=q->next;if(q1->exp>q2->exp){q->coef=q2->coef;q->exp=q2->exp;q2=q2->next;}else{q->coef=q1->coef;q->exp=q1->exp;q1=q1->next;}}}while(q1!=A){q->next=malloc(sizeof(polynode));q=q->next;q->coef=q1->coef;q->exp=q1->exp;q1=q1->next;}while(q2!=B){q->next=malloc(sizeof(polynode));q=q->next;q->coef=q2->coef;q->exp=q2->exp;q2=q2->next;}q->next=ptr;return ptr;}char caiDan(){char ch;do{printf("1:Create A list\n");printf("2:Create B list\n");printf("3:Add Two Polylist\n");printf("4:Display Polylist\n");printf("5:Exit\n");printf("Please Choose:");}while(ch=getch(),ch!='1'&&ch!='2'&&ch!='3'&&ch!='4'&&ch!='5');return ch;}void main(){polynode *a,*b,*c;char ch;do{clrscr();ch=caiDan();printf("%c",ch);getch();printf("\n");switch(ch){case '1': printf("Create A list\n");a=createList();printf("A list was created successfully");getch();break;case '2': printf("Create B list\n");b=createList();printf("B list was created successfully");getch();break;case '3': c=POLYADD(a,b);printf("C(C=A+B) list was created successfully\n");getch();break;case '4': printf("A List:\t");display(a);printf("\nB List:\t");display(b);printf("\nC List:\t");display(c);getch();break;case '5': exit(0);}}while(ch!='5');}。