多项式的加法为对单链表的进一步利用与延伸，此代码的核心部分在于怎么按顺序把两个多项式合并同类项相加。
老师原代码的多项式相加的衔接处有些小问题，类似于没有r-> = p;的衔接，便做了些修改。
一、代码功能:1、链表的定义
2、初始化链表
3、打印链表
4、打印节点
5、链表加入值
6、链表的多项式相加
7、测试代码1
8、测试代码2
9、程序入口
二、多项式加法的代码：1、链表的定义
typedef struct LinkNode
{
int coefficient;
int exponent;
struct LinkNode *next;
} *LinkList, *NodePtr;
2、初始化链表
LinkList initLinkList()
{
LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode));
tempHeader->coefficient = 0;
tempHeader->exponent = 0;
tempHeader->next = NULL;
return tempHeader;
}
3、打印链表
void printList(LinkList paraHeader)
{
NodePtr p = paraHeader->next;
while (p != NULL)
{
printf("%d * 10^%d + ", p->coefficient,p->exponent);
p = p->next;
}
printf("rn");
}
4、打印节点
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);
}
}
5、链表加入值
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;
}
6、链表的多项式相加
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->next = p;
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');
// free(s);
} else
{
printf("case 3.2rn");
r->next = p;
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);
}// Of if
printf("p = %ld, q = %ld rn", p, q);
} // Of while
printf("End of while.rn");
if (p == NULL)
{
r->next = q;
} else
{
r->next = p;
} // Of if
printf("Addition ends.rn");
}
7、测试代码1
void additionTest1()
{
// 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);
printf("The result is: ");
printList(tempList1);
printf("rn");
}
8、测试代码2
void additionTest2()
{
// 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, 10);
printList(tempList2);
// Step 3. Add them to the first.
add(tempList1, tempList2);
printf("The result is: ");
printList(tempList1);
printf("rn");
}
9、程序入口
int main()
{
additionTest1();
additionTest2();
printf("Finish.rn");
return 0;
}
10、运行结果
7 * 10^0 + 3 * 10^1 + 9 * 10^8 + 5 * 10^17 + 8 * 10^1 + 22 * 10^7 + -9 * 10^8 + The element of p is (7 * 10^0) The element of q is (8 * 10^1) The element of r is (0 * 10^0) case 1 The element of r is (7 * 10^0) The element of p is (3 * 10^1) p = 1709104, q = 1709232 case 3 The coefficient is: 11. case 3.2 The element of r is (11 * 10^1) The element of p is (9 * 10^8) p = 1709136, q = 1709264 case 2 The element of r is (22 * 10^7) The element of q is (-9 * 10^8) p = 1709136, q = 1709296 case 3 The coefficient is: 0. case 3.1 The element of p is (5 * 10^17) p = 1709168, q = 0 End of while. Addition ends. The result is: 7 * 10^0 + 11 * 10^1 + 22 * 10^7 + 5 * 10^17 + 7 * 10^0 + 3 * 10^1 + 9 * 10^8 + 5 * 10^17 + 8 * 10^1 + 22 * 10^7 + -9 * 10^10 + The element of p is (7 * 10^0) The element of q is (8 * 10^1) The element of r is (0 * 10^0) case 1 The element of r is (7 * 10^0) The element of p is (3 * 10^1) p = 1709296, q = 1709424 case 3 The coefficient is: 11. case 3.2 The element of r is (11 * 10^1) The element of p is (9 * 10^8) p = 1709328, q = 1709456 case 2 The element of r is (22 * 10^7) The element of q is (-9 * 10^10) p = 1709328, q = 1709488 case 1 The element of r is (9 * 10^8) The element of p is (5 * 10^17) p = 1709360, q = 1709488 case 2 The element of r is (-9 * 10^10) NULL p = 1709360, q = 0 End of while. Addition ends. The result is: 7 * 10^0 + 11 * 10^1 + 22 * 10^7 + 9 * 10^8 + -9 * 10^10 + 5 * 10^17 + Finish.三、整体代码：
#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; } 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->next = p; 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'); // free(s); } else { printf("case 3.2rn"); r->next = p; 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); }// Of if printf("p = %ld, q = %ld rn", p, q); } // Of while printf("End of while.rn"); if (p == NULL) { r->next = q; } else { r->next = p; } // Of if printf("Addition ends.rn"); } void additionTest1() { // 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); printf("The result is: "); printList(tempList1); printf("rn"); }// Of additionTest1 void additionTest2() { // 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, 10); printList(tempList2); // Step 3. Add them to the first. add(tempList1, tempList2); printf("The result is: "); printList(tempList1); printf("rn"); }// Of additionTest2 int main() { additionTest1(); additionTest2(); printf("Finish.rn"); return 0; }
如有错误还请评论区指出，必将认真采纳并修正。
