Advertisement
rihardmarius

final 1a - interseccion

Nov 23rd, 2013
1,096
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* 1. Intersección
  2. Temas evaluados: Listas enlazadas, abstracción procedural, estructuras de control, y lenguaje de programación.
  3. 1a. Escriba en Pascal, (puede ser C o C++, si asi lo decidiera) el encabezado de una función o procedimiento que reciba
  4. dos listas enlazadas de enteros, a y b, y genere una tercera, c, con la intersección de a y b. Asuma que las listas a y b están
  5. ordenadas y que no contienen repeticiones. La lista c debe generse ordenada. Escriba la definición de los tipos de datos no
  6. primtivos utilizados. Utilice el pasaje por referencia correctamente.
  7. */
  8.  
  9. #include <iostream>
  10. using namespace std;
  11.  
  12. struct node {
  13.   int entry = 0; // valores por defecto
  14.   node *next = nullptr;
  15. };
  16. struct lista {
  17.     node* root = nullptr;
  18. };
  19.  
  20. void mostrar_lista (lista& l);
  21. bool is_vacia (lista &l);
  22. void mostrar_vacia (lista& l);
  23. int get_by_index (lista& l, int index);
  24. void insertar_nodo_al_final (lista &l, int a);
  25. void insertar_nodo_en_index(lista& l, int index, int valor);
  26. void eliminar_nodo_en_index (lista& l, int index);
  27. void eliminar_lista (lista& l);
  28. int buscar_elemento (lista& l, int e);
  29.  
  30. void interseccion (const lista& a, const lista& b, lista& c)
  31. {
  32.     node* p = a.root;
  33.     node* q = b.root;
  34.  
  35.     while (p != 0 and q != 0)
  36.     {
  37.         if (p->entry == q->entry)
  38.         {
  39.             insertar_nodo_al_final(c,p->entry);
  40.             p = p->next;
  41.             q = q->next;
  42.             continue;
  43.         }
  44.  
  45.         if (p->entry < q->entry)
  46.             p = p->next;
  47.         else
  48.             q = q->next;
  49.     }
  50. }
  51.  
  52. int main()
  53. {
  54.     lista L, M, I;
  55.  
  56.     for (int i=0; i<5; i++)
  57.         insertar_nodo_al_final (L, i+1);
  58.     for (int i=0; i<5; i++)
  59.         insertar_nodo_al_final(M, i+3);
  60.  
  61. //  insertar_nodo_al_final(I, 0);
  62.  
  63.     interseccion(L,M,I);
  64.  
  65.     mostrar_lista(L);
  66.     mostrar_lista(M);
  67.  
  68.     if (is_vacia(I))
  69.         cout << "lista vacia" << endl;
  70.     else
  71.         mostrar_lista(I);
  72.  
  73.     return 0;
  74. }
  75.  
  76. void mostrar_lista (lista& l) // funciona
  77. {
  78.     for (node *p = l.root; p != 0; p = p->next)
  79.         cout << p->entry << ' ';
  80.     cout << endl;
  81. }
  82.  
  83. bool is_vacia (lista &l) // funciona
  84. {
  85.     return l.root == 0;
  86. }
  87.  
  88. void mostrar_vacia (lista& l) // funciona
  89. {
  90.     if (is_vacia(l))
  91.         cout << "esta vacia" << endl;
  92.     else
  93.         cout << "no esta vacia" << endl;
  94. }
  95.  
  96. int get_by_index (lista& l, int index) // funciona
  97. {
  98.     node* p = l.root;
  99.     for (int i=0; i < index; i++)
  100.     {
  101.         p = p->next;
  102.     }
  103.     return p->entry;
  104. }
  105.  
  106. void insertar_nodo_al_final (lista &l, int a) // funciona
  107. {
  108.     node* nuevo = new node;
  109.     nuevo->entry = a;
  110.     if (l.root != 0) // apunta a algo?
  111.     {
  112.         node* p = l.root;
  113.         while (p->next != 0)
  114.             p = p->next;
  115.         p->next = nuevo;
  116.     }
  117.     else
  118.         l.root = nuevo;
  119. }
  120.  
  121. void insertar_nodo_en_index(lista& l, int index, int valor) // funciona
  122. {
  123.     node* nuevo = new node;
  124.     nuevo->entry = valor;
  125.  
  126.     if (index != 0)
  127.     {
  128.         node* p = l.root;
  129.         for (int i = 0; i < index - 1; i++)
  130.         {
  131.             p = p->next;
  132.         }
  133.         nuevo->next = p->next;
  134.         p->next = nuevo;
  135.     }
  136.     else
  137.     {
  138.         nuevo->next = l.root;
  139.         l.root = nuevo;
  140.     }
  141. }
  142.  
  143. void eliminar_nodo_en_index (lista& l, int index) // funciona
  144. {
  145.     node* p = l.root;
  146.     if (index != 0)
  147.     {
  148.         node* q = l.root;
  149.         for (int i = 0; i < index - 1; i++)
  150.         {
  151.             p = p->next;
  152.         }
  153.         q = p->next->next;
  154.         delete p->next;
  155.         p->next = q;
  156.     }
  157.     else
  158.     {
  159.         l.root = p->next;
  160.         delete p;
  161.     }
  162. }
  163.  
  164. void eliminar_lista (lista& l) // funciona
  165. {
  166.     while (l.root != 0)
  167.         eliminar_nodo_en_index(l,0);
  168. }
  169.  
  170. int buscar_elemento (lista& l, int e) // funciona
  171. {
  172.     int index = 0;
  173.     node* p = l.root;
  174.     while (p->entry != e and p->next != 0) // p->next == 0  => es el ultimo
  175.     {
  176.         p = p->next;
  177.         index++;
  178.     }
  179.  
  180.     if (p->entry == e)
  181.         return index;
  182.     else
  183.         return -1;
  184. }
Advertisement
RAW Paste Data Copied
Advertisement