一.代码展示

1.创建结构体

//创建结构体 
typedef struct LinkNode{
	int coefficient;
	int index;
	struct LinkNode *next;
}*NodePtr,*LinkList;

2.初始化链表

//初始化链表 
LinkList initLinkList(){
	NodePtr tempHeader=(NodePtr)malloc(sizeof(NodePtr));
	tempHeader->coefficient=0;
	tempHeader->index=0; 
	tempHeader->next=NULL;

	return tempHeader; 
}

3.打印多项式

//打印多项式 
void  printList(NodePtr paraHeader){
	NodePtr p=paraHeader->next;
	while(p->next!=NULL){
		printf("%d * 10 ^ %d + ",p->coefficient,p->index);
		p=p->next;
	}
	
	printf("%d * 10 ^ %drn ",p->coefficient,p->index);
}

4.添加结点

//尾插法添加结点
void appendElement(NodePtr paraHeader,int paraCoefficient,int paraIndex){
	NodePtr p,q;
	
	//1.初始化要插入的结点 
	q=(NodePtr)malloc(sizeof(NodePtr));
	q->coefficient=paraCoefficient;
	q->index=paraIndex;
	q->next=NULL;
	
	//2.遍历链表
	p=paraHeader;
	while(p->next!=NULL) {
		p=p->next;
	}
	
	//3.插入结点
	 p->next=q;
	 q=NULL; 
}

5.多项式相加

这是流程图

这里情况较多，比较复杂，但是弄清整个流程就很轻松了。

//多项式相加（链表相加）
void add(LinkList paraHeader1,LinkList paraHeader2) {
	NodePtr p,q,r,deletePtr;
	
	p=paraHeader1->next;
	q=paraHeader2->next;
	r=paraHeader1;
	free(paraHeader2); 
	
    //四种可能性
	while(p!=NULL&&q!=NULL){
		if(p->index>q->index){
			r->next=q;
			q=q->next;
			r->next->next=p;
            r=r->next; 
		} else if(p->indexindex){
			r=p;
			p=p->next;
		}else if(p->index==q->index){
			p->coefficient=p->coefficient+q->coefficient;
			if(!p->coefficient){
				deletePtr=q;
				q=q->next;
				free(deletePtr);
				
				deletePtr=p;
				p=p->next;
				r->next=p;
				free(deletePtr);
			}else{
				r=p;
				p=p->next;
				q=q->next;
			}	
		}
	}
	
	if(p==NULL)
	{
			r->next=q;
	}
}

6.完整代码

#include 
#include 

//创建结构体 
typedef struct LinkNode{
	int coefficient;
	int index;
	struct LinkNode *next;
}*NodePtr,*LinkList;

//初始化链表 
LinkList initLinkList(){
	NodePtr tempHeader=(NodePtr)malloc(sizeof(NodePtr));
	tempHeader->coefficient=0;
	tempHeader->index=0; 
	tempHeader->next=NULL;

	return tempHeader; 
} 

//打印多项式 
void  printList(NodePtr paraHeader){
	NodePtr p=paraHeader->next;
	while(p->next!=NULL){
		printf("%d * 10 ^ %d + ",p->coefficient,p->index);
		p=p->next;
	}
	
	printf("%d * 10 ^ %drn ",p->coefficient,p->index);
}

//尾插法添加结点
void appendElement(NodePtr paraHeader,int paraCoefficient,int paraIndex){
	NodePtr p,q;
	
	//1.初始化要插入的结点 
	q=(NodePtr)malloc(sizeof(NodePtr));
	q->coefficient=paraCoefficient;
	q->index=paraIndex;
	q->next=NULL;
	
	//2.遍历链表
	p=paraHeader;
	while(p->next!=NULL) {
		p=p->next;
	}
	
	//3.插入结点
	 p->next=q;
	 q=NULL; 
}

//多项式相加（链表相加）
void add(LinkList paraHeader1,LinkList paraHeader2) {
	NodePtr p,q,r,deletePtr;
	
	p=paraHeader1->next;
	q=paraHeader2->next;
	r=paraHeader1;
	free(paraHeader2); 
	
	while(p!=NULL&&q!=NULL){
		if(p->index>q->index){
			r->next=q;
			q=q->next;
			r->next->next=p; 
		} else if(p->indexindex){
			r=p;
			p=p->next;
		}else if(p->index==q->index){
			p->coefficient=p->coefficient+q->coefficient;
			if(!p->coefficient){
				deletePtr=q;
				q=q->next;
				free(deletePtr);
				
				deletePtr=p;
				p=p->next;
				r->next=p;
				free(deletePtr);
			}else{
				r=p;
				p=p->next;
				q=q->next;
			}	
		}
	}
	
	if(p==NULL)
	{
			r->next=q;
	}
}

void additionTest(){
	//添加第一个多项式 
	LinkList tempList1 = initLinkList();
	appendElement(tempList1, 7, 0);
	appendElement(tempList1, 3, 1);
	appendElement(tempList1, 3, 2);
	appendElement(tempList1, 9, 8);
	appendElement(tempList1, 5, 17);
	printList(tempList1);

	//添加第二个多项式 
	LinkList tempList2 = initLinkList();
	appendElement(tempList2, 8, 1);
	appendElement(tempList2, 22, 7);
	appendElement(tempList2, -9, 8);
	printList(tempList2);

	//多项式相加 
	add(tempList1, tempList2);
	printList(tempList1);
}

int main(){
	additionTest();
	printf("Finish.rn");
}

7.测试结果

7 * 10 ^ 0 + 3 * 10 ^ 1 + 3 * 10 ^ 2 + 9 * 10 ^ 8 + 5 * 10 ^ 17
 8 * 10 ^ 1 + 22 * 10 ^ 7 + -9 * 10 ^ 8
 7 * 10 ^ 0 + 11 * 10 ^ 1 + 3 * 10 ^ 2 + 5 * 10 ^ 17
 Finish.

二.总结

1.多项式相加时应该考虑全面，将所有可能性不遗漏，人力有穷尽，遇见复杂情况可以借助流程图来帮助自己梳理思路。

2.多项式求和算是对链表学习的一次应用和

#include 
#include 


typedef struct LinkNode{
	int coefficient;
	int exponent;
	struct LinkNode *next;
} *LinkList, *NodePtr;


LinkList initLinkList(){
	LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode));
	tempHeader->coefficient = 0;
	tempHeader->exponent = 0;
	tempHeader->next = NULL;
	return tempHeader;
}


void printList(LinkList paraHeader){
	NodePtr p = paraHeader->next;
	while (p != NULL) {
		printf("%d * 10^%d + ", p->coefficient, p->exponent);
		p = p->next;
	}// Of while
	printf("rn");
}


void printNode(NodePtr paraPtr, char paraChar){
	if (paraPtr == NULL) {
		printf("NULLrn");
	} else {
		printf("The element of %c is (%d * 10^%d)rn", paraChar, paraPtr->coefficient, paraPtr->exponent);
	}// Of while
}


void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent){
	NodePtr p, q;

	// Step 1. Construct a new node.
	q = (NodePtr)malloc(sizeof(struct LinkNode));
	q->coefficient = paraCoefficient;
	q->exponent = paraExponent;
	q->next = NULL;

	// Step 2. Search to the tail.
	p = paraHeader;
	while (p->next != NULL) {
		p = p->next;
	}

	// Step 3. Now add/link.
	p->next = q;
}


void add(NodePtr paraList1, NodePtr paraList2){
	NodePtr p, q, r, s;

	// Step 1. Search to the position.
	p = paraList1->next;
	printNode(p, 'p');
	q = paraList2->next;
	printNode(q, 'q');
	r = paraList1; // Previous pointer for inserting.
	printNode(r, 'r');
	free(paraList2); // The second list is destroyed. 
	
	while ((p != NULL) && (q != NULL)) {
		if (p->exponent < q->exponent) {
			//Link the current node of the first list.
			printf("case 1rn");
			r = p;
			printNode(r, 'r');
			p = p->next;
			printNode(p, 'p');
		} else if ((p->exponent > q->exponent)) {
			//Link the current node of the second list.
			printf("case 2rn");
			r->next = q;
			r = q;
			printNode(r, 'r');
			q = q->next;
			printNode(q, 'q');
		} else {
			printf("case 3rn");
			//Change the current node of the first list.
			p->coefficient = p->coefficient + q->coefficient;
			printf("The coefficient is: %d.rn", p->coefficient);
			if (p->coefficient == 0) {
				printf("case 3.1rn");
				s = p;
				p = p->next;
				printNode(p, 'p');
			} else {
				printf("case 3.2rn");
				r = p;
				printNode(r, 'r');
				p = p->next;
				printNode(p, 'p');
			}
			s = q;
			q = q->next;
			//printf("q is pointing to (%d, %d)rn", q->coefficient, q->exponent);
			free(s);
		}

		printf("p = %ld, q = %ld rn", p, q);
	} 
	printf("End of while.rn");

	if (p == NULL) {
		r->next = q;
	} else {
		r->next = p;
	} 

	printf("Addition ends.rn");
}


void additionTest(){
	// Step 1. Initialize the first polynomial.
	LinkList tempList1 = initLinkList();
	appendElement(tempList1, 7, 0);
	appendElement(tempList1, 3, 1);
	appendElement(tempList1, 9, 8);
	appendElement(tempList1, 5, 17);
	printList(tempList1);

	// Step 2. Initialize the second polynomial.
	LinkList tempList2 = initLinkList();
	appendElement(tempList2, 8, 1);
	appendElement(tempList2, 22, 7);
	appendElement(tempList2, -9, 8);
	printList(tempList2);

	// Step 3. Add them to the first.
	add(tempList1, tempList2);
	printList(tempList1);
}


void main(){
	additionTest();
	printf("Finish.rn");
}

三.附上老师代码

#include 
#include 


typedef struct LinkNode{
	int coefficient;
	int exponent;
	struct LinkNode *next;
} *LinkList, *NodePtr;


LinkList initLinkList(){
	LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode));
	tempHeader->coefficient = 0;
	tempHeader->exponent = 0;
	tempHeader->next = NULL;
	return tempHeader;
}


void printList(LinkList paraHeader){
	NodePtr p = paraHeader->next;
	while (p != NULL) {
		printf("%d * 10^%d + ", p->coefficient, p->exponent);
		p = p->next;
	}// Of while
	printf("rn");
}


void printNode(NodePtr paraPtr, char paraChar){
	if (paraPtr == NULL) {
		printf("NULLrn");
	} else {
		printf("The element of %c is (%d * 10^%d)rn", paraChar, paraPtr->coefficient, paraPtr->exponent);
	}
}


void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent){
	NodePtr p, q;

	// Step 1. Construct a new node.
	q = (NodePtr)malloc(sizeof(struct LinkNode));
	q->coefficient = paraCoefficient;
	q->exponent = paraExponent;
	q->next = NULL;

	// Step 2. Search to the tail.
	p = paraHeader;
	while (p->next != NULL) {
		p = p->next;
	}// Of while

	// Step 3. Now add/link.
	p->next = q;
}


void add(NodePtr paraList1, NodePtr paraList2){
	NodePtr p, q, r, s;

	// Step 1. Search to the position.
	p = paraList1->next;
	printNode(p, 'p');
	q = paraList2->next;
	printNode(q, 'q');
	r = paraList1; // Previous pointer for inserting.
	printNode(r, 'r');
	free(paraList2); // The second list is destroyed. 
	
	while ((p != NULL) && (q != NULL)) {
		if (p->exponent < q->exponent) {
			//Link the current node of the first list.
			printf("case 1rn");
			r = p;
			printNode(r, 'r');
			p = p->next;
			printNode(p, 'p');
		} else if ((p->exponent > q->exponent)) {
			//Link the current node of the second list.
			printf("case 2rn");
			r->next = q;
			r = q;
			printNode(r, 'r');
			q = q->next;
			printNode(q, 'q');
		} else {
			printf("case 3rn");
			//Change the current node of the first list.
			p->coefficient = p->coefficient + q->coefficient;
			printf("The coefficient is: %d.rn", p->coefficient);
			if (p->coefficient == 0) {
				printf("case 3.1rn");
				s = p;
				p = p->next;
				printNode(p, 'p');
			} else {
				printf("case 3.2rn");
				r = p;
				printNode(r, 'r');
				p = p->next;
				printNode(p, 'p');
			}// Of if
			s = q;
			q = q->next;
			//printf("q is pointing to (%d, %d)rn", q->coefficient, q->exponent);
			free(s);
		}

		printf("p = %ld, q = %ld rn", p, q);
	} 
	printf("End of while.rn");

	if (p == NULL) {
		r->next = q;
	} else {
		r->next = p;
	} 

	printf("Addition ends.rn");
}


void additionTest(){
	// Step 1. Initialize the first polynomial.
	LinkList tempList1 = initLinkList();
	appendElement(tempList1, 7, 0);
	appendElement(tempList1, 3, 1);
	appendElement(tempList1, 9, 8);
	appendElement(tempList1, 5, 17);
	printList(tempList1);

	// Step 2. Initialize the second polynomial.
	LinkList tempList2 = initLinkList();
	appendElement(tempList2, 8, 1);
	appendElement(tempList2, 22, 7);
	appendElement(tempList2, -9, 8);
	printList(tempList2);

	// Step 3. Add them to the first.
	add(tempList1, tempList2);
	printList(tempList1);
}


void main(){
	additionTest();
	printf("Finish.rn");
}

数据结构多项式求和

一.代码展示

1.创建结构体
//创建结构体 typedef struct LinkNode{ int coefficient; int index; struct LinkNode next; }NodePtr,*LinkList;

2.初始化链表
//初始化链表 LinkList initLinkList(){ NodePtr tempHeader=(NodePtr)malloc(sizeof(NodePtr)); tempHeader->coefficient=0; tempHeader->index=0; tempHeader->next=NULL; return tempHeader; }

3.打印多项式
//打印多项式 void printList(NodePtr paraHeader){ NodePtr p=paraHeader->next; while(p->next!=NULL){ printf("%d * 10 ^ %d + ",p->coefficient,p->index); p=p->next; } printf("%d * 10 ^ %drn ",p->coefficient,p->index); }

7.测试结果
7 * 10 ^ 0 + 3 * 10 ^ 1 + 3 * 10 ^ 2 + 9 * 10 ^ 8 + 5 * 10 ^ 17 8 * 10 ^ 1 + 22 * 10 ^ 7 + -9 * 10 ^ 8 7 * 10 ^ 0 + 11 * 10 ^ 1 + 3 * 10 ^ 2 + 5 * 10 ^ 17 Finish.

C/C++/C#相关栏目本月热门文章

数据结构多项式求和

一.代码展示

1.创建结构体 //创建结构体 typedef struct LinkNode{ int coefficient; int index; struct LinkNode *next; }*NodePtr,*LinkList;

2.初始化链表 //初始化链表 LinkList initLinkList(){ NodePtr tempHeader=(NodePtr)malloc(sizeof(NodePtr)); tempHeader->coefficient=0; tempHeader->index=0; tempHeader->next=NULL; return tempHeader; }

3.打印多项式 //打印多项式 void printList(NodePtr paraHeader){ NodePtr p=paraHeader->next; while(p->next!=NULL){ printf("%d * 10 ^ %d + ",p->coefficient,p->index); p=p->next; } printf("%d * 10 ^ %drn ",p->coefficient,p->index); }

7.测试结果 7 * 10 ^ 0 + 3 * 10 ^ 1 + 3 * 10 ^ 2 + 9 * 10 ^ 8 + 5 * 10 ^ 17 8 * 10 ^ 1 + 22 * 10 ^ 7 + -9 * 10 ^ 8 7 * 10 ^ 0 + 11 * 10 ^ 1 + 3 * 10 ^ 2 + 5 * 10 ^ 17 Finish.

C/C++/C#相关栏目本月热门文章

1.创建结构体
//创建结构体 typedef struct LinkNode{ int coefficient; int index; struct LinkNode next; }NodePtr,*LinkList;

2.初始化链表
//初始化链表 LinkList initLinkList(){ NodePtr tempHeader=(NodePtr)malloc(sizeof(NodePtr)); tempHeader->coefficient=0; tempHeader->index=0; tempHeader->next=NULL; return tempHeader; }

3.打印多项式
//打印多项式 void printList(NodePtr paraHeader){ NodePtr p=paraHeader->next; while(p->next!=NULL){ printf("%d * 10 ^ %d + ",p->coefficient,p->index); p=p->next; } printf("%d * 10 ^ %drn ",p->coefficient,p->index); }

7.测试结果
7 * 10 ^ 0 + 3 * 10 ^ 1 + 3 * 10 ^ 2 + 9 * 10 ^ 8 + 5 * 10 ^ 17 8 * 10 ^ 1 + 22 * 10 ^ 7 + -9 * 10 ^ 8 7 * 10 ^ 0 + 11 * 10 ^ 1 + 3 * 10 ^ 2 + 5 * 10 ^ 17 Finish.