多项式加法的C语言实现

2018/01/30 数据结构

链表的三个主要例子之一,多项式加法

#include <stdio.h>
#include <stdlib.h>

typedef struct Node *PtrToNode;

struct Node {
	int Coefficient;	// 系数
	int Exponent;		// 指数
	PtrToNode Next;
};

typedef PtrToNode Polynomial;		// 多项式

PtrToNode CreatPoly();
void Insert(int Coefficient, int Exponent, Polynomial Poly);
Polynomial AddPoly(Polynomial Polya, Polynomial Polyb);

Polynomial CreatPoly() {
	PtrToNode head = (PtrToNode)malloc(sizeof(struct Node));
	head->Next = NULL;
	int Coefficient, Exponent;
	// 输入为系数指数,以-1结束
	while(~scanf("%d", &Coefficient) && Coefficient != -1) {
		scanf("%d", &Exponent);
		Insert(Coefficient, Exponent, head);
	}
	return head;
}

Polynomial AddPoly(Polynomial Polya, Polynomial Polyb) {
	PtrToNode head = (PtrToNode)malloc(sizeof(struct Node));
	head->Next = NULL;
	int Coefficient, Exponent;
	PtrToNode p;
	p = Polya->Next;
	while (p != NULL) {
		Insert(p->Coefficient, p->Exponent, head);
		p = p->Next;
	}
	p = Polyb->Next;
	while (p != NULL) {
		Insert(p->Coefficient, p->Exponent, head);
		p = p->Next;
	}
	return head;
}

void Insert(int Coefficient, int Exponent, Polynomial Poly) {
	PtrToNode p;
	p = Poly;
	
	// 注意判断是不是空链表,即第一个插入的元素
	while (p->Next != NULL && p->Next->Exponent > Exponent) {
		p = p->Next;
	}
	
	if(p->Next != NULL && p->Next->Exponent == Exponent) {
		p->Next->Coefficient += Coefficient;
	}
	else {
		PtrToNode node = (PtrToNode)malloc(sizeof(struct Node));
		node->Coefficient = Coefficient;
		node->Exponent = Exponent;
		node->Next = p->Next;
		p->Next = node;
	}
}

void PrintPoly(Polynomial Poly) {
	PtrToNode p;
	p = Poly->Next;
	while (p != NULL) {
		printf("%dx^%d", p->Coefficient, p->Exponent);
		if(p->Next != NULL) 
			printf(" + ");
		p = p->Next;
	}
	printf("\n");
}

int main() {
	Polynomial polya = CreatPoly();
	PrintPoly(polya);
	Polynomial polyb = CreatPoly();
	PrintPoly(polyb);
	Polynomial polyc = AddPoly(polya, polyb);
	PrintPoly(polyc);
	return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Search

    Table of Contents