004
17.08.2006, 17:43 Uhr
0xdeadbeef
Gott
(Operator)
|
So, hier dummy-liste zur Verdeutlichung. Die Implementierung eines geeigneten Interfaces bleibt dem Leser als Übungsaufgabe vorbehalten  Das Prinzip sollte jedenfalls klar werden. Die Einfachheit dieses zunächst etwas unintuitiven Sonderfalls ergibt sich daraus, dass deutlich weniger Sonderfälle zu behandeln sind, da z.B. jedes Element immer einen Vorgänger und Nachfolger hat.
| C++: |
#include <iostream>
namespace my {
struct list_element {
int data;
list_element *prev, *next;
list_element(int x) : data(x) { }
};
class list {
public:
list() : head(new list_element(0)), tail(new list_element(0)), size_(0) {
// Dummies initialisieren
head->prev = tail->prev = head;
head->next = tail->next = tail;
}
~list() {
list_element *ptr = head->next;
do {
delete ptr->prev;
ptr = ptr->next;
} while(ptr != tail);
delete tail;
}
::std::size_t size() const { return size_; }
void push_front(int data) {
insert_before(head->next, new list_element(data));
}
void push_back(int data) {
insert_before(tail, new list_element(data));
}
void insert(int pos, int data) {
insert_before(get_node(pos), new list_element(data));
}
int get_data(int pos) {
return get_node(pos)->data;
}
void remove_front() {
remove(head->next);
}
void remove_back() {
remove(tail->prev);
}
void remove_position(int pos) {
if(pos < size()) {
remove(get_node(pos));
} else
throw pos;
}
private:
void insert_before(list_element *anchor, list_element *new_element) {
new_element->prev = anchor->prev;
new_element->next = anchor;
anchor->prev->next = anchor->prev = new_element;
++size_;
}
void remove(list_element *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
--size_;
}
list_element *get_node(::std::size_t pos) {
list_element *ptr = head->next;
for(int i = 0; i < pos; ++i)
ptr = ptr->next;
return ptr;
}
list_element *head, *tail;
::std::size_t size_;
};
}
int main() {
my::list ls;
ls.push_front(10);
ls.push_back(20);
ls.push_front(5);
ls.push_back(30);
ls.insert(2, 12);
ls.insert(3, 13);
ls.insert(2, 11);
for(int i = 0; i < ls.size(); ++i)
std::cout << ls.get_data(i) << " ";
std::cout << std::endl;
ls.remove_front();
ls.remove_back();
ls.remove_position(2);
ls.remove_position(3);
for(int i = 0; i < ls.size(); ++i)
std::cout << ls.get_data(i) << " ";
std::cout << std::endl;
}
|
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra |
,
.
ie Anweisung in XXX verweist auf den Speicher in XXX, der Vorgang read konnte nicht ausgeführt werden ... . :confused: 
