• Author / Uploaded
• Victor Mendoza

Citation preview

ACTIVIDAD 5, SELECCIÓN DE LINEAL O NO LINEAL

REALIZADO POR: VICTOR ALFONSO MENDOZA MENDOZA

CORPORACION UNIVERSITARIA IBEROAMERICANA FACULTAD DE INGENIERIA INGENIERIA DE SOFTWARE

INTRODUCCION Las estructuras de datos simples se pueden combinar de varias maneras para formar estructuras más complejas. Las dos clases principales de estructuras de datos complejas 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. Lista lineal: Es una estructura de datos formada por un conjunto de elementos ordenados; el número de elementos en la lista puede variar. Se puede borrar un elemento o insertar en cualquier posición de la lista. Así la lista puede crecer o decrecer al transcurrir el tiempo. A continuación se mostraran mediante un cuadro comparativo los criterios de selección, los métodos aplicables y las propiedades que proveen al momento de adicionarlos al algoritmo de las pilas, colas, árboles y grafos en donde se comparan todas estas situaciones en el cuadro.

PILA

COLA

ESTRUCTURAS DE DATOS LINEALES Y NO LINEALES METODOS APLICABLES CRITERIO DE SELECCIÓN Una pila (stack) es un caso especial de una lista lineal en el cual, la Una de las estructuras lineales de datos mas comunes es la pila. Las inserción y supresión son operaciones que solo pueden ocurrir en un operaciones que definen una estructura de datos de tipo pila se extremo de la pila, el cual se denomina como tope de la pila. Si se presentan para dar paso a la declaración y manipulación de pilas. meten varios elementos en la pila y después se sacan de esta, el ultimo elemento en entrar será el primero en salir. (LIFO: last in first out).

PROPIEDADES el numero de elementos en la lista puede variar. Se puede borrar un elemento o insertar en cualquier posición de la lista. Asi la lista puede crecer o decrecer al transcurrir el tiempo.

Es otro caso especial de la estructura de datos de lista lineal. Mientras que en las pilas se restringe la adicion y supresión de elementos a través de un solo extremo, llamado tope de la lista, a las colas se les restringe a que los elementos se supriman por el frente y se agreguen por atrás.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

En una cola la inserción se hace estrictamente por un extremo de la lista, al cual podemos llamar fondo; la supresión solo puede hacerse por el otro extremo de la lista, al cual llamamos frente. 1. Crear (cola) 2. Está-vacía(cola) 3. Insertar(elemento, cola) 4. Eliminar(cola)

Un árbol es un grafo conexo, simple y aciclico. Un árbol no contiene ni ciclos ni bucles; existe una sola arista entre cualquier par de nodos. Un árbol se dice que esta enraizado si tiene un nodo (llamado raíz), el cual se distingue de los demás nodos. La raíz del árbol T es denotada por raíz (T).

Son fáciles de construir, interpretar y visualizar Si faltan datos no podremos recorrer el árbol hasta un nodo terminal, pero sí podemos hacer predicciones promediando las hojas del subárbol que alcancemos. Sirven tanto para variables dependientes cualitativas como cuantitativas, como para variables predictoras o independientes numéricas y categóricas. Además, no necesita variables dummys, aunque a veces mejoran el modelo.

Hay un nodo especialmente designado llamado Raiz 2. Los nodos restantes son particionados en >= 0 conjuntos disjuntos, llamados T1, T2, …, TM tales que, cada Ti es por si mismo un árbol. Estos conjuntos son llamados subarboles de la Raiz. Un árbol sin nodos es un árbol nulo. La raíz de un árbol no esta simplemente seleccionaa de manera aleatoria; mas bien es un nodo que se distingue por la propiedad de:

ARBOLES

Grado interno (v) = 0 para v = Raiz(T)

GRAFO

En el grafo dirigido se les asigna dirección a las aristas de la grafica. Cada arista del grafo dirigido incluye una flecha para indicar la dirección. El grado interno de un nodo en un grafo es el numero de aristas que terminan en ese nodo; el grado externo de un nodo, es el numero de aristas que salen de ese nodo. El grado de un nodo es la suma de sus grados internos y externos.

En estas estructuras cada elemento puede tener varios elementos “siguientes”, lo cual introduce el concepto de estructuras de ramificación. Estas estructuras de datos de ramificación son llamadas grafos y arboles.

Un grafo es un conjunto de puntos y un conjunto de líneas, con cada línea se une un punto a otro. Los puntos se llaman los nodos del grafo, y las líneas se llaman aristas. Un grafo nulo

es

un

grafo

con

orden

cero.

Una arista esta determinada por los nodos que conecta. Un grafo esta completamente definido por sus conjuntos de nodos y aristas. La posición real de estos elementos en la pagina no tiene importancia.

BIBLIOGRAFIA Cedano Olvera, M.A. y Rubio Gonzalez, J . A. (2015). Fundamentos de computación para ingenieros. Grupo Editorial Patria.