代写data structure、代做c/c++编程设计、c/c++代做、代写leaveFront

日期：2019-04-09 11:33

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

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 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 \"deltaalpha\" 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 <entered 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 <entered 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 <entered 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 (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).

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 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:

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