c語言求交集演算法

1. 如何用C語言編寫求交集和並集的程序

char c[20];//存儲交集的字元int count=0;//統計交集個數for (n=1;n<j;n++)
for (m=1;m<=k;m++)
{
if(a[n]==b[m]) { c[count]=a[n]; count++; }
}
} c[count]='\0';printf("交集為%s",c);

2. 求C語言描述的,用線性表的,求交集的演算法

先排序兩個先行表，然後去除重復項。
從一個表(a)第一項開始，為關鍵字掃描另一個表(b)，找一個與其相等的，如果找到，那麼在b表之前的項也不會是a表中的項了，然後從a表下一項作關鍵字，從b表被匹配的元素的下一項開始繼續搜索，如果沒有找到與a中第一項相等的，到遇到比該項大的項時，便從a中下一項開始，重復以上步驟。

排序就不說了，好多種，冒泡，快排，插入，二分插入都行。去除重復項，可以用以下演算法
void StripRepeatElement(int Array[],int Arraylen)
{
int Count = 0;//重復計數器
int i;

for(i = 0;i < ArrayLen;i++)
{
if(Array[i] == Array[i + 1])
{
Count++;
}
else
{
Array[i - Count] = Array[i];
}
}
}
復雜度為O(n)
以下為求交集的演算法，假設兩個表都已經排過序和剔出重復項了
void GetIntersection(int A[],int Alen,int B[],int Blen)
{
int i = 0,j = 0;

while(i < Alen)
{
while(j < Blen)
{
if(A[i] == B[j])
{
//交集
printf(" %d ",A[i]);
j++;
break;
}
else if(A[i] < B[j])
{
//從A的下一項開始匹配
break;
}
else
{
//比較B的下一項
j++;
}
}
i++;
}
}
復雜度也為O(n)

3. C語言編程，輸入兩個數列，求交集！

#include<stdio.h>
#include<stdlib.h>

int main()
{
int i,j,k,len=0,a[10],b[10],c[10];

for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<10;i++)
{
scanf("%d",&b[i]);
}
for(i=0;i<10;i++)
{
for(k=0;k<len;k++)
{
if(a[i]==c[k])
{
break;
}
}
if(k>=len)
{
for(j=0;j<10;j++)
{
if(a[i]==b[j])
{
c[len++]=a[i];
break;
}
}
}

}
for(i=0;i<len;i++)
{
printf("%d ",c[i]);
}
printf("\n");
return 0;
}

4. 如何寫一個c語言程序求兩個集合的交集

定義兩個數組存放這兩個集合，再定義一個數組存放它們的集合，用類似冒泡排序的演算法，遍歷數組1中的第一個元素和數組2中每一個元素，若有相同的，則把這個元素放入第三個數組，繼續遍歷，知道數組1遍歷完所有元素，那數組3中的元素，即為兩個數組(集合)的交集。

5. c語言求交集編程

程序如下（TC2.0下運行通過）：
#include <stdio.h>
#include <alloc.h>

#define SET_TYPE unsigned char /*集合所用數據類型*/
#define SET_END 0xff /*集合結束符*/
#define SET_NUM 3 /*集合個數*/

SET_TYPE A[] = {1,2,3,4,5,9,8,6,0,SET_END};
SET_TYPE B[] = {3,4,5,6,7,10,11,22,SET_END};
SET_TYPE C[] = {2,3,5,6,7,9,20,SET_END};

SET_TYPE *pSets[SET_NUM] = {A,B,C};

long setSize(const SET_TYPE *pset);
void insertSort(SET_TYPE *BigSet,const SET_TYPE *SmallSet);
main()
{
SET_TYPE *AuBuC;
long element_num=0;
long i;
long j;
int sameFlag=0;
int sameNum=0;
clrscr();
for(i=0;i<SET_NUM;i++){/*得到所有集合元素數總和*/
element_num+=setSize(pSets[i]);
}
AuBuC = (SET_TYPE *)malloc(sizeof(SET_TYPE)*(element_num+1));
for(i=0;i<element_num+1;i++){
AuBuC[i] = SET_END;
}
for(i=0;i<SET_NUM;i++){/*插入法排序*/
insertSort(AuBuC,pSets[i]);
}
for(i=0;i<element_num;i++){
printf("%d ",AuBuC[i]);
}
printf("\n");
for(i=0;i<element_num;i++){
if(AuBuC[i]==AuBuC[i+1]){
if(sameFlag==1){
sameNum++;
}else{
sameNum=1;
sameFlag=1;
}
}else{
sameNum=0;
sameFlag=0;
}
if(sameNum==SET_NUM-1){
for(j=0;j<SET_NUM;j++){
AuBuC[i-sameNum+1+j]=SET_END;
}
}
}
for(i=0;i<element_num;i++){
if(AuBuC[i]!=AuBuC[i+1]&&AuBuC[i]!=SET_END){
printf("%d ",AuBuC[i]);
}
}
free(AuBuC);
}

long setSize(const SET_TYPE *pset)/*得到集合元素個數*/
{
long i=0;
while(pset[i++]!=SET_END){
i=i;
}
return i-1;
}

void insertSort(SET_TYPE *BigSet,const SET_TYPE *SmallSet)
{
long i=0;
long j;
long k;
while(SmallSet[i]!=SET_END){
j = 0;
while(BigSet[j]!=SET_END && BigSet[j]<SmallSet[i]){/*從小到大排序*/
j++;
}
if(BigSet[j]==SET_END){
BigSet[j] = SmallSet[i];
}else{/*BigSet[j]>=SmallSet[i]*/
k = j;
while(BigSet[j++]!=SET_END);
while(j>k){
BigSet[j] = BigSet[j-1];
j--;
}
BigSet[k] = SmallSet[i];
}
i++;
}
}

自己弄的。。。

6. 如何用C語言編寫求交集和並集的程序求解

scanf ("%s",a);
j=strlen(a);
printf ("請輸入第二個集合內容\n");
scanf ("%s",b);
k=strlen(b);
printf ("集合的交集是："); ///////////////////////計算2個數組的交集//////////////////// //flag標志位,index數組下標標志位 int flag=1, index=0; //c[20]保存交集的數組，d[40]保存並集的數組
char c[20]="",d[40]="";
for (n=0;n<j;n++){for (m=0;m<=k;m++){if(a[n] == b[m]){c[index++] = a[n];break;}}}printf("\n%s\n",c); ////////////////////////////計算2個數組的並集/////////////////////// flag=1;index=0;for (n=0;n<j;n++){for(m=0;m<index;m++){if(d[m] == a[n])flag=0;}if(flag){d[index++]=a[n];}flag=1;}flag=1;for (n=0;n<j;n++){for(m=0;m<index;m++){if(d[m] == b[n])flag=0;}if(flag){d[index++]=b[n];}flag=1;} printf ("集合的並集是：");

7. C語言怎麼用函數求集合的交集

首先，如果是數學上的集合概念，那就說明，集合A自身的每個元素都不相同。
那麼，程序就可以簡化成，
設數組key[52]，用於記錄字母出現次數。
掃描一次集合A，把出現的字母計到key的對應位置里。
同理掃描一次集合B。
查看key數組，>=2的對應字母輸出到集合C，C就是所求交集。

8. c語言求兩個數組的並交集

只簡單地分析了一下交集的情況，求並集類似。網路知道這個代碼支持不怎麼好，復制粘貼到 vs 之類的代碼編輯器裡面縮進一下會比較好看。

見代碼如下：

#include <stdio.h>

#include <stddef.h>

#include <stdlib.h>

#include <time.h>

// 使用整型數組為例，其它數組同理

// 交集

// 通過迭代遍歷判斷相同元素，時間復雜度較高，平方量級

// 傳入原數組及其長度、結果數組

// 返回結果數組的長度

// （需要自行保證結果數組足夠大）

size_t getIntersection(array1, array1_len, array2, array2_len, result_array)

int* array1, * array2, * result_array;

size_t array1_len, array2_len;

{

size_t result_p = 0;

for (size_t i = 0; i < array1_len; ++i)

{

for (size_t j = 0; j < array2_len; ++j)

{

if (array1[i] == array2[j])

{

result_array[result_p++] = array1[i];

break;

}

}

}

return result_p;

}

// 另一種思路是用快速排序等高效的排序演算法先將數組排序，

// 然後再遍歷一次數組，這時因為已經排好序了，所以最多隻要

// 遍歷 array1_len + array2_len 即可，此時時間復雜度較低，

// 因為快速排序等一般是 nlog(n)，然後後面接一個一次量級的遍歷，

// 總的來說是 nlog(n) + n，也就是 nlog(n)，比 n^2 要快一些。

int intAscendingComparor(const void* left, const void* right)

{

return *(int*)left - *(int*)right;

}

// 交集

// 先排序後遍歷判斷相同元素，時間復雜度較低

// 傳入原數組及其長度、結果數組

// 返回結果數組的長度

// （需要自行保證結果數組足夠大）

size_t getIntersection_optimized(array1, array1_len, array2, array2_len, result_array)

int* array1, * array2, * result_array;

size_t array1_len, array2_len;

{

size_t result_p = 0;

size_t i = 0;

// 使用標准庫的 qsort 比較方便

int* tmpArray = (int*)malloc(sizeof(int) * (array1_len + array2_len));

for (i = 0; i < array1_len; ++i) tmpArray[i] = array1[i];

for (i = 0; i < array2_len; ++i) tmpArray[array1_len + i] = array2[i];

qsort(tmpArray, array1_len + array2_len, sizeof(int), intAscendingComparor);

for (size_t i = 0; i < array1_len + array2_len - 1; ++i)

{

if (tmpArray[i] == tmpArray[i + 1])

{

result_array[result_p++] = tmpArray[i];

do {

++i;

} while (i < array1_len + array2_len - 1 && tmpArray[i] == tmpArray[i + 1]);

}

}

free(tmpArray); tmpArray = NULL;

return result_p;

}

// 自定義的一個簡單的輸出數組內容的函數

void printArray(int* array, size_t len)

{

for (size_t i = 0; i < len - 1; ++i)

{

printf("%d, ", array[i]);

}

printf("%d", array[len - 1]);

}

int main()

{

clock_t start, end;

int first_array[5] = { 1, 2, 3, 4, 5 };

int second_array[4] = { 4, 5, 6, 7 };

printf("數組1為：{ 1, 2, 3, 4, 5 }，數組2為：{ 4, 5, 6, 7 } ");

// 第一種方法

int result_array[10];

start = clock();

size_t result_array_len = getIntersection(first_array, 5, second_array, 4, result_array);

end = clock();

printf("交集為：{ ");

printArray(result_array, result_array_len);

printf(" }，使用時間：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

// 第二種方法

start = clock();

result_array_len = getIntersection_optimized(first_array, 5, second_array, 4, result_array);

end = clock();

printf("使用優化演算法求出的交集：{ ");

printArray(result_array, result_array_len);

printf(" }，使用時間：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

// 接下來用兩個比較大的數組，測試一下兩種方法的效率

printf(" 下面是測試，求一個包含 100000 個元素和一個包含 199999 個元素的數組的交集： ");

#define len1 100000

#define len2 199999

int* testArray1 = (int*)malloc(sizeof(int) * len1);

int* testArray2 = (int*)malloc(sizeof(int) * len2);

int* testArray = (int*)malloc(sizeof(int) * len1);

start = clock();

for (size_t i = 0; i < len1; ++i) testArray1[i] = i;

for (size_t i = 0; i < len2; ++i) testArray2[i] = i + 12345;

end = clock();

printf("初始化數組用時：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

start = clock();

result_array_len = getIntersection(testArray1, len1, testArray2, len2, testArray);

end = clock();

printf("第一種方法用時：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

start = clock();

result_array_len = getIntersection_optimized(testArray1, len1, testArray2, len2, testArray);

end = clock();

printf("第二種方法用時：%d ms ", (end - start) * 1000 / CLOCKS_PER_SEC);

return 0;

}

注釋應該說明得比較清楚了，這里就不贅言了。

下面分別是在 Windows 上 msvc 和 mingw 編譯並運行的結果：

mingw

9. 用c語言求兩個集合的交集，並集，差集

#include<stdio.h>
#include<string.h>
#include<conio.h>

#defineARR_LEN255		/*數組長度上限*/
#defineelemTypechar	/*集合元素數據類型*/

/*集合數據結構*/
typedefstructset{
	elemTypedata[ARR_LEN];
	intlength;
}set;

/*初始化集合*/
voidinitSet(set*S){
	S->length=0;
}

/*交集*/
/*A與B的交集（A∩B）：既屬於A又屬於B的元素構成的集合*/
intsetIntersection(setA,setB,set*dest){
	inti=0,j=0,k=0;
	dest->length=0;
	for(i=0;i<A.length;i++){/*外循環遍歷A*/
		for(j=0;j<B.length;j++){/*內循環遍歷B*/
			if(A.data[i]==B.data[j]){/*既屬於A又屬於B的元素，存入dest*/
				dest->data[k]=A.data[i];
				k++;
			}
		}
	}
	dest->length=k;
	if(dest->length)
		return1;
	else
		return0;
}

/*並集*/
/*A與B的並集（A∪B）：A與B所有元素構成的集合*/
intsetUnion(setA,setB,set*dest){
	inti=0,j=0,k=0;
	dest->length=0;
	for(i=0;i<A.length;i++){/*外循環遍歷A*/
		for(j=0;j<B.length;j++){/*內循環遍歷B*/
			if(A.data[i]==B.data[j])/*既屬於A又屬於B的元素，跳過*/
				break;
		}
		if(j==B.length){/*屬於A但不屬於B的元素，存入dest*/
			dest->data[k]=A.data[i];
			k++;
		}
	}
	for(j=0;j<B.length;j++){/*B的所有元素，存入dest*/
		dest->data[k]=B.data[j];
		k++;
	}
	dest->length=k;
	if(dest->length)
		return1;
	else
		return0;
}

/*補集*/
/*B在A中的相對補集（A＼B）：屬於A但不屬於B的元素構成的集合*/
intsetComplement(setA,setB,set*dest){
	inti=0,j=0,k=0;
	dest->length=0;
	for(i=0;i<A.length;i++){/*外循環遍歷A*/
		for(j=0;j<B.length;j++){/*內循環遍歷B*/
			if(A.data[i]==B.data[j])/*既屬於A又屬於B的元素，跳過*/
				break;
		}
		if(j==B.length){/*屬於A但不屬於B的元素，存入dest*/
			dest->data[k]=A.data[i];
			k++;
		}
	}
	dest->length=k;
	if(dest->length)
		return1;
	else
		return0;	
}

/*列印集合內容*/
intprintSet(setS){
	inti;
	if(S.length==0){
		puts("Thesetisempty!");
		return0;
	}
	for(i=0;i<S.length;i++)
		printf("%c",S.data[i]);
	putchar('
');
	return1;
}

intmain(void){
	setA,B;
	setAIB,AUB,ACB;/*交集、並集、補集*/
	
	initSet(&A);initSet(&B);
	initSet(&AIB);initSet(&AUB);initSet(&ACB);
	
	strcpy(A.data,"123");
	A.length=strlen(A.data);
	strcpy(B.data,"4532");
	B.length=strlen(B.data);
	
	printf("A:	");
	printSet(A);
	printf("B:	");
	printSet(B);
	putchar('
');
	
	printf("A∩B:	");
	setIntersection(A,B,&AIB);
	printSet(AIB);
	
	printf("A∪B:	");
	setUnion(A,B,&AUB);
	printSet(AUB);

	printf("A＼B:	");
	setComplement(A,B,&ACB);
	printSet(ACB);
	
	getch();/*屏幕暫留*/
	return0;
}

10. 如何用C語言編寫求交集和並集的程序

printf ("請輸入第一個集合內容\n"); scanf ("%s",a); j=strlen(a); printf ("請輸入第二個集合內容\n"); scanf ("%s",b); k=strlen(b); printf ("集合的交集是："); ///////////////////////計算2個數組的交集//////////////////// //flag標志位,index數組下標標志位 int flag=1, index=0; //c[20]保存交集的數組，d[40]保存並集的數組 char c[20]="",d[40]=""; for (n=0;n<j;n++){for (m=0;m<=k;m++){if(a[n] == b[m]){c[index++] = a[n];break;}}}printf("\n%s\n",c); ////////////////////////////計算2個數組的並集/////////////////////// flag=1;index=0;for (n=0;n<j;n++){for(m=0;m<index;m++){if(d[m] == a[n])flag=0;}if(flag){d[index++]=a[n];}flag=1;}flag=1;for (n=0;n<j;n++){for(m=0;m<index;m++){if(d[m] == b[n])flag=0;}if(flag){d[index++]=b[n];}flag=1;} printf ("集合的並集是：");