C language programing Download the starting materials (list.c, list.h, listmain.
ID: 3861067 • Letter: C
Question
C language programing
Download the starting materials (list.c, list.h, listmain.c) from Canvas.
Write the following 5 functions:
1) struct node *deleteAll(struct node *list, int n);
This function deletes all occurrences of n from list and returns the result. Your deleteAll must be efficient. One INEFFICIENT approach would be to call a function that does a single delete repeatedly until no deletion is possible. This is inefficient because it requires searching over the same nodes again and again. For this function: solve it using one loop and without calling helper functions! (A helper function is a function written by you or provided in the starting code. You may call functions in the standard library, like malloc.)
This function adds a duplicate of each node next to the original and returns the resulting list. The list 1 4 6 2 becomes the list 1 1 4 4 6 6 2 2. No calls to helper functions.
This function takes two lists that are in non-decreasing order and returns a list that merges the two, also in nondecreasing order. So the lists 3 5 7 7 9 and 1 5 6 10 would merge to form 1 3 5 5 6 7 7 9 10. No new nodes are created; existing nodes in list1 and list2 are used to build the new merged list. The trick to merging is to focus on nodes at the front of both list1 and list2, decide which comes first, and transfer it to the new list. Repeat. Eventually one of the lists will run out and you will then need to deal with nodes in the remaining list.
For this function: no nested loops and no calls to helper functions!
This function returns true if there is no duplicated data in the list and false otherwise. The list is not required to be ordered. An empty list has no duplicated data, but the list 1 3 5 1 7 does.
This function returns the length of the list if the list terminates with a NULL. Instead of terminating with a NULL, the list may loop back to some previous node. In that case, the function returns the length of the list negated. If the list is 1 2 3 4 5 and the next link from 5 goes back to any of the 5 nodes, then the function
should return -5. This is the only function that will be tested using lists with loops.
This being a linked list assignment, you may not use arrays.
The prototypes for all 5 functions already appear in list.h. You may not change those prototypes at all. I will combine your list.c file with the original .h file and my grading application.
You must write a program to test your functions. Call it main.c and be sure to call each function at least twice. The test output can be whatever you find helpful.
Zip up list.c and main.c (and nothing else) and submit the zip file to Canvas. All the style and formatting rules of previous assignments remain in effect.
I have this so far..
#include <stdio.h>
List.h
#include <stdlib.h>
typedef struct node_tag {
int value;
struct node_tag *next;
} Node;
/* prints all data in list */
void printAll(Node* list);
/* adds n to front of list */
Node *add_to_list(Node *list, int n);
/* adds n to front of list, alternative version */
void add_to_listP2P(Node **list ,int n);
/* return boolean indicating if list is in order,
i.e. never decreasing */
int inOrder(Node *list);
/* remove n from the list */
Node *delete_from_list(Node *list, int n);
int looplesslength(Node *list);
Node *merge(Node* list1, Node* list2);
int nodupdata(Node *list);
Node *doubleAll(Node* list);
Node *deleteAll(Node *list, int n);
-----------------------------
main.c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
int main(void) {
Node *intlist = NULL;
int i;
for (i = 0; i < 10; i ++) {
intlist = add_to_list(intlist ,i );
}
printAll(intlist);
if (!inOrder(intlist))
printf("Out of Order ");
else
printf("In Order ");
for (i = 0; i < 10; i ++) {
intlist = delete_from_list(intlist ,i );
printAll(intlist);
}
return 0;
}
--------------------
List.c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include <stdbool.h>
void printAll(Node* list) {
Node* curr = list;
printf("List: ");
while (curr != NULL) { // Watch Out: curr->next != NULL
printf("%d ", curr->value);
curr = curr->next;
}
printf(" ");
}
Node *add_to_list(Node *list, int n) {
Node *new_node;
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
printf("Error: malloc failed in add_to_list ");
exit(EXIT_FAILURE);
}
new_node->value = n;
new_node->next = list;
return new_node;
}
void add_to_listP2P( Node **list ,int n) {
Node *new_node;
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
printf("Error: malloc failed in add_to_list ");
exit(EXIT_FAILURE);
}
new_node->value = n;
new_node->next = *list;
*list = new_node;
}
int inOrder(Node *list) {
Node *curr = list;
if (curr == NULL)
return 1;
while (curr->next != NULL) { // SAFETY CHECK: curr != NULL
if (curr->value > curr->next->value) { // SAFETY CHECK: curr->next != NULL
return 0;
}
curr = curr->next;
}
return 1;
}
Node *delete_from_list(Node *list, int n) {
Node *cur, *prev;
for (cur = list, prev = NULL;
cur != NULL ;
prev = cur, cur = cur->next) {
if (cur->value == n) {
if (prev == NULL)
list = list->next; /* n is in the first node */
else
prev->next = cur->next; /* n is in some other node */
free(cur);
break;
}
}
return list;
}
Node *deleteAll(struct node *list, int n) {
//set current node = list
Node *current = list;
//set previous node = null
Node *previous = NULL;
Node *next;
// to delete occurrence if it is head
// while current node is not null and its key is not n
while(current != NULL || current != n) {
// link the list to the current next node
list = current;
// free up the current node
free(curent);
// link the current node to the list
current = list;
} // end while
// to delete occurrence
//while current node is not null
while(current != NULL) {
// while current node is not null and its key is not n
while(current != NULL || current != n) {
//link previous node to the current node
previous = current;
//link the current node to the next node of the current node
current = current->next;
} //end while
//if the current node is null
if(current == NULL) {
// return list // no node deleted
return list;
}//end if
//link the next node of previous node to the next node of current node // unlink the current node
next->previous = current->next;
//free up the current node
free(current);
// link the current node to the next node of previous node
current->next = next->previous;
} //end while
return list;
}// end function
Node *doubleAll(struct node* list){
// link the current node to the list
Node *current = list;
Node * next;
//while the current node is not null
while(current != NULL) {
//create a temp node and set its value same as current node's
Node *temp = current;
//link the temp node to the next node of the current node
temp = current->next;
//link the next node of the current node to the temp node
current->next = temp;
} //end while
}// end function
Node *merge(struct node* list1, struct node* list2){
//create a result node
Node *result;
//if list1 is null
if(list1 == NULL) {
return list2;
} else if (list2 == NULL) {
return list1;
// the value of the list1 less than the value of list2
} else if (list1 < list2) {
//set the result node equal list1
result = list1;
// link the next node of the result to merge(the next node of list1, list2)
result -> next = merge(struct node* list1, struct node* list2);
} else {
// set the result node equal list2
result = List2;
//link the next node of the result to merge(list1, the next node of list2)
result -> next = merge(struct node* list1, struct node* list2);
return result;
} //end if
//end function
}
int nodupdata(struct node *list) {
Node *current, *head, *compared;
//set the current node to the list's head
current = list;
//while the current node is not null
while(current != NULL) {
//set the compared node the current node's next
compared = current ->next;
// while the compared node is not null
while(compared != NULL) {
//if the current node value is equal to the compared node's value
if(current == compared) {
return false;
} //end if
} //end while
//link the current node to its next node
current -> current->next;
} //end while
return true;
//end function
}
int looplesslength(struct node *list) {
Node *current;
// if the list is null
if(list == NULL) {
return 0;
}
// set the current node to the list's head
current = list;
//set the counter to 1
int counter = 1;
//while current node's next is not null
while(current -> next != NULL) {
// increase the counter by 1
counter++;
//link the current node to its next node
current = current->next;
} //end while
return counter;
}
I need help with main.c and check the 5 functions that i wrote.
Explanation / Answer
Fixed 4 functions and could not fix looplesslength().
Modified main to use the implemented functions. Please do rate if the answer helped. Thank you.
list.c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include <stdbool.h>
void printAll(Node* list) {
Node* curr = list;
printf("List: ");
while (curr != NULL) { // Watch Out: curr->next != NULL
printf("%d ", curr->value);
curr = curr->next;
}
printf(" ");
}
Node *add_to_list(Node *list, int n) {
Node *new_node;
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
printf("Error: malloc failed in add_to_list ");
exit(EXIT_FAILURE);
}
new_node->value = n;
new_node->next = list;
return new_node;
}
void add_to_listP2P( Node **list ,int n) {
Node *new_node;
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
printf("Error: malloc failed in add_to_list ");
exit(EXIT_FAILURE);
}
new_node->value = n;
new_node->next = *list;
*list = new_node;
}
int inOrder(Node *list) {
Node *curr = list;
if (curr == NULL)
return 1;
while (curr->next != NULL) { // SAFETY CHECK: curr != NULL
if (curr->value > curr->next->value) { // SAFETY CHECK: curr->next != NULL
return 0;
}
curr = curr->next;
}
return 1;
}
Node *delete_from_list(Node *list, int n) {
Node *cur, *prev;
for (cur = list, prev = NULL;
cur != NULL ;
prev = cur, cur = cur->next) {
if (cur->value == n) {
if (prev == NULL)
list = list->next; /* n is in the first node */
else
prev->next = cur->next; /* n is in some other node */
free(cur);
break;
}
}
return list;
}
Node *deleteAll(Node *list, int n) {
//set current node = list
Node *current = list;
//set previous node = null
Node *previous = NULL;
while(current != NULL) {
if(current->value == n) //current node contains the value to be deleted
{
if(previous == NULL) //deleting head node
list = list->next;
else
previous->next = current->next;
free(current);
current = previous->next;
}
else
{
previous = current;
current = current->next;
}
} //end while
return list;
}// end function
Node *doubleAll(Node* list){
// link the current node to the list
Node *current = list;
//while the current node is not null
while(current != NULL) {
//create a temp node and set its value same as current node's
Node *temp = malloc(sizeof(Node));
temp->value = current->value;
//link the temp node to the next node of the current node
temp->next = current->next;
//link the next node of the current node to the temp node
current->next = temp;
//go to the next node in original list
current = temp->next;
} //end while
return list;
}// end function
Node *merge(Node* list1, Node* list2){
//create a result node
Node *result;
if(list1 == NULL){
return list2;
}
else if(list2 == NULL){
return list1;
}
else{
//set the 1st node for the result
if(list1->value < list2->value){
result =list1;
list1 = list1->next;
}
else{
result = list2;
list2 = list2->next;
}
}
Node *curr = result;
while(list1 != NULL && list2 != NULL){
if(list1->value < list2->value){ //if the next node to go into result list is from list1
curr->next = list1;
list1 = list1->next;
}
else{//if the next node to go into result list is from list2
curr->next = list2;
list2 = list2->next;
}
curr = curr->next;
}
if(list1 != NULL) //if some node were still left out in list1
curr->next = list1;
else
curr->next = list2;
return result;
//end function
}
int nodupdata(Node *list) {
Node *current, *compared;
//set the current node to the list's head
current = list;
//while the current node is not null
while(current != NULL) {
//set the compared node the current node's next
compared = current ->next;
// while the compared node is not null
while(compared != NULL) {
//if the current node value is equal to the compared node's value
if(current->value == compared->value) {
return false;
} //end if
compared = compared->next;
} //end while
//link the current node to its next node
current = current->next;
} //end while
return true;
//end function
}
int looplesslength(Node *list) {
Node *current;
// if the list is null
if(list == NULL) {
return 0;
}
// set the current node to the list's head
current = list;
//set the counter to 1
int counter = 1;
//while current node's next is not null
while(current -> next != NULL) {
// increase the counter by 1
counter++;
//link the current node to its next node
current = current->next;
} //end while
return counter;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
int main(void) {
Node *intlist = NULL;
int i;
for (i = 1; i <= 10; i ++) {
intlist = add_to_list(intlist ,i );
}
printAll(intlist);
if(nodupdata(intlist))
printf("intlist does not have any duplicates ");
else
printf("intlist has duplicates ");
if (!inOrder(intlist))
printf("Out of Order ");
else
printf("In Order ");
for (i = 1; i < 10; i ++) {
intlist = delete_from_list(intlist ,i );
printAll(intlist);
}
//demonstrate removing all duplicates
Node *list1 = NULL;
add_to_listP2P(&list1, 12);
add_to_listP2P(&list1, 10);
add_to_listP2P(&list1, 8);
add_to_listP2P(&list1, 4);
add_to_listP2P(&list1, 6);
add_to_listP2P(&list1, 4);
add_to_listP2P(&list1, 2);
printf("list1 is (contains duplicte element 4) ");
printAll(list1);
list1 = deleteAll(list1, 4);
printf("After removing all copies of 4, list1 is ");
printAll(list1);
//demo merge
Node *list2 = NULL;
add_to_listP2P(&list2, 12);
add_to_listP2P(&list2, 7);
add_to_listP2P(&list2, 5);
add_to_listP2P(&list2, 5);
add_to_listP2P(&list2, 3);
add_to_listP2P(&list2, 1);
printf(" list2 is ");
printAll(list2);
Node *list3 = merge(list1, list2);
printf(" merged list list3 is ");
printAll(list3);
//demo doubling every element
list3 = doubleAll(list3);
printf(" after doubling all elements in list3, it is ");
printAll(list3);
//demo to check if list contains duplicate or not
if(nodupdata(list2))
printf("list2 does not have any duplicates ");
else
printf("list2 has duplicates ");
return 0;
}
output
List: 10 9 8 7 6 5 4 3 2 1
intlist does not have any duplicates
Out of Order
List: 10 9 8 7 6 5 4 3 2
List: 10 9 8 7 6 5 4 3
List: 10 9 8 7 6 5 4
List: 10 9 8 7 6 5
List: 10 9 8 7 6
List: 10 9 8 7
List: 10 9 8
List: 10 9
List: 10
list1 is (contains duplicte element 4)
List: 2 4 6 4 8 10 12
After removing all copies of 4, list1 is
List: 2 6 8 10 12
list2 is
List: 1 3 5 5 7 12
merged list list3 is
List: 1 2 3 5 5 6 7 8 10 12 12
after doubling all elements in list3, it is
List: 1 1 2 2 3 3 5 5 5 5 6 6 7 7 8 8 10 10 12 12 12 12
list2 has duplicates
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.