Question

this is part of my code im not sure how to do last 2 function. i think above last 2 functions need for making function please help me how to do it.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h"

typedef struct node {
ElemType val;
struct node *next;
} NODE;

struct list_struct {
NODE *front;
NODE *back;
};

int lst_remove_first(LIST *l, ElemType x) {

NODE *p;
NODE *tmp;

if(l->front == NULL) return 0;
if(l->front->val == x) {
   lst_pop_front(l);
   return 1;
}
// lst non-empty; no match on 1st elem
p = l->front;

while(p->next != NULL) {
if(x == p->next->val) {
   tmp = p->next;
   p->next = tmp->next;
   if(tmp == l->back)
   l->back = p;
   free(tmp);
   return 1;
}
p = p->next;
}
return 0;
}

int lst_remove_all_slow(LIST *l, ElemType x) {
int n=0;
while(lst_remove_first(l, x))
   n++;
return n;
}

/**
* function: lst_sra_bad_case (sra: slow_remove_all)
*
* description: constructs a list of length n such that
* the above function takes quadratic time to remove
* all occurrences of a specified value.
*
* By convention, the specified value will be 0
*/
LIST *lst_sra_bad_case(int n) {
LIST *lst;
int i;

   // idea: first n/2 elements are non-zero
   // the last n/2 are zeros
   // ever call to lst_remove_first will
   // have to walk through all of the 1's
   // [ 1 1 1 1 1 1 1 0 0 0 0 0 0 0 ]

   lst = lst_create();
   for(i=0; i<n/2; i++)
       lst_push_front(lst, 0);
   for(i=0; i<(n-n/2); i++)
       lst_push_front(lst, 1);
   return lst;
}

/** 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
*/
int lst_remove_all_fast(LIST *l, ElemType x) {
return 0;
}

// TODO
int lst_is_sorted(LIST *l){

return 0;

}

Answer 1

Hopefully, this code should work. If not, please provide the header file list.h, so that we can debug the code, and solve the problems for you.

/** 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
*/
int lst_remove_all_fast(LIST *l, ElemType x) {
NODE *p;
NODE *tmp;
int n = 0;
if(l->front == NULL) return n;
if(l->front->val == x) {
lst_pop_front(l);
n++;
}
// lst non-empty; no match on 1st elem
p = l->front;
while(p->next != NULL) {
if(x == p->next->val) {
tmp = p->next;
p->next = tmp->next;
if(tmp == l->back)
l->back = p;
free(tmp);
n++;
}
p = p->next;
}
return n;
}
/** TODO
* function: lst_is_sorted
*
* description: returns 1 if the list is sorted in
* non-decreasing order; 0 otherwise
*/
int lst_is_sorted(LIST *l){
NODE *p;
NODE *tmp;
if(l->front == NULL) return 1;
  
// lst non-empty;
p = l->front;
while(p->next != NULL) {
x = p->val;
if(x > p->next->val) {
  
return 0;
}
p = p->next;
}
return 1;
}