?
Solved

Linked List of 100 Random Numbers

Posted on 2005-03-10
14
Medium Priority
?
1,548 Views
Last Modified: 2010-04-15
I have to write a program that builds a linked list of 100 random numbers.  The program is then to sort the list (preferably a binary sort).  I must then display or print to the screen the list before sorted, and after it has been sorted.  PLEASE HELP!!!
0
Comment
Question by:nuclearcane
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 5
  • 2
  • +1
14 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13514226
Hi nuclearcane,

We cannot do your homework ... You need to make a sincere effort on your own ... post the code you have and we can help you get it working.

To get you started,

1. A way to generate numbers
use srand() to seed your random number generator ... For better results, seed it with time(). Use rand() to generate random numbers ...

2. Way to build linked list
you will need to write all functions for linked list implementation ... adding to list, deleting from list, searching in list etc.
Break down each of these functions into simpler steps which you can code

3. Sorting
I never heard binary sort .. I thought we had binary search only ... Any case, linked list offers you sequential access only ... So you will have to chose a sortig algorithm that you can apply to it ... we will discuss it once we have a linked list in place

Cheers!
sunnycoder
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 13514765
> binary sort
Are you confusing with bubble sort?
It is a well-known algorithm and you will have to study it before starting.

In any case, I would suggest you to, write down the steps en "plain" english.
Then try to convert them into code.

-ssnkumar
0
 

Author Comment

by:nuclearcane
ID: 13521307
Hello Sunnycoder and everyone else reading this.  Here is my sincere effort.  I basically went about using the same approach I used with another programming problem and this is what I have so far:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
typedef struct node
{
    int data;          
    struct node *next;  
} STACKNODE;


void push(int key, STACKNODE **stack);

int main()
{
    STACKNODE *stack;
    STACKNODE key[150];
    STACKNODE *pWalker;
    int linecount = 0;
    int i = 0;
    int limit;
    stack = NULL;
   
    printf("Generating Random Numbers: ");
    do
    {
        key[i].data = rand();
        push(key[i].data, &stack);
        i++;
    } while (i < 101);
   

    printf("\nList before sorting:\n");                
   
    pWalker = stack;
    while (pWalker)
    {
        if (++linecount > 10)
        {
            linecount = 1;
            printf("\n");
        }
       
    printf("%3d ", pWalker->data);
    pWalker = pWalker->next;
    }
   
    printf("\nList after sorting:\n");                            
             
    system("pause");
    return 0;
}

void push(int key, STACKNODE **stack)
{
    STACKNODE *newnode;
    newnode=(STACKNODE *)malloc(sizeof(STACKNODE));
    newnode->data = key;
    newnode->next = (*stack);
    (*stack) = newnode;
}

First of all am I going about this the right way, meaning, is this program going to accomplish the aforementioned objective(I have to write a program that builds a linked list of 100 random numbers.  The program is then to sort the list.  I must then display or print to the screen the list before sorted, and after it has been sorted.)  I have no idea how to use a bubble sort method to the list, please help.
nuclearcane
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 1

Expert Comment

by:ppk_cbe
ID: 13522164
This is a good start at creating a list of random numbers. You don't need the 'key' array though. You can use a single variable to hold the rand number and push it to the stack

>>        key[i].data = rand();
>>        push(key[i].data, &stack);

 or push the rand number directly.

push(rand(), &stack);

I shall try to get you a simple sorting routing.

BTW, Make sure you clear off the list before you exit the program. - PPK.
0
 

Author Comment

by:nuclearcane
ID: 13522186
Thank you so much PPK, I went ahead and did away with the array as I realized this was unecessary also.  So I have instead:

 do
    {
        key.data = rand();
        push(key.data, &stack);
        i++;
    } while (i < 100);

But yes, please get back to me on the sorting.  I'm finding this to be a real bear.  Thanks again.

nuclearcane

0
 
LVL 1

Expert Comment

by:ppk_cbe
ID: 13522227
Here is a simple clear_stack function.

void clear_stack(STACKNODE *stack)
{
    STACKNODE *pTmp;
    while (stack) {
      pTmp = stack;
      stack = stack->next;
      free(pTmp);
    }
}

Make sure you call this before you exit the program.
0
 

Author Comment

by:nuclearcane
ID: 13522276
I see, now do I call this from inside main as

clear_stack(stack);
??
Also, why is it necessary to use this function before ending the program?? Thanks again.
nuclearcane
0
 
LVL 1

Accepted Solution

by:
ppk_cbe earned 1000 total points
ID: 13522367
You need to free memory that you have allocated using malloc functions in your programs. If you don't, the memory that was allocated will not be usable - but will also not be available for any other program to use. This is what is called memory leak. Java implementes "Garbage-collection" to clear off such memory, but in good old C, the programmer has to free memory after using it.

On your sorting, if I were given an assigment like this, I would do insert-sort rather than sort after creating the list. What I mean by this is, when I create a node, rather than blindly placing the node at the top (or bottom) of the list, I would place it in the right position so that the list is always sorted.

Here is a modification of your push function which does this...

void push(int key, STACKNODE **stack)
{
  STACKNODE *newnode;
  STACKNODE *pWalker = *stack;
 
  newnode=(STACKNODE *)malloc(sizeof(STACKNODE));
  newnode->data = key;
  if (*stack == NULL) {
    newnode->next = NULL;
    *stack = newnode;
    return;
  }
  if (key < (*stack)->data) {
    newnode->next = *stack;
    *stack = newnode;
    return;
  }
  while ((pWalker->next) && (pWalker->next->data < key))
    pWalker = pWalker->next;
  newnode->next = pWalker->next;
  pWalker->next = newnode;
}

Let us know if this is sufficient.
0
 

Author Comment

by:nuclearcane
ID: 13522454
Much thanks again.  This is very sufficient.  One problem, however, is that I need to display the list before it's been sorted as well as after it's been sorted.  I thought rather than modifying the push function, I'd just display tne numbers while the random numbers were generating.  Does this sound like a good idea?  Here my code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
typedef struct node
{
    int data;          
    struct node *next;  
} STACKNODE;


void push(int key, STACKNODE **stack);

int main()
{
    STACKNODE *stack;
    STACKNODE key[150];
    STACKNODE *pWalker;
    int linecount = 0;
    int i = 0;
    int limit;
    stack = NULL;
   
    printf("Generating Random Numbers: \n");
    printf("\nList before sorting:\n");
    do
    {
        key[i].data = rand();
        push(key[i].data, &stack);
        if (++linecount > 10)
        {
            linecount = 1;
            printf("\n");
        }
        printf(" %3d ", key[i].data);
        i++;
    } while (i < 100);              
   
   
    printf("\n\nList after sorting:");              
   
    pWalker = stack;
    while (pWalker)
    {
        if (++linecount > 10)
        {
            linecount = 1;
            printf("\n");
        }
       
    printf(" %3d ", pWalker->data);
    pWalker = pWalker->next;
    }
                 
    printf("\n");        
    system("pause");
    return 0;
}

void push(int key, STACKNODE **stack)
{
  STACKNODE *newnode;
  STACKNODE *pWalker = *stack;
 
  newnode=(STACKNODE *)malloc(sizeof(STACKNODE));
  newnode->data = key;
  if (*stack == NULL) {
    newnode->next = NULL;
    *stack = newnode;
    return;
  }
  if (key < (*stack)->data) {
    newnode->next = *stack;
    *stack = newnode;
    return;
  }
  while ((pWalker->next) && (pWalker->next->data < key))
    pWalker = pWalker->next;
  newnode->next = pWalker->next;
  pWalker->next = newnode;
}


Thanks again.  
nuclearcane
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 13523203
Hi nuclearcane,

> I thought rather than modifying the push function, I'd just display tne numbers while the random numbers were generating.
Give us the exact statement of your assignment problem and we will find out.

Cheers!
sunnycoder
0
 
LVL 1

Expert Comment

by:ppk_cbe
ID: 13524870
OK sunnycoder, point well taken. Though I don't accept your statement that my post offers little learning advice, I will be more careful in future. Tx
0
 

Author Comment

by:nuclearcane
ID: 13525126
I don't necessarily agree with it either.  ppk_cbe only modified the push function that I had already written out.  Thanks.

nuclearcane
0
 
LVL 1

Expert Comment

by:ppk_cbe
ID: 13525176
But still, the fact that I wrote the sorting routine myself, violated in part, the guidelines here. So let us take sunnycoder's comments in the right spirit and get on with what makes this a great forum.

Cheers!!!
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question