Estructura De Datos2

E n P o s d e l a E x c e l e n c i a.

STITUTO ITUTO TECNOLOGICO “SPENCER W.KIMBALL”.

CURSO:

ESTRUCTURA DE DATOS

CATEDRATICO:

WAGNER OROZCO

ESTUDIANTE: DELMAR O. MORALES PEREZ

GRADO:

6to: PC

“B”

SECCION: CLAVE:

“34”

FECHA DE ENTREGA:

Computación ____20 20-FEB-2009___________

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

1

E n P o s d e l a E x c e l e n c i a.

INFORMACION Y DATOS En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema. Una estructura de datos define la organización e interrelación de éstos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son: • • •

Alta, adicionar un nuevo valor a la estructura. Baja, borrar un valor de la estructura. Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma SECUENCIAL o BINARIO (siempre (siempre y cuando los datos estén ordenados)...

Otras operaciones que se pueden realizar son: • •

Ordenamiento, de los elementos pertenecientes a la estructura. Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

Información La información no es un dato conjunto cualquiera de ellos. Es más bien una colección de hechos significativos y pertinentes, para el organismo u organización que los percibe. La definición de información es la siguiente: Información es un conjunto de datos significativos y pertinentes que describan sucesos o entidades. DATOS SIGNIFICATIVOS. Para ser significativos, los datos deben constar de símbolos reconocibles, estar completos y expresar una idea no ambigua. Los símbolos de los datos son reconocibles cuando pueden ser correctamente interpretados. Muchos tipos diferentes de símbolos comprensibles se usan para transmitir datos. La integridad significa que todos los datos requeridos para responder a una pregunta específica están disponibles. Por ejemplo, un marcador de béisbol debe incluir el tanteo de ambos equipos. Si se oye el tanteo "New York 6" y no oyes el del oponente, el anuncio ncio será incompleto y sin sentido. Los datos son inequívocos cuando el contexto es claro. Por ejemplo, el grupo de signos 2-xx puede parecer "la cantidad 2 menos la cantidad cantidad desconocida llamada x" para un estudiante de álgebra,, pero puede significar "2 barra x" a un vaquero que marca ganado. Tenemos que conocer el contexto de estos símbolos antes de poder conocer JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

2

E n P o s d e l a E x c e l e n c i a.

su significado. Otro ejemplo de la necesidad del contexto es el uso de términos especiales especial en diferentes campos especializados, tales como la contabilidad.. Los contables utilizan muchos términos de forma diferente al público en general, y una parte de un aprendizaje de contabilidad es aprender el lenguaje de contabilidad. Así los términos Debe y Haber pueden significar para un contable no más que "derecha" e "izquierda" en una contabilidad en T, pero pueden sugerir muchos tipos de ideas diferentes a los no contables. DATOS PERTINENTES. Decimos que tenemos datos pertinentes (relevantes) cuando pueden ser utilizados para responder a preguntas propuestas. Disponemos de un considerable número de hechos en nuestro entorno. Solo los hechos relacionados con las necesidades de información son pertinentes. Así la organización selecciona hechos entre sucesos y entidades particulares para satisfacer sus necesidades de información.

Datos Datos son los hechos que describen sucesos y entidades."Datos" entidades." " es una palabra en plural que se refiere a más de un hecho. A un hecho simple se le denomina "data-ítem" "data o elemento de dato. Los datos son comunicados por varios tipos de símbolos tales como las letras del alfabeto, números, movimientos de labios, puntos y rayas, señales con la mano, dibujos,, etc. Estos símbolos se pueden ordenar y reordenar de forma utilizable y se les denomina información. Los datos son símbolos que describen describen condiciones, hechos, situaciones o valores. Los datos se caracterizan por no contener ninguna información.. Un dato puede significar un número, una letra, un signo ortográfico o cualquier símbolo que represente una cantidad, una medida, una palabra o una descripción. La importancia de los datoss está en su capacidad de asociarse dentro de un contexto para convertirse en información. Por si mismos los datos no tienen capacidad de comunicar un significado y por tanto no pueden afectar el comportamiento de quien los recibe. Para ser útiles, los datos deben convertirse en información para ofrecer un significado, conocimiento,, ideas o conclusiones. Diferencia entre Datos e información 1. Los Datos a diferencia de la información son utilizados como diversos métodos para comprimir la información a fin de permitir una transmisión o almacenamiento más eficaces. 2. Aunque para el procesador de la computadora hace una distinción vital entre la información entre los programas y los datos, la memoria y muchas otras partes de la computadora no lo hace. Ambos son registradas temporalmente temporalmente según la instrucción que se le de. Es como un pedazo de papel no sabe ni le importa lo que JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

3

E n P o s d e l a E x c e l e n c i a.

se le escriba: un poema de amor, las cuentas del banco o instrucciones para un amigo. Es loo mismo que la memoria de la computadora. Sólo el procesador reconoce la diferencia entre datos e información de cualquier programa. programa Para la memoria de la computadora, computadora y también para los dispositivos de entrada y salida (E/S) y almacenamiento en disco, un programa es solamente más datos, más información que debe ser almacenada, movida o manipulada. manip 3. La cantidad de información de un mensaje puede ser entendida como el número de símbolos posibles que representan el mensaje."los símbolos que representan el mensaje no son más que datos significativos. 4. En su concepto más elemental, la información es un mensaje con un contenido determinado emitido por una persona hacia otra y, como tal, representa un papel primordial en el proceso de la comunicación, a la vez que posee una na evidente función social. A diferencia de los datos, la información tiene significado para quien la recibe, por eso, los seres humanos siempre han tenido la necesidad de cambiar entre sí información que luego transforman en acciones.. "La información es, entonces, conocimientos basados en los datos a los cuales, mediante un procesamiento, se les ha dado significado, propósito y utilidad" El Concepto de Procesamiento de Datos Hasta el momento hemos supuesto que los datos que maneja una aplicación no son tan voluminosos y por lo tanto caben en memoria.. Cuando recurrimos a archivos se debe a la necesidad de conservar datos después de que termina un programa, por ejemplo para apagar el computador. computador Sin embargo, existen problemas en donde el volumen de datos es tan grande que es imposible mantenerlos en memoria. Entonces, los datos se almacenan en un conjunto de archivos,, los que forman una base de datos. Una base de datos es por lo tanto un conjunto de archivos que almacenan, almacenan, por ejemplo, datos con respecto al negocio de una empresa. Cada archivo se forma en base a un conjunto de líneas y cada línea esta formada por campos de información. Todas las líneas de un mismo archivo tienen la misma estructura,, es decir los mismos campos de información. Diferentes archivos poseen estructuras distintas, i.e. campos de información. Recolección de datos: Provee un vínculo para obtener la información interoperacionables racional y las parametrizaciones. Almacenamiento de datos: Las unidades de disco de la computadora y otros medios de almacenamiento externo permiten almacenar los datos a más largo plazo, manteniéndolos disponibles pero separados del circuito principal hasta que el microprocesador los necesita. Una computadora dispone también de otros tipos de almacenamiento. La memoria de sólo lectura (ROM) es un medio permanente de almacenamiento de información básica, como las instrucciones de inicio y los procedimientos de entrada/salida. Asimismo, una computadora utiliza varios buffers (áreas reservadas de la memoria) como zonas de almacenamiento temporal de información específica, como JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

4

E n P o s d e l a E x c e l e n c i a.

por ejemplo los caracteres aracteres a enviar a la impresora o los caracteres leídos desde el teclado. Procesamiento de datos: a. El objetivo es graficar el Procesamiento de Datos, elaborando un Diagrama que permita identificar las Entradas, Archivos, Programas y Salidas de cada uno de los Procesos. b. Su antecedente es el Diagrama de Flujo. c. Los elementos claves son los Programas. d. Se confecciona el Diagrama de Procesamiento de Datos e. Este Diagrama no se podrá elaborar por completo completo desde un primer momento ya que depende del Flujo de Información. f. En este primer paso sólo se identifican las Salidas y Programas. Los elementos restantes se identifican en forma genérica. Validación de datos: Consiste en asegurar la veracidad e integridad integridad de los datos que ingresan a un archivo. Existen numerosas técnicas de validación tales como: Digito verificador, chequeo de tipo, chequeo de rango. 5. Concepto de Procesamiento Distribuido Distribu y Centralizado Procesamiento Centralizado: En la década de los años 50’s las computadoras eran máquinas del tamaño de todo un cuarto con las siguientes características: caracter • Un CPU • Pequeña cantidad de RAM • Dispositivos DC almacenamiento secundario (cintas) • Dispositivos d salida (perforadoras de tarjetas) • Dispositivos de entrada (lectores de tarjeta perforada) Con el paso del tiempo,, las computadoras fueron reduciendo su tamaño y creciendo en sofisticación, • Aunque la industria continuaba siendo dominada por las computadoras grandes "mainframes". A medida que la computación evolucionaba, las computadoras, fueron capaces de manejar aplicaciones múltiples simultáneamente, convirtiéndose en procesadores centrales "hosts" a los que se les Conectaban muchos periféricos y terminales tontas que consistían solamente de dispositivos de entrada/salida /salida (monitor ( y teclado)) y quizá poco espacio de almacenamiento, pero que no podían procesar por po sí mismas. 6. Estructura de Datos utilizados en el proceso electrónico de datos Arreglos Son una agrupación de datos homogéneos, es decir, con un mismo tipo de dato básico asociado. Se almacenan en forma contigua en la memoria y son referenciados con un nombre común y una posición relativa.

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

5

E n P o s d e l a E x c e l e n c i a.

Ejemplos: Arreglo Lineal al (1 dimensión ó vector) Vista gráfica [1] [2] [3] [4] [5] Definición de tipo Type Linea: Array [1..5] of TipoBasico; Var MiArreglo:Linea; Clasificación a.)Pila estática: Sin duda tendremos que utilizar arreglos o registros que como ya sabemos son la base para estructuras de datos más complejas. Considerando la siguiente figura: Vista gráfica

Suponiendo que Dato pertenece a un mismo tipo de datos y Cuenta Dato corresponde a un entero que se incrementa a medida que un nuevo elemento se incorpora a la pila. Intenta construir la definición de tipo para la estructura Pila. TYPE ______________________________ ______________________________ ______________________________ END; b.)Pila Dinámica: Sin duda tendremos que utilizar nodos con punteros. Considera la siguiente figura:

Suponiendo que los punteros que aparecen en la figura son capaces de apuntar a un nodo y que Dato pertenece a cualquiera de los tipos básicos o estructurados, estructura la definición de tipo sería:

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

6

E n P o s d e l a E x c e l e n c i a.

TYPE Puntero=^NodoPila; NodoPila=Record Info:AlgunTipo; sgte:Puntero; End; Var tope:Puntero;

TRATAMIENTO DE LA INFORMACION DE FORMA AUTOMATICA La informática es la disciplina que estudia el tratamiento automático de la información utilizando dispositivos electrónicos y sistemas computacionales. Informática es un vocablo proveniente del francés informatique, informatique acuñado por el ingeniero Philippe Dreyfus en 1962, acrónimo de las palabras information y automatique.. En lo que hoy conocemos como informática confluyen muchas de las técnicas y de las máquinas que el hombre ha desarrollado a lo largo de la historia para apoyar y potenciar sus capacidades de memoria, de pensamiento y de comunicación. La informática se utiliza utiliza en diversidad de tareas, por ejemplo: elaboración de documentos, control de procesos y robots industriales, telecomunicaciones y vigilancia, así como el desarrollo de juegos y multimedios. En la informática convergen los fundamentos de las ciencias de la computación, computación la programación y las metodologías para el desarrollo de software, software así como determinados temas de electrónica. Se entiende por informática a la unión sinérgica del cómputo y las comunicaciones. Estudia el tratamiento de la información de forma automática. Trata tanto los algoritmos de resolución de problemas, como el diseño y el manejo de ordenadores,, la estructura de los sistemas informáticos y los métodos de programación. DRAE: 1. De la informática o relacionado con esta forma de tratamiento de la información. - 2. Referido Referido a una persona, que se dedica a la investigación o al trabajo en la informática, especialmente si ésta es su profesión. La informática es, según el Diccionario de la Real Academia, Academia, el conjunto de conocimientos científicos y técnicas que hacen posible el tratamiento automático de la información por medio de ordenadores. La palabra INFORMÁTICA proviene del francés informatique, compuesto contracto de information automatique. 1. SISTEMAS DE INFORMACIÓN: Información: Todo aquello que es capaz de ser manejado por un sistema como entrada, programa o resultado. Los sistemas de inf. se clasifican en: Sistemas de Flujo de la Información: Aquellos en los que la información entrante es la misma que la saliente JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

7

E n P o s d e l a E x c e l e n c i a.

Sistemas de tratamiento de la Información: Aquellos en los que la información que entra es distinta a la que sale, sufre una manipulación. 1.2 Tratamiento de la Información: Es una serie ordenada de operaciones realizadas sobre la información: - La captación de la información: Recogida. - El registro de la información: Almacenamiento. - Ordenación: Clasificación bajo algún criterio. - Elaboración: Hacer algo con ella. - Utilización de la información: Obtener un resultado. Estas operaciones se pueden agrupar en cuatro grupos o tareas: - La comunicación: Se efectúa por los medios normales. - El almacenamiento - Tratamiento: Es necesario el estudio y operaciones que permitan elaborar los informes necesarios. - Distribución: Es importante tante hacer llegar la información a los puntos necesarios. Conceptos Básicos: - Recogida de datos: Búsqueda o toma de inf. - Flujo de información: Canales que permiten la circulación de la información de un punto a otro. - Proceso de datos: Cualquier tipo de operación que se hace con los datos - Clasificación: Ordenación de datos. - Iteración: Es el proceso o conjunto de procesos repetidos de un nº determinado de veces. 1.3. Tratamiento Automático de la Información: La elaboración de la información se realiza za sobre tres funciones básicas: -Entrada de datos El tratamiento y elaboración(proceso) -El -Emisión Emisión de informes y resultados. Los ordenadores para poder realizar todas las funciones deben de poder: - Memorizar: Retener los datos confeccionados por el usuario usuari

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

8

E n P o s d e l a E x c e l e n c i a.

- Discriminar y distribuir: Diferenciar los datos de programas - Manipulación: El ordenador interpreta las operaciones aritméticas y lógicas que se realizan con los datos. Definición de Informática: El conjunto de conocimientos y técnicas que hacen posible posib el tratamiento automático de la información por medio de ordenadores Definición de Ordenador: Es una máquina capaz de aceptar datos de entrada y efectuar con ellos operaciones lógicas y aritméticas y proporcionar la información resultante a través de un medio de salida. Estructura básica de un ordenador: - Unidades de E/S -Unidad Unidad central de Procesos (CPU): -Memoria Memoria Central (memorizar) (M.C) -Unidad Unidad de Control (discriminación y distribución) (U.C) -Unidad Unidad Aritmético lógica (manipulación) (U.A.L.) 1. REPRESENTACIÓN SENTACIÓN INTERNA DE LA INFORMACIÓN: 1.1 Sistemas de numeración: Es el conjunto de símbolos y de reglas que utilizamos para representar cantidades; en un sistema de numeración existe un elemento q se denomina base,, es el nº de símbolos distintos que utilizamos utilizamos para representar una cantidad. Se dice que es posicional cuando el valor de cada dígito depende de la posición que ocupa en la representación, es relativo a una base cuando el valor que representa cada dígito se obtiene multiplicando por la potencia de de la base. 1. S.N.Decimal: Utiliza 10 símbolos, es posicional y relativo a una base 2. S.N.Binario: Utiliza 2 símbolos (0,1) es posicional y relativo a una base 3. S.N.Octal: Utiliza 8 símbolos (0...7) es posicional y relativo a una base. 1dig=3dig bina 4. S.N.Hexadecimal: Utiliza 16 símbolos ( 0...9,A...F) es posicional y relativo a una base. 1digHexa=4díg 1.2. Sistemas de codificación de datos: Una información para poder ser tratada de forma automática necesita ser transformada a un código manejable por el e ordenador. La información tratada por un ordenador se presenta en un determinado sistema de representación que utiliza un alfabeto que llamaremos de entrada y por medio de un sistema de codificación la transformaremos en una información codificada que utiliza ut su correspondiente alfabeto de salida y que será reconocible y tratada por el ordenador.

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

9

E n P o s d e l a E x c e l e n c i a.

1.2.1. Códigos Numéricos 1. Código en binario puro: Un ordenador maneja datos en binario con una limitación de longitud referida al nº de bits y además necesita considerar el signo para operar con nº negativos, el nº de dígitos disponibles vendrá determinado por N siendo N=8,16,32...Las representaciones más habituales: - Módulo y signo:: El bit situado más a la izquierda es el signo (0=positivo, 1=negativo), el resto de los bits representa el módulo del nº. El Rango de Representación son aquellos nº q se pueden codificar: 2^N-1 2^N +1<X<2 -1 - Complemento a uno C-1: Para los nº positivos igual que en M.S. y el negativo de un nº se obtiene complementando todos los dígitos, dígitos, se cambian los 0 por 1 y viceversa. (0+ y 1-). C 1 y la representación de - Complemento a dos C-2: El positivo es igual que en M.S. y C-1 negativos lo obtenemos : Ponemos el nº en positivo, lo C-1 C 1 y al resultado del C-1 C le sumamos 1. - Los códigos en exceso eso a 2^N-1: 2^N Para representar un nº en exceso a 128, hay q sumarle a dicho nº el nº que queramos representar y representarlo en la longitud que nos digan. - Uso del C-1 y C-2 : Un desbordamiento es cuando teniendo dos nº con el mismo signo sale otro signo diferente, si sale en la suma .Un acarreo es que sobra un nº pero lo q hacemos es sumárselo al resultado, si se produce en la suma en C-1 C 1 se le vuelve a sumar 1 al nº que hayamos sacado, pero si se produce en C-2 C 2 se desprecia. 2. Decimal Codificado en Binario Bina (BCD): El BCD utiliza un cuarteto para la representación de cada cifra decimal, existen varias versiones de este código: (mirar suma en BCD) - El BCD natural: Cada cifra decimal se codifica por 4 dígitos binarios. - - El BCD en exceso a 3: Deja tres codificaciones codificaciones al principio y al final sin representación. Se le suma a cada nº 3. Hay dos formas de representar: - El decimal desempaquetado: Cada dígito decimal se representa en dos cuartetos, donde el primer cuarteto es todo lleno de 1 y el segundo es la cifra. El signo de este nº se escribe en el último cuarteto en el lugar de los 1. El sino + es 1100, - es 1101. Ej.1992 1111/0001 1111/1001 1111/1001 1100/0010 1 9 9 + 2.

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

10

E n P o s d e l a E x c e l e n c i a.

CLACIFICACIONES GENERALES DE LOS DATOS Como su nombre lo indica, los datos compartibles compartibles son aquellos cuya naturaleza los hace suceptibles de ser `compartidos` con mas de un host, un ejemplo de est e tipo de datos son los `home` de los usuarios. En todo sistema existen datos que solo tienen relacion con el `host` que los alberga, fuera de este, pierden toda utilidad (o por lo menos pierden su utilid ad oficial :-), : un ejemplo de este tipo de datos son los descriptores de disposi tivos o los `lock files` que crean algunos programas en ejecución. Son datos que varian sin necesitar de la intervencion del administrador de sist emas (root), los documentos, como este, son ejemplos de este tipo de datos Son datos que solo pueden variar bajo la intervención del administrador de sistemas, por ejemplo, las librerias, los programas instalados, etc. et Los datos se clasifican en cualitativos y cuantitativos. Cualitativos: Cuando la observación de la variable se hace sobre una cualidad no numérica, como por ejemplo el sexo, el estado civil, las enfermedades, lugar de nacimiento. Cuantitativos: Cuando la observación que se hace de la variable puede ser expresada en términos numéricos, como la edad, el peso, la talla, el número de hijos. Las variables cuantitativas a su vez se pueden clasificar en continuas o discontinuas. Continuas: Cuando el dato se puede puede expresar tanto en valor entero como en decimales, como por ejemplo la talla, el peso, la edad. Discontinuas o discretas: Cuando los datos solo admiten ser expresados en valores enteros, ejemplo el número de pacientes atendidos en un servicio.

Una estructura uctura de datos es una clase de datos que se puede caracterizar por su organización y operaciones definidas sobre ella. Algunas veces a estas estructuras se les llama tipos de datos.

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

11

E n P o s d e l a E x c e l e n c i a.

En ellas encontramos las siguientes: ESTRUCTURAS LÓGICAS DE DATOS: En un programa, cada variable pertenece a alguna estructura de datos explícita o implícitamente definida, la cual determina el conjunto de operaciones validas para ella. Las estructuras de datos que se discuten aquí son estructuras de datos lógicas. Cada estructura structura de datos lógica puede tener varias representaciones físicas diferentes para sus almacenamientos posibles. ESTRUCTURAS PRIMITIVAS Y SIMPLES: Son primitivas aquellas que no están compuestas por otras estructuras de datos por ejemplo, enteros, booleanos leanos y caracteres. Otras estructuras de datos se pueden construir de una o mas primitivas. Las estructuras de datos simples que consideramos se construyen a partir de estructuras primitivas y son: cadenas, arreglos y registros. A estas estructuras de datos os las respaldan muchos lenguajes de programación. ESTRUCTURAS LINEALES Y NO LINEALES: Las estructuras de datos simples se pueden combinar de varias maneras para formar estructuras mas complejas. Las dos cases principales de estructuras de datos son las lineales y las no lineales, dependiendo de la complejidad de las relaciones lógicas que representan. Las estructuras de datos lineales incluyen pilas, colas y listas ligadas lineales. Las estructuras de datos no lineales incluyen grafos y árboles. 3.1 Datos compartibles]] ===== Como su nombre lo indica, los datos compartibles son aquellos cuya naturaleza los hace suceptibles de ser `compartidos` con mas de un host, un ejemplo de est e tipo de datos son los `home` de los usuarios. ===== [[ 3.2 Datos no compartibles]] ===== En todo sistema existen datos que solo tienen relacion con el `host` que los alberga, fuera de este, pierden toda utilidad (o por lo menos pierden su utilid ad oficial :-), : un ejemplo de este tipo de datos son los los descriptores de disposi tivos o los `lock files` que crean algunos programas en ejecución.

===== [[ 3.3 Datos variables o dinámicos]] ===== Son datos que varian sin necesitar de la intervencion del administrador de sist emas (root), los documentos, como este, son ejemplos de este tipo de datos ===== [[ 3.4 Datos estáticos]] =====

JEUSUS FUENTE DE SABIDURIA Y DE LA INTELIGENCIA

12