Infinite loops with a linked list

Question

I'm working on a program that takes an input of numbers from stdin and computes the median of the sequence and prints it out as a float. I'm currently getting an infinite loop in the function

len(struct node *)

at the for loop and I'm not sure why.

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

struct node {
    float *val;
    struct node *next;
};

int len(struct node *list) {
    int i = 0;
    struct node *temp = list;
    for (i = 0; temp != NULL; i++) {
        temp = temp->next;
    }
    return i;
}

float median(int size, struct node list) {
    struct node temp = list;
    int i = 0;
    if (size == 1) {
        return *temp.val;
    } else
    if (size == 2) {
        return (*(temp.val) + *(temp.next->val)) / 2;
    } else {
        if (size / 2 == 1) {
            for (i = 3; i != (size / 2) - 1; i++) {
                temp = *(temp.next);
            }
            return *temp.val;
        } else {
            for (i = 3; i != (size / 2); i++) {
                temp = *(temp.next);
            }
            return (*(temp.val) + *(temp.next->val)) / 2;
        }
    }
}

int main() {
    struct node *tmpnode;
    tmpnode = malloc(sizeof(struct node));
    tmpnode->next = NULL;
    struct node *list = NULL;
    list = tmpnode;
    float temp = 0;
    int err = 0;
    int size = 0;
    while ((err = scanf("%f", &temp)) != EOF) {
        if (err < 1) {
            fprintf(stderr, "Error: non-integer character inputted\n");
            return 1;
        }
        tmpnode->val = &temp;
        tmpnode->next = list;
        list = tmpnode;
    }
    size = len(list);
    if (size == 0) {
        fprintf(stderr, "Error: no inputs found");
        return 1;
    }
    printf("%f\n", median(size, *list));
    return 0;
}

Edit: I've fixed the infinite loop, but now I'm getting a segfault at temp = *(temp.next) in median(). Do I need to allocate for temp?

Answer 1

If you're looking for the median you would have to arrange the nodes in order and get the number that is in the middle.If the number of nods is even and there is no middle you should add the two middlemost numbers and divide them by two.

Is the sequence in order? If not you're miscalculating the median.

Supposing the sequence is in order.

I didn't really understand the usefulness of this statement

if(size/2 == 1)

Maybe you're trying to see if the size is odd. In that case you should do:

>  if(size%2 == 1)

Why the list is probably looping might be due to this

 for(i = 3; i != (size/2); i++){
          temp = *(temp.next);
 }

Suppose you pass a 5 to the function size/2=2 (decimal part is lost), so it'll keep on going until an overflow occurs and it actually reaches 2, making your program most probably seg_fault in the process.

Start from i=0, because even though you started from 3 your current node is not the third one but the FIRST ONE.

Good luck hope this helps!!!!

Answer 2

You created only one node and assigned next of the node to itself, so this is cause of the infinite loop.

Create new nodes and link them in the input loop. Assigning address of temp to all nodes is also not good.

Your main() function should be like this:

int main(void){
    struct node *tmpnode;
    tmpnode = malloc(sizeof(struct node));
    if(tmpnode == NULL){
        perror("malloc 1");
        return 1;
    }
    tmpnode->next = NULL;
    struct node *list = NULL;
    list = tmpnode;
    float temp = 0;
    int err = 0;
    int size = 0;
    while((err = scanf("%f", &temp)) != EOF){
        if(err < 1){
            fprintf(stderr, "Error: non-integer character inputted\n");
            return 1;
        }
        tmpnode->val = malloc(sizeof(float));
        if(tmpnode->val == NULL){
            perror("malloc 2");
            return 1;
        }
        *tmpnode->val = temp;
        tmpnode->next = malloc(sizeof(struct node));
        if(tmpnode->next == NULL){
            perror("malloc 3");
            return 1;
        }
        tmpnode = tmpnode->next;
        tmpnode->val = NULL;
        tmpnode->next = NULL;
    }
    size = len(list);
    if(size == 0){
        fprintf(stderr, "Error: no inputs found");
        return 1;
    }
    printf("%f\n", median(size, *list));
    /* code to free the list should be here */
    return 0;
}

(I gave input 1 2 3 4 5 and this program's output was 1.500000, which might be wrong)