Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
30.04.2007, 20:08 Uhr
Pler
Einer von Vielen
(Operator)

Hi!

Ich packs einfach nicht...

Zuerst habe ich das mit memcpy probiert. Da habe ich dann gelesen, dass sich alter und neuer Bereich nicht überlappen sollen. Also nahm ich memmove, da soll das dann gehen; aber es ändert sich einfach nichts.
Der kopiert einfach den Restlichen Speicherinhalt nicht mit. Immer nur das nächste Element...

Hier der Code:

C++:

int *zgr = NULL;
int groesse = 0;

C++:

void append_element(int value)
{
        if(value < 0) {
                return;
        }

        zgr = (int*)realloc(zgr, (groesse + 1) * sizeof(int));

        if(zgr == NULL) {
                return;
        }

        *(zgr + groesse * sizeof(int)) = value;
        groesse++;
}

C++:

int remove_element()
{
        int v;

        if(groesse == 0) {
                return -1;
        }

        v = *zgr;

        memmove(zgr, zgr + sizeof(int), (groesse - 1) * sizeof(int));

        zgr = (int*)realloc(zgr, (groesse - 1) * sizeof(int));

        if(groesse == 1) {
                zgr = NULL;
        }

        groesse--;
        return v;
}

C++:

int main()
{
        append_element(47);
        append_element(11);
        append_element(42);
        append_element(43);
        append_element(44);
        append_element(45);
        printf("remove: %d\n", remove_element());
        printf("remove: %d\n", remove_element());
        printf("remove: %d\n", remove_element());
        printf("remove: %d\n", remove_element());
        printf("remove  %d\n", remove_element());
        printf("remove  %d\n", remove_element());
        printf("remove  %d\n", remove_element());
        append_element(13);
        printf("remove  %d\n", remove_element());

        return 0;
}

shell:

remove: 47
remove: 11
remove: 42
remove: 42
remove  42
remove  42
remove  -1
remove  13

Die Elf kommt also zwei mal. Das würde auch genauso weitergehen, egal wie viel Zahlen nach der Elf noch kommen.

Falls jmd. ganz viel Lust hat, hier gibts den Quellcode

Dieser Post wurde am 30.04.2007 um 20:11 Uhr von Pler editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
30.04.2007, 21:29 Uhr
Kest
saint

Hi!

C++:

void append_element(int value)
{
        if(value < 0) {
                return;
        }

        zgr = (int*)realloc(zgr, (groesse + 1) * sizeof(int));

        if(zgr == NULL) {
                return;
        }

        zgr[groesse++]=value;
}

int remove_element()
{
        int v;

        if(groesse == 0) {
                return -1;
        }

        v = *zgr;

        memmove(zgr, zgr + 1, (groesse - 1) * sizeof(int));

        zgr = (int*)realloc(zgr, (groesse - 1) * sizeof(int));

        if(groesse == 1) {
                zgr = NULL;
        }

        groesse--;
        return v;
}

--
Wenn man einen Hufschlag hört, sollte man >Pferd< denken und nicht >Zebra<.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
30.04.2007, 21:37 Uhr
Pablo
Supertux
(Operator)

Schreckliche Benutzung von realloc:

Mach so

C++:

void append_element(int value)
{
    int *tmp;
    if(value < 0) return;

    tmp = realloc(zgr, (groesse + 1) * sizeof(int));

    if(!tmp) return;

    zgr = tmp;

    zgr[groesse++] = value; /* "fügt" value hinzu und inkrementiert groesse */
}

die remove Funktion sollte ähnlich gehen (bzgl Benutzung von realloc). Aufpassen musst du bei Sachen wie "zgr + sizeof(int)", weil du jetzt Pointerarithmetik betreibst, und das hat das Effekt, dass zgr + sizeof(int) nicht auf die nächste Zahl zeigt sondern auf die 4. Stelle im Array zeigt. Du musst da nämlich zgr + 1 eingeben (der Compiler rechnet da das richtige offset)

C++:

memmove(zgr, zgr+1, (groesse - 1)*sizeof(int));

den Rest solltest du selber hinkriegen.

edit: jemand war ein bisschen schneller als ich

btw. thou shalt not cast a void*. Wenn du (int *) malloc machst, dann gehe ich davon aus, dass du C++ benutzt, und wenn du das tust, dann solltest du lieber new/free nehmen. Außerdem werden malloc/free in stdlib.h definiert und nicht in malloc.h (malloc.h ist nicht stdkonform)
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Dieser Post wurde am 30.04.2007 um 21:43 Uhr von Pablo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
30.04.2007, 21:52 Uhr
Pler
Einer von Vielen
(Operator)

Danke an beide!

Das mit zgr+1 hab ich voll vergessen. Naja. Kann ja passieren.

@Pablo:
Was bringt dein "Zwischenschritt" mit dem tmp-Zeiger? Wegen einer evtl. Freigabe wenn realloc nicht klappt?
Und warum nach realloc nicht casten? Ich dachte, das soll man gerade machen? Und was hat das mit c++ dann zu tun?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
30.04.2007, 22:06 Uhr
0xdeadbeef
Gott
(Operator)

Wie wärs damit?

C++:

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

struct queue_element {
  struct queue_element *prev, *next;
  int content;
};

struct queue {
  struct queue_element *head, *tail;
  size_t size;
};

void queue_construct(struct queue *this);
void queue_destruct (struct queue *this);
void queue_append   (struct queue *this, int x);
int  queue_remove   (struct queue *this);

void queue_construct(struct queue *this) {
  this->size = 0U;
  this->head = malloc(sizeof(struct queue_element));
  this->tail = malloc(sizeof(struct queue_element));

  this->head->prev = this->tail->prev = this->head;
  this->head->next = this->tail->next = this->tail;
}

void queue_destruct(struct queue *this) {
  while(this->size > 0)
    queue_remove(this);
  free(this->head);
  free(this->tail);
}

void queue_append(struct queue *this, int x) {
  struct queue_element *new_element = malloc(sizeof(struct queue_element));

  new_element->content = x;
  new_element->prev = this->tail->prev;
  new_element->next = this->tail;

  new_element->prev->next = new_element;
  this->tail->prev        = new_element;
  ++this->size;
}

int queue_remove(struct queue *this) {
  struct queue_element *item = this->head->next;
  int x;

  if(this->size == 0)
    return -1;

  item->next->prev = this->head;
  this->head->next = item->next;

  x = item->content;
  free(item);
  --this->size;

  return x;
}

int main(void) {
  struct queue q;

  queue_construct(&q);

  queue_append(&q, 1);
  queue_append(&q, 2);
  queue_append(&q, 3);
  queue_append(&q, 4);
  queue_append(&q, 5);
  queue_append(&q, 6);

  while(q.size > 0U)
    printf("%d\n", queue_remove(&q));

  queue_destruct(&q);

  return 0;
}

Weniger Hin- und Herkopiererei auf die Art.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
30.04.2007, 22:11 Uhr
Pler
Einer von Vielen
(Operator)

Danke!

So ne ähnliche Lösung hatte mein Kollege.
Meine Lösung kommt daher, dass ich mich einfach hingesetzt habe, ohne die Aufgabe nochmal zu lesen. Dann war ich fertig.
Aber leider hab ich ein Stack programmiert und keine queue

Und dann hab ichs versucht schnell noch umzuschreiben.

@0xdeadbeef
Denkst du, dass das überhaupt viel bringt so?
Naja, wenns viele Daten sind, wird man das bestimmt merken.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
30.04.2007, 22:16 Uhr
0xdeadbeef
Gott
(Operator)

Auf die Art ist das Einfügen und Rausnehmen immer O(1), wie sich das für eine queue gehört. Ne andere Möglichkeit wäre, ne Position einzuführen und ggf. halt Modulo zu rechnen - das bringt vor allem dann was, wenn Speicher knapp ist. Ansonsten halt ich das so aber für am sinnvollsten - vor allem, wenn man denn mal größere Objekte in die Queue packen will.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
01.05.2007, 02:44 Uhr
Pablo
Supertux
(Operator)

Zitat von Pler:

Was bringt dein "Zwischenschritt" mit dem tmp-Zeiger? Wegen einer evtl. Freigabe wenn realloc nicht klappt?

Angenommen realloc funktioniert n Mal hintereinander. Beim n+1. Mal gibt realloc NULL, weil der Speicher nicht verschoeben/vergrößert/was_auch_immer/ werden kann. Ohne den temp = realloc Trick hättest du den Speicher "verloren", sprich die Adresse, wo der Speicher noch reserviert ist, damit entsteht ein Speicherleck. Außerdem würdest du die ganze Queue verlieren, d.h. wenn du ein Element nicht hinzufügen kannst, dann ist die ganze Liste weg. Das ist nicht im Sinne einer Queue, meiner Meinung nach.

Zitat von Pler:

Und warum nach realloc nicht casten? Ich dachte, das soll man gerade machen? Und was hat das mit c++ dann zu tun?

In C muss man void* nicht casten, weil es implizit gemacht wird. Da malloc ein void* zurückliefert, braucht man malloc nicht zu casten. C++ ist da viel strikter als C, deswegen braucht man in C++ ein Cast vor malloc. Aber wenn man C++ benutzt, dann sollte man auch die C++ Mitteln nehmen, und diese sind new/delete, denn diese Bewirken auch, dass z.b. die Konstruktoren/Destruktoren bei Klassen aufgerufen werden. Ich bin jetzt nicht sicher, aber malloc/free würden das nicht tun, weil malloc/free nichts über Konstrukturen/Destruktoren wissen.

Zitat:

Ne andere Möglichkeit wäre, ne Position einzuführen und ggf. halt Modulo zu rechnen - das bringt vor allem dann was, wenn Speicher knapp ist.

und/oder wenn man einen Ringbuffer schreibt.

@beey: ist es notwenig ein 0U, wenn man 0 mit einem size_t Element vergleicht? Imho ist 0U == 0. Oder hat es etwas mit unnötigen shift Operationen, die der Compiler beim Vergleichen erzeugen würde?
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Dieser Post wurde am 01.05.2007 um 02:47 Uhr von Pablo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
01.05.2007, 03:03 Uhr
0xdeadbeef
Gott
(Operator)

Der einzige Unterschied ist, dass 0U vom Typ unsigned int ist, wo 0 vom Typ int ist. Macht in der Funktion hier keinen Unterschied, aber manche Compiler schmeißen sonst "signed to unsigned conversion"-Warnungen raus, und Lint-Programme nehmen dir sowas generell übel.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
01.05.2007, 03:23 Uhr
Pablo
Supertux
(Operator)

was sind Lint-Programme? Der Begriff Lint sagt mir gar nichts.
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: