Estructures de dades amb C++

De Wikijoan
Dreceres ràpides: navegació, cerca

Contingut

Introducció

La STL (Standard Template Library) de C++ es una colección genérica de plantillas de clases y algoritmos que permite a los programadores implementar fácilmente estructuras estándar de datos como colas (queues), listas (lists), y pilas (stacks).

La STL de C++ provee a los programadores con lo constructores siguientes, agrupados en tres categorias:

Secuencias (sequences)

  1. C++ Vectors
  2. C++ Lists
  3. C++ Double-Ended Queues

Adaptadores de contenedor (Container Adapters)

  1. C++ Stacks
  2. C++ Queues
  3. C++ Priority Queues

Contenedores asociativos (Associative Containers)

  1. C++ Bitsets
  2. C++ Maps
  3. C++ Multimaps
  4. C++ Sets
  5. C++ Multisets

La idea detras de la STL de C++ es que la parte dificil en el uso de estructuras complejas de datos ya ha sido previamente completada. Por ejemplo, si un programador desea usar un stack de enteros, todo lo que tiene que hacer es escribir el código:

stack<int> myStack;

Con un minimo de esfuerzo, él o ella puede usar la función push() para ingresar enteros al stack; y la función pop() para retirar enteros del stack. A travez de la magia de las plantillas de C++, se puede especificar cualquier tipo de dato, no sólo enteros. La clase Stack de la STL provee la funcionalidad genérica de un stack, sin importar el tipo de dato en el stack.

En general tots aquests containers en diem Standard Library Container: SLC. És a dir, tenim unes llibreries estàndard (recordar que utilitzem namespace std) que ens proporcionen aquestes estructures de dades ja implementades: llistes, cues, piles, vectors,...

Cues

he utilitzat cues al projecte jjoanillorouter i jplayfine (v101). Després he vist que el que necessito són llistes i no cues, doncs vull accedir a elements de dins. Té pocs mètodes, doncs se'n necessiten pocs (només es pot accedir al primer element).

A jjoanillorouter he utilitzat cues que emmagatzemen objectes.

Piles

Vectors

Llistes

Llibreria estàndard #include <list>

Com que es pot accedir a dins els elements de la llista disposo de molts mètodes (sort, inserir al principi, inserir al final,...)

Utilitzo llistes en el projecte jPlayfine. Concretament, les llistes que m'interessen són les llistes que emmagatzemen objectes. La info la he trobat a

Llista no estàndard

Ho he trobat a:

Per compilar:

$ g++ -o Exercise  Exercise.cpp

List.h

#ifndef NONSTD_LIST_H
#define NONSTD_LIST_H

#include <unistd.h>
#include <cassert>


namespace nonstd
{

template <class T>
class List
{
private:
class ListIterator;

public:
typedef ListIterator iterator;
typedef const ListIterator const_iterator;
typedef T value_type;

// constructor
List()
: m_head(0),
m_tail(0),
m_size(0)
{
}

List(const List<T>& other)
: m_head(0),
m_tail(0),
m_size(0)
{
for (iterator it = other.begin(); it != other.end(); ++it)
{
push_back(*it);
}
}

// destructor
~List()
{
clear();
m_head = m_tail = 0;
}

// push_front()
void push_front(T elem) // inserts at the beginning
{
if (m_head == 0)
{
m_head = new Node(elem, 0, 0);
m_tail = m_head;
}
else
{
m_head = new Node(elem, 0, m_head);
}
++m_size;
}

// pop_front()
void pop_front() // deletes the first element
{
Node* tmp = m_head->m_next;
delete m_head;
m_head = tmp;
m_head->m_prev = 0;
--m_size;
}

void push_back(T elem) // inserts at the end
{
if (m_head == 0)
{
m_head = new Node(elem, 0, 0);
m_tail = m_head;
}
else
{
m_tail->m_next = new Node(elem, m_tail, 0);
m_tail = m_tail->m_next;
}
++m_size;
}

void pop_back() // deletes the last element
{
Node* tmp = m_tail;
m_tail = tmp->m_prev;
delete tmp;
--m_size;
}

iterator insert(iterator& position, const T& elem)
{
iterator it = begin();

for (; it != position; ++it);

it.m_node->m_prev->m_next = new Node(elem, it.m_node->m_prev, it.m_node);
++m_size;

return it.m_node->m_prev->m_next;
}

iterator erase(iterator position)
{
iterator it = begin();

for (; it != position; ++it);

it.m_node->m_prev->m_next = it.m_node->m_next;
it.m_node->m_next->m_prev = it.m_node->m_prev;

iterator next = it.m_node->m_next;

delete it.m_node;

--m_size;

return next;
}

void clear()
{
iterator it = begin();

while (it != 0)
{
Node* node = it.m_node;
++it;
delete node;
}
m_size = 0;
}

size_t size() const
{
return m_size;
}

iterator begin()
{
return m_head;
}

const_iterator begin() const
{
return m_head;
}

iterator end()
{
return 0;
}

const_iterator end() const
{
return 0;
}

iterator last()
{
return m_tail;
}

const_iterator last() const
{
return m_tail;
}

void sort()
{
// we always number elements in linked list as 1, 2, ..., n
// instead of 0, 1, ..., n-1; hence start index is 1.
m_head = quicksort(m_head, 1, m_size);

// restore previous-element pointers
Node* node = m_head;
Node* pnode = 0;

while (node != 0)
{
node->m_prev = pnode;
pnode = node;
node = node->m_next;
}
m_tail = pnode;
}

typedef bool (*Sorter)(const T& first, const T& second);

void sort(Sorter s)
{
}

private:
struct Node
{
Node(T elem, Node* prev, Node* next) : m_elem(elem), m_prev(prev), m_next(next) {}
bool operator>(const Node& other) { return m_elem > other.m_elem; }
bool operator<(const Node& other) { return m_elem < other.m_elem; }
bool operator==(const Node& other) { return m_elem == other.m_elem; }

T m_elem;
Node* m_prev;
Node* m_next;
};

class ListIterator
{
public:
typedef T iterator_category;

ListIterator(Node* head) : m_node(head) {}

ListIterator(const ListIterator& it) : m_node(it.m_node) {}

bool operator==(const ListIterator& other) const { return m_node == other.m_node; }
bool operator!=(const ListIterator& other) const { return m_node != other.m_node; }

void operator++() // goto the next element
{
assert(m_node != 0);
m_node = m_node->m_next;
}

void operator--() // goto the previous element
{
assert(m_node != 0);
m_node = m_node->m_prev;
}

T& operator*() // access the current element
{
assert(m_node != 0);
return m_node->m_elem;
}

private:
friend class List<T>;
Node* m_node;
};


// quicksort()
//
Node* quicksort(Node* list, unsigned int listStart, unsigned int listEnd)
{
if (listStart >= listEnd)
return list;

unsigned int i = listStart;
unsigned int j = listEnd - 1;

Node* right = getNthNode(list, listEnd);
Node* left = getNthNode(list, listStart);
Node* pivot = selectPivot(left, right);
right = findPrev(left, pivot);

for (;;)
{
// now start partitioning the list
for (; left->m_elem < pivot->m_elem; ++i)
{
left = left->m_next;
}

for (; (right->m_elem > pivot->m_elem) && (j > 1); --j)
{
right = findPrev(list, right);
}

if (i < j)
{
list = swapNodes(list, left, right);

// left, right ptrs got swapped, to continue traversing we need them
// back at the same positions.
Node* tmp = left;
left = right;
right = tmp;
}
else
{
break;
}
}

// restore pivot
list = swapNodes(list, left, pivot);

// now sort on smaller linked lists
list = quicksort(list, listStart, i-1);
list = quicksort(list, i+1, listEnd);

return list;
}

// getNthNode()
//
Node* getNthNode(Node* list, unsigned int n)
{
for (unsigned int i = 1; list != 0 && i < n; ++i)
{
list = list->m_next;
}

return list;
}

// selectPivot()
//
Node* selectPivot(Node* list, Node* end)
{
unsigned int n = numNodes(list, end);
Node* noden = getNthNode(list, (unsigned int)((float)n/2 + 0.5));
Node* right = findPrev(list, end);

if (noden != right)
{
// swap the pivot and right most element in the list
// later pivot will be restored.
swapNodes(list, noden, right->m_next);
return noden;
}
else
{
return noden->m_next;
}
}

// numNodes()
//
unsigned int numNodes(Node* list, Node* end)
{
unsigned int i = 1;

for (; list && (list != end); ++i, list = list->m_next);

return (list == end ? i : 0);
}

// findPrev()
//
Node* findPrev(Node* list, Node* curr)
{
for (; list && list->m_next; list = list->m_next)
{
if (list->m_next == curr)
break;
}

if (list->m_next != curr)
{
// we did not find any element; probably indicates what
// we are searching for is the beginning node.
return curr;
}

return list;
}

// swapNodes()
//
// A complete swap algorithm which cares of several scenarios while swapping
// two nodes in a linked list which doesn't have any special nodes.
// Scenarios considered while swapping:
// 1) two nodes which are far away
// 2) two nodes which are far away, one is node at the beginning of the list
// 3) two nodes which are neighbors
// 4) two nodes which are neighbors, one node is at the beginning of the list
Node* swapNodes(Node* list, Node* node1, Node* node2)
{
Node* node1prev = findPrev(list, node1);
Node* node2prev = findPrev(list, node2);
Node* tmp = node2->m_next;

// check whether node to be swapped is in beginning (i.e. header node)
if (node1 != list)
{
node1prev->m_next = node2;
}
else
{
// as we do not have special header node, if the first node and some
// other node, need to be swapped, then update the list (makes new min
// node as logical header)
list = node2;
}

// are nodes to be swapped neighboring nodes?
if (node1->m_next == node2)
{
node2->m_next = node1;
node1->m_next = tmp;
}
else
{
// nodes to be swapped are not neighbor nodes, they are apart;
// so condiser all scenarios
node2->m_next = node1->m_next;
node1->m_next = tmp;
node2prev->m_next = node1;
}

return list;
}

// Data Members
Node* m_head;
Node* m_tail;
size_t m_size;
};

} // end namespace nonstd

#endif


Exercise.cpp:

//http://ubuntuforums.org/archive/index.php/t-1088320.html
//$ g++ -o Exercise  Exercise.cpp

#include "List.h"

#include <algorithm>
#include <iostream>
#include <cassert>


template <typename T> void displayValue(T& value);


int main(int argc, char** argv)
{
nonstd::List<int> list1;

list1.push_back(2);
list1.push_back(5);
list1.push_back(3);
list1.push_back(0);
list1.push_back(4);
list1.push_back(8);
list1.push_back(9);
list1.push_back(7);
list1.push_back(6);
list1.push_back(1);

std::cout << "Before sorting:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

list1.sort();
std::cout << "After sorting:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

list1.push_front(13);
list1.push_front(14);
list1.push_back(11);
list1.push_back(10);
list1.push_back(12);
std::cout << "After inserting 13, 14, 11, 10, 12:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

list1.sort();
std::cout << "After sorting:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

std::cout << "Iterating backwards:\nnil";
for (nonstd::List<int>::iterator it = list1.last(); it != 0; --it)
{
std::cout << " <- " << *it;
}
std::cout << std::endl;

return 0;
}


template <typename T> void displayValue(T& node)
{
std::cout << node << " -> ";
}

Piles


creat per Joan Quintana Compte, desembre 2011

Eines de l'usuari
Espais de noms
Variants
Accions
Navegació
IES Jaume Balmes
Màquines recreatives
CNC
Informàtica musical
joanillo.org Planet
Eines