strings in verketteten listen lexikalisch ordnen

funny

hallo,
ich möchte strings per strcmp vergleichen und entsprechend innerhalb einer verketteten liste lexikalisch sortieren, wie geht sowas? habe bisher nur etwas über sortieren innerhalb von arrays gelesen.

funny

hab da eine idee:
neue liste erstellen, 1. element von gegebener liste einkopieren, nächstes element sortiert einkopieren ( vergleich mit strcmp ) usw. bis alle elemente übertragen sind. neue liste zurückgeben.
ist das ok so oder gehts auch einfacher?

mata

also entweder kannst du halt direkt beim einfügen sortieren (so wie du das beschrieben hast), oder du schaust dir mal n paar sortieralgorithmen an, vielleich zum anfang mal bubblesort, der vergleicht immer nur elemente, die nebeneinander stehen und tauscht die dann, das is ja in ner liste auch nicht viel schwieriger zu realisieren. du kannst jeden algo, den du auf arrays anwenden kannst natürlich auch auf listen anweden, da musst du dann anstatt elemente im array zu tauschen die pointer umhängen.

muss man da nicht rekursiv zeichen vergleichen, falls die beiden ersten buchstaben übereinstimmen, so das z. B. Otto nach Ottfried eingeordnet wird?

Vielleicht ne kleine Hilfe, hihi

GradNichtRegistriert schrieb:

muss man da nicht rekursiv zeichen vergleichen, falls die beiden ersten buchstaben übereinstimmen, so das z. B. Otto nach Ottfried eingeordnet wird?

Vielleicht ne kleine Hilfe, hihi

Sollte das nicht strcmp erledigen?

Brauchst du denn unbedingt eine Verkettete Liste, oder geht auch ein Array mit Pointern auf Strings?
Ansonsten wie gesagt, einfach mit Bubblesort per strcmp die Liste durchgehen.

funny

problem ist nur, daß beliebig viele, beliebig lange strings in der verketteten liste sind. muß da irgendwie mit index arbeiten, damit ich nicht den überblick verliere, wo schon sortiert ist und wo nicht.das ist,was ich bisher habe, fehlt halt nur noch die funktion stringBuffer* stringBufferSort(stringBuffer*).

typedef struct stringBufferElement {
	char* line;
	struct stringBufferElement* next;
} stringBufferElement;

typedef struct stringBuffer {
	struct stringBufferElement* first;
	struct stringBufferElement* last;
	int numberOfNextElement;
} stringBuffer;

/*extern void yyerror(char* msg);*/

stringBuffer* newStringBuffer() {
	stringBuffer* temp = (stringBuffer*) malloc(sizeof(stringBuffer));
	temp->numberOfNextElement = 0;
	temp->first = 0;
	temp->last = 0;
	return temp;
}

void stringBufferAppend(stringBuffer* buffer, char* text) {
	stringBufferElement* newElement = (stringBufferElement*) malloc(sizeof(stringBufferElement));
	newElement->line = strdup(text);
	newElement->next = 0;

	if (buffer->last != 0) buffer->last->next = newElement;
	else buffer->first = newElement;
	buffer->last = newElement;
	buffer->numberOfNextElement++;
}

void stringBufferInsert(stringBuffer* buffer, int address, char* text) {
	stringBufferElement* newElement;
	stringBufferElement* elem;
	int i;

	newElement = (stringBufferElement*) malloc(sizeof(stringBufferElement));
	newElement->line = strdup(text);
	if (address == 0) {
		newElement->next = buffer->first;
		buffer->first = newElement;
	}
	else {
		elem = buffer->first;
		for (i=0; i<address-1; i++) {
			if (elem->next != 0) elem = elem->next;
			else ;/*yyerror("inserting address in stringbuffer to large (compiler-intern error).\n");
	*/	}
		newElement->next = elem->next;
		elem->next = newElement;
	}
	buffer->numberOfNextElement++;
}

void stringBufferConcatenate(stringBuffer* buf1, stringBuffer* buf2) {
	if (buf2->first == 0) return;
	buf1->last->next = buf2->first;
	buf1->last = buf2->last;
	buf1->numberOfNextElement = buf1->numberOfNextElement + buf2->numberOfNextElement;
	free(buf2); /* XXX */
}

void stringBufferSort(stringBuffer*){}

void stringBufferPrint(stringBuffer* buffer) {
	stringBufferElement* elem = buffer->first;
	if (elem == 0) {
		printf("empty buffer\n");
		return;
	}
	while (elem->next != 0) {
		printf("%s\n", elem->line);
		elem = elem->next;
	}
	printf("%s\n", elem->line);
}