《数据结构》2.4求两个递增链表的差集

前端之家收集整理的这篇文章主要介绍了《数据结构》2.4求两个递增链表的差集前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

2.4求连个递增来表的差集

题目描述:

已知A和B表是两个集合,其元素的值递增排列;设计一个算法,求A和B的差集,
(即出现在A中但是不在B中) 结果放在A中,同时返回元素的个数。


算法思想:

需要设置三个指针,pa,pb,pc;初始时,pa指向L1的第一个结点,pb指向第二个结点,pc指向L3求得头结点,L3=L1,即使用L1的头结点当做新链表L3的头结点。当pa和pb都非空时,比较两个指针所指向的元素的值:1.当pa->data<pb->data时,说明当前pa所指向的元素值在L1中,此时令pc=pa,pb不变,pa向后移动,pa=pa->next;2.当pa->data>pb->data时,说明pb所指向的元素在L2中,而不在L1中,则pa指针保持不变,pb后移,pb=pb->next;3.当pa->data==pb->data时,说明pa和pb所指向的是L1和L2的公共元素,则需要改变pc的指向,pa也啊哟后移,pc->next=pa->next,pa=pa->next。


void DiffSet(LinkList &L1,LinkList &L2,LinkList &L3){
	struct LNode *pa,*pb,*pc;
	pa=L1->next;
	pb=L2->next;
	pc=L3=L1;
	
	while(pa&&pb){
		if(pa->data<pb->data){
			pc=pa;
			pa=pa->next;
		}else if(pa->data>pb->data){
			//pc=pa;
			pb=pb->next;
		}else if(pa->data==pb->data){
//			pc=pa;
//			pa=pa->next;
//			pb=pb->next;
//			pc=pa;
			pc->next=pa->next;
			pa=pa->next;
		}
	}
}



具体实现:


/*
已知A和B表是两个集合,其元素的值递增排列;设计一个算法,求A和B的差集,
(即出现在A中但是不在B中) 结果放在A中,同时返回元素的个数。 
*/
#include<stdio.h>
#define MAX 100

typedef struct LNode {
	int data;
	struct LNode *next;
}LNode,*LinkList;

int InitList(LinkList &L){
	L=new LNode;
	L->next=NULL;
	return 1;
}

int ListLength(LinkList &L){
	struct LNode *p;
	p=L->next;
	int length=0;
	while(p){
		++length;
		p=p->next;
	}
	return length;
}

void TraveList(LinkList L){
	struct LNode *p;
	p=L->next;
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

void CreateList(LinkList &L,int n){
	L=new LNode;
	L->next=NULL;
	struct LNode *r;
	r=L;
	for(int i=0;i<n;i++){
		printf("请输入第%d个元素的值:",i+1);
		struct LNode *s;
		s=new LNode;
		scanf("%d",&s->data);
		s->next=NULL;
		r->next=s;
		r=s;
	}
}

void DiffSet(LinkList &L1,*pc;
	pa=L1->next;
	pb=L2->next;
	pc=L3=L1;
	
	while(pa&&pb){
		if(pa->data<pb->data){
			pc=pa;
			pa=pa->next;
		}else if(pa->data>pb->data){
			//pc=pa;
			pb=pb->next;
		}else if(pa->data==pb->data){
//			pc=pa;
//			pa=pa->next;
//			pb=pb->next;
//			pc=pa;
			pc->next=pa->next;
			pa=pa->next;
		}
	}
}
int main(){
	LinkList L1,L2,L3;
	
	if(InitList(L1)){
		printf("L1初始化成功!\n");
	}else{
		printf("L1初始化失败!\n");
	}
	
	if(InitList(L2)){
		printf("L2初始化成功!\n");
	}else{
		printf("L2初始化失败!\n");
	}
	
	if(InitList(L3)){
		printf("L3初始化成功!\n");
	}else{
		printf("L3初始化失败!\n");
	}
	
	printf("请输入L1的长度:");
	int n1;
	scanf("%d",&n1);
	CreateList(L1,n1);
	TraveList(L1);
	
	printf("请输入L2的长度:");
	int n2;
	scanf("%d",&n2);
	CreateList(L2,n2);
	TraveList(L2);
	
	DiffSet(L1,L3);
	TraveList(L3);
	printf("差集的元素个数:%d",ListLength(L3)); 
}

原文链接:https://www.f2er.com/datastructure/382534.html

猜你在找的数据结构相关文章