Using the code you built for Lab 1 add the command and function to reverse the l
ID: 3707214 • Letter: U
Question
Using the code you built for Lab 1 add the command and function to reverse the list. The reverse function has the following constraints:
Must be recursive.
Cannot make a copy of the list to create a duplicate or external input list. (A copy of an important pointer is acceptable.)
Accept the command "r" to invoke the reverse function.
HINT This is all about pointer manipulation.
The success of the reverse command can be verified by using the "p" or print command from Lab 1.
THIS IS THE CODE FROM LAB 1.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}
node;
struct node * addToList(struct node *base, int data)
{
struct node *newNode = NULL;
if (base == NULL)
{
base = malloc( sizeof(struct node));
// malloc defend
base -> data = data;
base -> next = NULL;
return base;
}
//Find the bottom of the list starting from the base
while (base -> next != NULL) //FJ was base NOT temp
{
base = base -> next; //FJ was base NOT temp
}
//Now at the end of the list
newNode = malloc( sizeof(struct node)); //get memory for new node
//Defend against bad malloc
base -> next = newNode; // add the new node to bottom of the list (FJ update)
newNode -> data = data; // slap the data into the list
newNode -> next = NULL; // terminate the list by setting next to NULL
return newNode; //return the new end of the list to the caller
//Shouldnt we return newNode?
}
//returns the found node's address is successful, otherwise NULL
struct node * find (struct node * start, int data)
{
struct node *temp;
temp = start;
//check until the last of list
while (temp != NULL)
{
if(temp -> data == data)
//return temp (address)
return temp;
temp = temp -> next;
}
return NULL;
}
//returns the inserted node's address is successful, otherwise NULL
struct node * insert(struct node * start, int dataAfter, int newData)
{
struct node * found = find(start, dataAfter);
struct node *newNode;
if(found == NULL)
{
return NULL;
}
//malloc can not do it, returns null
newNode = malloc( sizeof(struct node));
//not enough memory, return null
if(newNode == NULL) return NULL;
newNode -> data = newData;
//update newNode to next of found
newNode -> next = found -> next;
found -> next = newNode;
//return newNode
return newNode;
}
struct node * delete(struct node * start, int data)
{
struct node *temp;
temp = start;
if(temp -> data == data)
{
temp = temp -> next;
return temp;
}
while(temp -> next != NULL)
{
if(temp -> next -> data == data)
{
break;
}
//keep iterating
temp = temp -> next;
}
//if found then update
if(temp -> next -> data == data)
{
temp -> next = temp -> next -> next;
return start;
}
return NULL;
}
/*
* Walk the list and print the data
*/
void printList(struct node *list)
{
while (list != NULL)
{
fprintf(stdout, "Data: %3d ", list -> data);
list = list -> next;
}
return;
}
/*
* pass the input file to main, then add the data from the input file
* to the list. NB The list starts as an empty list.
*/
int main(int argc, char **argv)
{
char op = '/';
int fnumber = -1,snumber = -1;
struct node *temp = NULL;
struct node *root = NULL;
// Placeholder for end of the list
// input buffer
char *inBuf = NULL;
int lastlist = 0;
int data = 0;
FILE * ifp;
//get a 100 character buffer for input data
inBuf = malloc(100);
if (NULL == inBuf)
{
//Fail to get memory
fprintf(stderr, "No memory - Good Bye! ");
return -1;
}
//getting the filename from command
ifp = fopen(argv [1], "rwb");
if (NULL == ifp)
{
//Print if file is not found
fprintf(stderr, "%s file not to be found. ", argv [1]);
return -1;
}
/*
* Read the file, then add the data to the list
* All the while keep track of the last added node in temp
*/
fscanf(ifp, "%s", inBuf);//read line
do
{
if(inBuf [0] <= 'z' && inBuf [0] >= 'a')
{
//if not the first then execute previous one
if(op != '/')
{
switch (op)
{
//check if the operation is (i,p,d,or f)
case 'i':
if(snumber == -1)
{
if(root == NULL)
{
printf(" ");
root = addToList(root, fnumber);
printf("i %d succesfully inserted. ",fnumber);
}
//update root
else
{
//only first number is present
temp = addToList(root, fnumber);
if (NULL == temp)
printf("Insertion Failed for %d ", fnumber);
else
printf("i %d succesfully inserted. ", fnumber);
}
}
else
{
temp = insert(root,fnumber,snumber);
//Print the Failed and/or successful values
if (NULL == temp)
printf("Failed to insert %d after %d ",snumber,fnumber);
else
printf("i %d after %d successfully inserted ",snumber,fnumber);
}
break;
case 'p':
printf(" ");
printf("=========================================== ");
printf("Value List: ");
printList(root);
break;
case 'd':
//delete
temp = delete(root,fnumber);
if(temp == NULL)
printf("Failed to delete %d ",fnumber);
else
{
root = temp;
printf("d %d Successfully Deleted ",fnumber);
printf("===========================================");
}
break;
case 'f':
temp = find(root,fnumber);
if(temp == NULL)
printf("f %d Value Not to be Found",fnumber);
else
{
printf("f %d Found ",fnumber);
}
break;
}
}
//initialize for exucation
op = inBuf [0];
fnumber = -1;
snumber = -1;
}
else if(fnumber == -1)
{
fnumber = atoi(inBuf);
}
else
{
snumber = atoi(inBuf);
}
if(fscanf(ifp, "%s", inBuf) == EOF) lastlist++;
}
while(lastlist <= 1);
fclose(ifp);
return 0;
}
/*
* The sample input file is based on the included "booyah2.txt"
* file.
* New input file with commands. (Note the comments are for
* clarification and are NOT a requirement for this program.)
---Begin sample booyah2.txt
i 23 // insert 23
i 78 // insert 78
i 900 // insert 900 //remember if not two number the first is addToList only
i 23 42 // insert 42 after 23
p // print
f 78 // find 78
d 78 // delete 78
p // print
i 905 47 // insert 47 after 905 (failure: no afterData)
f 901 // find 901 (failure case test)
p //print
---End sample booyah2.txt
*/
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}
node;
struct node * addToList(struct node *base, int data)
{
struct node *newNode = NULL;
if (base == NULL)
{
base = malloc( sizeof(struct node));
// malloc defend
base -> data = data;
base -> next = NULL;
return base;
}
//Find the bottom of the list starting from the base
while (base -> next != NULL) //FJ was base NOT temp
{
base = base -> next; //FJ was base NOT temp
}
//Now at the end of the list
newNode = malloc( sizeof(struct node)); //get memory for new node
//Defend against bad malloc
base -> next = newNode; // add the new node to bottom of the list (FJ update)
newNode -> data = data; // slap the data into the list
newNode -> next = NULL; // terminate the list by setting next to NULL
return newNode; //return the new end of the list to the caller
//Shouldnt we return newNode?
}
//returns the found node's address is successful, otherwise NULL
struct node * find (struct node * start, int data)
{
struct node *temp;
temp = start;
//check until the last of list
while (temp != NULL)
{
if(temp -> data == data)
//return temp (address)
return temp;
temp = temp -> next;
}
return NULL;
}
//returns the inserted node's address is successful, otherwise NULL
struct node * insert(struct node * start, int dataAfter, int newData)
{
struct node * found = find(start, dataAfter);
struct node *newNode;
if(found == NULL)
{
return NULL;
}
//malloc can not do it, returns null
newNode = malloc( sizeof(struct node));
//not enough memory, return null
if(newNode == NULL) return NULL;
newNode -> data = newData;
//update newNode to next of found
newNode -> next = found -> next;
found -> next = newNode;
//return newNode
return newNode;
}
struct node * delete(struct node * start, int data)
{
struct node *temp;
temp = start;
if(temp -> data == data)
{
temp = temp -> next;
return temp;
}
while(temp -> next != NULL)
{
if(temp -> next -> data == data)
{
break;
}
//keep iterating
temp = temp -> next;
}
//if found then update
if(temp -> next -> data == data)
{
temp -> next = temp -> next -> next;
return start;
}
return NULL;
}
void reverse(node *curr, node *prev, node **head)
{
if (curr->next == NULL)
{
*head = curr;
curr->next = prev;
}
else
{
node *next = curr->next;
curr->next = prev;
reverse(next, curr, head);
}
}
/*
* Walk the list and print the data
*/
void printList(struct node *list)
{
while (list != NULL)
{
fprintf(stdout, "Data: %3d ", list -> data);
list = list -> next;
}
return;
}
/*
* pass the input file to main, then add the data from the input file
* to the list. NB The list starts as an empty list.
*/
int main(int argc, char **argv)
{
char op = '/';
int fnumber = -1,snumber = -1;
struct node *temp = NULL;
struct node *root = NULL;
// Placeholder for end of the list
// input buffer
char *inBuf = NULL;
int lastlist = 0;
int data = 0;
FILE * ifp;
//get a 100 character buffer for input data
inBuf = malloc(100);
if (NULL == inBuf)
{
//Fail to get memory
fprintf(stderr, "No memory - Good Bye! ");
return -1;
}
//getting the filename from command
ifp = fopen(argv [1], "rwb");
if (NULL == ifp)
{
//Print if file is not found
fprintf(stderr, "%s file not to be found. ", argv [1]);
return -1;
}
/*
* Read the file, then add the data to the list
* All the while keep track of the last added node in temp
*/
fscanf(ifp, "%s", inBuf);//read line
do
{
if(inBuf [0] <= 'z' && inBuf [0] >= 'a')
{
//if not the first then execute previous one
if(op != '/')
{
switch (op)
{
//check if the operation is (i,p,d,or f)
case 'i':
if(snumber == -1)
{
if(root == NULL)
{
printf(" ");
root = addToList(root, fnumber);
printf("i %d succesfully inserted. ",fnumber);
}
//update root
else
{
//only first number is present
temp = addToList(root, fnumber);
if (NULL == temp)
printf("Insertion Failed for %d ", fnumber);
else
printf("i %d succesfully inserted. ", fnumber);
}
}
else
{
temp = insert(root,fnumber,snumber);
//Print the Failed and/or successful values
if (NULL == temp)
printf("Failed to insert %d after %d ",snumber,fnumber);
else
printf("i %d after %d successfully inserted ",snumber,fnumber);
}
break;
case 'p':
printf(" ");
printf("=========================================== ");
printf("Value List: ");
printList(root);
break;
case 'd':
//delete
temp = delete(root,fnumber);
if(temp == NULL)
printf("Failed to delete %d ",fnumber);
else
{
root = temp;
printf("d %d Successfully Deleted ",fnumber);
printf("===========================================");
}
break;
case 'f':
temp = find(root,fnumber);
if(temp == NULL)
printf("f %d Value Not to be Found",fnumber);
else
{
printf("f %d Found ",fnumber);
}
case 'r':
reverse(root, NULL, &root);
break;
}
}
//initialize for exucation
op = inBuf [0];
fnumber = -1;
snumber = -1;
}
else if(fnumber == -1)
{
fnumber = atoi(inBuf);
}
else
{
snumber = atoi(inBuf);
}
if(fscanf(ifp, "%s", inBuf) == EOF) lastlist++;
}
while(lastlist <= 1);
fclose(ifp);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.