Einordnen von Elementen in eine Liste

mac_bobby

Hallo, schön dass es das Forum hier gibt, vielleicht könnt ihr mir ja auch helfen.

Wir sollen bei uns im Studium aus einer Liste mit ungeordneten Elementen jeweils das erste Element herauslösen und in eine neue Liste lexikographisch einordnen.
Irgendwie habe ich wahrscheinlich einen Denkfehler, denn es funktioniert nicht.
Ich zeige euch mal den gesamten Code, die Funktion 'out_order_in' ist die Funktion wo neu eingeordnet werden kann.

#include<iostream>
#include<string.h>
using namespace std;

struct list {
	list *next;
	char *string;
};

void getlines(list *lines);
void printlines(list *lines, int argc, char **argv);
void out_order_in(list *lines, list *ordered_lines);

int main(int argc, char **argv) {
	list *line = new list;
	list *ordered_line = new list;
	ordered_line = NULL;
	cout << "Es wird eingelesen...";
	getlines(line);
	cout << "[fertig]" << endl;
	cout << "Es wird eingeordnet...";
	out_order_in(line,ordered_line);
	cout << "[fertig]" << endl;
	cout << "Es wird ausgegeben...";
	printlines(ordered_line, argc, argv);
	cout << "[fertig]" << endl;
	//printlines(line, argc, argv);
}

void out_order_in(list *line, list *ordered_line) {

	list *start = new list;
	list *prev = new list;
	start=NULL,prev=NULL;
	while(line!=NULL) {
		list *totakeoff = new list;
		if(ordered_line == NULL) {
			ordered_line = line;
			prev = ordered_line;
			start = ordered_line;
			ordered_line->next = new list;
		}
		else {
			while(ordered_line != NULL) {
				if(strcmp(line->string, ordered_line->string)<0) {
					prev = line;
					line = ordered_line;
					ordered_line = ordered_line->next;
				}
				else if(strcmp(line->string, ordered_line->string)>0) {
					ordered_line = line;
					line = ordered_line->next;
					prev = ordered_line;
				}
			}
		}

		totakeoff = line;
		line = line->next;
		delete totakeoff;
		ordered_line = start;
	}

}

void getlines(list *line) {
	char input[100];
	bool first_line = true;

	while(gets(input)!=NULL) {
		if(first_line==false) {
			line->next = new list;
			line = line->next;
		}
		line->string = (char *)malloc(strlen(input)+1);
		strcpy(line->string,input);
		line->next = NULL;
		first_line = false;
	}
}

void printlines(list *line, int argc, char **argv) {
	if (argc > 1) {
		cout << "\nAusgabe der Suchliste:\n" << endl;
		int list_element = 1;
		while(line!=NULL) {
			if(strstr(line->string,argv[1])) {
				cout << "[" << list_element << "] " << line->string << endl;
			}
			line = line->next;
			list_element++;
		}
	}
	else {
		cout << "\nAusgabe der geordneten Liste:\n" << endl;
		while(line!=NULL) {
			cout << line->string << endl;
			line = line->next;
		}
	}
}

LordJaxom

Du musst Strings mit strcmp vergleichen, mit < vergleichst Du nur die Adressen im Speicher...

if(strcmp(line->string, ordered_line->string)<0)

mac_bobby

OK, danke, aber es geht immernoch nicht, sieht so aus, als ob er jetzt in einer endlosschleife steckt, denn er macht nicht weiter bzw. sehe ich nur einen blinkenden consolencursor !!!

CStoll

Die Funktion ist ein einziger Krampf:
* deine new's sind komplett überflüssig, weil du die entsprechenden Zeiger vor Verwendung wieder überschreibst.
* du iterierst mit 'line' durch die ordered_line - damit dürfte spätestens am Ende des zweiten Schleifendurchgangs die Originalliste futsch sein und du die bisherigen Elemente der ordered_line pausenlos.
* ordered_line soll etwas zurückgeben, da benötigst du Referenzen oder Doppelpointer.
*...

camper

das ist weitestgehend C mit einigen C++ elementen (und ausgerechent denen, die für sich genommen nur geringe vorteile haben - cout,new).
nunja:

#include<iostream>
#include<string.h>
using namespace std;

ok, allerdings, ähm... deprecated... beser:

#include<iostream>
#include<cstring>
using namespace std;

noch besser:

#include<iostream>
#include<string>
using namespace std;

und du verwendest strings und verzichtest auf char-arrays

list *start = new list;
    list *prev = new list;
    start=NULL,prev=NULL;

ich bin mir sicher, du weisst nicht, was du hier tust...

void out_order_in(list *line, list *ordered_line) {

    list *start = new list;
    list *prev = new list;
    start=NULL,prev=NULL;
    while(line!=NULL) {
        list *totakeoff = new list;
        if(ordered_line == NULL) {
            ordered_line = line;
            prev = ordered_line;
            start = ordered_line;
            ordered_line->next = new list;
        }
        else {
            while(ordered_line != NULL) {
                if(strcmp(line->string, ordered_line->string)<0) {
                    prev = line;
                    line = ordered_line;
                    ordered_line = ordered_line->next;
                }
                else if(strcmp(line->string, ordered_line->string)>0) {
                    ordered_line = line;
                    line = ordered_line->next;
                    prev = ordered_line;
                }
            }
        }

        totakeoff = line;
        line = line->next;
        delete totakeoff;
        ordered_line = start;
    }

}

man kann kaum erahnen, was hier passieren soll... der sinn von prev bleibt jedenfalls im dunkeln, denn genutzt wird es nie
im übrigen besteht hier auf jedenfall die chance einer endlos schleife, falls du zwei gleiche einträge hast, denn dann ist weder

if(strcmp(line->string, ordered_line->string)<0) {

noch

else if(strcmp(line->string, ordered_line->string)>0) {

zutreffend (bzw. selbiges falls line und odered_line zufällig mal gleich sind). andererseits ist das sowieso UB, denn:

ordered_line = line;
// ...
            ordered_line->next = new list;
// ...
        line = line->next;

und im nächsten durchgang verwendest du fröhlich line->string, obwohl nichts initialisiert wurde.

while(gets(input)!=NULL) {

gets ist böse, richtig, richtig böse...