Hallo zusammen,
ich komme bei einer Übungsaufgabe nicht mehr weiter. Die 1.Aufgabe war
eine Prozedur "drucke" zu schreiben die alle Szenen in einer Zeile
ausgibt. Das habe ich noch hinbekommen.
Jetzt soll ich eine Prozedur "schneide" schreiben die den als Parameter
übergebenen Film von allen Werbeszenen befreit und die
herausgeschnittenen Werbeszenen als eigene verkette Liste in einem
zweiten Parameter zurückgibt. Kann mir bei dieser Prozedur jemand
helfen?
PS: Es dürfen keine Speicherblöcke mit malloc angefordert bzw mit free
freigegeben werden.
d.h. man hat einen Zeiger, welcher auf das 'aktuelle' Listenelement
zeigt. Mit diesem macht man etwas. zb ausgeben, zb untersuchen ob es
bestimmte Eigenschaften erfüllt, etc- etc.
Ist man mit dem Listenelement fertig, dann wird dieser Pointer auf das
nächste Element weitergestellt. Die Information darüber, welches das
nächste Element ist, findet sich ja in Form des Next-Pointers bei jedem
Element. Das ganze wird solange wiederholt, solange es noch ein nächstes
Element gibt, der Pointer als nicht NULL geworden ist.
Jetztz schreibst du erst mal deine Ausgabefunktion korrekt um.
Und dann:
Das für mich wichtigste beim erlernen der Techniken der dynamischen
Programmierung war die Erkenntnis, dass einem ein Aufzeichnen der
Datenstruktur bzw. eines Testszenarios eine Menge Ärger und Frustration
erspart.
Das hier
1
film
2
+-----+ +-----------+
3
| o----------->| "Werbung" |
4
+-----+ | o--------------+
5
+-----------+ |
6
|
7
v
8
+-----------+
9
| "Szene A" |
10
| o |
11
+--|--------+
12
|
13
v
14
+-------------+
15
| "Werbung" |
16
| o |
17
+--|----------+
18
|
19
v
20
+-------------+
21
| "Werbung" |
22
| o |
23
+--|----------+
24
|
25
v
26
+-----------+
27
| "Szene B" |
28
| o |
29
+--|--------+
30
|
31
v
32
+-------------+
33
| "Werbung" |
34
| NULL |
35
+-------------+
36
37
werbung
38
+---------+
39
| NULL |
40
+---------+
ist deine Datenstruktur, die du mittels
1
szenes6={"Werbung",NULL},
2
s5={"Szene B",&s6},
3
s4={"Werbung",&s5},
4
s3={"Werbung",&s4},
5
s2={"Szene A",&s3},
6
s1={"Werbung",&s2},
7
*film=&s1,*werbung=NULL;
aufgebaut hast.
Wie musst du mit dem Finger die eingezeichneten Pfeile verfolgen und
welche Operationen musst du dabei jeweils machen, so dass sich das hier
...
1
film
2
+-----+ +-----------+
3
| o-------+ | "Werbung" |
4
+-----+ | | o--------------------------------+
5
| +-----------+ |
6
| ^ |
7
| | |
8
| | +-----------+ |
9
+-----)-------------->| "Szene A" | |
10
| +------ o | |
11
| | +-----------+ |
12
| | |
13
| | |
14
| | +-------------+ |
15
| | | "Werbung" |<----+
16
| | | o--------------+
17
| | +-------------+ |
18
| | |
19
| | |
20
| | +-------------+ |
21
| | | "Werbung" |<--+
22
| | | o-------------------+
23
| | +-------------+ |
24
| | |
25
| | |
26
| | +-----------+ |
27
| +------>| "Szene B" | |
28
| | NULL | |
29
| +-----------+ |
30
| |
31
| |
32
| +-------------+ |
33
| | "Werbung" |<----+
34
| | NULL |
35
| +-------------+
36
|
37
werbung |
38
+---------+ |
39
| o-------------+
40
+---------+
... daraus ergibt.
Dein Hilfsmittel ist nur dein Finger. Du fängst im Original bei 'film'
an. Du darfst mit dem Finger den Pfeilen folgen bzw. mit den Werten im
Rechteck arbeiten, auf das dein Finger zeigt.
Wenn dir klar ist, was du zu tun hast um aus dem Original zum
gewünschtenb Egrbenis zu kommen, dann bist du auch erstmals in der Lage
ein Verfahren dafür zu formulieren.
Die Techniken die du brauchst sind:
- Hänge ein Element an das Ende einer Liste
- Schneide ein Element mitten aus der Liste und gib das rausgeschnittene
zurück.
Schreib mal die beiden.
Immer frei nach Karl Heinz: " Das Problem solange in Teilprobleme
zerlegen bis man die Teilprobleme lösen kann"
Am Ende hast du dann (Pseudocode):
Gehe duch alle Szenen
If (Szene == Werbung) {
Werbungsszene = SchneideSzeneAusFilmRaus(AlleSzenen)
HängeAn(Werbung, Werbungsszene)
}
Alternativ geht natürlich auch ein Verteilen der Szenen auf 2 Variablen
eine
"FilmOhneWerbung"
und eine Zweite
"Werbung".
Dann musst du nicht schneiden sondern nur anhängen und hast den Vorteil,
daß die Originalreihenfolge erhalten bleibt.
Udo Schmitt schrieb:> Die Techniken die du brauchst sind:> - Hänge ein Element an das Ende einer Liste> - Schneide ein Element mitten aus der Liste und gib das rausgeschnittene> zurück.> Schreib mal die beiden.
Kann man machen.
Man kann dieses spezielle Problem aber auch so auffassen:
Durchmarsch durch die Liste und bei jedem Element entscheiden, in welche
andere Liste dieses Element gehört (dazu benutzt man eine "temporäre
Liste", deren Head Pointer nur in der Funktion existiert).
Nach dem Durchmarsch durch die Liste hat man dann alle Elemente in 2
Listen aufgeteilt: die eine ist die Liste die in 'werbung' startet, die
andere ist die temporäre Liste, die man dann einfach zur neuen
'film'-Liste erklärt.
Dadurch spart man sich den doch recht aufwändigen Teil des Ausschneidens
aus einer Liste.
Edit:
Da hatten wir wohl beide zeitgleich 'die Idee', wie man das Problem auch
einfacher angehen kann. :-)
Hallo Karl Heinz,
danke für deine schnelle antwort. Du hast natürlich recht so wie ich die
Ausgabefunktion geschrieben habe war das zwar zweckmäßig aber nicht
gerade sauber. Danke für die Erklärung.
Hier die saubere Ausgabe:
1
voiddrucke(szene*film)
2
{
3
4
while(film!=NULL)
5
{
6
printf("%s ",film->inhalt);
7
film=film->next;
8
}
9
}
Bei der "schneide" Prozedur hänge ich irgendwie. Habe es mir auch schon
aufgezeichnet aber richtig weiter bringt mich das leider auch nicht. Ich
denke ich brauch wieder eine while-schleife damit ich jedes einzelne
Element wieder für sich betrachten kann.(?) Nur wie kann ich z.B
überprüfen ob die Szene Werbung ist oder eine Szene A/B?
Kann man dass so machen?
if(film->inhalt == "Werbung")
Karl Heinz schrieb:> Dein Hilfsmittel ist nur dein Finger. Du fängst im Original bei 'film'> an. Du darfst mit dem Finger den Pfeilen folgen bzw. mit den Werten im> Rechteck arbeiten, auf das dein Finger zeigt.
Und du darfst dir natürlich noch weitere Pointer-Variablen (also
Rechtecke, aus denen Pfeile auf Elemente der Datenstruktur verweisen)
erzeugen. Diese Pfeile kommen allerdings nicht einfach so aus der Luft,
sondern du kannst sie zb nur dann in die Zeichnung einzeichnen, wenn du
einen anderen Pfeil darauf hast, den du zb über deinen Finger
'erreichen' kannst und auch eine Regel dafür angeben kannst.
Speziell bei der 'Aufteilungsmethode' wirst du ein paar dieser
Hilfs-Pointer benötigen.
Mhash schrieb:> Kann man dass so machen?> if(film->inhalt == "Werbung")
Die Idee ist gut, aber wie vergleicht man 2 Strings?
Lies deinen Kernigham Ritchie!
Mhash schrieb:> aufgezeichnet aber richtig weiter bringt mich das leider auch nicht. Ich> denke ich brauch wieder eine while-schleife damit ich jedes einzelne> Element wieder für sich betrachten kann.(?)
Welchen Teil von
"Den Durchmarsch durch eine verkettete Liste macht man IMMER so ...."
hast du nicht verstanden?
Nur wie kann ich z.B
> überprüfen ob die Szene Werbung ist oder eine Szene A/B?> Kann man dass so machen?> if(film->inhalt == "Werbung")
Ooops.
zurück an den Anfang deiner C-Studien.
Wie werden in C denn Strings miteinander verglichen? Wenn du dich an
dynamischen Datenstrukturen versuchst, dann sollte dieses Thema aber
schon längst in Fleisch und Blut übergegangen sein! Dazwischen liegen im
K&R rund 150 Seiten.
Bei dieser Funktion spielt es zwar keine Rolle, aber in der
Allegemeinheit rate ich dir dringend davon ab, deinen Head-Pointer der
Liste leichtfertig aufs Spiel zu setzen und zu verändern! Das führt
meistens in Probleme! Der Head-Pointer ist so ziemlich das wichtigste
was du von einer Liste haben kannst. Den gibst du nicht leichtfertig
auf.
1
voiddrucke(szene*film)
2
{
3
szene*loopPtr=film;
4
5
while(loopPtr!=NULL)
6
{
7
printf("%s ",loopPtr->inhalt);
8
loopPtr=loopPtr->next;
9
}
10
}
wenn du genau schaust, dann hast du hier bereits integriert das
allgemeine Schema zum Durchmarsch durch eine Liste. Es findet sich aus
dem allgemeinen Rezept
1
...
2
Pointer loopPtr;
3
4
loopPtr = Zeiger auf das erste Element
5
6
while( loopPtr != NULL )
7
{
8
... mach was mit dem Listenelement, auf welches loopPtr zeigt
9
10
loopPtr = loopPtr->next;
11
}
12
...
jeder einzelne Punkt wieder. Genau dieses 'Kochrezept' steckt in der
drucken-Funktion drinnen, einzig der Punkt 'mach was mit ....' ist über
den printf spezieller ausformuliert.
Der loopPtr (ob du den jetzt so nennst oder nicht, spielt keine Rolle),
diese Variable ist genau der 'Finger' von dem ich weiter oben im
Zusammenhang mit der Zeichnung gesprochen habe.
Karl Heinz schrieb:> Wenn du dich an> dynamischen Datenstrukturen versuchst, dann sollte dieses Thema aber> schon längst in Fleisch und Blut übergegangen sein! Dazwischen liegen im> K&R rund 150 Seiten.
Irgendwie keimt in mir so ein Verdacht daß da einer ein halbes Semester
gepennt/gefaulenzt/gefeiert hat und jetzt ein äh ... Problemchen hat.
Meine Guete, hier sind wohl Alle als Genies auf die Welt gekommen. So
sieht das halt aus, wenn Jemand ohne grosse Vorkenntnisse im Studium C
lernt. Ist doch nichts Schlimmes dabei...
Danke nochmal für eure schnelle Hilfe. Ich habe mich jetzt heute
Nachmittag nochmal in Strings eingelesen weils doch schon länger her
ist. Ich muss aber auch sagen dass dieses Thema "dynamische
Datenstrukturen" erst vor kurzem behandelt wurde.Und ich denke,dass es
auch nicht schlimm ist wenn ich damit noch nich ganz klar komme.
Leider konnte ich die Aufgabe immer noch nicht Lösen. Ich habe eure
Tipps alle versucht zu realisieren aber leider kommt bei mir nur scharn
raus =(
Vll. könnte mir jemand die Lösung aufzeigen?
Mhash schrieb:> Leider konnte ich die Aufgabe immer noch nicht Lösen.
Zeig halt mal.
der wichtigste Punkt ist das Lernen der Vorgehensweise. Ich kann dir nur
meine zeigen und die führt nun mal über das aufmalen der Datenstruktur
und dem sich klar machen, welche Pointer in welcher Reihenfolge
manipuliert werden müssen, damit man sich dem Ziel nähert. Dazu schrecke
ich auch nicht davor zurück, meinen 'Code' mittels Papier, Bleistift und
Radiergummi an dieser Zeichnung zu 'testen', um zu sehen, ob ich mir
nicht einen Pointer unter dem Hintern wegstehle.
Daher ist es auch nicht wirklich sinnvoll, da fertigen Code zu
präsentieren. Zumal der in der Variante "Aufteilen der Elemente auf 2
Listen" jetzt wirklich nicht so schwer zu realisieren ist.
Quack schrieb:> Meine Guete, hier sind wohl Alle als Genies auf die Welt gekommen. So> sieht das halt aus, wenn Jemand ohne grosse Vorkenntnisse im Studium C> lernt. Ist doch nichts Schlimmes dabei...
Meine Güte.
Ist doch nichts schlimmes dabei, wenn jemand in der Mathe-Vorlesung über
Differentialgleichungen nicht in der Lage ist, einfache lineare
Gleichungen so umzuformen, dass alle x auf einer Seite stehen. Ungefähr
auf dem Niveauunterschied bewegen sich die Problemkreise
"C-Stringverarbeitung" und "dynamische Datenstrukturen".
Karl Heinz schrieb:> Daher ist es auch nicht wirklich sinnvoll, da fertigen Code zu> präsentieren. Zumal der in der Variante "Aufteilen der Elemente auf 2> Listen" jetzt wirklich nicht so schwer zu realisieren ist.
Da kommen 2 Listen raus. Für jede Liste gibt es 2 Pointer-Variablen. Die
eine ist der Pointer auf das erste Element (der Head-Pointer), die
andere ist ein Pointer auf das jeweils zuletzt eingefügte Element (der
Tail-Pointer). Beide beginnen bei NULL, wodurch sie anzeigen: die Liste
ist noch leer.
Muss ein Element an eine Liste angefügt werden, dann befragt man den
Head-Pointer. Ist der NULL, die Liste also noch leer, dann ist dieses
Element das erste einzufügende Element der Liste. Man lässt dann einfach
den Head Pointer darauf zeigen.
Ist der Head-Pointer nicht NULL, dann gibt es bereits Elemente in dieser
Liste. Der Tail-Pointer sagt einem, welches von diesen bereits
vorhandenen Elementen das letzte ist. An dieses letzte Element muss das
neu einzufügende angehängt werden. Das macht man auch.
Egal wie jetzt dieses neue Element an diese Liste angehängt wurde, nach
der Operation ist dann auf jeden Fall dieses eingefügte Element das neue
letzte Element und demenstsprechend lässt man den Tail-Pointer auf
dieses Element zeigen, weil man diesen ja braucht, wenn das nächste
Element angefügt werden muss.
Den ganzen Mechanismus gibt es 2 mal, weil es ja 2 derartige Listen
gibt. Eine für Werbung, die andere für keine Werbung.
Aus der originalen Liste geht man alle Elemente eines nach dem anderen
durch, entscheidet in welche Liste das Element muss und macht das dann
ganz einfach.
In den jeweiligen Teillisten nicht vergessen, dass das jeweils letzte
Element noch einen NULL-Pointer am Listenende braucht und die Sache ist
gegessen.
D.h. fast.
Denn die Argumentschnittstelle für deine Funktion stimmt noch nicht.
Aber das kann warten, wenn du dir die Teillisten jeweils innerhalb der
Aufteilfunktion ausgeben lässt um das Ergebnis zu kontrollieren.
kopfkratz
Ja was hast Du nun nicht verstanden, Karl-Heinz hat es doch sehr schön
erklärt ?
Oder kann es sein das Du keinen Speicher für die einzelnen
Listenelemente allokierst und damit Datenmüll produzierst ?
Stelle den GESAMTEN Code der nicht funktioniert hier ein und wir schaun
drüber ;-)
Karl Heinz schrieb:> Da kommen 2 Listen raus. Für jede Liste gibt es 2 Pointer-Variablen.> ....
Das ist übrigens der aufwändigere und zugleich simplere Weg. Der
kanonische Weg führt über 2 allgemein verwendbarere Funktionen, die aber
jede für sich etwas aufwändiger zu schreiben sind.
* aushängen eines Wertes aus einer Liste
* anhängen eines Wertes an eine Liste
Die Aushäng Funktion ist in der allgemeinen Form etwas komplexer zu
schreiben. Da man es hier allerdings mit einem Sonderfall zu tun hat,
ist sie so kompliziert auch wieder nicht.
Die komplette Operation ist dann einfach: Das jeweils erste Element aus
der originalen Liste aushängen (wodurch ein neues Element erstes Element
wird), entscheiden in welche Teilliste es muss und der Anhängfunktion
den Auftrag dafür geben
1
szene*removeFirst(szene**liste)
2
{
3
...
4
}
5
6
voidaddTo(szene**liste,szene*elem)
7
{
8
...
9
}
10
11
voidschneide(szene**film,szene**werbung)
12
{
13
szene*nonWerbung=NULL;
14
*werbung=NULL;
15
16
while(*film)
17
{
18
szene*elem=removeFirst(film);
19
20
if(strcmp(elem->inhalt,"Werbung"))
21
addTo(werbung,elem);
22
else
23
addTo(&nonWerbung,elem);
24
}
25
26
*film=nonWerbung;
27
}
Also so komplex dann auch wieder nicht.
PS: die ** sind so gewollt. Willkommen in der 2-Stern Programmierung.
Karl Heinz schrieb:> Die Aushäng Funktion ist in der allgemeinen Form etwas komplexer zu> schreiben. Da man es hier allerdings mit einem Sonderfall zu tun hat,> ist sie so kompliziert auch wieder nicht.
Eigentlich ist die sogar recht trivial. Das haben sowohl Udo als auch
ich beim Überdenken im Kopf übersehen, dass es sich hier ja um einen
recht einfachen Sonderfall handelt. Man muss ja immer nur das erste
Element aus einer Liste aushängen.
aus
1
head
2
+-----+ +--------+ +-------+
3
| o-------->| | +--->| | +-->
4
+-----+ | o--------+ | o--------+
5
+--------+ +-------+
muss
1
+----------------+
2
head | |
3
+-----+ | +--------+ | +-------+
4
| o-----+ | | +--->| | +-->
5
+-----+ | NULL | | o--------+
6
+--------+ +-------+
7
^
8
elem |
9
+-----+ |
10
| o--------+
11
+-----+
werden, wobei elem dann der Returnwert der Funktion RemoveFirst ist.
Eine eigentlich recht einfache zu implementierende Funktionalität.
Da haben wir uns von der komplexeren Operation "Suche ein bestimmtes
Element und hänge es aus" blenden lassen. Aber die braucht hier ja
keiner.
Noch ein PS
'addTo' sollte besser 'appendTo' heißen, damit klar ist, dass an die
Liste hinten angehängt wird und nicht einfach irgendwo.
Es sei denn, es ist dir egal, dass die Reihenfolge durcheinander kommt.
Dann würde ich die Funktion 'addHead' nennen und das Element als jeweils
neues erstes Element in eine Liste einhängen. Eine ebenfalls triviale
Operation.
Aus
1
head
2
+-----+ +-------+
3
| o-------->| | +--> ...
4
+-----+ | o--------+
5
+-------+
6
7
8
+------+
9
| |
10
| NULL |
11
+------+
12
^
13
elem |
14
+-----+ |
15
| o--------+
16
+-----+
muss
1
head
2
+-----+ +-------+
3
| o----+ +->| | +--> ...
4
+-----+ | | | o--------+
5
| | +-------+
6
| |
7
| +-----------+
8
| |
9
| +------+ |
10
+->| | |
11
| o--------+
12
+------+
13
^
14
elem |
15
+-----+ |
16
| o--------+
17
+-----+
werden. Das sollte eigentlich keinerlei Schwierigkeiten machen. Aus der
Zeichnung ist unmittelbar ersichtlich, welcher Pointerwert wohin kopiert
werden muss.
Quack schrieb:> Meine Guete, hier sind wohl Alle als Genies auf die Welt gekommen. So> sieht das halt aus, wenn Jemand ohne grosse Vorkenntnisse im Studium C> lernt. Ist doch nichts Schlimmes dabei...
Interessant ist, daß die Quacks der Welt zwar weltverbesserisch
herumschreien und schimpfen können, aber so gut wie nie den hier
Fragenden helfen.
Warum nur?
Zum Rest der Aussage hat Karl Heinz schon genug gesagt.
Nachtrag: Karl Heinz, ich muss deine Geduld mal wieder bewundern :-)
Thread beobachten
Seitenaufteilung abschalten