31、数据结构与算法实战:顺序表的删除

Description
已知A,B和C为三个非递减有序的线性表,现要求对A表作如下操作:删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法。

Input
第一行输入3个正整数m,n,p(m,n,p<=100),用空格分开,分别表示三个线性表中的元素个数,其后3行依次输入A,B,C表中的元素。

Output
输出实现上述操作后的A表。

Sample Input

85 6
12 3 4 5 6 6 7
23 5 9 12
24 5 6 12 13

Sample Output

13 4 6 6 7

参考程序

#include <stdio.h>
#include <stdlib.h>
#define LEN 100

void CreateList(int a[],int n)
{
   
     
	int i;
	a[0]=n;
	for(i=1;i<=n;i++)
	{
   
     
		scanf("%d",&a[i]);
	}
}

void OutputList(int a[])
{
   
     
	int i;
	if(!a[0])
	{
   
     
		return;
	}
	for(i=1;i<=a[0]-1;i++)
	{
   
     
		printf("%d ",a[i]);
	}
	printf("%d\n",a[i]);
}

void GetInter(int b[],int c[],int u[])
{
   
     
	int pb=1,pc=1;
	int top=1;
	u[0]=0;
	while(pb<=b[0] && pc<=c[0])
	{
   
     
		if(b[pb]<c[pc])
		{
   
     
			pb++;
		}
		else if(b[pb]>c[pc])
		{
   
     
			pc++;
		}
		else
		{
   
     
			if(top==1 || u[top-1]!=b[pb])
			{
   
     
				u[top++]=b[pb];
			}
			pb++;
			pc++;
		}
	}
	u[0]=top-1;
}

int Find(int a[],int key)
{
   
     
	if(!a[0])
	{
   
     
		return 0;
	}
	int low=1,high=a[0];
	while(low<=high)
	{
   
     
		int mid=(low+high)/2;
		if(a[mid]<key)
		{
   
     
			low=mid+1;
		}
		else if(a[mid]>key)
		{
   
     
			high=mid-1;
		}
		else
		{
   
     
			return 1;
		}
	}
	return 0;
}

void GetDiff_Search(int a[],int inter[],int res[])
{
   
     
	int pa,top=1;
	for(pa=1;pa<=a[0];pa++)
	{
   
     
		if(!Find(inter,a[pa]))
		{
   
     
			res[top++]=a[pa];
		}
	}
	res[0]=top-1;
}

int main()
{
   
     
	int A,B,C,a[LEN+5],b[LEN+5],c[LEN+5],inter[LEN+5],diff[LEN+5];
	
	scanf("%d%d%d",&A,&B,&C);
	CreateList(a,A);
	CreateList(b,B);
	CreateList(c,C);
	GetInter(b,c,inter);
	GetDiff_Search(a,inter,diff);
	OutputList(diff);
	
	return 0;
}
/*
4 4 4
1 2 3 4
1 2 3 4
1 2 3 4

4 4 4
1 1 1 1
1 2 3 4
5 6 7 8

8 6 6
1 2 2 4 5 6 6 8
1 1 2 2 6 6
2 4 5 6 6 7
*/

注意:
①顺序表b和c的交集可能为空集,所以顺序表a可能和空集做求差集运算;
②顺序表a经求差运算后可能得到空集。

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: