gator
gator

Reputation: 3523

Linked list of "random" values, program hangs

I'm trying to learn C a little bit and am dealing with linked lists right now. I have defined a linked list as:

struct data {
    int xVal;
    int yVal;
    struct data *next;
};

What I want to do is insert num pairs of values into the linked list, but each pair must be unique.

void addToList(num) {
    srand(time(NULL));
    struct data *list = NULL;
    list = malloc(sizeof(struct data));
    struct data *q = list;
    list->xVal = rand() % 100;
    list->yVal = rand() % 100;
    int j = 0;
    while (j < num-1) {
        q->next = malloc(sizeof(struct data));
        q->next->xVal = rand() % 100;
        q->next->yVal = rand() % 100;
        if (unique(list, q->next->xVal, q->next->yVal)) {
            q = q->next;
            j++;
        }
    }
}

bool unique(struct data *list, int x, int y) {
    struct data *q = list;
    while (q->next != NULL) {
        if (q->xVal = x && q->yVal == y) { return false; }
        q = q->next;
    }
    return true;
}

What it does is it generates a random value 1-100 for both xVal and yVal, checks if that pair already exists in the list, and if not it inserts at the end. It compiles fine, but running the program makes it hang. I don't see any infinite loops here. I've tried with num equal to 2 and it still hangs.

Removing the check for unique values lets me fill and print the list, but I still run into an exception "Access violation reading location 0xCDCDCDD9.".

Upvotes: 0

Views: 52

Answers (1)

R Sahu
R Sahu

Reputation: 206577

Problem

You have a logic error.

You add couple of values to the list using:

    q->next->xVal = rand() % 100;
    q->next->yVal = rand() % 100;

and then check whether they exist in the list. Of course they do. The return value from unique is always false. As a consequence, j never gets incremented and the list keeps growing despite j not being incremented.

Fix

  1. Get the random numbers.
  2. Check whether they are unique before adding them to the list.

Here's how I see it.

void addToList(num) {
   srand(time(NULL));
   struct data *list = NULL;
   list = malloc(sizeof(struct data));
   struct data *q = list;
   list->xVal = rand() % 100;
   list->yVal = rand() % 100;
   int j = 0;
   while (j < num-1) {
      int x = rand() % 100;
      int y = rand() % 100;
      if ( unique(list, x, y) ) {
         q->next = malloc(sizeof(struct data));
         q->next->xVal = x;
         q->next->yVal = y;
         q->next->next = NULL; // Make sure the list has a clean end
         q = q->next;
         j++;
      }
   }
}

And ...

You also have a typo in unique.

    if (q->xVal = x && q->yVal == y) { return false; }

should be:

    if (q->xVal == x && q->yVal == y) { return false; }
             // ^^ Need to compare, not assigh.

Upvotes: 3

Related Questions