一元多项式的计算问题,线性链表的典型应用.
本帖最后由 Be_envious 于 2011-8-20 03:10 编辑#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 发表于 2011-8-20 18:45 static/image/common/back.gif
多项式用数组更简洁哦
用数组要写动态二维数组
只是现在在学习线性链表
不过谢谢你的提议
学到数组的时候
写一个
Be_envious 发表于 2011-8-20 20:14 static/image/common/back.gif
用数组要写动态二维数组
只是现在在学习线性链表
不过谢谢你的提议
一维就够了，下标当指数，保存系数
wangyexin 发表于 2011-8-20 22:51 static/image/common/back.gif
一维就够了，下标当指数，保存系数
好办法学习了 不错啊！！！！！！！！！！！！！！！！！！！！！！ 如果用一维数组，下标存指数，指数跳跃很大时，会很浪费空间的啊，还是二维好点吧~
LZ的代码写得很清晰，很容易读懂~。~ 不错啊！！！！！！！！！！！！！！！！！！！！！！
页:
[1]