De 5 senaste artiklarna

Musik/Lastfm Admin /  Skapad: 23:28 - Tisdagen den 19 Februari 2008 / Bloggnummer: 505 / Visad 8300 gånger Senast uppdaterad: 23:28 - Tisdagen den 19 Februari 2008 / Kommentararer är avstängda

Skolarbeten/Datastrukturer Admin /  Skapad: 20:11 - Tisdagen den 19 Februari 2008 / Bloggnummer: 504 / Visad 6918 gånger Senast uppdaterad: 20:11 - Tisdagen den 19 Februari 2008 / Kommentararer är avstängda

#ifndef HEAP_H
#define HEAP_H
#include <iostream>
using namespace std;
template <class T>
class Heap
{
private:
    int nrOfElements;
    int capacity;
    T * elements;
    int increment;
public:
    Heap();
    Heap(int size);
    ~Heap();
    void insert(T element);
    void remove();
    T front();
    int size();
    void print();
    void sizeUp(int newSize);
    bool inHeap(T element);
};
template <class T>
Heap<T>::Heap()
{
    nrOfElements = 0;
    increment = 10000;
    capacity = increment;
    elements = new T[capacity];
}
template <class T>
Heap<T>::Heap(int size)
{
    nrOfElements = 0;
    increment = 10000;
    capacity = size;
    elements = new T[size];
}
template <class T>
Heap<T>::~Heap()
{
    delete [] elements;
}
template <class T>
void Heap<T>::insert(T element)
{
    if(capacity <= nrOfElements)
        sizeUp(capacity+increment);

    if(nrOfElements == 0)
        elements[0] = element;
    else
    {
        elements[nrOfElements] = element;
        int temp = (nrOfElements-1)/2;//Föräldern
        int posHolder = nrOfElements; //Barnet
        while(elements[temp] < element)
        {
            T temp2 = elements[temp];
            elements[temp] = elements[posHolder];
            elements[posHolder] = temp2;
            posHolder = temp;
            temp = (temp-1)/2;
        }
    }
    nrOfElements++;
}
template <class T>
void Heap<T>::remove()
{
    nrOfElements--;
    int currentPos = 0;
    elements[currentPos] = elements[nrOfElements];
    int biggestChildPos = 0;
    while(currentPos*2+2 < nrOfElements)
    {
        if(elements[currentPos*2+1] > elements[currentPos*2+2])
            biggestChildPos = currentPos*2+1;
        else
            biggestChildPos = currentPos*2+2;
        if(elements[biggestChildPos] > elements[currentPos])
        {
            T temp = elements[currentPos];
            elements[currentPos] = elements[biggestChildPos];
            elements[biggestChildPos] = temp;
            currentPos = biggestChildPos;
        }
        else currentPos = nrOfElements;
    }
}
template <class T>
T Heap<T>::front()
{
    if(nrOfElements > 0)
        return elements[0];
    else return T();
}
template <class T>
int Heap<T>::size()
{
    return nrOfElements;
}
template <class T>
void Heap<T>::print()
{
    for(int i = 0;i<nrOfElements;i++)
        cout << elements[i] << endl;
    cout << endl;
}
template <class T>
void Heap<T>::sizeUp(int newSize)
{
    int inc = newSize-capacity;
    capacity = newSize;
    T * temp = new T[capacity];
    for(int i = 0;i<capacity-inc;i++)
        temp[i] = elements[i];
    delete [] elements;
    elements = temp;
}
template <class T>
bool Heap<T>::inHeap(T element)
{
    if(nrOfElements == 0)
        return false;
    else
    {
        for(int i = 0;i<nrOfElements;i++)
            if(element == elements[i])   
                return true;
    }
    return false;
}
#endif

insertionsort      0(n^2)
selectionsort    0(n^2)
bubblesort         0(n^2)       //tar längre tid

quickesort
mergesort
heapsort      //snabbre

kostnad bedöms utav jämförelserna
--------------------------------------------------------------------------------------------------------------------------------------
 
insertionsort:  ta ett element i taget och placera det på rätt plats
  bland de redan sorterade.
      sorterad       osorterad
  ex.  30   28 12 29 3 64
    jämför 28 med 30
   28 30       12 29 3 64
    jämför 12 med 30, flytta till höger, jämför 12 med 28 flytta höger.
   12 28 30        29 3 64
    jämför 29 med 30 mindre.. höger, jä,för 29 med 28 större alltså stanna där.
   12 28 29 30     3 64
    jämför 3 med alla.. flyttas längst fram
   3 12 28 29 30  64
    jämför 64 med 30, 64 större stanna kvar.
   12 28 29 30 64

--------------------------------------------------------------------------------------------------------------------------------------

selectionsort:  leta upp det minsta elementet bland de osorterade och placera det efter
  de redan sorterade.
    sorterad       osorterad
  ex.       30 28 12 29 3 64
   leta igenom allihopa och hitta 3 som minsta och byta plats på första elementet och 3
    3   28 12 29 30 64
   leta igenom igen och samma sak..
    3 12 28 29 30 64

--------------------------------------------------------------------------------------------------------------------------------------
    
bubblesort:  låta ett element i taget "bubbla" uppåt genom parvis jämförelser.
       bra med en checker som kolla om inga flytten gjorts.
   sorterad       osorterad
  ex.        30
     28
     12
     29
      3 
     64
     19

    jämför 19 med 64 = 19 upp, 19 med 3 = 3, 3med 29 3 upp och så vidare.

--------------------------------------------------------------------------------------------------------------------------------------

quickesort: plocka ut ett pivot-element, dela upp testerande element så att de som är mindre
     än pivot-elementet finns till vänster och de som är större till höger. rekursivt.
   sorterad       osorterad
  ex.       20 28 12 29 3 64 19
    plocka ut det första element som pivot.
    gör 2 indexerare, less och more gå med dessa tilös less hittat ett element som är större än pivot
    och more ett som är mindre, sedan byter vi plats på elemeten.
        20 19 12 29 3 64 28
    less på 29 more på 3, byt plats..
        20 19 12 3 29 64 28
    less och more går över varandra..
    stoppa in pivot på den plats more är på, 3 alltså
         3 19 12 20 29 64 28

    nu blor det rekursivt, 3  och 29 blir också pivot.
19 blir less och 12 more.. more letar efter mindre.. stanna på 3, 3an fanns på rätt plats.
         3 19 12 20 29 64 28
28 less, 64 more.. byta    
         3 19 12 20 29 28 64
byta pivot med det som markerat som störst alltså 28 byter med 29
         3 19 12 20 28 29 64
19 pivot, 12 blir både less och more, och då byter 12 ´med 19.. WIN :D
mergesort: 

heapsort:

Skolarbeten/Datastrukturer Admin /  Skapad: 23:27 - Tisdagen den 12 Februari 2008 / Bloggnummer: 500 / Visad 6852 gånger Senast uppdaterad: 23:27 - Tisdagen den 12 Februari 2008 / Kommentararer är avstängda Taggar: cplusplus

#ifndef STACK_H
#define STACK_H
#include "List.h"
template<class T>
class Stack
{
private:
    List<T>stack;
public:
    Stack();
    T top();
    void pop();
    bool empty();
    int size();
    void push(T element);

};
template<class T>
Stack<T>::Stack()
{

}
template<class T>
T Stack<T>::top()
{
    return stack.elementAt(stack.size()-1);
}
template<class T>
void Stack<T>::pop()
{
    stack.removeLast();
}
template<class T>
bool Stack<T>::empty()
{
    return (stack.size() == 0);
}
template<class T>
int Stack<T>::size()
{
    return stack.size();
}
template<class T>
void Stack<T>::push(T element)
{
    stack.insertLast(element);
}
#endif