数据结构--链表实现多项式求和

朴灿烈づ我的快乐病毒、 2023-10-01 04:31 62阅读 0赞

## 数据结构–用链表来实现多项式求和 ##

##### 首先，为什么不用顺序表来实现呢？ #####

*  如果用顺序表的话，可以创建一个数组，然后用index来表示多项式的指数，这样同样可以实现一个多项式的求和，而且更加简单了。
 *  但是：如果碰到一个2X^3000 + 1 和 3X^3000 + 5 那且不是要使用3001个数组的大小来存储多项式，但是却只用到了两个数组的值，其他的空间都浪费了。
 *  所以使用链表来实现是很有必要的

`**其实画图的话更容易理解，下次一定**`

> 贴上代码：

'//一个节点：数据包含一个系数和一个指数，也包含一个指向下一个node节点的指针'
    struct PolyNode {
        
    	int coef;
    	int expon;
    	struct PolyNode* link;
    };
    typedef struct PolyNode* Polynomial;
    Polynomial P1, P2;
    
    '//一个实现往节点后面添加node的函数'
    void Attach(int c, int e, Polynomial* pRear)
    {
        
    	Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));
    	P->coef = c;
    	P->expon = e;
    	P->link = NULL;
    	(*pRear)->link = P;		'  //rear的link指针指向P  '
    	*pRear = P;				'  //rear指针指向P  '
    }
    '//一个函数比较系数的大小  '
    int compare(int a, int b)
    {
        
    	if (a > b) return 1;
    	else if (a = b) return 0;
    	else return -1;
    }
    '//实现多项式相加  '
    Polynomial PolyAdd(Polynomial P1, Polynomial P2)
    {
        
    	Polynomial front, rear, temp;
    	int sum = 0;
    	rear = (Polynomial)malloc(sizeof(struct PolyNode));
    	front = rear;
    	'//当P1或者P2不为空，比较指数的大小，指数大的加入结果多项式中，同时指针向后移动。相等时系数相加，如果不为0就加入到结果里  '
    	while (P1 && P2)
    	{
        
    		switch (Compare(P1->expon, P2->expon)) {
        
    		case 1:
    			Attach(P1->coef, P1->expon, &rear);
    			P1 = P1->link;
    			break;
    		case -1:
    			Attach(P2->coef, P2->expon, &rear);
    			P2 = P2->link;
    			break;
    		case 0:
    			sum = P1->coef + P2->coef;
    			if (sum) Attach(sum, P1->expon, &rear);
    			P1 = P1->link;
    			P2 = P2->link;
    			break;
    		}
    		'//当P1，P2有一个为NULL时，将剩下的一个不为NULL的指针指向的剩余node添加到结果多项式中  '
    		for (; P1; P1 = P1->link) Attach(P1->coef, P1->expon, &rear);
    		for (; P2; P2 = P2->link) Attach(P2->coef, P2->expon, &rear);
    		rear->link = NULL;
    		temp = front;
    		front = front->link;
    		free(temp);
    		return front;
    	}