一元稀疏多项式计算器【数据结构课设】仿真界面 + 代码详解

痛定思痛。 2021-09-07 06:01 345阅读 0赞

### 一元稀疏多项式计算器 ###

--------------------

### 目录 ###

*   *   *  一元稀疏多项式计算器
         *  问题描述
         *  基本要求
         *  测试数据
         *  带界面版
         *  相关代码
         *  设计详解
         *   *  1、一元稀疏多项式的建立
             *  2.一元稀疏多项式的加法和减法运算
             *  3.一元稀疏多项式的打印和计算在x处的值

### 问题描述 ###

**设计一个一元稀疏多项式简单计算器。**

### 基本要求 ###

**（1）输入并建立多项式。**

（**2）输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci,ei分别是第i 项的系数和指数，序列按指数降序排列。**

**（3）实现多项式a和b相加，建立多项式a+b。**

**（4）实现多项式a和b相减，建立多项式a-b。**

**（5）计算多项式在x处的值。**

**（6）计算器的仿真界面。**

### 测试数据 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

### 带界面版 ###

博客地址： [一元稀疏多项式计算器仿真界面版][Link 1]

### 相关代码 ###

**不带界面，只包含数据结构的设计。**

#define _CRT_SECURE_NO_WARNINGS 
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    typedef struct Polynomial //多项式
    { 
    	float coef; //系数
    	int expn;   //指数
    	struct Polynomial *next;//指针
    } Polynomial, *Polyn;
    //创建一个头指针为head，项数为m的一元多项式
    Polyn CreatPolyn(Polyn head, int m)
    { 
    	head = (Polyn)malloc(sizeof(struct Polynomial));
    	head->next = NULL;
    	for (int i = 1; i <= m; i++)
    	{ 
    		Polyn p = (Polyn)malloc(sizeof(struct Polynomial));
    		printf("请输入第%d项的系数与指数：", i);
    		scanf("%f%d", &p->coef, &p->expn);
    		if (p->coef == 0) free(p);
    		else
    		{ 
    			Polyn q1, q2;
    			q1 = head;
    			q2 = head->next;
    			while (q2 != NULL && p->expn < q2->expn)
    			{ 
    				q1 = q2;
    				q2 = q2->next;
    			}
    			if (q2 != NULL && p->expn == q2->expn)
    			{ 
    				q2->coef += p->coef;
    				if (q2->coef == 0)
    				{ 
    					q1->next = q2->next;
    					free(q2);
    				}
    				free(p);
    			}
    			else
    			{ 
    				p->next = q2;
    				q1->next = p;
    			}
    		}
    	}
    	return head;
    }
    void printPoLlyn(Polyn head)
    { 
    	Polyn q = head->next;
    	int flag = 0;     //记录是否为第一项
    	if (!q)
    	{ 
    		puts("0");
    		puts("\n");
    		return;
    	}
    	while (q)
    	{ 
    		if (q->coef > 0 && flag == 1)
    		{ 
    			printf("+");
    		}
    		flag = 1;
    		if (q->coef != 1 && q->coef != -1)
    		{ 
    			printf("%g", q->coef);
    
    			if (q->expn == 1) printf("x");
    			else if (q->expn!=0) printf("x^%d", q->expn);
    		}
    		else
    		{ 
    			if (q->coef == 1)
    			{ 
    				if (q->expn == 0) printf("1");
    				else if (q->expn == 1) printf("x");
    				else printf("x^%d", q->expn);
    			}
    			if (q->coef == -1)
    			{ 
    				if (q->expn == 0) printf("-1");
    				else if (q->expn == 1) printf("-x");
    				else printf("-x^%d", q->expn);
    			}
    		}
    		q = q->next;
    	}
    	printf("\n");
    }
    int compare(Polyn a, Polyn b)//比较两个多项式的大小
    { 
    	if (a&&b)  // 多项式a和b均不为空
    	{ 
    		if (a->expn > b->expn) return 1;// a的指数大于b的指数
    		else if (a->expn < b->expn) return -1;
    		else return 0;
    	}
    	else if (!a&&b) return -1; //a为空，b不为空
    	else if (a&&!b) return 1;  //b为空，a不为空 
    	else if (!a&&!b)return 0;  //a,b均为空
    }
    Polyn addPolyn(Polyn a, Polyn b)  //求解a+b，并返回头结点head
    { 
    	Polyn head ,qc;
    	Polyn qa = a->next;
    	Polyn qb = b->next;
    	Polyn hc=(Polyn)malloc(sizeof(Polynomial));
    	hc->next = NULL;
    	head = hc;
    	while (qa || qb)
    	{ 
    		qc= (Polyn)malloc(sizeof(Polynomial));
    		if (compare(qa, qb) == 1)
    		{ 
    			qc->coef = qa->coef;
    			qc->expn = qa->expn;
    			qa = qa->next;
    		}
    		else if (compare(qa, qb) == 0) //指数相同，直接相加
    		{ 
    			qc->coef = qa->coef + qb->coef;
    			qc->expn = qa->expn ; 
    			qa = qa->next;
    			qb = qb->next;
    		}
    		else
    		{ 
    			qc->coef = qb->coef;
    			qc->expn = qb->expn;
    			qb = qb->next;
    		}
             
    		if (qc->coef != 0) //将该节点插入链表中
    		{ 
    			qc->next = hc->next;
    			hc->next = qc;
    			hc = qc;
    		}
    		else free(qc);		
    	}
    	return head;
    }
    Polyn subPolyn(Polyn a, Polyn b)
    { 
    	Polyn h = b;
    	Polyn p = b->next;
    	while(p)
    	{ 
    		p->coef *= -1;
    		p = p->next;
    	}
    	Polyn head = addPolyn(a, h);
    	for (Polyn i = h->next; i != 0; i = i->next)
    	{  
    		i->coef *= -1;
    	}		
    	return  head;
    }
    double value(Polyn head, int x) //计算x的值
    { 
    	double sum = 0;
    	for (Polyn p = head->next; p != 0; p = p->next)
    	{ 
    		int tmp = 1;
    		int expn = p->expn;
    		while(expn != 0) //指数不为0
    		{ 
    			if (expn < 0)   tmp /= x, expn++;
    			else if(expn>0) tmp *= x, expn--;
    		}
    		sum += p->coef*tmp;
    	}	
    	return sum;
    }
    int main()
    { 
    	int m;
    	Polyn a = 0, b = 0;
    	printf("请输入a的项数:");
    	scanf("%d", &m);
    	a = CreatPolyn(a, m);
    	printPoLlyn(a);
    	printf("请输入b的项数:");
    	scanf("%d", &m);
    	b = CreatPolyn(b, m);
    	printPoLlyn(b);
    	printf("输出 a+b：");
    	printPoLlyn(addPolyn(a, b));
    	printf("输出 a-b：");
    	printPoLlyn(subPolyn(a, b));
    	printf("请输入x的值：");
    	int x;
    	scanf("%d", &x);
    	printf("输出a的多项式的值为：%.2lf", value(a,x));
    	return 0;
    }
    /* 测试数据： 3 2 1 5 8 -3.1 11 3 7 0 -5 8 11 9 1 */

### 设计详解 ###

#### 1、一元稀疏多项式的建立 ####

**结构体的定义**

typedef struct Polynomial   //多项式
    { 
    	float coef;  //系数
    	int expn;   //指数
    	struct Polynomial *next;//指针
    } Polynomial, *Polyn;

使用带头结点的单链表存贮多项式，插入查找和删除较为方便。数据域中存贮系数和指数，指针域指向下一个节点的位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]  
**如果所示的存贮结构：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]

**设计思想：**

首先确定好多项式的项数`m`，新建立一个节点`p`，用来存贮读入的系数`coef`和项数`expn`。然后再定义两个指针`q1`和`q2`,一前一后，分别指向多项式的两个相邻节点。为了实现多项式的降序排列，这里我们利用插入排序的思想，如果`p`和`q2`的指数相同，即`p->expn == q2->expn`，则进行两个节点的合并。如果`p`的指数小于`q2`的指数，即`p->expn < q2->expn`，继续后移两个指针。否则，`p`的指数小于`q1`的指数，大于`q2`的指数，我们找到了插入的位置，将`p`节点插入两个节点中。执行`m`次插入操作，就将一元稀疏多项式的建立好了。最后注意要将系数`coef==0`的节点释放。

**定义两个指针：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]

**找到了插入位置，将节点p插入**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]

**代码**

//创建一个头指针为head，项数为m的一元稀疏多项式
    void CreatPolyn(Polyn head, int m)
    { 
    	for (int i = 1; i <= m; i++)
    	{ 
    		Polyn p = (Polyn)malloc(sizeof(struct Polynomial)); //新建节点p
    		printf("请输入第%d项的系数与指数：", i);
    		scanf("%f%d", &p->coef, &p->expn);
    		if (p->coef == 0) free(p);  //将系数为0的节点释放
    		else
    		{ 
    			Polyn q1, q2;     //两个指针一前一后
    			q1 = head;
    			q2 = head->next;
    			while (q2 != NULL && p->expn < q2->expn)  //p的指数小于q2的指数
    			{ 
    				q1 = q2;   //继续后移两个指针
    				q2 = q2->next;
    			}
    			if (q2 != NULL && p->expn == q2->expn)   //将相同指数的项进行合并
    			{ 
    				q2->coef += p->coef;   //合并两项
    				if (q2->coef == 0)
    				{ 
    					q1->next = q2->next;
    					free(q2);  //将系数为0的节点释放
    				}
    				free(p);   //将节点p释放
    			}
    			else
    			{ 
    				p->next = q2;    //将节点p插入到q1和q2之间
    				q1->next = p;
    			}
    		}
    	}
    }

#### 2.一元稀疏多项式的加法和减法运算 ####

**设计思想：**

关于多项式的加法运算。首先要定义一个比较函数`compare`，来比较两个多项式的每项指数大小。

我们从头到尾处理两个多项式的每一项。如果两项中，多项式`a`的项的指数大于多项式`b`的项的指数，那么将`a`的此项直接作为多项式`c`的一项。如果多项式`a`的指数等于多项式`b`的指数，将两项合并作为多项式`c`的一项。如果多项式`a`的指数小于多项式`b`的指数，那么将`b`的此项直接作为多项式`c`的一项。

因为多项式`a`和多项`b`的都是按照指数降序建立的，因此，**指数大的项会被先计算出来**，使用尾插法插入多项式`c`中，这样多项式`c`也是按照指数降序排列的。而减法就是将`a-b`改为`a+(-b)`。我们将`b`的每一项系数都取相反数，最后按照加法计算。

**图示过程：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 5]  
**c = a+b**  
将计算出来的`qc`节点使用尾插法插入多项式`c`中,然后再将`hc=qc`，`hc`指针后移一位，指向新插入的节点`qc`。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 6]

使用尾插法，`qc`是最后一个包含数据域的节点，因此`hc->next==NULL`。多项式`c`仍按照指数降序排列。

**代码**

int compare(Polyn a, Polyn b)//比较两个多项式每项的大小
    { 
    	if (a&&b)  // 多项式a和b均不为空
    	{ 
    		if (a->expn > b->expn) return 1; // a的指数大于b的指数，返回1
    		else if (a->expn < b->expn) return -1; //a的指数小于b的指数，返回-1
    		else return 0; //a的指数等于b的指数,返回0
    	}
    	else if (!a&&b) return -1; //a为空，b不为空
    	else if (a&&!b) return 1;  //b为空，a不为空 
    	else if (!a&&!b)return 0;  //a,b均为空
    }
    //一元稀疏多项式的加法和减法运算
    Polyn addPolyn(Polyn a, Polyn b)    
    	Polyn head ,qc;
    	Polyn qa = a->next;
    	Polyn qb = b->next;
    	Polyn hc=(Polyn)malloc(sizeof(Polynomial));  //新建节点 hc
    	hc->next = NULL;
    	head = hc;  //头结点head指向 hc
    	while (qa || qb)
    	{ 
    		qc= (Polyn)malloc(sizeof(Polynomial));  //用来存贮计算出来的多项式c的每一项
    		if (compare(qa, qb) == 1)     //多项式a的项的指数大于多项式b的项的指数
    		{ 
    			qc->coef = qa->coef;      //a的该项直接作为c的一项
    			qc->expn = qa->expn;
    			qa = qa->next;
    		}
    		else if (compare(qa, qb) == 0) //指数相同，两项相加作为c的一项
    		{ 
    			qc->coef = qa->coef + qb->coef;
    			qc->expn = qa->expn ; 
    			qa = qa->next;
    			qb = qb->next;
    		}
    		else     //多项式a的项的指数小于多项式b的项的指数 
    		{ 
    			qc->coef = qb->coef;  //b的该项直接作为c的一项
    			qc->expn = qb->expn;
    			qb = qb->next;
    		}
             
    		if (qc->coef != 0)  //将qc节点插入链表中
    		{ 
    			qc->next = hc->next;
    			hc->next = qc;
    			hc = qc;      //hc后移一位，指向新插入的节点qc
    		}
    		else free(qc);		
    	}
    	return head;
    }
    Polyn subPolyn(Polyn a, Polyn b)  //多项式减法运算
    { 
    	Polyn h = b;
    	Polyn p = b->next;
    	while(p)     //将b的每一项系数都取相反数
    	{ 
    		p->coef *= -1;  
    		p = p->next;
    	}
    	Polyn head = addPolyn(a, h);  //计算 a + (-b)
    	for (Polyn i = h->next; i != 0; i = i->next)  //最后再将b的每项系数还原
    	{  
    		i->coef *= -1;
    	}		
    	return  head;
    }

#### 3.一元稀疏多项式的打印和计算在x处的值 ####

**打印输出**

按照这种格式 `5x^8-3.1x^11+2x` 进行打印输出。从头到尾遍历多项式，特殊处理系数为`1`和`-1`。系数为`1`时，输出`'x'`,为`-1`时，输出`'-x'`,为其他时输出`x^,`或者 `-x^`。然后在`'x'`的后边将每项的指数格式输出。通过对系数和指数的情况分类讨论，正确输出`+`号和`-`号。具体思路见代码。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 7]

**代码**

void printPoLlyn(Polyn head)
    { 
    	Polyn q = head->next;
    	int flag = 0;     //记录是否为第一项
    	if (!q)
    	{ 
    		puts("NULL(0)\t");
    		return;
    	}
    	while (q)  //coef是系数，expn是指数
    	{ 
    		if (q->coef > 0 && flag == 1)  //系数为正，且不为第一项
    		{ 
    			printf("+"); //输出加号
    		}
    		flag = 1;
    		if (q->coef != 1 && q->coef != -1) //系数不为-1或者1
    		{ 
    			printf("%g", q->coef); //输出系数
    
    			if (q->expn == 1) printf("x");  //指数为1,输出x
    			else if (q->expn != 0) printf("x^%d", q->expn);
    		}
    		else
    		{ 
    			if (q->coef == 1)  //系数为1
    			{ 
    				if (q->expn == 0) printf("1");  //指数为0，按照常数1输出
    				else if (q->expn == 1) printf("x"); //指数为1,输出x
    				else printf("x^%d", q->expn);
    			}
    			if (q->coef == -1) //系数为-1
    			{ 
    				if (q->expn == 0) printf("-1");
    				else if (q->expn == 1) printf("-x");
    				else printf("-x^%d", q->expn);
    			}
    		}
    		q = q->next; //将q指针后移
    	}
    	printf("\t\t");
    }

**计算多项式在x的值**

遍历要计算的多项式的每一项，定义一个临时变量`tmp`。当该项的指数`expn`不为`0`时，如果为负数，我们进行`tmp /= x, expn++`。如果为正数，我们进行`tmp *= x, expn--`。重复上述操作，直到`expn==0`时停止。最后将每一项的值累加起来，记录到`sum`中，执行`sum += p->coef*tmp` 操作，便得到了多项式在`x`处的值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 8]

**代码**

double value(Polyn head, int x) //计算多项式在x处的值
    { 
    	double sum = 0;
    	for (Polyn p = head->next; p != 0; p = p->next) //遍历要计算的多项式
    	{ 
    		int tmp = 1;  //临时变量 tmp用来存贮计算 x^a 或者 x^-a
    		int expn = p->expn;
    		while(expn != 0)  //如果指数不为0，将一直执行下属操作
    		{ 
    			if (expn < 0)   tmp /= x, expn++;  //累乘运算
    			else if(expn>0) tmp *= x, expn--;  //累除运算
    		}
    		sum += p->coef*tmp;   //将每一项的值累加起来
    	}	
    	return sum;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/0adbee874aab45fbb51141afe54eaa6b.png
[Link 1]: https://blog.csdn.net/weixin_45629285/article/details/112484634
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/044bdf2d2fbc4bb0b8b2e9b7ad94f4fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/af448c66ac4d4563a0c589c2470f1696.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/8f66027076ed43ee8d76e34cb352c9af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]: /images/20210724/631e389e08e34e4aa307ceec95e0c29e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 5]: /images/20210724/3e5f6d6b140e448093e8ac9192274509.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 6]: /images/20210724/26fe1e1d24d649a086fface23bf6c8d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 7]: /images/20210724/3f5064169dd8430a9c49e97576f10991.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 8]: /images/20210724/400d5cc63e43480d9643a288e61e416b.png