• 一元多项式相加问题（两种方法）

    一元多项式的相加问题，主要运用了线性结构的合并，在合并线性结构的基础上，增加判断，所以我们可以将这个问题理解为一个复杂的线性表合并问题 

    目录

    问题描述

    一、顺序表法

    1.1 初始化并创建顺序表

    1.2 一元多项式相加算法

    1.3 完整代码

    二、单链表法

    1.1 初始化并创建链表

    1.2 一元多项式相加算法

    1.3 完整代码

    三、运行结果

    附：系列文章

    问题描述

    【问题描述】

    用线性表存放一元多项式，实现两个一元多项式相加，输出结果多项式。
    【输入形式】

    分两行依次输入两个一元多项式，按指数由低到高依次输入表达式各项的系数和指数，输入字符结束，如果输入的某项系数为0，则不建立该项。

    【输出形式】

    按指数由低到高依次输出结果表达式各项的系数和指数，如果结果表达式为空则不输出。

    【样例输入1】

    7 0 3 1 9 8 5 17  10 21 a

    8 1 22 2 -9 8 a

    【样例输出1】
    7.000000 0  11.000000 1 22.000000 2 5.000000  17 10.000000 21

    【样例输入2】

    22.2 1 a

    -22.2 1 b

    【样例输出2】

    一、顺序表法

    利用顺序表实现一元多项式的相加时，我们需要一个存放系数项的数组和一个存放指数项的数组，在执行合并的过程中对指数项进行判断，最后将系数等于零的项删除即可

    1.1 初始化并创建顺序表

    初始化和创建过程可以参考顺序表的创建，唯一不同的是这里是两个数组而已

    1. typedef struct List{
    2. 	double *base1;   //系数，double型变量   （理解为数组）
    3. 	int *base2;      //指数，int型变量      （数组）
    4. 	int len;
    5. 	int size;
    6. }List,*PList;
    7. int Init_List(PList L){
    8. 	L->base1=(double*)malloc(sizeof(double)*SIZE);  //初始化
    9. 	L->base2=(int*)malloc(sizeof(int)*SIZE);
    10. 	L->len=0;
    11. 	L->size=SIZE;
    12. 	return 1;
    13. }
    14. int Creat_List(PList L){   //创建的时候注意要给系数指数都赋值，其他就是创建顺序表的方法
    15. 	double a;
    16. 	int b;
    17. 	int i=0;
    18. 	while(scanf("%lf %d",&a,&b)==2){ 
    19.         if(a==0) continue;         //系数为零时不建立这个项，直接下一次循环 
    20. 		if(L->len>=L->size){
    21. 			L->base1=(double*)realloc(L->base1,sizeof(double)*(L->size+INCREAM));
    22. 			L->base2=(int*)realloc(L->base2,sizeof(int)*(L->size+INCREAM));
    23. 			L->size+=INCREAM;
    24. 		}
    25. 		L->base1[i]=a;
    26. 		L->base2[i++]=b;
    27. 		L->len++;
    28. 	}
    29. 	return 1;
    30. }

    1.2 一元多项式相加算法

    这个算法中一定要注意，当把所有元素都判断完并放入L3中后，一定要小心L3的长度不能忘

    1. int Connect_List(PList L1,PList L2,PList L3){
    2. 	int i=0,j=0,k=0;    //分别为L1,L2,L3的下标（L1,L2,L3是数组）
    3. 	if(L1->len+L2->len>L3->len){    //判断L3空间是否足够，不够时要重新开辟空间
    4. 		L3->base1=(double *)realloc(L3->base1,(L3->size+INCREAM)*sizeof(double));
    5. 		L3->base2=(int *)realloc(L3->base2,(L3->size+INCREAM)*sizeof(int));
    6. 		L3->size+=INCREAM;
    7. 	}
    8. 	while(ilen&&jlen){  //循环执行判断，直到一方元素循环完退出循环
    9. 		if(L1->base2[i]==L2->base2[j]){ //当L1,L2的指数项相等时，L3的系数项等于两者系数相加
    10.             L3->base1[k]=L1->base1[i]+L2->base1[j++]; 
    11.             L3->base2[k++]=L1->base2[i++];
    12. 		}else if(L1->base2[i]base2[j]){  //当L1指数项较小时，L3的系数就是L1
    13. 			L3->base1[k]=L1->base1[i];
    14. 			L3->base2[k++]=L1->base2[i++];
    15. 		}else{                                //当L2指数项较小时，L3的系数就是L2
    16. 			L3->base1[k]=L2->base1[j];
    17. 			L3->base2[k++]=L2->base2[j++];
    18. 		}
    19. 	}
    20. 	while(ilen){           //另一个循序表里剩余的元素都放入L3
    21. 		L3->base1[k]=L1->base1[i];
    22. 		L3->base2[k++]=L1->base2[i++];
    23. 	}
    24. 	while(jlen){          
    25. 		L3->base1[k]=L2->base1[j];
    26. 		L3->base2[k++]=L2->base2[j++];
    27. 	}
    28. 	L3->len=k;                //千万不能忘掉L3的长度！！
    29. 	for(i=0;ilen;i++){    //最后将L3中系数等于0的项删除
    30. 		if(L3->base1[i]==0){
    31. 			for(j=i;jlen-1;j++){
    32. 				L3->base1[j]=L3->base1[j+1];
    33. 				L3->base2[j]=L3->base2[j+1];
    34. 			}
    35. 			L3->len--;
    36. 		}
    37. 	}
    38. 	return 1;
    39. }

    1.3 完整代码

    1. #include
    2. #include
    3. #define SIZE 10
    4. #define INCREAM 10
    5. typedef struct List{
    6. 	double *base1;
    7. 	int *base2;
    8. 	int len;
    9. 	int size;
    10. }List,*PList;
    11. int Init_List(PList L){
    12. 	L->base1=(double*)malloc(sizeof(double)*SIZE);
    13. 	L->base2=(int*)malloc(sizeof(int)*SIZE);
    14. 	L->len=0;
    15. 	L->size=SIZE;
    16. 	return 1;
    17. }
    18. int Creat_List(PList L){
    19. 	double a;
    20. 	int b;
    21. 	int i=0;
    22. 	while(scanf("%lf %d",&a,&b)==2){
    23.         if(a==0) continue;
    24. 		if(L->len>=L->size){
    25. 			L->base1=(double*)realloc(L->base1,sizeof(double)*(L->size+INCREAM));
    26. 			L->base2=(int*)realloc(L->base2,sizeof(int)*(L->size+INCREAM));
    27. 			L->size+=INCREAM;
    28. 		}
    29. 		L->base1[i]=a;
    30. 		L->base2[i++]=b;
    31. 		L->len++;
    32. 	}
    33. 	return 1;
    34. }
    35. int Print_List(PList L){
    36. 	int i;
    37. 	for(i=0;ilen;i++){
    38. 		printf("%lf %d ",L->base1[i],L->base2[i]);
    39. 	}
    40. 	printf("\n");
    41. 	return 1;
    42. }
    43. int Connect_List(PList L1,PList L2,PList L3){
    44. 	int i=0,j=0,k=0;
    45. 	if(L1->len+L2->len>L3->len){
    46. 		L3->base1=(double *)realloc(L3->base1,(L3->size+INCREAM)*sizeof(double));
    47. 		L3->base2=(int *)realloc(L3->base2,(L3->size+INCREAM)*sizeof(int));
    48. 		L3->size+=INCREAM;
    49. 	}
    50. 	while(ilen&&jlen){
    51. 		if(L1->base2[i]==L2->base2[j]){
    52.             L3->base1[k]=L1->base1[i]+L2->base1[j++];
    53.             L3->base2[k++]=L1->base2[i++];
    54. 		}else if(L1->base2[i]base2[j]){
    55. 			L3->base1[k]=L1->base1[i];
    56. 			L3->base2[k++]=L1->base2[i++];
    57. 		}else{
    58. 			L3->base1[k]=L2->base1[j];
    59. 			L3->base2[k++]=L2->base2[j++];
    60. 		}
    61. 	}
    62. 	while(ilen){
    63. 		L3->base1[k]=L1->base1[i];
    64. 		L3->base2[k++]=L1->base2[i++];
    65. 	}
    66. 	while(jlen){
    67. 		L3->base1[k]=L2->base1[j];
    68. 		L3->base2[k++]=L2->base2[j++];
    69. 	}
    70. 	L3->len=k;
    71. 	for(i=0;ilen;i++){
    72. 		if(L3->base1[i]==0){
    73. 			for(j=i;jlen-1;j++){
    74. 				L3->base1[j]=L3->base1[j+1];
    75. 				L3->base2[j]=L3->base2[j+1];
    76. 			}
    77. 			L3->len--;
    78. 		}
    79. 	}
    80. 	return 1;
    81. }
    82. int main(){
    83. 	List L1,L2,L3;
    84. 	Init_List(&L1);
    85. 	Init_List(&L2);
    86. 	Init_List(&L3);
    87. 	Creat_List(&L1);
    88. 	getchar();
    89. 	Creat_List(&L2);
    90. 	Connect_List(&L1,&L2,&L3);
    91. 	Print_List(&L3);
    92. 	return 0;
    93. }

    二、单链表法

    运用单链表实现一元多项式相加的过程和顺序表类似，核心算法思想就是循环判断，将指数较小的项放入第三个表，当指数项相等时系数相加放入第三个表

    1.1 初始化并创建链表

    初始化和创建过程就是创建单链表的过程，唯一不同的也是我们有两个数据域

    1. typedef struct Node{
    2. 	double data1;    //系数
    3. 	int data2;           //指数
    4. 	struct Node * next;
    5. }Node,*PNode;
    6. PNode Init_Node(){           //初始化和创建发放就是链表的创建方法
    7. 	PNode head=(PNode)malloc(sizeof(Node));
    8. 	head->next=NULL;
    9. 	return head;
    10. }
    11. int Creat_Node(PNode head){
    12. 	double a;
    13. 	int b;
    14.     PNode p=head;
    15. 	while(scanf("%lf %d",&a,&b)==2){
    16.         if(a==0) continue;        //系数为0，不建立该项
    17. 		PNode q=(PNode)malloc(sizeof(Node));
    18. 		q->data1=a;
    19. 		q->data2=b;
    20. 		p->next=q;
    21. 		p=q;
    22. 	}
    23. 	p->next=NULL;
    24. 	return 1;
    25. }

    1.2 一元多项式相加算法

    算法思想与顺序表相同，循环判断，但是在单链表中，当我们遇到系数相加为零时可以直接释放，不连接到第三个单链表的后面，这正是单链表实现这个问题的一大亮点

    1. PNode Connect_Node(PNode head1,PNode head2,PNode head3){
    2. 	PNode p,q,r;
    3. 	r=head3;     //第三个单恋表
    4. 	p=head1->next;
    5. 	q=head2->next;
    6. 	while(p&&q){
    7. 		if(p->data2data2){    //判断将指数较小的项连接到r后面
    8. 			PNode s=(PNode)malloc(sizeof(Node));  //我们需要一个新的临时单链表
    9. 			s->data1=p->data1;
    10. 			s->data2=p->data2;
    11. 			r->next=s;
    12. 			r=s;
    13. 			p=p->next;
    14. 		}else if(p->data2==q->data2){   //当指数项相等时
    15. 			PNode s=(PNode)malloc(sizeof(Node));
    16. 			s->data1=p->data1+q->data1;   
    17. 			s->data2=p->data2;
    18. 			if(s->data1==0){  //判断两表系数相加是否为零
    19. 				free(s);     //为零时释放s
    20. 			}else{
    21. 				r->next=s;    //不为零时连接到r后面
    22. 				r=s;
    23. 			}
    24. 			p=p->next;
    25. 			q=q->next;
    26. 		}else{             //q的指数项较小，连接到r后面
    27. 			PNode s=(PNode)malloc(sizeof(Node));
    28. 			s->data1=q->data1;
    29. 			s->data2=q->data2;
    30. 			r->next=s;
    31. 			r=s;
    32. 			q=q->next;
    33. 		}		
    34. 	}
    35. 	if(p){       //最后还是要判断一下哪个表还有剩余元素，放入r后面
    36. 		r->next=p;
    37. 	}else if(q){
    38. 		r->next=q;
    39. 	}else{
    40. 		r->next=NULL;
    41. 	}
    42. 	return r;
    43. }

    1.3 完整代码

    1. #include
    2. #include
    3. typedef struct Node{
    4. 	double data1;
    5. 	int data2;
    6. 	struct Node * next;
    7. }Node,*PNode;
    8. PNode Init_Node(){
    9. 	PNode head=(PNode)malloc(sizeof(Node));
    10. 	head->next=NULL;
    11. 	return head;
    12. }
    13. int Creat_Node(PNode head){
    14. 	double a;
    15. 	int b;
    16.     PNode p=head;
    17. 	while(scanf("%lf %d",&a,&b)==2){
    18.         if(a==0) continue;
    19. 		PNode q=(PNode)malloc(sizeof(Node));
    20. 		q->data1=a;
    21. 		q->data2=b;
    22. 		p->next=q;
    23. 		p=q;
    24. 	}
    25. 	p->next=NULL;
    26. 	return 1;
    27. }
    28. PNode Connect_Node(PNode head1,PNode head2,PNode head3){
    29. 	PNode p,q,r;
    30. 	r=head3;
    31. 	p=head1->next;
    32. 	q=head2->next;
    33. 	while(p&&q){
    34. 		if(p->data2data2){
    35. 			PNode s=(PNode)malloc(sizeof(Node));
    36. 			s->data1=p->data1;
    37. 			s->data2=p->data2;
    38. 			r->next=s;
    39. 			r=s;
    40. 			p=p->next;
    41. 		}else if(p->data2==q->data2){
    42. 			PNode s=(PNode)malloc(sizeof(Node));
    43. 			s->data1=p->data1+q->data1;
    44. 			s->data2=p->data2;
    45. 			if(s->data1==0){
    46. 				free(s);
    47. 			}else{
    48. 				r->next=s;
    49. 				r=s;
    50. 			}
    51. 			p=p->next;
    52. 			q=q->next;
    53. 		}else{
    54. 			PNode s=(PNode)malloc(sizeof(Node));
    55. 			s->data1=q->data1;
    56. 			s->data2=q->data2;
    57. 			r->next=s;
    58. 			r=s;
    59. 			q=q->next;
    60. 		}		
    61. 	}
    62. 	if(p){
    63. 		r->next=p;
    64. 	}else if(q){
    65. 		r->next=q;
    66. 	}else{
    67. 		r->next=NULL;
    68. 	}
    69. 	return r;
    70. }
    71. int Print_Node(PNode head){
    72. 	PNode p=head->next;
    73. 	while(p){
    74. 		printf("%lf %d ",p->data1,p->data2);
    75. 		p=p->next;
    76. 	}
    77. 	printf("\n");
    78. 	return 1;
    79. }
    80. int main(){
    81. 	PNode p,q,r;
    82. 	p=Init_Node();
    83. 	q=Init_Node();
    84. 	r=Init_Node();
    85. 	Creat_Node(p);
    86. 	getchar();
    87. 	Creat_Node(q);
    88. 	Connect_Node(p,q,r);
    89. 	Print_Node(r);
    90. 	return 1;
    91. }

    三、运行结果

    附：系列文章

    序号文章目录直达链接
    1顺序表的十个基本操作（全）https://want595.blog.csdn.net/article/details/127139051
    2单链表的十三个基本操作（全）https://want595.blog.csdn.net/article/details/127139598
    3四种创建单链表的方法https://want595.blog.csdn.net/article/details/127017405
    4删除重复元素（顺序表、单链表）https://want595.blog.csdn.net/article/details/127023468
    5两个有序表的合并（三种方法）https://want595.blog.csdn.net/article/details/127104602
    6一元多项式相加问题（两种方法）https://want595.blog.csdn.net/article/details/127131351
    7约瑟夫环问题（三种方法）https://want595.blog.csdn.net/article/details/127019472
    8顺序栈与链栈https://want595.blog.csdn.net/article/details/127035609
    9顺序循环队列与链队列https://want595.blog.csdn.net/article/details/127040115
    10后缀表达式的转换（栈的运用）https://want595.blog.csdn.net/article/details/127088466
    11简单表达式的计算（两种方法）https://want595.blog.csdn.net/article/details/127121720
    12next数组（详细求法）https://want595.blog.csdn.net/article/details/127217629
    13BF算法（具体应用）https://want595.blog.csdn.net/article/details/127138894
    14串的模式匹配相关问题（BF算法、KMP算法）https://want595.blog.csdn.net/article/details/127182721
    15二叉树的遍历（七种方法）https://want595.blog.csdn.net/article/details/127472445
  • 相关阅读:
    山东2024年高企申报条件
    oracle实验七（安全管理）
    深入理解Java线程
    2022 年 Java 行业分析报告
    java扶贫平台计算机毕业设计MyBatis+系统+LW文档+源码+调试部署
    面试经典（7/150）买卖股票的最佳时机2
    C++ std::string 删除指定字符
    Python测试框架 Pytest —— mock使用（pytest-mock）
    代码库管理工具Git介绍
    RocketMQ源码(十九)之消费者Rebalance
  • 原文地址：https://blog.csdn.net/m0_68111267/article/details/127131351