Download Estructura de Datos

UNIVERSIDAD AUTONOMA DE GUERRERO
UNIDAD ACADEMICA DE MATEMATICAS
Academia de Computación
No. 001
Apuntes de
ESTRUCTURA
DE
DATOS
Serie: Material de Apoyo a la Licenciatura en
Matemáticas (Área: Computación).
Estos apuntes fueron desarrollados a partir de la experiencia obtenida impartiendo la materia y la bibliografía citada al final del mismo;
su propósito es servir como apoyo al curso de Estructura de Datos
que se imparte en la Licenciatura en Matemáticas (Área:
Computación). Su publicación no persigue fines de lucro, está
destinada al uso interno en la Unidad Académica de Matemáticas de
la Universidad Autónoma de Guerrero.
agosto de 2004
Edgar Altamirano
Estructura de Datos
pag. 2
Contenido.
Introducción.
2
Primera parte: Estructuras Elementales.
1. Estructuras Elementales de Datos.
4
Segunda parte: Estructuras Secuenciales.
2. Arreglos.
3. Pilas y Colas.
22
35
Tercera Parte: Estructuras Ligadas.
4. Listas.
5. Arboles.
44
63
Bibliografía.
72
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 3
Introducción.
Los datos proporcionados a la computadora se pueden representar dentro de
la computadora en múltiples formas, tal representación se conoce como
estructura de los datos; desde el punto de vista de la programación podemos
entender una estructura de datos como una colección de datos cuya
organización se caracteriza por las funciones de acceso que se usan para
almacenar y acceder a elementos individuales de datos. Las estructuras de
datos las podemos organizar para su estudio en estructuras elementales (su
manipulación y representación se ha venido estandarizando en los lenguajes
de programación y pueden casi siempre manejarse con instrucciones a nivel
de lenguaje de máquina en forma directa) y estructuras compuestas que se
construyen a partir de las estructuras elementales y cuya manipulación
requiere del ingenio de los programadores; el estudio de las estructuras
compuestas se puede a su vez dividir en estructuras secuencials ó ligadas
según que los datos estén almacenados consecutivamente (ocupando siempre
espacios consecutivos de memoria) ó en forma 'ligada' (pueden no ocupar
espacios consecutivos pero siempre existirá una 'liga' entre ellos.
Número Enteros
Números Reales
Elementales
Caracteres
Valores Lógicos
Estructuras
de Datos
Punteros
Arreglos
Lineales
Compuestas
Listas
No Lineales
Archivos
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 4
1. Estructuras elementales de datos.
En éste capítulo se describen las representaciones básicas de las estructuras
elementales en la memoria de la computadora. Estas estructuras forman una
base para la composición y discusión de estructuras más complejas que se
analizarán en los siguientes capítulos.
1.1. Representación de Números Enteros.
Un número entero es cualquier número que pertenece al conjunto definido
como:
Entero = {... , -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, ...}
Ejemplos de números enteros : -8, -72, 0, 4, 100
Para representar números en la computadora digital se utiliza el sistema de
numeración binaria ó de base 2 porque la tecnología que se usa para la
memoria permite solamente el uso de dos dígitos: 0 y 1.
En la computadora se representan dos clases de números enteros: con signo
(se asume que todos los números tienen magnitud 0 ó son positivos) y sin
signo (los números pueden ser positivos ó negativos y el signo del número
también tiene que representarse).
Números Enteros Sin Signo.
(a). Método de Representación Binaria.
Un número entero sin signo puede representarse por una secuencia de dígitos
binarios de la forma:
dn dn-1 ... d2 d1 d0
su valor ó magnitud se determina por la suma de:
dn bn + dn-1 bn-1 + ... + d2 b2 + d1 b1 + d0 b0
donde b es la base o raíz del sistema.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 5
Ejemplos.
La magnitud del número 12410 es la suma de los términos:
1 x 102 + 2 x 101 + 4 x 100
La magnitud del número 101112 es la suma de los términos :
1 x 24 + 0 x 2 3 + 1 x 22 + 1 x 21 + 1 x 20
Para trasladar un número entero sin signo a su correspondiente representación
binaria se puede usar el algoritmo conocido como de divisiones sucesivas
entre dos :
Ejemplo. Encontrar la representación binaria del número 16
8
2 16
0
2
4
8
0
2
2
4
0
2
1
2
0
2
0
1
1
.
..
16 = 10000
10
2
Para convertir un número de su representación binaria a decimal se puede
llevar a cabo encontrando su magnitud del modo siguiente:
Ejemplo. Encontrar la representación decimal del número cuya representación binaria es 100002
100002 = 1 x 24 + 0 x 23 + 0 x 22 + 0 x 21 + 0 x 20
100002 = 16 + 0 + 0 + 0 + 0
100002 = 1610
En el sistema de números binarios cada posición del bit representa una
potencia de dos :
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
Sistema de Números Binarios
pag. 6
Sistema Decimal
20
21
22
23
24
25
26
27
28
...
1
10
100
1,000
10,000
100,000
1,000,000
10,000,000
100,000,000
...
Debido a lo anterior, una cadena de bits de longitud n servirá para representar
un entero no negativo entre 0 y 2n-1. A esta propiedad la denominamos
rango de representación decimal.
Ejemplo. Una variable de tipo byte sin signo, utiliza un byte para el almacenamiento de la información, por lo tanto, su rango de representación decimal
es : 0 a 28-1 = 255.
(b). Convención BCD (Binary Coded Decimal).
Se utilizan cuatro bits para representar cada dígito decimal entre 0 y 9 :
0
1
2
9
0000
0001
0010
1001
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
así, una hilera de longitud arbitraria, se puede dividir en grupos de cuatro bits
consecutivos, donde cada grupo representa un dígito decimal; ésta representación tiene la ventaja de permitir realizar las operaciones aritméticas directamente debido a su interface directa con la representación decimal.
Ejemplo. Represente el número entero 26 mediante la convención BCD.
2610 = 0010 01102
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 7
Ejemplo. Escriba un programa que sirva para encontrar la representación
binaria de un número entero sin signo utilizando el algoritmo de divisiones
sucesivas entre dos.
/*------------------------------------------------*/
/* db.c */
/* Muestra la representacion binaria de un numero */
/* decimal entre 1 y 255. */
/*------------------------------------------------*/
#include <stdio.h>
#include <conio.h>
/*------------------------------------------------*/
void main(void)
{
int i,j, binario, decimal;
char digitos[20];
clrscr();
printf("CONVIERTE DECIMAL A BINARIO\n");
do {
printf("(Rango permitido : 1 a 255)\n");
printf("Numero Decimal : ");
scanf("%d", &decimal);
} while (decimal < 1 || decimal > 255);
i = 0;
while (decimal > 0) {
binario = decimal % 2; /* residuo de la division entera */
decimal = decimal / 2; /* cociente de la division */
digitos[i++] = binario;
}
printf("Numero Binario : ");
for (j = --i; j >= 0; j--)
printf("%1d", digitos[j]);
printf("\n");
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 8
Números enteros con signo.
Para representar en la computadora cuando un número entero es positivo ó
negativo, se han establecido convenciones como las siguientes :
(a). Convención de Signo y Magnitud.
Se escribe el signo "+" ó "-" junto a la magnitud del número. En la
computadora se utiliza generalmente el dígito binario de la extrema izquierda
para denotar el signo y los restantes para denotar la magnitud. Para representar la magnitud se utiliza el sistema de números binarios.
Ejemplo. Si Consideramos el caso de poder utilizar solamente cuatro
dígitos binarios para la representación tendríamos las posibilidades
siguientes:
Número Positivo
+0
+1
+2
+3
+4
+5
+6
+7
Signo y Magnitud Número Negativo Signo y Magnitud
0 000
-0
1 000
0 001
-1
1 001
0 010
-2
1 010
0 011
-3
1 011
0 100
-4
1 100
0 101
-5
1 101
0 110
-6
1 110
0 111
-7
1 111
(b). Convención del Complemento a uno.
Los números positivos se representan igual que con la convención de signo y
magnitud pero los números negativos se obtienen invirtiendo los bits de su
representación positiva.
Ejemplo. Si Consideramos el caso de poder utilizar solamente cuatro dígitos
binarios para la representación tendremos las posibilidades siguientes :
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
Número Positivo
+0
+1
+2
+3
+4
+5
+6
+7
pag. 9
Complemento a 1 Número Negativo Complemento a 1
0 000
-0
1 111
0 001
-1
1 110
0 010
-2
1 101
0 011
-3
1 100
0 100
-4
1 011
0 101
-5
1 010
0 110
-6
1 001
0 111
-7
1 000
(c). Convención del Complemento a dos.
Esta convención reconoce que el número cero es único y debe por lo tanto
tener una representación única. Para representar un número en complemento a
dos se parte del principio de asignar la mitad de las combinaciones posibles a
los números positivos y la otra mitad a los negativos. Se considera el número
0 como positivo.
Ejemplo. Si Consideramos el caso de poder utilizar también solamente
cuatro dígitos binarios para la representación tendríamos las posibilidades
siguientes :
Número Positivo
+0
+1
+2
+3
+4
+5
+6
+7
Complemento a 2 Número Negativo Complemento a 2
0 000
-8
1 000
0 001
-7
1 001
0 010
-6
1 010
0 011
-5
1 011
0 100
-4
1 100
0 101
-3
1 101
0 110
-2
1 110
0 111
-1
1 111
Los números positivos se representan igual que con la convención de signo y
magnitud siempre y cuando no rebasen (overflow) la capacidad de representación; pero la representación de los números negativos se obtiene mediante la
expresión : C = b - |Número|, donde C es la representación del número
en "n" dígitos de la base "b" y |Número| es la magnitud (valor absoluto) del
número negativo.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 10
Ejemplo. Represente el número 1 como negativo en complemento a dos,
utilizando cuatro dígitos binarios.
C = bn - |Número|
(b10)n = (210)4 = 1610 = 100002
|Número| = 110 = 00012
 C = 100002 - 00012 = 11112
Nota. Conversión decimal a binario :
8
2 16
0
2
4
8
0
2
2
4
0
2
1
2
0
2
0
1
1
.
..
16 = 10000
10
2
Resta binaria: 100002 - 00012 = 11112
0
1

1
(10)
0
0
1
(10)
0
0
1
(10)
0
0
(10)
0
1

0
1
1
1
1
Otra manera más sencilla de representar números negativos en complemento a
dos, es encontrar su representación positiva en el sistema de números
binarios, invertirla (igual que en complemento a uno) y sumarle un '1'.
Ejemplo. Represente el número uno como negativo en complemento a dos,
utilizando cuatro dígitos binarios:
Representación binaria :
Complemento a uno :
Sumar un '1' :
0001
1110
+ 0001

Rep. en Compl. a dos :
1111
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 11
1.2. Representación de Números Reales.
Notación de Punto Fijo.
Un número real, en cualquier base R puede representarse como:
AR =  ( An An-1 An-2 ... A1 A0 . A-1 A-2 ... A-(m+1) A-m )
esta notación se llama de punto fijo y tiene la desventaja de requerir una gran
cantidad de bits para representar cantidades como 0.00000000000827 ó
18700000000000.0; por ejemplo, para obtener una precisión de 27 dígitos
decimales se necesitarán aproximadamente 90 dígitos binarios.
El formato para almacenar éste tipo de números es:
POSICION DEL
PUNTO DECIMAL
DATO
NUMERICO
Notación de Punto Flotante.
Un número real, en cualquier base R se representa como:
 . f-1 f-2 f-3 ... f-m x RE
donde f-1 f-2 f-3 ... f-m es llamada la parte fraccionaria ó mantisa, "E" es
un número entero conocido como exponente y "R" es la base.
Ejemplo. El número 3.141592 se puede representar como :
3.141592 = + 0.3141592 x 10+1
Para representar un número real en notación de punto flotante, el formato más
usado en los lenguajes de programación es :
S
EXPONENTE
MANTISA
MANTISA
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 12
en donde S es el signo de la mantisa, EXPONENTE es el exponente
representado como número entero en complemento a dos y MANTISA es la
mantisa representada como número entero en magnitud y signo.
Para aumentar la precisión de un número es posible asignar optativamente
más palabras de computadora para la mantisa, llamándose entonces número
de doble precisión:
S
EXPONENTE
MANTISA
MANTISA
MANTISA
MANTISA
Ejercicios.
1. Considere el caso de utilizar nueve dígitos binarios para la representación
de números enteros :
a). En notación de complemento a dos, ¿cuál es el mayor número positivo
que se puede representar y cuál es el menor número negativo ?
b). Igual al inciso (a) pero usando la convención de signo y magnitud.
c). Igual al inciso (a) pero usando la notación de complemento a uno.
d). Para la notación en complemento a dos, represente los números 8 y 19
como negativos utilizando la expresión :
C = bn - | número |
2. Para representar números reales del tipo :
 0 . f-1 f-2 f-3 ... f-m x RE
se utiliza el siguiente formato :
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
mantisa
bit :
0
pag. 13
exponente
11 12
15
la mantisa está representada en magnitud y signo y el exponente en complemento a dos.
a). ¿ cuál es el mayor número positivo que se puede representar ?
b). ¿ el mayor número negativo ?
c). ¿ el menor número positivo ?
d). ¿ el menor número negativo ?
e). ¿ el rango de representación ?
f). ¿ la precisión de la mantisa en dígitos decimales ?
1.3 Representación de cadenas de caracteres.
Representación de caracteres.
Entendemos por caracter, la expresión literal de algún elemento tomado de un
alfabeto ó conjunto de signos. Cada caracter se puede representar con un
patrón de bits diferente que lo identifica. Entre los fabricantes de
computadoras se ha generalizado que un conjunto de caracteres se codifique
en secuencias de bits con longitud fija. En general tenemos que x = 2
caracteres se pueden representar utilizando secuencias de bits de longitud n.
Por tanto, con n = 6, 7 y 8 podemos codificar hasta 64, 128 y 256 caracteres
respectivamente.
Algunos de los códigos más importantes que actualmente se emplean para la
representación de letras, números y símbolos especiales son : ASCII (
American Standard Code for Information Interchange) el cual requiere 8 bits
para representar cualquier caracter; BCD (Binary Coded Decimal) que
requiere de 6 bits para representar cualquiera de sus 64 caracteres; y
EBCDIC (Extended BCD Interchange Code) que es un código de 8 bits.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 14
Ejemplo. Representación de letras y números para los códigos BCD,
EBCDIC y ASCII.
Símbolo
BCD
EBCDIC
ASCII
blanco
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
0
1
2
3
4
5
6
7
8
9
110 000
010 001
010 010
010 011
010 100
010 101
010 110
010 111
011 000
011 001
100 001
100 010
100 011
100 100
100 101
100 110
100 111
101 000
101 001
110 010
110 011
110 100
110 101
110 110
110 111
111 000
111 001
000 000
000 001
000 010
000 011
000 100
000 101
000 110
000 111
001 000
001 001
0100 0000
1100 0001
1100 0010
1100 0011
1100 0100
1100 0101
1100 0110
1100 0111
1100 1000
1100 1001
1101 0001
1101 0010
1101 0011
1101 0100
1101 0101
1101 0110
1101 0111
1101 1000
1101 1001
1110 0010
1110 0011
1110 0100
1110 0101
1110 0110
1110 0111
1110 1000
1110 1001
1111 0000
1111 0001
1111 0010
1111 0011
1111 0100
1111 0101
1111 0110
1111 0111
1111 1000
1111 1001
0010 0000
0100 0001
0100 0010
0100 0011
0100 0100
0100 0101
0100 0110
0100 0111
0100 1000
0100 1001
0100 1010
0100 1011
0100 1100
0100 1101
0100 1110
0100 1111
0101 0000
0101 0001
0101 0010
0101 0011
0101 0100
0101 0101
0101 0110
0101 0111
0101 1000
0101 1001
0101 1010
0011 0000
0011 0001
0011 0010
0011 0011
0011 0100
0011 0101
0011 0110
0011 0111
0011 1000
0011 1001
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 15
Representación de Cadenas de Caracteres.
Una secuencia de caracteres ó cadena, se representa en memoria generalmente utilizando una secuencia de localizaciones de almacenamiento. Las
cadenas pueden ser de longitud fija, longitud cambiante y longitud variable.
(a). Longitud Fija.
La cantidad de almacenamiento requerida por una cadena de longitud fija se
conoce al momento de crear la cadena. Por ejemplo, en PL/I :
declare S character (6) initial ('*A1');
en una computadora con palabras de cuatro bytes, implica la creación de la
cadena :
*
A
1
''
''
''
| no se usa
|
(b). Longitud Cambiante.
Para una cadena de longitud cambiante, su longitud máxima se conoce
también en el momento de su creación; en ése momento se dispone de
suficiente espacio de almacenamiento para guardar hasta un máximo número
de caracteres junto con un campo que contiene la longitud actual de la cadena:
declare S character (6) varying initial ('*A1');
resulta en la siguiente distribución de almacenamiento:
3
*
A
1
| disponible
|
(c). Longitud Variable.
La cadena de longitud variable es más dinámica y poderosa, en este caso, en
el momento de la creación no se necesita conocer ni su longitud precisa ni su
máxima longitud; la estructura de almacenamiento para este tipo de cadena se
maneja en dos formas: con delimitadores y descriptores de cadena :
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 16
Ejemplo. Longitud variable con delimitadores :
^
*
A
1
^
| no se usa
|
Ejemplo. Longitud variable con descriptores de cadena :
3
[22]
*
A
1
| no se usa
|
1.4 Valores Lógicos.
Una entidad de datos lógica es una estructura primitiva de datos que puede
asumir dos tipos de valores: verdadero y falso. La representación en memoria
de valores lógicos depende directamente del traductor de lenguaje que
procese el programa y de la máquina para la cual se diseñó el traductor.
El modo más obvio y eficiente que puede ser aplicado para almacenar datos
lógicos es la utilización de un bit. Si el bit está prendido (1) representa el
valor verdadero, y si está apagado (0), el valor falso.
Sin embargo la mayoría de las máquinas no disponen de instrucciones para
accesar un bit determinado de la memoria, consecuentemente, se adoptan
otras representaciones, por ejemplo, asignar una palabra completa de memoria
representando los valores lógicos con todos los bits prendidos ó apagados :
TODOS LOS BITS APAGADOS
FALSO
TODOS LOS BITS PRENDIDOS
VERDADERO
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 17
1.5 Apuntadores.
Un apuntador ó puntero es una referencia a una estructura de datos. Su
característica más importante es que aporta un método homogéneo para
referenciar cualquier estructura de datos sin importar su tipo ó complejidad.
Otra característica muy importante es la de que permiten rápidas inserciones y
eliminaciones de elementos en una estructura de datos.
APUNTADOR
ESTRUCTURA DE
DATOS
La dirección contenida en un apuntador puede referenciar una estructura de
datos en dos modos: dirección absoluta ó dirección relativa. La dirección
absoluta implica que el valor contenido en el apuntador es una localización
absoluta de memoria en la cual puede comenzar a residir una estructura de
datos. Una dirección relativa es en cambio un valor comprendido para una
región de memoria que tiene una localización base. Por ejemplo, si el valor de
un apuntador relativo es 5 y la localización base para el área de datos de un
programa es 7627, entonces la dirección real del apuntador es 7627 + 5 =
7632.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 18
1.6. El Código ASCII en el IBM-PC.
El IBM PC utiliza el código ASCII extendido a 8 bits; por lo tanto se pueden
representar 256 caracteres diferentes; éstos caracteres son :
a). Los primeros 32 caracteres (0 a 31) son caracteres de control como return,
escape, nulo; son caracteres no imprimibles.
b). Los siguientes caracteres (32 a 127) son letras, dígitos numéricos y
símbolos de puntuación normal; son caracteres imprimibles.
c). La última parte (128 a 255) son caracteres especiales de otros alfabetos y
algunos caracteres gráficos, los cuales pueden obtenerse en la pantalla
utilizando el teclado numérico de la derecha del teclado mientras se mantiene
pulsada simultáneamente la tecla ALT. Por ejemplo, Alt-224 produce el
caracter griego ''; son caracteres imprimibles.
El teclado del IMB PC genera el código ASCII para letras, números y
símbolos de puntuación. Sin embargo, existen teclas (F1, F2, ...) y
combinaciones de teclas (Ctrl-F1, Alt-PgUp, ...) no representadas en el
código ASCII. Para éstos casos el IBM PC utiliza otro byte para formar lo
que se conoce como código extendido de dos bytes : el primer byte es 0 y el
segundo es el código de la tecla ó combinación de teclas.
Cuando se oprime una tecla del conjunto normal de caracteres, se genera el
código ASCII correspondiente.
Cuando se oprime una tecla ó combinación de teclas que no forman parte del
conjunto normal de caracteres, se generan dos códigos, el primero es un 0 y el
segundo es el código extendido correspondiente dentro del buffer del teclado.
El buffer del teclado es un área de almacenamiento temporal donde se
almacenan los códigos de las teclas oprimidas hasta que son leídas por un
programa.
Un programa que sea capaz de entender cuáles teclas se han pulsado, debe
revisar si el primer caracter recibido es un cero, si lo es, se trata de una tecla
especial ó combinación de teclas y se debe leer el siguiente caracter. Si el
primer caracter no es cero, se trata entonces de una Tecla normal y debe
procesarse como tal.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
/*------------------------------------------------------------------ascii.c
imprime la tabla ascii
----------------------------------------------------------------------*/
#include <stdio.h>
#include <conio.h>
/*--------------------------------------------------------------------*/
void main(void)
{
unsigned char c = 0;
printf("\n\tdec\toctal\thexad\tcar");
for (;;)
{
if (c < 32)
printf("\n\t%d\t%o\t%x\t\tcaracter de control", c, c, c);
else if (c > 47 && c < 58)
printf("\n\t%d\t%o\t%x\t%c\tnúmero", c, c, c, c);
else if (c > 64 && c < 91)
printf("\n\t%d\t%o\t%x\t%c\tmayúscula", c, c, c, c);
else if (c > 96 && c < 123)
printf("\n\t%d\t%o\t%x\t%c\tminúscula", c, c, c, c);
else
printf("\n\t%d\t%o\t%x\t%c", c, c, c, c);
c++;
if (c == 0) break;
else if (c%24 == 0)
{
getch();
clrscr();
printf("\n\tdec\toctal\thexad\tcar");
}
}
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 19
Estructura de Datos
pag. 20
Valores en Decimal del Segundo Caracter (Código Extendido).
tecla
F1
F5
F9
Shift F1
Shift F5
Shift F9
Ctrl F1
Ctrl F5
Ctrl F9
Alt F1
Alt F5
Alt F9
Alt 1
Alt 5
Alt 9
Alt Alt C
Alt G
Alt K
Alt O
Alt S
Alt W
Home
End
Ins
Ctrl PtrSc
Ctrl Home
código tecla
59
63
67
84
88
92
94
98
102
104
108
112
120
124
128
130
46
34
37
24
31
17
71
79
82
114
119
F2
F6
F10
Shift F2
Shift F6
Shift F10
Ctrl F2
Ctrl F6
Ctrl F10
Alt F2
Alt F6
Alt F10
Alt 2
Alt 6
Alt 0
Alt =
Alt D
Alt H
Alt L
Alt P
Alt T
Alt X


Del
Ctrl 
Ctrl 
código tecla
60
64
68
85
89
93
95
99
103
105
109
113
121
125
129
131
32
35
38
25
20
45
72
80
83
115
116
código tecla
código
F3
F7
61
65
F4
F8
62
66
Shift F3
Shift F7
86
90
Shift F4
Shift F8
87
91
Ctrl F3
Ctrl F7
96
100
Ctrl F4
Ctrl F8
97
101
Alt F3
Alt F7
106
110
Alt F4
Alt F8
107
111
Alt 3
Alt 7
122
126
Alt 4
Alt 8
123
127
Alt A
Alt E
Alt I
Alt M
Alt Q
Alt U
Alt Y
PgUp
PgDn
Shift Tab
Ctrl End
Ctrl PgUp
30
18
23
50
16
22
21
73
81
15
117
132
Alt B
Alt F
Alt J
Alt N
Alt R
Alt V
Alt Z


48
33
36
49
19
47
44
75
77
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Ctrl PgDn 118
Estructura de Datos
/*------------------------------------------------------------------------------teclas.c
Reconoce que teclas se pulsan, incluyendo las teclas especiales.
-----------------------------------------------------------------------------------*/
#include <stdio.h>
#include <conio.h>
char c;
/*------------------------------------------------*/
void main(void)
{
clrscr()
printf("RECONOCEDOR DE TECLAS");
do {
printf("Pulse cualquier tecla ('f' para terminar) : ");
c = getch();
if (c == 0) { /* pulso una tecla especial */
c = getch();
switch (c) {
case 59 : printf("pulso <F1>");
break;
case 60 : printf("pulso <F2>");
break;
case 84 : printf("pulso <Shift-F1>");
break;
case 94 : printf("pulso <Ctrl-F1>");
break;
case 104 : printf("pulso <Alt-F1>");
break;
case 132 : printf("pulso <Ctrl-PgUp>"); break;
default : printf("");
}
} else { /* pulso una tecla ordinaria */
switch (c) {
case 13 : printf("pulso <CR>"); break;
case 27 : printf("pulso <ESC>"); break;
case 65 : printf("pulso <A>");
break;
case 97 : printf("pulso <a>");
break;
case 102 : printf("pulso <f>");
break;
default : printf("");
}
}
} while (c != 'f');
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 21
Estructura de Datos
pag. 22
2. Arreglos.
Estudiaremos a partir de ahora las estructuras de datos compuestas desde tres
niveles :
Nivel Abstracto ó Lógico.
Es decir, como una colección abstracta de elementos con un conjunto
particular de funciones de accesos. En este nivel, se dibuja la organización y
se especifican los procedimientos y funciones generales de acceso.
Nivel de Implementación.
Es decir, como un problema de codificación ( ¿ cómo se implementarán las
funciones de acceso ? ). En este nivel, se examinan las formas de representación de los datos en memoria y cómo implementar los procedimientos y
funciones de acceso.
Nivel de Aplicación.
Es decir, como una forma de representar las relaciones entre los datos en un
contexto específico. En este nivel, se diseñan ejemplos de aplicación en los
que la estructura de datos representa con precisión las relaciones entre los
datos.
Una estructura de datos compuesta consiste de una colección de nodos que
mantienen importantes relaciones entre sí :
nodo 2
nodo 1
nodo 4
nodo 3
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 23
El nodo es elemento básico para mantener la información en la estructura de
datos. Para representar la información contenida en un nodo se pueden utilizar
una ó más palabras de computadora dependiendo de las características de los
datos. Un nodo puede dividirse en campos conteniendo estructuras
elementales :
campo 1 campo 2 campo 3
campo n
...
2.1. Arreglos: nivel lógico.
Un arreglo es una estructura de datos con un número fijo de nodos. Al
conjunto de nodos se le identifica con un nombre y a los nodos con un índice.
En un arreglo se pueden practicar todas las operaciones relativas a la
información contenida en los nodos (extracción y almacenamiento) pero no
aquéllas relativas a alterar el número de nodos (suprimir y agregar). En la
figura 2.1 se muestra la organización de arreglos de una, dos y tres
dimensiones.
1
2 3
4
5
6
4
3
2
A[ I ]
1
2 3
1
4
5
6
1
1
2
2
3
3
4
4
5
6
5
6
1 2
A[ I, J ]
3
4
5 6
A[ I, J, K ]
Figura 2.1. Arreglos de una, dos y tres dimensiones.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 24
Funciones de Acceso.
Se utiliza una única función en dos formas:
(1). Almacenamiento.
Para especificar un lugar en el que ha de copiarse un valor. Por ejemplo, en el
lenguaje C :
A[i] = <Expresión>;
A[i, j] = <Expresión>;
A[i, j, k] = <Expresión>;
(2). Extracción.
Para especificar un lugar del que ha de extraerse un valor. Por ejemplo, en C :
<Nombre_de variable> = A[i];
<Nombre_de variable> = A[i, j];
<Nombre_de variable> = A[i, j, k];
2.2. Implementación de arreglos.
Se deben observar dos cosas para lograr la implementación de cualquier
estructura de datos: reservar memoria para la estructura de datos y codificar
las funciones de acceso. Un arreglo puede organizarse en la memoria de dos
formas: organización contigua y organización ligada. Analizaremos únicamente la organización contigua.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 25
Organización Contigua.
Los elementos del arreglo ocupan localidades contiguas de la memoria. En
este caso la recuperación de cualquier elemento del arreglo puede hacerse
básicamente sobre dos esquemas: 1) funciones de mapeo, y 2) tablas de
recuperación. Estudiaremos únicamente las funciones de mapeo.
Funciones de Mapeo.
Una función de mapeo es una expresión que permite calcular la dirección de
un nodo en función de sus índices.
Para un arreglo unidimensional A[i], que está limitado inferior y superiormente por b1  i  u1 , ésta función estará dada por :
DIR(A[i]) = L + (i - b1) * c
donde L es la dirección base del arreglo A (dirección en memoria de la
primera palabra del primer elemento del arreglo A), c representa el número de
palabras de memoria asignadas a cada elemento y b es la cota inferior del
índice del arreglo. Por facilidad para la exposición supondremos de ahora en
adelante que c = 1.
Para un arreglo bidimensional A[i,j] limitado tanto inferior como superiormente por: b1  i  u1 y b2  j  u2 la dirección en memoria del elemento
A[i,j] estará dada por :
1) si está almacenado por renglón ( i ) :
DIR(A[i,j]) = L + (i - b1) * (u2 - b2 + 1) + (j - b2)
2) si está almacenado por columna ( j ) :
DIR(A[i,j]) = L + (j - b2) * (u1 - b1 + 1) + (i - b1)
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 26
Ejemplo. Un arreglo bidimensional se puede almacenar por renglón y por
columna, teniendo los subíndices de renglones y columnas los siguientes
límites :
3  i  8
y
-5  j  0
obtenga una función para localizar la posición de almacenamiento del elemento A[i,j] si se almacena por renglón ó por columna, suponiendo en ambos
casos que el primer elemento del arreglo se almacenará en la posición L.
Solución.
n = 2 (bidimensional).
b1 = 3
u1 = 8
b2 = -5
u2 = 0
por renglón :
DIR(A[i,j]) = L + (i - b1) * (u2 - b2 + 1) + (j - b2)
DIR(A[i,j]) = L + (i - 3) * (0 + 5 + 1) + (j + 5)
DIR(A[i,j]) = L + 6(i-3) + (j+5)
para localizar A[3,-4] :
DIR(A[3,-4]) = L + 6(3-3) + (-4+5) = L + 0 + 1 = L + 1
por columna :
DIR(A[i,j]) = L + (j - b2) * (u1 - b1 + 1) + (i - b1)
DIR(A[i,j]) = L + (j + 5) * (8 - 3 + 1) + (i - 3)
DIR(A[i,j]) = L + 6(j+5) + (i-3)
para localizar A[3,-4] :
DIR(A[3,-4]) = L + 6(-4+5) + (3-3) = L + 6 + 0 = L + 6
Para un arreglo tridimensional A[i,j,k] limitado tanto inferior como
superiormente por: b1  i  u1 , b2  j  u2 y b3  k  u3 , la dirección en
memoria del elemento A[i,j,k] es:
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 27
1) si está almacenado por renglón ( i ) :
DIR(A[i,j,k]) = L + (i - b1) * (u2 - b2 + 1) * (u3 - b3 + 1) +
(j - b2) * (u3 - b3 + 1) + (k - b3)
2) si está almacenado por la profundidad ( k ) :
DIR(A[i,j,k]) = L + (k - b3) * (u2 - b2 + 1) * (u1 - b1 + 1) +
(j - b2) * (u1 - b1 + 1) + (i - b1)
Ejemplo. Considere un arreglo tridimensional 'X' almacenado por renglón,
teniendo los subíndices los siguientes límites :
1  i  3
1  j  3
-1  k  0
obtenga una expresión para localizar la posición de un elemento cualquiera
X[i,j,k] suponiendo que la localización base del arreglo es L. Pruebe
localizando el elemento X[1,1,-1].
Solución.
n = 3 (tridimensional).
b1 = 1 b2 = 1
b3 = -1
u1 = 3 u2 = 3
u3 = 0
DIR(X[i,j,k]) =
=
=
=
=
L + (i-1)(3-1+1)(0+1+1) + (j-1)(0+1+1) + (k+1)
L + (i-1)(3)(2) + (j-1)(2) + (k+1)
L + 6(i-1) + 2(j-1) + (k+1)
L + 6i - 6 + 2j - 2 + k + 1
L + 6i + 2j + k -7
DIR(X[1,1,-1]) = L + 6(1) + 2(1) + (-1) - 7
= L+6+2-1-7
= L
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 28
Para un arreglo n-dimensional, donde
b1  s1  u1 , b2  s2  u2 , b3  s3  u3 , . . . , bn  s n  un
si está almacenado por renglón, tendremos :
DIR(A(s1,s2,...,sn) = L + (s1-b1) * (u2-b2+1) * (u3-b3+1) * . . . * (un-bn+1)
+ (s2-b2) * (u3-b3+1) * . . . * (un-bn+1)
...
+ (sn-1-bn-1) * (un-bn+1)
+ (sn-bn)
ésta función puede reescribirse en la siguiente forma :
DIR(A[s1,s2,...,sn]) = L +  Pi (si-bi)
1  j n
donde
Pi =  (uj - bj + 1)
ijn
para
bi  si  u i
Ejemplo. Considere el siguiente arreglo de cinco dimensiones :
A[1..3, 3..5, 1..10, 1..6, 1..3]
si el arreglo se almacena por renglón, y su localización base es L, encuentre la
localización en memoria del elemento A[1,3,1,1,1].
Solución.
n = 5 (cinco dimensiones).
b1 = 1 b2 = 3 b 3 = 1 b4 = 1 b 5 = 1
u1 = 3 u2 = 5 u3 = 10 u4 = 6 u5 = 3
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 29
DIR(A[s1, s2, s3, s4, s5]) = L +  Pi (si-bi)
1  j 5
DIR(A[s1, s2, s3, s4, s5]) = L + P1(s1 - b1) + P2(s2 - b2) + P3 (s3 - b3)
+ P4(s4 - b4) + P5(s5 - b5)
P1 =  (uj - bj + 1) = (u2 - b2 + 1)(u3 - b3 + 1)(u4 - b4 + 1)(u5 - b5 + 1)
1  j 5
P2 =  (uj - bj + 1) = (u3 - b3 + 1)(u4 - b4 + 1)(u5 - b5 + 1)
2  j 5
P3 =  (uj - bj + 1) = (u4 - b4 + 1)(u5 - b5 + 1)
3  j 5
P4 =  (uj - bj + 1) = (u5 - b5 + 1)
4  j 5
P5 =  (uj - bj + 1) = 1
5  j 5
DIR(A[s1, s2, s3, s4, s5]) = L + (s1-b1)(u2-b2+1)(u3-b3+1)(u4-b4+1)(u5-b5+1)
+ (s2-b2)(u3-b3+1)(u4-b4+1)(u5-b5+1)
+ (s3-b3)(u4-b4+1)(u5-b5+1)
+ (s4-b4)(u5-b5+1)
+ (s5-b5)(1)
DIR(A[s1, s2, s3, s4, s5]) = L + (s1 - 1)(5-3+1)(10-1+1)(6-1+1)(3-1+1)
+ (s2 - 3)(10-1+1)(6-1+1)(3-1+1)
+ (s3 - 1)(6-1+1)(3-1+1)
+ (s4 - 1)(3-1+1)
+ (s5 - 1)
DIR(A(s ,s ,s ,s ,s )) = L + (s -1)(3)(10)(6)(3) + (s -3)(10)(6)(3)
+ (s -1)(6)(3) + (s -1)(3) + (s -1)
DIR(A[s1, s2, s3, s4, s5]) = L + (s1 - 1)(3)(10)(6)(3) + (s2 - 3)(10)(6)(3)
+ (s3 - 1)(6)(3) + (s4 - 1)(3) + (s5 - 1)
DIR(A[s1, s2, s3, s4, s5]) = L + (s1 - 1)(540) + (s2 - 3)(180) + (s3 - 1)(18)
+ (s4 - 1)(3) + (s5 - 1)
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 30
DIR(A[1, 3, 1, 1, 1]) = L + (1 - 1)(540) + (3 - 3)(180) + (1 - 1)(18)
+ (1 - 1)(3) + (1 - 1)
DIR(A[1,3,1,1,1]) = L + 0 = L.
2.3. Aplicaciones.
1). Como primer ejemplo de aplicación de arreglos consideraremos el problema de la manipulación simbólica para realizar operaciones sobre polinomios
algebraicos. Centraremos nuestra atención en particular a la manipulación de
polinomios en dos variables x y y. Se requiere, por ejemplo, escribir un
programa que sustraiga polinomios como los siguientes :

2x2 + 5xy +
x2 + 3xy +
x2 + 2xy +
y2
y2 +
0 -
y
y
+
x
x
Nos interesa, por lo tanto, encontrar una representación adecuada para
polinomios de tal modo que las operaciones puedan ser ejecutadas de una
manera razonable y eficiente. Es claro que debemos manipular cada término y
cada término consta de una ó dos variables, coeficiente y exponentes.Una
posibilidad es representar cada polinomio como una cadena de caracteres, lo
cual nos lleva a diseñar un algoritmo más ó menos complejo en los lenguajes
pascal ó C. Otra posibilidad más atractiva es representar cada polinomio
utilizando un arreglo bidimensional de la manera siguiente :
El arreglo que representaría al polinomio 2x2 + 5xy + y2 estaría dado por :
x0
x1
x2
x3
x4
y0
0
0
2
0
0
y1
0
5
0
0
0
y2
1
0
0
0
0
y3
0
0
0
0
0
y4
0
0
0
0
0
y el arreglo para x2 + 3xy + y2 + y - x estaría dado por :
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
x0
x1
x2
x3
x4
y0
0
-1
2
0
0
y1
1
3
0
0
0
y2
1
0
0
0
0
y3
0
0
0
0
0
pag. 31
y4
0
0
0
0
0
Con esta representación de polinomios, la adición y sustracción se
reduce a suma y resta de matrices respectivamente.
Ejercicio 1. Construya un programa que sirva para sumar ó restar
polinomios simbólicamente haciendo uso de la representación anterior.
Haga lo siguiente :
a). Convierta los datos de entrada en arreglos representando polinomios.
b). Sume ó reste los arreglos (polinomios) según el deseo del usuario.
c). Convierta el arreglo de salida a una forma entendible en la pantalla.
2). Realice una implementación del conocido juego del gato :
O
X
Introduzca las coordenadas de su X : _
basándose en el siguiente algoritmo :
ganador = false;
repeat
mostrar_dibujo( );
tira_jugador( );
ganador = revisar_tabla( );
if (NOT ganador)
then tira_computadora( );
ganador = revisar_tabla( );
end-if
until (ganador);
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 32
3). Recorridos de un caballo sobre un tablero de ajedrez.
El problema consiste en mover un caballo, comenzando en cualquier cuadro
del tablero pero permitiendo visitar cada cuadro una sola vez; se recomienda
representar la solución colocando los números 1,2,3, ... ,63, 64 en los cuadros
para indicar el orden en que se visitan, de este modo, el usuario que llegue al
número 64 habrá visitado todos los cuadros del tablero; dependiendo de la
elección de las visitas, el usuario podrá 'ahogarse' (no poder visitar ningún
cuadro y no haber terminado de recorrer el tablero).
La decisión más importante para resolver éste problema está relacionado con
la representación de datos en la computadora; el modo más natural para
representar un tablero de ajedrez es mediante un arreglo bidimensional de 8x8
elementos, tal como se muestra en la figura 2.2 en la cual se muestran además
los ocho movimientos posibles de un caballo colocado en el cuadro [5,3].
1
1
2
3
4
5
6
7
8
2
3
8
4
5
6
7
8
1
7
2
C
6
3
5
4
Figura 2.2. Movimientos posibles de un caballo sobre un tablero de ajedrez.
En general, un caballo posicionado en [i,j] puede moverse a cualquiera de los
siguientes cuadros :
[i-2, j+1]
[i-1, j+2]
[i+1, j+2]
[i+2, j+1]
[i+2, j+1]
[i+1, j-2]
[i-1, j-2]
[i-2, j-1]
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 33
Nótese sin embargo, que si [i,j] está localizado cerca de los bordes, alguna ó
varias de estas posibilidades pueden mover el caballo fuera del tablero, lo
cual no debe de ninguna manera permitirse. Los ocho movimientos posibles
se pueden representar de manera más conveniente con dos arreglos
unidimensionales que podemos llamar mov1 y mov2 de la siguiente manera:
mov1[] = -2, -1, 1, 2, 2, 1, -1, -2.
mov2[] = 1, 2, 2, 1, -1, -2, -2, -1.
con ésta representación, un caballo posicionado en [i,j] puede moverse a la
posición [i + mov1[k], j + mov2[k] ], donde 'k' es algún valor entre 1 y 8,
debiendo verificarse antes si la nueva posición está dentro del tablero.
Enseguida se proporciona un algoritmo para resolver éste problema y se deja
como ejercicio la implementación del mismo en la computadora.
Algoritmo Ajedrez.
[Recorridos de un caballo sobre un tablero de ajedrez.]
1. [ Iniciar el tablero.]
[El tablero es un arreglo de números enteros de 8x8 y se debe
inicializar con ceros, ésto significa que todavía no se ha visitado
ningún cuadro.]
inicia_tablero( );
[inicializa el tablero]
despliega_tablero( );
[se despliega el tablero vacío]
m  0;
[no se ha visitado ningún cuadro]
2. [Iterar mientras haya movimientos posibles]
repeat
[se pide al usuario un movimiento; algunos de los cuadros
pueden no ser posibles de visitar debido a que quedan fuera
del tablero ó bien que ya han sido visitados anteriormente
(contienen un número diferente de cero), también es posible
que el caballo se encuentre 'ahogado' (no es posible ningún
movimiento), éstos problemas deben ser detectados en el
algoritmo función 'rev_pos( )' que se propone como ejercicio]
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
write('Cuadro a visitar : ');
read(ren, col);
[renglón y columna]
pos_ok = rev_pos(ren, col); [ ¿ posición correcta ?]
if (pos_ok)
then m  m + 1;
[se visitó el siguiente cuadro]
i  ren;
[el cuadro visitado es correcto]
j  col;
tablero[i, j]  m; [se registra el cuadro visitado]
end-if;
despliega_tablero( ); [se despliega el tablero actualizado]
until (not pos_ok | | m  64)
3. [Fin del algoritmo.]
End.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 34
Estructura de Datos
pag. 35
3. Pilas y Colas.
3.1 Pilas.
Es una estructura del tipo "último en entrar, primero en salir" (LIFO : last
input, firs output). Estas estructuras son muy importantes en el diseño de
sistemas operativos y compiladores.
Funciones de Acceso.
push(s,nuevo).
pop(s).
tope(s).
vacio(s).
Insertar el elemento 'nuevo' en la pila 's'.
Eliminar un elemento de la pila 's'.
Obtener sin eliminar un elemento de la pila 's'.
Comprobar si la pila 's' está vacía.
Implementación.
Implementaremos una pila en un arreglo unidimensional que consista de un
número suficiente de elementos para poder manipular las inserciones necesarias. El esquema es el siguiente :
1
2
k
k+1
X
X
...
X
 tope (inserción y eliminación)
...
n
En esta representación, 'tope' es un apuntador a la parte frontal de la pila.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
Los algoritmos son:
Procedimiento push(s, tope, x).
[Inserta un elemento x en la parte superior tope de una pila que
está representada en un vector s conteniendo n elementos. ]
1. [Revisa si existe estado de overflow (sobrealmacenamiento)]
if tope  n
then write('Pila llena (overflow)')
return
end-if
2. [Se incrementa tope]
tope  tope + 1
3. [Se inserta el nuevo elemento]
s[tope]  x
4. [Termina]
return
Funcion pop(s, tope).
[Remueve el elemento superior de una pila que está representada en
un vector s y retorna el elemento removido.]
1. [Revisa si existe estado de underflow (pila vacia)]
if tope = 0
then write('Pila vacía (underflow)')
return(0)
end-if
2. [Se disminuye el apuntador]
tope  tope - 1
3. [Se retorna el elemento removido]
return(s[tope + 1])
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 36
Estructura de Datos
pag. 37
Aplicaciones.
1). Usando una pila, construya un algoritmo que analice en una expresión
aritmética, el uso correcto de los paréntesis "(" y ")" embebidos en ella.
Solución.
Queremos revisar que :
a). Exista igual número de paréntesis a la izquierda y a la derecha.
b). Cada paréntesis de la derecha está precedido por el correspondiente
paréntesis a la izquierda.
Para resolver éste problema debemos pensar en que cada paréntesis a la
izquierda abre una posibilidad y cada paréntesis a la derecha cierra ésta
posibilidad; una pila se puede aprovechar para registrar éste tipo de signos de
agrupación: en cuanto se encuentre un paréntesis a la izquierda, éste es
empujado hacia la pila y cuando se encuentre un paréntesis a la derecha, se
examina la pila, si esta vacía, la expresión aritmética no es válida, si no está
vacía, se retira un elemento de la pila y así sucesivamente hasta terminar de
examinar la expresión.
Algoritmo paréntesis.
[Dada una expresión algebraica llamada cadena, que contiene un
espacio en blanco ' ' en la última posición de la extrema derecha, por
ejemplo '(x+(y-(a+b))*c-((d+e)))/(b-(j-(k-(l-n)))) ', y dada la función
sigchar que retorna el siguiente símbolo de cadena, se analiza el uso
correcto de los paréntesis "(" y ")" embebidos en la expresión.]
1. [Inicia la pila colocando el signo ' ']
tope  1
s[tope]  ' '
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 38
2. [Obtiene símbolos, si es un '(' lo apila y si es un ')' quita un
símbolo de la pila. Repetirá lo anterior hasta que obtenga un ' '
ó bien que la expresión sea inválida.]
sig  sigchar(cadena)
repeat while sig  ' '
if sig = '('
then call push(s, tope, sig)
else if sig = ')'
then i  pop(s, tope)
if i = ' '
then write('Expresión incorrecta')
return(0)
end-if
end-if
end-if
sig  sigchar(cadena)
end-repeat
3. [El siguiente símbolo debe ser un espacio en blanco ' ']
i  pop(s, tope)
if i = ' '
then write('Expresión correcta')
else write('Expresión incorrecta')
end-if
4. [Terminar]
exit.
2). Consideraremos otro ejemplo que involucra el uso de una pila.
Sea el conjunto :
L = { w c wR | w E {a, b} }
done wR es el reverso de w, por ejemplo, si w = ab, entonces wR = ba.
El conjunto anterior define a un lenguaje 'L' que puede contener un número
infinito de cadenas. Algunas de las cadenas posibles son :
aca, bcb, abcba, bacab, abbcbba, abacaba, aabcbaa, ...
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 39
Se requiere formular un algoritmo para el cual, dada una cadena de entrada
sobre el alfabeto {a, b, c}, determine si dicha cadena existe en el lenguaje 'L'.
Este algoritmo requiere una pila para realizar su tarea. Asumiremos que la
cadena de entrada está terminada a la derecha con un espacio en blanco.
Algoritmo Reconocer.
[Dada una cadena llamada 'string' sobre el alfabeto {a, b, c} y que contiene un
espacio en blanco en la posición última de la extrema derecha y dada la
función 'nextchar' que retorna el siguiente símbolo de 'string', éste algoritmo
determina si el contenido de 'string' pertenece ó no al lenguaje 'L'. ]
1. [Inicia la pila colocando el signo 'c']
tope  1
s[tope]  'c'
2. [Obtiene y apila símbolos hasta que una 'c' ó un blanco ' ' se encuentran].
next  nextchar(string)
repeat while (next  'c')
if next = ' '
then write('cadena invalida')
exit
else call push(s, tope, next)
next  nextchar(string)
end-if
end-repeat
3. [Examina los caracteres posteriores al signo 'c' y los compara con
los caracteres apilados.]
repeat while (s[tope]  'c')
next  nextchar(string)
x  pop(s, tope)
if next  x
then write('cadena inválida')
exit
end-if
end-repeat
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 40
4. [El siguiente símbolo debe ser un blanco ' '.]
if next = ' '
then write('cadena correcta')
else write('cadena incorrecta')
end-if
5.[Terminar]
exit.
3). Usando una pila, construya un algoritmo que analice en una expresión
aritmética el uso correcto de tres tipos diferentes de separadores: '()', '[]', '{}'.
Compruebe el algoritmo con la siguiente expresión :
{x + (y - [a + b]) * c - [(d + e)]} / (b - (j - (k - [l - n])))
Ahora es necesario tener en cuenta no solamente cuántos separadores han sido
abiertos, sino también de qué tipo son. Esto es necesario porque cuando se
encuentre un signo de agrupación, debemos saber el tipo de símbolo mediante
el cual se abrió la agrupación y asegurarnos de que ha sido cerrado
apropiadamente.
Se puede utilizar una pila única para registrar los diferentes tipos de signos de
agrupación. En cuanto se encuentre un paréntesis a la izquierda, éste es
empujado hacia la pila, y cuando se encuentre un signo terminal, se retira un
elemento de la pila; si la pila está vacía, quiere decir que el paréntesis a la
derecha no tiene su correspondiente paréntesis a la izquierda y por tanto la
expresión aritmética no es válida. Sin embargo, si la pila no está vacía,
debemos revisar si el elemento retirado corresponde al tipo de signo de
agrupación terminal. Si coincide el tipo, continuamos, si no coincide, la
expresión aritmética no es válida. Cuando lleguemos al final de la expresión,
nos aseguramos de que la pila está vacía, de lo contrario quiere decir que se
han abierto uno ó más signos pero no se han cerrado, haciendo que la
expresión sea incorrecta.
4). Construya un algoritmo que acepte una cadena de caracteres y la invierta
usando una pila.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 41
3.2. Colas.
Son estructuras de datos lineales del tipo "primero que llega, primero que
sale" (FIFO : first input, first output).
Funciones de Acceso.
qinsert(q, f, r, x). Inserta x al final de la cola q.
qdelete(q, f, r). Elimina el último elemento de la cola q.
Implementación.
Implementaremos una cola en un arreglo unidimensional que consista también
de un tamaño suficiente como para poder manipular las inserciones y
eliminaciones necesarias :
1
2
k
k+1
X
...
X
 f (eliminación)
 r (inserción)
...
n
En esta representación, 'f' y 'r' son apuntadores a la posición frontal y final de
la cola, respectivamente.
Los algoritmos necesarios son :
Procedimiento qinsert(q, f, r, x).
[Dado un vector q que contiene 'n' elementos y las variables enteras
'f' y 'r' que apuntan a los elementos frontal y final de la cola, éste
procedimiento inserta el elemento 'x' al final de la cola. ]
1. [Revisa si existe estado de overflow (sobrealmacenamiento)]
if r  N
then write('Cola llena (overflow)')
return
end-if
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
2. [Se incrementa el apuntador del final]
rr+1
3. [Se inserta el nuevo elemento]
q[r]  x
4. [¿ Está el apuntador frontal debidamente fijado ?]
if f = 0
then f  1
end-if
5. [Termina]
return
Procedimiento qdelete(q, f, r).
[Dado un vector q que contiene 'n' elementos y las variables enteras
'f' y 'r' que apuntan a los elementos frontal y final de la cola, éste
procedimiento elimina y retorna el último elemento de la cola. ]
1. [Revisa si existe estado de underflow (cola vacía).]
if f = 0
then write('Cola Vacía (underflow)')
return (0)
{ 0 denota una cola vacía }
end-if
2. [Se elimina el elemento frontal]
x  q[f]
3. [¿ Resulta una cola vacía ?]
if f = r
then f  r  0
else f  f + 1
{ Se incrementa el apuntador frontal }
end-if
4. [Retorna el elemento eliminado.]
return x
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 42
Estructura de Datos
pag. 43
3.3. Cola Doble.
Es una estructura de datos en la cual las operaciones de agregar y retirar se
practican por ambos extremos.
Funciones de Acceso.
dqinsertf(dq, f, r, x). Inserta x al final de la cola doble.
dqinsertr(dq, f, r, x). Inserta x al frente de la cola doble.
dqdeletef(dq, f, r). Elimina el último elemento de la cola doble.
dqdeleter(dq, f, r). Elimina el primer elemento de la cola doble.
Implementación.
Implementaremos una cola doble en un arreglo unidimensional que consista
también de un tamaño suficiente como para poder manipular las inserciones y
eliminaciones necesarias :
1
2
k
k+1
X
...
X
 f (eliminación e inserción)
 r (eliminación e inserción)
...
n
En esta representación, 'f' y 'r' son apuntadores a la posición frontal y final de
la cola doble, respectivamente.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 44
4. Listas.
En este capítulo estudiaremos la organización ligada de las estructuras
lineales. Esta organización nos permite manejar de manera más eficiente el
almacenamiento de la computadora. Iniciaremos el estudio con un pequeño
recordatorio de los elementos necesarios para trabajar con listas ligadas.
4.1. Punteros.
Todas las variables, excepto las variables tipo registro, residen en algún lugar
de la memoria; éste lugar tiene una dirección de memoria que es en realidad
el número de byte inicial del espacio que ocupa la variable; un puntero es una
variable que sirve para almacenar la dirección de memoria de otra variable de
cualquier tipo.
Ejemplo 1. El siguiente programa despliega en la pantalla las direcciones
de dos variables.
/*---------------------------------------------------------------------------#include <stdio.h>
void main(void)
{
int i = 7, j = 8;
printf("i = %d, &i = %p\n", i, &i);
printf("j = %d, &j = %p\n", j, &j);
}
El programa produce una salida parecida a la siguiente :
i = 7, &i = FFF4
j = 8, &j = FFF2
el operador unario & retorna la dirección de la variable a la que se le aplica, el
descriptor %p indica que deseamos desplegar una dirección en formato
hexadecimal.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 45
Ejemplo 2. El programa que sigue ilustra un uso elemental de variables de
tipo puntero.
/*---------------------------------------------------------------------------#include <stdio.h>
void main(void)
{
int i = 7, j = 8;
int *p, *q;
p = &i;
q = &j;
printf("p = %p, *p = %d\n", p, *p);
printf("q = %p, *q = %d\n", q, *q);
*p = 9;
*q = 10;
printf("p = %p, *p = %d\n", p, i);
printf("q = %p, *q = %d\n", q, j);
}
El programa producirá una salida parecida a la siguiente :
p = FFF4,
q = FFF2,
p = FFF4,
q = FFF2,
*p = 7
*q = 8
*p = 9
*q = 10
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 46
4.2. Listas Simplemente Ligadas.
Una lista simplemente ligada es una lista de elementos que se denominan
generalmente como nodos :
Nodo 1
Nodo 2
Nodo 3
Nodo N
...
Apuntador al primer nodo
Cada nodo está constituido por dos partes : un campo (ó varios) para
contener datos y otro campo que contiene la liga al siguiente nodo en un
orden dado :
N
D A T O S
O
D
O
L I G A
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
Ejemplo 2. Lista simplemente ligada de caracteres. 1a. versión.
/*------------------------------------------------------lsl01.c
Genera una lista simplemente ligada de caracteres.
Estructura de Datos I.
---------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#include <conio.h>
struct nodo {
/* definicion del nodo */
char vocal;
struct nodo *liga;
};
struct nodo *primero;
struct nodo *temporal;
struct nodo *nuevo;
/* punteros */
void main(void)
{
/* crea un nodo e inserta la 'a' */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
nuevo->vocal = 'a';
nuevo->liga = NULL;
/* no apunta a ningun lado */
primero = nuevo;
/* apunta al nodo recien creado */
/* crea otro nodo e inserta la 'e' */
temporal = nuevo;
/* guarda la direccion del nodo */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
temporal->liga = nuevo; /* enlaza al nodo nuevo */
nuevo->vocal = 'e';
nuevo->liga = NULL;
/* no apunta a ningun lado */
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 47
Estructura de Datos
/* crea otro nodo e inserta la 'i' */
temporal = nuevo;
/* guarda la direccion del nodo */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
temporal->liga = nuevo; /* enlaza al nodo nuevo */
nuevo->vocal = 'i';
nuevo->liga = NULL;
/* no apunta a ningun lado */
/* crea otro nodo e inserta la 'o' */
temporal = nuevo;
/* guarda la direccion del nodo */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
temporal->liga = nuevo; /* enlaza al nodo nuevo */
nuevo->vocal = 'o';
nuevo->liga = NULL;
/* no apunta a ningun lado */
/* recorre la lista simplemente ligada */
clrscr( );
printf("\nLISTAS SIMPLEMENTE LIGADAS\n\n");
temporal = primero; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
printf("\n%c ",temporal->vocal);
temporal = temporal->liga; /* avanza al siguiente nodo */
}
/* recorre la lista y elimina los nodos */
temporal = primero; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
temporal = temporal->liga; /* avanza al siguiente nodo */
free(primero);
/* destruye el primer nodo */
primero = temporal;
/* apunta al nuevo primer nodo */
}
/* hace una pausa */
printf("\n\n<Oprima cualquier tecla para terminar>\n");
getch( );
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 48
Estructura de Datos
Ejemplo 3. Lista Simplemente Ligada de caracteres. 2a. versión.
/*--------------------------------------------------------lsl02.c
Genera una lista simplemente ligada de caracteres
utilizando un ciclo.
Estructura de Datos I.
---------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#include <conio.h>
struct nodo {
/* definicion del nodo */
char vocal;
struct nodo *liga;
};
struct nodo *primero;
/* punteros */
struct nodo *temporal;
struct nodo *nuevo;
char vocal;
void main(void)
{
/* se pide el primer caracter */
clrscr( );
printf("\nLISTAS SIMPLEMENTE LIGADAS\n");
printf("\nIntroduzca un caracter (f para terminar) : ");
vocal = getche( );
if (vocal != 'f')
{
/* se inserta el primer caracter */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
nuevo->vocal = vocal;
nuevo->liga = NULL; /* no apunta a ningun lado */
primero = nuevo;
/* apunta al nodo recien creado */
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 49
Estructura de Datos
/* se piden los demas caracteres y se insertan */
printf("\nIntroduzca un caracter (f para terminar) : ");
vocal = getche( );
while (vocal != 'f')
{
temporal = nuevo;
/* guarda la direccion del nodo */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
temporal->liga = nuevo; /* enlaza al nodo nuevo */
nuevo->vocal = vocal;
nuevo->liga = NULL;
/* no apunta a ningun lado */
printf("\nIntroduzca un caracter (f para terminar) : ");
vocal = getche( );
}
/* recorre la lista simplemente ligada */
clrscr( );
printf("\nLISTAS SIMPLEMENTE LIGADAS\n\n");
temporal = primero; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
printf("\n%c ",temporal->vocal);
temporal = temporal->liga; /* avanza al siguiente nodo */
}
/* recorre la lista y elimina los nodos */
temporal = primero; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
temporal = temporal->liga; /* avanza al siguiente nodo */
free(primero);
/* destruye el primer nodo */
primero = temporal; /* apunta al nuevo primer nodo */
}
}
/* hace una pausa */
printf("\n\n<Oprima cualquier tecla para terminar>\n");
getch( );
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 50
Estructura de Datos
4.3. Operaciones con listas ligadas.
Crear una lista.
Recorrer la lista.
Buscar un elemento.
Insertar un nodo.
Eliminar un nodo.
Invertir la lista.
Ordenar la lista.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 51
Estructura de Datos
Ejemplo 4. Operaciones sobre listas ligadas.
/*----------------------------------------------------oplis.c
Operaciones sobre Listas Ligadas.
Estructura de Datos I.
-------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h> /* para usar malloc( ) y free( ) */
#include <conio.h>
#include <ctype.h> /* para usar isalpha( ) */
#define c1 " UNIVERSIDAD AUTONOMA DE GUERRERO "
#define c2 "
programa oplis.c
"
#define c3 " Operaciones sobre Listas Ligadas. "
#define A "(a). Crear una lista ligada de caracteres."
#define B "(b). Desplegar la lista."
#define C "(c). Eliminar el primer nodo."
#define D "(d). Aumentar un nodo al principio."
#define F "(f). Fin."
#define TRUE 1
#define FALSE 0
char EXISTE_LISTA = FALSE;
struct nodo {
int dato;
struct nodo *liga;
};
typedef struct nodo *PNODO;
PNODO crear_nodo( );
PNODO adicionar_nodo( );
PNODO eliminar_nodo( );
PNODO leer_lista( );
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 52
Estructura de Datos
PNODO opcion_a( );
void opcion_b( );
PNODO opcion_c( );
PNODO opcion_d( );
void ver_lista( );
void menu(void);
void pausa(char mensaje[]);
/*----------------------------------------------------------*/
void main(void)
{
char c;
PNODO p;
menu( );
c = getche( );
while (c != 'f')
{
switch (c)
{
case 'a' : if (!EXISTE_LISTA) p = opcion_a( );
break;
case 'b' : if (EXISTE_LISTA) opcion_b(p);
break;
case 'c' : if (EXISTE_LISTA) p = opcion_c(p);
break;
case 'd' : if (EXISTE_LISTA) p = opcion_d(p);
break;
case 'f' : exit(1);
}
menu( );
c = getche( );
}
pausa("");
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 53
Estructura de Datos
/*------------------------------------------------------------*/
PNODO opcion_a( )
{
PNODO p;
clrscr( );
printf("\n\n\t");
printf(A);
p = leer_lista( );
EXISTE_LISTA = TRUE;
pausa("");
return (p);
}
/*------------------------------------------------------------*/
void opcion_b(p)
PNODO p;
{
clrscr( );
printf("\n\n\t");
printf(B);
ver_lista(p);
pausa("");
}
/*------------------------------------------------------------*/
PNODO opcion_c(p)
PNODO p;
{
clrscr( );
printf("\n\n\t");
printf(C);
p = eliminar_nodo(p);
pausa("");
return (p);
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 54
Estructura de Datos
/*------------------------------------------------------------*/
PNODO opcion_d(p)
PNODO p;
{
char x;
clrscr( ); printf("\n\n\t"); printf(D);
printf("\n\n\tIntroduzca un caracter : ");
x = getche( );
p = adicionar_nodo(p,x);
pausa("");
return (p);
}
/*------------------------------------------------------------*/
PNODO leer_lista( )
{
PNODO p;
char c[81];
int i=0;
printf("\n\n\tIntroduzca una lista de caracteres en una sola linea");
printf("\n\tseparados por espacios en blanco y pulse <enter> :");
/* lee la lista en un arreglo de caracteres */
printf("\n\n\t");
while ((c[i]=getche( )) != '\r')
{
if (c[i] == '\b') i--; else i++;
}
c[i]='\0';
/* genera la lista simplemente ligada */
i=0; p = NULL;
while (c[i] != '\0')
{
if (c[i] != ' ')
p = adicionar_nodo(p,c[i++]);
else i++;
}
return (p);
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 55
Estructura de Datos
/*------------------------------------------------------------*/
PNODO crear_nodo( )
{
PNODO p;
p = (PNODO) malloc(sizeof(struct nodo));
return (p);
}
/*------------------------------------------------------------*/
PNODO adicionar_nodo(p,x)
PNODO p;
char x;
{
PNODO q;
if (p == NULL)
{ /* se trata del primer nodo */
q = crear_nodo( );
q->dato = x;
q->liga = NULL;
p = q;
}
else
{ /* la lista ya existe */
q = crear_nodo( );
q->dato = x;
q->liga = p;
p = q;
}
return (p);
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 56
Estructura de Datos
/*------------------------------------------------------------*/
PNODO eliminar_nodo(p)
PNODO p;
{
PNODO q;
if (p->liga == NULL)
{ /* se trata de un solo nodo */
free(p); p = NULL;
EXISTE_LISTA = FALSE;
}
else
{ /* la lista ya existe */
q = p->liga;
free(p); p = q;
}
return (p);
}
/*------------------------------------------------------------*/
void ver_lista(p)
PNODO p;
{
PNODO q;
q = p;
printf("\n\n\tLISTA LIGADA :");
while (q)
{
printf(" %c", q->dato);
q = q->liga;
}
}
/*------------------------------------------------------------*/
void pausa(char mensaje[])
{
printf(mensaje);
printf("\n\n\t\t\t<pulse cualquier tecla>");
getch( );
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 57
Estructura de Datos
/*------------------------------------------------------*/
void menu(void)
{
clrscr( );
gotoxy(20,2); printf(c1); gotoxy(20,3); printf(c2);
gotoxy(20,4); printf(c3); gotoxy(10,7); printf(A);
gotoxy(10,9); printf(B); gotoxy(10,11); printf(C);
gotoxy(10,13); printf(D); gotoxy(10,15); printf(F);
gotoxy(15,18);
printf("Pulse su Opcion : ");
}
4.4. Listas doblemente ligadas.
Ejemplo 5. Lista doblemente ligada de caracteres.
/*------------------------------------------------------ldl02.c
Genera una lista doblemente ligada de caracteres.
utilizando un ciclo.
Estructura de Datos I.
---------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#include <conio.h>
struct nodo {
/* definicion del nodo */
struct nodo *ligai;
char vocal;
struct nodo *ligad;
};
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 58
Estructura de Datos
struct nodo *izquierdo;
struct nodo *derecho;
struct nodo *temporal;
struct nodo *nuevo;
char vocal;
/* punteros */
void main(void)
{
/* se pide el primer caracter */
clrscr( );
printf("\nLISTAS DOBLEMENTE LIGADAS\n");
printf("\nIntroduzca un caracter (f para terminar) : ");
vocal = getche( );
if (vocal != 'f')
{
/* se inserta el primer caracter */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
nuevo->vocal = vocal;
nuevo->ligai = NULL; /* no apunta a ningun lado */
nuevo->ligad = NULL;
izquierdo = nuevo; /* primer nodo por la izquierda */
derecho = nuevo;
/* primer nodo por la derecha */
/* se piden los demas caracteres y se insertan */
printf("\nIntroduzca un caracter (f para terminar) : ");
vocal = getche( );
while (vocal != 'f')
{
temporal = nuevo;
/* guarda la direccion del nodo */
nuevo = (struct nodo *) malloc(sizeof(struct nodo));
temporal->ligad = nuevo; /* enlaza al nodo nuevo */
nuevo->ligai = temporal; /* enlaza hacia atras */
nuevo->vocal = vocal;
nuevo->ligad = NULL;
/* no apunta a ningun lado */
derecho = nuevo;
/* primer nodo por la derecha */
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 59
Estructura de Datos
printf("\nIntroduzca un caracter (f para terminar) : ");
vocal = getche( );
}
/* recorre la lista doblemente ligada */
clrscr( );
printf("\nLISTAS DOBLEMENTE LIGADAS");
printf("\n\nRecorrido por la izquierda\n");
temporal = izquierdo; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
printf("\n%c ",temporal->vocal);
temporal = temporal->ligad; /* avanza al siguiente nodo */
}
printf("\n\nRecorrido por la derecha\n");
temporal = derecho; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
printf("\n%c ",temporal->vocal);
temporal = temporal->ligai; /* avanza al siguiente nodo */
}
/* recorre la lista y elimina los nodos */
temporal = izquierdo; /* copia la direccion del primer nodo */
while (temporal != NULL)
{
temporal = temporal->ligad; /* avanza al siguiente nodo */
free(izquierdo);
/* destruye el primer nodo */
izquierdo = temporal; /* apunta al nuevo primer nodo */
izquierdo->ligai = NULL;
}
}
/* hace una pausa */
printf("\n\n<Oprima cualquier tecla para terminar>\n");
getch( );
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 60
Estructura de Datos
pag. 61
Tarea #1 de listas.
Para una lista simplemente ligada de números enteros del tipo :
Nodo 1
7
Nodo 2
-3
Nodo 3
0
Nodo N
...
1
primero
Donde cada nodo tiene dos campos conocidos como dato y liga,escriba y
pruebe los siguientes procedimientos :
1). void promedio(struct *primero).
Este procedimiento debe obtener el valor promedio de los números
almacenados.
2). void inserta_despues(struct *primero, int x, int y).
Inserta un nodo exactamente después del nodo que contiene el valor 'x' y
almacena en este nuevo nodo el valor 'y'.
3). void elimina_despues(struct *primero, int x).
Elimina el nodo inmediatamente posterior al nodo que contiene el valor 'x'; si
no está, debe indicarlo con un mensaje.
4). void modificar(struct *primero, int x, int y).
Busca el nodo que contenga el valor 'x' y cambia éste valor a 'y'; si no lo
encuentra debe indicarlo con un mensaje.
5). void uno_cero(struct *primero).
Aplica el siguiente algoritmo a todos los nodos de la lista :
Si el valor almacenado en el nodo es negativo,
reemplazarlo por un 0;
de otro modo, si es cero, reemplazarlo por -1;
de otro modo, reemplazarlo por +1.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 62
6). void inserta_cola(struct nodo *primero, int x)
Inserta el elemento 'x' al final de la lista ligada; considere los casos de lista
vacía y 'overflow' (máximo diez nodos).
7). struct nodo *borra_cola(struct nodo *primero)
Elimina el primer elemento de la lista ligada; considere el caso de 'underflow'
(lista vacía).
8. struct nodo *borra_pila(struct nodo *primero, int x)
Elimina el último elemento de la lista ligada; considere el caso de 'underflow'
(lista vacía).
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 63
5. Estructuras no lineales.
Las estructuras no lineales son capaces de expresar relaciones mucho más
complejas entre los datos; en éste capítulo estudiaremos las estructuras de
datos conocidas como árboles binarios; posteriormente en otros cursos se
analizarán estructuras más complicadas como árboles no binarios, grafos y
estructuras combinadas.
5.1. Arboles binarios.
Se caracterizan porque cualquiera de sus nodos tiene exactamente cero, uno ó
dos subárboles. Un nodo del árbol binario puede representarse de la siguiente
manera :
apuntador
izquierdo
datos
apuntador
derecho
el esquema para un árbol binario podría ser el siguiente :
raiz
C
B
/
A
/
/
F
/
/
D
/
E
/
UNIDAD ACADEMICA DE MATEMATICAS, UAG
G
/
Estructura de Datos
pag. 64
Funciones de Acceso.
Recorrido, Inserción, Eliminación, Búsqueda, Copia, ..., étc.
Recorrido de árboles binarios.
Se denomina recorrido de un árbol al procedimiento por medio del cual cada
nodo se procesa exactamente una única vez de modo sistemático. Existen tres
modos principales de recorrido de árboles binarios: preorden, inorden y
postorden. La definición recursiva de éstos procedimientos es la siguiente :
Recorrido en Preorden.
1. Procesar el nodo raiz.
2. Recorrer el subárbol izquierdo en preorden.
3. Recorrer el subárbol derecho en preorden.
Recorrido en Inorden.
1. Recorrer el subárbol izquierdo en inorden.
2. Procesar el nodo raiz.
3. Recorrer el subárbol derecho en inorden.
Recorrido en Postorden.
1. Recorrer el subárbol izquierdo en postorden.
2. Recorrer el subárbol derecho en postorden.
3. Procesar el nodo raiz.
Ejemplo 1. Recorrer el árbol anterior de ejemplo en preorden, inorden y
postorden.
Preorden : C B A F D E G
Inorden : A B C D E F G
Postorden : A B E D G F C
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 65
Ejemplo 2. Escriba un algoritmo procedimiento para procesar un árbol
binario en preorden.
Algoritmo.
Procedimiento Preorden(raiz).
[Dado un árbol binario cuya dirección al nodo raiz es "raiz", éste
procedimiento recorre y procesa el árbol en preorden.]
1. [Procesa el nodo raiz ]
if raiz  null
then write(datos(raiz))
else write('Arbol vacío')
return
2. [Procesa el subárbol izquierdo ]
if ant(raiz)  null
then call preorden(ant(raiz))
3. [Procesa el subárbol derecho ]
if sig(raiz)  null
then call preorden(sig(raiz))
4. [Termina ]
return
Ejemplo 3. Programa para generar un árbol binario ordenado y efectuar los
recorridos en inorden, preorden y postorden.
/*--------------------------------------------------------------------------Nombre del Archivo : arbin01.c
Recorrido en inorden, preorden y postorden de arboles
binarios.
------------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#include <conio.h>
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
struct nodo {
/* definición del nodo */
struct nodo *ligai;
char vocal;
struct nodo *ligad;
};
struct nodo *raiz;
/* puntero a la raiz del árbol */
char vocal;
void insertar(char x, struct nodo **p);
void inorden (struct nodo *raiz);
void preorden (struct nodo *raiz);
void postorden (struct nodo *raiz);
void main(void)
{
/* se pide el primer caracter */
clrscr( );
printf("RECORRIDO DE ARBOLES BINARIOS");
printf("(1). Creación de un árbol binario ordenado.");
printf("Introduzca un caracter (f para terminar) : ");
vocal = getche( );
if (vocal != 'f')
{
/* se crea el árbol binario */
raiz = NULL;
do {
insertar(vocal, &raiz);
printf("Introduzca un caracter (f para terminar) : ");
vocal = getche( );
} while (vocal != 'f');
/* recorridos en el árbol */
printf("(2). Recorridos en el árbol binario.");
printf("RECORRIDO EN INORDEN :");
inorden(raiz);
printf("RECORRIDO EN PREORDEN :");
preorden(raiz);
printf("RECORRIDO EN POSTORDEN :");
postorden(raiz);
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 66
Estructura de Datos
/* hace una pausa */
printf("<Oprima cualquier tecla para terminar>");
getch( );
}
void insertar(char x, struct nodo **p)
{
if (*p == NULL) {
*p = (struct nodo *) malloc(sizeof(struct nodo));
(*p)->vocal = vocal;
(*p)->ligai = NULL; /* no apunta a ningun lado */
(*p)->ligad = NULL;
} else {
if (x < (*p)->vocal)
insertar(x, &(*p)->ligai);
else
insertar(x, &(*p)->ligad);
}
}
void inorden (struct nodo *raiz)
{
if (raiz != NULL) {
inorden(raiz->ligai);
printf("%c", raiz->vocal);
inorden(raiz->ligad);
}
}
void preorden (struct nodo *raiz)
{
if (raiz != NULL) {
printf("%c", raiz->vocal);
inorden(raiz->ligai);
inorden(raiz->ligad);
}
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 67
Estructura de Datos
pag. 68
void postorden (struct nodo *raiz)
{
if (raiz != NULL) {
inorden(raiz->ligai);
inorden(raiz->ligad);
printf("%c", raiz->vocal);
}
}
Ejercicios. Dado el siguiente árbol binario de números :
raiz
11
9
/
6
/
/
17
/
/
12
/
15
21
/
/
donde cada nodo tiene tres campos conocidos como 'ligai', 'número' y 'ligad',
escribir y probar los siguientes procedimientos :
a). void promedio (struct nodo *raiz)
Este procedimiento debe obtener el valor promedio de los números
almacenados.
b). void total_de_nodos(struct nodo *raiz)
Debe obtener el total de nodos intermedios, nodos terminales (hojas) y total
de nodos existentes en el árbol.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 69
c). void buscar(int x, struct nodo *raiz)
Debe Buscar si existe un nodo que contenga en su campo de datos el valor x;
si no existe debe indicarlo con un mensaje.
d). void modificar(int x, int y, struct nodo *raiz)
Debe buscar el nodo que contiene el valor 'x' y reemplazarlo con el valor
almacenado en 'y'; si 'x' no existe en el árbol, deberá indicarlo con un mensaje
apropiado.
e). void genera3(struct nodo *raiz)
Debe generar tres arreglos unidimensionales declarados como variables
globales y llamados preorden[], inorden[] y postorden[] conteniendo los datos
del árbol resultantes de haberlo recorrido en preorden, inorden y postorden
respectivamente.
Ejemplo 4. Construcción de un árbol binario perfectamente equilibrado.
/*------------------------------------------------------------------------------Nombre del Archivo : arbeq01.c
Construcción de un árbol binario perfectamente equilibrado
y recorrido en inorden.
--------------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#include <conio.h>
struct nodo {
/* definición del nodo */
struct nodo *ligai;
char vocal;
struct nodo *ligad;
};
struct nodo *raiz;
int n;
/* puntero a la raiz del árbol */
/* total de nodos a crear */
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 70
void insertar(char x, struct nodo **p);
void inorden (struct nodo *raiz);
struct nodo *construir_arbol(int n);
void main(void)
{
/* se pide el primer caracter */
clrscr();
printf("\nARBOLES BINARIOS PERFECTAMENTE EQUILIBRADOS");
printf("\n(1). Creación del árbol binario.\n");
printf("\nNumero de Nodos a Crear : ");
scanf("%d", &n);
raiz = construir_arbol(n);
/* recorrido del árbol */
printf("\n\n(2). Recorrido del árbol binario.\n");
printf("\nRECORRIDO EN INORDEN :\n");
inorden(raiz);
/* hace una pausa */
printf("\n\n<Oprima cualquier tecla para terminar>\n");
getch();
}
/*----------------------------------------------------------------------------*/
struct nodo *construir_arbol(int n)
{
struct nodo *q;
int ni,nd;
if (n == 0) return NULL;
else {
ni = n / 2;
/* nodos del subarbol izquierdo */
nd = n - ni - 1; /* nodos del subarbol derecho */
q = (struct nodo *) malloc(sizeof(struct nodo));
printf("\nIntroduzca un caracter : ");
q->vocal = getche();
q->ligai = construir_arbol(ni);
q->ligad = construir_arbol(nd);
return (q);
}
}
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 71
/*------------------------------------------------------------------------------*/
void inorden (struct nodo *raiz)
{
if (raiz != NULL) {
inorden(raiz->ligai);
printf("%c ", raiz->vocal);
inorden(raiz->ligad);
}
}
5.2. Enhebrado de árboles binarios.
Los apuntadores nulos se reemplazan por "hilos" (apuntadores a otros nodos
del árbol como guías para recorrerlos); el hilo izquierdo de un nodo apunta al
predecesor y el hilo derecho al sucesor en un orden previamente escogido.
Concepto de cabeza de árbol.
Es un nodo especial y asociado permanentemente a la existencia del árbol. El
campo de la información en el nodo cabeza no se utiliza. El árbol queda
encadenado al apuntador izquierdo del nodo cabeza.
Ejemplo. Enhebrar en preorden el árbol del ejemplo anterior.
Recorrido en preorden : C-B-A-F-D-E-G.
Enhebrado en preorden :
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 72
cabeza
C
B
A
F
G
D
E
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
pag. 73
BIBLIOGRAFIA
1. Estructuras de Datos.
Segunda Edición.
Osvaldo Cairó y Silvia Guardati.
Mc Graw-Hill, 2002.
2. Estructuras de Datos en C.
Tenenbaum; Langsam; Augenstein.
Prentice Hall, 1993.
3. Estructura de Datos.
Euán, J.I.; Cordero, L.G.
Limusa. 1989.
4. Estructura de Datos.
Seymour Lipschutz.
Mc Graw-Hill, 1988.
5. Programación Avanzada en Turbo C.
Herbert Schildt
Mc Graw-Hill.
6. Algoritmos y Estructura de Datos.
Niklaus Wirth.
Prentice Hall Hispanoamericana, 1987.
7. Data Structures, Algorithms and program style using C.
korsh, J.F.; Garrett, L.J.
PWS-KENT Publishing Company, 1988.
8. An Introduction to Data Structures with Applications.
Tremblay, J.P.; Sorenson, P.G.
Mc Graw-Hill. 1985.
9. Algoritmos Fundamentales. (El Arte de Programar Ordenadores, vol. 1).
Donald E. Knuth.
Reverté, S.A. 1985.
UNIDAD ACADEMICA DE MATEMATICAS, UAG
Estructura de Datos
UNIDAD ACADEMICA DE MATEMATICAS, UAG
pag. 74