Can anybody help on how to do this with C?

Post by **answerhappygod** » Fri Jul 08, 2022 6:45 am

: Can Anybody Help On How To Do This With C 1 (247.38 KiB) Viewed 39 times

: Can Anybody Help On How To Do This With C 2 (51.39 KiB) Viewed 39 times

: Can Anybody Help On How To Do This With C 3 (16.34 KiB) Viewed 39 times

: Can Anybody Help On How To Do This With C 4 (18.77 KiB) Viewed 39 times

Assignment 2 Stacks and Linked Lists In this assignment you are given code for a Stack. However, this code has been implemented using Arrays. You will need to rewrite the code (from scratch) implementing the Stack using Linked Lists instead of Arrays. Use the Arrays implementation code provided as a guide for your Linked List implementation. The demo/driver code should not be touched/changed (with the exception of uncommenting/commenting out 2 lines, as described below). It should work for either the Linked List or Array implementation (this is called "encapsulation" in computer science and is a fundamental principle of coding and software engineering, essentially stating that a program/function should not need to know how another program/function works only how to call that function, what data to provide it, and what data it will return). You will need to re-code the "stackArray.c" and "stackArray.h" files: Create 2 new files called "stackLinked List.h" and "stackLinkedList.c". • Create a "make" file that will run the necessary compiler commands to compile stackDemo.c with your stackLinkedList.h and stackLinkedList.c. • All of the function declarations and the boolean enum definition in stackArray.h must NOT be changed. Simply copy and paste them into your new stackLinkedList.h file. The only exception to this could be the "isFull" function (theoretically, the list has no "full" limit; concretely, it is limited by the amount of memory on the computer running the algorithm), so you may choose to not implement/define that function if you wish. • Include a modified Stack definition and add a Node definition in stackLinkedList.h. The data held by the node is the same as the data held by the array in stackArray.h. • Code/Implement each function declaration from stackLinked List.h in stackLinkedList.c using the newly defined Stack and Node. REMEMBER: there are different cases and checks you will need to handle: o If you malloc ANYTHING you must check that the pointer returned to you from the malloc is not NULL; if it is NULL then you will need to print an error message and then return from the function. o Your insert/delete (i.e., push/pop) implementation must be O(1) time. There are 2 main approaches to do this, you may use either. o There may be cases where you need to check that the list is empty before performing certain actions. o When you free a struct, make sure you free anything malloc-ed INSIDE the struct first, then the struct itself. Run valgrind to be sure you have no memory leaks. • Uncomment "#include "stackLinkedList.h"" from stackDemo.c and then comment out "#include "stackArray.h" ". • Compile and run stackDemo.c (using your make file), verify output, and then zip the files and turn it in on blackboard.
Notes/Hints: • In order to run the stackDemo program you will need to have "stackDemo.c", "stackArray.c", and "stackArray.h" in the same folder and then (from that folder) run: o gcc-c stackArray.c o gcc -c stackDemo.c o gcc stackDemo.o stackDemo.o -o stackDemo o/stackDemo The commands will be the same for the stackLinkedList implementation (just put into a make file and with the "stackLinked List" names instead of the "stackArray" names). • You may look at Lecture 3 for a make file template if you are unsure how to implement one. • Drawing pictures of the actions and going through some example states of the Linked List is often extremely helpful if you get stuck or are confused. I am available to help via email and in office hours. You make work with 1 partner on this assignment. You may also wish to review the Linked List lecture notes that has some code relevant to the assignment.
#include "stackArray.h" 18 * Default starting size for the stack int const STACK_STARTING_CAPACITY = 50; /* createStack input: none * output: a pointer to a stack (this is malloc-ed so must be freed eventually!) * Creates a new empty stack and returns a pointer to it. 8/ Stack *createStack(){ Stack *ps = (Stack *) malloc( sizeof (Stack)); ps->top= -1; ps->capacity = STACK_STARTING_CAPACITY; ps->data = (char **) malloc(sizeof(char *)*STACK_STARTING_CAPACITY ); return ps; } /* freeStack * input: a pointer to a stack * output: none * frees the given stack pointer. Also call freeStackElements if you want to free every element in the stack. 8/ void freeStack( Stack *ps ){ free (ps); } /* freeStackElements * input: a pointer to a stack output: none * pops and then frees all of the elements currently in the stack. Does not free the stack itself. Call freeStack to also free the stack. 3/ void freeStackElements ( Stack *ps ){ while( isEmpty (ps) == FALSE){ free( pop (ps) ); } } /* pop * input: a pointer to a stack * output: a string pops and returns the char* stored in the top element in the stack. It does not free the pop-ed element. 3/ char *pop(Stack *ps ) { if( isEmpty( ps ) ) { printf("Tried to pop, but Stack was empty\n"); return NULL; } return ps->data[ ps->top-- ]; /* push * input: a pointer to a stack, a string output: none
/* push input: a pointer to a stack, a string * output: none * pushes the string onto the top of the given stack. void push( Stack *ps, char *str ){ if(isFull( ps ) ) { * 1T 1sEmpty ps ) }{\ printf("Tried to pop, but Stack was empty\n"); return NULL; } /* top } return ps->data[ ps->top- ]; } /* 8 /* resize the array */ ps->capacity *= 2; ps->data (char **) realloc( ps->data, ps->capacity*sizeof(char *) ); } ps->data[ ++ps->top ] = str; * returns the string on top of the stack char *top( Stack *ps ) { if( isEmpty( ps ) ) { printf("Tried to peek at the top of the Stack, but it was empty.\n"); return NULL; input: a pointer to a stack output: a string * } return ps->data[ ps->top ]; is Empty input: a pointer to a stack output: a boolean * returns TRUE if the stack is empty and FALSE otherwise 8/ boolean isEmpty( Stack *ps ){ if(ps->top == -1){ return TRUE; } return FALSE; } /* is Full * input: a pointer to a stack * output: a boolean returns TRUE if the stack is at capacity currently and FALSE otherwise * Note that the stack handle resizing automatically so you do not need to ever run this as a user of stack. */ boolean isFull( Stack *ps ) { if(ps->capacity == ps->top+1 ){ return TRUE; } return FALSE;
#ifndef _stackArray_h #define stackArray_h #include #include typedef enum boolean { FALSE, TRUE} boolean; typedef typedef struct Stack char **data; int top; int capacity; } Stack; /*string data stored in the stack*/ /*index of the last element in the array*/ /*current capacity of stack*/ Stack "createStack(); void freeStack( Stack ps ); void freeStackElements ( Stack *ps ); char *pop(Stack *ps ); void push( Stack *ps, char *str); char *top(Stack *ps ); boolean isEmpty( Stack *ps ); boolean isFull( Stack "ps ); #endif
#include #include #include "stackArray.h" /*#include "stackLinkedList.h"*/ int main(int argc, char *argv[]) { int i = 0; Stack *ps = createStack(); char "buffer; while( i<=99 ) { i++; printf("\n"); while( i>=0 ) { } buffer= (char *)malloc( 3 ); sprintf( buffer, "%d", i); push( ps, buffer); printf("push %d\n", i); } if (top(ps) != NULL) { printf("pop %s\n", top( ps ) ); free pop(ps ) ); i--; } else{ } break; freeStackElements (ps); freeStack( ps ); return 0;