首页 > > 详细

辅导data structure、讲解c/c++编程设计、c/c++讲解、辅导leaveFront 辅导Python编程|辅导R语言程序

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 descriptionsappropriately 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 , #include , #include , 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 Iyou 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 Descriptionsswap 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 IIbucketstack.h .
bucketstack_client.c . This file must contain ONLY a main function and
#include , #include , #include , 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

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!