关于算法:CMPUT-201解题技巧

CMPUT 201 – Winter 2021
Assignment 3
Dynamic memory allocation
Linked Lists
Program organization
Header files and Makefiles
Adhering to provided code stubs
Program testing
Asserts
IF YOU HAVE NOT EXPLICITLY TOLD US YOU WANT TO WORK IN A PAIR, THEN
YOU ARE WORKING INDIVIDUALLY FOR THIS ASSIGNMENT. You will still have a team
name assigned to you but this team will only have 1 member: you.
Before clicking on the github classroom link below, please check your assigned team name
on eClass first. The process for joining a team is as before (if you are the first one to join,
you will create the team on GitHub classroom; if you are working with a partner and they
already joined, you will simply find the team name on the list and click on it).
The github classroom assignment invitation link is
https://classroom.github.com/… READ BELOW BEFORE CLICKING ON THIS
LINK
At thte end, you will have a repository with the following name:
https://gihub.com/cmput201-w2… .
Please update the LICENSE.md file with only your name (if working individually) or both
partner names (if working in a pair) where it says <student name>
Your GitHub starter repo is a bit different this time: you will already find the two folders
Concepts Covered
GitHub Instructions
for Part 1 and Part 2 of the assignment. In each part, you will find the header file you need
to adhere to and a sample C client file. Additionally, you will find a script called
check.sh in the main directory. Simply run ./check.sh to run the script against
your code. Documentation on what the script checks for can be found at the top of the
script. Note that your program should not fail any of the assert checks we have in the client
code. Please read the RepoStructure.md to understand the files provided in the
repo and how to find and interpret the Github Actions build status
Make sure to continuously commit and to your repository as you are developing your
assignment and not simply when you are done. This serves two purposes: (1) you always
have a backup of your code and can navigate through history to see your changes or revert
back to an old version of the code that worked better and (2) showing your progress
through the assignment allows us to see each partner’s contribution. Additionally, these
commits are a great way to show your changes and contributions if you are suspected of
plagiarism. To avoid overloading GitHub actions, you can commit locally as much as you
want but push only once every hour or at the end of your current working session (or when
you want to communicate your changes to your partner). We strongly recommend that you
watch the git tutorials on YouTube to avoid running into merge conflicts while working with
your partner on the assignment.
This assignment consists of two parts. For both parts of the assignment, we will be
checking for memory leaks; if you remove an element or nuke a list, or anything like
that, don’t forget to clean up and free any allocated memory as necessary. The
general rule is if you dynamically allocate any memory yourself, you need to free it yourself
too. You can use valgrind to check for memory leaks.
You must use dynamic memory allocation in this assignment. If you do not, you will
get a 0, even if your program behaves correctly
Your program must compile using -std=c99 -Wall without any warnings or errors. If
we cannot compile your program or if it compiles with a warning, you will receive a 0
for the assignment.
Any missing files will result in a 0 in the assignment. Please check the list of files your need
to submit for each part. If you forget the README, Makefile, etc., you will get a 0. Please
make use of the script we already provide you in your repo to check the format of
your submission.
You need only 1 ReadMe file in the root folder of your repository. Please see
https://www.makeareadme.com/ for information about how to create a good ReadMe file,
especially in markdown notation. Your README file should also have a references section
Important Information
that lists your references (e.g., any online resources you used) and the contributions of both
partners (if working in a team).
You must adhere to the provided function prototypes. You are free to add extra helper
functions, but you must implement the given functions without changing their signature.
Credits: This assignment has been adapted from one of Mike Godfrey’s assignments.
We’re going to implement a data structure called Squeue , because it’s a bit like both a Stack
and a Queue, that allows new elements to be added / removed / peeked at both ends of the list.
A Squeue supports the following operations (details to follow): initSqueue ,
isEmpty , addFront , leaveFront , mergeFront , peekFront , addBack ,
leaveBack , peekBack , mergeBack , print , and nuke . initSqueue and
isEmpty do the obvious things.
The four operations addFront , leaveFront , mergeFront and peekFront
operate on the front of the list.
The four operations addBack , leaveBack , peekBack and mergeBack operate
on the back of the list.
It is essential that you use the EXACT function prototypes provided. Otherwise, we will
not be able to compile and test your code and you will get a 0.
We’re going to implement our Squeue by using Nodes that have links in both directions
(forwards and backwards), plus we are going to keep two special pointers: one to the first
element and one to the last element. The following shows the structs we expect.
struct Node{
char* val;
struct Node* next;
struct Node* prev;
};
typdef struct{
struct Node* first;
struct Node* last;
} Squeue;
You must implement the Squeue using the exact structs above. We have provided you with a
Part I (50 marks)
header file that contains all the signatures of all functions you need to implement. You will find
this header file in a folder called Part1 in your GitHub repo. Here is the list again anyways
(detailed description of the functions follows):
void initSqueue (Squeue **squeue);
bool isEmpty (const Squeue *squeue);
void addFront (Squeue squeue, char val);
void addBack (Squeue squeue, char val);
void leaveFront (Squeue *squeue);
char peekBack (const Squeue squeue);
void leaveBack (Squeue *squeue);
char peekFront (const Squeue squeue);
void print (const Squeue * squeue, char direction);
void nuke (Squeue * squeue);
void mergeFront(Squeue* squeue, char direction);
void mergeBack(Squeue* squeue, char direction);
void reverse(Squeue* squeue);
void destroySqueue(Squeue **squeue);
The following is an example of a main program that shows what is expected from each function.
int main1 () {
Squeue *s1 = NULL;
initSqueue (&s1);
addFront (s1, “alpha”);
addFront (s1, “beta”);
addFront (s1, “gamma”);
addBack (s1, “delta”);
printf(“This prints \”gamma beta alpha delta\” across four lines with a tab before each element, and preceded by \”squeue is:\” on its own line:\n”);
print (s1, ‘f’);
printf(“This prints \”delta alpha beta gamma\” across four lines with a tab before each element, and preceded by \”stack is:\” on its own line:\n”);
print (s1, ‘r’);
mergeFront(s1, ‘f’);
printf(“This prints \”gammabeta alpha delta\” across three lines with a tab before each element, and preceded by \”squeue is:\” on its own line:\n”);
print(s1, ‘f’);
mergeBack(s1, ‘r’);
printf(“This prints \”gammabeta deltaalpha\” across two lines with a tab before each element, and preceded by \”squeue is:\” on its own line:\n”);
print(s1, ‘f’);
leaveFront (s1);
printf(“This prints \”deltaalpha\” in one line with a tab before each element, and preceded by \”squeue is:\” on its own line:e\n”);
print(s1, ‘f’);
addFront(s1, “zeta”);
addFront(s1, “eta”);
leaveBack (s1);
void initSqueue (struct Squeue ** squeue);
initSqueue initializes the given squeue to an empty squeue. After calling initSqueue
on a given squeue , we should be able to add elements to that squeue by calling
addFront or addBack .
bool isEmpty (const struct Squeue * squeue);
isEmpty checks if the given squeue is empty. Returns true if it is empty and false if
not.
void addFront (struct Squeue squeue, char val);
addFront adds the given string (i.e., val) to the front of the given squeue. Make sure you
adjust all pointers of the squeue appropriately. You need to dynamically allocate memory
for the new string. You cannot assume any maximum size for the string.
printf(“This prints \”eta zeta\” across two lines with a tab before each element, and preceded by \”squeue is:\” on its own line:\n”);
print(s1, ‘f’);
printf(“This prints \”eta zeta\” in one line \n”);
printf(“%s %s\n”, peekFront(s1), peekBack(s1));
printf(“This nuke has no output, but is good form to call when done\n”);
nuke (s1);
printf(“This assertion should succeed\n”);
assert (isEmpty (s1));
printf(“Illegal direction should cause error message\n”);
print (s1, ‘k’);
addBack (s1, “alpha”);
addBack (s1, “beta”);
addBack (s1, “gamma”);
reverse(s1);
printf(“This prints \”gamma beta alpha\” across two lines with a tab before each element, and preceded by \”squeue is:\” on its own line:\n”);
print(s1, ‘f’);
destroySqueue(&s1); //we will always call this for any squeue we test with so make sure it is implemented correctly to free any allocated memory
return 0;
}
Detailed function descriptions
void addBack (struct Squeue squeue, char val);
addBack adds the given string (i.e., val) to the back of the given squeue. Make sure you
adjust all pointers of the squeue appropriately. You need to dynamically allocate memory
for the new string. You cannot assume any maximum size for the string.
void leaveFront (struct Squeue * squeue);
leaveFront deletes the first element from the front of the given squeue. Make sure you
adjust all pointers of the squeue appropriately and delete any unneeded struct instances.
The first line of the function should be: assert (!isEmpty(s)); to ensure that you don’t
try accessing elements from an empty squeue.
void leaveBack (struct Squeue *squeue);
leaveBack deletes the last element at the back of the given squeue. Make sure you adjust
all pointers appropriately and delete any unneeded struct instances. The first line of the function
should be: assert (!isEmpty(s)); to ensure that you don’t try accessing elements from
an empty squeue.
char peekFront (const struct Squeue squeue);
peekFront returns the value of the first element from the front of the squeue without
changing the squeue. The first line of the function should be: assert (!isEmpty(s)); to
ensure that you don’t try accessing elements from an empty squeue.
char peekBack (const struct Squeue squeue);
peekBack returns the value of the last element from the back of the squeue without
changing the squeue. The first line of the function should be: assert (!isEmpty(s)); to
ensure that you don’t try accessing elements from an empty squeue.
void print (const struct Squeue * squeue, char direction);
print takes a Squeue and a single char that represents the direction, f for forward
and r for reverse, and then prints the squeue in the desired direction. If the direction passed
in is not ‘f’ or ‘r’, then print the following message to stderr:
Error, illegal direction <entered direction> . Note that
<entered direction> must be replaced by the direction passed in as an arugment. For
example, if the function was called with direction b , the message printed to stderr will be
Error, illegal direction b . If an illegal direction is detected, just print that
message; do not try to print the contents of squeue , and do not exit the program or
make an assertion that could cause the program to abort. To output elements of the stack,
the function prints squeue is: on a line, followed by each element on its own line. Each
element is preceded with a tab. See example code.
void nuke (struct Squeue * squeue);
nuke takes a Squeue , deletes all of the internal Nodes, and sets the first and last pointers
of the Squeue instance to NULL .
void mergeFront(struct Squeue* squeue, char direction);
mergeFront takes a Squeue and a single char that represents the direction, f for
forward and r for reverse. It concatenates the two strings contained in the first two nodes of
the squeue in the desired direction, stores the concatenated string in the first node, and then
deletes the second node. See the provided main function example above to understand what
mergeFront does. Note that it is an error if you call mergeFront on a squeue with
less than 2 nodes. You should have an assert to check for this. If the direction passed in is
not ‘f’ or ‘r’, then print the following message to stderr:
Error, illegal direction <entered direction> . Note that
<entered direction> must be replaced by the direction passed in as an arugment. For
example, if the function was called with direction b , the message printed to stderr will be
Error, illegal direction b . If an illegal direction is detected, just print that
message; do not try to do the merge, and do not exit the program or make an assertion
that could cause the program to abort.
void mergeBack(struct Squeue* squeue, char direction);
mergeBack takes a Squeue and a single char that represents the direction, f for
forward and r for reverse. It concatenates the two strings contained in the last two nodes of
the squeue in the desired direction, stores the concatenated string in the node before last, and
then deletes the last node. See the provided main function example above to understand what
mergeBack does. Note that it is an error if you call mergeBack on a squeue with less
than 2 nodes. You should have an assert to check for this. If the direction passed in is not ‘f’
or ‘r’, then print the following message to stderr:
Error, illegal direction <entered direction> . Note that
<entered direction> must be replaced by the direction passed in as an arugment. For
example, if the function was called with direction b , the message printed to stderr will be
Error, illegal direction b . If an illegal direction is detected, just print that
message; do not try to do the merge, and do not exit the program or make an assertion
that could cause the program to abort.
void reverse(Squeue* squeue);
reverses the elements in the given squeue. If the squeue was a->b->c->d , where first
points to a and last points to d , calling reverse would change the squeue contents to
d->c->b->a , and make first point to d and last point to a .
void destroySqueue(Squeue **squeue);
destroySqueue safely deletes all members of the given squeue as well as any memory
allocated for squeue. After calling destroySqueue on a given squeue , that squeue
would point to NULL .
In the Part1 folder on GitHub, you must submit the following files:
squeue.h — already there. Do not change the prototypes we provide; you may
add prototypes for your helper functions though.
squeue.c . This file contains the definitions of all the functions declared in
squeue.h . This is the file that contains all your implementation code.
squeue_client.c . This file must contain ONLY the main function and

include <stdio.h> , #include <assert.h> ,

include <stdlib.h> , and #include “squeue.h” . We have provided you

a sample file in your repository for testing purposes. When we mark your program, we
will be creating our own main function to test your program. Therefore, we will replace
your squeue_client.c so if you have anything other than main in there, we will
no longer have access to that functionality. NOTE: the local test scripts and GitHub
Actions check the output of the code we provided in squeue_client.c . Do
not change this file, or otherwise the expected output will not match the
program’s output and the tests will fail. To create your own tests, you can add
your own C file with your own main function (e.g. bucketstack_test.c and create
a separate test target in your Makefile). You can watch this YouTube video to
understand how to do that.
Makefile that correctly compiles and links the code in the above three files into an
executable called squeue . Your Makefile must have the clean target.
If your Makefile does not compile the above files into an executable called squeue
Deliverables of Part I
Grading of Part I
with no errors or warnings, you will get a 0 for this part
1 mark: clean target works correctly.
40 marks: Correct functionality of all expected functions.
9 marks: no memory leaks. You will not get these 9 marks if you got 0 for the correct
functionality part since, obviously, if you implement nothing, you will have no
memory leaks :-)
If global variables are used, 10 marks will be taken off your total grade
Linked lists have many advantages over, say, statically allocated approaches. For example, if we
were limited to only statically allocated storage, then one way to implement a stack would be by
using an array to hold the elements, and keeping track of the top element by keeping an integer
index to the top element, as depicted in Figure 1. The obvious disadvantage of this approach is
that there is an upper bound on how many elements the stack can hold at the same time (here,
the bound is 100). Additionally, you must allocate the whole array at once; if you were using only
a small percentage of the available elements most of the time, then you could be wasting a lot of
space depending on how big the array was. Another problem is that you will need to know the
maximum of a string. The advantages of this approach over a linked list are simplicity and
speed: linked lists are easy to get wrong, and with an array you have direct access to all
elements (that’s not much of an advantage for a stack, but it would be if the Abstract Data Type
(ADT) required immediate access to any given element).
Compare this to using a linked list approach shown in class. Each element is stored in its own
node, so there is a storage overhead of one pointer (typically, about four bytes) per element.
Also, while creating and deleting new nodes are constant time operations in principle, if real-time
Part II (50 marks)
performance is a big concern, they can be relatively expensive operations compared to just
accessing an array element.
In this assignment, you will investigate a hybrid approach, which we are going to call a Bucket
Stack. An example is shown in Figure 2.
Basically, we are going to use a linked list approach, but instead of just one element, each node
will contain an array of bucketSize elements, for some constant bucketSize . This
means that the stack will be unbounded, but that there will be a storage overhead of only one
pointer per bucketSize elements (instead of one per element). Of course, this might mean
some wasted space, but that will amount to at most bucketSize – 1 elements at any given
moment. The second diagram shows an example of a Bucket Stack with seven elements and a
bucketSize of 5. The order of insertion was: alpha , beta , gamma , delta ,
epsilon , zeta , eta . Note how topElt in this representation stores the index of the
current element at the top of the stack. For simplicity, the diagram shows each string as a direct
element in the array. Technically, each element of the array is a char * and the memory for
the string will be dynamically allocated so we can store any size string we want.
Note that because we want to be flexible about the bucket size, you will have to use a
dynamically allocated array as discussed in class. You will also use two different kinds of structs,
one called Stack for the stack itself (the green box) and one called NodeBucket for the
various nodes (the yellow boxes) that store the elements (or more precisely, store pointers to the
dynamic arrays that store the elements).
To implement this, you will use the following struct definitions. They are also provided in the
header file you will find in the Part2 folder in your GitHub repo.
struct NodeBucket {
char** val;
struct NodeBucket* next;
};
typedef struct {
struct NodeBucket* firstBucket;
int topElt;
int bucketSize;
} Stack;
The prototypes for the functions you must implement are given below; thes are included in the
provided header file.
void initStack (int bucketSize, Stack **stack);
bool isEmpty (const Stack *stack);
void push (char val, Stack stack);
void pop(Stack *stack);
int size (const Stack *stack);
char top (const Stack stack);
void swap (Stack *stack);
void print (const Stack *stack);
void clear(Stack *stack);
void destroyStack(Stack **stack);
Any given stack has a fixed bucketSize (a positive integer), which is set when you initialize
it via initStack ; that is, any NodeBucket belonging to this stack will have the same
number of elements, bucketSize , for a given stack. However, you should note that two
different stacks can have different bucketSizes .
Here is an example of a main function that uses the above bucketstack:
int main (int argc, char* argv[]) {
Stack *s = NULL;
initStack (3, &s);
push(“alpha”, s);
printf(“This prints \”alpha\”:\n”);
printf(“%s\n”, top(s));
push(“beta”, s);
printf(“This prints \”beta\”:\n”);
printf(“%s\n”, top(s));
push (“gamma”, s);
printf(“This prints \”gamma\”:\n”);
printf(“%s\n”, top(s));
push (“delta”, s);
printf(“This prints \”delta\”:\n”);
printf(“%s\n”, top(s));
printf(“This will print the whole stack with a tab before each element:\”delta gamma beta alpha\” across 4 lines, preceded by \”stack is:\” on a line on its own\n”);
print(s);
clear(s);
printf(“This will print an empty stack so just \”stack is:\”\n”);
print(s);
void initStack (int bucketSize, struct Stack **stack);
initStack creates an empty stack with the given bucketSize. Remember that the
firstBucket of an empty BucketStack is NULL .
bool isEmpty (const struct Stack *stack);
isEmpty returns true if the stack is empty, and false otherwise.
push (“alice”, s);
printf(“This will print a stack that only contains \”alice\”\n”);
print(s);
pop (s);
printf(“This will print an empty stack so just \”stack is:\”\n”);
print(s);
push (“bob”, s);
push (“bob”, s);
printf(“This will print the whole stack with a tab before each element:\”bob bob\” across 2 lines, preceded by \”stack is:\” on a line on its own\n”);
;
print(s);
push(“mike”, s);
printf(“This will print the whole stack with a tab before each element:\”mike bob bob\” across 3 lines, preceded by \”stack is:\” on a line on its own\n”);
;
print(s);
swap(s);
printf(“This will print the whole stack after swapping first two with a tab before each element:\”bob mike bob\” across 3 lines, preceded by \”stack is:\” on a line on its own\n”);
;
print(s);
clear(s);
printf(“This will print an empty stack so just \”stack is:\”\n”);
print(s);
destroyStack(&s); //we will always call this for any stack we test with so make sure it is implemented correctly to free any allocated memory
return 0
}
Detailed Function Descriptions
void push (char val, struct Stack stack);
push pushes the provided string on to the given stack. You need to dynamically allocate
memory for the new string. You cannot assume any maximum size for the string. Note that
push needs to check if the current firstNodeBucket is full; if so, another
NodeBucket needs to be allocated and linked in place.
void pop(struct Stack *stack);
pop pops the top element from the given stack. Note that the value of the popped string is not
returned. Also, note that pop needs to check if the element being removed is the last one in
the current first NodeBucket ; if so, that NodeBucket should be deleted (and so should its
dynamic array), and the appropriate links should be adjusted. At the beginning of the pop
function, assert that the stack is not empty.
int size (const struct Stack *stack);
size returns the current number of elements in the Stack; it would return 7 for the example in
the diagram.
char top (const struct Stack stack);
top returns the top string on the stack WITHOUT removing it from the stack. At the beginning
of the top function, assert that the stack is not empty.
void swap (struct Stack *stack);
swap swaps the top two elements. In the example shown in the diagram, zeta and eta
would change positions. Hint: there is one tricky case you have to consider. Note that it’s an
error if swap is called when there are fewer than two elements; you should use assert to
check this.
void print (const struct Stack *stack);
print prints stack is: on one line followed by the contents of the stack from top to
bottom, where each string is displayed on a line preceded by a tab character. In the example
above, invoking print on the current stack would display:
stack is:
eta
zeta
epsilon
delta
gamma
beta
alpha
void clear(struct Stack *stack);
clear deletes all contents of the stack and adjusts firstBucket , bucketSize , and
topElt accordingly.
void destroyStack(Stack **stack);
destroyStack completely destroys the stack. This means it deletes all contents of the
stack, as well as the memory allocated for the Stack struct. Calling destroyStack on any
stack (whether it has elements or not) should always clean up any memory. After caling the
destroyStack function, the stack that was passed in would point to NULL .
General Hint: When you test your program on your own, try different values of bucketSize .
Two good corner case examples are 1 (effectively giving you a linked list stack) and, say, 100
(effectively giving you an array stack). Try some other values too. Also, test different cases:
when you have exactly bucketSize elements, when you have one less than
bucketSize elements, when you have one more than bucketSize elements (to see if
you correctly create a new NodeBucket ). The idea is to make sure your program works
correctly at boundary values where programming mistakes typically happen. Also, think of
testing “corner cases” or error-handling behavior. For example, reversing popping an empty
stack or reversing a stack with 0 or 1 elements.
In the Part2 folder on GitHub, you must submit the following files:
bucketstack.h — already there. Do not change the prototypes we provide;
you may add helper functions though.
bucketstack.c . This file contains the definitions of all the functions declared in
bucketstack.h . This file contains all your implementation for this part.
bucketstack_client.c . This file must contain ONLY a main function and

include <stdio.h> , #include <assert.h> ,

Deliverables of Part II

include <stdlib.h> , and #include “bucketstack.h” . We have

provided you a sample file in your repository for testing purposes. When we mark your
program, we will be creating our own main function to test your program. Therefore,
we will replace your bucketstack_client.c file so if you have anything other
than main in there, we will no longer have access to that functionality. NOTE: the local
test scripts and GitHub actions check the output of the code we provided. Do
not change this file, or otherwise the expected output will not match the
program’s output and the tests will fail. To create your own tests, you can add
your own C file with your own main function (e.g. bucketstack_test.c and
create a separate test target test in your Makefile. See this YouTube video for
an explanation of how you can do that).
Makefile that correctly compiles and links all the code in the above 3 files into an
executable called bucketstack . Your Makefile must have the clean target.
If your Makefile does does not compile the above files into an executable called
bucketstack with no errors or warnings, you will get a 0 for this