代写CMPUT 201编程、代做C/C++

代写CMPUT 201编程、代做C/C++

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/g/UJKMgYrf. READ BELOW BEFORE CLICKING ON THIS

LINK

At thte end, you will have a repository with the following name:

https://gihub.com/cmput201-w21/assignment3-asgmt3_teamNN .

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 part

1 mark: make clean works as expected

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

Grading of Part II

 

请加QQ：99515681 或邮箱：99515681@qq.com   WX：codehelp