De 5 senaste artiklarna  | Musik/Lastfm Admin /
Skapad: 23:28 - Tisdagen den 19 Februari 2008 / Bloggnummer: 505 / Visad 9062 gånger Senast uppdaterad: 23:28 - Tisdagen den 19 Februari 2008 / Kommentararer är avstängda |
Senaste låtarna som spelades
 | Skolarbeten/Datastrukturer Admin /
Skapad: 20:11 - Tisdagen den 19 Februari 2008 / Bloggnummer: 504 / Visad 7596 gånger Senast uppdaterad: 20:11 - Tisdagen den 19 Februari 2008 / Kommentararer är avstängda |
Heap #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
| Skolarbeten/Datastrukturer Kuhr /
Skapad: 11:41 - Fredagen den 15 Februari 2008 / Bloggnummer: 501 / Visad 7409 gånger Senast uppdaterad: 11:41 - Fredagen den 15 Februari 2008 / Kommentararer är avstängda |
Sortering 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 7527 gånger Senast uppdaterad: 23:27 - Tisdagen den 12 Februari 2008 / Kommentararer är avstängda Taggar: cplusplus |
Stack #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
|