作业Data structure | 代写assignment | c++代写 | c代写 | 数据结构代做 | 代做lab – Dynamic memory allocation

Dynamic memory allocation

作业Data structure | 代写assignment | 代做lab – 这是利用Data structure进行训练的代写, 对Data structure的流程进行训练解析, 涉及了Data structure等代写方面, 这个项目是lab代写的代写题目

数据结构代写 代写数据结构 Data structure代写 算法代写

CMPUT 201 - Winter 2019
 assignment 3
Pointers
Dynamic memory allocation
Abstract Data Types (Stacks and linked lists)
Program organization
Header files and Makefiles
Adhering to provided code stubs
Program testing
Asserts

Concepts Covered

GitHub Instructions

you were doing is of great help to you if you are suspected of plagiarism. Make sure to push your code at
the end of your current "working session". Don't push each single commit to GitHub as this will trigger a
TravisCI build, overload the build server, and delay the results of the build for the whole class. A good
strategy is to commit and test locally and then push to GitHub once you have completed the current
functionality you are working on. Another strategy is to push your commits to GitHub every hour or two:
just in case anything happens to your computer, you don't want to lose your local changes.
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, dont 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.
Yo u n e e d only 1 ReadMe file in the root folder of your repository. 

Credits: This assignment has been adapted from one of Mike Godfrey’s assignments.

Important Information

Part I (50 marks)

Were going to implement a Data structure called Squeue , because its 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 next four operations operate on the front of the list, while the next four operate on the back. 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.

Were 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 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 befor
e each element, and preceded by \"stack is:\" on its own line:\n");
print (s1, 'f');
printf("This prints \"delta alpha beta gamma\" across four lines with a tab befor
e 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 befor
e each element, and preceded by \"stack is:\" on its own line:\n");
print(s1, 'f');
mergeBack(s1, 'r');
printf("This prints \"gammabeta deltaalpha\" across two lines with a tab before e
ach element, and preceded by \"stack is:\" on its own line:\n");
print(s1, 'f');
leaveFront (s1);
printf("This prints \"alphadelta\" in one line with a tab before each element, an
d preceded by \"stack is:\" on its own line:e\n");
print(s1, 'f');
addFront(s1, "zeta");
addFront(s1, "eta");
leaveBack (s1);
printf("This prints \"eta zeta\" across two lines with a tab before each element,
and preceded by \"stack 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 \"stack is:\" on its own line:\n");
print(s1, 'f');
destroySqueue(&s1); //we will always call this for any squeue we test with so mak
e sure it is implemented correctly to free any allocated memory
return 0;
}
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 appropriately.

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 appropriately.

void leaveFront (struct Squeue * squeue);

leaveFront deletes the first element from the front of the given squeue. Make sure you adjust all pointers appropriately and delete unneeded struct instances. Hint: 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

Detailed function descriptions

appropriately and delete unneeded struct instances. Hint: 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. Hint: 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. Hint: 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 . If an illegal direction is detected, just print that message; do not try to print the contents of the 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 stack 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 . 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 . 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 in 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 helper
functions though.
squeue.c. This file contains the definitions of all the functions declared in squeue.h.
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
TravisCI 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 similar to what

Deliverables of Part I

you did for  lab 7)
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 work as expected (e.g., does not compile the above files into an
executable called squeue , has errors or warnings, or its clean target does not work correctly),
you will get a 0 for this part
40 marks: Correct functionality of all expected functions.
10 marks: no memory leaks. You will not get these 10marks 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. 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 (thats 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).

Grading of Part I

Part II (50 marks)

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 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 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, 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 ga mma 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);

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 befor e each element:”bob mike bob” across 3 lines, preceded by “stack is:” on a line o n 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 s
ure it is implemented correctly to free any allocated memory
return 0
}
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.
void push (char* val, struct Stack *stack);
push pushes the provided string on to the given stack. 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. Hint: 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. Hint: at the beginning of the
top function, assert that the stack is not empty.
void swap (struct Stack *stack);

Detailed Function Descriptions

swap swaps the top two elements. In the example shown in the diagram, zeta and eta would change positions. In general, there is one tricky case you have to consider. Note that its 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.

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

Deliverables of Part II

bucketstack.h.
bucketstack_client.c. This file must contain ONLY a main function and
#include <stdio.h> , #include <assert.h> , #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 TravisCI 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 in your Makefile similar to what you did
for Lab 7)
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 not work as expected (e.g., does not compile the above files into an
executable called bucketstack , has errors or warnings, or its clean target does not work
correctly), you will get a 0 for this part
40 marks: Correct functionality of all expected functions.
10 marks: no memory leaks. You will not get these 10marks 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