数据结构之线性

Posted on | In |

两多项式相乘

1
2
P1=3x^4-5x^2+6x-2
P2=5x^20-7x^4+3x

  1. 将乘法运算转换为加法运算

  2. 逐项插入

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <stdlib.h>

typedef struct PolyNode *Polynomial;

struct PolyNode {
    int coef;
    int expon;
    Polynomial link;
};
//Polynomial P1,P2;

/*
 3x^4-5x^2+6x-2
 5x^20-7x^4+3x
 4 3 4 -5 2 6 1 -2 0
 3 5 20 -7 4 3 1
 1. 多项式表示
 2. 程序框架就
 3. 读多项式
 4. 加法实现
 5. 乘法实现
 6. 多项式输出
 */
void Attach(int c, int e, Polynomial *pRear)
{
    Polynomial P;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->link = NULL;
    
    (*pRear)->link = P;
    *pRear = P;
}

Polynomial ReadPoly()
{
    Polynomial P, Rear,t;
    int c,e,N;
    scanf("%d", &N);
    
    P = (Polynomial)malloc(sizeof(struct PolyNode));//头空节点
    P->link = NULL;
    Rear = P;
    
    while (N--) {
        scanf("%d %d",&c,&e);
        Attach(c, e, &Rear);
    }
    
    t = P;
    P = P->link;
    free(t);
    
    return P;
}

Polynomial Add(Polynomial P1, Polynomial P2)
{
    Polynomial t1 = P1;
    Polynomial t2 = P2;
    Polynomial rear = (Polynomial)malloc(sizeof(struct PolyNode));
    Polynomial front = rear;
    
    while (t1&&t2) {
        if (t1->expon == t2->expon) {
            int sum = t1->coef + t2->coef;
            if (sum) {
                Attach(sum, t1->expon, &rear);
            }
            t1 = t1->link;
            t2 = t2->link;
        }
        else if (t1->expon > t2->expon) {
            Attach(t1->coef, t1->expon, &rear);
            t1 = t1->link;
        }
        else {
            Attach(t2->coef, t2->expon, &rear);
            t2 = t2->link;
        }
    }
    while (t1) {
        Attach(t1->coef, t1->expon, &rear);
        t1 = t1->link;
    }
    while (t2) {
        Attach(t2->coef, t2->expon, &rear);
        t2 = t2->link;
    }
    
    rear->link = NULL;
    Polynomial temp = front;
    front = front->link;
    free(temp);
    
    return front;
}

Polynomial Mult(Polynomial P1,Polynomial P2)
{
    if (!P1 || !P2) {
        return NULL;
    }
    
    Polynomial t1 = P1;
    Polynomial t2 = P2;
    Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Polynomial Rear = P;

    while (t2) {
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->link;
    }
    t1 = t1->link;
    
    while (t1) {
        t2 = P2;
        Rear = P;
        while (t2) {
            int e = t1->expon + t2->expon;
            int c = t1->coef * t2->coef;
            
            while (Rear->link && Rear->link->expon > e) {
                Rear = Rear->link;
            }
            
            if (Rear->link && Rear->link->expon == e) {
                if (Rear->link->coef + c) {
                    Rear->link->coef += c;
                }
                else {
                    Polynomial t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            }
            else {
                Polynomial t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->link = Rear->link;
                Rear->link = t;
                Rear = Rear->link;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    t2 = P;
    P = P->link;
    free(t2);
    
    return P;
}

void PrintPoly(Polynomial P)
{
    int flag = 0;
    if (!P) {
        printf("0 0\n");
        return;
    }
    
    while (P) {
        if (!flag) {
            flag = 1;
        }
        else {
            printf(" ");
        }
        printf("%d %d",P->coef,P->expon);
        P = P->link;
    }
    printf("\n");
}

int main()
{
    Polynomial P1,P2,PP,PS;
    P1 = ReadPoly();
    P2 = ReadPoly();
    PP = Mult(P1,P2);
    PrintPoly(PP);
    PS = Add(P1,P2);
    PrintPoly(PS);
    
    return 0;
}

将两个链表表示的递增整数序列合并为一个非递减的整数序列。

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针

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
typedef struct Node *PtrToNode;
typedef int ElementType;

struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

List Merge( List L1, List L2 )
{
    List ret = (struct Node *)malloc(sizeof(struct Node));
    List rear = ret;
    List p = L1->Next;
    List q = L2->Next;
    
    while (p && q) {
        if (p->Data < q->Data) {
            rear->Next = p;
            p = p->Next;
        }
        else {
            rear->Next = q;
            q = q->Next;
        }
        rear = rear->Next;
    }
    rear->Next = NULL;
    
    if (p) {
        rear->Next = p;
    }
    
    if (q) {
        rear->Next = q;
    }
    
    L1->Next = NULL;
    L2->Next = NULL;
    
    return ret;
}