Dionysos211

Ok ich versuch die Antwort mal neu zu formulieren... Grundlegende Betrachtung zum gegebenen Heap: 32 Elemente 16 Knoten 16 Blätter Tiefe 6 Aufgaben Teil a.) 3. größter Schlüssel (3. Knoten bzw. 2. Knoten nach der Wurzel) Aufgabenstellung besagt die vorangegangenen Schlüssel sind größer. Somit handelt es sich um einen Heap-Max Aufgrund der Heapbedingung ist anzunehmen das die Folgeelemente kleiner sind. Aufgaben Teil b.) 3. kleinster Schlüssel (14. Blatt bzw. linker Nachfolger des 15. Knotens) Aufgabenstellung besagt die nachfolgenden Schlüssel sind kleiner. Es ist anzunehmen das es sich auch hier um einen Heap-Max handelt. Aufgrund der Heapbedingung ist anzunehmen das alle Vorgänger größer sind. 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

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: verstehe 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 ?

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 NULL sK *arK = NULL; int lenK = 0; Dies ist der Kopf meine Prototyp Funktion void einlesen(const char *dateiname, sK *arK,int *lenK); und so rufe ich die Funktion auf einlesen(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 Patienten arPatient_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)