ARRAY CON INSERCIÓN, BÚSQUEDA, Y BORRADO ORDENADO

 Hola

Aquí muestro un array con la inserción, búsqueda y borrado ordenado que vale para cualquier secuencia de números, si hay algún error, por favor dejar en comentarios.

En este ejercicio, es más eficiente sobre todo la búsqueda binaria, pues acorta muchísimo los tiempos de búsqueda de un elemento. 


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

//constantes
#define MAX_ELEMENTS 100
#define EXIT_ITEM 9


//prototipos de funciones    
void vacia_buffer();
void menu();
void inicializar_array(int pelements[], int *n_elements);
void inicializar_array_predefinidos(int pelements[], int *n_elements);
void insertar_elemento_orden(int pelements[], int *n_elements);
void buscar_elemento_ord(int pelements[], const int *n_elements);
void buscar_elemento_ord_bin(int pelements[], const int *n_elements);
void borrar_elemento_pos(int pelements[], int *n_elements);
void borrar_elemento_valor_ord(int pelements[], int *n_elements);
void ver_elementos(int pelements[], const int *n_elements);

//Función que sirve para que el intro no quede almacenado en el buffer tras scanf
void vacia_buffer()
{
  int ch;
  while ((ch = getchar()) != '\n' && (ch != EOF));
}

//función principal
int main()
{
    menu();
    return 0;
}

//menú principal de usuario
void menu()
{
    int n_elements = 0;
    int opc_menu = 0;
    int elementos[MAX_ELEMENTS];

    do {
        opc_menu = 0;
        printf("        MENU ARRAY        \n");
        printf("----------------------------\n");
        printf("1.Inicializar array a 0\n");
		printf("2.Insertar elementos predefinidos [1,2,3,4,5,6,7,8,9,10]\n");
        printf("3.Insertar en orden\n");
        printf("4.Buscar elemento en array por valor\n");
        printf("5.Búsqueda binaria en array por valor\n");
		printf("6.Borrar elemento en array por posición\n");
		printf("7.Borrar elemento en array por valor\n");
        printf("8.Visualizar array\n");
        printf("9.Salir\n");
        scanf("%i", &opc_menu);
		vacia_buffer();
        switch(opc_menu) {
            case 1 :
                inicializar_array(elementos, &n_elements);
                break; 
            case 2 :                
				inicializar_array_predefinidos(elementos, &n_elements);
                break;
            case 3 :
                insertar_elemento_orden(elementos, &n_elements);
                break;
            case 4 :
                buscar_elemento_ord(elementos, &n_elements);
                break;
            case 5 :
                buscar_elemento_ord_bin(elementos, &n_elements);
                break;
			case 6 :
                borrar_elemento_pos(elementos, &n_elements);
				break;
			case 7 :
			    borrar_elemento_valor_ord(elementos, &n_elements);
				break;
			case 8 :
			    ver_elementos(elementos, &n_elements);
				break;
            case EXIT_ITEM :
                printf("SALIDA :)\n");
				break;
            default : 
                printf("Opción no válida. Por favor seleccione una opción del menú\n");
        }
    } while (opc_menu != EXIT_ITEM);
    return ;
}

void inicializar_array(int pelements[], int *n_elements)
{
	*n_elements = 0;
	printf("Array creado\n");
	printf("El coste de operación ha sido de 0 iteraciones\n");
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}

//opción de menú 1. Escribir tuit a partir de nombre de usuario y texto de tuit
void inicializar_array_predefinidos(int pelements[], int *n_elements)
{
    if ((*n_elements) == 0 ) {
		printf("Insertando elementos\n");
		pelements[0] = 	1;
		pelements[1] = 	2;
		pelements[2] = 	3;
		pelements[3] =	4;
		pelements[4] =	5;
		pelements[5] =	6;
		pelements[6] =	7;
		pelements[7] =	8;
		pelements[8] =	9;
		pelements[9] =	10;
		printf("Array creado con elementos {1,2,3,4,5,6,7,8,9,10}\n");
		(*n_elements) = 10;
    } else {
        printf("Warning!! No se puede inicializar array. Array en uso \n");
    }
	printf("El coste de operación ha sido de 10 iteraciones\n");
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
    return;
}

void insertar_elemento_orden(int pelements[], int *n_elements) 
{
	int i,z,x;
	
	if ((*n_elements) == MAX_ELEMENTS )
	{
		printf("No hay espacio en el array. Array en máximo nro:%i\n ", MAX_ELEMENTS);
	}
	else
	{	
		printf("Escribe el elemento que quieres insertar\n");
		scanf("%i", &i);
		vacia_buffer();
		*n_elements = *n_elements + 1;
		z=0;
		for (x=0; ((x < *n_elements-1) && (i > pelements[x])); x++) {z++;}
		printf("La posición a insertar es %i\n",x);
		for (int j=*n_elements-1; j > x ; j--) {
			printf("j es %i\n", j);
			printf("*n_elements es %i\n", *n_elements);
			pelements[j] = pelements[j-1];
			printf("Reasignando pelements[%i=j] (%i) = pelements[%i=j-1] (%i);\n", j,pelements[j],j-1, pelements[j-1]);
			z++;
		}
		pelements[x] = i;
		printf("El valor %i ha sido insertado en la posicion %i\n", i, x);
	}
	printf("El coste de esta operación ha sido de %i iteraciones\n", z);
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}

void ver_elementos(int pelements[], const int *n_elements)
{
	int z=0;
	
	if (*n_elements == 0) 
	{
		printf("Array vacío, no hay elementos en el array :)\n");
	}
	else
	{
		printf("\n-------LISTADO DE ARRAY--------\n");
		for (int j=0;j < (*n_elements); j++) {
			printf("Elemento nro %i, contiene %i\n", j, pelements[j]);
			z++;
		}
	}
	printf("El coste de esta operación ha sido de %i iteraciones\n", z);
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}

void buscar_elemento_ord(int pelements[], const int *n_elements)
{
	int i,j,z;
	z=0;
	
	printf("\nEscribe el elemento que quieres buscar\n");
	scanf("%i", &i);
	vacia_buffer();
	j=0;
	for (;((j < (*n_elements)) && (i > pelements[j])); j++) {
		z++;
	}
	if (pelements[j] == i) {
			printf("Match!! Elemento nro %i, contiene %i\n\n", j, pelements[j]); 
	}
	else
	{
		printf("Lo siento, elemento no encontrado :(\n\n");
	}
	printf("El coste de esta operación ha sido de %i iteraciones\n", z);
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}

void buscar_elemento_ord_bin(int pelements[], const int *n_elements)
{
	int i,j,z,h,m,v;
	z=0;
	
	printf("\nEscribe el elemento que quieres buscar\n");
	scanf("%i", &i);
	vacia_buffer();
	j=0;
	h=*n_elements;
	while (j < h && i!=v) {
		printf("ANTES DE m=(h+j)/2. Posicion inferior: %i, Posición superior: %i, Media entera de los dos: %i. Busco: %i, valor de vector[media]: %i Ciclo: %i\n", j, h, m, i, v, z);
		m = (h + j) / 2;
		v = pelements[m];
		printf("Después de m= (h+j)/2 Posicion inferior: %i, Posición superior: %i, Media entera de los dos: %i. Busco: %i, valor de vector[media]: %i Ciclo: %i\n", j, h, m, i, v, z);
		getchar();
		z++;
		if (i<v) {
			printf("i<v ANTES DE h=m-1. %i<%i, h(%i)=m(%i)-1\n", i, v, h, m);
			h=m-1;
			printf("i<v DESPUÉS DE h=m-1. %i<%i, h(%i)=m(%i)-1\n", i, v, h, m);
		}
		else {
			if (i>v) {
				printf("i>v  ANTES DE j=m+1. %i>%i, j(%i)=m(%i)-1\n", i, v, j, m);
				j=m+1;
				printf("i>v DESPUES DE j=m+1.  %i>%i, j(%i)=m(%i)-1\n", i, v, j, m);
			}
			else
			if (i==v) {
				printf("Encontrado!!\n");
			}
		}
	}
	if (v == i) {
			printf("Match!! Elemento nro %i, contiene %i\n\n", m, pelements[m]); 
	}
	else
	{
		printf("Lo siento, elemento no encontrado (valor más próximo(%i) != valor buscado(%i)) :(\n\n", v, i);
	}
	printf("El coste de esta operación ha sido de %i iteraciones\n", z);
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}


void borrar_elemento_pos(int pelements[], int *n_elements)
{
	int i,j,z, aux;
	
	printf("\nEscribe la posición del elemento que quieres borrar [%i,%i]\n", 0, MAX_ELEMENTS);
	scanf("%i", &i);
	vacia_buffer();
	z=0;
	if ((i < *n_elements) && (i >= 0 ) && (*n_elements != 0))
	{
		aux = pelements[i];
		j=i;
		z++;
		for (;(j < (*n_elements)); j++) {
			pelements[j] = pelements[j+1];
			z++;
		}
		*n_elements = *n_elements - 1;
		printf("El elemento con valor %i ha sido borrado\n", aux, i );
	}
	else
	{
		printf("La posición %i no es válida para borrar :(\n", i);
	}
	printf("El coste de esta operación ha sido de %i iteraciones\n", z);
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}

void borrar_elemento_valor_ord(int pelements[], int *n_elements)
{
	int i,j,z, aux,zz;
	
	printf("\nEscribe el valor del elemento que quieres borrar.\n");
	scanf("%i", &i);
	vacia_buffer();
	zz=0;
	if (*n_elements != 0)
	{
		aux = pelements[i];
		for (j=0;(j < (*n_elements)) && (i>=pelements[j]); j++) {
			if (pelements[j] == i) {
				aux = pelements[j];
				for (z=j; z < *n_elements; z++) {
					pelements[z] = pelements[z+1];
					zz++;
				}
				*n_elements = *n_elements - 1;
				j=j-1;
				printf("El elemento con valor %i que estaba en la posición %i ha sido borrado.\n", aux, j );
				
			}
			zz++;
		}
	}
	else
	{
		printf("Array vacío :(\n", i);
	}
	printf("El coste de esta operación ha sido de %i iteraciones\n", zz);
	printf("Numelements vale %i\n", *n_elements);
	printf("\nPulse una tecla para continuar...\n\n");
	getchar();
	return;
}

Comentarios

Publicar un comentario

Entradas populares de este blog

ESTRUCTURA DE DATOS BÁSICA ARRAY

Hola Mi decisión de escribir este blog fue en base al libro de  Jay Wengrow   "A Common-Sense Guide to Data Structures and Algorithms" . Este libro ha sido toda una inspiración, por su claridad y su fácil lectura (aunque esté en inglés, que no es mi idioma). Empiezo el blog con un algoritmo para ir aprendiendo la estructura Array. Hay muchas cosas que decir de esta estructura. A pesar de ser la más simple, tiene su complejidad sobre todo a la hora de borrar y de insertar por el principio pues hay que re-acomodar el resto de la estructura. Gracias a esta web por la función de limpiar el buffer.  La función de búsqueda es lineal. Lo interesante a nivel de ingeniería es ver el coste de iteraciones que tiene cada estructura, analizando las operaciones que se van a hacer y el coste de cada operación.   # include < stdio.h > # include < stdlib.h > //constantes # define MAX_ELEMENTS 100 # define EXIT_ITEM 9 //prototipos de funciones void v...
Leer más