Introducción alas estructuras de datos Representación de reales con 64 bits suma y producto de números binarios usando cadenas ADT-complejos operaciones básicas complejos en C operaciones básicas complejos en C++ estructura y unión para biblioteca Recursividad Simulación de conversión a posfijo mcd recursivo función de Ackerman en C función de Ackerman evaluación manual Agregar constantes (e y pi) y variables a la calculadora recursiva Programa para resolver el Sudoku con el algoritmo de vuelta atrás Implementar el algoritmo de conversión prefijo posfijo Listas 1. Escriba un algoritmo para ejecutar cada una de las siguientes operaciones: a. Agregar un elemento al final de una lista. b. Concatenar dos listas. c. Liberar todos los nodos de una lista. d. Invertir una lista de manera que el último elemento se convierta en el primero, y así sucesivamente. e. Elimine el último elemento de una lista. f. Elimine el n-ésimo elemento de una lista. g. Combine dos listas ordenadas en una sola que también esté ordenada. h. Forme una lista que contenga la unión de los elementos de dos listas. i. Forme una lista que contenga la intersección de los elementos de dos listas. j. Inserte un elemento después del n-ésimo de una lista. k. Elimine todos los segundos elementos de una lista. l. Ponga los elementos de una lista en orden ascendente. m. Dé como resultado el número de elementos de una lista. n. haga una copia de una lista. o. mueva node(p) n posiciones hacia adelante de una lista. 2. Crear una aplicación en C que muestre todas las operaciones solicitadas en el problema 1. 3. Representar polinomios en x, y y z usando listas y escribir funciones para: a) evaluar un polinomio en (x0,y0,z0) b) derivar parcialmente respecto a x, y y z. c) integrar parcialmente respecto a x, y y z. d) sumar dos polinomios e) multiplicar dos polinomios f) dividir dos polinomios y obtener cociente y residuo g) dados 4 polinomios f(x,y,z), g(x,y,z), h(x,y,z), i(x,y,z), calcular f(g(x,y,z),h(x,y,z),i(x,y,z)) Árboles 1. Dada la siguiente secuencia de números de entrada dibuje el árbol binario resultante al aplicar el algoritmo de construcción siguiente: secuencia: 3 6 15 2 8 9 12 7 11 10 1 4 5 SUBRUTINA PLACE(P:NODEPTR,X:INFOTYPE) 1. SI P=NIL ENTONCES a. P MAKETREE(X) 2. SINO a. SI XINFO(P) ENTONCES 1. PLACE(RIGHT(P),X) c. SI X=INFO(P) ENTONCES 1. WRITE "ELEMENTO REPETIDO" 2. Recorra el árbol binario generado en el problema anterior usando los algoritmos de recorrido en preorden, entreorden y oposorden e imprima la lista de números generada en cada caso 3. Escriba un programa que lea un archivo de texto e inserte todas las palabras diferentes en un árbol binario. El objetivo es contar el número de veces que aparece cada palabra. Ayuda: La función strtok de la biblioteca string.h separa una cadena en subcadenas, cada una de ellas delimitada por algún carácter separador. El primer parámetro es la cadena a separar y el segundo es una cadena con todos los caracteres delimitadores. La función destruye la cadena original regresa el apuntador al primer pedaso extraido. Posteriores llamadas a esta función con el primer parámetro NULL extraen los demás pedasos. #include #include #include void separa(char *frase){ char *s; char delimitadores[] = " \n\t,.?!"; s = strtok(frase,delimitadores); //Primera llamada printf("%s\n", s); while(s!= NULL){ s = strtok( NULL,delimitadores); if(s!=NULL) printf("%s\n", s); } } main(){ char cad[80]; printf("Escriba una frase:\n"); scanf("%[^\n]",cad); separa(cad); getch(); } 4. El índice de un libro consta de términos principales colocados en orden alfabético. Cada uno de ellos va acompañado por un conjunto de números de página y un conjunto de subtérminos. Los subtérminos están impresos en líneas sucesivas que siguen al término principal. Cada subtérmino va acompañado de un conjunto de números de página. Diseñe una estructura de datos para representar un índice como el descrito y escriba un programa en C para imprimir un índice de datos como sigue. Cada línea de entrada comienza con una m (término principal) o una s (subtérmino). Una línea m contiene una m seguida de un término principal, seguido de un entero n (0 es posible) seguido de n números de página en que aparece el término principal. Una línea s es similar excepto contiene un subtérmino en lugar de un término principal. Las líneas de entrada no aparecen en orden particular, excepto por el hecho de que cada subtérmino se considera un subtérmino del último término principal que lo precede. Puede haber muchas líneas de entrada para un solo término o subtérmino (todos los números de página que aparecen en cualquier línea para el término particular deben imprimirse con el mismo). El índice debe imprimirse en una línea con un término seguido por todas las páginas en las que aparece decho término en orden ascendente. Los términos principales deben imprimirse en orden alfabético. Los subtérminos, que también deben aparecer en orden alfabético, van inmediatamente después del término principal. Los subtérminos deben colocarse a cinco columnas del término principal. El conjunto de términos debe organizarse como un árbol binario. Cada nodoe del árbol contiene (además de los apuntadores derecho e izquierdo y el término principal) apuntadores a otros dos árboles binarios. Uno de éstos representa el conjunto de números de página en las que aparece el término princpal; el otro representa el conjunto de subtérminos del mismo. Cada nodo de un árbol binario que representa un subtérmino contiene (además de los apuntadores derecho e izquierdo y el propio subtérmino) un apuntador a un árbol binario que representa el conjunto de números de página en las que aparece el subtérmino. m algoritmo 4 16 55 3 23 s de busqueda 2 27 34 s de ordenacion 3 24 57 26 s de busqueda 1 58 algoritmo 3, 16, 23, 55 de busqueda 34, 27, 58 de ordenacion 24, 26, 57 Ordenación 1. Aplique los algoritmos de ordenación al siguiente arreglo de enteros: 03 13 17 12 02 01 45 28 33 12 19 58 36 27 haga figuras como las de los acetatos en PP. 2. Ordene arreglos para verificar las fórmulas vistas en clase sobre el comportamiento de métodos de ordenación. Ordene arreglos aleatorios de hasta 500000 elementos. Luego ordene arreglos ordenados y finalmente arreglos en orden inverso. Comente sus resultados. 3. Modifique los metodos de ordenación para cadenas de caractres. 4. Repita el problema 2 con ordenamiento de cadenas de caracteres. comente sus resultados. Búsqueda 1. Escriba un algoritmo de búsqueda en un arreglo ordenado que busque un elemento y si no lo encuentra lo inserte en la posición que le corresponde. Utilice el algoritmo de búsqueda secuencial. 2. Escriba una función en C que encuentre todas las ocurrencias de un elemento a dentro de un arreglo. La primera llamada localizará la primera ocurrencia, y llamadas posteriores las demás. 3. El siguiente algoritmo de búsqueda en un arreglo ordenado que se conoce como búsqueda de Fibonacci a causa del uso de los números de Fibonacci. j = 0 ; while(fib(j) k[mid])){ if(f1==1) return -1; else{ mid = mid + f2; f1 = f1 - f2; f2 = f2 - f1; } }else { if(f2==0) return -1; else { mid = mid - f2; t = f1 - f2; f1 = f2; f2 = t; } } if(mid>0) Ok = key!=k[mid]; } return mid; Explique como trabaja el algoritmo. Confrontar el número de comparaciones de llaves con el número que realiza la búsqueda binaria. Modificar la proción inicial de este algoritmo de manera que calcule los números de Fibonacci de manera eficiente, en lugar de buscarlos en una tabla o computarlos cada vez de nuevo.