Dionysos211
-
Gesamte Inhalte
52 -
Benutzer seit
-
Letzter Besuch
Inhaltstyp
Profile
Forum
Downloads
Kalender
Blogs
Shop
Beiträge von Dionysos211
-
-
ok mein erster Denkfehler ist glaub ich das erreichen des letzten Elements vom rechten Teilbaum aus... das haut nicht hin... glaub ich...
-
Hallo,
hab da eine kleine Frage zu Übungen aus dem Sedgewick
Frage 4:
- Welche Positionen können von dem drittgrößten Schlüssel in einem Heap der Größe 32 eingenommen werden?
- Welche Positionen können von dem drittkleinsten Schlüssel in einem Heap der Größe 32 nicht eingenommen werden?
Aus dem Kapitel 11.5 (Robert Sedgewick: Algorithmen) geht hervor:
Um zum Beispiel einen Heap aus 127 Elementen aufzubauen, ruft die Methode downheap für (64 Heaps der Größe 1), 32 Heaps der Größe 3, 16 Heaps der Größe 7, 8 Heaps der Größe 15, 4 Heaps der Größe 31, 2 Heaps der Größe 63 und einen Heap der Größe 127 auf, so daß im ungünstigsten Falle 64 * 0 + 32 * 1 + 16 * 2 + 8 * 3 + 4 * 4 + 2 * 5 + 1 * 6 = 120 »Übertragungen« (doppelt so viele Vergleiche) benötigt werden. Für M = 2m ist eine obere Schranke für die Anzahl der Vergleiche durchverstehe ich das jetzt richtig das ich bei der Frage annehmen kann das mit der "Größe" eines Heap dort die Anzahl der Elemente gemeint ist ?
also:
16 Heaps der Größe 1
8 Heaps der Größe 3
4 Heaps der Größe 7
2 Heaps der Größe 15
1 Heap der Größe 31
16 * 0 + 8 * 1 + 4 * 2 + 2 * 3 + 1 * 4 = 26
( den Teil versteh ich leider nicht ganz)
Also mal gedanklich das ganz als Baum vorgestellt, hätte ich links 16 knoten (15+ das letzte Child (Element 32) und rechts 15 Knoten.... dazu + einmal die Wurzel = 32 Elemente.
Somit könnte der 3. größte Schlüssel 17 Positionen inkl. seiner derzeitigen der Wurzel und + das eine Blatt der letzten Knotenebene (Element 32) einnehmen.
Wenn man davon ausgeht das upheap wie downheap auf das element losgelassen wird.
Sollte nur Downheap gehen dann fällt die wurzel weg = 16 Positionen.
das 3. kleinste Element, was auch im rechten Teilbaum wäre, könnte 25 nicht einnehmen.
wenn man davon ausgeht das upheap und downheap losgelassen wird.
Denn es kann durch diese Operationen lediglich 7 Positionen einnehmen
bei 32 möglichen Positionen macht das 25 ...
De linke teilbaum fällt weg (ausgenommen element 32) und vom rechten teilbaum der linke zweig vom 7. größten und 3. Größten Schlüssel...
==========
So wenn das da oben von mir ÜBERHAUPT richtig ist kann man das sicher geschickter erklären... kann mir da wer helfen bitte ?
- Welche Positionen können von dem drittgrößten Schlüssel in einem Heap der Größe 32 eingenommen werden?
-
sodelle...
ich hab da jetzt was zusammen geschustert... und rumprobiert bis zum get no...
ich weiß wie der Quicksort an für sich laufen soll... und hab irgendwie das gefühl ich mach was falsch.. aber es funkioniert..
Quick Sort:
- ermittle median(pivot) element (links + rechts)/2
dabei steht links für das erste und rechts für das letzte element des "Arrays" oder beim Rekursiven Aufruf "Teil-Array"
- teile jetzt nach links und rechts auf
- links kleiner gleich (also zweiter string ist "größer" oder gleich string 1)
=> findest du eins was nicht passt hold on und geh zu nächsten while
- recht größer gleich (also erster string ist "größer" oder gleich string 1)
=> findest du eins was nicht passt hold on und TAUSCHE
mach das so lange wie du falsche elmente findest..
rufe nun rekursiv auf und bis weniger als 2 elemente da sind...
--------------
glaub so müsste das richtig sein...
und so hab ich das jetzt umgesetzt.. btw darf ich das mit der for schleife wegen dem break so handeln ?
void quicksort( int links, int rechts, sP *arP) { int l, r; sP pivot, temp; if( rechts > links) { pivot = arP[rechts]; l = links-1; r = rechts; for( ; { while((r > l) && (strcmp(arP[++l].pPD->cName, pivot.pPD->cName) <= 0)) ; while((r > l) && (strcmp(arP[--r].pPD->cName, pivot.pPD->cName) >= 0)) ; if( l >= r) break; temp = arP[l]; arP[l] = arP[r]; arP[r] = temp; } arP[rechts] = arP[l]; arP[l] = pivot; quicksort( links, l-1, arP); quicksort( l+1, rechts, arP); } } [/code]
-
bin grad am rumtesten...
derweil hier mal mein bubble...
void bubbleP(sP *arP, int lenP) { int i; sPD *pTempPD = (sPD*) malloc(sizeof(sPD)); while(lenP--) for(i = 1; i <= lenP; i++) if((strcmp(arP[i-1].pPD->cName, arP[i].pPD->cName)) > 0) { pTempPD = arP[i].pPD; arP[i].pPD = arP[i-1].pPD; arP[i-1].pPD = pTempPD; } }
brauch für 100.000 elemente satte 245 sekunden -.-
scheint mir grad n bischen zu happig
achja lenP ist die länge des Pointer array was zur laufzeit der main() ermittelt wird..
-
?
also die Vergleichsfunktion oben nutze ich lediglich für qsort() aus der stdlib.h ...
das funktioniert auch alles nur muss ich mir jetzt quasi ein my_quicksort() basteln...
und zu deiner strcmp() Frage...
char zeiger ist nicht anderes als char[] ...
sprich ich übergebe die adresse vom ersten Element des Strings... und strcmp() vergleicht Element für Element mit dem andern String bis ein /0 gelesen wurde...
strcmp liefert:
Element1 = Element2
rerun 0
Element1 > Element2
return 1
Element1 < Element2
return -1
-
ok da sieht das so aus...
aber keine Angst ich sorge schon dafür das ein sPD genügend Speicher zugewiesen bekommt..
und zwar in der Funktion die mir jeweils einen sPD mit Daten füllt und danach den Pointer auf dieses Element im Pointer Array speichert..
-
Moinsen,
ich hab da leider mal wieder n Problem... in C-Programmieren -.-
diesmal mit der Umsetzung von quicksort ohne qsort aus der stdlib...
folgende Struktur liegt zu Grunde:
typedef struct sP { struct sPD *pPD; }sP; typedef struct sPD { char cName[50]; }sPD;
nun habe ich ein Array dieser Form:sP *arP = (sP*)malloc(100000*sizeof(sP));
Sprich ich habe ein Array aus Pointern die jeweils auf einen Datensatz Zeigen (dahinter hängt noch was dran, ist ja aber für das sortieren egal... sprich ich muss die Pointer sortieren nach vergleich der Datensätze auf die sie zeigen... BubbleSort klappt... qSort stdLib auch... zb ist für qsort() dies hier meine Vergleichsfunktion:int vergleichP(const void *Str1, const void *Str2) { sP *pP1 = (sP *)Str1; sP *pP2 = (sP *)Str2; return strcmp(pP1->pPD->cName, pP2->pPD->cName); }
hoffe ihr könnt mir auf die Sprünge helfen...
-
Hallo,
ich steh hier grad voll aufm Schlauch...
Ich versuche ein struct Array in einer Unterfunktion zu erweitern...
ich glaube ich habe da jetzt grundsätzlich n Brett vorm Kopf...
ich raffe meinen Code mal zusammen.. sollte eigentlich langen..
hoffe Ihr könnt mir helfen
das hier ist die Struct
typedef struct sK { int iKID; struct sKD *pKD; }sK;
so initialisiere ich den Array Pointer in der Main halt einfach einen Pointer vom Typ SK.. ini mit NULLsK *arK = NULL; int lenK = 0;
Dies ist der Kopf meine Prototyp Funktionvoid einlesen(const char *dateiname, sK *arK,int *lenK);
und so rufe ich die Funktion aufeinlesen(inputfile1,arK,&lenK);
in der Funkion an sich lese ich eine CSV mit Fgets ein und Stroke die ";" zum zwischenspeichern der Tokens lege ich mir in der Funktion ne Temp Variable vom Typ pKD an.sKD *pTempKD = (sKD*) malloc(sizeof(sKD));
nach dem lesen mache ich jetzt folgendes...(*lenK)++; arK = (sK*) realloc (arK, *lenK * sizeof(sK)); arK[*lenK-1].iKID = *lenK; arK[*lenK-1].pKD = pTempKD;
Ich mach anscheinend was falsch beim übergeben...
oder mit dem Temp Pointer...
naja jedenfalls schaut es so aus das ich in der Funktion auf das struct array zugreifen kann...
in der main funktion bekomme ich n Bad ACCESS
-
Aber der andere von lilith ist echt schöner...
bin auch gerade dabei meinen neu zu schreiben, den poste ich dann auch nochmal...
trotzdem nochmal ein dickes Dankeschön !
-
Moin,
erstmal vielen vielen dank für eure Mühen!!
Ich hab für mich mittlerweile heraus gefunden warum er mal n leeren string erzeugt...
hier:
i
nt i, len = rand() % (size - 1); for ( i = 0; i < len; ++i )
lasse ich ihm ja eine zufällige länge des strings generieren...
die länge kann auch 0 sein *Schlag an die Stirn"
-
Moin,
hatte n bischen viel um die Ohren...
Erstmal vielen dank dafür das du dir die Zeit genommen hast um dich mit meinem Problem zu befassen..
Ich werd mir das erstmal alles anschaun und melde mich später nochmal...
Nur was ich noch sagen wollte, mein C-Lehrbuch sagt irgendwie "fgets niemals gar nicht überhaupt nicht nehmen weil übel"
eine richtige Begründung führen die aber nicht an...
und jub muss i C sein....
iAlter und cName etc. muss ich leider so machen (Wurde angewiesen den Code so "leichter" lesbar zu machen)
Den XML C parser schau ich mir gleich mal an, aber ich glaub das teil ist wie soll ich sagen zu "heavy"...
hab mal so etwas in Verbindung mit fscanf gelesen:
%[^;];%[^;];%[^\n]\n
nur versteh ich den einsatz nicht ganz...
auch nach dem hier nicht ganz B..4 Formatstring fr scanf(), fscanf, etc.
.....
öhm ja MIN MID und MAX sollen Konstanten sein, das wurde uns so beigebracht.
-
"C - Programmieren"
Moin,
ich seh den Wald vor lauter Bäumen äh chars nicht mehr...
kann mir wer auf die Sprünge helfen, warum mir das hier in regelmäßigen abständen ein leeres Array erzeugt...
Ich wollte es so dynamisch wie möglich halten...
Die Generatorfunktion
char *rand_str(char *dst, int size) { static const char text[] = "abcdefghijklmnopqrstuvwxyz" "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; int i, len = rand() % (size - 1); for ( i = 0; i < len; ++i ) { dst[i] = text[rand() % (sizeof text - 1)]; } dst[i] = '\0'; return dst; }
und hier n Teil aus der main wo ich die funktion nutze...int main (void) { char genChar[10]; srand(time(0)); ... .... strcpy(pTempPatientenkrankheit->pNext->cName, rand_str(genChar, sizeof genChar)); strcpy(pTempPatientenkrankheit->pNext->cDiagnose, rand_str(genChar, sizeof genChar)); ... ... return 0; }
dies sorgt für die Ausgabe des Struct in einer Datei für schöne ;;; in gewisser Regelmäßigkeit...
-
"C - Programmieren"
Moin,
Ich möchte gern eine CSV Datei einlesen.
Diese kann ich selber generieren, also wenn ihr Vorschläge habt wie ich das doch besser machen sollte... immer her damit.
50;5 Mqnmsebw;Wxeucquu;4;3;Besgvijm Str.;19;2;Rigfwkdv;+;1;K1;D1;2;K2;D2;3;K3;D3;4;K4;D4;5;K5;D5 Iaphhnll;Gawwknjm;8;6;Bvuprmie Str.;19;4;Bnctgswy;+;1;K1;D1;2;K2;D2;3;K3;D3;4;K4;D4;5;K5;D5 Psbvcrri;Xrxrszmk;12;9;Fnocvfga Str.;5;6;Mqllxikg;+;1;K1;D1;2;K2;D2;3;K3;D3;4;K4;D4;5;K5;D5 Rtsqqkle;Shgvufpa;16;12;Slxzmzrd Str.;16;8;Dqbwzjmt;+;1;K1;D1;2;K2;D2;3;K3;D3;4;K4;D4;5;K5;D5
So in etwa kann sie aussehen... Die erste Zeile enthält Infos über die Anzahl der Datensätze und die maximale Anzahl der Variablen Attribute. Kurze Erläuterung: Alles bis zum ;+; sind "feste" Werte... deren Anzahl ändert sich nicht... Nachname;Vorname;Gewicht;Geburtsdatum;Straße;Hausnummer;PLZ;Ort ;+; Alles was dann kommt können beliebig viele Attribute sein welche aber zu dem Datensatz gehören. Sie kommen immer in Paaren vor sprich wenn es ein K1 gibt dann gibt es ein D1 (Krankheit1 und Diagnose1) Sprich das erste sind Patienten Daten und das nach dem + sind dann seine beliebig vielen Krankheiten. Der generator ist noch nicht perfekt (Dazu kommt bestimmt später auch noch eine Frage) Hier einmal das Struct:#define MAX 150 #define MID 100 #define MIN 50 typedef struct sPatientenkrankheit { char cName[MID]; char cDiagnose[MAX]; struct sPatientenkrankheit *pNext; }sPatientenkrankheit; struct sPatient { char cNachname[MIN]; char cVorname[MIN]; int iGewicht; int iGeburtstag; // JJJJMMTT oder als cGeburtstag char cStrasse[MAX]; int iHausnummer; int iPLZ; char cOrt[MID]; struct sPatientenkrankheit *pPatientenkrankheit; };
Ich lege ein Array an was den Werten der Ersten Zeile der Datei entspricht hier jetzt grad [50]... z.B.struct sPatient arPatient_A[iAnzahlP];
ich versuche das ganze jetzt mit fscanf() zu lesen... und komm einfach nicht weiter.. ich weiß es gibt da irgendwie so Schablonen, aber keine Ahnung wie man die richtig verwendet. Meine Vorstellungen wie das eingelesen werden soll: 1. geh in die Erste Zeile 2. Lese den Wert bis Semikolon und speicher in iX Lese den Wert nach dem Semikolon bis zum "lf" und speicher in iKL 3. Lege ein arPatient[iX] an. Merke dir iKL als maximale Anzahl an Krankheiten die Patient haben kann... später vielleicht als Zählvariable zu gegrauchen - int i = 0 4. gehe in die zweite Zeile 5. Lese den Wert bis Semikolon und Speicher in arPatient.cNachname 6. Ignoriere das Semikolon 7. Lese den dann folgenden Wert bis Semikolon und speicher in arPatient.cVorname ... ... 8. Lese den dann folgenden Wert bis Semikolon und speicher in arPatient.cOrt 9. Ignoriere das Semikolon 10. Erstelle weil + nun ein Zeiger auf die erste Krankheitsliste des arPatient i'ten PatientenarPatient_A[i].pPatientenkrankheit->pNext = NULL; struct sPatientenkrankheit *pTempPatientenkrankheit; pTempPatientenkrankheit = arPatient_A[i].pPatientenkrankheit;
11. Ignoriere das Semikolon
12. Lese den dann folgenden Wert bis Semikolon und speicher in
pTempPatientenkrankheit->pNext->cName
14. Ignoriere das Semikolon
12. Lese den dann folgenden Wert bis Semikolon und speicher in
pTempPatientenkrankheit->pNext->cDiagnose
14. Ignoriere das Semikolon
15. Lege zeiger auf nächsten Listeneintrag und lese weiter aus datei so wie eben bis du ein LF (line feed) findest..
wenn ja geh in die zweite Zeile und und mach das ganze für Patienten i = 2
Mein Probrlem ist halt der Mix aus char und int und der variablen anzahl an Krankheiten...
oben steht lediglich die MAXIMALE Anzahl die ein Patient haben kann... er kann also auch nur 3 haben..
könnt ihr mir helfen... ?
-
Es ist ein Aufgabenblatt...
ich hab alles was drauf steht in den ersten Post kopiert...
ausm Prof hab ich jetzt nur rausbekommen nutzt ne CSV Datei zum einlesen.. mehr nicht...
und macht am besten n struct im array und die interessen der person als liste im struct...
aber das nur kurz gesagt zwischen tür und angel...
deswegen hab ich es dort aufgegeben und suche nun hier hilfe...
weil ich kein plan hab wie er das meint...
wie gesagt ich haben die grobe Aufgabenstellung (siehe Post 1... hinzu kommt als Punkt 4 setzte das Projekt in C um)
-
hmm das ne gute Frage...
das ist aus der Aufgabenstellung nicht genau ersichtlich...
Entweder ist die Beschreibung zum Interesse vorgegeben und hängt quasi an ihr...
oder sie ist so gewollt als würde sie die Beziehung der Person zu dem Interesse beschreiben...
Variante 1 (Als Attribut an Interesse):
Kevin -> Fußball (Ballsportart)
Variante 2 (Als Attribut an die Beziehung):
Kevin -> spielt sogar im Verein -> Fußball
oder die Grobe Kelle
Variante 2 (Als Attribut an die Beziehung und an das Interesse):
Kevin -> (spielt sogar im Verein) -> Fußball (Ballsportart)
ich glaub da hab ich freie Hand...
was wäre denn am besten ?
-
Semester Projekt Programmieren
-
-
ich füge nochmal fix Attribute hinzu...
-
yes sollte ne verkettete Liste sein..
ok mal pur ER-Modell dann wäre meine verkettete Liste ja die Beziehung... abgebildet als Verknüpfungstabelle (später)
also 2 Entitäten: Person und Interesse... dazwischen eine n:m Beziehung..
-
Ich kenn den Begriff von Datenbanken her... (Beziehungen und Typen festlegen)
1-N = 1 bis beliebig viele..
meinst du dann so etwas... (vielleicht nicht gerade hübsch)
-
genau das ist es...
ich bin mit dieser Aufgabe überfordert, aber machen muss ich sie trotzdem :/
deswegen such ich ja Hilfe...
Zum Interesse hatt ich mich auf 5 festgelegt obwohl da steht 1-N weil ich nur so überhaupt ne Ahnung habe wie ich die Datei lesen könne :/
Ich weiß ich denk schon wieder über das einlesen nach..
Und jub, ich habe so etwas noch nie gemacht...
-
Den Entwurf/Analyse was das Programm machen soll und wann (Dialog mit dem Nutzer) hab ich...
Quasi eine Auflistung von Funktionen (lediglich eine Namensgebung was sie können müsste, nicht wie)
Und bei den Dateien dacht ich auch erst an einer Textdatei, in der Die zu Lesenden Daten folgendermaßen organisiert sind:
Nachname
Vorname
Geburtsdatum
Strasse
Hausnummer
PLZ
Ort
Interesse1
Beschreibung1
Interesse2
Beschreibung2
Interesse3
Beschreibung3
Interesse4
Beschreibung4
Interesse5
Beschreibung5
Damit ich die einzelnen Attribute explizit von einander trennen kann nutze ich das Semikolon
Nachname;Vorname;Geburtsdatum;Strasse;Hausnummer;PLZ;Ort;Interesse1;Beschreibung1;Interesse2;Beschreibung2;Interesse3;Beschreibung3;Interesse4;Beschreibung4;Interesse5;Beschreibung5
Damit ich weiß wann ein "zusammenhängender" Satz also alle Infos zu einer Person aufhören und eine neue Person beginnt, nehme ich en linefeet
sprich sobald ein Zeilenumbruch erfolgt beginnt eine neue Person...
Beide Dateien sind so aufgebaut nur sind sie nicht nach Namen sortiert...
Das Programm sollte nun als erstes über eine Funktion diese Datei öffnen und Wert;Wert;Wert einlesen können...
Und diese Daten dann in der gleichen Reihenfolge wie in der Datei zwischenspeichern können...
Die zwischengespeicherten Daten sollen sortiert werden können über eine Funktion sortienName() und sortierenInteresse()
Ist das passiert soll es dies auch mit der zweiten Datei noch einmal so machen...
Nun soll es die Möglichkeit geben beide Dateien zusammen zu führen, dafür soll gefragt werden wonach die ausgegebene Datei sortiert werden soll... Damit beide Dateien vor dem zusammenführen gleich sortiert sind und nicht eine nach namen und eine nach Interessen.
Dann sollen die Daten ähnlich einem Reißverschlussverfahrens in eine Neue Datei geschrieben werden... so das sie in der richtigen Sortierung in der neuen Datei vorhanden sind...
Alle Dateien sollen auch ohne das Programm lesbar und verständlich sein...
-----
Meinst du so ?
-
Aber ich muss doch wissen was überhaupt möglich ist... :/
Ich dachte Das Datenmodell ist genau das wie ich mit den Dateien umgehen will und wie diese aufgebaut sein sollen...
dazu muss ich doch wissen wie ich die Dateien einlesen kann und wie die Daten vorhanden sein müssen damit ich sie mit einer geeigneten Methode abspeichern kann... und das ganze so das ich sie zur Weiterverarbeitung sortieren kann...
-
Mein Problem ist das ich was C angeht derweil noch recht laienhaftes Wissen habe, und daher nur bedingt konkrete Aussagen über den Systemaufbau geben konnte.
Überlegungen:
CSV Dateien zum einlesen erstellen
Atribute mit Semikolon getrennt
1 Datensatz je Zeile
Beide Dateien sortieren mit Quicksort
zusammenführen mit Mergesort
Ausgabe als CSV
aber wie ich das konkret mache... kein plan...
und vorallem das sortieren nach den Interessen
Denn ich hab keine Vorstellung wie ich die Datensätze dann im Array abbilden soll.. oder ob der Gedanke mit dem Array völlig bescheuert ist..
das wäre dann ja ne List in ner Struct in einem Array oder sowas für die Interessen..
Wenn ich das gedacht mal in Excel übertrage habe ich ein Datensatz pro Zeil in jeder Spalte ein Attribut, nur in einer Spalte sind in einer Zelle 5 Attribute als Aufzählung untereinander...
kein plan wie ich so alle Datensätze nach Interessen sortieren soll...
Heap Algo - Hilfe bei Übungen aus dem Sedgewick
in Algorithmik
Geschrieben · Bearbeitet von Dionysos211
Ok ich versuch die Antwort mal neu zu formulieren...
Grundlegende Betrachtung zum gegebenen Heap:
Aufgaben Teil a.)
Aufgaben Teil b.)
Somit finde ich die Aufgabe irgendwie schwer zu zu beantworten, weil somit implizit gesagt wurde das das jeweils beschriebene Element in Aufgabenteil a.) und b.) eigentlich nirgends hin kann da es sich bereits an der richtigen stelle befindet...
Eine gültige alternative Position könnte höchstens der Vaterknoten sein. Da die Heapbedingung an dieser Stelle besagt, dass der Nachfolgeknoten kleiner sein muss oder gleich groß wie das Knotenelement.. was ja an der Stelle der Fall sein könnt bei Aufgabenteil b.)
alles n bischen "strange"... kann mir wer ausm Dilemma helfen ?
Ich finde auch keine Lösung dazu im Netz... -.-
Wenn es wirklich nur ums hochschieben und runterschieben geht, und das auch in einem Schritt bis Ende dann bedeutet das für
Aufgabenteil a.)
+ runterschieben (14)
+ hochschieben (1)
+ sich selbst
= 16 mögliche Positionen
Aufgabenteil b.)
+ runterschieben (0) es ist ein Blatt
+ hochschieben (4)
+ sich selbst
= 5 mögliche Positionen
und nun der Clou da steht j ein nicht also ist die Antwort: Es gibt 27 Positionen die er nicht einnehmen kann (32 gesamt - 5 möglich)
wenn ich abwechselnd up und down heap benutzen könnte dann wären schlichtweg alle Positionen möglich...
boa ... *confused* hoch 3