Tipos y estructuras de datos

Cada variable necesita un tipo de dato 数据类型 — el tipo de valor que contiene y las operaciones permitidas:

• INTEGER — un número entero (42, -7). Para conteos, índices, IDs.
• REAL — un número con parte fraccionaria (3.14). Para dinero, mediciones.
• STRING — caracteres entre comillas ("Hello"). Para texto.
• CHAR — un solo carácter ('A').
• BOOLEAN — TRUE o FALSE. Para banderas.
• DATE — una fecha del calendario.

Elige el tipo más pequeño pero preciso que se adapte: INTEGER para conteos enteros, BOOLEAN para banderas (no las cadenas "yes"/"no").

Las tablas de "dar el tipo de dato adecuado" se determinan por cómo se usa el valor: la nota media de una clase es REAL (tiene parte fraccionaria); una dirección de correo electrónico es STRING; el número de estudiantes es INTEGER; si un estudiante ha pagado es BOOLEAN; una fecha de nacimiento es DATE; un índice de array es siempre INTEGER; una sola letra de calificación es CHAR; un número de teléfono es una STRING, porque comienza con 0 y nunca se usa en aritmética. Una BOOLEAN se usa para una bandera con solo dos estados: si una búsqueda ha encontrado su objetivo, si un miembro ha pagado, si un asiento está reservado. Para la tabla de identificadores, el nombre de la variable también debe ser significativo: NumberOfPeople, no n.

Un registro 记录 (una estructura de registro 记录结构) almacena varios campos de diferentes tipos bajo un solo nombre — útil cuando varios valores describen una misma cosa.

TYPE TStockItem
    DECLARE ItemID : INTEGER
    DECLARE Category : STRING
    DECLARE ItemCost : REAL
    DECLARE InStock : BOOLEAN
ENDTYPE

Esto define el tipo TStockItem; declara variables de este tipo:

DECLARE Item1 : TStockItem
DECLARE Items : ARRAY[1:100] OF TStockItem

Usa notación de puntos para acceder a cada campo 字段:

Item1.Category ← "Fruit"
OUTPUT Item1.Category, " costs ", Item1.ItemCost

Usa un registro cuando los valores siempre pertenecen juntos (un cliente, un artículo de inventario); usa variables separadas para valores no relacionados.

Ejemplo resuelto. Un club almacena, para cada estudiante, un ID de estudiante (una cadena), un nombre, una fecha de nacimiento y hasta tres números de club (enteros). Escribe pseudocódigo para declarar el tipo de registro, un array para almacenar $3000$ estudiantes, y una instrucción que almacene un nombre en el primer elemento.

TYPE Student
    DECLARE StudentID : STRING
    DECLARE Name : STRING
    DECLARE DateOfBirth : DATE
    DECLARE Club : ARRAY[1:3] OF INTEGER
ENDTYPE

DECLARE Membership : ARRAY[1:3000] OF Student
Membership[1].Name ← "Li Wei"

Las puntuaciones: TYPE con el identificador y ENDTYPE; cada campo declarado con un tipo adecuado; la array declarada con sus límites y OF Student; el campo alcanzado mediante el índice y un punto. Una pregunta de "enunciar el error en la declaración del registro" suele señalar una falta de ENDTYPE, un campo sin tipo, o un campo declarado como STRING que debe contener aritmética. Dos convenciones obtienen puntos por sí solas: un elemento no utilizado se marca con un valor que no puede ser datos reales (una cadena vacía, -1, un ID de 0), y es buena práctica usar el mismo marcador en todas partes para que cada módulo pueda reconocer una ranura no utilizada; un campo de club no utilizado es 0. Las ventajas de una array de registros, para "enunciar tres ventajas": todos los datos de una entidad se almacenan bajo un solo identificador; los campos pueden tener diferentes tipos de datos; una array reemplaza a varias arrays paralelas que tendrían que mantenerse sincronizadas; todo el conjunto se puede procesar con un solo bucle o pasarse como un solo parámetro; y añadir un campo cambia solo la definición del tipo. Para un cliente, la estructura adecuada es un registro (campos de diferentes tipos bajo un nombre); para todos los clientes es una array de registros.

Un array 数组 es una colección ordenada de elementos del mismo tipo, bajo un solo nombre, alcanzados por un índice 索引.

• elemento 元素 — un elemento en la array.
• bounds 边界 — los índices válidos más bajos y más altos.
• dimension 维度 — 1-D (una lista), 2-D (una tabla), etc.
• lower bound 下界 y upper bound 上界 — el primer y último índice válido; el número de elementos es límite superior menos límite inferior más uno, y para una array 2-D es el producto de ambas cantidades.

Así que en ThisArray[n] ← 42 la array tiene una dimensión, el índice es la variable n (un INTEGER), y el elemento en ese índice recibe 42. Antes de declarar una array necesitas su tipo de datos así como sus límites. Para declarar $120$ valores que puedan incluir un punto decimal: DECLARE Data : ARRAY[1:120] OF REAL; una tabla de strings de $150$ filas y dos columnas: DECLARE Data : ARRAY[1:150, 1:2] OF STRING, que tiene $300$ elementos. Las ventajas de una array sobre variables separadas, para una explicación de dos puntos: un identificador en lugar de treinta; los elementos se pueden procesar con un bucle usando el índice como contador; el tamaño es fácil de cambiar; y todo el conjunto se puede pasar a un módulo como un solo parámetro. Una array también puede reemplazar una cadena de sentencias de selección: DaysInMonth[Month] busca la respuesta directamente en lugar de doce cláusulas IF, lo cual es más corto, más rápido de escribir y más fácil de mantener.

Arrays 1-D

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
OUTPUT Names[3]

Procesa cada elemento con un bucle FOR:

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

Arrays 2-D (array 2D)

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99

El primer índice es la fila, el segundo la columna. Usa bucles anidados para visitar cada celda. Usa 1-D para una secuencia única, 2-D para dos dimensiones naturales (una cuadrícula, filas × columnas).

Operaciones comunes

Una búsqueda lineal 线性查找 revisa cada elemento hasta encontrarlo:

FOR i ← 1 TO n
    IF A[i] = Target THEN
        OUTPUT "Found at ", i
    ENDIF
NEXT i

Para encontrar una suma, conteo, máximo o mínimo, establece una variable acumuladora luego escanea a través:

Max ← A[1]
FOR i ← 2 TO n
    IF A[i] > Max THEN
        Max ← A[i]
    ENDIF
NEXT i

Un ordenamiento burbuja 冒泡排序 coloca una array en orden; pasa a través ella comparando cada par adyacente e intercambiando cualquier par fuera de orden; repite los pasos hasta que un paso no realice intercambios.

El Examen 2 pide estos algoritmos tanto en pseudocódigo como en pasos en palabras, y a veces en su forma "eficiente":

• Valor más grande: establece Largest al primer elemento; para cada elemento restante, si es mayor que Largest, guárdalo en Largest; después del bucle emite Largest. Para la posición del más grande, mantén una segunda variable que almacene el índice cada vez que Largest cambie.
• Búsqueda lineal devolviendo una posición: establece FoundAt ← -1 antes del bucle (un valor que nunca puede ser un índice válido, por lo que significa "no encontrado"); recorre la array; cuando el elemento coincida, guarda el índice y sal del bucle; después del bucle verifica FoundAt.
• Contar o emitir los elementos no vacíos: compara cada elemento con el marcador de elemento no utilizado ("" o -1) y cuenta o emite solo aquellos que difieran.
• Eliminar un elemento: encuentra su índice mediante una búsqueda lineal; mueve cada elemento posterior un lugar hacia el inicio, cerrando el espacio; marca el último elemento como no utilizado (o disminuye el conteo).
• Insertar en una array ordenada: encuentra el primer índice cuyo elemento sea mayor; mueve ese elemento y cada siguiente un lugar hacia el final; almacena el nuevo valor en el espacio abierto.
• Ordenamiento burbuja eficiente: una bandera Swapped para que los pasos se detengan tan pronto como un paso no haga ningún intercambio, y un límite superior que disminuye en uno cada paso porque el valor más grande ya ha llegado al final.

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

Las puntuaciones son por el bucle exterior que se repite hasta que no hay intercambios, la bandera establecida dentro del IF, el intercambio de tres líneas con una variable temporal, y el límite decreciente. Un ordenamiento en "pasos" (refinamiento paso a paso) es: repetir hasta ordenar; en cada paso comparar pares adyacentes; intercambiar un par fuera de orden; después de cada paso el valor no ordenado más grande está al final. Dos arrays 1-D de registros o de datos paralelos se procesan con un bucle y un índice; una array 2-D necesita un bucle anidado, el exterior sobre filas y el interior sobre columnas, y una búsqueda en una fila fija el índice de fila y itera sobre la columna.

Un archivo 文件 es datos almacenados en almacenamiento secundario 辅助存储器, mantenidos entre ejecuciones del programa. Las variables en RAM desaparecen cuando termina el programa, por lo que para guardar datos permanentemente (puntuaciones altas, registros, configuraciones) el programa escribe en un archivo. Los archivos también permiten que los programas compartan datos y reinicien desde un estado guardado.

Un archivo de texto 文本文件 contiene una o más líneas de caracteres legibles; los programas leen y escriben archivos de texto línea por línea. Abra un archivo antes de usarlo y cierre después:

OPENFILE "data.txt" FOR READ      // or FOR WRITE, FOR APPEND
WHILE NOT EOF("data.txt") DO
    READFILE "data.txt", LineString
    OUTPUT LineString
ENDWHILE
CLOSEFILE "data.txt"

EOF verifica el final del archivo 文件结束 antes de leer. Para escribir:

OPENFILE "log.txt" FOR WRITE
FOR i ← 1 TO 100
    WRITEFILE "log.txt", "Event " & i
NEXT i
CLOSEFILE "log.txt"

Siempre cierre cada archivo — de lo contrario las escrituras en búfer pueden perderse y otros programas podrían quedar bloqueados.

Por qué archivos (dos puntos): los datos se mantienen después de que el programa termina, por lo que están disponibles la próxima vez que se ejecuta; puede compartirse con otros programas; y puede contener más de lo que cabe en memoria. La característica de un archivo de texto que permite a un programa procesarlo es que es una secuencia de líneas, leídas una tras otra desde el inicio. Los tres modos: READ para leer desde el inicio; WRITE para crear un nuevo archivo, lo cual elimina cualquier contenido existente, por lo que no puede usarse para añadir a un archivo; APPEND para añadir líneas al final de un archivo existente. Verifique EOF antes de cada lectura, y abra el archivo solo una vez, incluso cuando varios módulos lo utilicen.

Ejemplo resuelto. Escriba pseudocódigo para un procedimiento LastLines(FileName : STRING) que muestre las últimas tres líneas de un archivo de texto, en orden.

PROCEDURE LastLines(BYVAL FileName : STRING)
    DECLARE LineX, LineY, LineZ : STRING
    LineX ← ""
    LineY ← ""
    LineZ ← ""
    OPENFILE FileName FOR READ
    WHILE NOT EOF(FileName) DO
        LineX ← LineY
        LineY ← LineZ
        READFILE FileName, LineZ
    ENDWHILE
    CLOSEFILE FileName
    OUTPUT LineX
    OUTPUT LineY
    OUTPUT LineZ
ENDPROCEDURE

Cada nueva línea empuja las tres anteriores, por lo que al finalizar el archivo las tres variables contienen sus últimas tres líneas; un archivo con menos líneas genera cadenas vacías. Para mostrar las cinco primeras líneas, cuente las líneas leídas y detenga el bucle en cinco o en EOF, lo que ocurra primero; un archivo vacío se detecta porque EOF mar TRUE inmediatamente después de abrirlo.

Campos en una línea. Un archivo de texto contiene cadenas, por lo que un registro se escribe como una línea con sus campos unidos por un carácter separador 分隔符, y cada número o booleano se convierte con NUM_TO_STR (y se lee de nuevo con STR_TO_NUM, o comparando con "TRUE"). Elija un separador que nunca aparezca en los datos: una coma o | para nombres y números, nunca un espacio si un nombre podría contener uno. Si un campo puede contener cualquier carácter, el separador puede confundirse con los datos; la solución es poner cada campo en su propia línea, o escribir la longitud del campo antes de este. Un elemento por línea es simple de leer de nuevo pero usa más líneas y hace que un registro sea menos evidente como unidad. Leer un archivo cuyas líneas están en un orden conocido (ascendente según un ID) permite que la búsqueda se detenga tan pronto como se lee un ID mayor, en lugar de leer hasta el final. Un archivo de guardado que se crea cada vez que se guarda el juego necesita un nombre de archivo significativo, por ejemplo el nombre del jugador y la fecha y hora, para que cualquier guardado anterior pueda restaurarse.

Un Tipo de Dato Abstracto 抽象数据类型 (TDA) es una colección de datos más operaciones sobre ellos, definido por qué hace, no cómo se almacena. El usuario trabaja solo a través de las operaciones; la implementación está oculta, por lo que puede cambiar sin afectar el código que usa el TDA. Conozca tres: pila, cola, lista enlazada.

La definición de un punto: un TDA es una colección de datos junto con un conjunto de operaciones sobre esos datos. Una pila, una cola, una lista enlazada, un árbol binario y un array son todos TDAs. Para justificar una elección: una cola cuando los elementos deben manejarse en el orden en que llegaron (trabajos de impresión, pulsaciones de tecla, clientes en una tienda), porque es primero en entrar, primero en salir; una pila cuando el elemento más reciente debe manejarse primero (deshacer, retroceder en páginas web, invertir un orden, las direcciones de retorno de llamadas anidadas), porque es último en entrar, primero en salir; una lista enlazada cuando los elementos se insertan y eliminan frecuentemente en medio de una secuencia ordenada, porque solo cambian los punteros y nada tiene que desplazarse. Para comparar una pila y una cola: ambas son estructuras lineales de elementos con un orden, ambas se implementan con un array y punteros, y ambas necesitan una verificación de lleno antes de agregar y de vacío antes de eliminar; una pila tiene un puntero y agrega y elimina en el mismo extremo, una cola tiene dos punteros y agrega en un extremo y elimina en el otro.

Pila

Una pila 栈 funciona en orden LIFO 后进先出 (Last In, First Out). Operaciones: empujar 入栈 (agregar en la parte superior), sacar 出栈 (quitar de la parte superior), inspeccionar (ver la parte superior), y pruebas de vacío/lleno. Usos: historial de deshacer, direcciones de retorno de llamadas de función, análisis de expresiones, retroceso.

Ejemplo resuelto. Una pila de caracteres contiene, desde la parte inferior, 'P', 'N', 'Z', 'X', 'Y', 'W', con el puntero de parte superior de la pila en 'W' (ubicación de memoria 202 de 200–207). Se realizan las operaciones POP, POP, PUSH 'A', PUSH 'B', POP. ¿Qué hay en la pila y dónde apunta el puntero?

Los dos pops eliminan 'W' luego 'Y'; los pushes añaden 'A' luego 'B' en su lugar; el último pop elimina 'B'. La pila ahora contiene 'P', 'N', 'Z', 'X', 'A' y el puntero está en 'A', ubicación 203. El valor que ha estado en la pila más tiempo es el elemento inferior, 'P'; como máximo cinco pops adicionales son posibles antes de que la pila esté vacía, y un pop sobre una pila vacía es un error, por eso Pop() verifica primero si está vacía. Una función Push() que retorna TRUE en caso de éxito verifica primero si el puntero está en la parte superior del array (llena) y retorna FALSE si es así. Los elementos del array no necesitan inicialización previa al uso, porque solo el punter indica cuáles están en uso.

Cola

Una cola 队列 funciona en orden FIFO 先进先出 (First In, First Out). Operaciones: enqueue 入队 (añadir al final), dequeue 出队 (eliminar desde el principio), y pruebas para vacío/lleno. Usos: colas de impresión, programación, búsqueda en anchura, buffering.

Para describir añadir un elemento: verificar que la cola no esté llena; almacenar el elemento en la posición indicada por el punter de fin de cola; incrementa el punter de fin (y el contador). Para describir eliminar: verificar que la cola no esté vacía; leer el elemento en el punter de inicio; incrementa el punter de inicio (y decrementa el contador). Establece la convención que usas: si el punter de fin marca el siguiente espacio libre, que los punters de inicio y fin sean iguales significa que la cola está vacía; si marca el último elemento, punters iguales significan un solo elemento. En una cola lineal el punter de inicio solo se mueve hacia adelante, por lo que las celdas detrás de él se desperdician; eso es lo que corrige la cola circular de abajo. Las dos características de una cola a mencionar: los elementos se añaden al final y se eliminan desde el principio, así que el primer elemento añadido es el primero en eliminarse.

Lista enlazada

Una lista enlazada 链表 almacena datos como una secuencia de nodos 节点. Cada nodo contiene un valor y un puntero 指针 al siguiente nodo; un punter de cabeza marca el inicio, y el punter del último nodo es un sentinela (ej. NULL). Operaciones: insertar, eliminar, buscar y recorrer 遍历 (visitar cada nodo en orden). Su ventaja frente a un array es la inserción/eliminación barata (solo ajustar punters); su desventaja es el acceso aleatorio lento (debes seguir los punters desde la cabeza).

Añadir un nodo en orden (cuatro puntos): recorre la lista desde la cabeza, siguiendo los punters, hasta encontrar el nodo anterior a la posición deseada (el último cuyo valor sea menor); toma un nodo libre y almacena el nuevo valor en él; establece el punter del nuevo nodo para que apunte a la dirección a la que apuntaba el nodo anterior; establece el punter del nodo anterior para que apunte al nuevo nodo. Si el nuevo valor debe ir al principio, se modifica el punter de cabeza en su lugar. Eliminar un nodo: encuentra el nodo anterior y establece el punter de ese nodo para que apunte a la dirección a la que apuntaba el nodo eliminado, saltándolo; el nodo liberado vuelve a la lista de nodos libres. Comparado con un array 1-D, insertar o eliminar en una lista enlazada no requiere desplazar otros elementos, y la lista puede crecer hasta agotar la memoria; el coste es el punter adicional almacenado con cada elemento, y llegar al ⟨$n$⟩-ésimo elemento implica seguir ⟨$n$⟩ punters, ya que no hay índice directo.

Pila usando un array

Almacena elementos en Stack[1:MaxSize] con un entero Top (0 cuando está vacía).

• Push(x): si Top = MaxSize la pila está llena (overflow 溢出); sino Top ← Top + 1; Stack[Top] ← x.
• Pop(): si Top = 0 la pila está vacía (underflow 下溢); sino retorna Stack[Top] y Top ← Top - 1.

Cola usando un array circular

Una cola simple permite que Front y Rear se marchen al final, desperdiciando el inicio. La solución es un array circular 循环数组 — cuando un punter llega a MaxSize, se reinicia a 1:

• Enqueue(x): verificar lleno; de lo contrario Rear ← (Rear MOD MaxSize) + 1; Queue[Rear] ← x.
• Dequeue(): verificar vacío; de lo contrario devolver Queue[Front] y Front ← (Front MOD MaxSize) + 1.

Rastrear un contador separado para distinguir entre vacío y lleno.

El algoritmo para el puntero final, en palabras: si el contador es igual al tamaño, informar que la cola está llena y detenerse; de lo contrario, sumar uno al puntero final; si ahora supera el último índice, establecerlo en el primer índice; almacenar el elemento allí y sumar uno al contador. Las declaraciones que una respuesta de "describir la declaración e inicialización" de cinco puntos enumera: el array con su tamaño y tipo de elemento; un puntero frontal y un puntero final, ambos inicializados al primer índice (o el frontal al primer índice y el final al siguiente espacio libre); y un contador de elementos, inicializado a $0$.

Por ejemplo, con MaxSize = 6: si Rear = 5, entonces (5 MOD 6) + 1 = 6, por lo que el próximo elemento va en la celda 6; si Rear = 6, entonces (6 MOD 6) + 1 = 1, por lo que el puntero vuelve a enrollarse a la celda 1.

Lista enlazada usando un array

Utilice un array de registros, cada uno con un índice de Next:

TYPE TNode
    DECLARE Value : INTEGER
    DECLARE Next : INTEGER     // index of the next node, or -1 for end
ENDTYPE

DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER         // index of first node, -1 if empty
DECLARE FreeListHead : INTEGER // first available free node

Una lista de espacios libres encadena las casillas no utilizadas, así como la lista de datos encadena las utilizadas. Para insertar: tome una casilla de FreeListHead, establezca el valor del nuevo nodo y su Next, y actualice el Next del nodo anterior (o su Head). Para eliminar: desvincule el nodo y devuelva su casilla a la lista de espacios libres. Esto ofrece la flexibilidad de una estructura enlazada con la asignación estática de un array.

Ejercicio resuelto. Una lista enlazada se mantiene en un array de Data y un array de Pointer, con Start apuntando al índice 1. La lista es 1 → 3 → 4 (el índice 1 contiene D40, el índice 3 contiene D32, el índice 4 contiene D11, cuyo puntero es $\emptyset$); la lista de espacios libres comienza en el índice 2 y continúa 2 → 5. Inserte D6 entre D32 y D11.

Tome el primer nodo libre, índice 2, y establezca FreeStart a su puntero, 5; almacene D6 en Data[2]; establezca Pointer[2] al valor Pointer[3] contenido, que es 4; establezca Pointer[3] a 2. La lista se lee 1 → 3 → 2 → 4 y la lista de espacios libres es 5 → $\emptyset$. La respuesta a "cómo puede implementarse la lista enlazada" son exactamente estas partes: un array (o array de registros) para los datos, un array paralelo para los punteros que contienen índices, un puntero de inicio, un puntero de lista de espacios libres y un valor nulo como $-1$ para el final.

Ejemplo resuelto. Una cola circular se almacena en un array de tamaño 5 (índices del 0 al 4) con Front = 3, Rear = 3 y un elemento almacenado. Se añaden dos elementos y luego se eliminan dos. ¿Dónde están los punteros y por qué usar una cola circular? Cada movimiento usa (pointer + 1) MOD size, así que los punteros envuelven. Añadir dos veces mueve Rear: $3 \rightarrow 4$, luego $4 \rightarrow 0$ (porque $(4+1) \bmod 5 = 0$), por lo que Rear = 0 y hay tres elementos almacenados. Eliminar dos veces mueve Front de la misma manera: $3 \rightarrow 4$, luego $4 \rightarrow 0$, dejando Front = 0 y un elemento. El envoltorio es el punto principal: en una cola de array lineal, los punteros avanzan hacia el final y el espacio liberado en la parte delantera se desperdicia incluso cuando la cola está vacía. Recuerda que una cola elimina desde el Frontal (delantero) y añade en el Rear (trasero); una pila usa un solo puntero para ambas operaciones.

Una pregunta de definición se califica según palabras fijas. Aprenda estas exactamente.

• Elige la estructura de datos adecuada y justifícala (un registro para campos mixtos, un array 2-D para una cuadrícula).
• Conoce cómo implementar una pila, cola y lista enlazada con un array y punteros (top; front/rear; next).
• Distingue un TDA (su comportamiento) de su implementación (array más punteros).

Errores comunes

• Una declaración de registro sin ENDTYPE, o campos sin tipos. Cada campo es una línea de DECLARE con un tipo.
• Leer más allá del final de un archivo, o escribir con WRITE cuando el archivo debe mantener su contenido. Prueba EOF antes de cada lectura; usa APPEND para añadir.
• Escribir un número en un archivo de texto sin convertirlo. Un archivo contiene cadenas: NUM_TO_STR fuera, STR_TO_NUM dentro.
• Olvidar las comprobaciones. Push y enqueue prueban si está llena primero; Pop y dequeue prueban si está vacía primero, y la respuesta lo indica.
• Perder el resto de la lista al insertar un nodo. Establece el puntero del nuevo nodo al nodo siguiente anterior antes de cambiar el puntero del nodo anterior.
• Una búsqueda lineal que nunca dice "no encontrado". Inicializa la posición a $-1$ y compruébala después del bucle.