用两链表解决两多项式求和问题

zerotwo020202

void Add(LinkList *pa, LinkList *pb)          //找出两链表的首元节点中指数最小的那个链表作为合并后的链表表头//
{
    LinkList pab,pB,temp,temp2;
    if((*pa)->next->data.expn <= (*pb)->next->data.expn)
    {   
        pab = (*pa)->next;                   //将pa链表的头节点pa当作相加后的pab链表的头节点，pab指向首元节点//   
        pB = (*pb)->next;
    }
    else
    {
        pab = (*pb)->next;
        pB = (*pa)->next;
    }
    while(pab != NULL && pB != NULL)
    {
        if(pab->data.expn == pB->data.expn)
        {
            pab->data.coef += pB->data.coef;
            pB = pB->next;
        }
        if(pab->data.expn < pB->data.expn)
        {
            temp = pab;
            if(pab->next != NULL)
            {
                pab = pab->next;
                if(pab->data.expn > pB->data.expn)
                {   
                    temp2 = pB->next;
                    pB->next = pab;
                    temp->next = pB;
                    pab = pB;
                    pB = temp2;
                }
            }
            else
            {
                pab->next = pB;
                break;
            }
        }
    }
}

int main(void)
{
    int n,m,ch;
    LinkList pa,pb;                     //定义头节点//
   
    pa = (LinkList)malloc(sizeof(Lnode));
    pb = (LinkList)malloc(sizeof(Lnode));
    if(pa == NULL || pb == NULL)
    {
        printf("error!O.o\n");
    }
    pa->next = NULL;
    pb->next = NULL;
    printf("How many terms are there in the polynomial pa:");
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        Create(&pa);
    }
    Print(pa);
    putchar('\n');
    printf("How many terms are there in the polynomial pb:");
    scanf("%d", &m);
    for(int i = 0; i < m; i++)
    {
        Create(&pb);
    }
    Print(pb);
    putchar('\n');

    if(pa->next->data.expn <= pb->next->data.expn)
    {
        ch = 1;
    }
    else
    {
        ch = 0;
    }

    Add(&pa, &pb);

    if(ch)
    {
        Delete(&pa);
        Print(pa);
    }
    else
    {
        Delete(&pb);
        Print(pb);
    }

    return 0;
}

请问为啥Add函数调用结束后，main函数直接退出了？main函数中写的Add(&pa, &pb) ，请问是哪里的指针出问题了吗？

zerotwo020202

我的想法是如果先把首元节点中指数较小的那个链表选出来，根据我后面的循环，可以不用再去判断if（大于）的情况了

isdkz

Add 函数本身的逻辑没有问题，但是 main 函数在处理多项式的创建和添加部分有一些问题。

首先，你需要实现 Create 和 Print 函数。同时，需要在创建多项式的过程中输入多项式的系数和指数。

下面是修改后的代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct {
   
5.     float coef;
   
6.     int expn;
   
7. } PolyElemType;
   
8. 
   
9. typedef struct LNode {
   
10.     PolyElemType data;
    
11.     struct LNode *next;
    
12. } LNode, *LinkList;
    
13. 
    
14. void Create(LinkList *L) {
    
15.     LNode *p, *q;
    
16.     PolyElemType e;
    
17. 
    
18.     printf("Enter the coefficient and exponent: ");
    
19.     scanf("%f %d", &e.coef, &e.expn);
    
20. 
    
21.     p = *L;
    
22.     while (p->next != NULL && p->next->data.expn < e.expn) {
    
23.         p = p->next;
    
24.     }
    
25. 
    
26.     q = (LNode *) malloc(sizeof(LNode));
    
27.     q->data = e;
    
28.     q->next = p->next;
    
29.     p->next = q;
    
30. }
    
31. 
    
32. void Print(LinkList L) {
    
33.     LNode *p = L->next;
    
34. 
    
35.     while (p != NULL) {
    
36.         printf("(%.1f, %d)", p->data.coef, p->data.expn);
    
37.         if (p->next != NULL) {
    
38.             printf(" -> ");
    
39.         }
    
40.         p = p->next;
    
41.     }
    
42.     printf("\n");
    
43. }
    
44. 
    
45. // 省略 Add 函数，该函数无需修改
    
46. 
    
47. int main(void) {
    
48.     int n, m, ch;
    
49.     LinkList pa, pb;
    
50. 
    
51.     pa = (LinkList) malloc(sizeof(LNode));
    
52.     pb = (LinkList) malloc(sizeof(LNode));
    
53.     if (pa == NULL || pb == NULL) {
    
54.         printf("error!O.o\n");
    
55.     }
    
56.     pa->next = NULL;
    
57.     pb->next = NULL;
    
58.     printf("How many terms are there in the polynomial pa: ");
    
59.     scanf("%d", &n);
    
60.     for (int i = 0; i < n; i++) {
    
61.         Create(&pa);
    
62.     }
    
63.     Print(pa);
    
64.     putchar('\n');
    
65.     printf("How many terms are there in the polynomial pb: ");
    
66.     scanf("%d", &m);
    
67.     for (int i = 0; i < m; i++) {
    
68.         Create(&pb);
    
69.     }
    
70.     Print(pb);
    
71.     putchar('\n');
    
72. 
    
73.     if (pa->next->data.expn <= pb->next->data.expn) {
    
74.         ch = 1;
    
75.     } else {
    
76.         ch = 0;
    
77.     }
    
78. 
    
79.     Add(&pa, &pb);
    
80. 
    
81.     if (ch) {
    
82.         // Delete(&pa); // 如果你要实现 Delete 函数，请在此处调用它
    
83.         Print(pa);
    
84.     } else {
    
85.         // Delete(&pb); // 如果你要实现 Delete 函数，请在此处调用它
    
86.         Print(pb);
    
87.     }
    
88. 
    
89.     return 0;
    
90. }

复制代码

上述代码中，我为你实现了 Create 和 Print 函数，并修改了 main 函数，以正确创建多项式并打印结果。

现在程序应该可以正常运行了。如果你还需要实现 Delete 函数来删除多项式中的零系数项，请在调用 Print 之前添加相应的调用。

zerotwo020202

isdkz 发表于 2023-3-24 18:39
Add 函数本身的逻辑没有问题，但是 main 函数在处理多项式的创建和添加部分有一些问题。

首先，你需要实 ...

大佬好，我是写了create和print函数的，只是我怕太长了，就没放进来了

zerotwo020202

zerotwo020202 发表于 2023-3-24 19:11
大佬好，我是写了create和print函数的，只是我怕太长了，就没放进来了

void GetInput(LinkList new)
{
    printf("Please enter the coefficient for this item:");
    scanf("%f", &new->data.coef);
    printf("Please enter the exponent for this item:");
    scanf("%d", &new->data.expn);
}

void Create(LinkList *head)
{
    Lnode *new,*temp;
    new = (LinkList)malloc(sizeof(Lnode));
    temp = *head;
    GetInput(new);
    putchar('\n');
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = new;
    new->next = NULL;

    if((*head)->next == NULL)
    {
        (*head)->next = new;
        new->next = NULL;        
    }

}

void Delete(LinkList *head)
{
    Lnode *q,*temp;
    q = (LinkList)malloc(sizeof(Lnode));
    temp = NULL;
    while((*head)->next->data.coef == 0)
    {
        (*head)->next = (*head)->next->next;
    }
    q = (*head)->next;
    while(q->next != NULL)
    {
        if(q->data.coef == 0)
        {
            temp->next = q->next;
        }
        else
        {
            temp = q;
            q = q->next;
        }
    }
    if(q->data.coef == 0)
    {
        temp->next = NULL;
    }
}

void Print(LinkList head)
{
    Lnode *q;
    q = head->next;                     //头节点不存放数据，从首元节点开始打印//
    printf("Fx=");
    while(q->next != NULL)
    {
        printf("%.1fx^%d+ ", q->data.coef, q->data.expn);
        q = q->next;
    }
    printf("%.1fx^%d\n", q->data.coef, q->data.expn);
}

zerotwo020202

isdkz 发表于 2023-3-24 18:39
Add 函数本身的逻辑没有问题，但是 main 函数在处理多项式的创建和添加部分有一些问题。

首先，你需要实 ...

但是我把add函数里的
        if(pab->data.expn < pB->data.expn)
        {
            temp = pab;
            if(pab->next != NULL)
            {
                pab = pab->next;
                if(pab->data.expn > pB->data.expn)
                {   
                    temp2 = pB->next;
                    pB->next = pab;
                    temp->next = pB;
                    pab = pB;
                    pB = temp2;
                }
            }
            else
            {
                pab->next = pB;
                break;
            }
        }
    }
这一段删除后，（构建两个系数都相等的多项式）可以正确运行，加上这段就不行了

isdkz

zerotwo020202 发表于 2023-3-24 19:15
但是我把add函数里的
        if(pab->data.expn < pB->data.expn)
        {

在 Add 函数中，你需要对指数小于其他链表中当前项指数的情况进行处理。

在你的代码中，当 pab->data.expn < pB->data.expn 时，你需要在 pab 链表中寻找合适的位置插入 pB 当前项。

你需要更改这一段代码，以在 pab 链表中找到合适的位置插入 pB 当前项。

请参考以下修改后的代码：

1. if (pab->data.expn < pB->data.expn) {
   
2.     temp = pab;
   
3.     while (temp->next != NULL && temp->next->data.expn < pB->data.expn) {
   
4.         temp = temp->next;
   
5.     }
   
6.     temp2 = pB->next;
   
7.     pB->next = temp->next;
   
8.     temp->next = pB;
   
9.     pB = temp2;
   
10. }

复制代码

这段代码首先初始化一个临时指针 temp，指向 pab 当前项。然后遍历 pab 链表，

直到找到一个位置，使得 temp 所指向项的指数小于 pB 当前项的指数，并且 temp->next 项的指数大于等于 pB 当前项的指数。

然后将 pB 当前项插入到 temp 项之后，更新 pB 指针指向下一个项。这样就可以保证链表的有序性。

现在，整个 Add 函数应该可以正常工作了。你可以尝试使用修改后的代码，看看是否可以解决你的问题。

zerotwo020202

isdkz 发表于 2023-3-24 19:20
在 Add 函数中，你需要对指数小于其他链表中当前项指数的情况进行处理。

在你的代码中，当 pab->data. ...

大佬，有点不太对，假如：
pa多项式=7.0x^0+ 3.0x^1+ 9.0x^8+ 5.0x^17
pb多项式=8.0x^1+ 22.0x^7+ -9.0x^8
用这两个算出来结果不太对，运行结果是
合并后的pa=7.0x^0+ 3.0x^1+ 8.0x^1+ 22.0x^7+ 9.0x^8+ -9.0x^8+ 5.0x^17，看起来好像是直接把系数相等那个if条件去掉了，并没有运行那一部分

isdkz

zerotwo020202 发表于 2023-3-24 19:33
大佬，有点不太对，假如：
pa多项式=7.0x^0+ 3.0x^1+ 9.0x^8+ 5.0x^17
pb多项式=8.0x^1+ 22.0x^7+ -9.0 ...

在细看代码后，我发现在处理两个链表指数相等的情况时，没有更新 pab 指针。


这可能导致在之后的循环中出现问题。修改一下 Add 函数的代码：

1. void Add(LinkList *pa, LinkList *pb) {
   
2.     LinkList pab, pB, temp, temp2;
   
3.     if ((*pa)->next->data.expn <= (*pb)->next->data.expn) {
   
4.         pab = (*pa)->next;
   
5.         pB = (*pb)->next;
   
6.     } else {
   
7.         pab = (*pb)->next;
   
8.         pB = (*pa)->next;
   
9.     }
   
10.     while (pab != NULL && pB != NULL) {
    
11.         if (pab->data.expn == pB->data.expn) {
    
12.             pab->data.coef += pB->data.coef;
    
13.             pB = pB->next;
    
14.             temp = pab;
    
15.             pab = pab->next;
    
16.         } else if (pab->data.expn < pB->data.expn) {
    
17.             temp = pab;
    
18.             while (temp->next != NULL && temp->next->data.expn < pB->data.expn) {
    
19.                 temp = temp->next;
    
20.             }
    
21.             temp2 = pB->next;
    
22.             pB->next = temp->next;
    
23.             temp->next = pB;
    
24.             pB = temp2;
    
25.         } else {
    
26.             pab = pab->next;
    
27.         }
    
28.     }
    
29. }

复制代码

在这个版本中，当两个链表当前项的指数相等时，我们不仅更新了系数，还更新了 pab 指针。这样，在处理 pab->data.expn < pB->data.expn 的情况时，我们可以保证 pab 指针总是指向正确的位置。

zerotwo020202

isdkz 发表于 2023-3-24 19:39
在细看代码后，我发现在处理两个链表指数相等的情况时，没有更新 pab 指针。

大佬，还是一样的啊，
while (temp->next != NULL && temp->next->data.expn < pB->data.expn) {
                temp = temp->next;
            }
这一段中，就根据我之间发的那个例子，当pa链表第二个节点的指数是1，跟pb的首元节点一样大，这样的情况下应该是要返回到上面相等的那个if条件，而
if (pab->data.expn < pB->data.expn) {
            temp = pab;
            while (temp->next != NULL && temp->next->data.expn < pB->data.expn) {
                temp = temp->next;
            }
            temp2 = pB->next;
            pB->next = temp->next;
            temp->next = pB;
            pB = temp2;
        }
这么写的话，就跟刚才一样的，没有加到一起去，在相等那个if条件里的temp指针更新也只是往后移了一位，并没有把系数相同的加到一起

不二猫猫

在 main 函数中调用 Add(&pa, &pb) 后，程序没有直接退出。但是，由于在 Add 函数中没有返回任何值，也没有对 pa 和 pb 的指针进行修改，因此 main 函数输出的结果仍然是原先的两个链表 pa 和 pb。

可能是你没有在 Print 函数中打印出换行符，导致最后输出的结果和输入提示信息连在一起，看起来像是程序直接退出了。你可以在 Print 函数中加上 putchar('\n') 来打印出一个换行符，使输出结果更加清晰。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node {
   
5.     int coef;       // 系数
   
6.     int exp;        // 指数
   
7.     struct Node *next;
   
8. } Node, *LinkList;
   
9. 
   
10. // 创建一个新节点
    
11. Node *new_node(int coef, int exp) {
    
12.     Node *newNode = (Node*)malloc(sizeof(Node));
    
13.     newNode->coef = coef;
    
14.     newNode->exp = exp;
    
15.     newNode->next = NULL;
    
16.     return newNode;
    
17. }
    
18. 
    
19. // 向链表末尾添加一个节点
    
20. void add_node(LinkList *list, Node *node) {
    
21.     Node *p = *list;
    
22.     while (p->next != NULL) {
    
23.         p = p->next;
    
24.     }
    
25.     p->next = node;
    
26. }
    
27. 
    
28. // 读取多项式
    
29. void read_polynomial(LinkList *list) {
    
30.     int n;
    
31.     printf("How many terms are there in the polynomial: ");
    
32.     scanf("%d", &n);
    
33.     printf("Input each term: \n");
    
34.     for (int i = 0; i < n; i++) {
    
35.         int coef, exp;
    
36.         scanf("%d%d", &coef, &exp);
    
37.         Node *newNode = new_node(coef, exp);
    
38.         add_node(list, newNode);
    
39.     }
    
40. }
    
41. 
    
42. // 打印多项式
    
43. void print_polynomial(LinkList list) {
    
44.     Node *p = list->next;
    
45.     while (p != NULL) {
    
46.         printf("%d %d ", p->coef, p->exp);
    
47.         p = p->next;
    
48.     }
    
49.     putchar('\n');
    
50. }
    
51. 
    
52. // 合并两个多项式
    
53. LinkList merge_polynomial(LinkList pa, LinkList pb) {
    
54.     LinkList pab, p, q;
    
55.     Node *newNode;
    
56.     p = pa->next;
    
57.     q = pb->next;
    
58.     pab = (LinkList)malloc(sizeof(Node));
    
59.     pab->next = NULL;
    
60.     while (p != NULL && q != NULL) {
    
61.         if (p->exp < q->exp) {
    
62.             newNode = new_node(p->coef, p->exp);
    
63.             add_node(&pab, newNode);
    
64.             p = p->next;
    
65.         } else if (p->exp > q->exp) {
    
66.             newNode = new_node(q->coef, q->exp);
    
67.             add_node(&pab, newNode);
    
68.             q = q->next;
    
69.         } else {
    
70.             int coef = p->coef + q->coef;
    
71.             if (coef != 0) {
    
72.                 newNode = new_node(coef, p->exp);
    
73.                 add_node(&pab, newNode);
    
74.             }
    
75.             p = p->next;
    
76.             q = q->next;
    
77.         }
    
78.     }
    
79.     while (p != NULL) {
    
80.         newNode = new_node(p->coef, p->exp);
    
81.         add_node(&pab, newNode);
    
82.         p = p->next;
    
83.     }
    
84.     while (q != NULL) {
    
85.         newNode = new_node(q->coef, q->exp);
    
86.         add_node(&pab, newNode);
    
87.         q = q->next;
    
88.     }
    
89.     return pab;
    
90. }
    
91. 
    
92. int main(void) {
    
93.     LinkList pa, pb, pab;
    
94.     pa = (LinkList)malloc(sizeof(Node));
    
95.     pb = (LinkList)malloc(sizeof(Node));
    
96.     pa->next = NULL;
    
97.     pb->next = NULL;
    
98.     read_polynomial(&pa);
    
99.     print_polynomial(pa);
    
100.     read_polynomial(&pb);
     
101.     print_polynomial(pb);
     
102.     pab = merge_polynomial(pa, pb);
     
103.     print_polynomial(pab);
     
104.     return 0;
     
105. }
     
106. 注释中对代码进行了简化，主要修改如下：
     
107. 
     
108. 将 Create 函数替换为 read_polynomial 函数，直接读取多项式的系数和指数，并将其添加到链表中；
     
109. 将 Print 函数替换为 print_polynomial 函数，直接打印多项式；
     
110. 将 Add 函数替换为 merge_polynomial 函数，直接合并两个多项式并返回结果链表；
     
111. 使用 typedef 定义了 Node 和 LinkList，使代码更加简洁易读；
     
112. 使用动态内存分配 malloc 分配链表头节点，避免了静态数组大小的限制。

复制代码

zerotwo020202

不二猫猫 发表于 2023-3-25 16:00
在 main 函数中调用 Add(&pa, &pb) 后，程序没有直接退出。但是，由于在 Add 函数中没有返回任何值，也没有 ...

大佬，虽然你的答案是对的，但是没有解决我的问题，我想知道的是为什么我的有错误，错误在哪？您刚才说的那个错误并不是，程序是直接退出了的，直接出来的这个
PS D:\VScode\vsc\数据结构与算法>

zerotwo020202

不二猫猫 发表于 2023-3-25 16:00
在 main 函数中调用 Add(&pa, &pb) 后，程序没有直接退出。但是，由于在 Add 函数中没有返回任何值，也没有 ...

所以请恕我无法给您设为最佳答案，不好意思，谢谢您的回复

不二猫猫

zerotwo020202 发表于 2023-3-25 22:19
大佬，虽然你的答案是对的，但是没有解决我的问题，我想知道的是为什么我的有错误，错误在哪？您刚才说的 ...

在Add函数中，pab和pB变量应该声明为指向Lnode结构体类型的指针，而不是LinkList类型的指针。因此，函数签名应该是void Add(Lnode **pa, Lnode **pb)，并且在函数中应该使用->操作符而不是*操作符。

在Create函数中，应该使用&操作符将指针的地址传递给scanf函数，而不是指针本身。因此，应该使用scanf("%d%d", &t.coef, &t.expn);。

在Print函数中，应该使用->操作符而不是*操作符。

在main函数中，如果pa或pb指向的节点为空，那么在调用Add函数时会出现空指针引用错误。因此，应该在调用Add函数之前检查它们是否为空。

在Add函数中，当pab或pB到达链表的末尾时，应该退出循环而不是继续执行。

在Delete函数中，应该使用free函数释放节点的内存空间。

在main函数中，当pa或pb指向的节点为空时，Delete函数可能会引起空指针引用错误。应该在调用Delete函数之前检查它们是否为空。

在main函数中，应该释放pa和pb的内存空间。