***** THIS IS MY CODE FOR HW10******** **hw10 file ** #include <stdio.h> #includ
ID: 3830321 • Letter: #
Question
***** THIS IS MY CODE FOR HW10********
**hw10 file **
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
struct node
{
int data;
struct node *next;
struct node *prev;
}
*trashHead, *trashTail, *trashCurrent;
void DisplayInorder (struct node *head1); // declaring function
void DisplayPostorder (struct node *tail1); // declaring function
void DisplayTrash (struct node *trashHead1); // declaring function
void FreeInorder (struct node *head2); // declaring function
void FreeTrash (struct node *trashHead2); // declaring function
int AddToTrash (struct node *toTrash, int trashSize1); // declaring function
int main( int argc, char *argv[] )
{
// Implement and check command line arguments
if( argc == 2 )
printf("Command line argument: %s ", argv[1]);
else if( argc > 2 )
{
printf("Too many arguments supplied. ");
return 1;
}
else
{
printf("One argument expected. ");
return 2;
}
// Declare thes structure and the variable and the pointers
int i, counter, removal, trashSize = 0;
counter = atoi(argv[1]);
struct node *current, *temp, *head, *tail;
// setting the pointer to null
head = NULL;
// inserts the numbers needed with the data given
for(i=0; i < counter; i++)
{
printf("Input data: %d ", i);
if (head == NULL)
{
if ((temp = (struct node *)malloc(sizeof(struct node))) != NULL)
{
// again seeting the pointers
temp->data = i;
temp->next = NULL;
temp->prev = NULL;
current = temp;
head = temp;
}
else
{
printf("Memory allocation failed");
return 1;
}
}
else
{
if ((temp = (struct node *)malloc(sizeof(struct node))) != NULL)
{
temp->data = i;
current->next = temp;
temp->prev = current;
current = temp;
}
else
{
printf("Memory allocation failed");
return 1;
}
}
}
// Set the tail pointer
tail = current;
// Print blank line make it look pretty
printf(" ");
// Print the list forwards
DisplayInorder(head);
// Print blank line make it look pretty
printf(" ");
// Print the list backwards
DisplayPostorder(tail);
// the random function to randomly select how many numbers it should remove and put it in the trash can
removal = rand() % counter + 3;
for (i = 0; i < removal; i++)
{
// use of the random function again to find out what number in particular is going to delete
removal = (rand() % counter);
//printf("%d ", removal);
// this will go through the list and determine which one is the one getting deleted.
current = head;
while (current)
{
if (current->data == removal)
{
if (current->prev == NULL)
{
// Set the next node in the linked list to head
current->next->prev = NULL;
head = current->next;
//adding it to the trash list just from the head anf pushing it in
trashSize = AddToTrash(current, trashSize);
printf("I just changed the head");
break;
}
else
{
// Change prev and next pointers to exclude this node
if (current->next != NULL)
{
current->next->prev = current->prev;
current->prev->next = current->next;
}
// Drop the pointers to the current node, as it is at the tail of the linked list
else // (current->next == NULL)
{
current->prev->next = NULL;
}
//Do something to put the node current into the Trash linked list
printf("I just sent %d to trash. ", removal);
trashSize = AddToTrash(current, trashSize);
break;
}
}
else if (current->next != NULL)
current = current->next;
else
{
//printf("Something went wrong or selected two numbers);
break;
}
}
}
// Display the trash linked list
DisplayTrash(trashHead);
// Print blank line
printf(" ");
// Print the list forwards
DisplayInorder(head);
// Print blank line
printf(" ");
// Print the list backwards
DisplayPostorder(tail);
// Free the array(s)
FreeInorder(head);
return 0;
}
void DisplayInorder (struct node *head1)
{
// Print the list forwards
while (head1)
{
// Print out data, tab delimited
printf("Left to right output: %d ", head1->data);
head1 = head1->next;
}
}
void DisplayPostorder (struct node *tail1)
{
while (tail1)
{
// Print out data, tab delimited
printf("Right to left output: %d ", tail1->data);
tail1 = tail1->prev;
}
}
int AddToTrash (struct node *toTrash, int trashSize1)
{
if (trashSize1 == 0)
{
trashHead = toTrash;
trashCurrent = toTrash;
trashTail = toTrash;
toTrash->prev = NULL;
toTrash->next = NULL;
trashSize1++;
}
else
{
toTrash->next = NULL;
trashCurrent->next = toTrash;
toTrash->prev = trashCurrent;
trashCurrent = trashCurrent->next;
trashTail = trashCurrent;
trashSize1++;
}
return trashSize1;
}
void DisplayTrash (struct node *trashHead1)
{
// Print the trash list forwards
while (trashHead1)
{
// Print out data, tab delimited
printf("Trash output: %d ", trashHead1->data);
if (!trashHead1->next)
{
free(trashHead1);
break;
}
trashHead1 = trashHead1->next;
free(trashHead1->prev);
}
}
void FreeTrash (struct node *trashHead2)
{
while (trashHead2)
{
if (!trashHead2->next)
{
free(trashHead2);
break;
}
trashHead2 = trashHead2->next;
free(trashHead2->prev);
}
}
void FreeInorder (struct node *head2)
{
while (head2)
{
if (!head2->next)
{
free(head2);
break;
}
head2 = head2->next;
free(head2->prev);
}
}
Explanation / Answer
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
struct timeval begin, end;
struct node {
int data;
struct node *next;
struct node *prev;
}*trashHead, *trashTail, *trashCurrent;
struct timeNode {
double data;
struct timeNode *next;
struct timeNode *prev;
}*timeHead, *timeTail, *timeCurrent;
// initalize variables to keep track of K best measurement bounds
int flag = 0, K = 3, M = 1000;
double e = 0.001;
void DisplayInorder (struct node *head1); // Prototype
void DisplayPostorder (struct node *tail1); // Prototype
void DisplayTrash (struct node *trashHead1); // Prototype
void FreeInorder (struct node *head2); // Prototype
void FreeTrash (struct node *trashHead2); // Prototype
int AddToTrash (struct node *toTrash, int trashSize1); // Prototype
int AddToTime (double elapsed1, int timeLength1); // Prototype
int main( int argc, char *argv[] )
{
// initalize variables to keep track of K best measurement bounds
int f;
int timeLength = 0;
// For loop to measure iterations of K best measurements
for (f = 0; f < M; f++)
{
// Get beginning runtime of program
gettimeofday(&begin, NULL);
// Implement and check command line arguments
if( argc == 2 )
printf("Command line argument: %s ", argv[1]);
else if( argc > 2 )
{
printf("Too many arguments supplied. ");
return 1;
}
else
{
printf("One argument expected. ");
return 2;
}
// Declare variables and pointers
int i, counter, removal, trashSize = 0;
counter = atoi(argv[1]);
struct node *current, *temp, *head, *tail;
head = NULL;
// For loop to insert data into linked list
for(i=0; i < counter; i++)
{
printf("Input data: %d ", i);
if (head == NULL)
{
if ((temp = (struct node *)malloc(sizeof(struct node))) != NULL)
{
temp->data = i;
temp->next = NULL;
temp->prev = NULL;
current = temp;
head = temp;
}
else
{
printf("Memory allocation failed");
return 1;
}
}
else
{
if ((temp = (struct node *)malloc(sizeof(struct node))) != NULL)
{
temp->data = i;
current->next = temp;
temp->prev = current;
current = temp;
}
else
{
printf("Memory allocation failed");
return 1;
}
}
}
// Set the tail pointer
tail = current;
// Print blank line
printf(" ");
// Print the list forwards
DisplayInorder(head);
// Print blank line
printf(" ");
// Print the list backwards
DisplayPostorder(tail);
// Determine how many and which nodes to put into Trashcan
removal = rand() % counter + 3;
for (i = 0; i < removal; i++)
{
// Pick a random node (payload) to delete.
removal = (rand() % counter);
//printf("%d ", removal);
// Find the specified payload in the linked list
current = head;
while (current)
{
if (current->data == removal)
{
if (current->prev == NULL)
{
// Set the next node in the linked list to head
current->next->prev = NULL;
head = current->next;
// Do something to put the node current into the Trash linked list
trashSize = AddToTrash(current, trashSize);
printf("I just changed the head ");
break;
}
else
{
// Change prev and next pointers to exclude this node
if (current->next != NULL)
{
current->next->prev = current->prev;
current->prev->next = current->next;
}
// Drop the pointers to the current node, as it is at the tail of the linked list
else // (current->next == NULL)
{
current->prev->next = NULL;
tail = current->prev;
printf("I just changed the tail ");
}
//Do something to put the node current into the Trash linked list
printf("I just sent %d to trash. ", removal);
trashSize = AddToTrash(current, trashSize);
break;
}
}
else if (current->next != NULL)
current = current->next;
else
{
//printf("Either something went REALLY wrong, or this number was selected twice. The number selected was %d. ", removal);
break;
// current = current->next;
}
}
}
// Display the trash linked list
DisplayTrash(trashHead);
// Free the trash linked list
//FreeTrash(trashHead);
// Print blank line
printf(" ");
// Print the list forwards
DisplayInorder(head);
// Print blank line
printf(" ");
// Print the list backwards
DisplayPostorder(tail);
// Free the array(s)
FreeInorder(head);
// Print blank line
printf(" ");
// Get time for end of execution
gettimeofday(&end, NULL);
// Calculate the difference between beginning time and end time
double elapsed = ((end.tv_sec - begin.tv_sec) + ((end.tv_usec - begin.tv_usec)/1000000.0));
// Pass elapsed time to a function
timeLength = AddToTime(elapsed, timeLength);
if (flag)
{
return 3;
}
//printf("%d", f);
// Print the difference to the standard output
//printf("The calculations took %f seconds. ", elapsed);
} // End of K measurement for loop
return 0;
}
void DisplayInorder (struct node *head1)
{
// Print the list forwards
while (head1)
{
// Print out data, tab delimited
printf("Left to right output: %d ", head1->data);
head1 = head1->next;
}
}
void DisplayPostorder (struct node *tail1)
{
while (tail1)
{
// Print out data, tab delimited
printf("Right to left output: %d ", tail1->data);
tail1 = tail1->prev;
}
}
int AddToTrash (struct node *toTrash, int trashSize1)
{
//struct node *trashCurrent;
if (trashSize1 == 0)
{
trashHead = toTrash;
trashCurrent = toTrash;
trashTail = toTrash;
toTrash->prev = NULL;
toTrash->next = NULL;
trashSize1++;
}
else
{
toTrash->next = NULL;
trashCurrent->next = toTrash;
toTrash->prev = trashCurrent;
trashCurrent = trashCurrent->next;
trashTail = trashCurrent;
trashSize1++;
}
return trashSize1;
}
void DisplayTrash (struct node *trashHead1)
{
// Print the trash list forwards
while (trashHead1)
{
// Print out data, tab delimited
printf("Trash output: %d ", trashHead1->data);
if (!trashHead1->next)
{
free(trashHead1);
break;
}
trashHead1 = trashHead1->next;
free(trashHead1->prev);
}
}
void FreeTrash (struct node *trashHead2)
{
while (trashHead2)
{
if (!trashHead2->next)
{
free(trashHead2);
break;
}
trashHead2 = trashHead2->next;
free(trashHead2->prev);
}
}
void FreeInorder (struct node *head2)
{
while (head2)
{
if (!head2->next)
{
free(head2);
break;
}
head2 = head2->next;
free(head2->prev);
}
}
int AddToTime (double elapsed1, int timeLength1)
{
double temp;
int q;
if (timeLength1 == 0) // Inserting the first node
{
if ((timeCurrent = (struct timeNode *)malloc(sizeof(struct timeNode))) != NULL)
{
timeCurrent->data = elapsed1;
timeCurrent->next = NULL;
timeCurrent->prev = NULL;
timeHead = timeCurrent;
timeTail = timeCurrent;
timeLength1 = 1;
}
else
{
printf("Memory allocation failed");
flag = 1;
return 1;
}
}
else // Inserting another node at the end of the list
{
if ((timeCurrent = (struct timeNode *)malloc(sizeof(struct timeNode))) != NULL)
{
timeCurrent->data = elapsed1;
timeCurrent->next = NULL;
timeCurrent->prev = timeTail;
timeTail->next = timeCurrent;
timeTail = timeCurrent;
timeLength1++;
}
else
{
printf("Memory allocation failed");
flag = 1;
return 1;
}
}
// Sort the list
timeCurrent = timeHead;
while (timeCurrent->next)
{
if (timeCurrent->data < timeCurrent->next->data)
{
temp = timeCurrent->next->data;
timeCurrent->next->data = timeCurrent->data;
timeCurrent->data = temp;
}
else
timeCurrent = timeCurrent->next;
}
// Compare values to evaluate if we have met the K requirement
timeCurrent = timeTail;
if (timeLength1 > 3)
{
if((timeCurrent->prev->data - timeCurrent->data) < e)
{
if((timeCurrent->prev->prev->data - timeCurrent->data) < e)
{
if((timeCurrent->prev->prev->prev->data - timeCurrent->data) < e)
{
printf("The measurements have converged at %f! It took all of %d iterations of the program's code to come up with that figure. ", timeCurrent->data, timeLength1);
flag = 1;
double timeTotal = 0;
timeCurrent = timeHead;
while (timeCurrent)
{
timeTotal = (timeTotal + timeCurrent->data);
if (!timeCurrent->next)
{
free(timeCurrent);
break;
}
timeCurrent = timeCurrent->next;
free(timeCurrent->prev);
}
printf("The total runtime of the garbage collection algorithm was %f seconds, by the way. ", timeTotal);
return;
}
}
}
}
if (timeLength1 >= M)
{
double timeTotal = 0;
timeCurrent = timeHead;
while (timeCurrent)
{
timeTotal = (timeTotal + timeCurrent->data);
if (!timeCurrent->next)
{
free(timeCurrent);
break;
}
timeCurrent = timeCurrent->next;
free(timeCurrent->prev);
}
printf("We couldn't get a definitive convergence value. Sad day. The total runtime of the garbage collection algorithm was %f seconds, by the way. ", timeTotal);
}
return timeLength1;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.