Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Linked List of 100 Random Numbers

Posted on 2005-03-10
Medium Priority
1,897 Views
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
Question by:nuclearcane
• 5
• 5
• 2
• +1

LVL 45

Expert Comment

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

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

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

LVL 1

Expert Comment

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

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

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

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

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

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

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

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

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

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

Question has a verified solution.

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

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â€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
###### Suggested Courses
Course of the Month15 days, 2 hours left to enroll