Lenguaje C para encontrar la unión e intersección de dos matrices.

Solo analicé brevemente la situación de la intersección y la unión es similar. Baidu sabe que este soporte de código no es muy bueno. Se verá mejor si lo copia y lo pega en un editor de código como VS y le aplica sangría.

Vea el código a continuación:

#include lt;stdio.hgt;

#include lt;stddef.hgt;

# include lt; stdlib.hgt;

#include lt; time.hgt

//Utilice una matriz de números enteros, lo mismo se aplica a otras matrices

// Intersección

// Determine los mismos elementos mediante recorrido iterativo, la complejidad del tiempo es alta, magnitud cuadrada

// Pase la matriz original, su longitud y el matriz de resultados

// Devuelve la longitud de la matriz de resultados

// (Debe asegurarse de que la matriz de resultados sea lo suficientemente grande)

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 lt; array1_len; i)

{

for (size_t j = 0; j lt; matriz2_len; j)

{

si (matriz1[i] == matriz2[j])

{

result_array[result_p ] = array1[i];

romper

}

}

}

return result_p;

}

// Otra idea es utilizar un algoritmo de clasificación eficiente, como la clasificación rápida, para ordenar la matriz primero,

// y luego recorra la matriz nuevamente, porque ya está ordenada, por lo que como máximo solo necesita

// atravesar array1_len array2_len. En este momento, la complejidad del tiempo es baja,

<. p>// porque la clasificación rápida, etc., generalmente es nlog (n), seguido de un recorrido lineal,

// En términos generales, es nlog (n) n, es decir, nlog ( n), que es más rápido que n^2.

int intAscendingComparor(const void* izquierda, const void* derecha)

{

return *(int*)izquierda - *(int*)derecha;

}

// Intersección

// Ordenar primero y luego atravesar para determinar los mismos elementos, la complejidad del tiempo es baja

// Pasar Ingrese la matriz original, su longitud y la matriz de resultados

// Devuelve la longitud de la matriz de resultados

// (Debe asegurarse de que la matriz de resultados sea lo suficientemente grande)

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;

// Es más conveniente usar qsort de la biblioteca estándar

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

for (i = 0; i lt; array1_len; i) tmpArray[i] = matriz1[i];

for (i = 0; i lt; array2_len; i) tmpArray[array1_len i] = matriz2[i];

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

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

{

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

{

result_array[result_p ] = tmpArray[i]; hacer {

i;

} while (i lt; array1_len array2_len - 1 amp; amp; tmpArray[i] == tmpArray[i 1]); p> }

}

gratis(tmpArray); tmpArray = NULL

return result_p; p>// Una función personalizada simple que genera el contenido de la matriz

void printArray(int* array, size_t len)

{

for (size_t i = 0; i lt; i)

{

printf("d, ", matriz[i]); /p>

printf("d", matriz

y[len - 1]);

}

int main()

{

clock_t inicio, fin;

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

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

printf("La matriz 1 es: {1, 2, 3, 4, 5}, la matriz 2 es: {4, 5, 6, 7}\n");

// Primer método

int result_array[10];

inicio = reloj();

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

end = reloj();

printf("La intersección es: { ");

printArray(result_array, result_array_len);

printf(" }, tiempo de uso: d ms\n", (fin - inicio) * 1000 / CLOCKS_PER_SEC

// Segundo método

inicio = reloj ();

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

end = clock()

printf("Usar optimización La intersección obtenida; por el algoritmo: { ");

printArray(result_array, result_array_len);

printf(" }, tiempo de uso: d ms\n", (fin - inicio) * 1000 / CLOCKS_PER_SEC);

// A continuación, use dos matrices más grandes para probar la eficiencia de los dos métodos

printf("\nLa siguiente es una prueba, encuentre una intersección de una matriz que contiene 100000 elementos y una matriz que contiene 199999 elementos: \n");

#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 lt; len1; i ) testArray1[i] = i;

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

end = reloj(); p>p

rintf("Tiempo de inicialización de la matriz: d ms\n", (fin - inicio) * 1000 / CLOCKS_PER_SEC

inicio = reloj()

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

end = clock();

printf("El primer método lleva tiempo: d ms\n", (fin - inicio) * 1000 / CLOCKS_PER_SEC);

inicio = reloj();

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

fin = reloj); ();

printf("El segundo método lleva tiempo: d ms\n", (fin - inicio) * 1000 / CLOCKS_PER_SEC

return

);

}

Los comentarios deberían explicarlo más claramente, así que no entraré en detalles aquí.

Los siguientes son los resultados de compilar y ejecutar msvc y mingw en Windows:

msvs

mingw