雙鏈表&鏈表合並&多項式相加算法

雙鏈表&鏈表合並&多項式相加算法

//單鏈表的合並

//鏈表合並
//兩個鏈表必須是有序的
#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<Maxsize;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<Maxsize;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) ;
}