• Categories
• Algoritmos y estructuras de datos
• Programación de computadoras
• Áreas de la informática
• Gestión de datos
• Informática

Citation preview

“Año de lA IntegrAcIón Nacional y el Reconocimiento de nuestrA dIversIdAd” Universidad Nacional del Santa Escuela Académica Profesional de Sistemas e Informática Asignatura:

ESTRUCTURA DE DATOS Integrantes:

Pinedo Flores Liseyka. VALLADARES VEGA JAMES BOTTGER ALOR PRISCILLA. Diaz Torres Manuel.

2012

APLICACIÓN DE PILAS 1. Algoritmo de transformación de una expresión infija a una expresión postfija. INICIO Leer nt // numero de términos Cont = 0 Topex = 0 Tope = 1 Mientras cont < nt hacer Leer X // elemento hacer ingresado EXIN [cont] = X Cont = cont + 1 Fin_Mientras EXIN *nt+ = “)” PILA *tope+ = “(“ Tope = tope + 1 Cont = 0 Mientras cont = Variable ) hacer Variableextraer = PILA [tope - 1] EXPO [topex] = Variableextraer tope = tope – 1 topex = topex + 1 Fin_Mientras Si PILA [tope - 1]) < Variable entonces PILA [tope] = Variable tope = tope + 1 Fin_Si Fin_Si Si Variable = “(” entonces PILA [tope] = Variable tope = tope + 1 Fin_Si Si Variable = “)” entonces j = tope – 1 Mientras PILA *j+ “(“ hacer Si ( tope > 0 ) entonces Variableextraer = PILA [tope - 1] tope = tope – 1

EXPO [topex] = variableextraer Fin_Si j=j–1 Topex = topex + 1 Fin_Mientras Variableextraer = PILA [tope - 1] Tope = tope - 1 Caso contrario EXPO [topex] = Variable Topex = topex + 1 Fin_Si Cont = cont + 1 Fin_Mientras K=0 Mientras k < topex hacer Imprimir “ EXPO *k+ “ K=k+1 Fin_Mientras FIN

2. Algoritmo de la expresión postfija. INICIO Leer nt // numero de términos indice = -1 cont = 0 Mientras ( cont < nt ) hacer Leer X // elemento hacer ingresado EXIN [cont] = X Cont = cont + 1 Fin_Mientras EXIN *nt+ = “)” cont = 0 Mientras EXPO *cont+ “)” hacer Si ( EXPO *cont+ “ + ” y EXPO *cont+ “ - ” y EXPO *cont+ “ * ” y EXPO *cont+ “ / ” y EXPO *cont+ “ ^ ”) entonces Índice = índice + 1 PILA [indice] = EXPO [cont] Caso contario a = PILA [indice] b = PILA [indice - 1] Fin_Si Si EXPO *cont+ = “ + ” entonces

Índice = índice - 1 PILA [indice] = b + a Fin_Si Si EXPO *cont+ = “ * ” entonces Índice = índice - 1 PILA [indice] = b * a Fin_Si Si EXPO *cont+ = “ - “ entonces Índice = índice - 1 PILA [indice] = b - a Fin_Si Si EXPO *cont+ = “ / ” entonces Índice = índice - 1 PILA [indice] = b / a Fin_Si Si EXPO *cont+ = “ ^ ” entonces Índice = índice - 1 PILA [indice] = b ^ a Fin_Si Cont = cont + 1 Fin_Mientras VALOR = PILA [indice] Imprimir VALOR FIN

3. Cierto número de usuarios n, envían simultáneamente un documento a la impresora común, la cual debe determinar su orden de impresión. Las longitudes los documentos enviados son: i1….in. Siendo la longitud del documento enviado por el usuario (la numeración de los usuarios es arbitraria). Suponiendo que el tiempo que se tarda en imprimir un documento es proporcional a su longitud. Escribir el algoritmo que indique el orden óptimo en que se deben imprimir de manera que se minimice el tiempo medio de espera de cada usuario. El tiempo de espera del usuario i-esimo vendrá dado por el orden que haya establecido al impresora para su documentación. Si su documento es el j-esimo en imprimirse, su tiempo de espera será la suma de los tiempos de impresión de los dos j primeros documentos según ese orden (se incluye el suyo en la suma). Los usuarios deben estar enterados del tiempo que los tomara esperar. INICIO Leer n // numero de términos Leer L // Longitud del Documento tiempo = 0 Frente = 0

Final = 0 ( Tiempo de impresión aproximado 30s = 0.5 m por hoja ) Si [ ( final = n ) y ( frente =1 ) ] o [ ( final + 1= frente ) ] entonces Escribir “Lista de Impresión Llena” Caso contrario Si Final = n Final = 1 Caso contrario Final = Final + 1 Fin _ Si Cola L[final] = L x 0.5 tiempo = tiempo + cola L[final] Imprimir “tiempo de impresión: te” Si Frente = 0 Frente = 1 Fin_ Si Fin_Si Si ( tiempo = t ) ( t: Tiempo transcurrido en verlo ) entonces Si Frente = 0 Escribir “Lista de impresión vacía” Caso contrario Cola *frente+ = “ ” Si Frente = Final Frente = 0 Final = 0 Caso contrario Si Frente = Final Frente = 0 Final = 0 Caso contrario Si Frente = n Frente = 1 Caso contrario Frente = Frente + 1 Fin_Si Fin_Si Fin_Si Fin_Si Fin_Si FIN

4. Dados los caracteres (), {}, [], y una cadena s, a esta balanceada si tiene alguno de estos formatos, s = “ ”, ( String nulo); s = (T); s = [T]; s = {T}; s = UT en donde T y U son cadenas balanceadas (en otras palabras, para cada paréntesis, llave o corchete abierto existe un carácter de cierre correspondiente). Ejemplo s = { [ (c - d) ˄ 2+ + 1 }. Escribir el algoritmo (Pseudo código) que use una PILA para ver si una cadena es balanceada. INICIO tope = 0 i=0 prece = 4 t = tamaño de cadena ele [ i ] = /* lee carácter de la cadena ingresada */ Mientras ( i