listy jednokierunkowe

Question

mam do napisania 2 funkcje dotyczące list jednokierunkowych.

struct EList{
	int klucz;
	struct EList *nast;
};

budowanie listy w porządku prostym – elementy w liście znajdują się w kolejności ich dodawania, klucze podawane przez użytkownika – wersja nierekurencyjna,

 

sprawdzanie długości listy (funkcja zwracająca informację o liczbie elementów w liście) - wersja rekurencyjna.

POMOCY

Comments

Z chęcią ci pomożemy, ale nie dajemy gotowców. Czego nie rozumiesz? Próbowałeś już coś napisać? Podziel się z nami swoim kodem, jeśli go masz.

---

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

struct EList{
	int klucz;
	struct EList *nast;
};

 
struct EList* dodaj_elem(struct EList*q, int x);
void drukuj_liste(struct EList* q);  
struct EList* usun_elem(struct EList*q, int x);
void drukuj_rek(struct EList *q);
void drukuj_ostatni(struct EList *q);


int main(void){
int  i,x;
struct EList* glowa=NULL;
 
   	
for(i=0;i<5; i++)
  glowa=dodaj_elem(glowa,i);
			  
printf("\n");
drukuj_liste(glowa);
		  
	 
if(glowa!=NULL){
   printf("\nPodaj element do usuniecia: ");
   scanf("%d", &x);
   glowa=usun_elem(glowa,x);
  }
else
printf("Lista pusta");

if(glowa!=NULL){		  
printf("\nDrukowanie listy - od ostatniego do pierwszego elementu");
drukuj_rek(glowa); 
}

if(glowa!=NULL){
printf("\nDrukowanie ostatniego elementu listy");
drukuj_ostatni(glowa); 
}




return 0;
}

//------------------------------------------------------
struct EList* dodaj_elem(struct EList*q, int x){
struct EList*pom;
pom=(struct EList*)malloc(sizeof(struct EList));
pom->klucz=x;
pom->nast=q;
q=pom;
return q;
}

//------------------------------------------------------
void drukuj_liste(struct EList* q){
struct EList*pom;
int i=0;
pom=q;
if(pom==NULL)
  printf("\nLista pusta");
else{
  printf("\nElementy listy:");
  while(pom!=NULL){
	 printf("\nElement nr %d: %d",++i,pom->klucz);	
	 pom=pom->nast;
    }
  }
}
 
//------------------------------------------------------
struct EList* usun_elem(struct EList*q, int x){
struct EList*pom, *tmp;
pom=q;
while (pom !=NULL && pom->klucz!= x){
      tmp=pom;
	  pom=pom->nast;
	} 
if(pom!=NULL){
   if (pom == q)
      q=pom->nast;
   else
      tmp->nast=pom->nast;
      
   free(pom);
}
else
   printf("Elementu %d nie ma w liscie", x);
return q;
}
 
//------------------------------------------------------
void drukuj_rek(struct EList *q){
if(q!=NULL){
  drukuj_rek(q->nast);		
  printf("\n%d",q->klucz);	
  }
}

//------------------------------------------------------
void drukuj_ostatni(struct EList *q){
if(q->nast==NULL)
  	printf("\n%d",q->klucz);	
else
  drukuj_ostatni(q->nast);
}

i musze jeszcze dopisac te 2 funkcje i za bardzo nie mam pomyslu na nie

Answer 1

budowanie listy w porządku prostym – elementy w liście znajdują się w kolejności ich dodawania, klucze podawane przez użytkownika – wersja nierekurencyjna

Jeśli dobrze rozumiem, chodzi o prostą funkcję dodającą elementy do końca listy (zastępujące jej ogon). Przecież w kodzie opublikowanym w komentarzu takowa funkcja się znajduje.

 sprawdzanie długości listy (funkcja zwracająca informację o liczbie elementów w liście) - wersja rekurencyjna.

Dziwne jest to, że posiadasz w kodzie funkcje o wiele bardziej skomplikowane niż ta, a jednak nie potrafisz jej napisać… Po prostu iterujesz po kolejnych elementach listy, sprawdzając w warunku, czy doszedłeś do końca i zwracasz jej długość. Oto pseudokod:

int dlugosc_listy(struct Lista *glowa)
{
    if (glowa != NULL) {
        return dlugosc_listy(glowa, 1);
    }
    printf("\nLista jest pusta!");
    return 0;
}

int dlugosc_listy(struct Lista *element, int dlugosc)
{
    if (element->nastepny == NULL) {
        return dlugosc;
    } else {
        return dlugosc_listy(element->nastepny, ++dlugosc);
    }
}