目录
功能介绍：
图解：
闵版代码
代码更改：
功能介绍：
将俩个一元多项式相加， 好了就这些。
图解：
1）.
2）.
3).
闵版代码
#include
#include
typedef struct LinkNode{
int cofficient;
int exponent;
struct LinkNode *next;
} *LinkList, *NodePtr;
LinkList initLinkList(){
LinkList tempHeader = (LinkList)malloc(sizeof(struct LinkNode));
tempHeader->cofficient = 0;
tempHeader->exponent = 0;
tempHeader->next = NULL;
return tempHeader;
}//Of initLinkList
void printList(LinkList paraHeader){
NodePtr p = paraHeader->next;
while(p != NULL) {
printf("%d * 10^%d", p->cofficient, p->exponent);
if(p->next != NULL){
printf(" + ");
}
p = p->next;
}//Of while
printf("rn");
}//Of printList
void printNode(NodePtr paraPtr, char paraChar){
if (paraPtr == NULL) {
printf("NULLn");
} else {
printf("The element of %c is (%d * 10^%d)n", paraChar, paraPtr->cofficient, paraPtr->exponent);
}//Of while
} //Of printNode
void appendElement(LinkList paraHeader, int paraCofficient, int paraExponent){
NodePtr p, q;
//Step 1.Construct a new node.
q = (NodePtr)malloc(sizeof(struct LinkNode));
q->cofficient = paraCofficient;
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;
}//Of addpendElement.
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');
s = paraList2; //s for free();
free(s);
//Step 2.add the two list.
while ((p != NULL) && (q != NULL)) {
printf("p->exponent = %d q->exponent = %dn", p->exponent, q->exponent);
if (p->exponent < q->exponent) {
//Link the current node of 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');
//r->next = p;
q = q->next;
printNode(q, 'q');
} else {
printf("case 3rn");
//Change the current node of the first list.
p->cofficient = p->cofficient + q->cofficient;
printf("The cofficient is: %d.n", p->cofficient);
if (p->cofficient == 0) {
printf("case 3.1rn");
s = p;
p = p->next;
printNode(p, 'p');
free(s);
} else {
printf("case 3.2rn");
r = p;
printNode(r, 'r');
p = p->next;
printNode(p, 'p');
} //Of if
s = q;
q = q->next;
free(s);
} //Of if
printf("p = %ld q = %ldn", p, q);
}// Of while
printf("End of while.n");
if (p == NULL) {
r->next = q;
} else {
r->next = p;
} //Of if
printf("Addition ends.rn");
}//Of add.
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);
}//of additionTest
int main(){
additionTest();
printf("Finish.rn");
return 0;
}
代码更改：
因为该相加算法，必须是按照指数从小到大排序的，那么在插入函数时应该自动排序。
另外可以增加加法函数的参数，来实现加法减法, 再把系数乘以（-1），但暂时没成功。
我就去找为什么不成功，发现老师代码有点小问题，就是没有在把q插入p后，把r->next = p;
和把p删除后没有把r->next = p；就少了这俩个，导致链表是断的，直接表现就是输出时会无限循环输出。但是老师的测试确是正确的，为什么呢？
我想了哈应该就是测试的式子太短、太特殊了，刚好其他它的下一个while循环不需要r->next = p；当然改了之后我也不清楚正确没有，欢迎纠错。
所以我的代码如下，新增加俩个r->next = p，和插入后自己排序（插入一个判断一个位置）， 添加一个减法（就第二项系数成了个-1）.
代码：
#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; }// Of initLinkList void printList(LinkList paraHeader){ NodePtr p = paraHeader->next; while (p != NULL) { printf("%d * 10^%d", p->coefficient, p->exponent); if(p->next != NULL){ printf(" + "); } p = p->next; }// Of while printf("rn"); }// Of printList 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 }// Of printNode void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent){ NodePtr p, q; p = paraHeader; q = (NodePtr)malloc(sizeof(struct LinkNode)); q->next = NULL; q->exponent = paraExponent; q->coefficient = paraCoefficient; //第一步-判断是不是空 if (p->next == NULL){ p->next = q; } else { while ((p->next->exponent < paraExponent)) { p = p->next; if(p->next == NULL){ break; } } q->next = p->next; p->next = q; } }//Of addpendElement. void add(NodePtr paraList1, NodePtr paraList2){ NodePtr p, q, r, s; // Step 1. Search to the position. p = paraList1->next; q = paraList2->next; r = paraList1; // Previous pointer for inserting. free(paraList2); // The second list is destroyed. while ((p != NULL) && (q != NULL)) { printf("The p is: %d.rn", p->exponent); printf("The q is: %d.rn", q->exponent); if (p->exponent < q->exponent) { //Link the current node of the first list. r = p; p = p->next; } else if ((p->exponent > q->exponent)) { //Link the current node of the second list. r->next = q; r = q; q = q->next; r->next = p;//增加 } else { //Change the current node of the first list. p->coefficient = p->coefficient + q->coefficient; if (p->coefficient == 0) { s = p; p = p->next; r->next = p;//增加 free(s); s = q; q = q->next; free(s); } else { r = p; p = p->next; s = q; q = q->next; free(s); }// Of if }// Of if } // Of while if (p == NULL) { r->next = q; } else { r->next = p; } // Of if }// Of add void sub(NodePtr paraList1, NodePtr paraList2){ NodePtr t; t = paraList2->next; while(t != NULL){ t->coefficient *= (-1); t = t->next; } NodePtr p, q, r, s; // Step 1. Search to the position. p = paraList1->next; q = paraList2->next; r = paraList1; // Previous pointer for inserting. free(paraList2); // The second list is destroyed. while ((p != NULL) && (q != NULL)) { printf("The p is: %d.rn", p->exponent); printf("The q is: %d.rn", q->exponent); if (p->exponent < q->exponent) { //Link the current node of the first list. r = p; p = p->next; } else if ((p->exponent > q->exponent)) { //Link the current node of the second list. r->next = q; q = q->next; r->next->next = p; r = r->next; } else { //Change the current node of the first list. p->coefficient = p->coefficient + q->coefficient; if (p->coefficient == 0) { s = p; p = p->next; r->next = p; free(s); s = q; q = q->next; free(s); } else { r = p; p = p->next; s = q; q = q->next; free(s); }// Of if }// Of if } // Of while if (p == NULL) { r->next = q; } else { r->next = p; } // Of if }// Of add 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, 5, 17); appendElement(tempList2, 8, 1); appendElement(tempList2, -9, 8); appendElement(tempList2, 22, 7); printList(tempList2); // Step 3. Add them to the first. add(tempList1, tempList2); printList(tempList1); }// Of additionTest void substactionTest(){ // 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); appendElement(tempList2, 5, 17); printList(tempList2); // Step 3. Add them to the first. sub(tempList1, tempList2); printList(tempList1); }// Of additionTest int main(){ additionTest(); substactionTest(); printf("Finish.rn"); return 0; }// Of main
