Estructura de datos elaboró: lic. Dora Araceli Cruz Huerta



Descargar 0,73 Mb.
Página1/6
Fecha de conversión14.03.2017
Tamaño0,73 Mb.
  1   2   3   4   5   6

Tecnológico de Estudios Superiores de Ecatepec











ESTRUCTURA DE DATOS
Elaboró:

LIC. Dora Araceli Cruz Huerta

2011


Departamento

de

Licenciatura en Informática



Av. Valle del Mayo Esq. Av. Hank González Col. Valle de Anáhuac C.P. 55210 Ecatepec de Morelos, Edo. de México

Tecnológico de Estudios Superiores de Ecatepec

Dirección Académica

Subdirección de Estudios Profesionales

Licenciatura en Informática



APUNTES DE LA ASIGNATURA

ESTRUCTURA DE DATOS

Por:
Lic. Cruz Huerta Dora Araceli.

4 DE JUNIO DE 2004




OBJETIVO:
El alumno aprenderá las principales estructuras de datos desde un punto de vista abstracto y las operaciones que se puedan realizar sobre ellas, aplicando en forma práctica los conceptos adquiridos mediante resolución de problemas.
TEMARIO
1.- TIPOS DE DATOS
1.1 Tipos de datos.

1.1.1 Tipos de datos simples.

1.1.1.1 Definición de bit, byte, carácter y palabra.

1.1.1.2 Manipulación de bits.

1.1.1.3 Representación de datos simples.

1.1.2 Tipos de datos abstractos.

1.2 Estructuras de datos.

1.2.1 Definición.

1.2.2 Clasificación.

1.2.2.1 Lineales y no lineales.

1.2.2.2 Dinámicas y estáticas.
2.- ESTRUCTURAS LINEALES
2.1 Arreglos.

2.1.1 Definición.

2.1.2 Unidimensionales.

2.1.3 Bidimensionales.

2.1.4 Multidimensionales.

2.1.5 Resolución de problemas con arreglos.

2.1.6 Clases para la implementación de arreglos.

2.2 Pilas.

2.2.1 Definición.

2.2.2 Operaciones.

2.2.3 Clases para la implementación de pilas.

2.3 Colas.

2.3.1 Definición.

2.3.2 Tipos.

2.3.2.1 Colas simples.

2.3.2.2 Colas circulares.

2.3.2.3 Colas dobles.

2.3.3 Operaciones.

2.3.4 Clases para la implementación de colas.


3.- LISTAS ENLAZADAS
3.1 Listas enlazadas.

3.1.1 Simples.

3.1.2 Dobles.

3.1.3 Circulares.

3.1.4 Multilistas.

3.1.5 Clases para la implementación de listas.


4.- ESTRUCTURAS NO LINEALES
4.1 Árboles.

4.1.1 Definición.

4.1.2 Representación en memoria de árboles.

4.1.2.1 Árboles generales.

4.1.2.2 Árboles binarios.

4.1.3 Recorridos en un árbol binario.

4.1.3.1 Preorden.

4.1.3.2 Inorden.

4.1.3.3 Posorden.

4.1.4 Balanceo de árboles binarios.

4.1.5 Clases para la implementación de árboles.

4.2 Grafos.

4.2.1 Definición.

4.2.2 Tipos de grafos.

4.2.3 Representación de grafos en memoria.

4.2.4 Clases para la implementación de grafos.




UNIDAD1 TIPOS DE DATOS

1.1 Tipos de datos.
El manejo de la información en cualquier lenguaje de programación se realiza mediante diferentes clases de datos. 



  Entero    (Integer)

Números enteros sin parte decimal.

Carácter    (Char)

Caracteres del código ASCII

Boleano (Boolean)

Pueden contener los valores de falso o verdadero

Real

Números que pueden incluir una parte decimal

Cadena (String)

En una secuencia de caracteres que se trata como un solo dato.

Un programa debe ser capaz de manejar diferentes tipos de datos, como pueden ser números enteros, reales, caracteres, cadenas de caracteres, etc. Para lograr el manejo de toda esta información. Algunos de los más importantes se citan en seguida:



Tipos enteros
En esta categoría generalmente cuenta con 5 tipos diferentes, cada uno abarca un rango específico de valores y utilizan una diferente cantidad de memoria dependiendo de ese rango. Naturalmente el trabajar con rangos menores nos ofrece una mayor velocidad y menor espacio en memoria, pero si se utilizan enteros largos se cuenta con mayor presición. Los tipos de enteros en  son:



Tipo 

Rango de valores que acepta 

Integer  (Entero)

-32,768 a 32,767 

Word     (Palabra)

0 a 65535 

ShortInt  (Entero corto)

-128 a 127 

Byte 

0 a 255 

LongInt  (Entero largo)

-2,147,483,648 a 2,147,483,648 

Al utilizar los tipos enteros es posible representar en el programa un número en formato hexadecimal, para hacer esto solo se le antepone el símbolo "$" al valor hexadecimal, al momento de visualizar dicho valor, o utilizarlo en alguna operación será como decimal casi siempre en todos los casos que se utilice.



Tipos reales
Los números reales son aquellos que cuentan con una parte decimal. En algunos lenguajes de programación se tienen varios tipos de datos reales, pero no se puede utilizar, más que el tipo real, en máquinas que no cuenten con un coprocesador matemático. Los tipos de datos reales son:



Tipo 

Rango de valores que acepta 

Real  )

2.9E-39 a 1.7E38

Single 

1.5E-45 a 3.4E38

Double 

5.0E-324 a 1.7E308

Extended 

1.9E-4851 a 1.1E4932

Comp 

-9.2E18 a 9.2E18

Los números reales deben llevar por fuerza al menos un dígito de cada lado del punto decimal así sea éste un cero. Como ejemplo, el número 5 debe representarse como: 5.0, el .5 como 0.5 , etc.

 En este tipo de datos se utiliza la notación científica, que es igual a la de las calculadoras, el dígito que se encuentra a continuación de la E representa la potencia a la que se elevará el número 10 para multiplicarlo por la cantidad a la izquierda de dicha E:


3.0E5 = 3.0 * 10^5 = 3.0 * 100000 = 300000 
1.5E-4 = 1.5 * 10^-4 = 1.5 * 0.0001 = 0.00015 

Tipos carácter

Los caracteres son cada uno de los símbolos que forman el código ASCII.. Los caracteres se especifican entre apostrofes:





'a' 

'B' 

'2' '#' 

El tipo Char es un tipo ordinal en algunos lenguajes de programación, esto quiere decir que sus elementos válidos siguen una secuencia ordenada de valores individuales. La secuencia de caracteres para este tipo corresponde al número del código ASCII, del 0 al 255.

Es posible accesar a cada uno de los caracteres utilizando un signo # antes de su valor correspondiente, por ejemplo, la letra A puede ser representada como #65, el retorno de carro, o enter, se representa como #13, y así cualquier carácter.

Tipo cadena
Las cadenas son secuencias de caracteres o arreglos que tienen una longitud máxima de 255 caracteres. Se definen entre apostrofes.
 


 
Nombre : Cadena; 

 
Nombre = 'Ernesto Chávez'; 


 

La cadena 'Ernesto Chávez' es almacenada en la variable nombre definida como tipo cadena.

 El tamaño por defecto para un tipo string es de 255 caracteres, pero es posible definir uno mas pequeño utilizando el siguiente formato:

Variable : Cadena[Tamaño];
Donde Variable es la variable a definir y Tamaño es el número máximo de caracteres que podrá contener esa variable (naturalmente mayor a 0 y menor a 256).

 Es posible acceder a un solo carácter de una cadena utilizando inmediatamente después del nombre de la misma la posición del carácter encerrada entre corchetes. Por ejemplo:



Nombre : String[30];  
{Permite un máximo de 30 caracteres en la variable} 

Nombre := 'Ernesto Chávez';  

Escribir (Nombre[5]);  
{Visualiza el 5to carácter de la cadena} 
 

Tipos lógicos

Este tipo de datos tienen la peculiaridad de que solo pueden tomar dos tipos de datos: verdadero o falso, el verdadero puede ser representado por su nombre en inglés: True y el falso por False; también se representan por 1 y por 0 respectivamente.


El tipo está definido como Boolean.

Los datos lógicos tienen una enorme aplicación en la evaluación de ciertos procesos, así como en el control de flujo de los programas. 




      1. Tipos de datos simples.

Los datos a procesar por una computadora se pueden clasificar en:




  • Simples

  • Estructurados

La principal característica de los datos simples es que ocupan solo una casilla de memoria, por lo tanto una variable simple hace referencia a un único valor a la vez. Dentro de este grupo de datos se encuentran: enteros, reales, carácter, boleanos, enumerados y subrrango (los dos últimos no existen en algunos lenguajes de programación).


Los datos estructurados se caracterizan por el hecho de que con un nombre (Identificador de variable) se hace referencia a un grupo de casillas de memoria). Es decir, un dato estructurado tiene varios componentes. Cada uno de los componentes puede ser un dato simple o estructurado. Sin embargo los componentes básicos de cualquier dato estructurado son datos simples.


Todas las estructuras de datos constituyen un aspecto muy importante en la computación, estas son:



  • Arreglos.

  • Registros.

  • conjuntos.



        1. Definición de bit, byte, carácter y palabra.


Bit: es una síntesis de dos términos en inglés: Binary digit, que en español significan dígito binario, o lo que es lo mismo, número (dígito) con dos posibles valores (binario). El término surge de usar las dos primeras letras de Binary con la última de digit.: bit. Es la unidad de información más sencilla posible en el sistema binario.
Byte: Unidad de información que consta de 8 bits equivalente a un único carácter, como una letra, número o signo de puntuación.
Carácter: Es un elemento tomado de un conjunto de símbolos. Un ejemplo de un conjunto de símbolos es {0,1,2,3,4,5,6,7,8,9,A,B,C....Y,z,¡,-,+,*} en el cual se incluyen dígitos, los caracteres del alfabeto y algunos caracteres especiales. Un compilador de lenguaje reconoce un conjunto particular de caracteres.
Palabra: Conjunto de bits que, como unidad elemental, puede manipular una computadora. La longitud en bits de una palabra en una computadora puede ser de 8, 16, 32, etc., y depende del microprocesador de su unidad central de proceso.
1.1.1.2 Manipulación de bits.
Ahora el ser humano digitaliza su entorno. Pero, ¿qué significa digitalizar? Digitalizar es traducir información como textos, imágenes o sonidos, a un formato que puedan entender los microprocesadores, y éstos sólo están capacitados para manejar los valores unos y ceros. En efecto, para tu microprocesador todo lo que ves en estos momentos en la pantalla se maneja con unos o ceros. Esto es porque la computadora maneja un sistema binario, que se llama así porque sólo acepta dos valores (0 y 1).
Tal sencillez tiene su razón de ser: los microprocesadores son circuitos electrónicos plasmados en un material llamado silicio (algo parecido al vidrio) que procesan diminutos impulsos eléctricos, el más pequeño de los cuales es conocido por el nombre de bit.
Como impulso eléctrico, el microprocesador sólo puede detectar cuando un bit tiene carga eléctrica --su valor sería, en este caso, 1-- o cuando no la tienen --su valor sería 0 - En este ejemplo manejamos los valores unos y ceros de manera un tanto arbitraria, ya que la presencia o ausencia de carga eléctrica en un bit puede ser interpretada como una gran diversidad de valores: cierto y falso, hombre o mujer, T o J, etc.
La eficacia de las computadoras no se basa en la complejidad de su fundamento lógico, que como vimos se reduce a manejar dos posibles valores, sino de la velocidad con la que se aplica dicha lógica: los microprocesadores actuales pueden procesar varios millones de bits en un sólo segundo.

Un bit puede representar solamente dos valores. Dos bits, cuatro posibles valores y ocho bits 256 posibles combinaciones de unos y ceros. Una unidad de medida muy utilizada en la informática es el byte, que consiste en la agrupación de ocho bits.


Ejemplo de combinaciones posibles por número de bits
Posibles combinaciones de unos y ceros usando dos bits 4:
00, 01, 11, 10
Posibles combinaciones de unos y ceros usando ocho bits 256:
00000000, 00000001, 00000011, 00000111 […] 11111111
Usando grupos de 8 bits (es decir, bytes) es posible representar a todos los caracteres que conforman el abecedario, incluyendo las mayúsculas y los signos especiales, como el de moneda o los acentos, de tal suerte que cuando se oprime la "e" en el teclado, el microprocesador recibe un paquete de 8 bits con la siguiente combinación de valores:
Valor de la letra "e" minúscula en bits:


0

1

1

0

0

1

0

1

Pero si en cambio se presiona la misma tecla en mayúsculas, el paquete de bits que se estará mandando al microprocesador sería el siguiente:

Valor de la letra "E" mayúscula en bits:


0

1

0

0

0

1

0

1

Mediante combinaciones de bits y bytes es posible representar una cantidad infinita de cosas: desde bibliotecas completas hasta juegos y películas, todo un universo de información que puede estar en diversas formas; textos, imágenes y sonidos.


Se dice que algunas computadoras tienen aritmética decimal en lugar de binaria. Cuatro bits proporcionan 16 combinaciones, utilizadas para los 10 dígitos de 0 a 9, con 6 combinaciones sin utilizar. El número 1944 se muestra abajo codificado en decimal y en binario, utilizando 16 bits en cada ejemplo:


  • Decimal: 0001 1001 0100 0100




  • binario: 0000011110011000


1.1.1.3 Representación de datos simples.

Los datos que utilizan los programas se pueden clasificar en base a diferentes criterios. Uno de los más significativos es aquel que dice que todos los datos que utilizan los programas son simples o compuestos.


Un dato simple es indivisible (atómico), es decir, no se puede descomponer.


  • Ejemplo 1: Un año es un dato simple.




  • Año...: 2006

Un año se expresa con un número entero, el cual no se puede descomponer. Sin embargo, un dato compuesto está formado por otros datos.




  • Ejemplo 2: Una fecha es un dato compuesto por tres datos simples (día, mes, año).




  • Fecha:

  • Día...: 30

  • Mes...: 11

  • Año...: 2006



  • Ejemplo 3: Otro ejemplo de dato simple es una letra.




  • Letra...: t

Una letra se representa con un carácter del alfabeto. Pero, cuando varias letras se agrupan, entonces se obtiene un dato compuesto por varios caracteres.




  • Ejemplo 4: Para formar un nombre de persona se utilizan varios caracteres.




  • Nombre...: Ana (dato compuesto por tres caracteres)


Clasificación de los tipos de datos simples

Los tipos de datos simples se clasifican en predefinidos y definidos por el programador. La clasificación completa es:



  1   2   3   4   5   6


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal