|
如何使用
 顺序链表没有实现求积只有求和，单向链表实现了求和以及求积。所以建议用单向链表的实现代码。 代码里面封装了两个一元多项式求和和求积的函数，调用编译运行就行。 先输入非常数项，再输入常数项，比如上面的输入就代表了 2x^3 + 3x^5 + 6x^6 + 9这个一元多项式。暂时不支持系数为负数，指数可以是负数。
运行结果
 上图就代表了两个一元多项式求积。
顺序链表实现
#include
#include
#include
#define MAX 99
typedef struct list //顺序结构链表结构体
{
double arr[MAX];
int first; //指向了一元多项式的第一项的系数的下标
int last; //指向了下一个要增加的项的系数的下标
int constsub; //指向了常数项元素的下标
} LIST;
/************************************顺序结构链表函数声明***********************************/
LIST * create_polynomial_list();//创建一个一元多项式顺序链表
LIST * select_polynomial_data(LIST *str);//设置一个一元多项式的数据
LIST * polynomial_sum(LIST *str, LIST *ptr);//求和，结果保存在str
int printf_list(LIST *str); //打印这个顺序链表
void display_polynomial(); //创建一个一元多项式并打印
void set_polynomial_sum(); //创建两个一元多项式顺序链表，并求和之后打印
/************************************顺序结构链表函数声明 end*******************************/
int main(void)
{
return 0;
}
/********************************顺序结构链表函数定义*********************************/
//创建一个一元多项式顺序链表
LIST * create_polynomial_list()
{
LIST *ptr = (LIST *)malloc(sizeof(LIST));
memset(ptr->arr, 0, sizeof(ptr->arr)); //将数组arr内的元素全部填充为0
ptr->first = 0;
ptr->last = 0;
ptr->constsub = MAX - 1; //常数项固定放在arr最后一个元素arr[MAX-1]中。
return ptr;
}
//设置一个一元多项式的数据
LIST * select_polynomial_data(LIST *str)
{
printf("请输入每个项的系数和指数\n");
printf("输入形式为：x y，输入指数为0则代表结束输入且进入常数项的输入\n");
double coefficient = 0; //系数
double index = 0; //指数
double constnum = 0; //常数项
while(1) {
scanf("%lf%lf",&coefficient,&index);
if(0 == index) //输入指数为0，则退出此循环并进去常数项输入
break;
if(-1 == str->last) //除了常数项之外，已经存满了，强行进入常数项输入
break;
str->arr[str->last] = coefficient; //赋值
str->arr[str->last + 1] = index;
str->last += 2; //last后移，指向下一项增加的位置的下标
if(str->last == MAX-1) //指向了常数项元素的下标
str->last = -1;
}
printf("请输入常数项\n");
scanf("%lf",&constnum);
str->arr[str->constsub] = constnum;
return str;
}
//str和ptr指向的链表的一元多项式的求和
//最终结果会保存在str指向的那个链表中
LIST * polynomial_sum(LIST *str, LIST *ptr)
{
//先算常数项
str->constsub += ptr->constsub;
int StrFirst = str->first; //辅助循环
int PtrFirst = ptr->first; //辅助循环 str->first 和 ptr->first 的值其实就是0
//PtrFirst代表准备相加项的系数的下标
while(0 != ptr->arr[PtrFirst]) { //等于0则代表相加完毕
while(StrFirst != ptr->last) { //查找完毕，退出
if(str->arr[StrFirst+1] == ptr->arr[PtrFirst+1]) { //找到了指数相等的项
str->arr[StrFirst] += ptr->arr[PtrFirst]; //系数相加
break;
}
StrFirst += 2;
}/*内while*/
if(StrFirst == ptr->last) { //代表没有找到相等的项，那么就将此项加入str指向的一元多项式后面
if(str->last == MAX-1) {
printf("已经保存不下多余的项，请增加MAX的值再次尝试\n");
exit(-1);
}
str->arr[ptr->last] = ptr->arr[PtrFirst];
str->arr[ptr->last + 1] = ptr->arr[PtrFirst+1];
str->last += 2;
}
StrFirst = 0;//置0，便于下次循环比较
PtrFirst += 2; //继续对ptr链表中的下一项进行相加
}/*外while*/
return str;
}
//打印这个链表，以一元多项式的方式
int printf_list(LIST *str)
{
int print = 0; //从第一项开始打印
int flag = 1;//一元多项式是否只有常数项的标志
int i = 0;
//开始打印
while(print != str->last) {
if(str->arr[print] > 0) { //系数大于0
flag = 0; //代表不止有常数项
if((0 == print) || (0 == i)) //第一项
printf("%.2lfx^%.2lf",str->arr[print],str->arr[print+1]);
else
printf(" + %.2lfx^%.2lf",str->arr[print],str->arr[print+1]);
i = 1;
}
else if(str->arr[print]
if(1 == flag) //只有常数项
printf("%.2lf\n",str->arr[str->constsub]);
else
printf(" + %.2lf\n",str->arr[str->constsub]);
}
return 0;
}
//创建一个一元多项式并打印
void display_polynomial()
{
LIST * p = create_polynomial_list();//创建一个一元多项式顺序链表
select_polynomial_data(p);//设置一个一元多项式的数据
printf_list(p);
}
//创建两个一元多项式顺序链表，并求和之后打印
void set_polynomial_sum()
{
LIST * p = create_polynomial_list();//创建一个一元多项式顺序链表
LIST * p2 = create_polynomial_list();//创建一个一元多项式顺序链表
select_polynomial_data(p);//设置一个一元多项式的数据
select_polynomial_data(p2);//设置一个一元多项式的数据
polynomial_sum(p, p2); //求和
printf_list(p);
}
/******************************顺序结构链表函数定义 end*********************************/
单向链表实现
#include
#include
#include
/*vvvvvvvvvvvvvvvvvvvvvvvvvvv链式结构单向链表vvvvvvvvvvvvvvvvvvvvvvvvvvvv*/
/*
每一个结点保存了一元多项式每一项的系数和指数，且最后一个结点保存了常数项的值
功能：实现一元多项式的求和，求积
*/
typedef struct list2 //链式结构单向链表结构体
{
double Coeff; //系数
double Index; //指数
struct list2 * next;//指向下一个结点
} LIST_2;
/********************************链式结构链表函数声明**********************************/
LIST_2 * CreateSelectPolyData(); //创建并设置数据
int PrintfList(LIST_2 *str); //打印这个链表
LIST_2 * PolynomialSum(LIST_2 *str, LIST_2 *ptr); //求和
LIST_2 * PolyMultiplicate(LIST_2 *str, LIST_2 *ptr); //求积
void DisplayPolynomial(); //创建一个链式链表并以一元多项式的方式打印
void SetPolynomialSum();//创建两个链式链表求和之后以一元多项式的方式打印
void SetPolynomialMult();//创建两个链式链表求积之后以一元多项式的方式打印
/********************************链式结构链表函数声明 end******************************/
int main(void)
{
system("chcp 65001");
return 0;
}
/******************************链式结构链表函数定义*************************************/
//创建并设置数据
LIST_2 * CreateSelectPolyData()
{
double coefficient = 0; //系数
double exponent = 0; //指数
LIST_2 *first = NULL;
LIST_2 *last = NULL;
printf("请输入系数和指数，以x(系数) y(指数)的形式，输入指数为0时则系数的值就是常数项的值\n");
while(1) {
scanf("%lf%lf",&coefficient, &exponent);
LIST_2 *p = (LIST_2 *)malloc(sizeof(LIST_2));
p->Coeff = coefficient; //赋值
p->Index = exponent;
p->next = NULL;
if(NULL == first) { //输入的还是第一个结点
first = p;
last = p;
}
else {
last->next = p;
last = p;
}
if(0 == exponent) //如果指数为0，则代表这次输入的是常数项，退出循环
break;
}/*while*/
return first; //返回头结点的指针
}
//打印这个链表
int PrintfList(LIST_2 *str)
{
int i = 0; //特殊情况标志变量
LIST_2 *ptr = str; //代替str循环
int flag = 1; //一元多项式是否只有常数项的标志
while(ptr->next != NULL) { // ptr->next 等于NULL 即ptr指向最后一个结点的时候退出循环
if(ptr->Coeff > 0) {//系数大于0
flag = 0;
if((ptr == str) || (0 == i)) //第一项
printf("%.2lfx^%.2lf",ptr->Coeff, ptr->Index);
else
printf(" + %.2lfx^%.2lf",ptr->Coeff, ptr->Index);
i = 1;
}
else if(ptr->Index
if(1 == flag) //有且只有常数项
printf("%.2lf\n",ptr->Coeff);
else
printf(" + %.2lf\n",ptr->Coeff);
}
else if(ptr->Coeff Coeff * -1));
//等于0则不打印常数项
return 0;
}
//求和，找到指数相等的就系数直接相加，否则就当成一个新项插入目标链表中
LIST_2 * PolynomialSum(LIST_2 *str, LIST_2 *ptr)
{
//先加其他项
LIST_2 *s = NULL; //代替str循环
while(ptr->next != NULL) { //当ptr指向了最后一个结点时，跳出循环开始常数项的相加
s = str;
while(s->next != NULL) { //当s指向了链表最后一个结点(保存了常数项的结点)的时候会跳出循环
if(s->Index == ptr->Index) {//找到了指数相等的
s->Coeff += ptr->Coeff; //系数直接相加即可
break;
}
s = s->next; //比较下一项
}/*while*/
if(NULL == s->next) {//说明没找到指数相等的，此时s指向了str的最后一个结点
//为了方便，我们直接增加一个结点到str最后一个结点和倒数第二个结点之间
LIST_2 *p = (LIST_2 *)malloc(sizeof(LIST_2));
LIST_2 *t = str;
p->Coeff = ptr->Coeff;
p->Index = ptr->Index;
p->next = NULL;
while(t->next != s) //将t指向str倒数第二个结点
t = t->next;
//开始连接
t->next = p;
p->next = s;
}
ptr = ptr->next; //后移一位，继续判断相加
}/*while*/
//常数项相加
while(s->next != NULL) //将s指向str链表的最后一个结点
s = s->next;
s->Coeff += ptr->Coeff;
}
//求积
/*
将ptr链表中的结点依次与str的结点相乘，每一个乘积项都放入一个新的链表，
//然后对其化简(即合并同类项)得出最终结果
*/
LIST_2 * PolyMultiplicate(LIST_2 *str, LIST_2 *ptr)
{
LIST_2 *nfirst = NULL;
LIST_2 *nlast = NULL;
LIST_2 *s = str;
while(ptr != NULL) {
s = str; //s重新指向str链表的第一个结点
while(s != NULL) { //将ptr指向的的一个结点和str链表中的所有结点依次相乘并且放入新链表中
LIST_2 *p = (LIST_2 *)malloc(sizeof(LIST_2));
p->next = NULL;
if((0 == ptr->Index) && (0 != ptr->Coeff)) { //指数是0且系数不为0，代表ptr指向的结点是常数项
p->Coeff = s->Coeff * ptr->Coeff; //只需系数相乘
p->Index = s->Index; //指数无需乘，直接赋值即可，如果是两个常数项相乘，那么s->Index的值就是0
}
else { //不是常数项该怎么乘就怎么乘
p->Coeff = s->Coeff * ptr->Coeff; //系数相乘
p->Index = s->Index + ptr->Index; //指数相加
}
if(NULL == nfirst) { //新链表中还没有结点
nfirst = p;
nlast = p;
s = s->next; //s右移，继续相乘
continue; //所以无需判断是否需要化简
}
LIST_2 *nfp = nfirst; //代替nfirst循环
//此时新链表中已经有结点，我们在插入新乘积项的时候就要先判断是否存在同类型，有则化简
//没有则放在新链表后面
while(nfp != NULL) {
if(nfp->Index == p->Index) {//存在同类型
nfp->Coeff += p->Coeff;
break; //跳出while循环
}
nfp = nfp->next;
} /*while*/
if(NULL == nfp) { //说明在新链表中没有找到同类项，需要插入在链表最后面
nlast->next = p; //开始连接结点
nlast = p;
}
s = s->next; //s指向下一个结点，继续相乘
}/*while*/
ptr = ptr->next; //ptr指向下一个结点，继续相乘
}/*while*/
return nfirst; //返回新链表的头节点的指针，答案保存在这个新链表中
}
//创建一个链式链表并以一元多项式的方式打印
void DisplayPolynomial()
{
LIST_2 * p = CreateSelectPolyData();
PrintfList(p);
}
//创建两个链式链表求和之后以一元多项式的方式打印
void SetPolynomialSum()
{
LIST_2 * p = CreateSelectPolyData();
LIST_2 * p2 = CreateSelectPolyData();
PolynomialSum(p, p2);
PrintfList(p);
}
//创建两个链式链表求积之后以一元多项式的方式打印
void SetPolynomialMult()
{
LIST_2 * p = CreateSelectPolyData();
LIST_2 * p2 = CreateSelectPolyData();
LIST_2 * nptr = PolyMultiplicate(p, p2); //求积，nptr用于指向新链表的头结点
PrintfList(nptr);
}
/******************************链式结构链表函数定义 end ********************************/
|