[C] Funktion zum Suchen schreiben [eilt, da für Schule]

HansGeorg

Hallo,

ich bin auf einer Informatikschule und nun haben wir folgenden Auftrag bekommen. Wir sollen eine Funktion schreiben (int anzahl(char * suchbegriff, char * suche))

Diese Funktion soll einen String mit einem String durchsuchen. Also wie oft kommt das Suchwort in dem String vor.

Das Problem dabei ist bei mir die Syntax, wie baue ich so eine Funktion auf? Was passieren muss ist klar. Ich vergleiche den einen String mit den anderen String wie wenn ich eine Array vergleiche (suchbegriff[i] == suche [i])

Der Ablauft ist ja klar. In der ersten Schleife durchsucht er beide Arrays und prüft ob diese identisch sind. Das wird mit einer For schleife realisiert. doch wie mach ich das dann mit den weiteren Chars im Suchstring? Nehmen wir an, der String wurde am Anfang einmal gefunden. Wie überprüfe ich jetzt jedoch die anderen Chars die noch folgen?

Mein Problem ist nicht das denken, sondern schlicht einfach die Umsetzung.

Wie würdet Ihr das machen?

Ich stecke irgendwie fest.

Für baldige Antworten freue ich mich

Gruß

Hans

CStoll

Du mußt die Startposition im vergleichsstring für jeden Durchlauf entsprechend erhöhen - und dann halt suche[i+startpos]==suchbegriff[i] vergleichen.

(PS: Wenn erlaubt, würde ich die Stringfunktionen von C verwenden - besonders strstr() bietet sich an)

HansGeorg

Hallo,

nein die Stringfunktionen sind eben nicht erlaubt. Ich hatte bislang auch keine Probleme eine Funktion die was mit Strings macht zu schreiben, aber diese macht mir etwas Probleme.

also hier mal das script etwas aufgesetzt:

#include <stdio.h>
#include <stdlib.h>

int anzahl(char * sb, char * str)
{
    for (int i = 0; i < strlen(str); i++)
    {
    }
};

int main(int argc, char *argv[])
{
  char * derstring = new char [20];
  strcpy("TestTestTestTest",derstring);
  cout<<anzahl("Test", derstring);
  system("PAUSE");
  return 0;
}

Also nochmal die Reihenfolge die ich dachte:

Die zwei Strings byteweise vergleichen (dabei so lange wie der suchbegriff gehen)

Danach beim zweiten String, das ganze nochmal, aber nach den ersten string (oder nur ein byte vorgehen, sozuagen jedes byte mit jeden vergleichen)

CStoll

Na toll, das wird jetzt eine bunte Mischung aus C und C++. (für cout und new bist du im falschen Board gelandet und außerdem ist der reservierte Speicherbereich zu klein)

OK, zum Thema: in der äußeren Schleife zählst du die Startposition hoch, von der ab der Vergleichswert vorkommen soll, in der inneren Schleife kannst du die beiden String zeichenweise miteinander vergleichen.

PS: Dafür, daß die Stringfunktionen nicht erlaubt sind, benutzt du sie aber ziemlich ausführlich

HansGeorg

naja wir haben es so gelernt, ich kann nichts dafür. unser lehrer hat halt gesagt das wir angeblich c lernen, aber das wir dann gleich mit cout beginnen hat mich auch gewundert, da es doch c++ ist.

zu den stringfunktionen, diese zwei dürfen wir benutzen aber nicht mehr. ohne diese funktionen würde es auch zu umfangreich sein.

zu der speicherreservierung. hoppla, da hat sich wohl ein kleiner fehler eingeschlichen.

CStoll

HansGeorg schrieb:

naja wir haben es so gelernt, ich kann nichts dafür. unser lehrer hat halt gesagt das wir angeblich c lernen, aber das wir dann gleich mit cout beginnen hat mich auch gewundert, da es doch c++ ist.

*verd - wo ist der Kopf-durch-die-Wand Smilie?*

zu den stringfunktionen, diese zwei dürfen wir benutzen aber nicht mehr. ohne diese funktionen würde es auch zu umfangreich sein.

Ach, wo du schon dabei bist, kannst du die zwei Funktionen auch noch selber schreiben

// schnell hingeschrieben und nicht optimiert

int mystrlen(const char* str)
{
  int l=0;
  while(str[l]!='\0')++l;
  return l;
}

void mystrcpy(char* tgt,const char* src)
{
  for(int i=0;i<=mystrlen(src);++i)tgt[i]=src[i];
}

HansGeorg

aha danke für diese kleine hilfe. ja ich hab mich auch schon gefragt warum der lehrer alles vermischt und nichts trennt...

aber ich hab immer noch eine frage. wenn ich die strings dann zeichenweise verglichen habe (also die erste runde) und es ist identisch, wie speichere ich die anzahl dann ab in eine variable?

sorry für diese bescheurten fragen, aber unser lehrer ist nich im stande gut zu erklären.

hab mich deshalb selbst weitergebildet.

naja und diese funktion wird bewertet.

CStoll

Du nimmst dir eine int-Variable und initialisierst sie mit 0. Anschließend kannst du immer, wenn der Suchstring gefunden wurde, sie inkrementieren (++).

HansGeorg

ja ne das ist klar, aber der string den ich vergleiche, vergleiche ich doch byteweise, wie kann ich denn feststellen ob jedes byte identisch ist? denn ich vergleiche ja nicht nur ein einziges zeichen...

Daniel E.

Mal ein Beispiel: wir suchen "def" in "abdcdefghi" okay?

'd' == 'a'? Ne, also ersten Index hochschieben.
'd' == 'b'? Ne, also ersten Index wieder hochschieben.
'd' == 'd'? Jo. Ersten Index nicht hochschieben, dafür jetzt den zweiten Index hochschieben: 'e' == 'c'? Ne? Zweiten Index wieder auf 0.
'd' == 'c'? Ne, also ersten index weiter hochschieben.
'd' == 'd'? Jo. Ersten Index nicht weiter hochschieben, dafür jetzt den zweiten Index hochschieben. 'e' == 'e'? Jo, zweiten Index weiter hochschieben. 'f'=='f'? Jo, zweiten Index weiter hochschieben. '\0' == 'g'? '\0' im zu suchenden String gefunden, also ein komplettes Match -> der erste Index gibt den Trefferindex an.

Das ist jetzt so ganz stumpfsinnig eine Mustersuche.

na, du brauchst halt 2 schleifen ineinander

die erste geht die position im string durch und die zweite das suchwort. du vergleichst dann, ob alle bytes vom string und dem suchwort ab der position im string übereinstimmen. also string[stringPos + suchPos] == suchwort[suchPos]. Wenn du die innere Schleife ganz durchlaufen hast und alle bytes gleich waren hast du einen treffer. du musst natürlich auch noch die stringlängen beachten.

TheTester

Daniel E. schrieb:

Das ist jetzt so ganz stumpfsinnig eine Mustersuche.

Um das von Daniel E. aufzugreifen, das es "eine" Mustersuche ist, was impliziert das es mehrere gibt, noch ein paar Schlagworte für eine Recherche, damit du auch ein bisschen was zu erzählen hast.

Boyer-Moore-Algorithmus
Knuth-Morris-Pratt-Algorithmus
Karp-Rabin-Algorithmus

Dabei handelt es sich um drei der bekanntesten Algorithmen.

tt

HansGeorg

DAnke für deinen Hinweis zu den Algorithmen, also der Tut es für unserere Schulsachen bestimmt ganz gut,

1 function NaiveSuche(string s[1..n], string sub[1..m])
2 for i from 1 to n
3 for j from 1 to m
4 if s[i+j-1] ≠ sub[j]
5 springe zur nächsten Iteration der äußeren Schleife
6 return i
7 return nicht gefunden

jedoch kann ich mit der sprache nicht so viel anfangen, wie schreib ich das für CPP um?

HansGeorg

hallo,

ok ich hab es jetzt mit C++ Strings hinbekommen. Das ging viel einfacher und ist sogar noch schneller.

int anzahl(const char * sb, const char * str)
{
std::string text(str);
std::string::size_type stelle = text.find(sb);
int result = 0;
while(stelle != std::string::npos)
{
result++;
stelle = text.find(sb, stelle+1);
}
return result;
}

Rontha

mhhh, wenn dein lehrer sagt du sollst es in C schreiben und die Stringfunktionen (bzw. STL) nicht nehmen sollst, ist die Lösung sicherlich falsch.

supertux

HansGeorg schrieb:

naja wir haben es so gelernt, ich kann nichts dafür. unser lehrer hat halt gesagt das wir angeblich c lernen, aber das wir dann gleich mit cout beginnen hat mich auch gewundert, da es doch c++ ist.

ich sag's doch immer wieder: Was für Idioten gibt es, die sich Lehrer oder Prof. nennen

@Hans: Wenn du eine Lösung in C brauchst, dann guck dir folgende Funktion an: man: strstr(3).

wieso glaub ich nicht, dass die lösung von dir ist

CStoll

HansGeorg schrieb:

1 function NaiveSuche(string s[1..n], string sub[1..m])
2 for i from 1 to n
3 for j from 1 to m
4 if s[i+j-1] ≠ sub[j]
5 springe zur nächsten Iteration der äußeren Schleife
6 return i
7 return nicht gefunden

Na das ist doch schon mal ein Lösungsansatz - den in C umzusetzen sollte doch nicht das Problem sein. Für die aktuelle Aufgabe mußt du nur Zeile 6 ersetzen durch "erhöhe Zähler und springe zur nächsten Iteration der äußeren Schleife".

Btw, die äußere Schleife muß nur bis n-m laufen, sonst rennst du über das Speicherende hinaus.

@supertux: Das hatte ich auch schon vorgeschlagen, ist aber anscheinend nicht zugelassen.