C - stos na liscie

0

Witam,
Chciałbym zaimplementować w ISOC99 strukturę działającą tak jak Stack<int> z STL (nie chodzi mi o dokładną kopię, ale o praktyczny kontener) wykorzystując bibliotekę standardową. Robię to by porządnie nauczyć się C.

Planuje, by stos który utworzę był wskaźnikiem, następnie wskaźnik ten podawać jako argument funkcji obsługującej stos, dzięki temu będę miał podobny efekt jakbym wykonywał metodę na obiekcie, którym jest przekazywany argument. Planuję zastosować listę jednokierunkową.

Mam problem z operacją push. Ponieważ jest to stos nowy, zaalokowany węzeł jest wstawiany na koniec listy. W nowo wstawionym wskaźnik na ostatnim elemencie jest ustawiony na NULL. W momencie wstawiania wskaźnik na koniec stosu ma zmieniać adres elementu ->next z NULL na adres nowego węzła. Problem w tym, ze informacja ta nie jest zapamiętywana.

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

int main()
{
  stackroot* root = NULL;
  stackint* top = NULL;
  
  printf("top address before malloc %d\n", top);
  if( initialize_stack(&root, &top) == -1) {
    fprintf(stderr, "Cannot create stack!\n");
    exit(1);
  }
 
  printf("top address %d\n", top);
  push(root, &top, 2);
  printf("After in program: %d\n", top);
  push(root, &top, 3);
  printf("After in program: %d\n", top);
  push(root, &top, 7);
  printf("After in program: %d\n", top);
  push(root, &top, 9);
  printf("After in program: %d\n", top);
  printf("Last element: %d\n", top->value);
  printf("ilosc elementow: %d\n", size(root));
   
  return 0;
}

#ifndef STACK_H
#define STACK_H

typedef struct stackint {
  struct stackint* next;
  int value;
} stackint;

typedef struct stackroot {
 struct stackint* first;
 int size;
} stackroot;

#define STACKSIZE sizeof(stackint)
#define ROOTSIZE sizeof(stackroot)

int initialize_stack(stackroot** root, stackint** top);
int size(stackroot* root);
int push(stackroot* root, stackint** stack,  int value);

#endif  /* STACK_H */
#include<stdlib.h>
#include<stdio.h>
#include "stack.h"

int initialize_stack(stackroot** root, stackint** top)
{
  if( (*root = malloc(ROOTSIZE)) == NULL ) {
    fprintf(stderr, "Cannot allocate memory!\n");
    return -1;
  }
  
  if( (*top = malloc(STACKSIZE)) == NULL ) {
    fprintf(stderr, "Cannot allocate memory!\n");
    return -1;
  }
  
  //set number of elements in empty stack
  (*root)->size = 0;
  // connect root with top node
  (*root)->first = *top;
  
  return 1;
}

int push(stackroot* root, stackint** stack, int value)
{
  stackint* stackNode = NULL;
  if( (stackNode = malloc(STACKSIZE)) == NULL ) {
    fprintf(stderr, "Cannot allocate memory!\n");
    return -1;
  }

  // set value in node
  stackNode->value = value;
  stackNode->next = NULL;
 
  // put in the end
  if(root->size == 0)
    root->first = stackNode;
  else {
    // set top's next as node
    // there seems not to remember
    printf("Before: %d\n", (*stack)->next);
    (*stack)->next = stackNode;
    printf("After: %d\n", (*stack)->next);
  } 
  // increase size 
  ++(root->size);
  
  // return value > 0
  return 1;
}

int size(stackroot* root)
{
  return root->size;
}

Podejrzewam, że problemem jest kwestia kopiowania argumentu, a nie przekazywania przez wskaźnik. Jednoczesnie mam problem z poprawieniem tego.

Wyjscie:

top address before malloc 0
top address 16760880
After in program: 16760880
Before: 0
After: 16760944
After in program: 16760880
Before: 16760944
After: 16760976
After in program: 16760880
Before: 16760976
After: 16761008
After in program: 16760880
Last element: 0
ilosc elementow: 4

Pozdrawiam i dziekuje za podpowiedzi,

0

**stack w procedurze push, jak mi się zdaje, powinno u Ciebie wskazywać na najwyższy element stosu - zauważ jednak, że nigdzie w funkcji nie ustawiasz tego najwyższego elementu i **stack cały czas wskazuje na najniższy element, stworzony w funkcji initialize_stack. Czyli:

  else {
    // set top's next as node
    // there seems not to remember
    printf("Before: %d\n", (*stack)->next);
    (*stack)->next = stackNode;
    printf("After: %d\n", (*stack)->next);
    // set the value of *stack to the node we've just created
    *stack = stackNode;
  }

Powinno działać.

0

Dzieki, w tym tkwil problem. Napisalem funkcje zwalniajaca cala liste zaczynajac od korzenia.

int free_stack(stackroot** stack)
{
  if((*stack)->first != NULL) {
    stackint* tmp = NULL;
    // free elements in the list
    while( tmp != NULL ) {
      tmp = (*stack)->first->next->next;
      free( (*stack)->first->next );
    }
  }

  free((*stack)->first);
  
  // free stackroot
  free(*stack);
  return 1;
}

Bede wdzieczny jak ktos doswiadczony rzuci okiem, bo w sumie mam z tym troche problemow i cwicze, a krytyka zasze sie przyda.

0

na początku funkcji możesz dodać sprawdzanie, czy stackroot nie jest null. w innych prockach też.

   stackint* tmp = NULL;
    while( tmp != NULL ) {

skoro tmp jest null, to pętla się ani razu nie wykona.

0

Dzieki, dopisalem sprawdzanie czy korzen nie jest NULLem. Wykrylem blad w poprzednim kodzie (petla byla nieskonczona) i mam chyba dobra wersje. Po poprawce:

int free_stack(stackroot** stack)
{
  if(stack == NULL) {
    fprintf(stderr, "Stack root seems not to be initialized!\n");
    return -1;
  }
  
  // free 2, 3, 4 .. elements
  if((*stack)->first != NULL) {
    // pointer to free memory
    stackint* ptr = (*stack)->first->next;
    // remember next element after free
    stackint* nextptr = NULL;
    // free elements in the list
    while( ptr != NULL ) {
      nextptr = ptr->next;
      //printf("Loop!\n");
      free( ptr );
      ptr = nextptr;
    }
  }
  
  // free 1 element
  free((*stack)->first);
  
  // free stackroot
  free(*stack);
  return 1;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1