首页 > 代码库 > 数据结构链表之 一元多次多项式

数据结构链表之 一元多次多项式

//尽量多声名几个指针 避免使用到 头节点 还有

/*

第一点 :初始化和建造链表放在一起了

且返回值用linklist类型

第二点:多项式相加是本质是链表的交集

交集需要注意的是(比较指数大小 小的放在新链表上 指针后移  如果那个表空了直接把

剩下的链到新链表)

 

 


#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
typedef struct n
{
int left;
int right;
}node;

typedef struct node1
{
node point;
struct node1 *next;
}lnode,*linklist;

 


linklist makeup(void)//注意一下这里
{
int n;
lnode *p,a,b,c,*s,*l;

l=(linklist)malloc(sizeof(lnode));
if(l==NULL)
{
printf("分配失败");
exit(-1);
}
l->next=NULL;
s=l;//注意这个 否者就会变成一个头节点指向周围一圈节点
printf("请输入节点个数(多项式的项数):" );
scanf("%d",&n);

for(int i=0;i<n;i++)
{
p=(linklist)malloc(sizeof(lnode));

if(p==NULL)
{
printf("分配失败");
exit(-1);
}

printf("请分别输入链表的系数和指数:");
scanf("%d %d",&p->point.left,&p->point.right);//我是大沙比 scanf取址符居然忘了;检查好久
s->next=p;
p->next=NULL;
s=p;
}

return l;

}


void display(lnode *l)
{
int i;
lnode *p;
p=l;
while(p->next!=NULL)
{
p=p->next;

printf("---|%d_%d|--",p->point.left,p->point.right);


}
cout<<endl;
}

linklist add(linklist a,linklist b)
{
linklist c,p,d,e,s;
c=(linklist)malloc(sizeof(lnode));
if(c==NULL)
{
printf("分配失败");
exit(-1);
}
p=c; d=a->next; e=b->next;
while(d!=NULL&&e!=NULL)
{
if(d->point.right > e->point.right)
{
p->next=e;
p=e;
e=e->next;
}
else if(d->point.right < e->point.right)
{
p->next=d;
p=d;
d=d->next;
}

else
{
d->point.left=d->point.left + e->point.left;
e=e->next;
}

if(d==NULL)
{
p->next=e;
}
else
{
p->next=s;
}
}

return c;
}

int len(linklist l)
{
linklist p;
p=l->next;
int count=0;
while(p!=NULL)
{
count++;
p=p->next;
}
return count;
}

int sort(linklist l)
{
linklist p,q;
node temp;
int i,j;
for(i=0,p=l->next;i<len(l)-1;i++,p=p->next)//记住不要写p->count 因为p->count==1
{
for(j=i+1,q=p->next;j<len(l);j++,q=q->next)

if(p->point.right > q->point.right)
{
temp=q->point;
q->point=p->point;
p->point=temp;
}
}
return 1;
}

int main()
{
int n,k;
lnode p, r,l ;
lnode *a,*b,*c;
a=(linklist)malloc(sizeof(lnode));
b=(linklist)malloc(sizeof(lnode));
c=(linklist)malloc(sizeof(lnode));

printf("链表一 :\n");
a=makeup();
sort(a);
display(a);
cout<<endl;

printf("链表二 : \n");
b=makeup();
display(b);


c=add(a,b);
printf("一元多次式的结果为:\n");
display(c);
return 0;
}

技术分享

 

数据结构链表之 一元多次多项式