https://www.answers.com/homework-help/que ... -q94775068
- Previous Question Https Www Chegg Com Homework Help Questions And Answers File Listc Include Include Include Include 1 (66.37 KiB) Viewed 31 times
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
stack *stack_init() {
// allocate the stack struct
stack *s = malloc(sizeof(stack));
if (!s) {
return NULL;
}
// initialize members for an empty list
s->top = NULL;
s->size = 0;
return s;
}
bool stack_is_empty(const stack *s) {
return s->size == 0;
}
size_t stack_size(const stack *s) {
return s->size;
}
bool stack_push(stack *s, void *elem) {
// allocate storage for a new node
node *n = malloc(sizeof(node));
if (!n) {
return false;
}
// initialize node members so that the node is
in
// front of the current top node
n->elem = elem;
n->next = s->top;
// the top node in the stack is now n
s->top = n;
s->size++;
return true;
}
void *stack_pop(stack *s) {
assert(!stack_is_empty(s));
// get a pointer to the top node so that we can
free the node later
node *top = s->top;
// get the element to return to the caller
void *elem = top->elem;
// pop the element by moving the top pointer to
the next node
s->top = top->next;
s->size--;
// free the old top node
free(top);
return elem;
}
void stack_free(stack *s, free_elem_func free_elem) {
// free all nodes by iterating over all nodes and
freeing
// nodes as they are visited
node *n = s->top;
while (n) {
node *next = n->next;
if (free_elem) {
(*free_elem)(n->elem);
}
free(n);
n = next;
}
// free the stack
free(s);
}
/* iterative version of print
void stack_print(const stack *s) {
printf("TOP, ");
node *n = s->top;
while (n) {
printf("%d, ", n->elem);
n = n->next;
}
printf("BOTTOM\n");
}
*/
void print_rec(const node *n, print_elem_func print_elem);
void stack_print(const stack *s, print_elem_func print_elem)
{
printf("TOP, ");
print_rec(s->top, print_elem);
printf("BOTTOM\n");
}
/**
* Recursive helper function to demonstrate recursion
* on a linked structure.
*
* Prints the elements in all of the nodes starting at
* the specified node n.
*/
void print_rec(const node *n, print_elem_func print_elem) {
// base case
if (!n) {
return;
}
// n not NULL, recursive case
// print the element in n
(*print_elem)(n->elem);
printf(", ");
// then print the remaining elements
print_rec(n->next, print_elem);
}
File stack.h:
#ifndef stack_H
#define stack_H
#include <stdbool.h>
/**
* Name of the node struct used by stack.
*/
typedef struct node node;
/**
* The node struct definition.
*/
struct node {
void *elem;
node *next;
};
/**
* Name of the stack struct.
*/
typedef struct stack stack;
/**
* The stack struct definition.
*/
struct stack {
node *top;
size_t size;
};
/**
* Pointer to function that prints an element.
*/
typedef void (*print_elem_func)(const void *elem);
/*
* Pointer to function that frees an element.
*/
typedef void (*free_elem_func)(void *elem);
stack *stack_init();
bool stack_is_empty(const stack *s);
size_t stack_size(const stack *s);
bool stack_push(stack *s, void *elem);
void *stack_pop(stack *s);
/**
* Free the memory associated with a stack. If
* free_elem is not NULL, then the memory for each
element
* is also freed by calling the provided function;
* otherwise, the elements are not freed.
*/
void stack_free(stack *s, free_elem_func free_elem);
/**
* Prints the elements of the stack where each element
is
* printed using the provided function. Undefined
behavior
* results if print_elem is NULL.
*/
void stack_print(const stack *s, print_elem_func
print_elem);
#endif // stack_H
File Makefile
# Makefile for Assignment 5
list_demo : list.o list_utils.o list_demo.c
gcc -o list_demo list_demo.c list.o
list_utils.o
stack_demo : stack.o stack_utils.o stack_demo.c
gcc -o stack_demo stack_demo.c stack.o
stack_utils.o
list_utils.o : list_utils.h list_utils.c
gcc -c list_utils.c
stack_utils.o : stack_utils.h stack_utils.c
gcc -c stack_utils.c
list.o : list.c list.h
gcc -c list.c
stack.o : stack.c stack.h
gcc -c stack.c
clean :
rm list_demo *.o
5. stack_contains Create the files stack_utils.h and stack_utils.c. All of your code for Question 5 should go into these files. Create a function called stack_contains that takes as input: . a pointer to a const stack, and • avoid pointer val to a value to search the stack for, and • a pointer to a comparison function that can compare two elements pointed at by void pointers for equality and returns true if the stack has an element equal to val . For example: stack *s1 = stack_init(); stack_push(s1, "a"); stack_push(s1, "b"); stack_push(s1, "c"); the stack si has a string element equal to "b" but does not have a string element equal to "z" Our stack implementation is generic; thus, the elements are stored as void pointers. As the implementer of the stack_contains function, you do not know how the user defines equality for their element type; thus, the user must supply a pointer to a function that compares two elements for equality. You should define a typedef for a pointer to an appropriate comparison function in the stack_utils.h header file (see stack.h for examples of typedef statements). Special cases Searching an empty stack or a non-existant stack should return false. 6. stack_demo Create a short C program called stack_demo that demonstrates the functionality of your stack_contains The main function of stack_demo should: • Create a stack of 3 or more strings and print the stack • use stack_contains to test if the stack contains some value that is in the stack and print the result • use stack_contains to test if the stack contains some value that is not in the stack and print the result • create a stack of 3 or more double values and print the stack • use stack_contains to test if the stack contains some value that is in the stack and print the result • use stack_contains to test if the stack contains some value that is not in the stack and print the result When your program prints something it should also print a short message explaining what is being printed (e.g., "stack" "contains 2.5" , etc.)