3. Lexikographische Sortierung

Lexikographische Sortierung

  • L

    Hallo,

    in meinem Blockkurs C++ lehrt uns der Prof mehr C als C++ (ich hab C++ schonmal gelernt, aber halt cin/cout/STL usw...). Ich hatte ein Problem bei einem Programm, welches 20 Strings einlesen und sie lexikographisch sortiert wieder ausgeben sollte. Ich hab es ins C-Forum gestellt, aber dort antwortet niemand. Hier wird immer schneller geantwortet(ich hab auch das Gefühl, dass hier kompetentere Leute sitzen). Deshalb wollt ich meinen Code hier posten:

    //zeichenlesen.cpp
#include <cstdio>
#include <cstring>

int main(){
	const int n = 5;	
	char eingabe[n][10];

	for(int i = 0; i < n; i++){
		printf("Bitte geben Sie das %i.te Wort ein: ",i+1);
		scanf("%s",&eingabe[i][0]);
	}

	printf("\nSie haben folgende Wörter eingegeben: \n");
	printf("[");
	for(int i = 0; i < n; i++){
		printf("%s",&eingabe[i][0]);
		if(i != n-1)printf(", ");
		else printf("]\n");
	}

	//lexikalische Sortierung
	char tmp;
	int x = n;
	do{
		for(int i = 0; i < n-1; i++){
			if(strcmp(&eingabe[i][0], &eingabe[i+1][0]) > 0){
				tmp = eingabe[i+1][0];
				eingabe[i+1][0] = eingabe[i][0];
				eingabe[i+1][0] = tmp;
			}
		}
	} while(x--);

	//lexikographisch sortierte Ausgabe
	printf("\nLexikographisch sortiert:\n");
	for(int j = 0; j < n; j++) printf("%s\n",&eingabe[j][0]);

	return 0;
}

    Folgende Ausgabe entsteht:

    Bitte geben Sie das 1.te Wort ein: Hallo
Bitte geben Sie das 2.te Wort ein: Welt
Bitte geben Sie das 3.te Wort ein: mir
Bitte geben Sie das 4.te Wort ein: ist
Bitte geben Sie das 5.te Wort ein: schlecht

Sie haben folgende Wörter eingegeben: 
[Hallo, Welt, mir, ist, schlecht]

Lexikographisch sortiert:
Hallo
Welt
mir
ist
schlecht

    Wo liegt mein Fehler?

    0
  • ?

    lil_pingu schrieb:

    Wo liegt mein Fehler?

    Du vertauschst nicht richtig

    Die folgenden Zeilen müsstest du nochmal überarbeiten. Du verarbeitest immer nur das erste Zeichen und außerdem hast du einen kleinen Fehler bei der Zuweisung, der dazu führt, dass sich gar nichts tut. 😉

    char tmp;
// ...
tmp = eingabe[i+1][0];   
eingabe[i+1][0] = eingabe[i][0];
eingabe[i+1][0] = tmp; // !!!!!!!!!!!!!!!!!!

    Ein paar Tipps:

    - mit eingabe[0], eingabe[1], ... sprichst du bereits die Zeichenketten an

    - um eine 10 Zeichen lange Zeichenkette aufzunehmen braucht es auch ein entsprechendes tmp, also char tmp[10]

    - sieh dir mal die Funktion strcpy an, denn oben vertauschst du nur ein Zeichen (fast!)

    0
  • L

    Ok, hab nun meinen Code verändert: DIe Zeichenketten immer direkt angesprochen und strcpy benutzt, aber die Zeichenketten werden immernoch nicht sortiert:

    //zeichenlesen.cpp
#include <cstdio>
#include <cstring>

int main(){
	const int n = 5;	
	char eingabe[n][10];

	for(int i = 0; i < n; i++){
		printf("Bitte geben Sie das %i.te Wort ein: ",i+1);
		scanf("%s",eingabe[i]);
	}

	printf("\nSie haben folgende Wörter eingegeben: \n");
	printf("[");
	for(int i = 0; i < n; i++){
		printf("%s",eingabe[i]);
		if(i != n-1)printf(", ");
		else printf("]\n");
	}

	//lexikalische Sortierung
	char tmp[10];
	int x = n;
	do{
		for(int i = 0; i < n-1; i++){
			if(strcmp(eingabe[i], eingabe[i+1]) > 0){
				strcpy(tmp,eingabe[i+1]);
				strcpy(eingabe[i+1],eingabe[i]);
				strcpy(eingabe[i],tmp);
			}
		}
	} while(x--);

	//lexikographisch sortierte Ausgabe
	printf("\nLexikographisch sortiert:\n");
	for(int j = 0; j < n; j++) printf("%s\n",eingabe[j]);

	return 0;
}
    0
  • ?

    lil_pingu schrieb:

    Ok, hab nun meinen Code verändert: DIe Zeichenketten immer direkt angesprochen und strcpy benutzt, aber die Zeichenketten werden immernoch nicht sortiert

    Sie werden sehr wohl sortiert, nur anders alst du erwartest. Im ASCII Zeichensatz haben Groß- und Kleinbuchstaben unterschiedliche Positionen, daher gilt z.B. A < W < a

    Wenn du zwischen Groß- und Kleinbuchstaben nicht unterscheiden willst, dann hilft z.B. eine Umwandlung vor dem Vergleich, wobei die Originalzeichenketten unberührt bleiben.

    char tmp[10];
char s1[10];
char s2[10];

    int x = n;
    do{
        for(int i = 0; i < n-1; i++){
            // hier wird s1 zu engabe[i] 
            // hier wird s2 zu eingabe[i+1]
            if(strcmp(s1, s2) > 0){
                strcpy(tmp,eingabe[i+1]);
                strcpy(eingabe[i+1],eingabe[i]);
                strcpy(eingabe[i],tmp);
            }
        }
    } while(x--);

    Wieder ein Tipp:

    - Es gibt in C die Funktionen tolower() und toupper()

    char s1[10]
for( i = 0; s1[i]; ++i)
    s1[i] = toupper( s1[i]);

    Würde die Zeichen von s1 in Großbuchstaben umwandeln, falls möglich.

    0
  • ?

    P.S.:

    Vielleicht könntest du dir auch ein eigenes strcmp() schreiben, welches auf Groß- und Kleinbuchstaben Rücksicht nimmt. War vielleicht sogar die Intention des Professors, dass ihr das selbst macht.

    0

  • Mitleid schrieb:

    P.S.:

    Vielleicht könntest du dir auch ein eigenes strcmp() schreiben, welches auf Groß- und Kleinbuchstaben Rücksicht nimmt. War vielleicht sogar die Intention des Professors, dass ihr das selbst macht.

    Wenn´s das nicht schon gibt... guck dir mal stricmp() an.

    0
  • ?

    DocShoe schrieb:

    Wenn´s das nicht schon gibt... guck dir mal stricmp() an.

    Du meinst _stricmp() und wir wissen ja alle was dieses _ bedeutet. 😉

    0

  • Nö, ich meine stricmp, das ist sowohl ANSI-C als auch ANSI-C++ Standard.

    0
  • ?

    OK, das glaub ich dir mal, ohne es überprüft zu haben. Dann passt ja alles. 😃

    0
  • ?

    DocShoe schrieb:

    Nö, ich meine stricmp, das ist sowohl ANSI-C als auch ANSI-C++ Standard.

    Hab nochmal drüber nachgedacht. Hast du einen Nachweis dafür bzw. in welchem Paper steht das?

    0
  • ?

    Nun? Doc?

    Nach kurzer Recherche denke ich deine Aussage bezüglich stricmp() ist nicht zu halten. Das Ding gehört nicht zum Standard. Trotzdem würde es lil_pingu die Arbeit abnehmen, das zumindest ist gewiss.:)

    0

  • Und unter Linux/gcc heißt die Funktion dann strcasecmp() (http://linux.die.net/man/3/strcasecmp).

    Leider ist stricmp/strcasecmp aber kein Standard (auch nicht mit Unterstrich).

    0
  • L

    So, hab nun das Problem gelöst.

    //zeichenlesen.cpp
#include <cstdio>
#include <cstring>
#include <cctype>

int main(){
	const int n = 5;	
	char eingabe[n][10];

	for(int i = 0; i < n; i++){
		printf("Bitte geben Sie das %i.te Wort ein: ",i+1);
		scanf("%s",eingabe[i]);
	}

	printf("\nSie haben folgende Wörter eingegeben: \n");
	printf("[");
	for(int i = 0; i < n; i++){
		printf("%s",eingabe[i]);
		if(i != n-1)printf(", ");
		else printf("]\n");
	}

	//lexikalische Sortierung
	char tmp[10];
	char s1[10];
	char s2[10];
	int x = n;
	do{
		for(int i = 0; i < n-1; i++){
			strcpy(s1,eingabe[i]);
			strcpy(s2,eingabe[i+1]);			

			//alles in Großbuchstaben umformen
			for(int k = 0; s1[k] != '\0'; ++k) 
				s1[k] = (char)toupper(s1[k]);
			for(int k = 0; s1[k] != '\0'; ++k) 
				s2[k] = (char)toupper(s2[k]);

			if(strcmp(s1, s2) > 0){
				strcpy(tmp,eingabe[i]);
				strcpy(eingabe[i],eingabe[i+1]);
				strcpy(eingabe[i+1],tmp);
			}
		}
	} while(x--);

	//lexikographisch sortierte Ausgabe
	printf("\nLexikographisch sortiert:\n");
	for(int j = 0; j < n; j++) printf("%s\n",eingabe[j]);

	return 0;
}

    Bitte geben Sie das 1.te Wort ein: Zickzack
Bitte geben Sie das 2.te Wort ein: X-Men
Bitte geben Sie das 3.te Wort ein: Mama
Bitte geben Sie das 4.te Wort ein: Hiho
Bitte geben Sie das 5.te Wort ein: jura

Sie haben folgende Wörter eingegeben: 
[Zickzack, X-Men, Mama, Hiho, jura]

Lexikographisch sortiert:
Hiho
jura
Mama
X-Men
Zickzack

    Hab heute übrigens mit meinem Prof geredet und gesagt, dass es mich verdammt stört, dass wir darauf ausdrücklich hingewiesen werden, alles C-like zu machen. Hab ihm gesagt, wie schnell die Lösung mit <string> und <vector> gehen würde. Er meinte, wir sollen das so machen, um uns mit C-Strings vertraut zu machen (was ich einerseits verstehen kann, denn das ist wirklich etwas schwieriger als string). Aber trotzdem ist es nicht gut, streams, stl, usw nicht richtig zu erklären. Als er heute kurz mal eine cout-Ausgabe (mit Namespace-Prefix) zeigte, wurden alle ganz panisch...Als ich damals für ein Praktikum C++ lernen musste, habe ich mich auch tagelang damit rumgequält, die STL zu verstehen, weil meine C++-Lektüre auch im C-Stil war...hab dann im Forum um Rat gebeten und man hat mir die beiden Vols von "Thinking in C++" empfohlen. Die sind wirklich genial! 🙂

    0
  • ?

    *räusper* *hüstel*

    //...
for(int k = 0; s1[k] != '\0'; ++k)
    s1[k] = (char)toupper(s1[k]);

for(int k = 0; s1[k] != '\0'; ++k) // !!!!!!!!!!
    s2[k] = (char)toupper(s2[k]);
//...
    0
  • L

    Mitleid schrieb:

    *räusper* *hüstel*

    //...
for(int k = 0; s1[k] != '\0'; ++k)
    s1[k] = (char)toupper(s1[k]);

for(int k = 0; s1[k] != '\0'; ++k) // !!!!!!!!!!
    s2[k] = (char)toupper(s2[k]);
//...

    Was ist damit? Es hat bei mir nicht rumgemeckert...

    0
  • U

    lil_pingu schrieb:

    Mitleid schrieb:

    *räusper* *hüstel*

    //...
for(int k = 0; s1[k] != '\0'; ++k)
    s1[k] = (char)toupper(s1[k]);

for(int k = 0; s1[k] != '\0'; ++k) // !!!!!!!!!!
    s2[k] = (char)toupper(s2[k]);
//...

    Was ist damit? Es hat bei mir nicht rumgemeckert...

    gucks doch noch mal an... 😛

    0
  • L

    😮 😮 😮 oje, ich sehs. In der zweiten for-Schleife muss s2[k] != ... stehen...Danke für den Hinweis 👍 😋

    0
  • M

    Muhaha, sehr witzig hier Leute schreiben zu sehen, mit denen ich zusammen diesen C++ Kurs gerade mache. Ich habe diese Aufgabe auch bearbeitet, aber auf vorgefertigte Funktionen zu Übungszwecken verzichtet. Ich bin übrigens der Meinung, dass die starke C-Orientierung im Kurs viel Sinn macht. Die Grundlagen müssen zuerst sitzen, dann kann man auch gerne zur STL greifen.

    #include <cstdio>

int strlen(const char * string)
{
	for(int i = 0;; ++i)
	{
		if(string[i] == '\n' || string[i] == '\0')
		{
			return i;
		}
	}
}

// Alphabetischer Char Vergleich: a > b -> 1 / a < b = -1 / a == b = 0
// Zahlen und Sonderzeichen sind kleiner als Buchstaben
int cmp(char a, char b)
{
	bool a_letter = false;
	bool b_letter = false;

	// Gross -> Klein
	if(a < 91 && a > 64)
	{
		a += 32; a_letter = true;
	}
	if(a < 123 && a > 96)
		a_letter = true;

	if(b < 91 && a > 64)
	{
		b += 32; b_letter = true;
	}
	else if(b < 123 && b > 96)
		b_letter = true;

	if(a_letter && b_letter)
	{
		if(a > b) return 1;
		else if(a == b) return 0;
		else return -1;
	}
	else if(a_letter && !b_letter)
		return 1;
	else if(!a_letter && b_letter)
		return -1;
	else
	{
		if(a == b) return 0;
		return (a > b) ? 1 : -1;
	}
}

// Char[] Vergleich: a > b -> true
bool strcmp(char * a, char * b)
{
	int compare;
	int la = strlen(a);
	int lb = strlen(b);
	int l = (la > lb) ? lb : la;

	for(int i = 0; i < l; ++i)
	{
		compare = cmp(a[i], b[i]);
		if(compare == 1)
		{
			return true;
		}
		else if(compare == -1)
		{
			return false;
		}
	}

	return (lb <= la) ? true : false;
}

int partition(int links, int rechts, char ** words)
{
	char * tmp;
    int i = links; 
    int j = rechts - 1;

	do
	{
		while(strcmp(words[rechts], words[i]) && i < rechts) i++; 
		while(strcmp(words[j], words[rechts]) && j > links) j--;

		if(i < j)
		{
			tmp  = words[i];
			words[i] = words[j];
			words[j] = tmp;
			j--;
			i++;
		}
	}
	while(i < j);

	if(strcmp(words[i],words[rechts]))
	{
		tmp  = words[i];
		words[i] = words[rechts];
		words[rechts] = tmp;
	}

	return i;
}

void qsort(int links, int rechts, char ** words)
{
	if(links < rechts)
	{
         int teiler = partition(links, rechts, words);
         qsort(links, teiler-1, words);
		 qsort(teiler+1, rechts, words);
	}
}

int main()
{
	int n = 8;
	int i;
	char ** words = new char*[n];

	for(i = 0; i < n; ++i)
	{
		words[i] = new char[20];
	}

	for(i = 0; i < n; ++i)
	{
        printf("Bitte geben Sie das %i. Wort ein: ",i+1);
        if(fgets(words[i], 20, stdin) == NULL)
		{
			printf("Fehler beim Einlesen!\n");
			return 1;
		}
    }

	qsort(0, (n-1), words);

	printf("Lexikografische Ausgabe:\n");
	for(i = 0; i < n; i++)
	{
		printf("%s",words[i]);
		delete words[i];
	}

	delete words;
}
    0
  • U

    Ich bin übrigens der Meinung, dass die starke C-Orientierung im Kurs viel Sinn macht.

    Die Diskussion hatten wir hier schon ca. 82938mal - es gibt da wohl mehrere ansichten - ich weiß allerdings nicht, wieso man als C++ Anfänger char*-gefrickel vor std::string erlernen sollte...

    Michamab schrieb:

    Ich habe diese Aufgabe auch bearbeitet, aber auf vorgefertigte Funktionen zu Übungszwecken verzichtet.

    auch hier lässt sich über den Sinn streiten - allerdings ist es zumindest nicht unnötig...

    Die Grundlagen müssen zuerst sitzen, dann kann man auch gerne zur STL greifen.

    siehe 1.

    int strlen(const char * string)
{
	for(int i = 0;; ++i)
	{
		if(string[i] == '\n' || string[i] == '\0')
		{
			return i;
		}
	}
}

    '\n' hat nichts darüber auszusagen, ob ein string zu ende ist...
    Bsp.: "Hallo\r\nWelt!"

    richtiger wäre:

    int strlen(const char *str)
{
  int R;

  for(R = 0; str[R] != '\0'; ++R)
    ;

  return R;
}

    (nebenbemerkung:
    nur ist es in C++ nicht üblich, int für einen zähler zu nutzen - hier nimmt man std::size_t:

    size_t strlen(const char *str)
{
  size_t R(0);

  if(str[R] != '\0')
    return R;

  while(str[++R] != '\0')
    ;

  return R;
}

    hab auch keine ahnung, ob es was gebracht hat, das for mit dem if+while zu ersetzen)

    warum es nicht sonderlich klug ist, auf vorgefertigte fkt zu verzichten wird auch hier wieder klar: es muss eben nicht immer funktionieren... es wird zwar auf PCs funktionieren, aber ist nicht festgeschrieben, dass a..z direkt nacheinander kommen - auch bei A..Z nicht.
    normalerweise müsste man das wohl mit riesen switch-blöcken machen müssen...
    schrecklich ist vor allem, dass du die ascii-werte nimmst - völlig unnötig...

    char is_letter(char character)
{
  return is_lower(character) || is_upper(character);
}

bool is_lower(char buchstabe)
{
  return buchstabe >= 'a' && buchstabe <= 'z';
}

bool is_upper(char buchstabe)
{
  return buchstabe >= 'A' && buchstabe <= 'Z';
}

char to_lower(char buchstabe)
{
  if(is_lower(buchstabe))
    return buchstabe;

  return buchstabe-'A'+'a';
}

// Alphabetischer Char Vergleich: a > b -> 1 / a < b = -1 / a == b = 0
// Zahlen und Sonderzeichen sind kleiner als Buchstaben
int cmp(char a, char b)
{
  if(is_letter(a) && is_letter(b))
  {
    a = to_lower(a);
    b = to_lower(b);
    if(a == b)
      return 0;
    return a > b ? 1 : -1;
  }

  if(!is_letter(b))
  {
    if(is_letter(a))
      return 1;

    if(a == b)
      return 0;
    return a > b ? 1: -1;
  }

  return -1; //bleibt nur noch !is_letter(a) && is_letter(b) übrig
}

    bool strcmp(char * a, char * b)
    wie wärs mit
    bool strcmp(const char *a, const char *b) ?
    oben hast du doch auch noch const char* genommen und nicht char*...

    // Char[] Vergleich: a > b -> true
bool strcmp(const char *a, const char *b)
{
  for(int i(0), e(strlen(a)); i != e; ++i)
  {
    bool same( cmp(a++, b++) == 0 );
    if(!same)
      return false;
  }

  return true;
}

    zu mehr hab ich gerade keine lust - vll kommt später noch mehr^^

    man könnte auch noch mehr auslagern - z.bsp. eine fkt:

    bool is_delimiter(char x)
{
  return x == '\0';
}

    bei strlen verwenden.
    bei strcmp könnte man dann auch auf das strlen verzichten und die fkt nehmen...
    man könnte auch jz schon auf strlen verzichten, aber hässlich, wie ich finde^^
    ich will in nem strcmp nicht unbedingt selbst auf '\0' testen sondern wenn ich teste, will ich die '\0' dort weghaben...

    bb

    0
  • V

    unskilled schrieb:

    Ich bin übrigens der Meinung, dass die starke C-Orientierung im Kurs viel Sinn macht.

    Die Diskussion hatten wir hier schon ca. 82938mal - es gibt da wohl mehrere ansichten - ich weiß allerdings nicht, wieso man als C++ Anfänger char*-gefrickel vor std::string erlernen sollte...

    Damit er keine häßliche Kacke baut.

    Um genau zu sein, damit

    unskilled schrieb:

    // Char[] Vergleich: a > b -> true
bool strcmp(const char *a, const char *b)
{
  for(int i(0), e(strlen(a)); i != e; ++i)
  {
    bool same( cmp(a++, b++) == 0 );
    if(!same)
      return false;
  }

  return true;
}

    sowas nicht passiert. Boah, ey, ist das häßlich!

    0
Anmelden zum Antworten