关键词 > CS32
CS 32, WINTER 2015, PRACTICE MIDTERM II.
发布时间：2022-02-23
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS 32, WINTER 2015, PRACTICE MIDTERM II.
|
Problem #1: Stack is a LIFO (Last In First Out) container while Queue is a FIFO (First In First Out) container. If you were given 2 sequence of numbers in which the first sequence of numbers are the numbers entering a mystery container, and the second sequence of numbers are the numbers leaving a container, are you able to determine whether that mystery container is a Stack, Queue, Might Be Either One, or Neither? For example, if you were given these two sequences: 1 2 3 // 1 entered the container first, then 2, and finally 3. 3 2 1 // 3 left the container first, then 2, and finally 1. then that mystery container must be a Stack. |
|
Implement the functions on the next page (which are called by the main routine on the page after that) so that this input:
etc. 1 2 3 4 5 7 1 2 3 4 3 2 1 1 2 3 4 3 2 1 4 1 3 4 2 1 4 2 3 produces this output: This is a Stack! This is a Queue! Either a Stack or a Queue! Neither a Stack nor a Queue! |
#include
#include
using
namespace
std;
bool
isQueue(const vector
{
}
bool
isStack(const vector
{
}
int
main()
{
int
numberOfValues;
while(
cin
>>
numberOfValues
)
//
leave
loop
if
there
is
no
next
test
case {
vector
v1,
v2;
for
(int
i
=
0;
i
<
numberOfValues;
i++)
{
int
value;
cin
>>
value;
v1.push_back(value);
}
for
(int
i
=
0;
i
<
numberOfValues;
i++)
{
int
value;
cin
>>
value;
v2.push_back(value);
}
bool
s
=
isStack(v1,
v2);
bool
q
=
isQueue(v1,
v2);
if
(s)
{
if
(q)
cout
<<
"Either
a
Stack
or
a
Queue!"
<<
endl;
else
cout
<<
"This
is
a
Stack!"
<<
endl;
}
else
{
if
(q)
cout
<<
"This
is
a
Queue!"
<<
endl;
else
cout
<<
"Neither
a
Stack
nor
a
Queue!"
<<
endl;
}
}
|
Problem #2: Below is an implementation of a singly linked list with no dummy node. |
#include
using
namespace
std;
class
LinkedList
{
public:
LinkedList():
head(nullptr)
{
}
~LinkedList(); void
append(int
value); void
print()
const; void
printReverse()
const; void
reverse();
int
sum()
const;
private:
struct
Node
//
append
value
to
the
list //
show
the
items
in
the
list // show
the
items
in
the
list
in
the
opposite
order //
change
list
so
items
are
in
the
opposite
order //
return
the
sum
of
the
values
in
the
list
{
int
num;
Node*
next;
};
Node*
head;
// this
is
the
only
data
member;
do
not
add
any
others
void
printReverseHelper(const
Node*
p)
const;
Node*
reverseHelper(Node*
current,
Node*
previous);
Int
sumHelper(const
Node*
p)
const;
void
removeNodes(Node*
p);
};
int
main()
{
LinkedList
list;
cout
<<
list.sum()
<<
endl; //
writes
0
int
values[4]
=
{
30,
10,
40,
20
};
for
(int
i
=
1;
i
<=
4;
i++)
list.addToList(values[i]);
list.print();
cout
<<
list.sum()
<<
endl; list.printReverse();
list.print();
list.reverse();
list.print();
}
|
// |
30 100
20 |
//
this
changes
the
list
//
writes
20
40
10
30
void
LinkedList::append(int
value)
{
Node*
current
=
new
Node;
current->num
=
value;
current->next
=
nullptr;
if
(head
==
nullptr)
head
=
current;
else
{
Node*
ptr
=
head;
while
(ptr->next
!=
nullptr)
ptr
=
ptr->next;
ptr->next
=
current;
}
}
void
LinkedList::print()
const
{
for
(const
Node*
ptr
