文档库

最新最全的文档下载
当前位置:文档库 > 两个单链表求差集

两个单链表求差集

/******

//作者:cc

//功能:求A、B链表的差集

//日期:2012-05-12

*******/

#include

#include

//单链表类型定义

typedef struct node{

int data;

struct node *next;

}lnode,*linklist;

//创建有序非递减链表

linklist createlink(linklist l,int n)

{

int i=0;

linklist p,q,pre;

l=(linklist)malloc(sizeof(lnode));

l->next=0;

for(;i

pre=l;

p=l->next;

q=(linklist)malloc(sizeof(lnode));

printf("Input a element:");scanf("%d",&q->data);

while(p&&p->datadata){

pre=p;

p=p->next;

}

q->next=p;

pre->next=q;

}

return l;

}

//打印链表元素

void printlink(linklist l)

{

linklist p;

p=l->next;

printf("h->");

while(p)

{

printf("%d->",p->data);

p=p->next;

}

printf("next\n");

}

//返回链表的长度(元素个数)

int linklength(linklist l)

{

linklist p;

int count=0;

p=l->next;

while(p)

{

count++;

p=p->next;

}

return count;

}

//求A、B表的差集(差集,即仅由A中出现而不在B中出现的元素所构成的集合)

linklist link_difset(linklist la,linklist lb,int *e)

{

linklist pa,pb,lc,pc,s; //结点pa,pb,pc,lc,s

*e=0; //e用于表示A,B差集个数lc=la; //C表头结点利用A表的头结点

pa=la->next;pb=lb->next; //pa,pb分别指向A,B的首结点pc=lc; //pc指向C表的头结点

while(pa&&pb){ //pa,pb均不为空if(pa->data==pb->data){ //pa,pb结点的元素相等s=pa;pa=pa->next;free(s); //释放pa结点

(*e)++; //差集个数+1

while(pa&&(pa->data==pb->data)){ //除去重复的A表元素(前提是pa,pb结点的元素相等)

s=pa;pa=pa->next;free(s); //释放pa结点

(*e)++; //差集个数+1

}

}else if(pa->datadata){ //pa结点元素小于pb结点元素pc->next=pa;pc=pa;pa=pa->next; //A结点后移

}else{

s=pb;pb=pb->next;free(s); //B结点后移

}

}

if(!pa){ //pa结点不空

while(pb){

s=pb;pb=pb->next;free(s); //s释放剩余的pb结点}

pc->next=0; //pc->next=0尾结点

}else

pc->next=pa; //链接剩余的A表结点free(lb); //释放pb头结点

return lc; //返回表

}

void main()

{

linklist la,lb,lc;

int n,e;

printf("==================================创建递增链表==================================");

printf("A元素个数:");scanf("%d",&n); //输入A表元素个数

la=createlink(la,n); //创建A表

printlink(la); //打印A表元素

printf("A表长:%d\n",linklength(la)); //输出A表长

printf("B元素个数:");scanf("%d",&n); //输入B表元素个数

lb=createlink(lb,n); //创建B表

printlink(lb); //打印B表元素

printf("B表长:%d\n",linklength(lb)); //输出B表长

printf("=================================递增链表求差集=================================");

lc=link_difset(la,lb,&e); //C表用于保存A,B表的差集

printf("A,B差集个数:%d\n",e); //输出A,B表的差集个数

printlink(lc); //打印C表元素

printf("C表长:%d\n",linklength(lc)); //输出C表长

printf("=======================================End========== ============================");

}