I need a dynamically allocated linked list

Can someone give me an idea on how to turn the following program into dynamically allocated link list. Currently I have a linked list that I am using but I was told it does not dynamically allocate the values to the linked list. The linked list can only have ten nodes and after the ten are filled I would then evict the value from the node with the lowest counter and the node will take on the new value from the ref string that I generated randomly.

/* Program uses linked list to function as LRU algorithm for paging system */

#include <stdio.h>
#include <stdlib.h>
struct node {
int number;
struct node *next;
};

main()
{
struct node n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;
int d, r, x, y, count, ct, framect, z;
int i, a, min, pages[39],frames[9];
int n1ct, n2ct, n3ct, n4ct, n5ct, n6ct, n7ct, n8ct, n9ct, n10ct = 0;
unsigned seed;
printf("\nThis is the complete ref string\n");
printf("Enter seed: ");

scanf("%u", &seed);
srand(seed);

for( y=0;y<40;y++){
a = (1 + rand() % 20);
printf("%10d", a);

pages[y]=a;
}

count = 0;
y=0;
framect=1;

/* first page fram gets filled here */
n1ct = framect;
n1.number = pages[y];
printf("\nFirst page frame value = %d\n", n1.number);
y++;count++;
printf("\nFrame 1 counter = %d\n", n1ct);
printf("\nTotal number of page faults = %d\n", count);

/* second page frame gets filled here */
framect++;
count++;
if (n1.number != pages[y])
{
n2.number = pages[y];
y++;

}
else{
if(pages[y] = n1.number){n1ct=framect ;framect++;}
y++;
n2.number = pages[y];
y++;
framect++;
}

n2ct = framect;
printf("\nSecond page frame value = %d\n", n2.number);
printf("\nFrame 2 counter = %d\n", n2ct);
printf("\nTotal number of page faults = %d\n", count);

/* third page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y])
{
n3.number = pages[y];
y++;

}

else
{
if(n2.number = pages[y]){framect++; n2ct=framect;}
if(n1.number = pages[y] ){framect++; n1ct=framect;}
y++;
n3.number = pages[y];
y++;

}

n3ct = framect;
printf("\nThird page frame value = %d\n", n3.number );
printf("\nFrame 2 counter = %d\n", n2ct);
printf("\nFrame 3 counter = %d\n", n3ct);
printf("\nTotal number of page faults = %d\n", count);

/* fourth page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y])
{
n4.number = pages[y];
y++;
framect++;
}

else
{
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}
y++;
n4.number = pages[y];
y++;
framect++;
}

n4ct = framect;
printf("\nFourth page frame value = %d\n", n4.number );
printf("\nFrame 4 counter = %d\n", n4ct);
printf("\nTotal number of page faults = %d\n", count);

/* fifth page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y]
&& n4.number != pages[y])
{

n5.number = pages[y];
y++;

}
else
{
if(pages[y] == n4.number){framect++; n4ct=framect;}
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}
y++;
n5.number = pages[y];
y++;

}

n5ct = framect;
printf("\nFourth page frame value = %d\n", n4.number );
printf("\nFifth page frame value = %d\n", n5.number );
printf("\nFrame 3 counter = %d\n", n3ct);
printf("\nFrame 5 counter = %d\n", n5ct);
printf("\nTotal number of page faults = %d\n", count);
printf("\nFifth page frame value = %d\n", n5.number );
/* sixth page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y]
&& n4.number != pages[y] && n5.number != pages[y])

{

n6.number = pages[y];
y++;

}
else
{
if(pages[y] == n5.number){framect++; n5ct=framect;}
if(pages[y] == n4.number){framect++; n4ct=framect;}
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}
y++;
n6.number = pages[y];
y++;
framect++;
}

n6ct = framect;
printf("\nSixth page frame value = %d\n", n6.number );
printf("\nFrame 5 counter = %d\n", n5ct);
printf("\nFrame 6 counter = %d\n", n6ct);
printf("\nTotal number of page faults = %d\n", count);

/* seventh page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y]
&& n4.number != pages[y] && n5.number != pages[y] && n6.number != pages[y])
{

n7.number = pages[y];
y++;
framect++;
}
else
{
if(pages[y] == n6.number){framect++; n6ct=framect;}
if(pages[y] == n5.number){framect++; n5ct=framect;}
if(pages[y] == n4.number){framect++; n4ct=framect;}
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}
y++;
n7.number = pages[y];
y++;
framect++;
}

n7ct = framect;
printf("\nSeventh page frame value = %d\n", n7.number );
printf("\nFrame 6 counter = %d\n", n6ct);
printf("\nFrame 7 counter = %d\n", n7ct);
printf("\nTotal number of page faults = %d\n", count);

/* eighth page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y]
&& n4.number != pages[y] && n5.number != pages[y] && n6.number != pages[y]
&& n7.number != pages[y])
{

n8.number = pages[y];
y++;
framect++;
}
else
{
if(pages[y] == n7.number){framect++; n7ct=framect;}
if(pages[y] == n6.number){framect++; n6ct=framect;}
if(pages[y] == n5.number){framect++; n5ct=framect;}
if(pages[y] == n4.number){framect++; n4ct=framect;}
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}
y++;
n8.number = pages[y];
y++;
framect++;

}

n8ct = framect;
printf("\nEighth page frame value = %d\n", n8.number );
printf("\nFrame 7 counter = %d\n", n7ct);
printf("\nFrame 8 counter = %d\n", n8ct);
printf("\nTotal number of page faults = %d\n", count);

/* ninth page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y]
&& n4.number != pages[y] && n5.number != pages[y] && n6.number != pages[y]
&& n7.number != pages[y] && n8.number != pages[y])
{

n9.number = pages[y];
y++;
framect++;
}
else
{
if(pages[y] == n8.number){framect++; n8ct=framect;}
if(pages[y] == n7.number){framect++; n7ct=framect;}
if(pages[y] == n6.number){framect++; n6ct=framect;}
if(pages[y] == n5.number){framect++; n5ct=framect;}
if(pages[y] == n4.number){framect++; n4ct=framect;}
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}

y++;
n9.number = pages[y];
y++;
framect++;
}

n9ct = framect;
printf("\nNinth page frame value = %d\n", n9.number );
printf("\nFrame 6 counter = %d\n", n6ct);
printf("\nFrame 8 counter = %d\n", n8ct);
printf("\nFrame 9 counter = %d\n", n9ct);
printf("\nTotal number of page faults = %d\n", count);

/* tenth page frame gets filled here */
count++;
ct++;
if (n1.number != pages[y] && n2.number != pages[y] && n3.number != pages[y]
&& n4.number != pages[y] && n5.number != pages[y] && n6.number != pages[y]
&& n7.number != pages[y] && n8.number != pages[y] && n9.number != pages[y])
{

n10.number = pages[y];
y++;
framect++;
}
else
{ if(pages[y] == n9.number){framect++; n9ct=framect;}
if(pages[y] == n8.number){framect++; n8ct=framect;}
if(pages[y] == n7.number){framect++; n7ct=framect;}
if(pages[y] == n6.number){framect++; n6ct=framect;}
if(pages[y] == n5.number){framect++; n5ct=framect;}
if(pages[y] == n4.number){framect++; n4ct=framect;}
if(pages[y] == n3.number){framect++; n3ct=framect;}
if(pages[y] == n2.number){framect++; n2ct=framect;}
if(pages[y] == n1.number){framect++; n1ct=framect;}
y++;
n10.number = pages[y];
y++;
framect++;
}

n10ct = framect;
printf("\nTenth page frame value = %d\n", n10.number );
printf("\nFrame 9 counter = %d\n", n9ct);
printf("\nFrame 10 counter = %d\n", n10ct);
printf("\nTotal number of page faults = %d\n", count);

printf("\n1st node contains value %d\n", n1.number);
printf("\n2nd node contains value %d\n", n2.number);
printf("\n3rd node contains value %d\n", n3.number);
printf("\n4th node contains value %d\n", n4.number);
printf("\n5th node contains value %d\n", n5.number);
printf("\n6th node contains value %d\n", n6.number);
printf("\n7th node contains value %d\n", n7.number);
printf("\n8th node contains value %d\n", n8.number);
printf("\n9th node contains value %d\n", n9.number);
printf("\n10th node contains value %d\n", n10.number);

printf("\nTotal number of page faults = %d\n", count);

scanf("%d", &z);
return 0;
}

Change this:

struct node n1, n2, n3, n4, n5, n6, n7, n8, n9, n10;

to node pointers. Make the other changes necessary to allocate and deallocate said pointers using malloc() and change to referencing fields using '->' instead of '.'

enjoy.

Quote:

unsigned seed;
printf("\nThis is the complete ref string\n");
printf("Enter seed: ");

scanf("%u", &seed);
srand(seed);

If you include <time.h> you can just say:

Code:

srand( (unsigned) time( NULL );

This will automatically seed the random number generator with a different value every time you run the program so you don't need the seed variable and don't need to ask for a seed value from the user.

There is a problem with this bit:

Quote:

int pages[39];
...
...
...
for( y=0;y<40;y++){
a = (1 + rand() % 20);
printf("%10d", a);

pages[y]=a;
}

You have an array of 39 integers indexed from 0 to 38 inclusive, but it looks like you are trying to fill an array of 40 integers in the for loop (0 through 39 = 40 values). Either increase the pages array to 40 or change the value in the for loop to 39 instead of 40.

As for your question, it looks like you are trying to fill 10 nodes with unique numbers. Is that the only reason for the pages array? To ensure you have enough values to pick from that you can almost garuantee that you will be able to pick unique ones?

Your whole main function could probably be reduced down into something like this:

Code:

int main() { struct node* pHead = NULL; int iLoop; // Seed the random number generator. srand( (unsigned) time(NULL) ); // Create and add 10 unique values onto linked list. for( iLoop = 0; iLoop < 10; iLoop++ ) { // Create a unique number not already in the linked list. iValue = GetRandomNumber(); while( FoundNumberInList( iValue, pHead ) ) iValue = GetRandomNumber(); // Insert the unique number into the linked list. pHead = InsertValueIntoList( iValue, pHead ); } // Output data to screen. Add your output code here in another for loop perhaps. // Clean up our dynamically allocated nodes. DeleteList( pHead ); return 0; }

You can get an idea of what the functions are suppossed to do by the names I have given them. GetRandomNumber will return an integer in the range of 1-20. The FoundNumberInList function will try to find the given value in the current linked list. If the value is found it returns true and the loop continues getting a new random number and trying again. If not, the loop exits and the InsertValueIntoList function will then be called. The FoundNumberInList function can also be made to increment a global value to take care of the "page-faults" you are keeping track of if that is important to you. InsertValueIntoList will add the unique value obtained from the GetRandomNumber function onto the linked list pointed to by the pHead node pointer. The DeleteList function takes care of some housecleaning for us by freeing up all the nodes we have allocated.

Of course now you have to write all these functions. Take a shot a writing some of these functions yourself and see how it goes
if you still have problems then just post another message here.

Try not to post so much code next time directly in the message box area next time. Try to include it as an attachment if there is that much code.