数据结构_实验一_线性表的操作(二)_一元n次加法操作

不念不忘少年蓝@ 2021-11-23 03:20 201阅读 0赞

二、一元n次加法操作  
 2.1 需求分析  
 2.2 概要设计  
 2.3 详细设计  
 2.4 调试分析  
 2.5 用户使用说明  
 2.6 测试结果  
 2.7 附录

#### 二、一元n次加法操作 ####

###### 2.1 需求分析 ######

A、顺序表

输出形式：  
array1(column\_size1=5) : (the first row is exponent , the second row is coefficient .)  
指数行  
系数行  
array2(column\_size2=8) : (the first row is exponent , the second row is coefficient .)  
指数行  
系数行  
array3 : (the first row is exponent , the second row is coefficient .)  
相加后的指数行  
相加后的系数行

功能：用户输入两个一元多项式，程序实现相加，输出最后结果

数据范围：  
指数：正整数 系数：全体实数

测试数据：  
正确输入：输入值范围内 正确结果 错误输入：输入值超出规定范围 跳出程序

B、链表  
输出形式：  
L1 :  
coefficient exponent (exp=-1 to quit)  
系数 指数  
L2 :  
coefficient exponent (exp=-2 to quit)  
系数 指数  
L3 :  
coefficient exponent  
相加后的系数 相加后的指数

功能：用户输入两个一元多项式，程序实现相加，输出最后结果

数据范围：  
指数：正整数 系数：全体实数

测试数据：  
正确输入：输入值范围内 正确结果 错误输入：输入值超出规定范围 跳出程序

###### 2.2 概要设计 ######

A、顺序表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]  
B、链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]

###### 2.3 详细设计 ######

A、顺序表

创建二维数组1、2、3  
初始化数组3每项均为0  
输入数组1、2的每一项系数、指数  
while(数组1、2有一个输出完全）  
\{  
比较数组1、2的指数大小  
if(数组1指数>数组2指数）  
\{  
数组3的系数、指数=数组2的系数、指数  
数组2、3往后摞一位  
\}  
else if (数组1的指数== 数组2的指数）  
\{  
If(数组1的系数+数组2的系数==0）  
\{  
数组1、2往后摞一位  
\}  
else  
\{  
数组3的指数=数组1的指数  
数组3的系数=数组1的系数+数组2的系数  
数组1、2、3均往后摞一位  
\}  
\}  
else if（数组1的指数<数组2的指数）  
\{  
数组3的指数、系数=数组1的指数、系数  
数组1、3往后摞一位  
\}  
while(数组1未完全输出）  
\{  
数组3的指数、系数=数组1的指数、系数  
数组1、3往后摞一位  
\}  
while(数组2未完全输出）  
\{  
数组3的指数、系数=数组2的指数、系数  
数组1、2往后摞一位  
\}  
输出数组3的指数非零项  
\}

B、链表  
创建链表1、2、3  
输入链表1、2的每一项系数、指数  
while(链表1、2有一个指针为空）  
\{  
比较链表1、2的指数大小  
if(链表1指数>链表2指数）  
\{  
链表3的系数、指数=链表2的系数、指数  
链表2、3指针指向下一个结点  
\}  
else if (链表1的指数== 链表2的指数）  
\{  
If(链表1的系数+链表2的系数==0）  
\{  
链表1、2指针指向下一个结点  
\}  
else  
\{  
链表3的指数=链表1的指数  
链表3的系数=链表1的系数+链表2的系数  
链表1、2、3指针指向下一个结点  
\}  
\}  
else if（链表1的指数<链表2的指数）  
\{  
链表3的指数、系数=链表1的指数、系数  
链表1、3指针指向下一个结点  
\}  
while(链表1的指针不为空）  
\{  
链表3的指数、系数=链表1的指数、系数  
链表1、3指针指向下一个结点  
\}  
while(链表2的指针不为空）  
\{  
链表3的指数、系数=链表2的指数、系数  
链表1、2指针指向下一个结点  
\}  
输出链表3  
\}

###### 2.4 调试分析 ######

A、顺序表

算法时间复杂度n2，空间复杂度由输入数组大小而定。  
遇到问题：二维数组行下标错误，应该从0开始，误写为1开始；  
改进：生成动态数组，由用户确定数组大小

B、链表  
算法时间复杂度n，空间复杂度大小由用户输入数据多少确定。  
遇到问题：头指针弄丢了，建立新的指针，将头指针赋给新指针，调用时用新指针，输出时再调用头指针。  
改进：将合并的链表归于已经建立的链表1或2中，而不是新建链表3

###### 2.5 用户使用说明 ######

A、顺序表

根据提示，在第一行输入多项式的指数，每输入一个，空一格，输入足够数值时，enter换行，同样的输入方法输入对应指数的系数，enter进入第二个多项式的输入，同样的输入方法，输入完成后enter键输出结果

B、链表  
根据提示，先陆续输入多项式1每一项的系数、指数，先输入系数，空格，输入指数，enter换行，输入下一项，完成输入后，下一项的系数随意，指数输入为-1,跳出输入多项式1，接下来，同样输入方法输入多项式2，输入完成后，最后一项的系数随意，指数输入-2。

###### 2.6 测试结果 ######

A、顺序表

![在这里插入图片描述][20190725190946368.png]  
![在这里插入图片描述][20190725190956217.png]  
B、链表  
![Alt][]  
![在这里插入图片描述][20190725191019536.png]

###### 2.7 附录 ######

A、顺序表

#include<iostream>
    using namespace std;
    
    //第一行指数，第二行系数
    const int column_size1=5;     //二维数组1的列数
    const int column_size2=8;     //二位数组2的列数
    const int column_size3=13;    //二维数组3的列数
    //合并二维数组12函数声明
    int merge(const int array1[2][column_size1],const int array2[2][column_size2]);
     int main()
    { 
    	int array1[2][column_size1], array2[2][column_size2];    //声明二维数组12
    	//创建array1
    	cout<<"array1(column_size1=5) : (the first row is exponent , the second row is coefficient .) "<<endl;
    	for (int row1=0; row1<2; row1++)         //循环输入二维数组1的数据，此循环控制行
    	{ 
    		for (int col1=0; col1<column_size1; col1++)  //循环控制每行列的每个数据的输入
    			cin>>array1[row1][col1];             //输入数据
    	}
    	//创建array2
    	cout<<"array2(column_size2=8) : (the first row is exponent , the second row is coefficient .) "<<endl;
    	for (int row2=0; row2<2; row2++)      //二维数组2的行控制
    	{ 
    		for (int col2=0; col2<column_size2; col2++)  //二位数组2的列控制
    			cin>>array2[row2][col2];             //输入每行每列的数据
    	}
    	merge(array1, array2);                    //调用合并函数，合并二维数组12
    	return 0;
    }
    
    int merge(const int array1[2][column_size1],const int array2[2][column_size2])
    { 
        int array3[2][column_size3];        //声明二维数组3
        //创建array3
    	for (int row3=0; row3<2; row3++)    //控制二维数组3的行
    	{ 
    		for(int col3=0; col3<column_size3; col3++)  //控制二维数组3的列
    			array3[row3][col3]=0;              //初始化每个数据均为0
        }
    	int a, b, c;
        a=b=c=0;
    while(a<column_size1&&b<column_size2) 
    //a控制二维数组1的列数，b控制二维数组2的列数
        { 
            if (array1[0][a]==array2[0][b])            //二维数组12的数据相等
            { 
                if (array1[1][a]+array2[1][b]==0)      //系数相加为0
                    { 
                        ++a;                    //二维数组1的列数+1
                        ++b;                    //二维数组2的列数+1
                    }
                else                            //系数相加不为0
                { 
                    array3[0][c]=array1[0][a];     
    //系数赋值，二维数组3的第一行此列的数据等于二维数组1的此列的数据 
                    array3[1][c]=array1[1][a]+array2[1][b];
    //指数赋值，二维数组3的第二行此列的数据等于二维数组1和二维数组2此列的数据之和
                    ++a;        //二维数组1的列数+1
                    ++b;        //二维数组2的列数+1
                    ++c;        //二位数组3的列数+1
                }
            }
            else if (array1[0][a]<array2[0][b])   //二维数组1的指数小于二维数组2的指数
           { 
               array3[0][c]=array1[0][a]; 
    //数组3的第一行的此列数据=数组1的第一行的此列数据
               array3[1][c]=array1[1][a];
    //数组3的第二行的此列数据=数组1的第二行的此列数据
               ++c;    //数组3的列数+1
               ++a;    //数组1的列数+1
           }
           else if (array1[0][a]>array2[0][b])  //数组1的指数>数组2的指数
            { 
                array3[0][a]=array2[0][b];
    //数组3的第一行的此列数据=数组2的第一行的此列数据
                array3[1][c]=array2[1][b];
    //数组3的第二行的此列数据=数组2的第二行的此列数据
                ++c;    //数组3的列数+1
                ++b;    //数组2的列数+1
            }
        }
        if (a<column_size1)        //数组1未输出完毕
        { 
            for (; a<column_size1; a++)  //控制数组1的列数
                { 
                    array3[0][c]=array1[0][a];
    //数组3的第一行的此列数据=数组1的第一行的此列数据
    				array3[1][c]=array1[1][a];
    //数组3的第二行的此列数据=数组1的第二行的此列数据
    				++c;     //数组3的列数+1
    			}
        }
        if (b<column_size2)        //数组2未输出完毕
        { 
            for (; b<column_size2; b++)
            { 
                array3[0][c]=array2[0][b];
    //数组3的第一行的此列数据=数组2的第一行的此列数据
                array3[1][c]=array2[1][b];
    //数组3的第二行的此列数据=数组2的第二行的此列数据
                ++c;   //数组3的列数+1
            }
        }
    	//输出array3
    	cout<<"array3 : (the first row is exponent , the second row is coefficient .) "<<endl;
    	for (int j=0; j<2; j++)  //控制数组3的行数
    	{ 
    		for (int col=0; col<column_size3; col++)   //控制数组3的列数
    		{ 
    			if(array3[j][col]!=0)           //如果数组3的数据不为0
    				cout<<array3[j][col]<<" ";  //输出此项数据
    		}
    		cout<<endl;
    	}
    	cout<<endl;
    	return 0;
    }

B、链表

#include<iostream>
    #include<stdlib.h>
    #include<time.h>
    using namespace std;
    
    typedef struct node{         //创建链表的结构体
    	int coe;
    	int exp;
    	struct node *next;
    }node;
    
    //AB单链表相加为C 主函数
    int merge(node *L1, node *L2);
    int main()
    { 
    	node *L1, *L2, *p1, *p2, *t1, *t2;
    
    	L1=new node;
    	t1=L1;
    	L2=new node;
    	t2=L2;
    
    	int coe1, coe2, exp1, exp2;
    	cout<<"L1 : "<<endl<<"coefficient exponent (exp=-1 to quit)"<<endl;
    	cin>>coe1>>exp1;
    	while(exp1!=-1)             //输入链表1的多项式的每一项指数，系数
    	{ 
    		p1=new node;
    		p1->coe=coe1;
    		p1->exp=exp1;
    		t1->next=p1;
    		t1=p1;
    		cin>>coe1>>exp1;
    	}
    	t1->next=NULL;
    	cout<<"L2 : "<<endl<<"coefficient exponent (exp=-2 to quit)"<<endl;
    	cin>>coe2>>exp2;
    	while (exp2!=-2)             //输入链表1的多项式的每一项指数，系数
    	{ 
    		p2=new node;
    		p2->coe=coe2;
    		p2->exp=exp2;
    		t2->next=p2;
    		t2=p2;
    		cin>>coe2>>exp2;
    	}
    	t2->next=NULL;
    	merge(L1,L2);        //调用合并函数
    	return 0;
    }
    //AB单链表相加为C
    int merge(node *L1, node *L2)
    { 
    	node *L3, *p3, *t3;
    	L3=new node;
    	t3=L3;
    	while (L1->next!=NULL&&L2->next!=NULL)     //链表1、2的指针为空时跳出循坏
    	{ 
    		if (L1->next->exp==L2->next->exp)        //链表1、2的数据相等 
    		{ 
    			if (L1->next->coe+L2->next->coe==0)  //链表1、2的数据相加为0
    			{ 
    				L1->next=L1->next->next;       //链表的指针指向下一个结点的指针域
    				L2->next=L2->next->next;       //链表的指针指向下一个结点的指针域
    			}
    			Else                            //链表1、2的数据相加不为0
    			{ 
    				p3=new node;
    				p3->coe=L1->next->coe+L2->next->coe;  
     //新建结点的系数等于链表1、2此结点数据的和
    				p3->exp=L1->next->exp;
    //新建结点的指数等于链表1的指数
    				t3->next=p3;  //链表3指向新建结点
    				t3=p3;       //将新建结点赋给链表3的此结点
    				L1->next=L1->next->next;   //链表1的指针指向下一个结点
    				L2->next=L2->next->next;   //链表2的指针指向下一个结点
    			}
    		}
    		else if (L1->next->exp<L2->next->exp)   //链表1的指数小于链表2的指数
    		{ 
    			p3=new node;                 //新建结点
    			p3->coe=L1->next->coe;         //将链表1的系数赋给新建结点的系数 
    			p3->exp=L1->next->exp;         //将链表1的指数赋给新建结点的系数
    			t3->next=p3;                  //链表3指向新建结点
    			t3=p3;                       //将新建结点赋给链表3的此结点
    			L1->next=L1->next->next;       //链表1的指针指向下一个结点的指针
    		}
    		else if(L1->next->exp>L2->next->exp)  //链表1的指数>链表2的指数
    		{ 
    			p3=new node;                //新建结点
    			p3->coe=L2->next->coe;        //将链表2的系数赋给新建结点的系数
    			p3->exp=L2->next->exp;        //将链表2的指数赋给新建结点的指数
    			t3->next=p3;                 //链表3的指针指向新建结点
    			t3=p3;                      //将新建结点赋给链表3的此结点
    			L2->next=L2->next->next;      //链表2的指针指向下一个结点的指针域
    		}
    	}
    	while (L1->next!=NULL)               //链表1未完全输出
    	{ 
    		p3=new node;
    		p3->coe=L1->next->coe;
    		p3->exp=L1->next->exp;
    		t3->next=p3;
    		t3=p3;
    		L1->next=L1->next->next;
    	}
    	while (L2->next!=NULL)             //链表2未完全输出
    	{ 
    		p3=new node;                //新建结点
    		p3->coe=L2->next->coe;        //将链表2的系数赋给新建结点的系数
    		p3->exp=L2->next->exp;        //将链表2的指数赋给新建结点的指数
    		t3->next=p3;                 //将新建结点赋给链表3的此结点
    		t3=p3;                      //将新建结点赋给链表3的此结点
    		L2->next=L2->next->next;      //链表2的指针指向下一个结点的指针域
    	}
    	t3->next=NULL;                  //链表3的下一个指针域为空
    	cout<<"L3 : "<<endl<<"coefficient exponent"<<endl;
    	while (L3->next!=NULL)            //链表3指针为空时跳出循环
    	{ 
    		cout<<L3->next->coe<<" "<<L3->next->exp<<endl; 
    //输出链表3的每一项的系数、指数
    		L3->next=L3->next->next;      //链表3的指针指向下一个结点的指针
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70]: /images/20211122/e0d9ca5781fc4833ae4e69f72df6cd91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTY0NTU1_size_16_color_FFFFFF_t_70 1]: /images/20211122/f4b09f26e08a4c8e850a800a9b10fa10.png
[20190725190946368.png]: /images/20211122/be866f2fffa54d6d997b6ed5577d459e.png
[20190725190956217.png]: /images/20211122/9c07f416ab58432d94b3618b2014ec98.png
[Alt]: /images/20211122/91460d92b45a41c38b1f8c50e72707bb.png
[20190725191019536.png]: /images/20211122/b2a137f1cb614ee19624b0d25461e262.png