Programing in C not C Today we are working with singly linke

Programing in C: (not C++)

Today we are working with singly linked lists. Last week in class we covered inserting into, deleting from, sorting, and printing a singly linked list. For lab today we want you to create a new function called insertSorted() that is similar to insert() we created last week, but instead of just inserting the new value at the beginning of the list, 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 -->

We have included the code from class on thursday 11/16, that contains insert( ), deleteFromList( ), sortList( ), and printList( ) so you can use that code as a starting point.

#include <stdio.h>
#include <stdlib.h>

struct SSL1 {
   int value;
   struct SSL1 *next;
  
};

struct SSL1 * deleteFromList(struct SSL1 *myPtr, int value)
{
struct SSL1 *tmpHead=myPtr;
struct SSL1 *head = myPtr;
   while (myPtr != NULL) {
       // look for value
       if (myPtr->value == value) {
           // we found a match
           printf(\"we have found a match will proceed to delete\");
           // right now where is myPtr? (referencing value to be removed)
           // do we know where the beginning of hte list is?
           // A-Y B-N (no we don\'t so we added a variable tmpHead;
           if(tmpHead != myPtr) {
           while(tmpHead->next != myPtr){
               tmpHead = tmpHead->next;
           }
           // we have reference to prev node, so let\'s reroute ptrs
           tmpHead->next = myPtr->next;
           myPtr->next = NULL;
           free(myPtr);
           myPtr=NULL;
//       break;
           }
           else { // at beginning of list and myPtr = tmpHead
           myPtr = myPtr->next;
           tmpHead->next = NULL;
           free(tmpHead);
           return(myPtr);
           }
          
       }
       else
       myPtr = myPtr->next;
   }
   return(head);
}

void printList(struct SSL1 *myPtr){
   while (myPtr != NULL){
       printf(\"%d \",myPtr->value);
       myPtr = myPtr->next;
   }
   printf(\"\ \");
}

void sortList(struct SSL1 *myPtr){
   /*
   1) scan list find smallest value
   2) move smallest value to correct place (end of the sorted space)
   3) loop until done  
   */
  
   struct SSL1 *firstUnSorted;
   struct SSL1 *smallest;
   int tmp;
       firstUnSorted = myPtr;
       smallest = firstUnSorted;
   while (firstUnSorted != NULL){

   while (myPtr != NULL) {
       if (myPtr->value < smallest->value)
           smallest = myPtr;
       myPtr = myPtr->next;
       }
       // here smallest should reference smallest value in list
       printf(\"smallest is %d \ \",smallest->value);   
       tmp= smallest->value;
       smallest->value = firstUnSorted->value;
       firstUnSorted->value = tmp;
       printList(firstUnSorted);
       firstUnSorted = firstUnSorted->next;
       smallest = firstUnSorted;
       myPtr=firstUnSorted;
   }
}

struct SSL1 *insert (struct SSL1 *head, int invalue){
   /* create a new instance of ssl1,
   add invalue to the new instance
   add new instance of ssl1 to existing list at beginning , update head by
   returning the new address of the lis
   */
   struct SSL1 *tempPtr;
   tempPtr = (struct SSL1 *)malloc(sizeof(struct SSL1));
   tempPtr->value = invalue;
   tempPtr->next = head;
   return tempPtr;
}

int main() {
   int temp;
   struct SSL1 *head = NULL;

// create your first test case here

// create your second test case here

   return 0;
  
}

Solution

#include <stdio.h>
#include <stdlib.h>
struct SSL1 {
int value;
struct SSL1 *next;
  
};
struct SSL1 * deleteFromList(struct SSL1 *myPtr, int value)
{
struct SSL1 *tmpHead=myPtr;
struct SSL1 *head = myPtr;
while (myPtr != NULL) {
// look for value
if (myPtr->value == value) {
// we found a match
printf(\"we have found a match will proceed to delete\");
// right now where is myPtr? (referencing value to be removed)
// do we know where the beginning of hte list is?
// A-Y B-N (no we don\'t so we added a variable tmpHead;
if(tmpHead != myPtr) {
while(tmpHead->next != myPtr){
tmpHead = tmpHead->next;
}
// we have reference to prev node, so let\'s reroute ptrs
tmpHead->next = myPtr->next;
myPtr->next = NULL;
free(myPtr);
myPtr=NULL;
// break;
}
else { // at beginning of list and myPtr = tmpHead
myPtr = myPtr->next;
tmpHead->next = NULL;
free(tmpHead);
return(myPtr);
}
  
}
else
myPtr = myPtr->next;
}
return(head);
}
void printList(struct SSL1 *myPtr){
while (myPtr != NULL){
printf(\"%d \",myPtr->value);
myPtr = myPtr->next;
}
printf(\"\ \");
}
void sortList(struct SSL1 *myPtr){
/*
1) scan list find smallest value
2) move smallest value to correct place (end of the sorted space)
3) loop until done
*/
  
struct SSL1 *firstUnSorted;
struct SSL1 *smallest;
int tmp;
firstUnSorted = myPtr;
smallest = firstUnSorted;
while (firstUnSorted != NULL){
while (myPtr != NULL) {
if (myPtr->value > smallest->value)
smallest = myPtr;
myPtr = myPtr->next;
}
// here smallest should reference smallest value in list
//printf(\"smallest is %d \ \",smallest->value);   
tmp= smallest->value;
smallest->value = firstUnSorted->value;
firstUnSorted->value = tmp;
//printList(firstUnSorted);
firstUnSorted = firstUnSorted->next;
smallest = firstUnSorted;
myPtr=firstUnSorted;
}
}
struct SSL1 *insert (struct SSL1 *head, int invalue){
/* create a new instance of ssl1,
add invalue to the new instance
add new instance of ssl1 to existing list at beginning , update head by
returning the new address of the lis
*/
struct SSL1 *tempPtr;
tempPtr = (struct SSL1 *)malloc(sizeof(struct SSL1));
tempPtr->value = invalue;
tempPtr->next = head;
return tempPtr;
}

/* insert in sorted order*/
struct SSL1 *insertSorted (struct SSL1 *head, int invalue){

struct SSL1 *temp,*temp1;
temp = (struct SSL1 *)malloc(sizeof(struct SSL1));
temp->value = invalue;
temp->next = NULL;
  
//head reference
temp1 = head;
// if head is empty make temp as head
if(head==NULL){
return temp;
}
  
// insert at beginning.
if(temp1->value<=invalue){
temp->next = temp1;
return temp;
}
  
// insert in middle
while(temp1->next!=NULL){
if(temp1->next->value<invalue){
temp->next = temp1->next;
temp1->next = temp;
return head;
}
else{
temp1 = temp1->next;
}
}
  
// insert at the end.
temp1->next = temp;
return head;
  
}

int main() {
int temp;
setvbuf(stdout, NULL, _IONBF, 0);
struct SSL1 *head = NULL;
head = insert(head,65);
head = insert(head,100);
head = insert(head,29);
head = insert(head,-138);
head = insert(head,-5);
sortList(head);
printList(head);
head = insertSorted(head,51);
printList(head);
return 0;
  
}
/* sample output
100 65 29 -5 -138
100 65 51 29 -5 -138
*/