单链表的应用

问题描述：

完成两个多项式的相加操作:已知有两个多项式P(x)、Q(x)， 设计算法实现P(x)+Q(x)运算，而且对加法运算不重新开辟存储空间。要求用链式存储结构实现。例如:

算法设计

程序中设计了四个函数:
➢函数Init()用来初始化一一个空链表;
➢函数CreateTail()用来创建一-个链表， 这里是用尾插法来创建链表;
➢函数add()用来实现两个多项式相加算法;
➢函数print()用来输出多项式。
两个多项式相加算法的实现，首先是将两个多项式分别用链表进行存放。可以设置两个指针LA1和LB1分别从多项式Pm(x)和Qm(x)的首结点移动，比较LA1和LB1所指结点的指数项，则可以分下面三种情况进行处理:
(1) 若LA1->exp < LB1->exp，则LA1所指结点为多项式中的一项，LA1 指针在原来的基础_上向后移动一个位置。
(2)若LA1->exp=LB1->exp， 将对应项的系数相加，然后分两种情况处理:如果系数
项的和为零，则释放LA1和LB1所指向的结点;如果系数项的和不为零，则修改LA1所
指向结点的系数域，释放LB1结点。
(3)若LA1->exp>LB1->exp， 则LB1所指结点为多项式中的一项，LB1指针在原来的
基础上向后移动一个位置。
实验图如图所示：

程序实现

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct poly
{
    int exp;//指数幂
    int coef;//指数
    struct poly* next;//指针域
}PNode,*Plinklist;
int Init(Plinklist* head)//链表的初始化
{
    *head=(Plinklist)malloc(sizeof(PNode));
    if(*head)
    {
        (*head)->next=NULL;
        return 1;
    }
    else
        return 0;
}
int CreateTail(Plinklist *head)//尾插法创建链表
{
    Plinklist pTemp,pHead;
    int c;//存放系数
    int exp;//存放指数
    int i=1;//计数用户计算到第几项
    pHead=*head;
    scanf("%d,%d",&c,&exp);
    while(c!=0)
    {
        pTemp=(Plinklist)malloc(sizeof(PNode));
        if(pTemp)
        {
            pTemp->exp=exp;
            pTemp->coef=c;
            pTemp->next=NULL;
            pHead->next=pTemp;
            pHead=pTemp;
            scanf("%d,%d",&c,&exp);
        }
        else
            return 0;
    }
    return 1;
}
void add(Plinklist LA,Plinklist LB)//两个多项式相加，两个表都是按指数顺序增长
{
    PNode *LA1=LA->next;//LA的移动
    PNode *LB1=LB->next;//LB的移动
    PNode *temp;//保存要删除的节点
    int sum=0;//存放系数的和
    while(LA1&&LB1)
    {
        if(LA1->exp<LB1->exp)
        {
            LA->next=LA1;
            printf("%d %d\n",LA->coef,LA->exp);
            LA=LA->next;
            LA1=LA1->next;
        }
        else if(LA1->exp==LB1->exp)
        {
            sum=LA1->coef+LB1->coef;
            if(sum)
            {
                LA1->coef=sum;
                LA->next=LA1;
                LA=LA->next;
                LA1=LA1->next;
                temp=LB1;
                LB1=LB1->next;
                free(temp);
            }
            else
            {
                temp=LA1;
                LA1=LA1->next;
                free(temp);
                temp=LB1;
                LB1=LB1->next;
                free(temp);
            }
        }
        else
        {
            LA->next=LB1;
            LA=LA->next;
            LB1=LB1->next;
        }
    }
    if(LA1)//剩余节点插入链表
        LA->next=LA1;
    else
        LA->next=LB1;
}
void print(Plinklist head)//输出多项式
{
    head=head->next;
    while(head)
    {
        if(head->exp)
            printf("%dx^%d",head->coef,head->exp);
        else
            printf("%d",head->coef);
        if(head->next)
            printf("+");
        else
            break;
        head=head->next;
    }
}
int main()
{
    Plinklist LA,LB;
    Init(&LA);
    Init(&LB);
    printf("请输入第一个多项式的系数，指数（如2,3）输入0,0结束输入\n");
    CreateTail(&LA);
    printf("请输入第二个多项式的系数，指数（如2,3）输入0,0结束输入\n");
    CreateTail(&LB);
    print(LA);
    printf("\n");
    print(LB);
    printf("\n");
    add(LA,LB);
    printf("两个多项式相加的结果为：\n");
    print(LA);
    printf("\n");
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
 

运行结果:

代码写完了，借鉴一本书上完成的。但是在两个多项式相加的函数中最后有一个判断语句：

这个还是不太明白为什么要加这一句话，好像去掉了也没有什么影响吧。有没有大佬可以告诉小白一下，是我少考虑了那种情况？

文章来源: wlybsy.blog.csdn.net，作者：万里羊，版权归原作者所有，如需转载，请联系作者。

原文链接：wlybsy.blog.csdn.net/article/details/105124438