MUST BE WRITTEN IN C PROGRAMMING, PLEASE TAKE SCREENSHOT OF OUTPUT! /***********

Question

 MUST BE WRITTEN IN C PROGRAMMING, PLEASE TAKE SCREENSHOT OF OUTPUT! /************* structs and typedefs *************/  typedef struct node {     ElemType val;     struct node *next; } NODE;   struct list_struct {     NODE *front;     NODE *back; }; /************* structs and typedefs *************/   /* * returns pointer to newly created empty list */ LIST *lst_create() { LIST *l = malloc(sizeof(LIST));    l->front = NULL;   l->back = NULL;   return l; }  LIST * lst_from_array(ElemType a[], int n) { int i; LIST *lst;    lst  = lst_create();    for(i=n-1; i>=0; i--)     lst_push_front(lst, a[i]);   return lst; }  /** HEADER FILE ^ 

     /** TODO  * function:  lst_remove_all_fast  *  * description:  same behavior as lst_remove_all_slow but has  *      faster execution time even on "bad cases" as generated by  *      the function above.  Number of operations proportional to the   *      length of the list regardless of number of matches and distribution  *      of matches.  *  * Approach:  all occurrences of x removed in a single pass   *  * returns: number of elements removed  *  * DIFFICULTY LEVEL:  3+  */ extern int lst_remove_all_fast(LIST *l, ElemType x) ;  /** TODO  (part of previous lab, but no solution provided!)  * function:  lst_is_sorted  *  * description:  returns 1 if the list is sorted in   *      non-decreasing order; 0 otherwise  *  * DIFFICULTY LEVEL:  1  */ extern int lst_is_sorted(LIST *l); 

Explanation / Answer

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

typedef struct node{
   int val; //Assuming int for the ElemType
   struct node *next;

} NODE;

typedef struct list_struct{

    NODE *front;
    NODE *back;
}LIST;

LIST *lst_create(){

   LIST *l;
   l = (LIST *)malloc(sizeof(LIST));
   l->front = NULL;
   l->back = NULL;
   return l;
}

void lst_push_front(LIST *lst,int a){

   NODE *node;
   node = (NODE *)malloc(sizeof(NODE));
   node->val = a;
   node->next = NULL;
   if (lst->front == NULL){
       lst->front = node;
       lst->back = node;
   }
   else {
      node->next = lst->front;
      lst->front = node;
   }
}

LIST *lst_from_array(int a[], int n){
   int i;
   LIST *lst;
   NODE *ptr;

   lst = lst_create();

   for (i=n-1; i>=0; i--)
       lst_push_front(lst,a[i]);

   return lst;
}

int lst_is_sorted(LIST *lst){

    NODE *ptr;

    if (lst->front == NULL){
       return 1;
    }  
    ptr = lst->front;
    while (ptr->next != NULL){
         if (ptr->val > ptr->next->val){
            return 0;
         }
         ptr = ptr->next;
    }
    return 1;
}

int lst_remove_all(LIST *slst, int a){

   NODE *ptr;
   int count = 0;

   if (lst->front == NULL){
      return 0;
   }
   ptr = lst->front;

   while (ptr->val == a){
       lst->front = lst->front->next;
       ptr = lst->front;
       count++;      
   }
   ptr = lst->front;
   while (ptr->next != NULL){
        if (ptr->next->val == a) {
            ptr->next = ptr->next->next;
            count++;
        }
        else {
          ptr = ptr->next;
        }
   }
   return count;
}

void disp(LIST *lst){

   NODE *ptr;

   ptr = lst->front;

   while (ptr != NULL){
       printf("%d ", ptr->val);
       ptr = ptr->next;
   }
   printf(" ");
}

int main(){

   int a[5] = {1,2,3,3,4};
   LIST *lst;
   NODE *ptr;
   
   lst = lst_from_array(a,5);
   disp(lst);
   printf("%d ",lst_remove_all(lst,3));
   disp(lst);
   printf("%d ", lst_is_sorted(lst));
   
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.