Doppelverkettetes Array Plätze tauschen

lima-city → Forum → Programmiersprachen → C/C++ und D

Autor dieses Themas

~~g****e~~

18:53, 4.6.2013

Juten Abend,
Ich habe einen Hirnknoten und komm einfach nicht weiter...
Ich habe ein Doppelt verkettetes Array, in welchem ich 2 Plätze tauschen möchte. Hier mal ein bisschen Code, damit ihr die doppelt verkettete Liste nachvollziehen könnt, erstmal das Listenelement:

template<class T>
class ListenElement {
public:
    ListenElement<T>();
    ~ListenElement<T>();
    
    ListenElement<T> *next;
    ListenElement<T> *prev;
    T inhalt;
};

#pragma once
#include "ListenElement.h"

template<class T>
ListenElement<T>::ListenElement() {
    this->next = 0;
    this->prev = 0;
}

template<class T>
ListenElement<T>::~ListenElement() {
    
}

Die Liste:

#include "ListenElement.cpp"

template<class T>
class Liste {
public:
    Liste();
    ~Liste();
    
    void Add(T);
    
    ListenElement<T> *erstesElement;
};

#pragma once
#include "Liste.h"
#include "ListenElement.cpp"

template<class T>
Liste<T>::Liste() {
    this->erstesElement = 0;    
}

template<class T>
Liste<T>::~Liste() {
    
}

template<class T>
void Liste<T>::Add(T neuerInhalt) {
    ListenElement<T> *neuesElement = new ListenElement<T>();
    neuesElement->inhalt = neuerInhalt;
    if (this->erstesElement == 0)
        this->erstesElement = neuesElement;
    else {
        ListenElement<T> *tmp = this->erstesElement;
        while(tmp->next != 0)
            tmp = tmp->next;
        tmp->next = neuesElement;
        tmp->next->prev = tmp;
    }
}

Und zu guter letzt die main.cpp:

#include <iostream>
#include <string>
#include "Liste.cpp"

using namespace std;

int main() {
    Liste<int*> list;
    list.Add(new int(1));
    list.Add(new int(3));
    list.Add(new int(2));
    list.Add(new int(4));
    
    cout<<"press q and enter to exit";
    string quit;
    cin>>quit;
    return 0;
}

So, nun seht ihr viel Code und habt schon den Tab geschlossen. Für die mutigen weiterleser: Ursprünglich wollt ich Bubbelsort nochmal in den Kopf bringen. Bubblesort selbst ist kein Problem, wenn ich aber in diesem Hintergrund das zweite und das dritte Element tauschen möchte, mit einer doppelt verketteten Liste bin ich aufgeschmissen. Ich kann mir einfach nicht merken, welchen Zeiger ich wann wie setzen muss, um alle zu behalten... Darum hoffe ich darauf, dass mir hier jemand das Tauschen dieser beiden Elemente evtl mal aufzeigen kann, oder vllt auch einfach einen Bubblesort für INT schreibt, um einen Kontext zu haben, einfach, damit ich sehe, wie ich die richtig tausche.

Liebe Grüße

Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage

hackyourlife

Moderator

hackyourlife hat kostenlosen Webspace.

19:48, 4.6.2013

Mehrere Dinge:

1) NIE eine .cpp per include einbinden!
2) Da deine Liste einen »Kopf« hat vermeidest du eine sehr interessante Eigenheit beim Sortieren.
3) Der Bubblesort für ein int-array (in C):

void bubblesort(int* array, const unsigned int size) {
	char done = 0;
	int tmp;
	unsigned int i;
	while(!done) {
		done = 1;
		for(i = 0; i < (size - 1); i++) {
			if(array[i] > array[i + 1]) {
				done = 0;
				tmp = array[i];
				array[i] = array[i + 1];
				array[i + 1] = tmp;
			}
		}
	}
}

4) Ich liefere dir eine fertige Liste, in C und ohne einem Listenkopf, also nur mit Listenelementen, weil ich zu faul bin dir den Rest entsprechend »aufzubereiten«. Hoffentlich kannst du dennoch die Funktionsweise erkennen.

list.h

#ifndef __LIST_H__
#define __LIST_H__

struct __ListEntry {
	struct __ListEntry*	next;
	struct __ListEntry*	prev;
};

typedef struct __ListEntry ListEntry;

void LIST_init(ListEntry* list);
void LIST_add(ListEntry* data, ListEntry* list);
void LIST_remove(ListEntry* list);
ListEntry* LIST_sort(ListEntry* list, int (*sortcb)(const void*, const void*));
int LIST_empty(ListEntry* list);
ListEntry* LIST_next(ListEntry* list);
ListEntry* LIST_prev(ListEntry* list);

#endif

list.c

#include "list.h"

void LIST_init(ListEntry* list) {
	list->next = list;
	list->prev = list;
}

void LIST_add(ListEntry* data, ListEntry* list) {
	ListEntry* n = list->next;
	list->next = data;
	data->next = n;
	data->prev = list;
}

void LIST_remove(ListEntry* data) {
	ListEntry* n = data->next;
	ListEntry* p = data->prev;
	p->next = n;
	n->prev = p;
}

int LIST_empty(ListEntry* list) {
	return list->next == list;
}

ListEntry* LIST_sort(ListEntry* list, int (*sortcb)(const void*, const void*)) {
	int e = 1, first;
	ListEntry* c;
	ListEntry* n;
	ListEntry* n2;
	ListEntry* p;
	ListEntry* s = list;
	while(e) {
		e = 0;
		first = 1;
		for(c = s; c->next != s || first; first = 0) {
			n = c->next; // next
			p = c->prev; // previous
			n2 = n->next; // next next
			if(sortcb((const void*)c, (const void*)n) > 0) {
				p->next = n, n->prev = p;
				n->next = c, c->prev = n;
				c->next = n2, n2->prev = c;
				e = 1;
				if(c == s)
					s = n;
			} else
				c = c->next;
		}
	}
	return s;
}

ListEntry* LIST_next(ListEntry* list) {
	return list->next;
}

ListEntry* LIST_prev(ListEntry* list) {
	return list->prev;
}

demo.c

#include <malloc.h>
#include <stdio.h>

#include "list.h"

typedef struct {
	ListEntry	list;
	char		name[32];
} ENTRY;


int listsort(const void* a, const void* b) {
	//printf("s(%s)\n", ((ENTRY*)a)->name);
	return strcasecmp(((ENTRY*)a)->name, ((ENTRY*)b)->name);
}

int main(int argc, char** argv) {
	ENTRY entries[5] = {
		{ .name = "EINS" },
		{ .name = "ZWEI" },
		{ .name = "DREI" },
		{ .name = "VIER" },
		{ .name = "FUENF" }
	};

	LIST_init((ListEntry*)entries);
	int i;
	for(i = 1; i < sizeof(entries) / sizeof(ENTRY); i++)
		LIST_add((ListEntry*)&entries[i], (ListEntry*)&entries[i - 1]);

	ENTRY* current;
	int first = 1;
	for(current = entries; current != entries || first; current = (ENTRY*)current->list.next, first = 0) {
		printf("%s\n", current->name);
	}

	ENTRY* start = (ENTRY*)LIST_sort((ListEntry*)entries, listsort);

	printf("sorted:\n");
	first = 1;
	for(current = start; current != start || first; current = (ENTRY*)current->list.next, first = 0) {
		printf("%s\n", current->name);
	}

	// free list
	for(current = (ENTRY*)start->list.next; current != (ENTRY*)current->list.next; current = (ENTRY*)current->list.next)
		LIST_remove((ListEntry*)current);

	return 0;
}

Autor dieses Themas
~~g****e~~
20:45, 4.6.2013
Du hast leider total verfehlt, was ich wollte :-S aber erstmal:

hackyourlife schrieb:
1) NIE eine .cpp per include einbinden!

Doch. Das muss sogar so sein. Binde ich nicht die cpp ein kann nicht mit den Templates gearbeitet werden. Probiers aus

Es ging auch nicht um den Bubblesort speziell, der ist kein Problem. Es ging darum in der verketteten Liste die Elemente zu sortieren (Klassen stehen oben, C++ halt).
Ich bin unsicher, wie ich die ListenElemente richtig tausche:
```
void Liste::BubbleSort(std::function(bool<T,T>) compare) {
  bool isSorted = false;
  while(!isSorted) {
    isSorted = true;
    ListenElement<T> *tmp = this->erstesElement;
    while (tmp->next != 0) {
      if ( !compare(tmp, tmp->next ) {
        // tmp ist größer als tmp->next, also tauschen
        isSorted = false;
      }
    }
  }  
}
```
Ist jetzt mal die einfachste Variante. Wie ich tmp und tmp->next tausche hab ich allerdings wenig Idee. Auf anhieb:
```
ListenElement<T> *tmpE1 = tmp;
ListenElement<T> *tmpE2 = tmp->next;
ListenElement<T> *tmpE1p = tmp->prev;
ListenElement<T> *tmpE2p = tmp;
ListenElement<T> *tmpE1n = tmp->next;
ListenElement<T> *tmpE2n = tmp->next->next;
tmpE1->next = tmpE2n;
tmpE1->prev = tmpE1p;
tmpE2->next = tmpE2p;
tmpE2->prev = tmpE1p;
```
Aber das ist doch viiiiel zu umständlich, und ich seh einfach nicht richtig, wie ich das zusammen fassen kann, ohne alle möglichen Adressen zwischen zu speichern.
Dafür brauch ich eine zusammenfassende Idee :-S
Ich hoffe jetzt ist klarer, was ich meine.

Liebe Grüße

Edit: Mein Fehler, stimmt. Wenn man genau hinschaut, und es versteht, steht es bei dir in der list.c Zeile 38 beginnent, was ich meine. Das ist doch einfach umständlich^^ wer hat das nur erfunden, dafür gibts doch vectoren... Doofes Studium. Danke :)

Beitrag zuletzt geändert: 4.6.2013 21:33:26 von ggamee
darkpandemic

darkpandemic hat kostenlosen Webspace.

2:53, 8.6.2013

ggamee schrieb:
Du hast leider total verfehlt, was ich wollte :-S aber erstmal:

hackyourlife schrieb:
1) NIE eine .cpp per include einbinden!

Doch. Das muss sogar so sein. Binde ich nicht die cpp ein kann nicht mit den Templates gearbeitet werden. Probiers aus

So leid es mit tut das sagen zu müssen, aber hackyourlife hat recht. Wenn Du die cpp-Datei inkludieren musst, dann hast Du Mist gebaut. Templates implementiert man nämlich in Header-Files wenn sie in mehr als einem Modul verwendet werden sollen.
Daher gibt es in C++ ja Header und Module, damit man das auseinander halten kann.
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

lima-city bietet dir kostenlosen und werbefreien Speicherplatz für Deine Homepage. Sofort anmelden und direkt loslegen mit Webspace, PHP, Datenbanken, günstigen Domains und einer tollen Community!

kostenloser Webspace werbefrei: lima-city