Question

C Programming

Take screenshot of compiled output once complete. (which should look similar to the sample one provided). Will rate positively.

Problem:

(1) Add PopTailSLL() as a new member function to the SLL abstract data type. “Unlink” the logically-last node (tail) from the list *sll, call the DestructElement function to destruct the object pointed-to by the node’s element data member, free() the node, and decrement size. A SLL_UNDERFLOW exception occurs when size = 0.

void PopTailSLL(SLL *sll);

Hint PopTailSLL() is similar to PopHeadSLL(), but the PopTailSLL() algorithm must do a little more work than PopHeadSLL() to complete the “unlinking” that is required:

(2) Add IsInSLL() as a new member function to the SLL abstract data type. Return true when at least one node in *sll contains an element data member that points-to a character string that compares “equal to” the string pointed-to the parameter element; otherwise return false.

bool IsInSLL(const SLL *sll,const char *element);

(3) Add TraverseSLL() as a new member function to the SLL abstract data type. Traverse *sll from head-to-tail; that is, visit each node in *sll one time. When visiting a node, invoke the client?supplied call-back function pointed-to by the function-pointer parameter ProcessElement; the call-back function then processes the character string that the element data member points-to in a meaningful, client application-specific way. Note The strings passed to the call-back can be changed by the call-back function’s execution. For example, the call-back function could “flip” the case of the string’s alphabetic characters or reverse the string contents or replace the contents with an entirely different set of characters.

void TraverseSLL(const SLL *sll,void (*ProcessElement)(char *element));

Note You will need to add the prototypes for the new member functions to SLL.h and add the new member function definitions to SLL.c.

(4)

Take screenshot of compiled output once complete. (which should look similar to the sample one provided). Will rate positively.

Sample Program Dialo E:COURSEsyCS1311Code'ADTsSLLVProblem2.exe ushN? ? PJHHMP WNXY MERLCW DSM PHDMG MNFMAS QECRET It took 154341 tries to find "DSM" PopTailsLLO-ed "QECRET PopTai1SLL-ed "MNFMAS" PopTailS LL()-ed ·PHDMG PopTa?1SLL()-ed ''DSM PJHHMP WNXY MERLCW DSM PHDMG MNFMAS PJHHMP WNRY MERLCW DSM PHDMG PJHHMP WNXY MERLCW DSH PJHHMP WNXY MERLCW PopTa?1SLL()-ed PopTailSLL-ed ''WNXY "PJHHMP" PJHHMP <enpty> pushN? 7 WFCZIZJOT OYNAUU QIG PIBGD NSM IIPY It took 2714 tries to find "NSM" PopTailSLLC-ed "IIPY PopTai1SLLC-ed "NSM PopTai1SLL-ed "PIBGD" PopTa?1SLL()-ed "QIG PopTai1SLLC-ed "OYNAUU PopTailSLL-ed "ZIZJOT" PopTai1SLLO-ed "OWFC OWFC ZIZJOT OYNAUU QIG PIBGD NSM OUFC ZIZJOT OYNAUU IG PIBGD OWFC XZIZJOT OYNAUU QIG OWFC ZIZJOT OYNAUU OWFC (enpty> pushN? 7 JOQPCU ENRU QGIWYRUEBK FXNAU JJUXQNU ITFMMKT It took 4729575 tries to find "ENRU" JOQPCU ENRU QGIWYQ RUEBK FXNAU JJUXQNU JOQPCU ENRU QGIWYQ RUEBK FXNAU J0QPCU ENRU QGIYQ RUEBK JOQPCU ENRU QGIWYq JOQPCU ENRU JOQPCU (enpty) PopTailSLL-ed "ITFHMKT" PopTai1SLLC-ed "FNAU PopTailSLLC-ed "RUEBK" PopTai1SLLC-ed "QGIWYQ " PopTa?1SLL()-ed "JOQPCU Press any key to continue . " " -

//--------------------------------------------------------------

// SLL ADT Problem #2

// Problem2.c

//--------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include "..\Random.h"

#include ".\SLL.h"

//--------------------------------------------------------------

int main()

//--------------------------------------------------------------

{

   void DestructElement(const char *element);

   char *NewElement();

   void DisplayElement(char *element);

   int pushN;

   SetRandomSeed();

   printf("pushN? ");

   while ( scanf("%d",&pushN) != EOF )

   {

      SLL sll;

      int n,tries;

      char *key = NewElement();

      ConstructSLL(&sll,DestructElement);

      for (n = 1; n <= pushN; n++) PushHeadSLL(&sll,NewElement());

      TraverseSLL(&sll,DisplayElement); printf("\n\n");

     

      tries = 1;

      while ( !IsInSLL(&sll,key) )

     {

         tries++;

         free(key);

         key = NewElement();

      }

      printf("It took %d tries to find \"%s\"\n\n",tries,key);

      free(key);

      while ( !IsEmptySLL(&sll) )

      {

         printf("PopTailSLL()-ed \"%-7s\"\t",PeekSLL(&sll,GetSizeSLL(&sll)-1));

         PopTailSLL(&sll);

         if ( IsEmptySLL(&sll) )

            printf("(empty)\n");

         else

            TraverseSLL(&sll,DisplayElement), printf("\n");

      }

      DestructSLL(&sll);

      printf("\npushN? ");

   }

   system("PAUSE");

   return( 0 );

}

//--------------------------------------------------------------

char *NewElement()

//--------------------------------------------------------------

{

   const char ALPHABET[] = "ABCDEFGHIJKLM"

                           "NOPQRSTUVWXYZ";

   int i;

   int len = RandomInteger(3,7);

   char *element = (char *) malloc(sizeof(char)*(len+1));

   for (i = 0; i <= len-1; i++)

      element[i] = RandomCharacter((char *) ALPHABET,26);

   element[len] = '\0';

   return( element );

}

//--------------------------------------------------------------

void DisplayElement(char *element)

//--------------------------------------------------------------

{

   printf("%s ",element);

}

//--------------------------------------------------------------

void DestructElement(const char *element)

//--------------------------------------------------------------

{

   free((char *) element);

}

//--------------------------------------------------------------

// Singly-linked list (SLL) abstract data type

// SLL.h

//--------------------------------------------------------------

#ifndef SLL_H

#define SLL_H

//==============================================================

// Data model definitions

//==============================================================

typedef struct SLLNODE

{

   char *element;

   struct SLLNODE *FLink; // (F)orward Link to logically-next node

} SLLNODE;

typedef struct SLL

{

   int size;

   SLLNODE *head;         // pointer-to logically-first node

   SLLNODE *tail;         // pointer-to logically-last node

   void (*DestructElement)(const char *element);

} SLL;

//==============================================================

// Public member function prototypes

//==============================================================

void ConstructSLL(SLL *sll,

                  void (*DestructElement)(const char *element));

void DestructSLL(SLL *sll);

void PushHeadSLL(SLL *sll,const char *element);

void PopHeadSLL(SLL *sll);

void PushTailSLL(SLL *sll,const char *element);

char *PeekSLL(const SLL *sll,const int offset);

bool IsEmptySLL(const SLL *sll);

int GetSizeSLL(const SLL *sll);

//==============================================================

// Private utility member function prototypes

//==============================================================

// (none)

#endif

//--------------------------------------------------------------

// Singly-linked list (SLL) abstract data type

// SLL.c

//--------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include ".\SLL.h"

#include "..\ADTExceptions.h"

//--------------------------------------------------------------

void ConstructSLL(SLL *sll,

                  void (*DestructElement)(const char *element))

//--------------------------------------------------------------

{

   sll->size = 0;

   sll->head = NULL;

   sll->tail = NULL;

   sll->DestructElement = DestructElement;

}

//--------------------------------------------------------------

void DestructSLL(SLL *sll)

//--------------------------------------------------------------

{

   while ( !IsEmptySLL(sll) )

   {

      PopHeadSLL(sll);

   }

}

//--------------------------------------------------------------

void PushHeadSLL(SLL *sll,const char *element)

//--------------------------------------------------------------

{

   SLLNODE *p = (SLLNODE *) malloc(sizeof(SLLNODE));

   if ( p == NULL ) RaiseADTException(MALLOC_ERROR);

   p->element = (char *) element;

   if ( IsEmptySLL(sll) )

   {

      p->FLink = NULL;

      sll->head = p;

      sll->tail = p;

   }

   else

   {

      p->FLink = sll->head;

      sll->head = p;

   }

   sll->size++;

}

//--------------------------------------------------------------

void PopHeadSLL(SLL *sll)

//--------------------------------------------------------------

{

   SLLNODE *p = sll->head;

   if ( GetSizeSLL(sll) == 0 ) RaiseADTException(SLL_UNDERFLOW);

   if ( GetSizeSLL(sll) == 1 )

   {

      sll->head = NULL;

      sll->tail = NULL;

   }

   else

   {

      sll->head = p->FLink;

   }

   if ( sll->DestructElement != NULL ) sll->DestructElement(p->element);

   free(p);

   sll->size--;

}

//--------------------------------------------------------------

void PushTailSLL(SLL *sll,const char *element)

//--------------------------------------------------------------

{

   SLLNODE *p = (SLLNODE *) malloc(sizeof(SLLNODE));

   if ( p == NULL ) RaiseADTException(MALLOC_ERROR);

   p->element = (char *) element;

   p->FLink = NULL;

   if ( IsEmptySLL(sll) )

   {

      sll->head = p;

      sll->tail = p;

   }

   else

   {

      sll->tail->FLink = p;

      sll->tail = p;

   }

   sll->size++;

}

//--------------------------------------------------------------

char *PeekSLL(const SLL *sll,const int offset)

//--------------------------------------------------------------

{

   SLLNODE *p = sll->head;

   int i;

   if ( !((0 <= offset) && (offset <= GetSizeSLL(sll)-1)) ) RaiseADTException(SLL_OFFSET_ERROR);

   for (i = 0; i <= offset-1; i++)

      p = p->FLink;

   return( p->element );

}

//--------------------------------------------------------------

bool IsEmptySLL(const SLL *sll)

//--------------------------------------------------------------

{

   return( sll->size == 0 );

}

//--------------------------------------------------------------

int GetSizeSLL(const SLL *sll)

//--------------------------------------------------------------

{

   return( sll->size );

}

//--------------------------------------------------------------

// ADTExceptions.h

//--------------------------------------------------------------

#ifndef ADTEXCEPTIONS_H

#define ADTEXCEPTIONS_H

// ADT exception definitions

#define MALLOC_ERROR                "malloc() error"

#define DATE_ERROR                  "DATE error"

#define STACK_CAPACITY_ERROR        "STACK capacity error"

#define STACK_UNDERFLOW             "STACK underflow"

#define STACK_OVERFLOW              "STACK overflow"

#define STACK_OFFSET_ERROR          "STACK offset error"

// ADT exception-handler prototype

void RaiseADTException(char exception[]);

#endif

//--------------------------------------------------------------

// ADTExceptions.c

//--------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include ".\ADTExceptions.h"

//--------------------------------------------------------------

void RaiseADTException(char exception[])

//--------------------------------------------------------------

{

   fprintf(stderr,"\a\nException \"%s\"\n\n",exception);

   system("PAUSE");

   exit( 1 );

}

/--------------------------------------------------

// Random.h

//--------------------------------------------------

#ifndef RANDOM_H

#define RANDOM_H

#include <stdbool.h>

// Initialize the "seed" used by the "rand()" function in <stdlib.h>.

void SetRandomSeed(void);

// Return a uniformly and randomly chosen integer from [ LB,UB ].

int RandomInteger(int LB,int UB);

// Return a uniformly and randomly chosen real number chosen from [ 0.0,1.0 ).

double RandomReal(void);

// Return a uniformly and randomly chosen boolean from { false,true }.

bool RandomBoolean(void);

// Return a uniformly and randomly chosen character from characters[i] i in [ 0,(size-1) ].

char RandomCharacter(char characters[],int size);

#endif

//--------------------------------------------------

// Random.c

//--------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <time.h>

#include ".\Random.h"

//--------------------------------------------------

void SetRandomSeed(void)

//--------------------------------------------------

{

   srand(time(NULL));

}

//--------------------------------------------------

int RandomInteger(int LB,int UB)

//--------------------------------------------------

{

   return( (int) (RandomReal()*(UB-LB+1)) + LB );

}

//--------------------------------------------------

double RandomReal()

//--------------------------------------------------

{

   int R;

   do

      R = rand();

   while ( R == RAND_MAX );

   return( (double) R/RAND_MAX );

}

//--------------------------------------------------

bool RandomBoolean(void)

//--------------------------------------------------

{

   return( RandomInteger(1,10000) <= 5000 );

}

//--------------------------------------------------

char RandomCharacter(char characters[],int size)

//--------------------------------------------------

{

   return( characters[RandomInteger(0,(size-1))] );

}

Answer 1

Add below entries in SLL.h file:

void PopTailSLL(SLL *sll);

bool IsInSLL(SLL *sll, const char *element);

void TraverseSLL(const SLL *sll,void (*ProcessElement)(char *element));

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

Add below functions in SLL.c file:

void PopTailSLL(SLL *sll)

//--------------------------------------------------------------

{

SLLNODE *p = sll->head;

if ( GetSizeSLL(sll) == 0 ) RaiseADTException(SLL_UNDERFLOW);

if ( GetSizeSLL(sll) == 1 )

{

sll->head = NULL;

sll->tail = NULL;

}

else

{

// Traverse List till we reach node->Flink equals to tail node of sll.

while (p->Flink != sll->tail)

p = p->Flink;

sll->tail = p;

p = p->Flink;

sll->tail->Flink = NULL;

}

if ( sll->DestructElement != NULL ) sll->DestructElement(p->element);

free(p);

sll->size--;

}

bool IsInSLL(SLL *sll, const char *element)

//--------------------------------------------------------------

{

SLLNODE *p = sll->head;

if ( GetSizeSLL(sll) == 0 ) RaiseADTException(SLL_UNDERFLOW);

while (p != NULL) {

if (!strcmp(p->element, element))

return true;

p = p->Flink;

}

return false;

}

void TraverseSLL(const SLL *sll,void (*ProcessElement)(char *element))

{

SLLNODE *p = sll->head;

if ( GetSizeSLL(sll) == 0 ) RaiseADTException(SLL_UNDERFLOW);

while (p != NULL) {

(*ProcessElement)(p->element);

p = p->Flink;

}

}