链栈实现一元多项式的加法
1.初始化栈
1.1一元多项式的栈结构
typedef struct LinkStackNode{
ElemType data1;//储存系数 ElemType可以指任意数据类型 本次使用的为int
ElemType data2;//储存指数
struct LinkStackNode* next;
}LinkStackNode,*LinkStack;
1.2两个空栈
void InitStack(LinkStack& S1,LinkStack& S2)
{
S1 = (LinkStack)malloc(sizeof(LinkStackNode));
S2 = (LinkStack)malloc(sizeof(LinkStackNode));
S1->next = NULL;
S2->next = NULL;
}
2.建立一元多项式
2.1算法思想
-
通过while循环持续读取一元多项式的系数和指数,循环结束条件为输入系数为0
-
将读取到的a,b的值传递给Push函数
-
Push函数让系数,指数储存到栈中
2.2算法设计
//入栈操作
void Push(LinkStack& S,ElemType a,ElemType b)
{
LinkStack temp= (LinkStack)malloc(sizeof(LinkStackNode));
temp->data1 = a;
temp->data2 = b;
temp->next = S->next;
S->next = temp;
}
//通过循环和Push函数让系数,指数储存到栈中
void InitLinkStack(LinkStack& S)
{
int a, b, i = 1;
printf("请按指数从大到小输入\n");
printf("请输入第%d项的系数:", i);
scanf("%d", &a);
while (a != 0)
{
printf("请输入第%d项的指数:", i);
scanf("%d", &b);
Push(S, a, b);
i++;
printf("请输入第%d项的系数:", i);
scanf("%d", &a);
}
}
3.加法函数
3.1算法思想
-
用创建三个指示器p,q1,q2
-
q1指向第一个式子的项(初值设为第一个链栈的首元结点)
-
q2指向第二个式子的项(初值设为第二个链栈的首元结点)
-
p指向q1的前一个结点(初值设为第一个链栈的头结点)
-
-
比较q1和q2指向项的指数大小(也就是比较q1->data2和q2->data2)
-
q1->data2大于q2->data2,则将q2插到q1的前面,q1不变,让p重新指向q1的前继结点,q2指向后续结点
-
q1->data2等于q2->data2,则将这两个项数的系数相加赋予q1,之和为零则删除该项,让q1,q2分别指向后继结点
-
q1->data2小于q2->data2,则让q1指向后继结点,q2不变
-
-
如果q2先为空,则加法结束
-
如果q1先为空,则让p直接指向q2
3.2算法设计
void add(LinkStack& S1,LinkStack S2)
{
LinkStack p = (LinkStack)malloc(sizeof(LinkStackNode));
LinkStack q1 = (LinkStack)malloc(sizeof(LinkStackNode));
LinkStack q2 = (LinkStack)malloc(sizeof(LinkStackNode));
p = S1;
q1 = S1->next;
q2 = S2->next;
while(q1 != NULL && q2 != NULL){
if(q1->data2 > q2->data2)
{
LinkStack temp = (LinkStack)malloc(sizeof(LinkStackNode));
temp->data1 = q2->data1;
temp->data2 = q2->data2;
p->next = temp;
temp->next = q1;
p = p->next;
q2 = q2->next;
}
else if(q1->data2 == q2->data2)
{
q1->data1 = q1->data1 + q2->data1;
if (q1->data1 == 0)
{
p->next = q1->next;
free(q1);
q1 = p->next;
q2 = q2->next;
}
else
{
q1 = q1->next;
q2 = q2->next;
p = p->next;
}
}
else
{
q1 = q1->next;
p = p->next;
}
}
if(q1==NULL)
{
p->next = q2;
}
printf("\n");
}
标签:q1,LinkStack,q2,LinkStackNode,多项式,next,链栈,加法,data2
From: https://www.cnblogs.com/wlb429/p/16756037.html