C-Aufgabe -> Verkettete Liste / Speicherverwalt

Computer: Software & Programmierung C/C++
#1

Hallo an alle!

Ich habe die Arbeit aufgedrückt bekommen mir eine C-Übungsaufgabe zu überlegen, welche die Themengebiete „Verkettete Liste“ (mit struct) und Speicherverwaltung (malloc/free) abdeckt.
Bekannt sind (sollten zumindest sein :smile:):

  • Datentypen (int, float, char, …)
  • if-Bedingung, Schleifen
  • Einlesen von der Konsole
  • Pointer
  • Arrays, auch mehrdimensional
  • structs & unions

Also eigentlich ein gutes C-Fundament (Java-Grundlagen sind auch vorhanden). Habt Ihr Ideen was man da für eine schöne Aufgabe basteln könnte? Der Aufwand um die Aufgabe zu lösen, sollte nicht mehr als 1h betragen (wobei ich da auch schon was als Zusatz für die, die sich langweilen, dazumachen kann, das etwas kniffliger ist).

Fällt Euch irgendwas ein?

Danke schon mal im voraus + Gruß PHANTOM

#2

Mahlzeit,

Fällt Euch irgendwas ein?

ich hätte eine Aufgabe aus dem wirklichen Leben. Ein Kollege von mir hatte eine Katalogverwaltung programmiert; der Benutzer sollte den Katalog (es ging um medizinische Substanzen) durchsuchen können. Er hatte das so programmiert, daß er eine Eingabemaske einsetzte; der Benutzer gab das Gesuchte ein (z.B. „1-2-Thiabendazole Stearate“ o.Ä), und die gesamte Menge wurde durchsucht.

Das hatte zwei Nachteile: 1. dauerte die Suche sehr lang, 2. mußte man das Gesuchte ganz und fehlerfrei eingeben, um es zu finden.

Ich löste das auf anderer Weise: zunächst einmal las ich den Katalog in den Speicher ein und verwendete dazu eine doppelt verkettete Liste (1. Teilaufgabe). Das waren ein paar zehntausend Eintragungen, aber der Speicher reichte aus, und die Einleseprozedur mußte ja nur einmal bei Programmstart stattfinden. Danach sortierte ich die Liste alphabetisch (2. Teilaufgabe). Die Suche war dann sozusagen trivial: schon bei der Tastatureingabe sprang ich auf die passende Stelle der Liste, und das Finden erfolgte in Echtzeit (3. Teilaufgabe). Von meinem Auftraggeber wurde ich dafür geliebt (4. Teilaufgabe - äh, nein :smile: ).

Wäre das was?

Gruß

Sancho

#3

Vielen Dank für die Antwort.
Das Problem ist, das habe ich vergessen zu sagen: Es werden nur einfach-verkettete Listen behandelt und so kann ich nur auf dieses Wissen zurückgreifen.

Aber ansonsten ist das natürlich eine schöne Idee…

Danke + Gruß PHANTOM

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Vielen Dank für die Antwort.
Das Problem ist, das habe ich vergessen zu sagen: Es werden
nur einfach-verkettete Listen behandelt und so kann ich nur
auf dieses Wissen zurückgreifen.

Hmmm, na dann… obwohl, die doppelte Verkettung brauchst Du ja nur, wenn der Benutzer sich bei der Eingabe vertippt…

Wieso nur einfache Verkettung? Die doppelte ist ja vom Aufwand her nicht schwerer zu implementieren, und der Nutzen ist mehr als doppelt so groß :smile:

Gruß

Sancho

#5

Hmmm, na dann… obwohl, die doppelte Verkettung brauchst Du
ja nur, wenn der Benutzer sich bei der Eingabe vertippt…

Wieso nur einfache Verkettung? Die doppelte ist ja vom Aufwand
her nicht schwerer zu implementieren, und der Nutzen ist mehr
als doppelt so groß :smile:

Tja, an den Themen die gelehrt werden, habe ich keinen Einfluss. Aber das in einer Übung hinzubekommen was nicht gezeigt wurde, das würde das Niveau doch etwas übersteigen.

Gruß PHANTOM

#6

Ich löste das auf anderer Weise: zunächst einmal las ich den
Katalog in den Speicher ein und verwendete dazu eine doppelt
verkettete Liste (1. Teilaufgabe). Das waren ein paar
zehntausend Eintragungen, aber der Speicher reichte aus, und
die Einleseprozedur mußte ja nur einmal bei Programmstart
stattfinden. Danach sortierte ich die Liste alphabetisch (2.
Teilaufgabe). Die Suche war dann sozusagen trivial: schon bei
der Tastatureingabe sprang ich auf die passende Stelle der
Liste, und das Finden erfolgte in Echtzeit (3. Teilaufgabe).

Ich will ja nicht unhöflich sein, und in deinem Fall war es ja anscheinend trotzdem ok, aber: eine verkettete Liste ist eine denkbar schlechte Datenstruktur zum sortierten Suchen von Elementen (O(n))! Ein einfacher sortierter Array wäre z.B. viel besser (O(log n) mit binärer Suche).

Als Lehraufgabe wäre deine Lösung also denkbar ungeeignet.

Viele Grüße,
Sebastian

#7

Ich will ja nicht unhöflich sein, und in deinem Fall war es ja
anscheinend trotzdem ok, aber: eine verkettete Liste ist eine
denkbar schlechte Datenstruktur zum sortierten Suchen von
Elementen (O(n))! Ein einfacher sortierter Array wäre z.B.
viel besser (O(log n) mit binärer Suche).

Als Lehraufgabe wäre deine Lösung also denkbar ungeeignet.

Okay, hast du eine gute Idee was ich als Aufgabe stellen könnte?

Gruß PHANTOM

#8

Als Lehraufgabe wäre deine Lösung also denkbar ungeeignet.

Okay, hast du eine gute Idee was ich als Aufgabe stellen
könnte?

Keine Ahnung, was ist denn die Zielgruppe? Informatikstudenten im 2./3. Semester? Welchen Umfang soll die Aufgabe haben?

Eine sehr einfache Anwendung von verketteten Listen ist eine Warteschlange oder ein Stack, falls sie das schon kennen. Falls nicht, ist es trotzdem kein großer Aufwand, zu erklären, was man will.

Wie wäre es damit:

  • Eine Textdatei/Wortliste unbekannter Länge zeilenweise einlesen und dann nur jede gerade Zeile ausgeben?
  • Einlesen und rückwärts ausgeben?
  • Ein Wort in der Liste suchen und sich überlegen, wie viele Zugriffe im Mittel/best/worst case dafür nötig sind?
  • Den merge-Schritt vom Mergesort implementieren, um zwei sortierte Wortlisten zu einer neuen sortierten Wortliste zu verschmelzen (ok, hier würde man vermutlich keine Listen verwenden, sondern on the fly arbeiten :smile:)? Darauf aufbauend könnte man später Mergesort leichter einführen.
  • Jedes Vorkommnis eines verbotenen Substrings aus der Liste löschen, bevor man sie ausgibt? Dann wird die Löschoperation auch behandelt
  • Interaktiv in eine sortierte Wortliste neue Elemente an die richtige Position einfügen? Suchen und Einfügen wird behandelt.

…

Also ich kann dir nur Anregungen geben :smile:. Aus den bisher genannten kann man locker mehr als eine Aufgabe machen. Man muss halt auch abhängig vom gewünschten Level die Schwierigkeit der Aufgabe wählen.

Grundsätzlich sinnvoll wäre, wenn Einfügen am Anfang/Ende, Suche nach einem Element, Einfügen mittendrin und Löschen Anfang/Ende/Mitte vorkämen, um die interessanten use cases von verketteten Listen abzudecken.

Viele Grüße,
Sebastian

#9

Grundsätzlich sinnvoll wäre, wenn Einfügen am Anfang/Ende,
Suche nach einem Element, Einfügen mittendrin und Löschen
Anfang/Ende/Mitte vorkämen, um die interessanten use cases von
verketteten Listen abzudecken.

Ich habe gerade noch mal in deinem Urposting gelesen, dass das Zeitbudget für die Lösung der Aufgabe nur eine Stunde sein soll. Da passt bei Anfängern das alles vermutlich eher nicht rein. Ich würde wohl einfache Stack/Queue-Funktionalität plus eine einfache Anwendung davon wie eine Textdatei umdrehen als Aufgabe stellen.

Viele Grüße,
Sebastian

#10

Die Dateiein-/ausgabe soll separat in einer Aufgabe formuliert werden, da das etwas zu viele Themengebiete in einer Aufgabe wären.

Das was du schreibst, das geht in Richtung unserer Algorithmen-Vorlesung mit Listen, Stacks, usw.

Zielgruppe sind E-Techniker im 2-3 Semester. Es ist also eine C-Grundvorlesung.

Gruß PHANTOM

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#11

Die Dateiein-/ausgabe soll separat in einer Aufgabe formuliert
werden, da das etwas zu viele Themengebiete in einer Aufgabe
wären.

Hm… dann stattdessen Eingabe von Wörtern an der Konsole, Abschluss mit leerem Wort, dann Ausgabe in umgekehrter Reihenfolge? Oder jedes zweite Wort? In zwei Spalten?

Das was du schreibst, das geht in Richtung unserer
Algorithmen-Vorlesung mit Listen, Stacks, usw.

Na darum geht es doch genau, dache ich :smile:. Um eine Liste und was man mit ihr so macht.

Zielgruppe sind E-Techniker im 2-3 Semester. Es ist also eine
C-Grundvorlesung.

Und haben die E-Techniker auch eine Algorithmen-VL oder sind sie diesbezüglich blank? In jedem Fall ist es nicht verkehrt, die Liste z.B. als Queue zu verwenden. E-Techniker kennen Warteschlangen auch aus ihrem Fach (FIFOs kommen da schon mal vor), und wenn man nicht allzusehr auf Datentypen herumreitet, sonder einfach eine konkrete Aufgabe mit Warteschlangenfunktionalität stellt, sollte das hinhauen.

Ist ja nur hinten rein, vorne raus. Mehr muss man nicht wissen.

VG,
Sebastian

#12

Die Dateiein-/ausgabe soll separat in einer Aufgabe formuliert
werden, da das etwas zu viele Themengebiete in einer Aufgabe
wären.

Hm… dann stattdessen Eingabe von Wörtern an der Konsole,
Abschluss mit leerem Wort, dann Ausgabe in umgekehrter
Reihenfolge? Oder jedes zweite Wort? In zwei Spalten?

Ja, die Eingabe werde ich auf der Konsole machen lassen.

Das was du schreibst, das geht in Richtung unserer
Algorithmen-Vorlesung mit Listen, Stacks, usw.

Na darum geht es doch genau, dache ich :smile:. Um eine Liste und
was man mit ihr so macht.

Nein, hier werden nur absolute Grundlagen vermittelt. Das ist sozusagen das Abschluss-Thema für das es noch eine Übungsaufgabe gibt, aber auch nicht relevant für die Klausur ist.

Zielgruppe sind E-Techniker im 2-3 Semester. Es ist also eine
C-Grundvorlesung.

Und haben die E-Techniker auch eine Algorithmen-VL oder sind
sie diesbezüglich blank? In jedem Fall ist es nicht verkehrt,
die Liste z.B. als Queue zu verwenden. E-Techniker kennen
Warteschlangen auch aus ihrem Fach (FIFOs kommen da schon mal
vor), und wenn man nicht allzusehr auf Datentypen herumreitet,
sonder einfach eine konkrete Aufgabe mit
Warteschlangenfunktionalität stellt, sollte das hinhauen.

Ja, sie haben eine Algo-VL, jedoch erst ein Semester später. Da wird alles behandelt und nochmals mit Übungsaufgaben vertieft.

Danke + Gruß PHANTOM

#13

ServuZ,
vorab Fehler sind möglich alles auf die schnelle IDE XD:

include

iclude

include

const char NULL = ‚\0‘
const int ELMENT_COUNT =10;

struct listElement_Typ{
listElement_Typ* next_typ;
char[101] input;
int listElementId = 0;
};

int main(){
char[101] inputString;
printf(„Listen-Programm“);
inputString = gets();
listElement_Typ start_typ* = (listElement_Typ*)malloc sizeof(listElement_Typ)
for(int i = 0; iinput,inputString);
element_typ->listElementId;

element_typ->next_typ = element_typ

}

for(int i = 0; inext_typ->input,start_typ->next_typ->listElementId);

}

}

meist du sowas in der Art vllt.?
Das ist das simpelste was mir für Grundlagen eingefallen ist.
Entschuldige Fehler(vor allem printf("") benutze sonst cin>> und cout

#14

Hallo

Ich habe die Arbeit aufgedrückt bekommen mir eine
C-Übungsaufgabe zu überlegen, welche die Themengebiete
„Verkettete Liste“ (mit struct) und Speicherverwaltung
(malloc/free) abdeckt.
Bekannt sind (sollten zumindest sein :smile:):

  • Datentypen (int, float, char, …)
  • if-Bedingung, Schleifen
  • Einlesen von der Konsole
  • Pointer
  • Arrays, auch mehrdimensional
  • structs & unions

Folgende Aufgabe:

  1. 3D-Volumen definieren (einfach als x-laenge, y-laenge, z-laenge,
    die Box geht dann pro koordinate von 0 bis zu dieser Position
    Beispiel: double Lx=100,Ly=100,Lz=100

  2. 1,000,000 (1 Mio) 3D-Punkte Erzeugen, die per Zufall „irgendwo“
    in der Box verteilt sind

  3. einen „Schuss“ durch die Box mit einem „Kugel“-Partikel mit
    Durchmesser 2 (r=1) machen (parallel zu einer Hauptachse, also Start
    z.B. bei ( x=0 ,y=20,z=30) und Ende bei ( x=100 ,y=20,z=30).
    Dabei wird der „Schuß“ in 100 Intervalle (bei x=0, x=1, x=2 usw.)
    zerlegt.

  4. Ziel_1: Feststellen aller 3D-Punkte, die von der Kugel „getroffen“
    werden, diese werden (Index, Feld) zurückgeliefert.
    Ziel_2: maximale Performance

  5. Lösung: Zerlegen der 100³-Box in Untergitter einer Größe K x M x N,
    die es ermöglicht, durch Suche in den benachbarten zugeordneten Gitter-
    elementen einer Box-Position alle 3D-Punkte zu finden (Abstandskriterium)

  6. Jedes Gitterelement dieses Gitters ist dann der Startpunkt einer
    einfach verketteten Liste, welche nacheinander die 3D-Punkte (deren
    Indices) enthält, die in diesem Gitterelement vorkommen.

Das liesse sich vor allem später einmal ausbauen (grafische
Darstellung) und eignet sich vorzüglich dafür, durch eine
Datenstruktur (Liste) ein O(N²)-Problem in ein K x O(N)
Problem zu verwandeln.

Grüße

CMБ

#15

Hallo!

Vielen Dank, die Aufgabe finde ich echt supertoll! Leider, wirklich leider ist diese doch m.E. zu kompliziert. Es sind einige Personen dabei, die Sprachprobleme haben, da sie nicht aus Deutschland kommen.
Diese Aufgabe denen nahezubringen, das wäre sehr sehr schwieirg und der Zeitaufwand würde somit auch deutlich überschritten werden.
Aber echt, die Aufgabe ist toll, die löse ich mal zu meinem privaten Vergnügen :smile:

Danke vielmals + Gruß PHANTOM

Folgende Aufgabe:

  1. 3D-Volumen definieren (einfach als x-laenge, y-laenge,
    z-laenge,
    die Box geht dann pro koordinate von 0 bis zu dieser Position
    Beispiel: double Lx=100,Ly=100,Lz=100

  2. 1,000,000 (1 Mio) 3D-Punkte Erzeugen, die per Zufall
    „irgendwo“
    in der Box verteilt sind

  3. einen „Schuss“ durch die Box mit einem „Kugel“-Partikel mit
    Durchmesser 2 (r=1) machen (parallel zu einer Hauptachse, also
    Start
    z.B. bei ( x=0 ,y=20,z=30) und Ende bei
    ( x=100 ,y=20,z=30).
    Dabei wird der „Schuß“ in 100 Intervalle (bei x=0, x=1, x=2
    usw.)
    zerlegt.

  4. Ziel_1: Feststellen aller 3D-Punkte, die von der Kugel
    „getroffen“
    werden, diese werden (Index, Feld) zurückgeliefert.
    Ziel_2: maximale Performance

  5. Lösung: Zerlegen der 100³-Box in Untergitter einer Größe K
    x M x N,
    die es ermöglicht, durch Suche in den benachbarten
    zugeordneten Gitter-
    elementen einer Box-Position alle 3D-Punkte zu finden
    (Abstandskriterium)

  6. Jedes Gitterelement dieses Gitters ist dann der Startpunkt
    einer
    einfach verketteten Liste, welche nacheinander die 3D-Punkte
    (deren
    Indices) enthält, die in diesem Gitterelement vorkommen.

Das liesse sich vor allem später einmal ausbauen (grafische
Darstellung) und eignet sich vorzüglich dafür, durch eine
Datenstruktur (Liste) ein O(N²)-Problem in ein K x O(N)
Problem zu verwandeln.

Grüße

CMБ

#16

Ja, sowas meine ich, jedoch muss da natürlich eine Aufgabe drumherum gebaut werden!

Gruß PHANTOM