Problem ze zliczaniem parzystych elementów w liście

0

Witajcie!
Mam problem ze zliczaniem parzystych elementów listy rekurencyjnie.
Oto mój kod:

int numberOfEvenElements(node_t *head){

    if(head->val==NULL||(head->val)%2!=0)return 0;
    else {
        printf("%d",head->val);
        return 1+numberOfElements(head->next);

    }
}

//Wywołanie:

number=numberOfEvenElements(head);
printf("\nNumber of even elements: %d",number);

Wypisuje mi jakieś kompletne głupoty. Powinno wyjśc 2, bo mam 2 elementy parzyste w liście.

2
  1. Gdzie sprawdzasz koniec listy? Powinno gdzieś być
if (head == NULL) return 0;
  1. Dlaczego kończysz jeśli wartość jest nieparzysta? Jeśli wartość jest nieparzysta to lecisz dalej, tyle że nie zwiększasz licznika.
0
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int val;
    struct node* next;
} node_t;

int numberOfEvenElements(node_t *head);

int main(){
    node_t * head = NULL;
    head = malloc(sizeof(node_t));
    head->val = 1;
    head->next = malloc(sizeof(node_t));
    head->next->val = 2;
    head->next->next = malloc(sizeof(node_t));
    head->next->next->val = 3;
    head->next->next->next = malloc(sizeof(node_t));
    head->next->next->next->val = 4;
    head->next->next->next->next = malloc(sizeof(node_t));
    head->next->next->next->next->val = 5;
    head->next->next->next->next->next = malloc(sizeof(node_t));
    head->next->next->next->next->next->val = 6;
    head->next->next->next->next->next->next = NULL;
    int number = numberOfEvenElements(head);
    printf("\nNumber of even elements: %d\n",number);
    
    node_t * tmp;
    while ((tmp = head) != NULL) 
    {
        head = head->next;
        free (tmp);
    }
}

int numberOfEvenElements(node_t *head){
    if(head == NULL) return 0;
    if((head->val)%2==0) return 1 + numberOfEvenElements(head->next);
    return numberOfEvenElements(head->next);
}

0

Twoja funkcja nie ma struktury rekurencyjnej, czyli, jak pusta to stop (warunek stopu, tutaj return 0;), a jak nie to procesuj w jakiś sposób głowę, lub pomijaj. Tak by to wyglądało:

int evenElements(node_t * node) {
	if (! node) {return 0;}
	else if (node->data % 2 == 0) {
		return 1 + evenElements(node->next); 
	}
	else {
		return evenElements(node->next);
	}
}
0

"Twój kod nie działa do mojego - dalej wypisuje bzdury. Inne funkcje jak dodawanie elementów , usuwanie itd działają super, tylko to zliczanie powoduje jakieś głupoty - jakby w ogóle ta struktura tam nie była czytana"
To Pokaż cały kod, strukturę, jak Dodajesz elementy, itp...

0

Twój kod nie działa do mojego ...

Bo dostałaś przykład na podstawie którego powinnaś sobie poradzić. Gdy czekasz tylko na gotowca to mało się nauczysz.

2

Takie problemy rozwiązuje się stopniowo:

  1. Dodaj printf, który wypisze elementy z listy - stwierdzisz, czy na pewno po wszystkich przechodzisz
  2. Dodaj if, ktory wypisze tylko parzyste elementy z listy - stwierdzisz, czy warunek jest dobry
  3. Spróbuj zwrócić sumę elementów listy - stwierdzisz, czy rekurencja ci działa
  4. Zamiast zwracać wartości elementu zwracaj 1/0 w zależności od tego, czy element jest parzysty
0
typedef struct node {
    int val;
    struct node * next;
} node_t;

void pushOnTheEnd(node_t * head, int val) {
    node_t * current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    /* now we can add a new variable */
    current->next = malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

void pushOnTheBeginning(node_t ** head, int val) {
    node_t * new_node;
    new_node = malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}


int numberOfEvenElements(node_t *head){
   //int counter;
    if(!head)return 0;
   else if((head->val)%2==0) {
       // printf("%d",head->val);
        return 1+numberOfElements(head->next);
    }
    else{
        return numberOfElements(head->next);
    }
}

int main(){
int number;
node_t*new_node;
node_t * head = NULL;
head = malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

head->val = 1;
head->next = NULL;
printf("List on the beginning:\n");
print_list(head);
puts("");
printf("Push on end twice:\n");
pushOnTheEnd(head,5);
pushOnTheEnd(head,7);
print_list(head);
puts("");
printf("Push on the beginning:\n");
pushOnTheBeginning(&head,4);
print_list(head);
number=numberOfEvenElements(head);
printf("\nNumber of even elements: %d",number);
return 0;
}

0

Kasia, wystarczy że użyjesz pętli while (i formatowania kodu jak Swaróg przykazał):

int numberOfEvenElements(node_t *head)
{
    node_t *current = head;
    uint evenElementsCount = 0;
    while (current != NULL)
    {
         if (current->val % 2 == 0)
         {
             evenElementsCount++;
         }
         current = current->next;        
    }
    return evenElementsCount;
}

wersja rekurencyjna

int numberOfEvenElements(node_t *node)
{
    if (node == NULL)
    {
        return 0;
    }
    else return (node->val % 2 == 0) ? 1 + numberOfEvenElements(node->next) : numberOfEvenElements(node->next) ;
}
0

Przerobienie takiego iteracyjnego podejścia to raczej nie problem:

int numberOfEvenElements(node_t *head)
{
    uint evenElementsCount = 0;

    if (head == NULL) {
         return evenElementsCount;
     }

    if (head->val % 2 == 0) {
        ++evenElementsCount;
    }

    return evenElementsCount + numberOfEvenElements(head->next);
}
0

Tak, jak to jest teraz to w momencie tworzenia nowej listy (node_t * node = (node_t *) malloc(sizeof(node_t));) ma ona już element 0 i nie jest NULL - em, dlatego podaje dwa parzyste elementy a nie jeden. Nie wiem jak tego uniknąć w takiej postaci, ja bym to zamknął w oddzielnej klasie - zrobił prościutkie ADT.

typedef struct node {
    int val;
    struct node * next;
} node_t;


void pushOnTheBeginning(node_t ** head, int val) {
    node_t * new_node = (node_t *) malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}


int evenElements(node_t * node) {
	if (! node) {return 0;}
	else if (node->val % 2 == 0) {
		return 1 + evenElements(node->next); 
	}
	else {
		return evenElements(node->next);
	}
}


void printList(node_t * node) {
	node_t * tmp = node;
	while (tmp) {
		std::cout << tmp->val;
		std::cout << " ";
		tmp = tmp->next;
	}
	std:: cout <<"\n";
}

int main(){

	node_t * node = (node_t *) malloc(sizeof(node_t));
	pushOnTheBeginning(&node, 3);
	pushOnTheBeginning(&node, 2);
	pushOnTheBeginning(&node, 1);
	printList(node); // -> 1 2 3 0
	std::cout << evenElements(node); // -> 2
	std::cout << "\n";
1
#include <stdlib.h>

using namespace std;

typedef struct node {
    int val;
    struct node * next;
} node_t;

void pushOnTheEnd(node_t * head, int val) {
    node_t * current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    /* now we can add a new variable */
    current->next = (node_t*)malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

void pushOnTheBeginning(node_t ** head, int val) {
    node_t * new_node;
    new_node = (node_t*)malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}

int numberOfEvenElements(node_t *head){

    if(!head) {
        return 0;
    }
    else if((head->val)%2==0) {
        return 1 + numberOfEvenElements(head->next);
    }
    else{
        return numberOfEvenElements(head->next);
    }
}

int numberOfEvenElements2(node_t *head)
{
    uint evenElementsCount = 0;

    if (head == NULL) {
         return evenElementsCount;
     }

    if (head->val % 2 == 0) {
        ++evenElementsCount;
    }

    return evenElementsCount + numberOfEvenElements(head->next);
}

int main(){
    int number;
    node_t*new_node;
    node_t * head = NULL;
    head = (node_t*)malloc(sizeof(node_t));
    if (head == NULL) {
        return 1;
    }

    head->val = 1;
    head->next = NULL;
    pushOnTheEnd(head,5);
    pushOnTheBeginning(&head,9);
    pushOnTheEnd(head,7);
    pushOnTheEnd(head,2);
    pushOnTheEnd(head,8);
    pushOnTheBeginning(&head,4);
    pushOnTheEnd(head,118);

    number=numberOfEvenElements2(head);
    printf("\nNumber of even elements: %d",number);
    return 0;
}

Output jest dobry, obie wersje funkcji działają (przerabiałem Twoją wklejkę):

Number of even elements: 4
0

No jak nie działa jak działa?

#include <stdio.h>

typedef struct node 
{
    int val;
    struct node *next;
} node_t;

int numberOfEvenElements(node_t *node)
{
    if (node == NULL)
    {
        return 0;
    }
    else return (node->val != 0 && node->val % 2 == 0) ? 1 + numberOfEvenElements(node->next) : numberOfEvenElements(node->next) ;
}

int main()
{
    node_t *head = malloc(sizeof(node_t));
    head->val = 2;
    
    head->next = malloc(sizeof(node_t));
    head->next->val = 4;
    
    head->next->next = malloc(sizeof(node_t));
    head->next->next->val = 6;
    
    printf("even count = %d", numberOfEvenElements(head));//wyświetla 3
    

    return 0;
}

https://onlinegdb.com/BJ1-2XAyB
Upewnij się @Kasia Iks że masz dobrze zainicjowane i popodpinane do siebie kolejne elementy listy

0

Jak manualnie Wpisujesz elementy do listy, to rzeczywiście wyświetla poprawnie. Ale jak to Zrobisz tak jak ja (i każdy, kto będzie tego kodu intuicyjnie używał - czyli stworzyć obiekt i dodać do niego funkcją), to wynik jest zły - jeden więcej element parzysty.

0
lion137 napisał(a):

Jak manualnie Wpisujesz elementy do listy, to rzeczywiście wyświetla poprawnie. Ale jak to Zrobisz tak jak ja (i każdy, kto będzie tego kodu intuicyjnie używał - czyli stworzyć obiekt i dodać do niego funkcją), to wynik jest zły - jeden więcej element parzysty.

A jaki z tego wniosek Bracie @lion137? Kasia Iks ma źle zrobioną funkcję dodającą nowy element.

1

Jest jeszcze jeden problem, po tej linijce:
node_t * node = (node_t *) malloc(sizeof(node_t));
Już jest lista niepusta - z jednym elementem, zero.

1

@Kasia Iks - napisałem tak nie wgłębiając się w analizę Twego kodu, ale wygląda na to, że dodawanie do końca listy działa poprawnie:

#include <stdio.h>

typedef struct node 
{
    int val;
    struct node *next;
} node_t;

void pushOnTheEnd(node_t *head, int value) 
{
    node_t *current = head;
    while (current->next != NULL) 
    {
        current = current->next;
    }
    /* now we can add a new variable */
    current->next = malloc(sizeof(node_t));
    current->next->val = value;
    current->next->next = NULL;
}

int numberOfEvenElements(node_t *node)
{
    if (node == NULL)
    {
        return 0;
    }
    else return (node->val != 0 && node->val % 2 == 0) ? 1 + numberOfEvenElements(node->next) : numberOfEvenElements(node->next);
}

int main()
{
    node_t *head = malloc(sizeof(node_t));
    head->val = 2;
    
    pushOnTheEnd(head, 4);
    pushOnTheEnd(head, 6);
    // head->next = malloc(sizeof(node_t));
    // head->next->val = 4;
    
    // head->next->next = malloc(sizeof(node_t));
    // head->next->next->val = 6;
    
    printf("even count = %d", numberOfEvenElements(head));//nadal dobrze liczy, i dla tych danych wyświetla 3

    return 0;
}

https://onlinegdb.com/H12FUNRkH

0

Problem udało się rozwiązać! Dziękuję za odzew - dobrze mieć mądrych ludzi wokół siebie ;)

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