一元多项式的计算问题,线性链表的典型应用.

Be_envious

#include<stdio.h>
#include<malloc.h>
//需注意的是 多项式加法默认的是 幂指数从小大依次排列 输入幂指数时应注意
//只是练习题,所以没有更深入的对多项式进行幂指数整理升序排序
//目的只是学会线性链表在多项式上的应用 
struct polynomial
//polynomial 中文意思 多项式 起这么长的名字其实是为了顺便学学英语 
{
int coefficient; //coefficient 系数 
int index; //index 指数 
struct polynomial * next; //多项式后继指针 
};

struct polynomial * creat(void); //创建函数 
//多项式相加函数 
struct polynomial * plus(struct polynomial * an,struct polynomial * bn); 
void print(struct polynomial * P);
int main(void)
{
struct polynomial * an = NULL;
struct polynomial * bn = NULL;
struct polynomial * cn = NULL;

an = creat();
bn = creat();
cn = plus(an,bn);
print(cn);
system("pause");
}

//创建函数 
struct polynomial * creat(void)
{
//分配一个没有数据的空间给头结点,这个很重要 
struct polynomial * head = (struct polynomial *)malloc(sizeof(struct polynomial));
if(NULL == head)
{
printf("No enough space!");
exit(-1);
}

struct polynomial * tail = head;
tail->next = NULL;

int NUMBER_OF_TERMS;
int coefficient;
int index;
int loop;

printf("Input number of terms: ");
scanf("%d",&NUMBER_OF_TERMS);

for(loop = 0;loop < NUMBER_OF_TERMS;++loop)
{
printf("\nInput coefficient of No.%d term: ",loop+1);
scanf("%d",&coefficient);
printf("Input index of No.%d term: x^",loop+1);
scanf("%d",&index);

struct polynomial * GENERAL_TERM = (struct polynomial *)malloc(sizeof(struct polynomial));
if(NULL == GENERAL_TERM)
{
printf("no enough space!");
exit(-1);
}
GENERAL_TERM->coefficient = coefficient;
GENERAL_TERM->index = index;

tail->next = GENERAL_TERM;
GENERAL_TERM->next = NULL;
tail = GENERAL_TERM;
}
return (head);
}

//多项式相加函数 
struct polynomial * plus(struct polynomial * an,struct polynomial * bn)
{
struct polynomial * pointer_a = an->next;
struct polynomial * pointer_b = bn->next;

//这里很重要 
struct polynomial * cn = (struct polynomial *)malloc(sizeof(struct polynomial));
if(NULL == cn)
{
printf("No enough space!");
exit(-1);
} 
struct polynomial * pointer_c = cn;

while(pointer_a && pointer_b)
{
struct polynomial * pointer_a_plus_b = (struct polynomial *)malloc(sizeof(struct polynomial));
if(NULL == (pointer_a_plus_b))
{
printf("No enough space!");
exit(-1);
}
if(pointer_a->index < pointer_b->index)
{
pointer_a_plus_b->coefficient = pointer_a->coefficient;
pointer_a_plus_b->index = pointer_a->index;
pointer_a = pointer_a->next;

pointer_c->next = pointer_a_plus_b;
pointer_a_plus_b->next = NULL;
pointer_c = pointer_a_plus_b;
}
else if(pointer_a->index == pointer_b->index)
{
pointer_a_plus_b->coefficient = pointer_a->coefficient + pointer_b->coefficient;
pointer_a_plus_b->index = pointer_a->index;
pointer_a = pointer_a->next;
pointer_b = pointer_b->next;

pointer_c->next = pointer_a_plus_b;
pointer_a_plus_b->next = NULL;
pointer_c = pointer_a_plus_b;
}
else
{
pointer_a_plus_b->coefficient = pointer_b->coefficient;
pointer_a_plus_b->index = pointer_b->index;
pointer_b = pointer_b->next;

pointer_c->next = pointer_a_plus_b;
pointer_a_plus_b->next = NULL;
pointer_c = pointer_a_plus_b;
}
}

if(pointer_a == NULL)
{
while(pointer_b)
{
struct polynomial * pointer_a_plus_b = (struct polynomial *)malloc(sizeof(struct polynomial));
if(NULL == pointer_a_plus_b)
{
printf("No enough space");
exit(-1);
}

pointer_a_plus_b->coefficient = pointer_b->coefficient;
pointer_a_plus_b->index = pointer_b->index;
pointer_b = pointer_b->next;

pointer_c->next = pointer_a_plus_b;
pointer_a_plus_b->next = NULL;
pointer_c = pointer_a_plus_b;
}
}
else
{
while(pointer_a)
{
struct polynomial * pointer_a_plus_b = (struct polynomial *)malloc(sizeof(struct polynomial));
if(NULL == pointer_a_plus_b)
{
printf("No enough space!");
exit(-1);
}

pointer_a_plus_b->coefficient = pointer_a->coefficient;
pointer_a_plus_b->index = pointer_a->index;
pointer_a = pointer_a->next;

pointer_c->next = pointer_a_plus_b;
pointer_a_plus_b = NULL;
pointer_c = pointer_a_plus_b;
}
}
return (cn);
}

//打印输出函数 
void print(struct polynomial * P)
{
int total_terms = 0;
struct polynomial * pointer = P->next;
while(pointer)
{
if(total_terms != 0)
{
printf("+");
}
printf("%dx^%d",pointer->coefficient,pointer->index);
pointer = pointer->next;
++total_terms;
}
printf("\nTotal terms : %d\n",total_terms);
}

希望大家多多交流,有不足之处望指出,日后写的代码都会完全共享,希望大家给予支持.

wangyexin

多项式用数组更简洁哦

Be_envious

wangyexin 发表于 2011-8-20 18:45

                               
登录/注册后可看大图

多项式用数组更简洁哦

用数组要写动态二维数组
只是现在在学习线性链表
不过谢谢你的提议
学到数组的时候
写一个

wangyexin

Be_envious 发表于 2011-8-20 20:14

                               
登录/注册后可看大图

用数组要写动态二维数组
只是现在在学习线性链表
不过谢谢你的提议

一维就够了，下标当指数，保存系数

Be_envious

wangyexin 发表于 2011-8-20 22:51

                               
登录/注册后可看大图

一维就够了，下标当指数，保存系数

好办法  学习了  

tantrong

不错啊！！！！！！！！！！！！！！！！！！！！！！

Davishu

如果用一维数组，下标存指数，指数跳跃很大时，会很浪费空间的啊，还是二维好点吧~
LZ的代码写得很清晰，很容易读懂~。~

□_谁_□_枫_□

不错啊！！！！！！！！！！！！！！！！！！！！！！