rihardmarius

listas libreria

Nov 23rd, 2013
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct node {
  2.   int entry = 0; // valores por defecto
  3.   node *next = nullptr;
  4. };
  5.  
  6. struct lista {
  7.     node* root = nullptr;
  8. };
  9.  
  10. node* create_node (int a)
  11. {
  12.     node* nuevo = new node;
  13.     nuevo->entry = a;
  14.     return nuevo;
  15. }
  16.  
  17. void insertar_nodo_en_orden (lista& l, int a)
  18. {
  19.     node* nuevo = create_node(a);
  20.     node* p = l.root;
  21.     if(l.root == 0)
  22.     {
  23.         l.root = nuevo;
  24.         return;
  25.     }
  26.     if (a <= p->entry)
  27.     {
  28.         nuevo->next = p;
  29.         l.root = nuevo;
  30.         return;
  31.     }
  32.     node* previous = 0;
  33.     while (p != 0 and a > p->entry) //se termina cuando se acaba la lista o encontro un valor menor a a
  34.     {
  35.         previous = p;
  36.         p = p->next;
  37.     }
  38.     nuevo->next = p;
  39.     previous->next = nuevo;
  40. }
  41.  
  42. void insertar_nodo_en_orden_decreciente (lista& l, int a)
  43. {
  44.     node* nuevo = create_node(a);
  45.     node* p = l.root;
  46.     if(l.root == 0)
  47.     {
  48.         l.root = nuevo;
  49.         return;
  50.     }
  51.     if (a >= p->entry)
  52.     {
  53.         nuevo->next = p;
  54.         l.root = nuevo;
  55.         return;
  56.     }
  57.     node* previous = 0;
  58.     while (p != 0 and a < p->entry) //se termina cuando se acaba la lista o encontro un valor menor a a
  59.     {
  60.         previous = p;
  61.         p = p->next;
  62.     }
  63.     nuevo->next = p;
  64.     previous->next = nuevo;
  65. }
  66.  
  67. int get_size_of_list (lista& a)
  68. {
  69.     node* p = a.root; int c = 0;
  70.     while (p != 0)
  71.     {
  72.         c++;
  73.         p = p-> next;
  74.     }
  75.     return c;
  76. }
  77.  
  78. void swap_entries (node*& a, node*& b)
  79. {
  80.     int aux = a->entry;
  81.     a->entry = b->entry;
  82.     b->entry = aux;
  83. }
  84.  
  85. void ordenar_lista (lista& a)
  86. {
  87.     node* p = a.root;
  88.     node* q = a.root;
  89.  
  90.     while (p != 0)
  91.     {
  92.         q = q->next;
  93.         while (q != 0)
  94.         {
  95.             if (p->entry > q->entry)
  96.                 swap_entries (p,q);
  97.             q = q->next;
  98.         }
  99.         p = p->next;
  100.         q = p;
  101.     }
  102. }
  103.  
  104. bool is_list_sorted (lista& a)
  105. {
  106.     node *p = a.root;
  107.     int aux = p->entry;
  108.     p = p->next;
  109.     while (p!=0)
  110.     {
  111.         if(p->entry < aux)
  112.             return false;
  113.         aux = p->entry;
  114.         p = p->next;
  115.     }
  116.     return true;
  117. }
  118.  
  119. bool is_vacia (lista &l) // funciona
  120. {
  121.     return l.root == 0;
  122. }
  123.  
  124. void mostrar_lista (lista& l) // funciona
  125. {
  126.     if(not is_vacia(l))
  127.     {
  128.         for (node *p = l.root; p != 0; p = p->next)
  129.             cout << p->entry << ' ';
  130.         cout << endl;
  131.     }
  132.     else
  133.         cout << "Lista vacia." << endl;
  134. }
  135.  
  136. void mostrar_vacia (lista& l) // funciona
  137. {
  138.     if (is_vacia(l))
  139.         cout << "esta vacia" << endl;
  140.     else
  141.         cout << "no esta vacia" << endl;
  142. }
  143.  
  144. int get_by_index (lista& l, int index) // funciona
  145. {
  146.     node* p = l.root;
  147.     for (int i=0; i < index; i++)
  148.     {
  149.         p = p->next;
  150.     }
  151.     return p->entry;
  152. }
  153.  
  154. void insertar_nodo_al_final (lista &l, int a) // funciona
  155. {
  156.     node* nuevo = new node;
  157.     nuevo->entry = a;
  158.     if (l.root != 0) // apunta a algo?
  159.     {
  160.         node* p = l.root;
  161.         while (p->next != 0)
  162.             p = p->next;
  163.         p->next = nuevo;
  164.     }
  165.     else
  166.         l.root = nuevo;
  167. }
  168.  
  169. void insertar_nodo_en_index(lista& l, int index, int valor) // funciona
  170. {
  171.     node* nuevo = new node;
  172.     nuevo->entry = valor;
  173.  
  174.     if (index != 0)
  175.     {
  176.         node* p = l.root;
  177.         for (int i = 0; i < index - 1; i++)
  178.         {
  179.             p = p->next;
  180.         }
  181.         nuevo->next = p->next;
  182.         p->next = nuevo;
  183.     }
  184.     else
  185.     {
  186.         nuevo->next = l.root;
  187.         l.root = nuevo;
  188.     }
  189. }
  190.  
  191. void eliminar_nodo_en_index (lista& l, int index) // funciona
  192. {
  193.     node* p = l.root;
  194.     if (index == -1)
  195.     return;
  196.     if (index != 0)
  197.     {
  198.         node* q = l.root;
  199.         for (int i = 0; i < index - 1; i++)
  200.         {
  201.             p = p->next;
  202.         }
  203.         q = p->next->next;
  204.         delete p->next;
  205.         p->next = q;
  206.     }
  207.     else
  208.     {
  209.         l.root = p->next;
  210.         delete p;
  211.     }
  212. }
  213.  
  214. void eliminar_lista (lista& l) // funciona
  215. {
  216.     while (l.root != 0)
  217.         eliminar_nodo_en_index(l,0);
  218. }
  219.  
  220. int buscar_elemento (lista& l, int e) // funciona
  221. {
  222.     int index = 0;
  223.     node* p = l.root;
  224.     while (p->entry != e and p->next != 0) // p->next == 0  => es el ultimo
  225.     {
  226.         p = p->next;
  227.         index++;
  228.     }
  229.  
  230.     if (p->entry == e)
  231.         return index;
  232.     else
  233.         return -1;
  234. }
  235.  
  236. void eliminar_nodo_segun_entry (lista& l, int a)
  237. {
  238.     int i = buscar_elemento(l,a);
  239.     eliminar_nodo_en_index(l,i);
  240. }
  241.  
  242. void buscar_o_insertar (lista& l, node*& ptr, int valor)
  243. {
  244.     node* p = l.root;
  245.     node* previous;
  246.     while (p != 0 and p->entry != valor)
  247.     {
  248.         previous = p;
  249.         p = p->next;
  250.     }
  251.     if (p == 0)
  252.     {
  253.         node* nuevo = create_node(valor);
  254.         previous->next = nuevo;
  255.         ptr = nuevo;
  256.     }
  257.     else if (p->entry == valor)
  258.         ptr = p;
  259. }
  260.  
  261. void insertar_despues (lista& l, int nodo, int valor)
  262. {
  263.     int index = buscar_elemento(l, nodo);
  264.     if (index != -1)
  265.         insertar_nodo_en_index(l,index+1,valor);
  266. }
  267.  
  268. void insertar_antes (lista& l, int nodo, int valor)
  269. {
  270.     int index = buscar_elemento(l, nodo);
  271.     if (index != -1)
  272.         insertar_nodo_en_index(l,index,valor);
  273. }
  274.  
  275. void insertar_primero (lista& l, int valor)
  276. {
  277.     node* p = l.root;
  278.     node* nuevo = create_node(valor);
  279.     nuevo->next = p;
  280.     l.root = nuevo;
  281. }
RAW Paste Data