Problemas de pila en lenguaje pascal.

Si Pascal de arriba no entiende, ¡no lo copie! ! !

Esto es una blasfemia.

También tengo una pila de folletos PPT. Por favor envíame tu dirección de correo electrónico, gracias. Enviaré el archivo adjunto al correo electrónico.

1 Concepto y funcionamiento de pila

Definición de pila: La pila es una tabla especial que solo se puede insertar y eliminar en la cabecera de la tabla. Por lo tanto, la cabeza tiene un significado especial para la pila y se llama parte superior de la pila. Por lo tanto, el pie de página se denomina parte inferior de la pila. Una pila sin ningún elemento se llama pila vacía.

Estructura lógica de la pila: supongamos que los elementos en una pila S son an, an-1,..., a1, entonces A1 se llama el elemento inferior de la pila y an es el elemento superior. de la pila. Los elementos de la pila están en el orden de A1, A2,..., An-1, An. En cualquier momento, el elemento que sale de la pila es el elemento superior de la pila. En otras palabras, la pila se modifica según el principio de último en entrar, primero en salir, como se muestra en la Figura 1. Por lo tanto, la pila también se denomina tabla de último en entrar, primero en salir, o tabla LIFO para abreviar. Entonces, siempre que el problema satisfaga el principio LIFO, puedes utilizar la pila.

Operación de pila: como tipo de datos abstracto, las operaciones de pila comúnmente utilizadas son:

Significado de la operación

Hacer de S una pila vacía.

GetTop(S) Esta es una función cuyo valor es el elemento superior en S.

Pop(S) elimina el elemento superior de la pila S, lo que se conoce como lanzamiento de pila.

Push(S, x) inserta el elemento x en la parte superior de la pila de S. En pocas palabras, coloca el elemento x en la pila.

Esta es una función. Cuando s es una pila vacía, el valor de la función es verdadero; de lo contrario, el valor de la función es falso.

2 Almacenamiento e implementación de la pila

Implementación de la pila en matriz: debido a que la pila es una tabla especial, podemos usar una matriz para implementar la pila. Teniendo en cuenta la particularidad de las operaciones de pila, cuando usamos elementos de matriz [1...maxlength] para representar una pila, fijamos la parte inferior de la pila a la parte inferior de la matriz, es decir, elementos [1] es el primer elemento colocado en la pila. Deje que la pila se expanda hasta la parte superior de la matriz (en la dirección de subíndices crecientes). Al mismo tiempo, usamos un cursor superior para indicar la unidad donde se encuentra el elemento superior de la pila actual. Cuando top = 0, significa que la pila está vacía. En términos generales, el orden de los elementos elementos [arriba], elementos [arriba-1],..., elemento [1] constituye una pila. Esta estructura se muestra en la Figura 2.

Figura 2

Usando la estructura anterior, podemos definir formalmente el tipo de pila TStack de la siguiente manera:

Tipo

TStack = registro

arriba: entero;

Elemento: matriz [1..longitud máxima];

Fin;

En esta representación, el stack Se pueden implementar cinco operaciones básicas de la siguiente manera.

Proceso en pila(Var S: t pila);

Inicio

s.top:= 0;

Fin;

Función vacía(var S: Pila): booleana;

Inicio

retorno(s . top = 0);

Fin;

Función top(var S: TStack): Telemetría;

Inicio

Si está vacío, se produce un error ("La pila está vacía")

Inicio

p>

else return(s . elemento[s . top]);

Fin

Proceso Pop(var; S: t stack);

Inicio

Si está vacío, se produce un error ("La pila está vacía.

")

else dec(s. top); {S.top menos 1}

Fin;

Proceso push (var S: t stack; x : Telemetría;);

Iniciar

Si S.top=maxlength, se produce un error ('La pila está llena')

En caso contrario, Iniciar

Inc(s . top); {S.top aumentado en 1}

s . top]: = x

Fin;

Fin;

La complejidad de cada una de las operaciones anteriores es O(1)

En algunos problemas, puede ser necesario utilizar varias pilas del mismo tipo al mismo tiempo. Al mismo tiempo, para evitar que cada pila se desborde cuando se ejecuta el algoritmo, se debe establecer un espacio de pila grande en la parte superior de cada pila. De hecho, durante la ejecución del algoritmo, cada pila generalmente no estará llena al mismo tiempo. Algunas están llenas y otras vacías. Por lo tanto, si permitimos que varias pilas compartan la misma matriz y se ajusten dinámicamente entre sí, mejorará la utilización del espacio y reducirá la posibilidad de que la pila se desborde en el programa. 1...n]. Aprovechando la posición constante de la parte inferior de la pila, podemos colocar las partes inferiores de las dos pilas en ambos extremos de la matriz S y luego extenderlas hacia el medio, como se muestra en la Figura 3. Los valores iniciales de las dos pilas S son 0 y n 1 respectivamente. El desbordamiento solo ocurrirá cuando las partes superiores de las dos pilas se encuentren. Debido a que las dos pilas pueden ser complementarias, el espacio máximo real disponible para cada pila suele ser mayor. que n. /2.

Aplicación de 3 pilas

1. Evaluación de expresiones

Pregunta: ¿Puedes diseñar un algoritmo y escribir un programa para permitir la computadora? ¿Escanee las siguientes expresiones e imprima sus valores?

# 3 * ( 4 8 ) / 2 -5 #

Nota: Establezca # en la expresión para marcar el inicio y el final escaneados.

Algoritmo de solicitud: configure dos pilas, una es la pila de operandos, que se usa para almacenar operandos, como 3, 4, 8, y la otra es la pila de operadores, que se usa para almacenar operadores. /p>

Primero, coloque el signo "#" en la parte inferior de la pila del operador.

Luego escanee la pila secuencialmente según el principio de último en entrar, primero en salir:

(1) Cuando encuentre un operando, ingrese la pila de operandos

(2) Cuando encuentre un operador, debe comparar la prioridad de este operador con la prioridad del operador de nivel superior

(2) Cuando encuentre un operador, debe comparar la prioridad de este operador con la prioridad del operador de nivel superior p>

Si es mayor que el elemento superior de la pila. , va a la pila y continúa buscando el siguiente símbolo.

De lo contrario, el elemento superior de la pila de operadores se devuelve para formar el código de operación Q y se devuelve el elemento superior de la pila de operandos. A y B se forman dos veces, para que la computadora pueda realizar una operación en los operandos y códigos de operación, es decir, aQb, y almacenar los resultados de la operación en la pila de operandos...

Simular el procesamiento de la computadora proceso de expresiones aritméticas. Ingrese una cadena de expresión aritmética desde el teclado (solo se permiten los operadores , -, ×, ÷ y paréntesis) y genere el valor de la expresión aritmética. Haga que la cadena de expresión de entrada sea legal.

Programa fuente adicional:

Programa exsj_1;

Constante

max = 100;

Definir variables

Número: entero de la matriz [0..max];

Símbolo: matriz[1..char max];

s, t : string <; /p>

I, p, j, código: entero;

Empuje del programa; {operación de pila del operador}

Inicio

Inc(p) ; símbolo [p]: = s[I];

Fin;

Emergente del programa; {saque el elemento superior de la pila de operadores y complete el elemento de la pila de operandos. operación correspondiente}

Inicio

dec(p);

símbolo de caso [p 1]

': inc (número [p ], número [p 1]);

-': dec (número [p], número [p 1]); p]* número[p 1];

/': número[p]:= número[p]div número[p 1];

Fin;

Fin;

La función puede ser: Booleana; {Juzga la prioridad del operador y establece una función de bandera}

Inicio

Puede: = true; /p>

if (s[i] in [' ', '-']) y (symbol [p] lt; gt(') luego sale;

if ( s[i] en ['* ',/']) y ['* ',/']) y luego salir

Can: = false

End; p> p>

Inicio

write(' String: '); readln(s); s: = '(' s ')'; /p >

mientras I lt=length hago

inicio

mientras s[I]= '(' hago {procesamiento del corchete izquierdo]

inicio

p>

Push; inc(one);

End;

j:= I;

Repetir {extraer datos al operando pila}

inc(一);

Hasta (s[I] lt; 0 ') o (s[I] gt; '9'); p> t:=copiar(s,j,I-j);val(t,número[p],código);

Repetir

Si s[i]= ')' luego {Procesamiento de corchetes cerrados}

Iniciar

mientras símbolo [p] lt(do pop

dec(p); número [p]: = número [ p 1];

Fin

Otros

Iniciar {operación de entrada o salida de la pila del operador según el valor de la función de bandera}

En su lugar, puedes hacer pop

push;

end;

inc(one);

hasta que (i gt length (s)) o (s[I-1] lt; gt')');

Fin

write('Result= ', número[0]); /p>

readln

Fin.

2. Problema de mochila

Pregunta: Supongamos que hay n artículos con distribución de masa w1, w2,..., wn y una mochila con una masa total máxima T, podemos seleccionar una. algunos artículos de estos n artículos y colóquelos en la mochila de modo que la masa total de los artículos seleccionados sea exactamente igual a la masa máxima que la mochila puede transportar, es decir, WI1 WI2 ... WIK = T. Si es así, el El problema de la mochila tiene solución, de lo contrario no hay solución.

Idea de algoritmo: primero coloque n artículos en una fila y selecciónelos en secuencia, si la masa total de los artículos en la mochila no excede la masa de carga máxima de la mochila después de cargar un artículo, cargue (; pila); de lo contrario, abandone Para esta selección de artículos, se selecciona el siguiente artículo para probar hasta que la suma de los artículos cargados sea exactamente la masa máxima de carga de la mochila. En este momento decimos que la mochila está llena.

Si una mochila que contiene varios artículos no está llena y no hay otros artículos que se puedan seleccionar en la mochila, significa que hay artículos no calificados en la mochila y el último artículo debe retirarse de la mochila (Regresar a la pila), luego seleccione entre los artículos descargados, repitiendo este proceso hasta que la mochila esté llena (solución disponible) o no haya artículos para elegir (sin solución).

Implementación específica: Sea el peso de la matriz [1...n] y apile [1, N] para almacenar el peso y el número de artículo de los artículos que se han cargado en la mochila (apilar ) respectivamente. MaxW representa el peso máximo de la mochila. Cada vez que se apila un artículo, la masa del artículo se resta de MaxW e I es el número de serie del artículo que se seleccionará. si maxw-weight[i]>=0, este elemento es opcional; si maxw-weight[i]n, debe volver a la pila. Si la pila está vacía en este momento, no hay solución.

Función de referencia implementada en Pascal;

Función knapstack(n, MaxW, peso);

Inicio

arriba: = 0 ; I:= 1;{i es el número de serie del artículo a seleccionar}

mientras (MaxW gt; 0) y (i lt do

Iniciar

if (MaxW-weight[I] gt; = 0) y (i lt= n) entonces

comenzar arriba: = top 1; pila[top]: = MaxW = MaxW-weight [I]fin;

{Coloca el artículo I en la mochila}

Si MaxW=0, regresa (verdadero)

De lo contrario comienza

Si (i=n) y (top gt0) entonces {hay elementos inapropiados en la mochila}

Comienza {obtener el elemento superior de la pila y restaurar el valor de MaxW}

I: = pila[top]; top: = top-1; MaxW peso[I];

Si top gt0 entonces iniciar

I: = pila [arriba]; arriba: = top-1; MaxW = peso MaxW[I];

Fin

Fin

I: = I 1;

Fin;

Fin

return(false){problema no resuelto}

Fin; Ejercicio: Problema de mochila completamente completado