removeduplicate

Hi,

habe eine funktion geschreiben um mehrfach vorkommende zeichen zu löschen. kann ich so den pointer übergeben? removeduplicate...
welche laufzeit komplexität habe ich im moment? n^3? kann ich die verbessern?

void deletechar(char *str, char todelete)
{
	bool found = false;

	if(str)
	{
		while(*str != NULL)
		{
			if(*str == todelete)
			{
				found = true;
			}

			if(found == true)
			{
				*str = *(++str);
			}
			else
			{
				str++;
			}
		}
	}
}

void removeduplicate(char *str)
{
	if(str)
	{
		for(int i = 0; i < strlen(str); i++)
		{
			for(int j = i + 1; j < strlen(str); j++)
			{
				if(str[i] == str[j])
				{
					deletechar(str+j, str[j]);
				}
			}
		}
	}
}

Hi, was meint ihr zu diesem algo? Laufzeitkomplexität wäre da n^2 ?

void removeduplicate(char *str)
{
	int found = false;

	if(str)
	{
		for(int i = 0; i < strlen(str); i++)
		{
			found = false;

			for(int j = i + 1; j < strlen(str); j++)
			{
				if(str[i] == str[j])
				{
					str[j] = str[j+1];
					found = true;
				}
			}

			if(found == true)
			{
				i--;
			}
		}
	}
}

SeppJ

Solange du Sachen wie for(int i = 0; i < strlen(str); i++) drin hast, braucht man nicht ernsthaft über Komplexität reden. Da zählt höchstens richtig und falsch. Und richtig ist das nicht. Zum Beispiel ist das Ergebnis von ="Hallo Welt!!" ein "Halo Wet!".

Warum so umständlich? Es gibt nur 256 mögliche Zeichenwerte, da kann man sich locker merken, welche man bereits gefunden hat, und alle auf einmal abkanzeln. Ich denke mir das etwa so:

void remove_duplicates(char *str) {
  unsigned char *dest, *src, found[256] = { 0 };

  for(dest = src = (unsigned char *) str; *src; ++src) {
    if(!found[*src]) {
      *dest++ = *src;
      found[*src] = 1;
    }
  }

  *dest = '\0';
}

Übrigens:

*str = *(++str);

erzeugt undefiniertes Verhalten; der Ausdruck enthält keinen Sequenzpunkt, so dass nicht vorgeschrieben ist, wann genau der Nebeneffekt von ++str (d.h. die Erhöhung von str) eingetreten ist. Insbesondere ist unklar, ob das str auf der linken Seite noch auf die alte oder bereits auf die neue Speicherstelle zeigt.

ich möchte kein zusätzliches array verwenden!

wie findest du diese lösung?

void removeduplicate(char *str)
{
	int pos = 0;

	if(str)
	{
		for(int i = 0; i < strlen(str); i++)
		{
			int j;
			for(j = 0; j < pos; j++)
			{
				if(str[i] == str[j])
				{
					break;
				}				
			}

			if(j == pos)
			{
				str[pos] = str[i];
				pos++;
			}
		}

		str[pos] = 0;
	}
}

Ich halte generell nichts davon, einen Ω(n²)-Algorithmus einem O(n)-Algorithmus vorzuziehen, bloß weil man kein zusätzliches Array verwenden will. Was soll das?