In C coding: Create a new function called insertSorted(). The function should in
ID: 3821011 • Letter: I
Question
In C coding:
Create a new function called insertSorted(). The function should insert the value into the linked-list so that the values in the list are in sorted order from LARGEST to SMALLEST. The largest value should always be the first item in the list, and the smallest should always be the last item in the list. The function should take two arguments, 1) The reference (pointer) to the beginning of the list and 2) the value to be inserted. The function should return the new reference (pointer) to the list. Here is an example list detailing what the function should do:
Let's say we start with a linked list as follows: head --> 100 --> 65 --> 29 --> -5 --> -138 --> if we now want to insert 51, the value would NOT go at the beginning of the list, instead it would go somewhere in the middle and would look like: head --> 100 --> 65 --> 51 --> 29 --> -5 --> -138 -->
Given code:
#include <stdio.h>
#include <stdlib.h>
struct SSL1 {
int value;
struct SSL1 *next;
};
void deleteNum(struct SSL1 *myPtr, int numToDelete){
struct SSL1 *aPtr = myPtr;
while ((aPtr!= NULL)&&(aPtr->value != numToDelete)){
aPtr = aPtr->next;
}
if (aPtr != NULL) {
printf("aPtr is referencing %d ",aPtr->value);
// let's go find previous node, might need to be careful if only 1 node
struct SSL1 *tmp = myPtr;
while (tmp->next != aPtr)
tmp = tmp->next;
//when we reach here, tmp references
tmp ->next = aPtr->next; // node referenced by aPtr not in list
aPtr->next = NULL;
free(aPtr); // remove node
}
}
void recprintList(struct SSL1 *myPtr) {
if(myPtr == NULL)
return;
else{
recprintList(myPtr->next);
printf("%d ",myPtr->value);
}
}
void printList(struct SSL1 *myPtr){
while (myPtr != NULL){
printf(" value %d is at %p ",myPtr->value,myPtr);
myPtr = myPtr->next;}
}
void sortList(struct SSL1 *myPtr){
// how will we know when we are through the list once?
// we should be looking for the NULL
// how are we going to swap two values?
// we should really keep myPtr referencing the beginning of the list
struct SSL1 *ptr1=myPtr;
struct SSL1 *ptr2=myPtr;
while (ptr1->next != NULL) {
ptr2 = myPtr;
while (ptr2->next != NULL) {
if (ptr2->value < ptr2->next->value) {
int tmp = ptr2->value;
ptr2->value = ptr2->next->value;
ptr2->next->value = tmp;
}
ptr2=ptr2->next;
}// does code above go through linked list once? A-Y B-N
ptr1 = ptr1->next;
}
}
struct SSL1 *insert (struct SSL1 *ourList, int invalue){
// we are going to insert at the beginning of the list
// 1 create space for struct
struct SSL1 * temp = (struct SSL1 *)malloc(sizeof(struct SSL1));
// 2 initialize the values of the node
temp->value = invalue;
//temp->next = NULL; // don't initialize to NULL
temp->next = ourList;
return temp;
}
int main() {
int temp;
struct SSL1 *head = NULL;
// create your first test case here
// create your second test case here
return 0;
}
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct SSL1 {
int value;
struct SSL1 *next;
};
void deleteNum(struct SSL1 *myPtr, int numToDelete){
struct SSL1 *aPtr = myPtr;
while ((aPtr!= NULL)&&(aPtr->value != numToDelete)){
aPtr = aPtr->next;
}
if (aPtr != NULL) {
printf("aPtr is referencing %d ",aPtr->value);
// let's go find previous node, might need to be careful if only 1 node
struct SSL1 *tmp = myPtr;
while (tmp->next != aPtr)
tmp = tmp->next;
//when we reach here, tmp references
tmp ->next = aPtr->next; // node referenced by aPtr not in list
aPtr->next = NULL;
free(aPtr); // remove node
}
}
void recprintList(struct SSL1 *myPtr) {
if(myPtr == NULL)
return;
else{
recprintList(myPtr->next);
printf("%d ",myPtr->value);
}
}
void printList(struct SSL1 *myPtr){
while (myPtr != NULL){
printf(" value %d is at %p ",myPtr->value,myPtr);
myPtr = myPtr->next;}
}
void sortList(struct SSL1 *myPtr){
// how will we know when we are through the list once?
// we should be looking for the NULL
// how are we going to swap two values?
// we should really keep myPtr referencing the beginning of the list
struct SSL1 *ptr1=myPtr;
struct SSL1 *ptr2=myPtr;
while (ptr1->next != NULL) {
ptr2 = myPtr;
while (ptr2->next != NULL) {
if (ptr2->value < ptr2->next->value) {
int tmp = ptr2->value;
ptr2->value = ptr2->next->value;
ptr2->next->value = tmp;
}
ptr2=ptr2->next;
}// does code above go through linked list once? A-Y B-N
ptr1 = ptr1->next;
}
}
struct SSL1 *insert (struct SSL1 *ourList, int invalue){
// we are going to insert at the beginning of the list
// 1 create space for struct
struct SSL1 * temp = (struct SSL1 *)malloc(sizeof(struct SSL1));
// 2 initialize the values of the node
temp->value = invalue;
//temp->next = NULL; // don't initialize to NULL
temp->next = ourList;
return temp;
}
int main() {
int temp;
struct SSL1 *head = NULL;
// create your first test case here
head=insert(head ,100);
//sortList(head);// we can sort after addition of the element.
head=insert(head ,-138);
//sortList(head);
head=insert(head ,65);
//sortList(head);
head=insert(head ,5);
//sortList(head);
head=insert(head ,29);
//sortList(head);
printf("List before adding 51 ");
recprintList(head);
// inserting the value 51 in correct place
head=insert(head ,51);// adding the 51 to the head
sortList(head);// sort the list
printf(" List after adding 51 ");
recprintList(head);// print ting the list using the recursion method
// create your second test case here
struct SSL1 *newhead = NULL;
newhead=insert(newhead ,100);
//sortList(newhead);
newhead=insert(newhead ,10);
//sortList(head);
newhead=insert(newhead ,30);
//sortList(newhead);
newhead=insert(newhead ,40);
//sortList(newhead);
newhead=insert(newhead ,50);
//sortList(newhead);
printf(" List before adding 20 ");
recprintList(newhead);
// inserting the value 20 in correct place
newhead=insert(newhead ,20);// adding the 20 to the head
sortList(newhead);
printf(" List after adding 51 ");
recprintList(newhead);// print ting the list using the recursion method
return 0;
}
--------output----------
List before adding 51
100 -138 65 5 29
List after adding 51
-138 5 29 51 65 100
List before adding 20
100 10 30 40 50
List after adding 51
10 20 30 40 50 100
--------output----------
Note: Feel free to ask nay question. happy to help. God bless you!!