程序人生 链表的应用-多项式的加法

写在前面——

            本章是链表的一个实践，即运用链表来进行多项式的计算。本篇的预备知识——单链表的基本运用。

代码实现如下：

     1.（闵版）

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;

}

//打印函数(1)

void printList(LinkList paraHeader){

NodePtr p = paraHeader->next;

while (p != NULL) {

printf("%d * 10^%d + ", p->coefficient, p->exponent);

p = p->next;

}

printf("\r\n");

}

//打印函数(2)

void printNode(NodePtr paraPtr, char paraChar){

if (paraPtr == NULL) {

printf("NULL\r\n");

} else {

printf("The element of %c is (%d * 10^%d)\r\n", paraChar, paraPtr->coefficient, paraPtr->exponent);

}

}

//添加

void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent){

NodePtr p, q;

q = (NodePtr)malloc(sizeof(struct LinkNode));

q->coefficient = paraCoefficient;

q->exponent = paraExponent;

q->next = NULL;

p = paraHeader;

while (p->next != NULL) {

p = p->next;

}

p->next = q;

}

//加合

void add(NodePtr paraList1, NodePtr paraList2){

NodePtr p, q, r, s;

p = paraList1->next;

printNode(p, 'p');

q = paraList2->next;

printNode(q, 'q');

r = paraList1;

printNode(r, 'r');

free(paraList2);

while ((p != NULL) && (q != NULL)) {

if (p->exponent < q->exponent) {

printf("case 1\r\n");

r = p;

printNode(r, 'r');

p = p->next;

printNode(p, 'p');

} else if ((p->exponent > q->exponent)) {

printf("case 2\r\n");

r->next = q;

r = q;

printNode(r, 'r');

q = q->next;

printNode(q, 'q');

} else {

printf("case 3\r\n");

p->coefficient = p->coefficient + q->coefficient;

printf("The coefficient is: %d.\r\n", p->coefficient);

if (p->coefficient == 0) {

printf("case 3.1\r\n");

s = p;

p = p->next;

printNode(p, 'p');

} else {

printf("case 3.2\r\n");

r = p;

printNode(r, 'r');

p = p->next;

printNode(p, 'p');

}

s = q;

q = q->next;

free(s);

}

printf("p = %ld, q = %ld \r\n", p, q);

}

printf("End of while.\r\n");

if (p == NULL) {

r->next = q;

} else {

r->next = p;

}

printf("Addition ends.\r\n");

}

//单元测试

void additionTest(){

LinkList tempList1 = initLinkList();

appendElement(tempList1, 7, 0);

appendElement(tempList1, 3, 1);

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.\r\n");

return 0;

}

    漏洞：(这里特别鸣谢陈涛同学，以下内容是引用的他的内容，均为引用)

         ""

     我在使用不同的样例测试老师的代码时候发现，我把表2最后的-9×10^8改成了-9×10^10 从而使样例中不存在有多项式可以抵消的情况，我惊奇地发现，运行结果错了。因为我把表2最后的-9×108改成了-9×10^10，从而让表一的9×10^8没有和他指数相同的项可以合并，但是运行结果居然没有了9×10^8这一项，为什么呢。我开始画图寻找原因，在画了两遍之后，我发现老师的代码居然链接的时候将其表1的9×10^8漏链了。

   可以说，最关键的一步就是要将r也就是最新的结点链接到指数小的那一方去（如果相等就链接到p，因为我们保留表一）。但是老师有两个关键步骤没写到，为什么按照老师的样例测试是正确的呢。我又画图分析了一下，发现虽然老师的代码没有将表一的9×10^8链接到我们最后的表一中来，但是，但是！刚好那一个没有链接的表一的9×108的在下一步与表二的-9×10^8抵消了，于是他就被释放了。之所以我们根本没有发现它没有链接进来，是因为最后结果本就不该有它的存在。但是我们将测试用例换成我上诉的样例，就明显发现9×10^8没有在运行结果里面。  

                                                                                                                                ""

2.陈涛同学改进版(主要再add函数处进行了改进)

void add(linkNodePtr paraList1,linkNodePtr paraList2)

{

linkNodePtr p,q,r,s;

/* p用来跟踪表1里面的元素，q用来跟踪表2里面的元素

r是跟踪当前结点的，s是用来free的暂存的（相当于temp）*/

p = paraList1->next ;

q = paraList2->next ;

r = paraList1;

/*其实整体思路也不难，r是跟随最新结点的，根据大小排序，谁指数小

就马上将r的next链接过（即r->next = p 或者 r->next = q这一步）

去，链接过去后将r更新（即r = p 或者 q这一步），并且将小的指针往

后推一个(即 p = p->next 或者 q = q->next这一步)如果指数一样大

且相加不为零的话，肯定是链接到p上面，因为我们整体保存的是表1*/

while(p != NULL && q != NULL)

{

if(p->exponent > q->exponent )

{

printf("case1\r\n");

r->next = q;

/*因为是从小到大排列，p的指数大，

马上就要链接将当前结点r的next到q上，

老师的代码就是失误少写差了这关键的一步

我们走一步就要链一次*/

r = q;

q = q->next;

}

else if(p->exponent < q->exponent )

{

//和上一种情况一样，不再赘述

printf("case2\r\n");

r->next = p;//老师的代码有这一步链接

r = p;

p = p->next;

}

else

{

printf("case3\r\n");

int sum = p->coefficient + q->coefficient;//不妨先申请个变量存放两个的和

if(sum != 0)

{

printf("case3.1\r\n");

p->coefficient = sum;

r->next = p;//这一个链接老师也没写到

r = p;

p = p->next;

s = q; //这里存放q方便后面直接free

q = q->next ;

free(s);

}

else

{

/*这里是唯一一步不用将当前节点r的next链接到小的那一个的一步

因为系数加起来等于零，直接将两个数都free，相当于两个表都往前走了一步*/

printf("case3.2\r\n");

s = p;

p = p->next ;

free(s);

s = q;

q = q->next ;

free(s);

}

}

}

if(p == NULL)

{

r->next = q;

}

else

{

r->next = p;

}

}

3.图示

     本质上，多项式的加法，实质上是多个“表”之间的运算

4.综合修改型代码

#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;

}

//显示函数(1)

void printList(LinkList paraHeader) {

NodePtr p = paraHeader->next;

while (p != NULL) {

printf("%d * 10^%d + ", p->coefficient, p->exponent);

p = p->next;

}

printf("\r\n");

}

//显示函数(2)

void printNode(NodePtr paraPtr, char paraChar) {

if (paraPtr == NULL) {

printf("NULL\r\n");

} else {

printf("The element of %c is (%d * 10^%d)\r\n", paraChar, paraPtr->coefficient, paraPtr->exponent);

}

}

//节点添加函数

void appendElement(LinkList paraHeader, int paraCoefficient, int paraExponent) {

NodePtr p, q;

// 1.创建一个新的结点

q = (NodePtr)malloc(sizeof(struct LinkNode));

q->coefficient = paraCoefficient;

q->exponent = paraExponent;

q->next = NULL;

// 2.遍历链表

p = paraHeader;

while (p->next != NULL) {

p = p->next;

}

// 3.连接链表

p->next = q;

}

//添加函数

void add(LinkList paraList1, LinkList paraList2) {

NodePtr p, q, r, s;

// 1.找到位置

p = paraList1->next;

printNode(p, 'p');

q = paraList2->next;

printNode(q, 'q');

r = paraList1; // 作为新链表的头指针

printNode(r, 'r');

free(paraList2);

while ((p != NULL) && (q != NULL)) {

if (p->exponent < q->exponent) { // 应该排链表1里的结点

printf("case 1\r\n");

r->next = p;

r = p;

printNode(r, 'r');

p = p->next;

printNode(p, 'p');

} else if (p->exponent > q->exponent) { // 应该排链表2里的结点

printf("case 2\r\n");

r->next = q;

r = q;

printNode(r, 'r');

q = q->next;

printNode(q, 'q');

} else {

printf("case 3\r\n");

//Change the current node of the first list.

p->coefficient = p->coefficient + q->coefficient;

printf("The coefficient is: %d.\r\n", p->coefficient);

if (p->coefficient == 0) {

printf("case 3.1\r\n");

s = p;

p = p->next;

printNode(p, 'p');

} else {

printf("case 3.2\r\n");

r->next = p;

r = p; // 连接

printNode(r, 'r');

p = p->next;

printNode(p, 'p');

}

s = q;

q = q->next;

free(s); // 释放不使用的内存空间

}

printf("p = %p, q = %p \r\n", p, q);

}

printf("End of while.\r\n");

if (p == NULL) {

r->next = q;

} else {

r->next = p;

}

printf("Addition ends.\r\n");

}

//单元测试

void additionTest() {

// Step 1. 创建第一个链表

LinkList tempList1 = initLinkList();

appendElement(tempList1, 7, 0);

appendElement(tempList1, 3, 1);

appendElement(tempList1, 9, 8);

appendElement(tempList1, 5, 17);

printList(tempList1);

// Step 2. 创建第一个链表

LinkList tempList2 = initLinkList();

appendElement(tempList2, 8, 1);

appendElement(tempList2, 22, 7);

appendElement(tempList2, -9, 10);

printList(tempList2);

// Step 3. 整合

add(tempList1, tempList2);

printList(tempList1);

}

int main() {

additionTest();

printf("Finish.\r\n");

return 0;

}

参考文章

 您阅读本篇文章共花了：