Stosy, listy

Przygotuj funkcje push(stos, element), pop(stos, element), które odpowiednio pozwalają na umieszczenie na stosie stos i zdjęcie z niego elementu element w postaci liczby całkowitej, oraz funkcje empty(stos), print(stos), które pozwalają na uzyskanie informacji, czy stos jest pusty oraz wyświetlenie na standardowym wyjściu elementów znajdujących się na nim.

Stos powinien zostać zrealizowany z wykorzystaniem dynamicznej listy jednokierunkowej. Wszystkie funkcje z wyjątkiem funkcji print, która ma charakter pomocniczy, mają dostęp jedynie do początku listy. W zastępstwie funkcji empty można dostarczyć funkcję pop, której zwracana wartość będzie informowała o tym, czy stos jest pusty czy nie.

Czy pytanie brzmi: - Gdzie znajdę jełopa który za darmo odwali całą pracę za mnie?

http://www.algorytm.org/klasyczne/stos.html

Zacząłem od funkcji push i wywala mi naruszenie ochrony pamięci, nie mam pojecia dlaczego.

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

typedef struct element {
   struct element *next;
   unsigned int liczba;
 } el_listy;
 
el_listy *first;



void push (el_listy *lista,int *a){
  el_listy *wsk, *nowy;
  wsk=lista;
  while(wsk->next != NULL)
    wsk=wsk->next;
 
  nowy=malloc(sizeof(el_listy));
  nowy->liczba=*a;
  nowy->next=NULL;
  wsk->next=nowy;
}

  int main(){
  int *a;
  printf("Podaj liczbe, ktora chcesz dodac na stos\n");
  scanf("%d",a);
    push(first,a);
    return 0;}

#include <stdio.h>
#include <stdlib.h>
 
typedef struct element {
   struct element *next;
   unsigned int liczba;
 } el_listy;
 
el_listy *first=0; // koniecznie, oznacza że lista pusta
 
el_listy *push (el_listy *lista,unsigned int a) // po kiego liczbę przekazywać przez wskaźnik? Element trzyma unsigned int więc tu ma być to samo.
  {
  el_listy *nowy;
  // wsk=lista; while(wsk->next != NULL) wsk=wsk->next; // To jest nie poprawne, poza tym dodawanie na koniec ...  albo dodaj dodatkowy wskaźnik na koniec albo dodawaj na początek
 
  nowy=malloc(sizeof(el_listy));
  nowy->liczba=a; 
  nowy->next=lista;
  return nowy;
}
 
 int main()
  {
   int a; // miałeś wskaźnik na losowy obszar pamięci
   printf("Podaj liczbe, ktora chcesz dodac na stos: ");
   scanf("%d",&a); // a tu pod ten losowy wskaźnik wpisywałeś dane
   first=push(first,a); // push może zmienić adres pierwszego elementu, np kiedy lista jest pusta.
   return 0;
  }

Wszystko ok tylko ja muszę dodać ten element na, stos czyli na koniec listy a nie na jej początek.

 #include <stdio.h>
#include <stdlib.h>
 
typedef struct element {
   struct element *next;
   unsigned int liczba;
 } el_listy;
 
el_listy *first=0; // koniecznie, oznacza że lista pusta
 
el_listy *push (el_listy *lista,unsigned int a) // po kiego liczbę przekazywać przez wskaźnik? Element trzyma unsigned int więc tu ma być to samo.
  {
 el_listy *wsk, *nowy;
  wsk=lista;
  while(wsk->next != NULL)
    wsk=wsk->next;
 
  nowy=malloc(sizeof(el_listy));
  nowy->liczba=a;
  nowy->next=NULL;
  wsk->next=nowy;
}
 
 int main()
  {
   int a; // miałeś wskaźnik na losowy obszar pamięci
   printf("Podaj liczbe, ktora chcesz dodac na stos: ");
   scanf("%d",&a); // a tu pod ten losowy wskaźnik wpisywałeś dane
   first=push(first,a); // push może zmienić adres pierwszego elementu, np kiedy lista jest pusta.
   return 0;
  }

Dalej nie gra.

Mylisz pojęcia: stos, lista, lista jednokierunkowa.
stos - to pojęcie abstrakcyjne, zasada wrzucania, ostatni wszedł - pierwszy wyszedł (LIFO)
lista - to pojęcie abstrakcyjne, zasada wrzucania, pierwszy wszedł - pierwszy wyszedł (FIFO)
lista jednokierunkowa - konstrukcja danych w pamięci komputera, za jej pomocą da się zrealizować stos oraz listę.
Dla listy jednokierunkowej pojecie początek i koniec są umowne, czyli zmień nazwy zmiennych first na last zaś next na prev, ba nawet zmieniać nie musisz, przecież dla komputera nie ma to znaczenia.
Więc musisz wykorzystywać możliwości listy jednokierunkowej.
W przypadku stosu, dodajesz na początek i zabierasz z początku, jeżeli ci to przeszkadza to zmień nazwy jak powiedziałem wyżej.

Chciałbym teraz zdjąć ten dopisany element, napisalem funkcje ale ona faktycznie nie zdjela tej liczby bo potem mam funkcje print ktora wypisuje elementy listy i wypisala mi tą liczbę którą sobie dopisałem..
A jak mogę sprawdzić czy stos jest pusty?

 void pop (el_listy *lista, int element){

  el_listy *wsk=lista;
  while(wsk->next != NULL)
    {    
    if (wsk->next->liczba==element)
      { 
	el_listy *usuwany=wsk->next;
        wsk->next=usuwany->next;
        free(usuwany);
      } else
      {
	wsk=wsk->next;
      }
    }
}

 void print(el_listy *lista)
 {
   el_listy *wsk=lista;          /* 1 */
   while( wsk != NULL )          /* 2 */
     {
     printf ("%u\n", wsk->liczba); /* 3 */
     wsk = wsk->next;            /* 4 */
     }                           /* 5 */
 }

 
 int main()
  {
   int a; // miałeś wskaźnik na losowy obszar pamięci
   printf("Podaj liczbe, ktora chcesz dodac na stos: ");
   scanf("%d",&a); // a tu pod ten losowy wskaźnik wpisywałeś dane
   first=push(first,a); // push może zmienić adres pierwszego elementu, np kiedy lista jest pusta.
   
   pop(first,a);
   print(first);
return 0;

  }

Jeżeli to ma być stos, to zdejmujesz z tego samego końca, czyli żadnych pętli.
if(!first) // jeżeli stos pusty
pop też może zmienić początek listy, oraz przekazać wartość:
first=pop(first,&a);
el_listy * pop (el_listy *lista, unsigned int *element) {...
W funkcji print nie potrzebujesz dodatkowych wskaźników:
void print(el_listy *lista)
{
for(;lista;lista=lista->next) printf ("%u\n",wsk->liczba);
}

Dobra , odświeżam temat. Chcę po prostu wrzucić trzy liczby na stos, potem zdjąć z niego jeden i wyswietlic elementy stosu. Daje np 1 2 3 ( powinno zdjac 3 i wyswietlic mi 2 i 1. Tymczasem program po wczytaniu 3 liczb konczy dzialanie) W sytuacji gdy usunę wywołanie funkcji pop to wyswietla te trzy liczby, czyli proces wrzucania liczb do listy przebiega ok .Oto mój kod. :

#include <stdio.h>
#include <stdlib.h>
 
typedef struct element {
   struct element *next;
   unsigned int liczba;
 } el_listy;
 

el_listy *first=0; 
 
el_listy *push (el_listy *lista,unsigned int a) 
  {
  el_listy *nowy;

  nowy=malloc(sizeof(el_listy));
  nowy->liczba=a; 
  nowy->next=first;
  return nowy;
}

el_listy *pop (el_listy *lista, unsigned int element){
el_listy *wsk=lista;
  while(wsk->next != NULL)
    {    
    if (wsk->next->liczba==element)
      { 
        el_listy *usuwany=wsk->next;
        wsk->next=usuwany->next;
        free(usuwany);
      } else
      {
        wsk=wsk->next;
      }
    }
}


 void print(el_listy *lista)
 {
   el_listy *wsk=lista;          /* 1 */
   while( wsk != NULL )          /* 2 */
     {
     printf ("%u\n", wsk->liczba); /* 3 */
     wsk = wsk->next;            /* 4 */
     }                           /* 5 */
 }
 



 int main()
  {
   int a;
   printf("Podaj liczbe, ktora chcesz dodac na stos: ");
   scanf("%d",&a); 

   first=push(first,a);

   printf("Podaj liczbe, ktora chcesz dodac na stos: ");
   scanf("%d",&a); 

   first=push(first,a);
  
 printf("Podaj liczbe, ktora chcesz dodac na stos: ");
   scanf("%d",&a); 

   first=push(first,a);
  
 
  

   first=pop(first,a);

 print(first);


return 0;

  } 

Nie zrozumiałeś pojęcia pop.
Pop ma ci pobrać ostatnio dodany element, nie wyszukiwać nic na liście, zdjąć ten jeden z góry i to wszystko.
el_listy *pop (el_listy *lista, unsigned int *element) { ... }
first=pop(first,&a);
printf("pobrano %d\n",a);

Toz to zadanie ze spoja prawie ;)

http://pl.spoj.com/problems/PROGC03/

W sumie bardziej podobne do tego

http://pl.spoj.com/problems/STOS/

Jesli chcesz dynamiczna liste jednokierunkowa to uzyj STLowej listy i masz tam metody push_back pop_back, ktore mozesz upakowac do wlasnych metod pop/push i tyle.

Działa, wystarczyło usunąc linijkę z while (..) w funkcji pop.

Dobra powiedzmy, ze chce to sobie fajnie pukladac i podzielic na moduły.
Wiec w main dodaje na samym pcozątku taką deklarację :

el_listy first=0; 

Tworzę plik struct.h a w nim :

 ypedef struct element {
   struct element *next;
   unsigned int liczba;
 } el_listy;
 

A w pliku push.c z definicją funkcji :

 #include <stdio.h>
#include <stdlib.h>
#include "struct.h"
#include "push.h"



el_listy *push (el_listy *lista, unsigned int a) {
  
  el_listy *first;
  
  el_listy *nowy;

  nowy=malloc(sizeof(el_listy));
  nowy->liczba=a; 
  nowy->next=first;
  return nowy;
}

Uruchamiam prog, daje mu 3 liczby i wywala naruszenie ochrony pamięci. DLaczego? Przeciez poprawnie przekazane są parametry itp.

el_listy first=0; // main cpp albo jeszcze lepiej przenieść wewnątrz main'a
typedef struct element { ... // stos.h
el_listy *push (el_listy *lista, unsigned int a); // stos.h
el_listy *push (el_listy *lista, unsigned int a) { ... // stos.cpp

Czemu nie tak wewnatrz maina ? :

el_listy *first=0;  

Przeciez musze miec wskaznik.

Pozostale rzeczy mam tak jak piszesz i teraz program po prostu konczy dzialanie jakby nigdy nic.

Co ciekawe, gdy zaś pominę wywołanie f. pop ( ona jest teraz w main normalnie w glownym pliku), to mam cos takiego :

Podaj liczbe, ktora chcesz dodac na stos: 1
Podaj liczbe, ktora chcesz dodac na stos: 2
Podaj liczbe, ktora chcesz dodac na stos: 3
3
3077785688
Naruszenie ochrony pamięci (core dumped)

A my mamy zgadnąć jak ty teraz tego pop'a napisałeś ?

nic w nim nie zmieniłem w pop

No to NIE MA się czemu dziwić. Ten pop to jakieś nieporozumienie. Kilkakrotnie o tym mówiłem w tym temacie.

nie wiem czy czytasz to uważnie co ja piszę ale gdy usunalem linijke z while, w momencie przed podziałem programu na moduły wszystko śmigało..

Czy ty rozumiesz co do ciebie się mówi?
Ten pop trzeba usunąć w całości i napisać od nowa, w nim jest tylko jeden sensowny wiersz: klamerka kończąca funkcje.
To że ci przypadkiem nie wywaliło przy pewnym układzie tych funkcji w pamięci - niczego nie oznacza.

a co z push ? jest napisane dobrze, tak?! to dlaczego w.momencie gdy usuwam f. pop i wywołuje push i print tylko, to wypisuje mi 3 , jakies smieci i potem jest core dumped?

Ja ci podałem poprawnie działającą wersje push, może ją zignorowałeś, może ją zepsułeś, kryształowa kula w naprawie więc nie wiem.

[EN]
http://www.thegeekstuff.com/2012/08/c-linked-list-example/
http://www.cprogramming.com/tutorial/c/lesson15.html

[PL]
http://pl.wikibooks.org/wiki/C/Typy_z%C5%82o%C5%BCone#Implementacja_listy
http://www.algorytm.org/klasyczne/lista/lista-2-c.html

Minuta googlowania, przeanalizuj.

Czy teraz jest poprawnie ? Dodaje na poczatek listy i usuwam z poczatku dodany ostatnio element.

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


void push (t_elem **wsk_lista, t_elem *elem){

  elem->next=*wsk_lista;
  *wsk_lista=elem;
}



void print(t_elem **wsk_lista)
 {
   t_elem *wsk=lista;          /* 1 */
   while( wsk != NULL ){          /* 2 */     
     printf ("%d\n", wsk->val); /* 3 */
     wsk = wsk->next;            /* 4 */
     }                           /* 5 */
 }

void pop (t_elem **lista, t_elem *elem){

  elem = *lista;
  *lista=(*lista)->next;
}




int main(){

  lista=NULL;



  pom=(t_elem*)malloc(sizeof(t_elem));
  pom->val=5;
  push(&lista,pom);

  pom=(t_elem*)malloc(sizeof(t_elem));
  pom->val=50;      /* Moge dac scanfa przed tym frag i wstawic tu dowolna liczbe*/
  push(&lista,pom);

  pop(&lista,pom);


  print(&lista);
}
 

Bo to co próbujesz zrobić to nie lista zaś jakiś potworek. Nawet main - nie ma sensu.

Tak wygląda moja funkcja pop :

 void pop (t_elem **lista, t_elem *elem){
 
  elem = *lista;
  *lista=(*lista)->next;
}
 

A tak struct.h :

 typedef struct elem {
  int val;
  struct elem *next;
} t_elem;

t_elem *lista, *pom;
\

Jak mam zmodyfikować f. pop, aby zwracała wartosc usuwanego elementu ?
Chodzi o to, żebym mogl w programie napisac cos takiego:

 liczba=pop(&lista,pom); 

??

t_elem *pop (t_elem **lista, t_elem *elem){

  elem = *lista;
  *lista=(*lista)->next;
  return t_elem;
}

Już to mówiłem, kilka postów temu.