015
13.06.2006, 11:12 Uhr
(un)wissender
Niveauwart
|
So, sollte jetzt laufen.
| C++: |
#include <algorithm>
#include <iostream>
#include <cassert>
struct Knoten;
struct Knoten
{
int a;
Knoten*next;
Knoten*prev;
Knoten(int a)
{
this->a = a;
next = 0;
prev = 0;
}
void chain(Knoten & other)
{
next = &other;
other.prev = this;
}
bool operator<(Knoten const& other) const
{
return a < other.a;
}
void swap(Knoten &other)
{
std::swap(a, other.a);
}
};
class Liste
{
private:
Knoten*first;
Knoten*last;
int number;
Knoten* internal_get(int index) const;
public:
Liste();
~Liste();
void pushFront(int a);
void pushBack(int a);
void popFront();
void popBack();
Knoten* get(int index);
Knoten const* get(int index) const;
int size() const;
bool isEmpty() const;
void sort();
};
std::ostream & operator<<(std::ostream &out, Knoten const& knoten)
{
return
out << "this: " << &knoten << ", a: " << knoten.a << ", prev: "
<< knoten.prev << ", next: " << knoten.next;
}
std::ostream & operator<<(std::ostream &out, Liste const& list)
{
for(int i = 0; i < list.size(); ++i)
{
out << "\nKnoten " << i << '\n' << *list.get(i);
}
return out;
}
Liste::Liste()
{
number=0;
first=0;
last=0;
}
Liste::~Liste()
{
Knoten * current = first;
while(current)
{
Knoten * temp = current->next;
delete current;
current = temp;
}
}
void Liste:: pushFront(int a)
{
if(isEmpty())
{
pushBack(a);
}
else
{
Knoten*p= new Knoten(a);
p->chain(*first);
first = p;
number++;
}
}
void Liste:: pushBack(int a)
{
if(isEmpty())
{
first=new Knoten(a);
last=first;
}
else
{
assert(last);
Knoten*p= new Knoten(a);
last->chain(*p);
last = p;
}
number++;
}
void Liste::popFront()
{
if(isEmpty() || !first->next) return;
Knoten*p=first->next;
delete first;
first=p;
p->prev=0;
number--;
}
void Liste::popBack()
{
if(isEmpty()) return;
Knoten* p =last->prev;
delete last;
p->next=0;
last = p;
number--;
}
Knoten* Liste::internal_get(int index) const
{
if(index >= number) return 0;
Knoten * p = 0;
if(index > number/2)
{
p = last;
for(int i = number - 1; i != index; i--)
{
p = p->prev;
}
}
else
{
p=first;
for(int i = 0; i != index; i++)
{
p=p->next;
}
}
assert(p);
return p;
}
Knoten* Liste::get(int index)
{
return internal_get(index);
}
Knoten const* Liste::get(int index) const
{
return internal_get(index);
}
int Liste::size() const
{
assert(number >= 0);
return number;
}
bool Liste::isEmpty() const
{
return first==0;
}
void Liste::sort()
{
for(int i = 0; i < number - 1; ++i)
{
for(int j = 0; j < number - 1; ++j)
{
Knoten* k1=get(j);
Knoten* k2=get(j+1);
assert(k1);
assert(k2);
if(*k2 < *k1)
{
k1->swap(*k2);
}
}
}
}
int main()
{
Liste MyListe;
MyListe.pushBack(3);
MyListe.pushBack(7);
MyListe.pushBack(1);
MyListe.pushBack(8);
MyListe.pushBack(3);
MyListe.pushBack(2);
std::cout << "Before sort: " << MyListe;
MyListe.sort();
std::cout << "\nAfter sort: " << MyListe;
}
|
--
Wer früher stirbt ist länger tot. |
