线性表的应用多项式求和问题

实验综述

目的与要求

实现多项式的建立、相加操作、要求利用原有空间求其和多项式，并且按指数从小到大顺序排列输出这两个多项式及其和多项式，其输出形式为多项式的系数指数

软件与运行环境

系统环境

1
Darwin jhsymac.local 20.6.0 Darwin Kernel Version 20.6.0: Mon Aug 29 04:31:12 PDT 2022; root:xnu-7195.141.39~2/RELEASE_ARM64_T8101 arm64

编辑器

1
2
3
4
5
VIM - Vi IMproved 9.0 (2022 Jun 28, compiled Aug 29 2022 04:57:59)
macOS version - arm64
Included patches: 1-217
Compiled by root@apple.com
Normal version without GUI.

编译器

1
2
3
4
gcc-12 (Homebrew GCC 12.2.0) 12.2.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

内容与原理

  • 链表的相关操作
  • 链表的创建
  • 链表的排序
  • 链表的修改

实验过程

问题分析

代码主要实现的功能

  • 多项式存储
  • 多项式排序
  • 多项式相加（不改动原数据相加）
  • 多项式合并
  • 多项式输出

多项式存储问题

多项式每一项相连，可以使用链式存储的结构储存多项式

我们定义一个结构体用来存放指数和系数

分别用int类型的变量存储系数和指数

1
2
3
4
5
6
7
struct polynominal{
	int coef;
	int exp;
	struct polynominal *next;
};

typedef struct polynominal poly;

多项式创建

初始化一个链表，并将用户输入的数据存储至对应的成员变量

题目要求当输出的系数为0时，结束数据输入

while循环条件结束标志ic=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
poly * CreatePoly()
{
	poly *head,*p,*rear;
	head=(poly *)malloc(sizeof(poly));
	rear=head;
	head->next=NULL;
	int ie,ic;
	scanf("%d,%d",&ic,&ie);
	while(ic!=0){
		p=(poly *)malloc(sizeof(poly));
		p->exp=ie;
		p->coef=ic;
		p->next=NULL;
		rear->next=p;
		rear=rear->next;
		scanf("%d,%d",&ic,&ie);
}
	return head;
}

多项式排序

要排序链表，首先要获取链表长度，用一个循环遍历整个链表并使用length变量累计链表长度

从头节点开始分别比对后面数据大小，从大到小排序。

使用冒泡排序，若当前节点大于后一节点，则交换两节点位置

交换链表的几点需要知道三个节点的内存地址

交换两个结点的前一个地址和两个被交换地址

分别为 pi q p

交换qp的位置只需要更改三个节点的连接顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
poly * SortPoly(poly * const head){
	int length=0;
	poly *p,*q,*o,*pi;
	p=head->next;
	while(p){
		length++;	
		p=p->next;
	}
	o=head;
	for(int i=0;i<length-1;i++){
		pi=o;
		for(int j=0;j<length-1-i;j++){
			q=pi->next;
			p=q->next;
			if(q->exp>p->exp){
				q->next=p->next;
				p->next=q;
				pi->next=p;
			}
			pi=pi->next;
		}
	}
	return head;

}

多项式输出

要输出一个多项式，本质是一个链表数据的输出，从头结点开始遍历至尾节点，输出每一项

多项式首项不需要带符号，以后的每一项都需要用+号连接起来，我们只需要特殊处理第一项，并判断多项式的项数是否大于1

函数本质是一个过程，不需要回传参数，类型可以根据实际情况修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int PrintPoly(poly * const head){
	poly *p;
	p=head->next;
	int length=0;
	p=p->next;
	while(p){
		length++;
		p=p->next;
	}
	p=head;
	p=p->next;
		printf("%dx^%d",p->coef,p->exp);
		p=p->next;
	if(length>1){
			while(p){
				printf("+%dx^%d",p->coef,p->exp);
				p=p->next;
			}
	}
	return 1;
}

多项式相加

题目要求本质是原地算法，但是为了不破坏代码原始数据，我们创建一个新的链表用来储存相加结果

分别定义两个当前指针p1_current和p2_current分别指向两个相加的链表

对比当前节点指数大小，分情况讨论

  • P1_current == p2_ current :两系数相加并添加至新节点末尾,p1 p2分别向后移动
  • P1_current > p2_ current ：将p2添加至新节点末尾，p2向后移动
  • P1_current < p2_ current ：将p1添加至新节点末尾，p1向后移动

当任意一个链表p_current指向末尾没有数据后，直接将另一个链表剩余所有数据添加至新链表结尾。

最后返回头指针保存结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//		多项式相加，并创建新的链表保存数据
poly * AddPoly(poly * const p1,poly * const p2){

	poly *new=(poly *)malloc(sizeof(poly));
	poly *rear=new;
	new->next=NULL;
	poly *p1_current,*p2_current;
	p1_current=p1->next;
	p2_current=p2->next;
	poly *innew;

	while(p1_current&&p2_current){

		if(p1_current->exp == p2_current->exp){
				if(p1_current->coef + p2_current->coef != 0){
					innew=(poly *)malloc(sizeof(poly));
					innew->coef=p1_current->coef+p2_current->coef;
					innew->exp=p1_current->exp;
					p1_current=p1_current->next;
					p2_current=p2_current->next;
					innew->next=NULL;
					rear->next=innew;
					rear=innew;
				}
				else
				{
					p1_current=p1_current->next;
					p2_current=p2_current->next;
				}
		}	

		else if(p1_current->exp > p2_current->exp){
			innew=(poly *)malloc(sizeof(poly));
			innew->coef=p2_current->coef;
			innew->exp=p2_current->exp;
			p2_current=p2_current->next;
			innew->next=NULL;
			rear->next=innew;
			rear=innew;	
		}
		
		else if(p1_current->exp < p2_current->exp){
			innew=(poly *)malloc(sizeof(poly));
			innew->coef=p1_current->coef;
			innew->exp=p1_current->exp;
			p1_current=p1_current->next;
			innew->next=NULL;
			rear->next=innew;
			rear=innew;	
		}
	}

	if(p1_current==NULL&&p2_current!=NULL){
		while(p2_current){
			innew=(poly *)malloc(sizeof(poly));
			innew->coef=p2_current->coef;
			innew->exp=p2_current->exp;
			p2_current=p2_current->next;
			innew->next=NULL;
			rear->next=innew;
			rear=innew;	
		}
	}
	
	if(p2_current==NULL&&p1_current!=NULL){
		while (p1_current) {
			innew=(poly *)malloc(sizeof(poly));
			innew->coef=p1_current->coef;
			innew->exp=p1_current->exp;
			p1_current=p1_current->next;
			innew->next=NULL;
			rear->next=innew;
			rear=innew;	
		}
	}

	return new;
}

多项式合并

多项式原地合并，不启用额外的内存空间

我们利用原有数据，只改变链表的连接顺序，而不创建新的空间。头指正的返回值等于传入参数第一个链表的头指正地址。

定义一个指尾指针变量存储第一个链表的头指正地址，将之后所有的节点链接至此

两个链表分别指向第一个节点。

释放第二个链表的头结点。

  • 如果两个链表节点相等，则相加至第一个链表的节点，分别向后移动，并释放p2内存空间
  • 分别对比两个链表的节点指数大小，将较小者使用尾插法插入至尾指针后。

遍历至尾指针后，将剩余节点添加到尾指针末尾结束算法

返回p1头指针地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

// 原地算法，多项式相加并合并为一个链表
poly *PolyConverge(poly *p1,poly *p2){

	poly *head,*rear,*temp;
	head=p1;
	rear=head;
	temp=p2;
	p2=p2->next;
	p1=p1->next;
	free(temp);
	rear->next=NULL;
	
	while(p1&&p2){

			
		if(p1->exp == p2->exp){
				if(p1->coef + p2->coef !=0){
					p1->coef = p1->coef+p2->coef;
					rear->next=p1;
					p1=p1->next;
					temp=p2;
					p2=p2->next;
					free(temp);
					rear=rear->next;
					rear->next=NULL;	
				}
				else
				{
					temp=p1;
					p1=p1->next;
					free(temp);
					temp=p2;
					p2=p2->next;
					free(temp);
				}
		}

		
		else if(p1->exp < p2->exp){
			rear->next=p1;
			p1=p1->next;
			rear=rear->next;
			rear->next=NULL;
		}

		else if(p1->exp > p2->exp){
			rear->next=p2;
			p2=p2->next;
			rear=rear->next;
			rear->next=NULL;
		}
	}
	
	if(p2){
		rear->next=p2;
	}

	if(p1){
		rear->next=p1;
	}

	return head;
}

编写主函数

  1. 声明头指针
  2. 初始化链表并链接头指针
  3. 链表排序
  4. 两个链表相加生成新的结果
  5. 输出最后结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(){
	poly *p1,*p2,*sum;
	printf("分别输入第一个多项式的系数和指数（系数，指数）\n");
	p1=CreatePoly();
	SortPoly(p1);
	printf("分别输入第一个多项式的系数和指数（系数，指数）\n");
	p2=CreatePoly();
	SortPoly(p2);
	sum=AddPoly(p1,p2);
	printf("\nsum:\n");
	PrintPoly(sum);
	printf("\nsum:\n");
	sum=PolyConverge(p1,p2);
	PrintPoly(sum);
	return 0;
}

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
分别输入第一个多项式的系数和指数（系数，指数）
4,4
7,7
2,2
9,9
4,4
6,6
0,0
分别输入第一个多项式的系数和指数（系数，指数）
1,1
5,5
9,9
5,5
4,4
8,8
3,3
0,0

sum:
1x^1+2x^2+3x^3+8x^4+4x^4+5x^5+5x^5+6x^6+7x^7+8x^8+18x^9
sum:
1x^1+2x^2+3x^3+8x^4+4x^4+5x^5+5x^5+6x^6+7x^7+8x^8+18x^9

过程中踩坑

  • GCC和LLVM机制的差异，不同编译器对指针检查机制不同
  • 不熟悉GDB操作，指针越界检查消耗时间成本太大
  • 对于编译器相关知识不太熟悉，未来需要补充编译相关内容

程序改进

输入

固定输入方式太过死板，若用户输入数据不正确无法正确处理数据的存储。

我们可以让用户按写法输入多项式，通过字符串解析的方式自动处理数据写入内存。若用户输入为 23x^2+76x^2+98x^2 程序应能够自动读取到指数和系数并相应存储。

操作

多项式的操作过于单一，多项式包含加减乘除四则运算。操作函数体的内部代码过于重复，我们可以使用面向对象编程的思想去考虑多项式的操作问题，定义一个多项式类，定义相关操作。用C++重构代码，下次实验编写一个计算器程序时，可以拓展到计算多项式结果。