UNIVERSIDAD POLITÉCNICA DE PUEBLA

INGENIERÍA EN INFORMÁTICA

MANUAL DE ASIGNATURA
Asignatura: ESTRUCTURAS DE DATOS

Tipo de asignatura: ESPECÍFICA.

Cuatrimestre: TERCERO

Nombre de quién elaboró: M.C. ANTONIO CESAR RODRÍGUEZ ALARCÓN

Fecha de elaboración: NOVIEMBRE 2004.

 Manual de la asignatura

ÍNDICE
INTRODUCCIÓN .................................................................................................................................... 1
HOJA TÉCNICA ...................................................................................................................................... 2
BIBLIOGRAFÍA ...................................................................................................................................... 4
IDENTIFICACIÓN DE OBJETIVOS DE APRENDIZAJE (OA), TEMAS DE APRENDIZAJE (TA)
Y RESULTADOS DE APRENDIZAJE (RAP) ....................................................................................... 5
IDENTIFICACIÓN DE SESIONES DE APRENDIZAJE (SAP) ......................................................... 12
LINEAMIENTOS DE EVALUACIÓN ................................................................................................ 15
INSTRUMENTOS DE EVALUACIÓN ................................................................................................ 16
GUÍA DE PRÁCTICAS ......................................................................................................................... 20
Práctica No. 1.......................................................................................................................................... 20
Práctica No. 2.......................................................................................................................................... 21
Práctica No. 3.......................................................................................................................................... 24
Práctica No. 4.......................................................................................................................................... 28
Práctica No. 5.......................................................................................................................................... 38
Práctica No. 6.......................................................................................................................................... 40
Práctica No. 7.......................................................................................................................................... 42
Práctica No. 8.......................................................................................................................................... 47
 Manual de la asignatura

INTRODUCCIÓN

Para la mayoría de las personas que han tenido contacto con una computadora, la conciben
como una herramienta que permite lograr cosas tan fascinantes como vuelos espaciales, control sobre
plantas nucleares, diagnósticos médicos, diseños, accesos eficientes a grandes bancos de información
remotos, simulación de generaciones de virus y en algunos casos hasta entretenimiento y diversión. Las
computadoras digitales aun las más modernas y complejas, pueden ser vistas como un gran conjunto de
piezas. De una manera simple cada una de estas piezas representa información en forma de conjuntos
de bits, cada bit (dígito binario) puede estar en una de dos posiciones o dicho de otra manera puede
tener cualquiera de dos valores 0 ó 1. Cualquier computadora tiene un conjunto muy reducido de
operaciones triviales que puede realizar, como son: corrimientos, comparaciones, sumas, etc., pero
entonces, ¿cuál es la distancia entre las operaciones triviales con bits y las increíbles hazañas que
realizan las computadoras? La respuesta a la pregunta anterior es el proceso y el algoritmo que lo
controla y provoca para que tenga lugar.

Un algoritmo se define como un conjunto finito de reglas que producen una secuencia de
operaciones para resolver un tipo específico de problemas con las siguientes cinco características
principales: finito, preciso, eficaz, cero o más entradas y una o más salidas.

Este curso busca proveer una introducción a las estructuras de datos básicas, y los algoritmos
para manipularlas, usando un lenguaje de programación orientado al objeto. En esta asignatura se
complementan las habilidades de programación en lo que se refiere a los Tipos de Datos. Se estudian
los diferentes tipos de datos más utilizados en programación para la representación de la información,
así como sus aplicaciones. Se hace énfasis en presentar cada Tipo de Dato como un Tipo de Dato
Abstracto formado por la integración de los datos y sus operaciones.

Constituye la base para un gran número de cursos de la carrera vinculados a las áreas de
programación visual, programación orientada a objetos, bases de datos y compiladores. En el curso se
le enseña a los alumnos los tipos de datos abstractos mas utilizados en programación, tales como las
estructuras lineales y sus aplicaciones, y las estructuras no lineales, de manera que para cada nuevo
problema el estudiante pueda escoger adecuadamente los tipos de datos necesarios para representar la
información. De la misma manera tiene que ser capaz de implementar correctamente los tipos de datos
estudiados así como nuevos tipos derivados.

Por lo anterior el objetivo de esta asignatura es desarrollar la capacidad en el alumno para

diseñar algoritmos que utilicen las estructuras de datos para mejorar el rendimiento de una aplicación.

1
 Manual de la asignatura

HOJA TÉCNICA

Nombre de la asignatura: ESTRUCTURAS DE DATOS

Código de la asignatura: EDA303

Área del conocimiento: Ciencias de la ingeniería

Cuatrimestre al que aplica: TERCERO

Carreras en las que aplica: Ingeniería en Informática

DISEÑO DE LA ASIGNATURA
OBJETIVO DE LA ASIGNATURA
Desarrollar la capacidad en el alumno para diseñar algoritmos que utilicen las estructuras de datos para
mejorar el rendimiento de una aplicación.

Tipo de práctica requerida para el aprendizaje del

alumno: Practica en laboratorio.

Competencia Habilidades Actitudes

• Desarrollo de programas Reforzar • Cooperación para
utilizando tipos de datos • Diseño de algoritmos. trabajar de forma conjunta
para realizar una actividad.
abstractos. Responsabilidad de la materia • Iniciativa para participar
• Uso de estructuras de datos. en clase.
• Orden para presentar de
forma clara los resultados
de un trabajo.

2
 Manual de la asignatura

UNIDADES DE TEORIA PRACTICA

APRENDIZAJE
Tipos de Datos 3 2
Estimación de tiempo (horas) Abstractos
necesario para transmitir el Arreglos. 4 4
aprendizaje al alumno, por UA: Listas ligadas. 5 6
Pilas y Colas 6 6
Árboles 6 6
Grafos. 6 6
Total de horas por 30 30
cuatrimestre:
Total de horas por semana: 2 2
Total de horas presénciales: 60
Total de horas no presénciales: 15
Total de horas: 75
Créditos: 5

3
 Manual de la asignatura

BIBLIOGRAFÍA
1. H.M Deitel y P.J. Deitel, Como programar en C / C++2ª edición, Prentice Hall.
2. Yedidyah Langsam - Moshe J. Augenstein - Aaron M. Tenenbaum, ESTRUCTURAS DE DATOS CON C Y
C++2ª edición, Prentice Hall.
3. Goordich y Tamassia, Estructuras de datos y algoritmos en java1ª edición, CECSA.
4. Allen Weiss, M, Estructuras de datos en Java, Addison Wesley.
5. Aho Ullman, Hopcroft, Estructura de Datos y Algoritmos, 2000.

M.C. ANTONIO CESAR RODRIGEZ ALARCÓN

Nombre y firma de quien elaboró Nombre y firma de quien revisó

Dr. MIGUEL ÁNGEL CELIS FLORES

Nombre y firma de quien validó Nombre y firma del representante de la UPPuebla

Nombre y firma del representante de la CUP

4
 Manual de la asignatura

IDENTIFICACIÓN DE OBJETIVOS DE APRENDIZAJE (OA), TEMAS DE APRENDIZAJE

(TA) Y RESULTADOS DE APRENDIZAJE (RAP)

Sesión
Unidades de Aprendizaje Objetivos de
Temas de Aprendizaje Resultados de Aprendizaje
aprendizaje
Número Nombre
1. Tipos de Datos 1.1 El alumno 1.1 Definición de estructuras de 1.1 El alumno describe las 1 Tipos de
Abstractos describirá las datos. características y datos
características y 1.1.1 Estructuras de datos clasificación de las abstractos
clasificación de las estáticas. estructuras de datos.
estructuras de datos. 1.1.2 Estructuras de datos
dinámicas.

1.2 El alumno 1.2 Introducción a los tipos de 1.2 El alumno describe las
describirá las datos abstractos. características de los
características de un 1.2.1 Definición de tipos de tipos de datos abstractos
tipo de datos datos abstracto. y sus aplicaciones
abstracto y sus 1.2.2 Aplicaciones de los
aplicaciones. tipos de datos
abstractos.

5
 Manual de la asignatura

Sesión
Unidades de Aprendizaje Objetivos de
Temas de Aprendizaje Resultados de Aprendizaje
aprendizaje
Número Nombre
2.1 El alumno 2.1 Características de los 2.1 El alumno implementa 2 Arreglos.
implementará arreglos unidimensionales. programas que utilicen
programas que 2.1.1 Componentes de los arreglos
utilicen arreglos arreglos unidimensionales.
unidimensionales, unidimensionales.
bidimensionales y 2.2 Arreglos de cadenas de 2.2 El alumno implementa
multidimensionale caracteres. programas que utilicen
s. arreglos de cadenas de
caracteres.
2. Arreglos.
2.3 Características de los 2.3 El alumno implementa
arreglos bidimensionales. programas que utilicen
2.3.1 Componentes de los arreglos bidimensionales.
arreglos
bidimensionales.
2.4 Arreglos 2.4 El alumno implementa
multidimensionales. programas que utilicen
arreglos
multidimensionales.

6
 Manual de la asignatura

Sesión
Unidades de Aprendizaje Resultados de
Objetivos de aprendizaje Temas de Aprendizaje
Aprendizaje
Número Nombre
3.1 El alumno 3.1 Apuntadores. 3.1 El alumno describe 3 Apuntadores.
desarrollará 3.1.1 Direcciones y que es un apuntador
programas utilizando referencias. y sus características.
apuntadores. 3.1.2 Concepto de
apuntador.
3.1.3 Declaración de 3.2 El alumno
apuntador. desarrolla programas
3.1.4 Inicialización que utilizan
de apuntadores. apuntadores.
3.2 Arreglos de
apuntadores.
3.3 Apuntadores de
cadenas.
3.4 Asignación dinámica 3.3 El alumno describe
3. Listas ligadas.
de memoria. como se realiza la
3.4.1 El operador asignación dinámica
new. de memoria con los
3.4.2 El operador operadores new y
delete. delete.

3.2 El alumno 3.5 Estructuras. 3.4 El alumno 4 Estructuras.

desarrollará 3.5.1 Declaración de desarrollará
programas utilizando una estructura. programas
estructuras. 3.5.2 Definición de utilizando
variables estructuras.
estructuras.
3.5.3 Acceso a
estructuras.

7
 Manual de la asignatura

Sesión
Unidades de Aprendizaje Resultados de
Objetivos de aprendizaje Temas de Aprendizaje
Aprendizaje
Número Nombre
3.3 El alumno describirá 3.6 Estructuras 3.5 El alumno 5 Listas
las características de autoreferenciadas. describe las ligadas.
una estructura características de
autorefrenciada. una estructura
autorefrenciada.
3.4 El alumno 3.7 Listas enlazadas. 3.6. El alumno
implementará 3.7.1 Clasificación implementará
programas utilizando de las listas programas
listas enlazadas. enlazadas. utilizando listas
3.7.2 Declaración de enlazadas.
un nodo.
3. Listas ligadas. 3.7.3 Puntero
cabecera,
cola y nulo.
3.8 Insertar un elemento
en una lista.
3.9 Búsqueda de un
elemento en una
lista.
3.10 Borrar un elemento
de la lista.
3.11 Listas doblemente
enlazadas.

8
 Manual de la asignatura

Sesión
Unidades de Aprendizaje Resultados de
Objetivos de aprendizaje Temas de Aprendizaje
Aprendizaje
Número Nombre
4.1 El alumno describirá 4.1 Concepto de pila. 4.1 El alumno describe 6 Pilas.
el concepto de pila. el concepto de pila.
4.2 El alumno 4.2 Implementación de 4.2 El alumno
implementará una pila utilizando implementa
programas que arreglos. programas que
utilicen la estructura 4.3 Operaciones de utilizan la
de datos pila. verificación del estructura de datos
estado de la pila. pila.
4.4 Implementación de
una pila utilizando
una lista enlazada.
4.3 El alumno describirá 4.5 Concepto de cola. 4.3 El alumno describe
4. Pilas y Colas el concepto de cola. 4.5.1 Colas simples. el concepto de pila.
4.5.2 Colas
circulares.
4.5.3 Colas dobles.
4.4 El alumno 4.6 Implementación de 4.4 El alumno 7 Colas
implementará una cola utilizando implementa
programas que arreglos. programas que
utilicen la estructura 4.7 Operaciones de utilizan la
de datos cola. verificación de estructura de datos
estado de la cola. cola.
4.8 Implementación de
una cola utilizando
una lista enlazada.

9
 Manual de la asignatura

Sesión
Unidades de Aprendizaje Resultados de
Objetivos de aprendizaje Temas de Aprendizaje
Aprendizaje
Número Nombre
5.1 El alumno describirá 5.1 Definición. 5.1 El alumno describe 8 Árboles
los elementos de la 5.2 Representación en los elementos de la
estructura de datos memoria de árboles. estructura de datos
árbol. 5.2.1 Árboles árbol.
generales.
5.2.2 Árboles
binarios.
5.2 El alumno 5.3 Recorridos de un 5.2 El alumno
5. Árboles implementará árbol binario. implementará
programas que 5.3.1 Recorridos programas que
utilizan la estructura preorden utilizan la
de datos árbol. 5.3.2 Recorrido, estructura de datos
entreorden árbol.
5.3.3 Recorrido
postorden.
5.3.4 Recorrido en
amplitud.
6.1 El alumno describirá 6.1 Definición. 6.1 El alumno describe 9 Grafos
las características de 6.2 Tipos de grafos. las características
los grafos. 6.3Representación en de los grafos.
memoria de los
6 Grafos. grafos.
6.2 El alumno 6.4 Implementación de 6.2 El alumno
implementa grafos. implementa
programas que programas que
utilizan grafos. utilizan grafos.

10
Manual de la asignatura

11
 Manual de la asignatura

IDENTIFICACIÓN DE SESIONES DE APRENDIZAJE (SAP)

Sesiones de Aprendizaje Lugar de Formación

Instrumento Técnica de
Resultados de Aprendizaje Evidencia de Referencia N° Nombre Duración Aprendizaje Aula Lab. Campo Otro
sugerida
1.1 El alumno describe las
características y
clasificación de las
Tipos de Exposición
estructuras de datos.
EC Cuestionario 1 datos 1 por parte del X
1.2 El alumno describe las
abstractos profesor.
características de los tipos
de datos abstractos y sus
aplicaciones.
2.1 El alumno implementa
programas que utilicen
arreglos unidimensionales.
2.2 El alumno implementa
Exposición
programas que utilicen
por parte del
arreglos de cadenas de
EC Cuestionario profesor.
caracteres. Práctica 1
2 Arreglos. 8 X X
EP1 Practicas de
2.3 El alumno implementa
laboratorio.
programas que utilicen
Programas.
arreglos bidimensionales.
2.4 El alumno implementa
programas que utilicen
arreglos multidimensionales.

12
 Manual de la asignatura

Sesiones de Aprendizaje Lugar de Formación

Instrumento Técnica de
Resultados de Aprendizaje Evidencia de Referencia N° Nombre Duración Aprendizaje Aula Lab. Campo Otro
sugerida
3.1 El alumno describe que es
un apuntador y sus
características. Exposición
3.2 El alumno desarrolla por parte del
programas que utilizan EC Cuestionario Apuntadores profesor.
Práctica 2
3 8 X X
apuntadores. EP2 . Practicas de
3.3 El alumno describe como se laboratorio.
realiza la asignación Programas.
dinámica de memoria con los
operadores new y delete.
3.4 El alumno desarrollará Practicas de
EC Cuestionario
programas utilizando Práctica 3
4 Estructuras. 4 laboratorio. X
EP3
estructuras. Programas.
3.5 El alumno describe las Exposición
características de una por parte del
estructura autorefrenciada. EC Cuestionario Listas profesor.
Práctica 4.
5 8 X X
3.6. El alumno implementará EP4 ligadas. Practicas de
programas utilizando listas laboratorio.
enlazadas. Programas.

13
 Manual de la asignatura

Sesiones de Aprendizaje Lugar de Formación

Instrumento Técnica de
Resultados de Aprendizaje Evidencia de Referencia N° Nombre Duración Aprendizaje Aula Lab. Campo Otro
sugerida
4.1 El alumno describe el
Exposición
concepto de pila.
por parte del
4.2 El alumno implementa
EC Cuestionario profesor.
programas que utilizan la Práctica 5.
6 Pilas. 8 X X
EP5 Practicas de
estructura de datos pila.
laboratorio.
4.3 El alumno describe el
Programas.
concepto de pila.
4.4 El alumno implementa Practicas de
EC Cuestionario
programas que utilizan la Práctica 6.
7 Colas 8 laboratorio. X
EP6
estructura de datos cola. Programas.
5.1 El alumno describe los Exposición
elementos de la estructura por parte del
de datos árbol. EC Cuestionario profesor.
Práctica 7.
8 Árboles 8 X X
5.2 El alumno implementará EP7 Practicas de
programas que utilizan la laboratorio.
estructura de datos árbol. Programas.
6.1 El alumno describe las Exposición
características de los grafos. por parte del
6.2 El alumno implementa EC Cuestionario profesor.
Práctica 8.
9 Grafos 7 X X
programas que utilizan EP8 Practicas de
grafos. laboratorio.
Programas.
Total: 60 h

14
 Manual de la asignatura

LINEAMIENTOS DE EVALUACIÓN

PORCENTAJES DE EVALUACIÓN

Evidencia por desempeño 30%

Evidencia por producto 35%
Evidencia de conocimiento 35%

Desempeño Producto Conocimiento

Uso adecuado de las estructuras Reporte escrito. 3 exámenes parciales
de datos simples en la solución de
problemas.
Uso adecuado de las estructuras Problemas resueltos. 1º parcial
de datos lineales en la solución de
problemas.
Uso adecuado de las estructuras Practicas de laboratorio. UA 1,2,
de datos no lineales en la solución
de problemas.
Uso adecuado de los algoritmos 2º Parcial
de orden de datos en la solución
de problemas.
Uso adecuado de los algoritmos UA 3,4
de búsqueda de datos en la
solución de problemas.
3º Parcial
UA 5,6

15
 Manual de la asignatura

INSTRUMENTOS DE EVALUACIÓN

UNIVERSIDAD POLITÉCNICA DE PUEBLA

INGENIERÍA EN INFORMÁTICA
EVALUACIÓN DE REPORTE ESCRITO
LISTA DE COTEJO
DATOS GENERALES DEL PROCESO DE EVALUACIÓN
NOMBRE DE LOS ALUMNOS: MATRICULA:

FECHA:
MATERIA: ESTRUCTURAS DE DATOS.

NOMBRE DEL MAESTRO:

INSTRUCCIONES
Revisar las actividades que se solicitan y marque en los apartados “SI” cuando la evidencia se cumple; en caso contrario marque “NO”. En la
columna “OBSERVACIONES” indicaciones que puedan ayudar al alumno a saber cuales son las condiciones no cumplidas, si fuese necesario.

CUMPLE
Característica a cumplir (Reactivo) OBSERVACIONES
SI NO

Portada 5% (Nombre de la Universidad, Nombre del Programa Académico que se

estudia, Nombre de la asignatura, Nombre del tema que se presenta, Nombre de los
integrantes que conforman el trabajo, Fecha de entrega. Se entrega en limpio y sin
faltas de ortografía , se definen márgenes y su redacción es aceptable )

Indice 5% (capítulos, subcapítulos, secciones y subsecciones. Los números de

página están correctos )

Introducción 10% (Los antecedentes y el objetivo dan una idea clara del contenido
del reporte. Además da a conocer un panorama general del contenido del reporte
escrito )

Cuerpo 50% (Contiene los puntos fundamentales del documento dividido por
capítulos y secciones y subsecciones numeradas en orden ascendente. )

Conclusiones 20% (Son claras y de acuerdo con el objetivo esperado, además de

ser originales y estar numeradas (usando viñetas) )

Bibiliografía 10% (Presenta todo el material usado en el trabajo de forma correcta y

sencilla de consultar, listada en forma alfabética usando un formato único y
particular )

CALIFICACIÓN:

16
 Manual de la asignatura

UNIVERSIDAD POLITÉCNICA DE PUEBLA

INGENIERÍA EN INFORMÁTICA
EVALUACIÓN DE BANCOS DE PROBLEMAS RESUELTOS
LISTA DE COTEJO
DATOS GENERALES DEL PROCESO DE EVALUACIÓN
NOMBRE DE LOS ALUMNOS: MATRICULA:

FECHA:

MATERIA: ESTRUCTURAS DE DATOS.

NOMBRE DEL MAESTRO:

INSTRUCCIONES
Revisar las actividades que se solicitan y marque en los apartados “SI” cuando la evidencia se cumple; en caso contrario marque “NO”. En la
columna “OBSERVACIONES” indicaciones que puedan ayudar al alumno a saber cuales son las condiciones no cumplidas, si fuese necesario.

CUMPLE
Característica a cumplir (Reactivo) OBSERVACIONES
SI NO

Portada 10% (Nombre de la Universidad, Nombre del Programa Académico que se

estudia, Nombre de la asignatura, Nombre del tema que se presenta, Nombre de los
integrantes que conforman el trabajo, Fecha de entrega. Se entrega en limpio y sin
faltas de ortografía , se definen márgenes y su redacción es aceptable )

Indice 10% (Listado de los problemas que integran el banco y los números de
página correspondientes)

Enunciado del Problema 20% (Se escribe el enunciado definitivo del problema
explicando “que” es lo que hay que resolver con los tecnicismos propios del tema
que se esta trabajando. )

Metodología de Solución 30% (Se definen las precondiciones, post-condiciones y

metodología o algoritmo que resuelve el problema planteado )

Solución del Problema 30% (Se sigue la metodología o algoritmo descrito, se

soluciona el problema y se concluye escribiendo la solución al mismo )

CALIFICACIÓN:

17
 Manual de la asignatura

UNIVERSIDAD POLITÉCNICA DE PUEBLA

INGENIERÍA EN INFORMÁTICA
EVALUACIÓN DE PRACTICAS DE LABORATORIO
LISTA DE COTEJO
DATOS GENERALES DEL PROCESO DE EVALUACIÓN
NOMBRE DEL ALUMNO: MATRICULA:

FECHA:

MATERIA: ESTRUCTURAS DE DATOS.

NOMBRE DEL MAESTRO:

INSTRUCCIONES

Revisar las actividades que se solicitan y marque en los apartados “SI” cuando la evidencia se cumple; en caso contrario marque “NO”.

CUMPLE
REACTIVO
SI NO
Presentación 30% (Código fuente del programa, impreso y en disco. Programas ejecutables en
disco. Todo en un sobre manila rotulado con el nombre del estudiante y su matrícula)
Funcionalidad 35% (El producto o programa es funcional, es decir, resuelve el problema
utilizando la estructura de datos indicada.)
Revisión 35% (Ejecuta la aplicación en la computadora y da una explicación de la metodología
implementada para resolver el problema. )
CALIFICACIÓN

18
 Manual de la asignatura

UNIVERSIDAD POLITÉCNICA DE PUEBLA

INGENIERÍA EN INFORMÁTICA
EVALUACIÓN DE CONOCIMIENTOS
CUESTIONARIO
DATOS GENERALES DEL PROCESO DE EVALUACIÓN
NOMBRE DEL ALUMNO: MATRICULA:

FECHA:

MATERIA: ESTRUCTURAS DE DATOS.

NOMBRE DEL MAESTRO:

INSTRUCCIONES
• Llene cada uno de los siguientes espacios vacíos..

CUMPLE
Código REACTIVO
SI NO
Los elementos de un arreglo están relacionados entre sí por el hecho de que tienen el mismo
a) Nombre, tipo. b)Tamaño, tipo. c)
¿Cuál es el nombre del número utilizado para referirse a un elemento de un arreglo.
a)Número. b)Índice. c)Subíndice. d) Tamaño

CALIFICACIÓN

19
 Manual de la asignatura

GUÍA DE PRÁCTICAS
Práctica No. 1.
Nombre de la sesión de la práctica: Arreglos.
Objetivo de la práctica: El alumno utilizará los arreglos para almacenar información
Introducción: Un arreglo es un tipo de estructura de datos que consta de un número fijo de elementos
del mismo tipo. En una máquina, dichos elementos se almacenan en posiciones contiguas de memoria.
Estos elementos pueden ser variables o estructuras. Para definirlos se utiliza la expresión:

tipo_de_elemento nombre_del_arreglo[número_de_elementos_del_arreglo];
int mapa[100];

Cada uno de los elementos de los que consta el arreglo tiene asignado un número (índice). El primer
elemento tiene índice 0 y el último tiene índice número_de_elementos_del_arreglo-1. Para acceder a
ese elemento se pone el nombre del arreglo con el índice entre corchetes:

nombre_del_arreglo[índice]
mapa[5]

Los elementos no tienen por qué estar determinados por un solo índice, pueden estarlo por dos (por
ejemplo, fila y columna), por tres (p.e. las tres coordenadas en el espacio), o incluso por más. A estos
arreglos definidos por más de un índice se le llaman arreglos multidimensionales o matrices, y se
definen:

tipo_de_elemento nombre_del_arreglo[número1] [número2]... [númeroN];

int mapa[100][50][399];

Y para acceder a un elemento de índices i1,i2,...,iN, la expresión es similar:

nombre_del_arreglo[i1][i2]...[iN]
mapa[34][2][0]

Hay que tener cuidado con no utilizar un índice fuera de los límites, porque dará resultados inesperados
(tales como cambio del valor de otras variables o finalización del programa, con error "invalid memory
reference").

Manejo de arreglos
Para manejar un arreglo, siempre hay que manejar por separado sus elementos, esto es, NO se pueden
utilizar operaciones tales como dar valores a un arreglo (esperando que todos los elementos tomen ese
valor). También hay que tener en cuenta de que al definir un arreglo, al igual que con una variable
normal, los elementos del arreglo no están inicializados. Para ello, hay que dar valores uno a uno a
todos los elementos. Para arreglos unidimensionales, se utiliza un for:

20
 Manual de la asignatura

for(i=0;i<N;i++)
arreglo[i]=0;

y para arreglos multidimensionales se haría así:

for(i1=0;i1<N1;i1++)
for(i2=0;i2<N2;i2++)
...
for(iN=0;iN<NN;iN++)
arreglo1[i1][i2]...[iN]=0;

Recursos requeridos: Una computadora con el lenguaje de programación C instalado.

Desarrollo: Utilice un arreglo de un subíndice para resolver el problema siguiente. Lea 20 números,
cada uno de los cuales este entre 10 y 100 inclusive. Conforme cada número es leído, imprima sólo si
no es un duplicado de un número ya leído.
Tiempo de ejecución: Una hora.

Práctica No. 2.
Nombre de la sesión de la práctica: Apuntadores.
Objetivo de la práctica: El alumno desarrollará un programa utilizando apuntadores.
Introducción:
Un apuntador es una variable que contiene la dirección en memoria de otra variable. Se pueden tener
apuntadores a cualquier tipo de variable.
• El operador unario o monádico & devuelve la dirección de memoria de una variable.
• El operador de indirección o dereferencia * devuelve el ``contenido de un objeto apuntado por un
apuntador''.

Para declarar un apuntador para una variable entera hacer:

int *apuntador;

Se debe asociar a cada apuntador un tipo particular. Por ejemplo, no se puede asignar la dirección de un
short int a un long int.

Para tener una mejor idea, considerar el siguiente código:

main()
{
int x = 1, y = 2;
int *ap;
ap = &x;
y = *ap;
x = ap;
*ap = 3;
}

21
 Manual de la asignatura

Cuando se compile el código se mostrará el siguiente mensaje:

warning: assignment makes integer from pointer without a cast.

Con el objetivo de entender el comportamiento del código supongamos que la variable x esta en la
localidad de la memoria 100, y en 200 y ap en 1000. Nota: un apuntador es una variable, por lo tanto,
sus valores necesitan ser guardados en algún lado.

int x = 1, y = 2;
int *ap;
ap = &x;
100 200 1000
X 1 y 2 ap 100

Las variables x e y son declaradas e inicializadas con 1 y 2 respectivamente, ap es declarado como un

apuntador a entero y se le asigna la dirección de x (&x). Por lo que ap se carga con el valor 100.
y = *ap;

100 200 1000

X 1 y 1 ap 100

Como se ha visto C no es muy estricto en la asignación de valores de diferente tipo (apuntador a

entero). Así que es perfectamente legal (aunque el compilador genera un aviso de cuidado) asigna el
valor actual de ap a la variable x. El valor de ap en ese momento es 100.
*ap = 3;

100 200 1000

X 3 y 1 ap 100

Finalmente se asigna un valor al contenido de un apuntador (*ap).

Importante: Cuando un apuntador es declarado apunta a algún lado. Se debe inicializar el apuntador
antes de usarlo. Por lo que:
main()
{
int *ap;
*ap = 100;
}
puede generar un error en tiempo de ejecución o presentar un comportamiento errático.

22
 Manual de la asignatura

El uso correcto será:

main()
{ int *ap;
int x;
ap = &x;
*ap = 100;
}

Con los apuntadores se puede realizar también aritmética entera, por ejemplo:
main()
{
float *flp, *flq;
*flp = *flp + 10;
++*flp;
(*flp)++;
flq = flp;
}

NOTA: Un apuntador a cualquier tipo de variables es una dirección en memoria -- la cual es una
dirección entera, pero un apuntador NO es un entero.
La razón por la cual se asocia un apuntador a un tipo de dato, es por que se debe conocer en cuantos
bytes esta guardado el dato. De tal forma, que cuando se incrementa un apuntador, se incrementa el
apuntador por un ``bloque'' de memoria, en donde el bloque esta en función del tamaño del dato.
Por lo tanto para un apuntador a un char, se agrega un byte a la dirección y para un apuntador a entero
o a flotante se agregan 4 bytes. De esta forma si a un apuntador a flotante se le suman 2, el apuntador
entonces se mueve dos posiciones float que equivalen a 8 bytes.

Recursos requeridos: Una computadora con el lenguaje de programación C instalado.

Desarrollo: Solicitar al alumno el desarrollo de los siguientes programas utilizando apuntadores.
• Convertir letras minúsculas a mayúsculas utilizando un apuntador a una función.
• Implementar el método de ordenación de burbuja utilizando apuntadores a funciones.
Tiempo de ejecución: 2 horas.

23
 Manual de la asignatura

Práctica No. 3.
Nombre de la sesión de la práctica: Estructuras.
Objetivo de la práctica: El alumno implementará programas utilizando estructuras.
Introducción:
La palabra clave struct define una estructura. Por tratarse de un tipo de datos puede utilizarse
directamente para definir una variable. La variable aparece entre corchetes puesto que puede ser
omitida.
struct [Nombre_de_la_estructura]
{
tipo1 campo1;
tipo2 campo2;
.
.
tipoN campoN;
} [variable];
Si se especifica una variable, estaremos definiendo una variable cuyo tipo será la estructura que la
precede. Si la variable no es indicada definimos un nuevo tipo de datos
(structNombre_de_la_estructura), que podremos utilizar posteriormente. Si es el nombre de la
estructura lo que se omite, tendremos que especificar obligatoriamente una variable que tendrá esa
estructura y no podremos definir otras variables con esa estructura sin tener que volver a especificar
todos los campos. Lo que se encuentra dentro de las llaves es una definición típica de variables con
su tipo y su identificador. Ejemplo:
struct punto
{
float x;
float y;
int color;
} punto_de_fuga;

Aquí estamos definiendo una variable llamada punto_de_fuga cuyo tipo es una estructura de datos
formada por tres campos y a la que hemos llamado punto. Dos de ellos son de tipo float y
representan las coordenadas del punto, el tercer valor es un entero que indica el color de ese punto.
En este caso hemos definido una variable y una estructura. Al disponer de un identificador para esta
última podemos definir nuevas variables de esta estructura.

struct punto origen1;

struct punto final1;

Donde origen1 y final1 son variables de tipo struct punto que hemos definido anteriormente. Si en la
definición de punto_de_fuga no se hubiese incluído un identificador para la estructura (en este
caso el identificador es punto), no podríamos definir nuevas variables con esa estructura ya que
no estaría identificada por ningún nombre.

24
 Manual de la asignatura

También podríamos haber excluído el nombre de la variable (punto_de_fuga). En este caso lo que
definiríamos sería una estructura llamada punto que pasaría a ser un nuevo tipo disponible por el
usuario. Así los tipos de variables de que dispondríamos ahora serían:

int
float
double
char
struct punto

Por tanto podríamos definir cualquier variable con estos tipos o incluso definir matriz de estos tipos.

struct punto matriz_de_puntos[30];

Así estaríamos definiendo una matriz de 30 elementos en la que cada elemento es una struct punto con
sus tres campos.
Lo que ahora nos interesa es saber como referenciar esos campos y acceder o modificar, por
tanto la información que contienen. Esto se consigue separando el identificador del campo de la
variable mediante un punto. Así:

punto_de_fuga.x = 0;
punto_de_fuga.y = 0;
punto_de_fuga.color = 10;

inicializa la cada uno de los campos de la variable punto de fuga con sus valores correspondientes. Está
claro que para acceder a los campos necesitamos alguna variable cuyo tipo sea nuestra estructura.
Si no tenemos variable no tenemos información (sería como hacer int = 6).

En el caso de la matriz tenemos tantas variables de tipo struct punto como las indicadas,
puesto que el punto separa el nombre de la variable del campo al que queremos acceder, la forma de
modificar una entrada de la matriz sería:

matriz_de_puntos[4].x = 6;
matriz_de_puntos.x[4] = 6; /* No sería correcto */

Esta última declaración se podría utilizar con una estructura de un tipo como:

struct otra
{
float x[10];
} matriz_de_puntos;

Con lo cual accederíamos al cuarto elemento del campo x de matriz_de_puntos que es una variable de
tipo struct otra constituida por una matriz de diez floats.

25
 Manual de la asignatura

Para terminar con la declaración struct indicar que es posible la declaración de estructuras
anidadas, es decir, un campo de una estructura puede ser otra estructura.

struct vector
{
float x;
float y;
float z;
};

struct poligono_cuadrado
{
struct vector p1;
struct vector p2;
struct vector p3;
struct vecto p4;
};

struct cubo
{
struct poligono_cuadrado cara[6];
int color;
struct vector posicion;
};

struct cubo mi_cubo;

Hemos declarado una variable (mi_cubo) de tipo struct cubo que es una estructura conteniendo un
valor entero que nos indica el color de nuestro objeto, una variable de tipo struct vector (posicion)
indicando la posición del objeto en un espacio de tres dimensiones (posicion tiene tres campos x,y,z
por tratarse de una struct vector) y una matriz de seis elemento en la que cada elemento es un struct
poligono_cuadrado, el cual está formado por cuadro vectores que indican los cuatro vértices del
cuadrado en 3D. Para aceder a todos los campos de esta variable necesitaríamos sentencias del tipo.
mi_cubo.color = 0;
mi_cubo.posicion.x = 3;
mi_cubo.posicion.y = 2;
mi_cubo.posicion.z = 6;
mi_cubo.cara[0].p1.x = 5;
/* Ahora acedemos a la coordenada 0 del tercer polígono
de la cara 0 de mi_cubo*/
mi_cubo.cara[0].p3.z = 6;

26
 Manual de la asignatura

Recursos requeridos: Una computadora con el lenguaje de programación C instalado.

Desarrollo: Solicitar al alumno desarrollar los siguientes programas
• Crear dos estructuras
struct distancia{
metros
centimetros
}
struct volumen {
longitud
anchura
altura
}
representan las dimensiones de una habitación.
Escribir un programa que lea las dimensiones de una habitación en metros y centímetros y calcule
su volumen.
• Escribir un programa que almacene en un array los nombres y números de teléfono de 10
personas. El programa debe leer los datos introducidos por el usuario y guardarlos en memoria.
Después debe ser capaz de buscar el nombre correspondiente a un número de teléfono y el teléfono
correspondiente a una persona. Ambas opciones deben se accesibles a través de un menú, así como
la opción de salir del programa. El menú debe tener el siguiente formato:
a) Buscar por nombre
b) Buscar por número de teléfono
c) Salir
Teclea una opción
Tiempo de ejecución: .2 horas.

27
 Manual de la asignatura

Práctica No. 4.
Nombre de la sesión de la práctica: Listas enlazadas.
Objetivo de la práctica: El alumno utilizará listas enlazadas para almacenar información.
Introducción:
Una lista es una estructura de datos secuencial.
Una manera de clasificarlas es por la forma de acceder al siguiente elemento:
• lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un
array.
• lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual.
Es necesario almacenar al menos la posición de memoria del primer elemento. Además es
dinámica, es decir, su tamaño cambia durante la ejecución del programa.

Una lista enlazada se puede definir recursivamente de la siguiente manera:

- una lista enlazada es una estructura vacía o

- un elemento de información y un enlace hacia una lista (un nodo).

Gráficamente se suele representar así:

Como se ha dicho anteriormente, pueden cambiar de tamaño, pero su ventaja fundamental es que son
flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una mayor lentitud a la hora
de acceder a cualquier elemento.

En la lista de la figura anterior se puede observar que hay dos elementos de información, x e y.
Supongamos que queremos añadir un nuevo nodo, con la información p, al comienzo de la lista. Para
hacerlo basta con crear ese nodo, introducir la información p, y hacer un enlace hacia el siguiente nodo,
que en este caso contiene la información x.
¿Qué ocurre si quisiéramos hacer lo mismo sobre un array?. En ese caso sería necesario desplazar todos
los elementos de información "hacia la derecha", para poder introducir el nuevo elemento, una
operación muy engorrosa.

Implementación
Para representar en lenguaje C esta estructura de datos se utilizarán punteros, un tipo de datos que
suministra el lenguaje. Se representará una lista vacía con la constante NULL. Se puede definir la lista
enlazada de la siguiente manera:

struct lista
{
int clave;
struct lista *sig;
};

28
 Manual de la asignatura

Como se puede observar, en este caso el elemento de información es simplemente un número entero.
Además se trata de una definición autorreferencial. Pueden hacerse definiciones más complejas.
Ejemplo:

struct cl
{
char nombre[20];
int edad;
};

struct lista
{
struct cl datos;
int clave;
struct lista *sig;
};

Cuando se crea una lista debe estar vacía. Por tanto para crearla se hace lo siguiente:

struct lista *L;

L = NULL;

Operaciones básicas sobre listas

Inserción al comienzo de una lista:
Es necesario utilizar una variable auxiliar, que se utiliza para crear el nuevo nodo mediante la reserva
de memoria y asignación de la clave. Posteriormente es necesario reorganizar los enlaces, es decir, el
nuevo nodo debe apuntar al que era el primer elemento de la lista y a su vez debe pasar a ser el primer
elemento.
En el siguiente ejemplo se muestra un programa que crea una lista con cuatro números. Notar que al
introducir al comienzo de la lista, los elementos quedan ordenados en sentido inverso al de su llegada.
Notar también que se ha utilizado un puntero auxiliar p para mantener correctamente los enlaces dentro
de la lista.

#include <stdlib.h>
struct lista
{
int clave;
struct lista *sig;
};

29
 Manual de la asignatura

int main(void)
{
struct lista *L;
struct lista *p;
int i;
L = NULL; /* Crea una lista vacia */

for (i = 4; i >= 1; i--)

{
/* Reserva memoria para un nodo */
p = (struct lista *) malloc(sizeof(struct lista));
p->clave = i; /* Introduce la informacion */

p->sig = L; /* reorganiza */
L = p; /* los enlaces */
}
return 0;
}

Recorrido de una lista.

La idea es ir avanzando desde el primer elemento hasta encontrar la lista vacía. Antes de acceder a la
estructura lista es fundamental saber si esa estructura existe, es decir, que no está vacía. En el caso de
estarlo o de no estar inicializada es posible que el programa falle y sea difícil detectar donde, y en
algunos casos puede abortarse inmediatamente la ejecución del programa, lo cual suele ser de gran
ayuda para la depuración.
Como se ha dicho antes, la lista enlazada es una estructura recursiva, y una posibilidad para su
recorrido es hacerlo de forma recursiva. A continuación se expone el código de un programa que
muestra el valor de la clave y almacena la suma de todos los valores en una variable pasada por
referencia (un puntero a entero). Por el hecho de ser un proceso recursivo se utiliza un procedimiento
para hacer el recorrido. Nótese como antes de hacer una operación sobre el elemento se comprueba si
existe.

int main(void)
{
struct lista *L;
struct lista *p;
int suma;
L = NULL;
/* crear la lista */
...

suma = 0;
recorrer(L, &suma);
return 0;
}

30
 Manual de la asignatura

void recorrer(struct lista *L, int *suma)

{
if (L != NULL) {
printf("%d, ", L->clave);
*suma = *suma + L->clave;
recorrer(L->sig, suma);
}
}

Sin embargo, a la hora de hacer un programa, es más eficaz si el recorrido se hace de forma iterativa.
En este caso se necesita una variable auxiliar que se desplace sobre la lista para no perder la referencia
al primer elemento. Se expone un programa que hace la misma operación que el anterior, pero sin
recursión.

int main(void)
{
struct lista *L;
struct lista *p;
int suma;
L = NULL;
/* crear la lista */
...
p = L;
suma = 0;
while (p != NULL) {
printf("%d, ", p->clave);
suma = suma + p->clave;
p = p->sig;
}
return 0;
}

A menudo resulta un poco difícil de entender la instrucción p = p->sig; Simplemente cambia la

dirección actual del puntero p por la dirección del siguiente enlace. También es común encontrar
instrucciones del estilo: p = p->sig->sig; Esto puede traducirse en dos instrucciones, de la siguiente
manera:
p = p->sig;
p = p->sig;
Obviamente sólo debe usarse cuando se sepa que p->sig es una estructura no vacía, puesto que si fuera
vacía, al hacer otra vez p = p->sig se produciría una referencia a memoria no válida.

31
 Manual de la asignatura

¿Y si queremos insertar en una posición arbitraria de la lista o queremos borrar un elemento? Como se
trata de operaciones algo más complicadas (tampoco mucho) se expone su desarrollo y sus variantes en
los siguientes tipos de listas: las listas ordenadas y las listas reorganizables. Asimismo se estudiarán
después las listas que incorporan cabecera y centinela. También se estudiarán las listas con doble
enlace. Todas las implementaciones se harán de forma iterativa, y se deja propuesta por ser más
sencilla su implementación recursiva, aunque es recomendable utilizar la versión iterativa.

Listas ordenadas
Las listas ordenadas son aquellas en las que la posición de cada elemento depende de su contenido. Por
ejemplo, podemos tener una lista enlazada que contenga el nombre y apellidos de un alumno y
queremos que los elementos -los alumnos- estén en la lista en orden alfabético.

La creación de una lista ordenada es igual que antes:

struct lista *L;

L = NULL;

Cuando haya que insertar un nuevo elemento en la lista ordenada hay que hacerlo en el lugar que le
corresponda, y esto depende del orden y de la clave escogidos. Este proceso se realiza en tres pasos:
1.- Localizar el lugar correspondiente al elemento a insertar. Se utilizan dos punteros: anterior y actual,
que garanticen la correcta posición de cada enlace.
2.- Reservar memoria para él (puede hacerse como primer paso). Se usa un puntero auxiliar (nuevo)
para reservar memoria.
3.- Enlazarlo. Esta es la parte más complicada, porque hay que considerar la diferencia de insertar al
principio, no importa si la lista está vacía, o insertar en otra posición. Se utilizan los tres punteros
antes definidos para actualizar los enlaces.

A continuación se expone un programa que realiza la inserción de un elemento en una lista ordenada.
Suponemos claves de tipo entero ordenadas ascendentemente.

#include <stdio.h>
#include <stdlib.h>

struct lista
{
int clave;
struct lista *sig;
};

/* prototipo */
void insertar(struct lista **L, int elem);

32
 Manual de la asignatura

int main(void)
{
struct lista *L;
L = NULL; /* Lista vacia */

/* para probar la insercion se han tomado 3 elementos */

insertar(&L, 0);
insertar(&L, 1);
insertar(&L, -1);
return 0;
}
void insertar(struct lista **L, int elem)
{
struct lista *actual, *anterior, *nuevo;

/* 1.- se busca su posicion */

anterior = actual = *L;
while (actual != NULL && actual->clave < elem) {
anterior = actual;
actual = actual->sig;
}

/* 2.- se crea el nodo */

nuevo = (struct lista *) malloc(sizeof(struct lista));
nuevo->clave = elem;

/* 3.- Se enlaza */
if (anterior == NULL || anterior == actual) { /* inserta al principio */
nuevo->sig = anterior;
*L = nuevo; /* importante: al insertar al principio actuliza la cabecera */
}
else { /* inserta entre medias o al final */
nuevo->sig = actual;
anterior->sig = nuevo;
}
}

Se puede apreciar que se pasa la lista L con el parámetro **L . La razón para hacer esto es que cuando
se inserta al comienzo de la lista (porque está vacía o es donde corresponde) se cambia la cabecera.

33
 Manual de la asignatura

Un ejemplo de prueba: suponer que se tiene esta lista enlazada: 1 -> 3 -> 5 -> NULL
Queremos insertar un 4. Al hacer la búsqueda el puntero actual apunta al 5. El puntero anterior apunta
al 3. Y nuevo contiene el valor 4. Como no se inserta al principio se hace que el enlace siguiente a
nuevo sea actual, es decir, el 5, y el enlace siguiente a anterior será nuevo, es decir, el 4.
La mejor manera de entender el funcionamiento es haciendo una serie de seguimientos a mano o con la
ayuda del depurador.

A continuación se explica el borrado de un elemento. El procedimiento consiste en localizarlo y

borrarlo si existe. Aquí también se distingue el caso de borrar al principio o borrar en cualquier otra
posición. Se puede observar que el algoritmo no tiene ningún problema si el elemento no existe o la
lista está vacía.

void borrar(struct lista **L, int elem)

{
struct lista *actual, *anterior;
/* 1.- busca su posicion. Es casi igual que en la insercion, ojo al (<) */
anterior = actual = *L;
while (actual != NULL && actual->clave < elem) {
anterior = actual;
actual = actual->sig;
}

/* 2.- Lo borra si existe */

if (actual != NULL && actual->clave == elem) {
if (anterior == actual) /* borrar el primero */
*L = actual->sig; /* o tambien (*L)->sig; */
else /* borrar en otro sitio */
anterior->sig = actual->sig;
free(actual);
}
}

Ejemplo: para borrar la clave '1' se indica así: borrar(&L, 1);

Listas doblemente enlazadas

Son listas que tienen un enlace con el elemento siguiente y con el anterior. Una ventaja que tienen es
que pueden recorrerse en ambos sentidos, ya sea para efectuar una operación con cada elemento o para
insertar/actualizar y borrar. La otra ventaja es que las búsquedas son algo más rápidas puesto que no
hace falta hacer referencia al elemento anterior. Su inconveniente es que ocupan más memoria por
nodo que una lista simple.

34
 Manual de la asignatura

Se realizará una implementación de lista ordenada con doble enlace que aproveche el uso de la
cabecera y el centinela. A continuación se muestra un gráfico que muestra una lista doblemente
enlazada con cabecera y centinela, para lo que se utiliza un único nodo que haga las veces de cabecera
y centinela.

- Declaración:

struct listaDE
{
int clave;
struct listaDE *ant,
*sig;
};

Procedimiento de creación:
void crearDE(struct listaDE **LDE)
{
*LDE = (struct listaDE *) malloc(sizeof(struct listaDE));
(*LDE)->sig = (*LDE)->ant = *LDE;
}

Procedimiento de inserción:

void insertarDE(struct listaDE *LDE, int elem)

{
struct listaDE *actual, *nuevo;

/* busca */
actual = LDE->sig;
LDE->clave = elem;

while (actual->clave < elem)

actual = actual->sig;

35
 Manual de la asignatura

/* crea */
nuevo = (struct listaDE *) malloc(sizeof(struct listaDE));
nuevo->clave = elem;

/* enlaza */
actual->ant->sig = nuevo;
nuevo->ant = actual->ant;
nuevo->sig = actual;
actual->ant = nuevo;
}

Procedimiento de borrado:
void borrarDE(struct listaDE *LDE, int elem)
{
struct listaDE *actual;

/* busca */
actual = LDE->sig;
LDE->clave = elem;

while (actual->clave < elem)

actual = actual->sig;

/* borra */
if (actual != LDE && actual->clave == elem) {
actual->sig->ant = actual->ant;
actual->ant->sig = actual->sig;
free(actual);
}
}

Para probarlo se pueden usar las siguientes instrucciones:

struct listaDE *LDE;

...
crearDE(&LDE);
insertarDE(LDE, 1);
borrarDE(LDE, 1);

36
 Manual de la asignatura

Listas circulares
Las listas circulares son aquellas en las que el último elemento tiene un enlace con el primero. Su uso
suele estar relacionado con las colas.

Recursos requeridos: Una computadora con el lenguaje de programación C instalado.

Desarrollo: Escriba un programa que concatene dos listas enlazadas de caracteres. El programa deberá
incluir la función concatenate que toma como argumentos apuntadores a ambas listas y que concatena
la segunda lista a la primera.
Tiempo de ejecución: Una hora.

37
 Manual de la asignatura

Práctica No. 5.
Nombre de la sesión de la práctica: Pilas.
Objetivo de la práctica: El alumno implementará una pila utilizando arreglos y listas ligadas.
Introducción:
La PILA es quizá la estructura de datos común con un acceso más restrictivo, y sin embargo es quizá
también la más usada en el funcionamiento diario de cualquier programa de cómputo.

La PILA cuenta únicamente con dos operaciones básicas: se puede insertar un dato al inicio de la pila,
y se puede remover un dato del inicio de la pila.

La pila, como puede inferirse, deriva su nombre de que los datos se apilan uno sobre otro, ocasionando
que en cualquier momento únicamente se tenga acceso al dato superior de la pila. La pila funciona
como si hicieran una pila de cajas de refrescos, cuando llega una nueva caja, la ponen hasta arriba de la
pila, ya que sería mucho trabajo levantar todas las cajas para poder meterla nueva caja hasta abajo.
Cuando se necesita un refresco se retira de la caja superior, si esta se vacía, entonces se remueve y se
prosigue con la siguiente caja. Como se habrán dado cuenta, existe la posibilidad de que una caja de
refrescos quede olvidada en la parte inferior de la pila y se eche a perder. ¡Sin embargo, un taquero con
éxito, debe ser capaz de terminar con toda la pila sin que ningún refresco se le eche a perder!

A las pilas se les conoce en la literatura como estructuras LIFO por sus siglas en inglés (Last In - First
Out), que quiere decir, que el último que entro es el primero que sale. De ahí el consabido dicho de
"Los últimos serán los primeros".

Las pilas tienen un campo de aplicación muy grande en los programas, el más común es la
recursividad, aunque tal vez no lo notaron, ya que el compilador lo hace por ustedes, para poder
implementar cualquier rutina recursiva es necesario contar con una pila. En la sección de ejercicios se
revisarán aplicaciones de una pila para implementar recursión y para analizar una sentencia.

Una buena implementación de pila debe de tomar en cuenta dos puntos. El primero es que no debe
permitir el remover un dato cuando la pila esta vacía, y el segundo es que no debe permitir que se
inserten datos a la pila si esta ya esta llena.
Ejemplo de implementación en pseudocódigo de pila utilizando la memoria estática
#include<stdio.h>;
#define MAXPILA 100; (* TAMAÑO MAXIMO DE LA PILA *)
int MemPila[MAXPILA + 1];
int SP; // ESTA VARIABLE NOS SERVIRA PARA
// SABER CUAL ES EL ELEMENTO SUPERIOR
// DE LA PILA

38
 Manual de la asignatura

void Insertar(int dato)

{
(* LA VARIABLE SP, APUNTA A LA PRIMERA POSICION
VACIA DE LA PILA *)
MemPila[SP++]=dato;
if (SP > MAXPILA){
(* AQUI VA UN ERROR INDICANDO QUE SE SOBREPASO
EL LIMITE DE LA PILA *)
}
}
int Remover(void)
{
(* DECREMENTA EL INDICE DE LA PILA *)
if (--SP > 0) then {
return(MemPila[SP]);
}
else {
(* AQUI VA UN ERROR INDICANDO QUE LA PILA ESTA
VACIA Y NO SE PUEDE REMOVER NINGUN DATO *)
}
}
int main(void) {
SP=0; (* INICIALIZA EL INDICE DE LA PILA
AQ UI DEBEN DE PONER SU CODIGO PARA USAR LA PILA *)
}
Recursos requeridos: Una computadora con el lenguaje de programación C instalado.
Desarrollo: Solicitar al alumno el desarrollo de los siguientes programas.
• Implementar una pila utilizando un arreglo. La entrada son números enteros y deberá realizar
todas las operaciones que aplican a la pila.
• Implementar una pila utilizando una lista ligada. La entrada son números enteros y deberá
realizar todas las operaciones que aplican a la pila.
Tiempo de ejecución: 4 horas.

39
 Manual de la asignatura

Práctica No. 6.
Nombre de la sesión de la práctica:Colas.
Objetivo de la práctica: El alumno implementará la estructura de datos cola utilizando un arreglo y
listas ligadas.
Introducción:
Las COLAS, al igual que las pilas, son una estructura de datos de acceso restrictivo. Al igual que en
una pila únicamente se cuenta con 2 operaciones, la operación insertar y la operación remover.

La diferencia entre una cola y una pila es que en la cola (como en una cola para comprar boletos), el
primero que llegó es al primero que se atiende, es decir, una cola tiene un inicio y un final, los nuevos
elementos que llegan se agregan al final de la cola, cuando se remueve un elemento, se remueve del
inicio de la misma.

A las colas se les conoce como estructuras FIFO (First In - First Out), que quiere decir que el primero
que entra, es el primero que sale.

Existe una implementación muy común de la cola que se conoce como cola circular, esta
implementación aprovecha el espacio en memoria de la computadora de la siguiente forma:
inicialmente aparta un espacio para la cola, conforme llegan los elementos los va agregando al final,
cuando remueve un elemento lo hace del inicio de la cola, una vez que ha terminado con el espacio de
memoria que había apartado, revisa si ya se liberó el espacio al inicio de la cola y "da la vuelta" para
aprovechar el espacio al máximo, la implementacion que se presenta a continuación es la de una cola
circular.

Al igual que en la pila, en la cola es muy importante revisar si todavía hay espacio para seguir
guardando elementos, o si la cola esta vacía.
Ejemplo de implementación en pseudocódigo de cola utilizando la memoria estática

#include<stdio.h>;
#define MAXCOLA 100; (* TAMAÑO MAXIMO DE LA COLA *)

int MemCola[MAXCOLA + 1];

int Inicio; (* INICIO DE LA COLA *)
int Fin; (* FIN DE LA COLA *)

void Insertar(int dato)

{
(* LA VARIABLE FIN, APUNTA A LA PRIMERA POSICION
VACIA DE LA COLA *)
MemCola[Fin++]=dato;
if (Fin > MAXCOLA) {

40
 Manual de la asignatura

(* SI YA SE LLENO TODA LA MEMORIA HAY QUE

DAR LA VUELTA *)
Fin=0;
}
if (Inicio == Fin) {
(* SI EL FIN ALCANZO AL INICIO, QUIERE DECIR QUE
DIO TODA LA VUELTA Y YA NO HAY ESPACIOS
LIBRES, POR LO QUE HAY QUE MARCAR UN ERROR
DE QUE LA COLA ESTA LLENA *)
}
}

int Remover(void)
{
if (Inicio == Fin) {
(* EL INICIO ES IGUAL AL FIN, QUIERE DECIR QUE
NO HAY DATOS EN LA COLA, POR LO TANTO
MANDA UN ERROR DE COLA VACIA *)
}
else {
Remover=MemCola[Inicio++]; (*EL DATO A DEVOLVER
ES EL QUE ESTA AL INICIO DE LA COLA *)
(* MUEVE EL INICIO DE LA COLA *)
if (Inicio > MAXCOLA) {
(* SI LLEGO AL FINAL, DA LA VUELTA *)
Inicio=0;
}
}
}

int main(void){
Inicio=0; (* INICIALIZA EL INICIO DE LA COLA *)
Fin=0; (* INICIALIZA EL FINAL DE LA COLA *)
(* AQUI DEBEN DE PONER SU CODIGO PARA USAR LA COLA*)
}
Recursos requeridos: Una computadora con el lenguaje de programación C instalado.
Desarrollo: Solicitar al alumno el desarrollo de los siguientes programas.
• Implementar una cola utilizando un arreglo. La entrada son números enteros y deberá realizar
todas las operaciones que aplican a la cola.
• Implementar una cola utilizando una lista ligada. La entrada son números enteros y deberá
realizar todas las operaciones que aplican a la cola.
Tiempo de ejecución: 4 horas.

41
 Manual de la asignatura

Práctica No. 7.
Nombre de la sesión de la práctica: Árboles.
Objetivo de la práctica: El alumno implementará la estructura de datos árbol.
Introducción:
Un árbol es una estructura de datos, que puede definirse de forma recursiva como:
• Una estructura vacía o
• Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol,
disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un
árbol binario.
Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo (ver grafos): un árbol es un grafo acíclico, conexo
y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par
de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las
representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta
implementación.

Representación mediante un grafo:

Figura 1

En la computación se utiliza mucho una estructura de datos, que son los árboles binarios. Estos árboles
tienen 0, 1 ó 2 descendientes como máximo. El árbol de la figura anterior es un ejemplo válido de árbol
binario.

Nomenclatura sobre árboles

• Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.
• Rama: arista entre dos nodos.
• Antecesor: un nodo X es es antecesor de un nodo Y si por alguna de las ramas de X se puede
llegar a Y.
• Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.

42
 Manual de la asignatura

• Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d
tiene grado 0, a tiene grado 2.
•
• Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d
• Nodo interno: aquel que tiene al menos un descendiente.
• Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel
del nodo a es 1 (es un convenio), el nivel del nodo e es 3.
• Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.
• Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es
3.

Aclaraciones: se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo
podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la
raíz, y a y d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre un
computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz.

Declaración de árbol binario

Se definirá el árbol con una clave de tipo entero (puede ser cualquier otra tipo de datos) y dos hijos:
izquierdo (izq) y derecho (der). Para representar los enlaces con los hijos se utilizan punteros. El árbol
vacío se representará con un puntero nulo.

Un árbol binario puede declararse de la siguiente manera:

typedef struct tarbol
{
int clave;
struct tarbol *izq,*der;
} tarbol;

Otras declaraciones también añaden un enlace al nodo padre, pero no se estudiarán aquí.

Recorridos sobre árboles binarios

Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel. Puesto
que los árboles no son secuenciales como las listas, hay que buscar estrategias alternativas para visitar
todos los nodos.

Recorridos en profundidad:
Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la
clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el
subárbol derecho. Es un proceso recursivo por naturaleza.
Si se hace el recorrido en preorden del árbol de la figura 1 las visitas serían en el orden siguiente:
a,b,d,c,e,f.

43
 Manual de la asignatura

void preorden(tarbol *a)

{
if (a != NULL) {
visitar(a);
preorden(a->izq);
preorden(a->der);
}
}

Recorrido en inorden u orden central: se visita el subárbol izquierdo, el nodo actual, y después se
visita el subárbol derecho. En el ejemplo de la figura 1 las visitas serían en este orden: b,d,a,e,c,f.

void inorden(tarbol *a)

{
if (a != NULL) {
inorden(a->izq);
visitar(a);
inorden(a->der);
}
}

Recorrido en postorden: se visitan primero el subárbol izquierdo, después el subárbol derecho, y por
último el nodo actual. En el ejemplo de la figura 1 el recorrido quedaría así: d,b,e,f,c,a.

void postorden(arbol *a)

{
if (a != NULL) {
postorden(a->izq);
postorden(a->der);
visitar(a);
}
}

La ventaja del recorrido en postorden es que permite borrar el árbol de forma consistente. Es decir, si
visitar se traduce por borrar el nodo actual, al ejecutar este recorrido se borrará el árbol o subárbol que
se pasa como parámetro. La razón para hacer esto es que no se debe borrar un nodo y después sus
subárboles, porque al borrarlo se pueden perder los enlaces, y aunque no se perdieran se rompe con la
regla de manipular una estructura de datos inexistente. Una alternativa es utilizar una variable auxiliar,
pero es innecesario aplicando este recorrido.
- Recorrido en amplitud:

44
 Manual de la asignatura

Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay
uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más.
Si se hace el recorrido en amplitud del árbol de la figura una visitaría los nodos en este orden:
a,b,c,d,e,f
En este caso el recorrido no se realizará de forma recursiva sino iterativa, utilizando una cola (ver
Colas) como estructura de datos auxiliar. El procedimiento consiste en encolar (si no están vacíos) los
subárboles izquierdo y derecho del nodo extraido de la cola, y seguir desencolando y encolando hasta
que la cola esté vacía.
En la codificación que viene a continuación no se implementan las operaciones sobre colas.

void amplitud(tarbol *a)

{
tCola cola; /* las claves de la cola serán de tipo árbol binario */
arbol *aux;

if (a != NULL) {
CrearCola(cola);
encolar(cola, a);
while (!colavacia(cola)) {
desencolar(cola, aux);
visitar(aux);
if (aux->izq != NULL) encolar(cola, aux->izq);
if (aux->der != NULL) encolar(cola, aux->der);
}
}
}
Por último, considérese la sustitución de la cola por una pila en el recorrido en amplitud. ¿Qué tipo de
recorrido se obtiene?

Construcción de un árbol binario

Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin embargo no se ha

estudiado ningún método para crearlos. A continuación se estudia un método para crear un árbol
binario que no tenga claves repetidas partiendo de su recorrido en preorden e inorden, almacenados en
sendos arrays.

Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno
es capaz de construir el árbol viendo sus recorridos pero sin haber visto el árbol terminado.

Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede determinarse que la raíz es
el primer elemento del recorrido en preorden. Ese elemento se busca en el array inorden. Los elementos
en el array inorden entre izq y la raíz forman el subárbol izquierdo. Asimismo los elementos entre der y
la raíz forman el subárbol derecho. Por tanto se tiene este árbol:

45
 Manual de la asignatura

Recursos requeridos: Una computadora con el lenguaje de programación C instalado.

Desarrollo: Solicitar al alumno el desarrollo del siguiente programa.
• Programa que genera números aleatorios y los inserta en un árbol binario. Además de obtener los
niveles máximos y mínimo saca la diferencia de estos mismos y nos dice cuántas veces de las 50
se repitieron cifras de la diferencia.
• Programa que evalúa una expresión aritmética cuyos operadores y operandos estan almacenados
en un árbol binario.
Tiempo de ejecución: .4 horas.

46
 Manual de la asignatura

Práctica No. 8.
Nombre de la sesión de la práctica: Grafos.
Objetivo de la práctica: El alumno implementará programas utilizando grafos.
Introducción:
Un grafo es un objeto matemático que se utiliza para representar circuitos, redes, etc. Los grafos son
muy utilizados en computación, ya que permiten resolver problemas muy complejos.

Imaginemos que disponemos de una serie de ciudades y de carreteras que las unen. De cada ciudad
saldrán varias carreteras, por lo que para ir de una ciudad a otra se podrán tomar diversos caminos.
Cada carretera tendrá un coste asociado (por ejemplo, la longitud de la misma). Gracias a la
representación por grafos podremos elegir el camino más corto que conecta dos ciudades, determinar si
es posible llegar de una ciudad a otra, si desde cualquier ciudad existe un camino que llegue a cualquier
otra, etc.

Conceptos básicos.
Un grafo consta de vértices (o nodos) y aristas. Los vértices son objetos que contienen información y
las aristas son conexiones entre vértices. Para representarlos, se suelen utilizar puntos para los vértices
y líneas para las conexiones, aunque hay que recordar siempre que la definición de un grafo no depende
de su representación.

Un camino entre dos vértices es una lista de vértices en la que dos elementos sucesivos están
conectados por una arista del grafo. Así, el camino AJLOE es un camino que comienza en el vértice A
y pasa por los vértices J,L y O (en ese orden) y al final va del O al E. El grafo será conexo si existe un
camino desde cualquier nodo del grafo hasta cualquier otro. Si no es conexo constará de varias
componentes conexas.

Un camino simple es un camino desde un nodo a otro en el que ningún nodo se repite (no se pasa dos
veces). Si el camino simple tiene como primer y último elemento al mismo nodo se denomina ciclo.
Cuando el grafo no tiene ciclos tenemos un árbol (ver árboles). Varios árboles independientes forman
un bosque. Un árbol de expansión de un grafo es una reducción del grafo en el que solo entran a formar
parte el número mínimo de aristas que forman un árbol y conectan a todos los nodos.

Según el número de aristas que contiene, un grafo es completo si cuenta con todas las aristas posibles
(es decir, todos los nodos están conectados con todos), disperso si tiene relativamente pocas aristas y
denso si le faltan pocas para ser completo.

Las aristas son la mayor parte de las veces bidireccionales, es decir, si una arista conecta dos nodos A y
B se puede recorrer tanto en sentido hacia B como en sentido hacia A: estos son llamados grafos no
dirigidos. Sin embargo, en ocasiones tenemos que las uniones son unidireccionales. Estas uniones se
suelen dibujar con una flecha y definen un grafo dirigido. Cuando las aristas llevan un coste asociado
(un entero al que se denomina peso) el grafo es ponderado. Una red es un grafo dirigido y ponderado.

47
 Manual de la asignatura

Representación de grafos
Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de
datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptarán tiempos distintos
dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en
función del número de vértices y el de aristas, por lo que la utilización de una representación u otra
dependerá en gran medida de si el grafo es denso o disperso.

Para nombrar los nodos utilizaremos letras mayúsculas, aunque en el código deberemos hacer
corresponder cada nodo con un entero entre 1 y V (número de vértices) de cara a la manipulación de
los mismos.

Representación por matriz de adyacencia

Es la forma más común de representación y la más directa. Consiste en una tabla de tamaño V x V, en
que la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el
valor será 0. Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el peso de la
arista. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 (o con el peso) tanto la
entrada a[i][j] como la entrada a[j][i], puesto que se puede recorrer en ambos sentidos.

int V,A;
int a[maxV][maxV];

void inicializar()
{
int i,x,y,p;
char v1,v2;
// Leer V y A
memset(a,0,sizeof(a));
for (i=1; i<=A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&p);
x=v1-'A'; y=v2-'A';
a[x][y]=p; a[y][x]=p;
}
}

En esta implementación se ha supuesto que los vértices se nombran con una letra mayúscula y no hay
errores en la entrada. Evidentemente, cada problema tendrá una forma de entrada distinta y la
inicialización será conveniente adaptarla a cada situación. En todo caso, esta operación es sencilla si el
número de nodos es pequeño. Si, por el contrario, la entrada fuese muy grande se pueden almacenar los
nombres de nodos en un árbol binario de búsqueda o utilizar una tabla de dispersión, asignando un
entero a cada nodo, que será el utilizado en la matriz de adyacencia.

Como se puede apreciar, la matriz de adyacencia siempre ocupa un espacio de V*V, es decir, depende
solamente del número de nodos y no del de aristas, por lo que será útil para representar grafos densos.

48
 Manual de la asignatura

Representación por lista de adyacencia

Otra forma de representar un grafo es por medio de listas que definen las aristas que conectan los
nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los
cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un
elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo
es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia al nodo A.

Las listas de adyacencia serán estructuras que contendrán un valor entero (el número que identifica al
nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado. En el
ejemplo se ha utilizado un nodo z ficticio en la cola (ver listas, apartado cabeceras y centinelas).

struct nodo
{
int v;
int p;
nodo *sig;
};

int V,A; // vértices y aristas del grafo

struct nodo *a[maxV], *z;

void inicializar()
{
int i,x,y,peso;
char v1,v2;
struct nodo *t;
z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;
for (i=0; i<V; i++)
a[i]=z;
for (i=0; i<A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&peso);
x=v1-'A'; y=v2-'A';

t=(struct nodo *)malloc(sizeof(struct nodo));

t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;

t=(struct nodo *)malloc(sizeof(struct nodo));

t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;
}
}

En este caso el espacio ocupado es O(V + A), muy distinto del necesario en la matriz de adyacencia,
que era de O(V2). La representación por listas de adyacencia, por tanto, será más adecuada para grafos
dispersos.

49
 Manual de la asignatura

Hay que tener en cuenta un aspecto importante y es que la implementación con listas enlazadas
determina fuertemente el tratamiento del grafo posterior. Como se puede ver en el código, los nodos se
van añadiendo a las listas según se leen las aristas, por lo que nos encontramos que un mismo grafo con
un orden distinto de las aristas en la entrada producirá listas de adyacencia diferentes y por ello el orden
en que los nodos se procesen variará. Una consecuencia de esto es que si un problema tiene varias
soluciones la primera que se encuentre dependerá de la entrada dada. Podría presentarse el caso de
tener varias soluciones y tener que mostrarlas siguiendo un determinado orden. Ante una situación así
podría ser muy conveniente modificar la forma de meter los nodos en la lista (por ejemplo, hacerlo al
final y no al principio, o incluso insertarlo en una posición adecuada), de manera que el algoritmo
mismo diera las soluciones ya ordenadas.
Recursos requeridos: Una computadora con el lenguaje de programación C instalado.
Desarrollo: Solicitar al alumno el desarrollo de los siguientes programas.
• Crear un grafo con datos enteros y realizar la búsqueda de un elemento en profundidad.
• Crear un grafo con datos enteros y realizar una búsqueda de un elemento en amplitud.
Tiempo de ejecución: .4 horas.

50