西电oj数据结构-276多项式加减_Yeyu__的博客-程序员宅基地

技术标签: 算法  c语言  数据结构  

标题

西电数据结构与算法分析-276 多项式加减法——链表

题目要求

试题名称 多项式加减法
时间限制: 1 秒
内存限制: 10000KB

问题描述
给定两个多项式,求解其和与差。多项式的项数为M,而最高幂次为N。(1<=M<=10,1<=N<=1000000)

输入说明
输入包含了两个多项式,分为两行给出(同行数据间以空格隔开):

每一行为两组数据:第一组为一个值,表示多项式的非零项数M;第二组为2*M个值,每相邻两个值表达一个多项式的非零系数项,分别为系数值、幂次值(其中各项按照幂次的降序排列)。但如果多项式没有非零系数项,则仅用0(M的值)表示,后面没有系数和幂次值出现。例如,第一行的数据为:4 1 10 2 5 3 4 4 0,那么表示多项式有4项,对应的多项式为:x10+2x5+3x^4+4. 又例如,第二行的数据为:4 1 8 -2 5 3 3 4 1,表示多项式有4项,对应的多项式为:x8-2x5+3x^3+4x。那么上述两个多项式相加的输出结果应为:6 1 10 1 8 3 4 3 3 4 1 4 0,对应的多项式为:x10+x8+3x4+3x3+4x+4.第一个多项式减去第二个多项式的输出结果为:7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0,对应多项式:x10-x8+4x5+3x4-3x^3-4x+4.

输出说明
输出包含了两个多项式,分为两行给出(同行数据间以空格隔开):

第一行是多项式相加的结果,第二行是多项式相减的结果。每一行为两组数据:第一组为一个值,表示多项式的非零项数M;第二组为2*M个值,每相邻两个值表达一个多项式的非零系数项,分别为系数值、幂次值(其中各项按照幂次的降序排列)。但如果多项式没有非零系数项,则仅用0(M的值)表示,后面没有系数和幂次值出现。

输入样例
例1:
4 1 10 2 5 3 4 4 0
4 1 8 -2 5 3 3 4 1

输出样例
例1:
6 1 10 1 8 3 4 3 3 4 1 4 0
7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0

提示:
用链表表示多项式

*解题思路
1.读取,使用头插法或者尾插法都可以,先定义整形数组存放一个多项式的数据,定义链表之后读入该组数据。

2.加减,双重循环判断两个多项式中是否存在相等幂次的值,对其中一个链表对应项的系数值进行加减的数值变动。

3.排序,题干要求中,输出的多项式需先输出项数,再由幂次从高到低输出,对于系数为0的项进行忽略处理,多项式若不含非0项则仅输出 0 。

总结
1.经常遗忘链表的重置,在上个循环使用过的链表,需要在另一个循环使用,导致循环走不出来。

2.分步骤去完成功能,出现异常也分步骤去测试才能有效率解决问题。

写的不好见谅。
源代码

``

#include<stdlib.h>
typedef struct LinkList{
	int num1;  //系数 
	int num2;  //指数 
	struct LinkList *next;
}LinkList;
void print(LinkList *&L,int n){         //排序并输出 	
    int flag =0,N =n; 
	LinkList *t1,*t2,*t3;
	t1 =L;
	t3 = L;              
	for(int k=0;k<n;k++){            //该步骤为了筛选系数全为0的结果 
   	    if(L->num1==0){N--;}
   	    else{flag = 1;}	
   	    L = L->next;
	}
	if(flag==0){
		printf("0\n");
	}
    else{                
      printf("%d ",N);             //排序降幂交换 
      for(int j =0;j<n;j++){
   	    t2 = t1->next;
   	     if(t2==NULL){break;}
           for(int k=j+1;k<n;k++){
             	if(t1->num2<t2->num2){
      	          	int temp1,temp2;
      		        temp1 = t1->num1;
      	         	temp2 = t1->num2;
      	        	t1->num1 = t2->num1;
      	        	t1->num2 = t2->num2;
      	          	t2->num1 = temp1;
      	         	t2->num2 = temp2;
		         }
		       t2 = t2->next;
	       }	
	       t1 = t1->next;	
	}
	L = t3;   
    for(int k=0;k<n;k++){     //输出系数不为0的项 
    	if(L->num1 != 0){         
		printf("%d %d ",L->num1,L->num2);
			L = L->next;}
		}
	printf("\n");
   }
}    
void Creat(LinkList *&L1,LinkList *&L2,LinkList*&L3,int n1,int n2,int num1[100],int num2[100]){
	int n3 = n2;
	 L1 = (LinkList*)malloc(sizeof(LinkList));
	 L2 = (LinkList*)malloc(sizeof(LinkList));
	 L3 = (LinkList*)malloc(sizeof(LinkList));
	 L1  = NULL;
	 L2  = NULL;
	 L3  = NULL;
	 LinkList *s1,*s2,*s3;
	 for(int i=0;i<2*n1;i+=2){           // 使用头插法将数据传入链表其中L2、L3的数值一致方便加减处理 
	 	s1 =(LinkList*)malloc(sizeof(LinkList));       
	 	s1->num1 =num1[i];
	 	s1->num2 =num1[i+1];
		 s1->next = L1;
	 	L1 = s1;
	 }
	 for(int i=0;i<2*n2;i+=2){
	 	s2 =(LinkList*)malloc(sizeof(LinkList));
	 	s2->num1 =num2[i];
	 	s2->num2 =num2[i+1];
		s2->next = L2;
	 	L2 = s2;
	 }
	  for(int i=0;i<2*n2;i+=2){
	 	s3 =(LinkList*)malloc(sizeof(LinkList));
	 	s3->num1 =num2[i];
	 	s3->num2 =num2[i+1];
		s3->next = L3;
	 	L3 = s3;
	 }
	 //处理数据
	 int flag;
	 for(int i=0;i<n1;i++){
	 	flag = 1;
	 	for(int j=0;j<n2;j++){
	 		if(L1->num2 == L2->num2){
	 			L2->num1 = L2->num1 + L1->num1;
	 			flag = 0;
	 			break;
			 }
			 else L2 = L2->next;
		 }L2 = s2;  
		 if(flag ==1){ //L1中出现L2中没有的元素 
		 	s2 = (LinkList*)malloc(sizeof(LinkList));
		 	s2->num1 = L1->num1;
		 	s2->num2 = L1->num2;
		 	s2->next = L2;
		 	n2++;
		 }
			L2 = s2;
		 L1 = L1->next;
	 }
	 L1 = s1; //重置
	 for(int i=0;i<n3;i++){
	 	flag = 1;
	 	for(int j=0;j<n1;j++){
	 		if(L3->num2 == L1->num2){
	 			L1->num1 = L1->num1 - L3->num1;
	 			flag = 0;
	 			break;
			 }
			   else L1 = L1->next;
		 }
		      L1 = s1;  
		 if(flag ==1){ //L3中出现L1中没有的元素 
		 	s1 = (LinkList*)malloc(sizeof(LinkList));
		 	s1->num1 =(-1)*L3->num1;
		 	s1->num2 = L3->num2;
		 	s1->next = L1;
		 	n1++;
		 }	L1 = s1;
		 L3 = L3->next;               
	 }
	print(L2,n2);
	print(L1,n1);
}
int main(){
	int n1,n2,num1[100],num2[100];         //主函数中实现数据读入 
	scanf("%d",&n1);
	for(int i=0;i<2*n1;i++){
		scanf("%d",&num1[i]);
	}
	scanf("%d",&n2);
	for(int j=0;j<2*n2;j++){
		scanf("%d",&num2[j]);
	}
	LinkList *L1,*L2,*L3;                  //创建链表 
	Creat(L1,L2,L3,n1,n2,num1,num2);       //传入 
	return 0;
}
//yeyu_

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Yeyu__/article/details/120619811

智能推荐

随便推点