PROGRAM MUST BE IN C PROGRAMMING AND PLEASE COMPLETE ALL AS WELL AS SEND SCREENS

Question

PROGRAM MUST BE IN C PROGRAMMING AND PLEASE COMPLETE ALL AS WELL AS SEND SCREENSHOT OF OUTPUT FOR THE THUMBS UP! SRC files are given below!

Examine the files list.h and llist.c in the src directory where you found this handout.

You will discover that it is a partially implemented linked list “module”.

The lists store numeric values (the type of which can be changed by altering the typedef for ElemType in list.h).

As in previous projects, the .h file gives the interface for an ADT while the actual implementation is given in the .c file. The members of list_struct are also “hidden” in the .c file. The ADT defines many natural operations on lists -- some of these have already been implemented and will be used as motivating examples during lecture; others have not been implemented: It is your job to do the implementation! Look for TODO labels throughout the files.

A subtle detail: why did I decide to name the header file list.h (one ‘l’), but the implementation file llist.c (two ‘l’s)???

So… part I is completion of all of the TODO items specified.

Rules: you cannot change list.h (except maybe to experiment with different ElemTypes). All of your work is in llist.c (except testing code).

list.h

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

llist.c

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------MakeFile

llist.o: list.h llist.c

gcc -c llist.c

ll_tst: ll_tst.c llist.o

gcc -o ll_tst ll_tst.c llist.o

quad: quad.c

gcc -o quad quad.c

clean:

rm quad ll_tst llist.o

Explanation / Answer

The list.h and llist.c files seemed to be incomplete. Lot of other functions being used in ll_tst.c seemed to be missing in .h as well as llist.c file. So in order to get the test program to work, I modiifed the .h file to include the declarations of all functions needed. I guess you should be having the complete file with other functions as well. I have implemented all other functions as well that were needed by the test program, since it is not possible to test these functions alone without the other functinos in place. If you needed the implementation of only 2 functions, you can take it from list.c file below.

Please don't forget to rate the answer if it helped. Thank you.

list.h

typedef int ElemType;

/************* structs and typedefs *************/

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

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

/** TODO
* function: lst_pop_back
*
* description: removes last element from list
* and returns that value.
*
* Note: if list is empty, the return value is
* implementation specific -- i.e., caller's
* fault.
*
* DIFFICULTY LEVEL: 3
*/
extern ElemType lst_pop_back(LIST *l);

/** TODO
* function: lst_reverse
*
* description: reverses the given list.
* this is different from printing it
* in reverse order!
*
* The ordering of the actual list is
* reversed.
*
* constraint: for full credit, NO MEMORY
* ALLOCATION is allowed in this function;
* it just re-links the already existing
* nodes
*
* DIFFICULTY LEVEL: 3
*/
extern void lst_reverse(LIST *lst);

//******************
LIST * lst_create();
void lst_print(LIST * lst);
ElemType lst_pop_front(LIST * lst);
void lst_push_back(LIST * lst, ElemType e);
void lst_push_front(LIST * lst, ElemType e);
int lst_is_sorted(LIST * lst);
LIST* lst_from_array(ElemType *arr, int size);
void lst_free(LIST * lst);
int lst_count(LIST * lst, ElemType e);
int lst_len(LIST * lst);

llist.c

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

ElemType lst_pop_back(LIST *lst)
{
NODE* curr;
ElemType val;
if(lst != NULL && lst->front != NULL) //list is not empty
{
if(lst->front == lst->back) //single node
{
val = lst->front->val;
free(lst->front);
lst->front = lst->back = NULL;
}
else
{
//goto till last but 1 node
curr = lst->front;
while(curr->next != lst->back)
curr = curr->next;
  
curr->next = NULL; //make this as the last node
val = lst->back->val;
free(lst->back);
lst->back = curr;
}
}
return val;
  
}
void lst_reverse(LIST *lst)
{
NODE *prev, *curr, *temp;
//nothing to do when the list is empty or single element
if(lst == NULL || lst->front == NULL || lst->front == lst->back)
return;
  
//there is min of 2 elements
prev = lst->front;
curr = prev->next;
//for each node , save its next node, update the current node to point to behind node and then move onto saved next node
while(curr != NULL)
{
temp = curr->next; // save next node
curr->next = prev; //update to point to behind node
prev = curr;
curr = temp; //move to saved next
}
  
lst->front->next = NULL; //make the 1st node in original order to point to NULL
//interchange front and back pointers or reversed list
temp = lst->front;
lst->front = lst->back;
lst->back = temp;
}

//***********************
LIST * lst_create()
{
LIST* lst = (LIST*)malloc(sizeof(LIST));
lst->front = NULL;
lst->back = NULL;
return lst;
}

void lst_print(LIST * lst)
{
NODE* curr;
if(lst == NULL)
return;
else
{
curr = lst->front;
while(curr != NULL)
{
printf("%d ", curr->val);
curr = curr->next;
}
  
printf(" ");
}
}
ElemType lst_pop_front(LIST *lst)
{
NODE *next;
ElemType val;
if(lst != NULL && lst->front != NULL) //list is not empty
{
if(lst->front == lst->back) //single node
{
val = lst->front->val;
free(lst->front);
lst->front = lst->back = NULL;
}
else
{
val = lst->front->val;
next = lst->front->next;
free(lst->front);
lst->front = next;
  
}
}
return val;
}

void lst_push_back(LIST * lst, ElemType e)
{
NODE *n = (NODE*) malloc(sizeof(NODE));
n->val = e;
n->next = NULL;
  
if(lst != NULL)
{
if(lst->front == NULL)
lst->front = lst->back = n;
else
{
lst->back->next = n;
lst->back = n;
}
}
}

void lst_push_front(LIST * lst, ElemType e)
{
NODE *n = (NODE*) malloc(sizeof(NODE));
n->val = e;
n->next = NULL;
  
if(lst != NULL)
{
if(lst->front == NULL)
lst->front = lst->back = n;
else
{
n->next = lst->front;
lst->front = n;
}
}
}

int lst_is_sorted(LIST * lst)
{
int retval = 1;
NODE *curr, *prev;
if(lst != NULL && lst->front != lst->back) //make sure there are atleast 2 nodes
{
prev = lst->front;
curr = prev->next;
while(curr != NULL)
{
if(curr->val < prev->val)
{
retval = 0;
break;
}
prev = curr;
curr = curr->next;
}
}
return retval;
}
LIST* lst_from_array(ElemType *arr, int size)
{
LIST* lst = lst_create();
int i;
for(i = 0; i < size; i++)
lst_push_back(lst, arr[i]);
return lst;
}
void lst_free(LIST * lst)
{
NODE *curr, *next;
if(lst != NULL && lst->front != NULL)
{
curr = lst->front;
while(curr != NULL)
{
next = curr->next;
free(curr);
curr = next;
}
lst->front = lst->back = NULL;
free(lst);
}
}

int lst_count(LIST * lst, ElemType e)
{
NODE *curr;
int count = 0;
if(lst != NULL && lst->front != NULL)
{
curr = lst->front;
while(curr != NULL)
{
if(curr->val == e)
count++;
curr = curr->next;
}
}
return count;
}
int lst_len(LIST * lst)
{
NODE *curr;
int count = 0;
if(lst != NULL && lst->front != NULL)
{
curr = lst->front;
while(curr != NULL)
{
count++;
curr = curr->next;
}
}
return count;
}

ll_tst.c

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

// very incomplete small demo/test program...
// You may use this as a template/framework for developing tests

int main() {
LIST *lst1;
int i;

lst1 = lst_create();

for(i=0; i<5; i++) {
lst_push_front(lst1, i);
}
for(i=0; i<5; i++) {
lst_push_back(lst1, i);
}

printf("lst_len(lst1) : %i ", lst_len(lst1));
printf("lst1 contents: ");
lst_print(lst1);

lst_pop_front(lst1);
lst_pop_front(lst1);
printf("lst1 contents after two pops: ");
lst_print(lst1);

// an example of a "real" test

int a[5] = {3, 4, 5, 6, 2};
int b[5] = {3, 4, 5, 6, 8};

LIST *lstA = lst_from_array(a, 5);
LIST *lstB = lst_from_array(b, 5);

if(lst_is_sorted(lstA) )
printf("is_sorted TEST 1 FAILED! ");
else
printf("is_sorted TEST 1 PASSED! ");

if(lst_is_sorted(lstB) )
printf("is_sorted TEST 2 PASSED! ");
else
printf("is_sorted TEST 2 FAILED! ");

/** test code for lst_count **/

// TESTS THAT REQUIRE VISUAL INSPECTION
printf("number of 3's = %i ", lst_count(lst1, 3));
printf("number of 0's = %i ", lst_count(lst1, 0));

/** test code for lst_pop_back **/
  

lst_reverse(lst1);
printf("lst1 after reversing is ");
lst_print(lst1);

lst_pop_back(lst1);
lst_pop_back(lst1);
printf("lst1 after 2 pops at back is ");
lst_print(lst1);

/** test code for lst_push_back **/

lst_free(lst1);
lst_free(lstA);
lst_free(lstB);
}

output

lst_len(lst1) : 10
lst1 contents: 4 3 2 1 0 0 1 2 3 4
lst1 contents after two pops: 2 1 0 0 1 2 3 4
is_sorted TEST 1 PASSED!
is_sorted TEST 2 PASSED!
number of 3's = 1
number of 0's = 2
lst1 after reversing is 4 3 2 1 0 0 1 2
lst1 after 2 pops at back is 4 3 2 1 0 0

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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