线性表->应用->一元多项式

文字描述
　　在数学上，一个一元多项式可以按升幂写成如下形式。

　　
　　它由n+1个系数唯一确定。因此，在计算机里，可以用一个线性表P来表示，P中每一项的指数i隐含在其系数pi的序号里。
　　
　　但是在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。比如如下多项式，就要用一个长度为20001的线形表来表示，表中仅有3个非零元素，这种会极其浪费内存空间。
　　
　　针对上面这种情况，可以在线形表中只存放非零的元素，每个元素有两个数据项(系数项和指数项)，如下。这便可唯一确定多项式Pn(x)。在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。

示意图

算法分析
　　多项式的相加过程和之前讨论的归并两个有序表的过程很类似。时间复杂度同单向链表的归并算法相同。

代码实现

  1 //
  2 // Created by lady on 19-2-17.
  3 //
  4 
  5 #include <stdlib.h>
  6 #include <stdio.h>
  7 
  8 typedef struct {
  9     float coef;//系数
 10     int expn;//指数
 11 }term, ElemType;
 12 
 13 typedef struct LNode{//结点类型
 14     ElemType e;
 15     struct LNode *next;
 16 }*Link;
 17 
 18 typedef struct {//链表类型
 19     Link head;//指向线性链表中的头结点
 20 }LinkList;
 21 
 22 typedef LinkList polynomial;//用带表头结点的有序链表表示多项式
 23 
 24 //构造一个空的线性链表L
 25 static int InitList(LinkList *L)
 26 {
 27     if(L == NULL)
 28         return -1;
 29     Link p = (Link)malloc(sizeof(struct LNode));
 30     p->next = NULL;
 31     L->head = p;
 32     return 0;
 33 }
 34 
 35 //返回链表L的头结点
 36 static Link GetHead(LinkList *L){
 37     if(L==NULL){
 38         return NULL;
 39     }
 40     return L->head;
 41 }
 42 
 43 //设置p结点的数据元素值为e
 44 static void SetCurElem(Link p, ElemType e)
 45 {
 46     p->e = e;
 47     return 0;
 48 }
 49 
 50 //返回线性表L中第1个与e满足函数fun判定关系的元素的位置，并用q指示其结点地址值
 51 static int LocateElem(LinkList *L, ElemType e, Link *q, int (*fun)(term, term))
 52 {
 53     Link p = L->head->next;
 54     (*q) = L->head;
 55     while(p){
 56         if(fun(p->e, e) == 0){
 57             (*q) = p;
 58             return 0;
 59         }
 60         (*q) = p;
 61          p = p->next;
 62     }
 63     return -1;
 64 }
 65 
 66 //已知h指向线性表的头结点，将s所指结点插入在第一个结点之前
 67 static int InsFirst(Link *h, Link *s)
 68 {
 69     if(h==NULL || s==NULL){
 70         return -1;
 71     }
 72     if(*h == NULL || *s == NULL){
 73         return -1;
 74     }
 75     (*s)->next = (*h)->next;
 76     (*h)->next = (*s);
 77     return 0;
 78 }
 79 
 80 //创建新的结点，其地址值为*p, 结点值为e
 81 static int MakeNode(Link *p, ElemType e)
 82 {
 83     if(p==NULL){
 84         return -1;
 85     }
 86     if(((*p) = (Link)malloc(sizeof(struct LNode))) == NULL){
 87         return -1;
 88     }
 89     (*p)->next = NULL;
 90     (*p)->e = e;
 91     return 0;
 92 }
 93 
 94 //返回链表L中p结点的后继
 95 static Link NextPos(LinkList *L, Link p)
 96 {
 97     if(L == NULL || p==NULL){
 98         return NULL;
 99     }
100     return p->next;
101 }
102 
103 //返回结点p的数据元素值
104 static  ElemType GetCurElem(Link p)
105 {
106     return p->e;
107 }
108 
109 //释放结点及其一系列后面的结点的存储空间
110 static void FreeNode(Link p)
111 {
112     Link q;
113     while(p){
114         q = p;
115         p = p->next;
116         free(q);
117     }
118     return;
119 }
120 //已知h指向线性链表的头结点，删除链表中的第一个结点并以求返回
121 static int DelFirst(Link *h, Link *q)
122 {
123     if(h==NULL || q==NULL){
124         return -1;
125     }
126     if(*h == NULL || *q == NULL){
127         return -1;
128     }
129     (*q) = (*h)->next;
130     (*h)->next = (*q)->next;
131     (*q)->next = NULL;
132     return 0;
133 }
134 
135 //返回1-链表为空， 返回0-链表非空
136 static int ListEmpty(LinkList *L)
137 {
138     if(L->head->next == NULL){
139         return 1;
140     }else{
141         return 0;
142     }
143 }
144 
145 //将指针s所指的一串结点连接到线性链表L的最后一个结点
146 static int Append(LinkList *L, Link *s)
147 {
148     if(L == NULL || s==NULL || *s==NULL){
149         return -1;
150     }
151     Link p = L->head->next;
152     Link q = L->head;
153     while(p){
154         q = p;
155         p = p->next;
156     }
157     q->next = (*s);
158     return 0;
159 }
160 
161 /*
162  * 依a的指数值<(或=)(或>)b的指数值，分别返回-1、0和+1
163  */
164 static int cmp(term a, term b)
165 {
166     if(a.expn<b.expn){
167         return -1;
168     }else if(a.expn == b.expn){
169         return 0;
170     }else{
171         return 1;
172     }
173 }
174 
175 
176 
177 //输入m项的系数和指数，建立表示一元多项式的有序链表P
178 static void CreatPolyn(polynomial *P, int m, char note[]){
179     printf("创建多项式%s!
", note);
180     int i = 0;
181     Link h;
182     Link s;
183     Link q;
184     ElemType e;
185     InitList(P);
186     h = GetHead(P);
187     e.coef = -1;
188     e.expn = -1;
189     SetCurElem(h, e);//设置头结点的数据元素
190     for(i=1; i<=m; i++){//依次输入m个非零项
191         printf("输入第%d个非0项(系数,指数):", i);
192         scanf("%f,%d[^\n]", &e.coef, &e.expn);
193         if(LocateElem(P, e, &q, cmp)<0){//如果当前链表中不存在该指数项
194             if(MakeNode(&s, e)==0){//生成结点并插入链表
195                 InsFirst(&q, &s);
196             }
197         }
198     }
199     return ;
200 }
201 
202 //打印一元多项式
203 static void PrintPolyn(polynomial P, char note[])
204 {
205     printf("打印输出一元多项式%s: ", note);
206     Link p = P.head->next;
207     while(p){
208         printf("%.2fx^%d", p->e.coef, p->e.expn);
209         if(p->next){
210             printf("+");
211         }
212         p = p->next;
213     }
214     printf("
");
215 }
216 
217 //多项式加法：Pa=Pa+Pb,利用两个多项式的结点构成"和多项式"
218 static void AddPolyn(polynomial *Pa, polynomial *Pb, char note[])
219 {
220     printf("多项式相加,%s!
", note);
221     //ha和hb分别指向Pa和Pb的头结点
222     Link ha = GetHead(Pa);
223     Link hb = GetHead(Pb);
224     //qa和qb分别指向Pa和Pb中的当前结点
225     Link qa = NextPos(Pa, ha);
226     Link qb = NextPos(Pb, hb);
227     ElemType a;
228     ElemType b;
229     ElemType e;
230     while(qa && qb){//qa和qb均非空
231         //a和b为两个表中当前的比较元素
232         a = GetCurElem(qa);
233         b = GetCurElem(qb);
234         switch(cmp(a,b)){
235             case -1://a<b，多项式Pa中当前结点的指数小
236                 ha = qa;
237                 qa = NextPos(Pa, qa);
238                 break;
239             case 0://a==b，两者的指数值相等
240                 e.expn = a.expn;
241                 e.coef = a.coef+b.coef;
242                 if(e.coef!=0.0){//修改多项式Pa中当前结点的系数值
243                     SetCurElem(qa, e);
244                     ha = qa;
245                 }else{
246                     DelFirst(&ha, &qa);
247                     FreeNode(qa);
248                 }
249                 DelFirst(&hb, &qb);
250                 FreeNode(qb);
251                 qb = NextPos(Pb, hb);
252                 qa = NextPos(Pa, ha);
253                 break;
254             case 1://a>b，多项式Pb中当前结点的指数小
255                 DelFirst(Pb, &qb);
256                 qb->next = NULL;
257                 InsFirst(&ha, &qb);
258                 qb = NextPos(Pb, hb);
259                 qa = NextPos(Pa, ha);
260                 break;
261         }
262     }
263     if(ListEmpty(Pb)==0){//链接Pb中剩余结点
264         Append(Pa, &qb);
265     }
266     FreeNode(hb);//释放Pb的头结点
267     return ;
268 }
269 
270 int main(int argc, char *argv[])
271 {
272     polynomial A;//7+3x+9x^8+5x^17
273     polynomial B;//8x+22x^7-9x^8
274 
275     CreatPolyn(&A, 4, "A");
276     PrintPolyn(A, "A");
277 
278     CreatPolyn(&B, 3, "B");
279     PrintPolyn(B, "B");
280 
281     AddPolyn(&A, &B, "A=A+B");
282     PrintPolyn(A, "A");
283     return 0;
284 }

线性表的应用(一元多项式)

代码运行

/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
创建多项式A!
输入第1个非0项(系数,指数):7,0
输入第2个非0项(系数,指数):3,1
输入第3个非0项(系数,指数):9,8
输入第4个非0项(系数,指数):5,17
打印输出一元多项式A: 7.00x^0+3.00x^1+9.00x^8+5.00x^17
创建多项式B!
输入第1个非0项(系数,指数):8,1
输入第2个非0项(系数,指数):22,7
输入第3个非0项(系数,指数):-9,8
打印输出一元多项式B: 8.00x^1+22.00x^7+-9.00x^8
多项式相加,A=A+B!
打印输出一元多项式A: 7.00x^0+11.00x^1+22.00x^7+5.00x^17

Process finished with exit code 0