已知递增有序的两个单链表A和B分别存储一个集合，设计程序实现两个集合的交集运算A=A∩B。
//伪代码
struct node *pA = pListAHead; //有序列表A
struct node *pB = pListBHead; //有序列表B
struct node *pCHead = NULL; //A与B交集头
struct node *pCEnd = NULL; //A与B交集尾
while (pA != NULL && pB != NULL)
{
if (pA->value == pB->value)
{
//相等，同时后移
if (pCEnd == NULL)
{
pCHead = new node();
pCHead->value = pA->value;
pCHead->next = NULL;
pCEnd = pCHead;
}
else
{
pCEnd->next = new node();
pCEnd = pCEnd->next;
pCEnd->next = NULL;
pCEnd->value = pA->value;
}
pA = pA->next;
pB = pB->next;
continue;
}
else if (pA->value > pB->value)
{
//最小的相比，B小 B后移
pB = pB->next;
continue;
}
else
{
//最小的相比，A小 A后移
pA = pA->next;
}
}
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct Lnode
{
ElemType date;
struct Lnode* next;
}*LNode;
LNode InitLnode(void) //初始化链表
{
LNode L;
L = (LNode)malloc(sizeof(struct Lnode));
if(L == NULL)
exit(1);
L->next = NULL;
return L;
}
/*尾插入元素*/
void Insert(LNode head,ElemType x)
{
struct Lnode *p,*q;
p = head;
q = (LNode)malloc(sizeof(struct Lnode));
if(!q)
{
printf("Out of space\n");
exit(1);
}
q->date = x;
q->next = NULL;
while(p->next != NULL) //带头结点的链表
{
p = p->next;
}
p->next = q;
}
/*输出链表*/
void Print(LNode head)
{
LNode p;
p = head->next;
while(p!=NULL)
{
printf("%d ",p->date);
p = p->next;
}
}
int IfHas(LNode L,ElemType x)
{
LNode p = L->next;
if(!L)
exit(1);
while(p)
{
if(p->date == x)
return 1;
p = p->next;
}
return 0;
}
void REORDER(LNode LA,LNode LB,LNode LC)
{
LNode p;
p = LA->next;
while(p)
{
if(IfHas(LB,p->date))
Insert(LC,p->date);
p = p->next;
}
}
/*测试一下*/
int main(void)
{
LNode LA,LB,LC;
LA = InitLnode();
LB = InitLnode();
LC = InitLnode();
ElemType N;
printf("输入你要放入链表LA中的数据，输入为零是代表输入结束\n");
while(scanf("%d",&N)!=EOF)
{
if(N == 0)
break;
Insert(LA,N);
}
printf("输入你要放入链表LB中的数据，输入为零是代表输入结束\n");
while(scanf("%d",&N)!=EOF)
{
if(N == 0)
break;
Insert(LB,N);
}
printf("LA,LB分别为：\nLA:");
Print(LA);
printf("\nLB:");
Print(LB);
REORDER(LA,LB,LC);
printf("\nLC:");
Print(LC);
printf("\n");
return 0;
}
|
广告 您可能关注的内容 |
