双链表&链表合并&多项式相加算法

//单链表的合并

//链表合并
//两个链表必须是有序的
#define Maxsize 5
typedef int elemtype;
typedef struct linklist
{
elemtype data;
struct linklist *next;
}Linklist;

//建立链表1
Linklist *CreateList1 ()
{
int i,data ;
Linklist *head, *p, *q;
head=p=(Linklist *)malloc(sizeof(Linklist));
p->next=NULL; //创建单链表的表头结点head

for(i=0;i {
data =2*i;
q= (Linklist *)malloc(sizeof(Linklist));
q->data=data;
q->next=p->next;
p->next=q;
p=q;
}
return (head);
}

//建立链表2
Linklist *CreateList2 ()
{
int i,data ;
Linklist *head, *p, *q;
head=p=(Linklist *)malloc(sizeof(Linklist));
p->next=NULL; //创建单链表的表头结点head

for(i=0;i {
data =2*i+1; //减10,两个链表不等
q= (Linklist *)malloc(sizeof(Linklist));
q->data=data;
q->next=p->next;
p->next=q;
p=q;

}
return (head);
}

int main()
{
linklist *La=CreateList1();
linklist *Lb=CreateList2();

linklist *Lc,*L1,*L2,*Lp;
Lc=(Linklist *)malloc(sizeof(Linklist));
Lc->next=NULL;
Lc->next=La->data < Lb->data La:Lb;
L1=La;
L2=Lb;
Lp=Lc;
while(L1->next!= NULL && L2->next!=NULL)
{
if(L1->data < L2->data )
{
Lp->next=L1;
L1=L1->next;
}
if(L1->data > L2->data )
{
Lp->next=L2;
L2=L2->next;
}
if(L1->data == L2->data )
{
Lp->next=L1;
L1=L1->next;
L2=L2->next;
}
}
if(L1->next= NULL)
Lp->next=L2;
else
Lp->next=L1;

while(1);
return 0;
}

//循环链表的条件： p->next=head;

//双向链表
ADT:
typedef struct dullinklist
{
elemtype data;
struct dullinklist *prior,*next;
}
ADP:
//添加一个结点：假设在p,q中间添加一个结点add：
dullinklist *add;
add=(dullinklist *)malloc(sizeof(dullinklist));
add.data=data;
p->next=add;
add->next=q;
q->prior=add
add->next=p;
//删除一个结点：

p->prior->next=p->next;
p->next->prior=p->prior;
free(p);

//线性表和链表的应用——多项式的加减法
1）线性表表示法：
typedef struct linearlist
{
elemtypefloat factor; //系数
elemtypeint series; //级数
}
多项式的每一项都由级数和系数唯一确定，但是对于某些系数为0的项，会占用内存浪费资源
因此使用链表

2）链表表示法
typedef struct linklist
{
elemtypefloat factor; //系数
elemtypeint series; //级数
struct linearlist *next；
}
3)多项式相加：两个链表合并，系数为0的项删掉
linklist *add(linklist *la,linklist *lb)
{
linklist *lc,*pc,*pa,*pb,*flag;
lc=(linklist *)malloc(sizeof(linklist));
pc=(linklist *)malloc(sizeof(linklist));
pa=(linklist *)malloc(sizeof(linklist));
pb=(linklist *)malloc(sizeof(linklist));

lc=pc;
lc->next=pa;
pa=la;
pb=lb;
while(pa->next!=NULL && pb->next!=NULL)
{
if(pa->series < pb=series)
{
pc-next=pa;
pc=pa;
pa=pa-next;
}
if(pa->series > pb->series)
{
pc-next=pb;
pc=pb;
pb=pb-next;
}
if(pa->series = pb->series)
{
elemtype x=pa->factor+pb->factor;
if(x<=1e-6)
{
flag=pa;
pa=pa->next;
pb=pb->next;
free(pa);
free(pb);
}
else
{
pc->factor=x;
pc-next=pa;
pc=pa;
pa=pa-next;
flag=pb;
pb=pb->next;
free(pb);
}
}
}
if(pa==NULL)
pc->next=pb ;
else
pc->next=pa ;
return (Lc) ;
}