tag:blogger.com,1999:blog-36005110672735203252024-03-19T14:41:55.325-07:00Programacion C++ y JavaUnknownnoreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3600511067273520325.post-338585522079557702009-12-02T20:20:00.000-08:002009-12-02T20:47:45.243-08:00Estructura de Datos I<div class="MsoNormal"> <span style="color: white;"><span style="font-size: x-large;">Contenido</span></span><span lang="ES-TRAD" style="font-family: Arial, sans-serif;"><span style="color: white;"><o:p></o:p></span></span> </div> <div class="MsoNormal"> </div> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Introducción</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Tipos de Datos Abstractos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul type="disc"> <li class="MsoNormal"><span style="color: white;">Tipos de Datos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Tipos de Datos Abstractos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Recursividad</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Análisisi de la Performance de Algoritmos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">TAD Lista</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul style="margin-top: 0cm;" type="disc"> <li class="MsoNormal"><span style="color: white;"><a href="http://codigodeprogramacion.blogspot.com/2009/11/listas-secuenciales.html">Listas Secuenciales</a></span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;"><a href="http://codigodeprogramacion.blogspot.com/2009/12/listas-encadenadas.html">Listas Encadenadas</a></span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;"><a href="http://codigodeprogramacion.blogspot.com/2009/09/listas-simplemente-encadenada.html">Listas Simplemente Encadenadas</a></span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Implementación (Estática)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Implementación (Dinámica)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;"><a href="http://codigodeprogramacion.blogspot.com/2009/12/listas-doblemente-encadenada.html">Listas Doblemente Encadenadas</a></span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Implementación (Dinámica)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;"><a href="http://codigodeprogramacion.blogspot.com/2009/12/listas-circulares.html">Listas Circulares</a></span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Implementación (Dinámica)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> <li class="MsoNormal"><span style="color: white;">Pilas y Colas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Pilas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Implementación (Estática)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Implementación (Dinámica)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Colas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Implementación (Estática)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Implementación (Dinámica)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> <li class="MsoNormal"><span style="color: white;">Listas Generalizadas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Algoritmos Recursivos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Matrices</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul style="margin-top: 0cm;" type="disc"> <li class="MsoNormal"><span style="color: white;">Matrices Esparcidas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Representación por líneas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Representación utilizando conjunto de listas encadenadas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> <a href="http://www.blogger.com/goog_1259814019902"> </a></span><span style="color: white;"><a href="http://codigodeprogramacion.blogspot.com/2009/10/tabla-hash-en-c.html">Hashing</a></span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul style="margin-top: 0cm;" type="disc"> <li class="MsoNormal"><span style="color: white;">Funciones Hash</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Método de la División</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Hashing Universal</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Colisiones</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Encadenamiento Separado (Separate Chaining)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Direccionamiento Abierto (Open Addressing)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Distribución lineal</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Distribución cuadrática</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Distribución doble</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Ordenamiento</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul style="margin-top: 0cm;" type="disc"> <li class="MsoNormal"><span style="color: white;"> 47"></span><span style="color: white;"><a href="file:///D:/Mis%20documentos/datos/Ordenacao/node45.htm"></a></span><span style="color: white;">BubbleSort</span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">implementación</span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Método de inserción directa</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Shell (Classificación de Incremento Decreciente)</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">HeapSort</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="square"> <li class="MsoNormal"><span style="color: white;">Teorema Master</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> <li class="MsoNormal"><span style="color: white;">MergeSort</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">QuickSort</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">implementación</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">BucketSort</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Arboles</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Arboles Binarios</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Representación de Árboles Binarios</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Representación Implicita</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Representación Encadenada</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Recorrido de árboles binarios</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Representación de Árboles a través de Árboles Binarios</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Arbol de Búsqueda Binaria</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Inserción en árboles de búsqueda binaria</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Eliminación en árboles de búsqueda binaria</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Árboles AVL</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Algoritmo de Inserción en un árbol AVL</span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;"><a href="file:///D:/Mis%20documentos/datos/AVL/insercao.html"></a></span><span style="color: white;">Implementación de las Rotaciones</span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Algoritmo de Inserción</span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;"><a href="file:///D:/Mis%20documentos/datos/AVL/insercao.html"></a></span><span style="color: white;">Algoritmo de Eliminación en árbol AVL </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Árboles-B</span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Búsqueda en un árbol-B</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Inserción en un árbol-B</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Eliminación en árbol-B</span><span style="color: white;"><o:p></o:p></span></li> </ul> </ul> <ul style="margin-top: 0cm;" type="disc"> <li class="MsoNormal"><span style="color: white;"> 75"></span><span style="color: white;"><a href="file:///D:/Mis%20documentos/datos/Grafos/node73.html"></a></span><span style="color: white;">Quad-Tree</span><span style="color: white;"><o:p></o:p></span></li> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> Grafos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span> </div> <ul style="margin-top: 0cm;" type="disc"> <li class="MsoNormal"><span style="color: white;">Representación de Grafos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Matriz de Adyacencia</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Listas de adyacencia</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Multilistas</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Búsqueda en Grafos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Búsqueda en Profundidade</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Búsqueda en anchura</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Árbol generador mínimo</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Camino de costo Mínimo</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <ul style="margin-top: 0cm;" type="circle"> <li class="MsoNormal"><span style="color: white;">Camino más Corto</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Algoritmo de Dijkstra</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <li class="MsoNormal"><span style="color: white;">Ordenación Topológica</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> <li class="MsoNormal"><span style="color: white;">Coloración en Grafos</span><span style="color: white;"> </span><span style="color: white;"><o:p></o:p></span></li> </ul> <div class="MsoNormal"> <span lang="ES-TRAD" style="font-family: Symbol;"><span style="color: white;">•</span></span><span style="color: white;"> </span><span style="color: white;">Bibliografia</span> <o:p></o:p> </div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-80366019782030604292009-12-02T19:49:00.000-08:002009-12-02T19:49:44.164-08:00Listas EncadenadasEn listas encadenadas, los elementos consecutivos en la lista no significa que los mismos esten consecutivamente representados (el orden es lógico)<br />
En la implementación es necesario almacenar separadamente la información de un elemento de la lista, normalmente el primero.<br />
Existen dos formas representar listas encadenadas, a través de array, denominadas listas estáticas, o por punteros llamadas listas dinámincas.<br />
<img alt="Listas Encadenadas " src=" http://img222.imageshack.us/img222/6517/61507878.jpg" /><br />
Las principales ventajas de las listas encadenadas son:<br />
1. Elimina el problema de los traslados de nodos<br />
2. En el caso de listas dinámicas no se requiere saber previamente el número de elementos a ser almacenados. <br />
Las principales desventajas son: <br />
1. No se consigue (de manera directa) accesar a los elementos de la lista en tiempo constante.<br />
2. Mayor número de operaciones para mantener la integridad de los datos.<br />
Las listas encadenadas puede ser divididas en:<br />
<omg alt="Listas Encadenadas " src=" "></omg><br />
<ul><li><a href="http://codigodeprogramacion.blogspot.com/2009/09/listas-simplemente-encadenada.html">Únicamente o simplemente encadenadas </a></li>
<li><a href="http://codigodeprogramacion.blogspot.com/2009/12/listas-doblemente-encadenada.html">Doblemente encadenadas</a> </li>
<li><a href="http://codigodeprogramacion.blogspot.com/2009/12/listas-circulares.html">Circulares </a></li>
</ul><omg alt="Listas Encadenadas " src=" "> En el caso de listas no circulares, las operaciones de inserción y eliminación deben considerar algunos o casos especiales, que son las inserciones y eliminaciones al comienzo y final de las listas.<br />
La inserción del primer elemento en la lista (convirtiéndola en no vacía) y la eliminación del último elemento (convirtiéndoloa en vacía) deben ser considerados como casos especiales para todos los tipos de lista.<br />
<br />
</omg>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-3690944108737001612009-12-02T19:27:00.000-08:002009-12-02T19:30:56.920-08:00Listas Doblemente EncadenadaEn una lista doblemente encadenada, cada elemento posee las informaciones de quien es su sucesor y su antecesor.<br />
<img alt="Listas Doblemente Encadenada " src="http://img37.imageshack.us/img37/2029/47721956.jpg" /><br />
Principales ventajas:<br />
1. Permite caminar en las dos direcciones de la lista.<br />
2. Inserción y eliminación de elementos son realizados con más facilidad.<br />
<br />
Principales problemas:<br />
• Mayor espacio reservado<br />
• Manipulación de un puntero extra
Implementación (Dinámica)<br />
<br />
Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada. (Fig 4.2)La operación de inserción de un nuevo elemento en la posición anterior al elemento actual puede ser descrito como sigue (suponiendo que actual no es el primer elemento de la lista):
<img alt="Listas Doblemente Encadenada " src="http://www.utpl.edu.ec/ecc/wiki/images/1/12/Listas_Doblemente_Enlazadas.JPG" /><br />
<span style="font-family: 'Courier New', Courier, monospace;">nuevo-&gt;proximo = actual; </span><br />
<span style="font-family: 'Courier New', Courier, monospace;">nuevo-&gt;anterior = actual-&gt;anterior; </span><br />
<span style="font-family: 'Courier New', Courier, monospace;">actual-&gt;anterior-&gt;proximo = nuevo; </span><br />
<span style="font-family: 'Courier New', Courier, monospace;">actual-&gt;anterior = nuevo; </span><br />
Note que en este caso no es necesario un elemento posterior.
Especificación: Igual a la del ejemplo estático para listas simplemente encadenadas<br />
<b>Observación:</b> En el ejemplo abajo todavía estamos utilizando un puntero auxiliar llamdo "ant", como ejercicio, realice una nueva implementación de la función inserta_elemento sin utilizar este puntero auxiliar.<br />
<a href="http://www.box.net/shared/c0bs6tz22k" target="blank"><img alt="Descarga" src="http://s1.animeid.com/imagenes/descargar.gif" width="100" /></a><br />
<br />
<a href="http://www.box.net/shared/c0bs6tz22k" target="blank"></a><b>
Código:</b><br />
<textarea cols="70" rows="30" style="background-color: white; color: #2e2efe;" wrap="soft">
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
typedef struct lista LE;
typedef struct nodo_lista NO;
struct nodo_lista{
int elem;
NO *prox; // guarda la pos. del próx. elem. en la lista
NO *ante; // guarda la pos.del elem. ant. en la lista */
};
struct lista
{
NO *head ; // guarda la dir. de primer elem. de lista
};
LE *Inicia_Lista(void)
{
LE *temp;
if ((temp = (LE *) malloc(sizeof(LE))) != NULL)
{
temp->head = NULL;
return(temp);
}
else
exit(0);
}
void Inserta_Elemento(LE *L, int A){
NO *aux,*ant,*atu;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
aux->elem = A;
if (L->head == NULL)//lista ESTA VACIA
{ aux->prox = NULL;
aux->ante = NULL;
L->head = aux;
}
else{
atu = L->head;
ant = NULL;
while ((atu != NULL) && (atu->elem <= A))
{
ant = atu;
atu = atu->prox;
}
if (ant == NULL) // insert en primera pos. de lista
{
aux->prox = L->head;
aux->ante = NULL;
L->head->ante = aux;
L->head = aux;
}
else
{
aux->prox = ant->prox;
aux->ante = ant;
if (ant->prox != NULL)
ant->prox->ante = aux;
ant->prox = aux;
}
}
}
else
exit(0);
return;
}
int Eliminar_Elemento(LE *L, int A){
NO *ant,*act;
if ((ant = (NO *) malloc(sizeof(NO))) != NULL)
{if(L->head==NULL)
return -1;
else
{ act=L->head;
if(act->elem==A)
{if(act->prox==NULL)
L->head=NULL;
else{
L->head=act->prox;
act->prox->ante=NULL;
}return 1;
}
while(act!=NULL)
{
if(act->elem==A)
{
if(act->prox==NULL)
{ant->prox=NULL;
act->prox=NULL;
act->ante=NULL;
}
else{
ant->prox=act->prox;
act->prox->ante=ant;
act->prox=NULL;
act->ante=NULL;
}
return 1;
}
else {
ant=act;
act=act->prox;
}
}
return -1;
}
}
}
void Imprime_Lista(LE *L){
NO *aux,*atu;
int tam=0;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
atu = L->head;
while (atu != NULL)
{
tam++;
cout<<atu->elem<<" ";
atu = atu->prox;
}
cout<<" de tama\xa4o "<<tam;
}
}
main()
{
int aux_l;
LE *l;
int x;
char opc;
l = (LE *) Inicia_Lista();
while (1)
{
cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) ";
cin>>opc;
if (opc == 'i')
{
cout<<"\n Ingrese el nuevo elemento entero ";
cin>>x;
Inserta_Elemento(l,x);
}
if (opc == 'e')
{
cout<<"\n Ingrese el numero entero a buscar ";
cin>>x;
aux_l = Eliminar_Elemento(l,x);
if (aux_l == -1)
cout<<"Numero no encontrado\n";
}
if (opc == 'p')
Imprime_Lista(l);
if (opc == 's')
{
//l = (LE *) Vacia_Lista(l);
exit(0);
}
}
}
</textarea>
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-48561964547293325472009-12-01T04:29:00.000-08:002009-12-01T05:11:36.626-08:00Listas CircularesUna lista circular puede ser simple o doblemente encadenada. Lo que caracteriza a las listas circulares es el hecho que el sucesor del último elemento es el primer elemento de la lista.
En el caso de una lista doblemente encadenada, el predecesor del primer elemento es el último elemento de la lista.<br />
<img alt="Listas Circulares " src="http://img513.imageshack.us/img513/5669/49609392.jpg" /><br />
La principal ventaja de las listas circulares es que no necesitamos considerar casos especiales de inserción y eliminación de elemento (primero y último).<br />
<br />
<b> Implementación (Dinámica)</b><br />
<br />
<i>Listas Circulares simplemente enlazada
</i><br />
<a href="http://www.box.net/shared/2nui7qdrdq" target="blank"><img alt="Descarga" src="http://s1.animeid.com/imagenes/descargar.gif" width="100" /></a><br />
<span style="font-family: 'Courier New', Courier, monospace;"><b>Código</b></span><br />
<textarea cols="70" rows="30" style="background-color: #FFFF00; color: #0000FF;" wrap="soft">#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
typedef struct lista LE;
typedef struct nodo_lista NO;
struct nodo_lista
{
int elem;
NO *prox; /* guarda la posicion del proximo elemento en la lista */
};
struct lista
{
NO *head ; /* guarda la dirección del primer elemento de la lista */
};
LE *Inicia_Lista(void)
{
LE *temp;
if ((temp = (LE *) malloc(sizeof(LE))) != NULL)
{
temp->head = NULL;
return(temp);
}
else
exit(0);
}
void Inserta_Elemento(LE *L, int A)
{
NO *aux,*ant,*atu;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
aux->elem = A;
if (L->head == NULL)
{ aux->prox = aux;
L->head = aux;
}
else
{ /* Inserta en la pos. anterior de head */
aux->prox = L->head->prox;
L->head->prox = aux;
}
}
else
exit(0);
return;
}
int Eliminar_Elemento(LE *L,int A){
NO *ant,*act;
if ((ant = (NO *) malloc(sizeof(NO))) != NULL)
{
if(L->head == NULL){
return -1;
}
else
{ act=L->head;
ant=NULL;
do
{ant=act;
act=act->prox;
}while(act->elem!=A&&act!=L->head);
if(act->elem==A)
{ ant->prox=act->prox;
act->prox=NULL;
if(act==L->head)
{L->head=ant;
if(act==ant)
L->head=NULL;
}
return 1;
}
else
return -1;
}
}
}
void Imprime_Lista(LE *L){
NO *aux,*atu;
int tam=0;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
atu = L->head;
do
{ if(L->head!=NULL)
{tam++;
cout<<atu->elem<<" ";
atu = atu->prox;
}
}while (atu != L->head);
if(tam)cout<<" de tama\xa4o "<<tam;
else cout<<"Lista vacia";
}
}
/* Ejercicios: Implementar las funciones que faltan */
main()
{
int aux_l;
LE *l;
int x=0;
char opc;
l = (LE *) Inicia_Lista();
while (1)
{
cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) ";
cin>>opc;
if (opc == 'i')
{
cout<<"\n Ingrese el nuevo elemento entero ";
cin>>x;
Inserta_Elemento(l,x);
}
if (opc == 'e')
{
cout<<"\n Ingrese el número entero a buscar ";
cin>>x;
aux_l = Eliminar_Elemento(l,x);
if (aux_l == -1)
cout<<"Numero no encontrado\n";
}
if (opc == 'p')
Imprime_Lista(l);
if (opc == 's')
{
//l = (LE *) Vacia_Lista(l);
exit(0);
}
}
}
</textarea>
<br />
<br />
<i>Listas Circulares doblemente enlazada
</i><br />
<a href="http://www.box.net/shared/t01pf7yozf" target="blank"><img alt="Descarga" src="http://s1.animeid.com/imagenes/descargar.gif" width="100" /></a><br />
<span style="font-family: 'Courier New', Courier, monospace;"><b>Código</b></span><br />
<textarea cols="70" rows="30" style="background-color: white; color: #0000FF;" wrap="soft">#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
typedef struct lista LE;
typedef struct nodo_lista NO;
struct nodo_lista
{
int elem;
NO *prox,*ante; /* guarda la posicion del proximo elemento en la lista */
};
struct lista
{
NO *head ; /* guarda la dirección del primer elemento de la lista */
};
LE *Inicia_Lista(void)
{
LE *temp;
if ((temp = (LE *) malloc(sizeof(LE))) != NULL)
{
temp->head = NULL;
return(temp);
}
else
exit(0);
}
void Inserta_Elemento(LE *L, int A)
{
NO *aux,*ant,*atu;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
aux->elem = A;
if (L->head == NULL)
{ aux->prox = aux;
aux->ante=aux;
L->head = aux;
}
else
{ /* Inserta en la pos. anterior de head */
aux->prox = L->head->prox;
L->head->prox = aux;
aux->ante=L->head;
L->head->prox->ante = aux;
}
}
else
exit(0);
return;
}
int Eliminar_Elemento(LE *L,int A){
NO *ant,*act;
if ((ant = (NO *) malloc(sizeof(NO))) != NULL)
{
if(L->head == NULL){
return -1;
}
else
{ act=L->head;
ant=NULL;
do
{ant=act;
act=act->prox;
}while(act->elem!=A&&act!=L->head);
if(act->elem==A)
{ ant->prox=act->prox;
act->prox->ante=ant;
act->prox=NULL;
act->ante=NULL;
if(act==L->head)
{L->head=ant;
if(ant==act)
L->head=NULL;
}
return 1;
}
else
return -1;
}
}
}
void Imprime_Lista(LE *L){
NO *aux,*atu;
int tam=0;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
atu = L->head;
do
{ if(L->head!=NULL)
{tam++;
cout<<atu->elem<<" ";
atu = atu->prox;
}
}while (atu != L->head);
if(tam)cout<<" de tama\xa4o "<<tam;
else cout<<"Lista vacia";
}
}
/* Ejercicios: Implementar las funciones que faltan */
main()
{
int aux_l;
LE *l;
int x=0;
char opc;
l = (LE *) Inicia_Lista();
while (1)
{
cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Sair (s) ";
cin>>opc;
if (opc == 'i')
{
cout<<"\n Ingrese el nuevo elemento entero ";
cin>>x;
Inserta_Elemento(l,x);
}
if (opc == 'e')
{
cout<<"\n Ingrese el número entero a buscar ";
cin>>x;
aux_l = Eliminar_Elemento(l,x);
if (aux_l == -1)
cout<<"Numero no encontrado\n";
}
if (opc == 'p')
Imprime_Lista(l);
if (opc == 's')
{
//l = (LE *) Vacia_Lista(l);
exit(0);
}
}
}
</textarea><br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-24544144821804610572009-11-30T11:32:00.000-08:002009-11-30T11:36:43.013-08:00Listas Secuenciales<div class="separator" style="clear: both; text-align: left;">En una lista secuencial, el sucesor de un elemento ocupa la posición física subsecuente de este elemento. Una de las formas más comunes de implementar una lista secuencial es utilizando ARRAY. En un array asociamos a cada elemento un índice (lo denominamos elemento <i>a(i)</i>). De esta forma, estamos almacenando el elemento <i><b><span style="font-size: small;">a(i)</span></b></i> e <i><b><span style="font-size: small;">a</span></b></i><i><b><span style="font-size: small;">(i+1)</span></b> </i>en las posiciones consecutivas<i><span style="font-size: small;"> </span><b><span style="font-size: small;">i</span></b></i><span style="font-size: small;"> </span>e <i><b><span style="font-size: small;">i+1</span></b></i><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="http://img81.imageshack.us/img81/6971/ls1t.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Listas Secuenciales " border="0" src="http://img81.imageshack.us/img81/6971/ls1t.jpg" /></a><br />
</div>Las principales ventajas de utilizar un array son:<br />
<ol><li>Rápido acesso a los elementos.</li>
<li>Facilidad en modificar información.</li>
</ol>Los elementos del array pueden ser accesados en tiempo constante, por ejemplo en C el elemento que está en la posición i de un array a pode ser recuperado utilizando <i>a[i]</i>. Las principales desventajas son:<br />
<ol><li>Definición previa del tamaño de un array.</li>
<li>Dificultad para insertar (y eliminar) un elemento entre dos otros ya existentes.</li>
</ol>En la definición de un array necesitamos especificar el número máximo de elementos que serán almacenados. <br />
<br />
Suponga que querramos inserir un nuevo elemento x en una posición i ya ocupada de un vector <br />
Para realizar esta tarea tendremos que mover los elementos <i><b><span style="font-size: small;">a</span></b></i><i><b><span style="font-size: small;">(i+1), </span><span style="font-style: normal; font-weight: normal;"><i><b><span style="font-size: small;">a</span></b></i><i><b><span style="font-size: small;">(i+2)...a(k)</span> </b></i></span></b></i> para las posiciones <span style="font-style: italic; font-weight: bold;"><span style="font-size: small;">i+1, i+2, i+3...,i+k+1</span></span> respectivamente. Note que en el peor de los casos (insertar en la primera posición) esta operación lleva un tiempo de <i>O(n). </i><br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://img188.imageshack.us/img188/636/ls2hw.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Listas Secuenciales " border="0" src="http://img188.imageshack.us/img188/636/ls2hw.jpg" /></a><br />
</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-16077252331284102492009-10-07T06:43:00.000-07:002009-10-07T07:01:57.301-07:00Tabla Hash en c++"Hashing" es una técnica que busca realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante. Esa característica es muy importante cuando se traba con almacenamiento secundario en disco, donde el acceso a una determinada dirección es bastante lenta. Algunas aplicaciones que son beneficiadas por el uso de tablas hash son diccionarios y tablas de palabras reservadas de un compilador.<br />
En vez de organizar la tabla según el valor relativo de cada llave en relación a las demás, la tabla hash toma encuenta solamente su valor absoluto, interpretado como un valor numérico.<br />
<br />
<div><br />
</div><img alt="tabla hash en c++" src="http://img16.imageshack.us/img16/5219/tablahash.png" /><br />
<br />
Si consiguiésemos asociar a cada elemento a ser almacenado un número como en el ejemplo anterior, podremos realizar las operaciones de inserción, eliminación y búsqueda en tiempo constante.<br />
La función que asocia a cada elemento de un conjunto U un número que sirva de índice en una tabla (array) es llamada de función hash. <br />
Una función hash debe satisfacer las siguientes condiciones: <br />
<ol><li> Ser simple de calcular</li>
<li>Asegurar que elementos distintos posean índices distintos.</li>
<li>Generar una distribución equilibrada para los elementos dentro del array.<br />
</li>
</ol><strong><span style="font-size: large;">Funciones Hash</span></strong><br />
<br />
Crear una función hash satisfaciendo las condiciones anteriores no siempre es una tarea fácil. Existen mucho modelos de creación para funciones hash. A continuación se presentan apenas dos formas de creación de funciones hash. en "Cormen,T.H. Leiserson C.E., Rivest R.L. Introduction to Algorithms" pueden ser encontraod varios ejemplos afines hash.<br />
<br />
Una buena función hash es aquella en que toda entrada (slot) del array posee la misma probabilida de ser alcanzado por la función.<br />
<br />
<strong>Método da División</strong><br />
El método de la división consiste en los siguiente: suponga que los elementos x que deben ser almacenados sean números enteros, una función hash que puede ser utilizada para distribuir tales números en un array (tabla hash) es:<br />
h(x)=x% (tamaño de la tabla)<br />
Implementación<br />
La siguiente función describe la implementación de la función hash descrita anteriormente para el caso de strings.<br />
<br />
int Hash(char *a, int stringsize)<br />
{<br />
int hashval, j;<br />
hashval = (int) a[0];<br />
for (j = 1; j < stringsize; j++) <br />
hashval += (int) a[j]; <br />
return(hashval % tablesize); /* suponiendo que tablesize es global */<br />
} <br />
<br />
<div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong>Método del Doblado</strong> <br />
</div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">En este método, las llaves son interpretadas como una secuencia de dígitos escritos en un pedazo de papel. Ello consiste en "doblar" ese papel, de manera que los dígitos se superpongan sin llevar en consideración el "se lleva uno" como se muestra en la siguiente figura. <br />
</div><br />
<div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><a href="http://img225.imageshack.us/img225/9115/metododoblado.jpg" imageanchor="1" style="clear: left; cssfloat: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img alt="metodo del boblado hash " border="0" src="http://img225.imageshack.us/img225/9115/metododoblado.jpg" /></a><br />
</div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><br />
<br />
El proceso es repetido hasta que los dígitos formen un número menor al del tamaño de la tabla hash.<br />
</div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Es importante resaltar que el metodo de doblar tambien puede ser usado con números binarios. En este caso, en vez de la suma, se debe realizar una operación de "OR exclusivo", pues operaciones de "AND" y de "OR" tienden a producir direcciones-base concentrados al final o al inicio de la tabla. <br />
</div><br />
<div><br />
</div><br />
<span style="font-size: large;"><strong>Colisiones</strong></span><br />
<br />
Por más que se intente encontrar una función hash eficiente, en aplicaciones prácticas es difícil conseguir evitar el problema de colisiones de llaves. Así, se vuelve necesario estudiar alternativas para este problema.<br />
Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos:<br />
Existen varias formas de resolver el problema de colisiones, dentro de ellas destacamos:<br />
<strong>Encadenamiento Separado o Externo (Separate Chaining)</strong><br />
En el encadenamiento separado colocamos los elementos que poseen llaves iguales en una listas encadenada.<br />
<br />
<img alt="coliciones con listas" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgM2CmCQp6qZGve2MPtGo_eMmtk_0W2FkYn1-uRmzLJHEPtrjRphTd8o8RPPCRvW5Ts3MQkffjbDhY-dTpe9w39ULFbBFTMAFGLuXFIzjueg5NODF2AyiH9Eal2PANjYn9lCLDPBcFqc0Y/s320/Tablahash.gif" /><br />
<br />
Utilizando esta estrategia, no es difícil percibir que en el peor de los casos el tiempo para insertar un nuevo elemento en la tabla es de O(1). La búsqueda por un elemento, toma el tiempo proporcional al tamaño de la lista almacenada en cada slot.<br />
<br />
<strong>Encadenamiento Interno</strong><br />
Encadenamiento interno es un método para resolver problemas de colisiones mediante el empleo de listas encadenadas que comparten el mismo espacio de memoria al de la tabla de distribución.<br />
<br />
El encadenamiento interno prevee la división de la tabla T en dos zonas, una de dirección-base, de tamaño p, y otra reservada para colisiones, de tamaño s. Naturalmente, p+s = m, donde m corresponde al tamaño de la tabla hash.<br />
<br />
<div><br />
</div><img alt="encadenamiento interno " src="http://www.alipso.com/monografias/2813_datos2/index_archivos/image015.gif" /><br />
Un problema de esta técnica es que ella puede provocar colisiones secundaria, eso quiere decir, que puede provocar colisiones provenientes de la coincidencia de direcciones para llaves que no son sinónimas. Este fue el caso ocurrido en al figura anterior cuando se intentó insertar el número 02. En la dirección base de este número ya se encontraba el número 14, el cual no es sinónimo de 02.<br />
Otra dificultad de esta técnica se encuentra en la función de eliminación de un elemento. Es necesario tomar cuidado en este procedimiento para que la llamada de búsqueda y eliminación futuras no retornen falsos resultados. ¿Por qué? Cuando estudiamos la técnica de direccionamiento abierto, veremos una solución para este problema.<br />
<br />
<strong><span style="font-size: large;">Implementación</span></strong><br />
<br />
A continuación se tiene la implementación de una estructura hash y las funciones de inserción, búsqueda y eliminación en la tabla. <br />
<br />
<div><br />
</div><a alt="descarga" href="http://www.box.net/shared/58k014kgfs" target="blank">Ver código </a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-42058865248430184912009-09-28T00:30:00.000-07:002009-09-30T00:50:47.746-07:00Árbol Patricia en c++Practical Algorithm to Retrieval Information Coded in Alphanumeric.<br />
Es un trie en el cual se han eliminado todas las ramas (terminales o no) que degeneran en listas.<br />
<br />
<img src="http://img12.imageshack.us/img12/8571/patricia.png" /><br />
<br />
la estructura del arbol esta dado por:<br />
<br />
<strong>struct </strong>nodo_arbl<br />
{<br />
<strong>char </strong>dato;<br />
<strong>int</strong> vistas;<br />
ro *dir[32];<br />
};<br />
<br />
un nodo contiene con 32 punteros pa las diferentes letras mas un contador de visitas, y su dato..<br />
el contadro de visitas se usa para cuando queramos imprir las palabras ..<br />
para ver cuantas veces fue visitado ese nodo, si lo no lo visito mas de 1 ves es evidencia de que es un nodo padre ..<br />
para el cual es ahi donde se aplica la recursividad de en orden ....<br />
<br />
<strong>descargar:</strong><br />
<br />
<a href="http://www.megaupload.com/?d=O6JM8B0T" target="blank"><img alt="Descarga" src="http://img87.imageshack.us/img87/1453/downloadc.png" /> </a>Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-3600511067273520325.post-83712716484814496362009-09-27T23:39:00.000-07:002009-12-01T05:49:10.464-08:00Listas simplemente encadenadaEn una lista simplemente encadenada, cada elemento posee apenas información de quien es su sucesor.<br />
Es necesario también almacenar la información del primer elemento de la lista.<br />
Principales problemas:<br />
_Imposibilidad de regresar al elemento anterior.<br />
_Necesidad de guardar información del elemento anterior a fin de realizar algunas operaciones.<br />
<a href="http://www.blogger.com/goog_1259673008538"><br />
</a><br />
<strong>Implementación (Estática)</strong><br />
<a href="http://www.blogger.com/goog_1259673008538"><br />
</a><br />
Para simplificar se considerará que los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada. <br />
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada estática. El nuevo elemento será insertado entre el elemento actual y el elemento anterior.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.blogger.com/goog_1259673008538"><img alt="Listas simplemente encadenada estática" border="0" src="http://img502.imageshack.us/img502/7922/ls3.jpg" /></a><br /></div>
Especificación: <br />
1. LE *Inicia_Lista(int N) // Crea una nueva lista con N elementos<br />
2. void Inserta_Elemento(LE *L, int A) //Inserta un nuevo elemento A en la posicion correcta de la lista L<br />
3. int Elimina_Elemento(LE *L, int A) //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía, retorna -1.<br />
4. void Imprime_Lista (LE *L) <br />
5. LE *Vacia_Lista(LE *L)<br />
<img alt="Descarga" src="http://s1.animeid.com/imagenes/descargar.gif" /><br />
<br />
Código:<br />
<br />
<textarea cols="70" rows="30" style="background-color: white; color: blue;" wrap="soft">#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
typedef struct lista LE;
typedef struct nodo_lista NO;
typedef struct vacio VC;
struct vacio
{
int ultimo; /* guarda a última posición ocupada del vector pos_vac */
int *pos_vac;
};
struct nodo_lista
{
int elem;
int prox; /* guarda la posición del próximo elemento en la lista */
};
struct lista
{
int head ; /* marca la posición del primer elemento de la lista */
VC *vac ; /* guarda posiciones vacías */
NO *nodo ;
};
LE *Inicia_Lista(int N)
{
LE *temp;
int i ;
if ((temp = (LE *) malloc(sizeof(LE))) != NULL)
{
if ((temp->nodo = (NO *) malloc(N*sizeof(NO))) != NULL)
{
if ((temp->vac = (VC *) malloc(N*sizeof(VC))) != NULL)
{
if ((temp->vac->pos_vac = (int *) malloc(N*sizeof(int))) != NULL)
{
temp->vac->ultimo = N-1;
for (i = 1; i <= N; i++)
temp->vac->pos_vac[i-1] = N-i;
temp->head = -1; /* lista vacia */
return(temp);
}
else
exit(0);
}
else
exit(0);
}
else
exit(0);
}
else
exit(0);
}
void Inserta_Elemento(LE *L, int A)
{
int i,ant;
/* Ejercicio: realizar prueba para ver si todavía existe espacio */
if (L->head == -1) /* Lista esta vacía */
{
L->head = 0;
L->nodo[0].elem = A;
L->nodo[0].prox = -1;
(L->vac->ultimo)--;
}
else
{
i = L->head;
ant = -1;
while ((i != -1) && (L->nodo[i].elem <= A))
{
ant = i; /* guarda la posicion del anterior */
i = L->nodo[i].prox;
}
L->nodo[L->vac->pos_vac[L->vac->ultimo]].elem = A;
if (ant == -1) /* incluir al inicio de la lista */
{
L->nodo[L->vac->pos_vac[L->vac->ultimo]].prox = L->head;
L->head = L->vac->pos_vac[L->vac->ultimo];
}
else
{
L->nodo[L->vac->pos_vac[L->vac->ultimo]].prox = L->nodo[ant].prox;
L->nodo[ant].prox = L->vac->pos_vac[L->vac->ultimo];
}
(L->vac->ultimo)--;
}
return;
}
void Imprime_Lista(LE *l)
{
int i;
i = l->head;
cout<<"\n Elementos ";
while (i != -1)
{
cout<<l->nodo[i].elem<<" ";
i = l->nodo[i].prox;
}
}
/* Ejercicios: Implementar las funciones que faltan */
int Elimina_Elemento(LE *L, int A){
int i,ant;
if (L->head == -1){
return -1;
}
else
{
i = L->head;
if (L->nodo[i].elem == A)
{
L->head = L->nodo[i].prox;
(L->vac->ultimo)++;
return 1;
}
while(i != -1){
if(L->nodo[i].elem==A){
L->nodo[ant].prox=L->nodo[i].prox;
L->nodo[i].prox=NULL;
(L->vac->ultimo)++;
return 1;
}
else{
ant=i;
i=L->nodo[i].prox;
}
}
return -1;
}
}
main()
{
LE *l;
int N,aux_l,x=0;
char opc;
cout<<"Ingrese el num. max. elem. en la lista\n";
cin>>N;
l = (LE *) Inicia_Lista(N);
while (1)
{
cout<<"\n Insertar(i) Eliminar(e) Imprimir(p) Salir(s) ";
cin>>opc;
if (opc == 'i')
{
cout<<"\n Ingrese el nuevo número entero ";
cin>>x;
Inserta_Elemento(l,x);
}
if (opc == 'e')
{
printf("\n Ingrese el núm. entero a buscar ");
scanf("%d",&x);
aux_l = Elimina_Elemento(l,x);
if (aux_l == -1)
printf("Numero no encontrado\n");
}
if (opc == 'p')
Imprime_Lista(l);
if (opc == 's')
{
/* l = (LE *) Vacia_Lista(l); */
exit(0);
}
}
}
</textarea>
<br />
<br />
<strong><span style="color: white;">Implementación (Dinámica)</span></strong><span style="color: white;"> <br />
<br />
Por simplicidad los elementos almacenados serán números enteros. Los elementos serán insertados de forma ordenada.<br />
El esquema gráfico abajo muestra el proceso de inserción de un nuevo elemento en una lista encadenada dinámica. el nuevo elemento será insertado entre el elemento actual y el elemento anterior.</span><a href="http://www.blogger.com/goog_1259673008538"> </a><a href="http://www.box.net/shared/i1z2sccmdd" target="blank"><br />
<br />
</a> <img src="http://img121.imageshack.us/img121/4807/listas.png" /><br />
<br />
Las operaciones ilustradas pueden ser descritas como: <br />
nuevo->prox = actual; <br />
anterior->prox = nuevo; <br />
<br />
Especificación: <br />
<br />
<a href="http://www.box.net/shared/i1z2sccmdd" target="blank"></a><br />
<ol>
<li>LE *Inicia_Lista() //Crea una nueva lista</li>
<li>void Inserta_Elemento(LE *L, int A) //Inserta un nuevo elemento A en la posición correcta de la lista L</li>
<li>int Elimina_Elemento(LE *L, int A) //Elimina el elemento A de la lista L. Si el elemento no existe o la lista está vacía retorna -1.</li>
<li>void Imprime_Lista (LE *L) </li>
<li>LE *Vacia_Lista(LE *L)</li>
</ol>
<a href="http://www.box.net/shared/i1z2sccmdd" target="blank"><br />
</a><a href="http://www.box.net/shared/49ivfev0tt" target="blank"><img alt="Descarga" src="http://s1.animeid.com/imagenes/descargar.gif" /><br />
<br />
Código:<br />
<textarea cols="70" rows="30" style="background-color: white; color: blue;" wrap="soft">#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
typedef struct lista LE;
typedef struct nodo_lista NO;
struct nodo_lista
{
int elem;
NO *prox; /* guarda la posicion del proximo elemento en la lista */
};
struct lista
{
NO *head,*pa,*imp; /* guarda la direccion del primer elemento de la lista */
};
LE *Inicia_Lista(void)
{
LE *temp;
if ((temp = (LE *) malloc(sizeof(LE))) != NULL)
{
temp->head = NULL;
return(temp);
}
else
exit(0);
}
void Inserta_Elemento(LE *L, int A)
{
NO *aux,*ant,*atu;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
aux->elem = A;
if (L->head == NULL)
{
aux->prox = NULL;
L->head = aux;
}
else
{
atu = L->head;
ant = NULL;
while ((atu != NULL) && (atu->elem <= A))
{
ant = atu;
atu = atu->prox;
}
if (ant == NULL) /* insertar en la primera posición de la lista */
{
aux->prox = L->head;
L->head = aux;
}
else
{
aux->prox = ant->prox;
ant->prox = aux;
}
}
}
else
exit(0);
return;
}
int Eliminar_Elemento(LE *L,int A){
NO *aux,*ant,*atu;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
if(L->head == NULL){
return -1;
}
else{
atu=L->head;
if(atu->elem==A){
L->head = atu-> prox;
return 1;
}
while (atu != NULL)
{
if(atu->elem==A){
ant->prox=atu->prox;
atu->prox=NULL;
return 1;
}
else{
ant=atu;
atu=atu->prox;
}
}
return -1;
}
}
}
void Invertir_Lista(LE *L){
NO *aux,*ant,*atu;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{ atu = L->head;
ant = NULL;
while (atu!= NULL)
{
L->head=atu->prox;
atu->prox=ant;
ant=atu;
atu=L->head;
}
while (ant != NULL)
{ cout<<ant->elem<<" ";
ant = ant->prox;
}
}
}
void InPar_Lista(LE *L){
NO *atu,*par,*impar;
if ((par = (NO *) malloc(sizeof(NO))) != NULL)
{ atu = L->head;
par = NULL;
impar = NULL;
while (atu != NULL)
{ if(atu->elem%2==0)
{ if(par==NULL)
{L->pa=atu;
par=atu;
}
else{
par->prox=atu;
par=atu;
}}
else
{
if(impar==NULL)
{L->imp=atu;
impar=atu;
}
else{
impar -> prox = atu;
impar=atu;
}}
atu = atu->prox;
if(atu==NULL)
{if(par!=NULL)par->prox=NULL;
if(impar!=NULL)impar->prox=NULL;
}
}
par=L->pa;
impar=L->imp;
while(par!=NULL)
{ cout<<par->elem<<" ";
par = par->prox;
}
cout<<endl;
while(impar!=NULL)
{ cout<<impar->elem<<" ";
impar = impar->prox;
}
}
}
void Imprime_Lista(LE *L){
NO *aux,*atu;
int tam=0;
if ((aux = (NO *) malloc(sizeof(NO))) != NULL)
{
atu = L->head;
while (atu != NULL)
{
tam++;
cout<<atu->elem<<" ";
atu = atu->prox;
}
cout<<" de tama\xa4o "<<tam;
}
}
/* Ejercicios: Implementar las funciones que faltan */
main()
{
int aux_l;
LE *l;
int x=0;
char opc;
l = (LE *) Inicia_Lista();
while (1)
{
cout<<"\nInsertar (i) Eliminar (e) Imprimir (p) Invertir (v) Inpar Par (d) Sair s) ";
cin>>opc;
if (opc == 'i')
{
cout<<"\n Ingrese el nuevo elemento entero ";
cin>>x;
Inserta_Elemento(l,x);
}
if (opc == 'e')
{
cout<<"\n Ingrese el número entero a buscar ";
cin>>x;
aux_l = Eliminar_Elemento(l,x);
if (aux_l == -1)
cout<<"Numero no encontrado\n";
}
if(opc=='v')
Invertir_Lista(l);
if(opc=='d')
InPar_Lista(l);
if (opc == 'p')
Imprime_Lista(l);
if (opc == 's')
{
//l = (LE *) Vacia_Lista(l);
exit(0);
}
}
}
</textarea>
</a><br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3600511067273520325.post-16309209522703841382009-08-20T13:34:00.000-07:002009-08-20T13:38:50.757-07:00Bienbenidos<a href="http://www.bloginformatico.com/wp-content/uploads/2007/05/lenguajes-de-programacion.jpg"><img style="FLOAT: left; MARGIN: 0px 10px 10px 0px; WIDTH: 350px; CURSOR: hand; HEIGHT: 263px" alt="" src="http://www.bloginformatico.com/wp-content/uploads/2007/05/lenguajes-de-programacion.jpg" border="0" /></a>Este es un foro de programacion esta orientado a estudiantes de preparatoria en la universidad y publico en general interezado.<br /><br />Ps aki os dejare alguno ejempliyos que son pedidos con frecuencia para tareas y trabajos...cualquier pedido solo haganmelo llegar..bueno el lenguaje q domina es el c++ y java..si quieren los programas igual me piden ..yo les dejo aki .....xfa comenten..Unknownnoreply@blogger.com0