Linux C/C++ 作业辅导

C++ Program Design

Raven Elevators Inc. (REI), a manufacturer of elevators, has hired you to build them a simulator for their line of elevator control systems. You happily accept the task, eager to impress your new employer with your development skills. REI asked you to implement it in Qt C++, but before doing the implementation REI requested that you first deliver use cases, design documentation, traceability matrix, and C++ class interfaces.
Learning objectives:
 Designing and expressing your design in UML
 Verifying consistency between use cases and design
 Building a requirements traceability matrix
 Designing for variability in elevator allocation strategy
 Use cases (can borrow from A1 & grading feedback)
 Design documentation – structure and behavior:
o UML Class diagram
o Sequence diagrams for these scenarios: 1 Basic use cases and 5 safety features
o Activity or state diagram (where relevant)
o Textual explanation of your design decisions including use of design patterns, if any.  C++ header files (interfaces and significant variables)  Traceability matrix
Your design should include passenger and sensor actors driving the elevator controller responses that are displayed through a simple GUI.
Your design should accommodate for variability in elevator allocation strategy (handle 2 or more allocation strategies).

Elevator system specification (same as Assignment 1)
<Paragraph 1> A building is serviced by M elevators (also called cars). On each of the N floors is a pair of buttons marked “up” and “down. When a button is pressed it illuminates, and remains illuminated, until an elevator arrives to transport the customers who, at this floor, have requested an elevator going in a certain direction. When the elevator arrives, it rings a bell, opens its doors (the elevator and floor doors) for a fixed time (10 seconds) allowing people to exit or board, rings the bell again, closes its doors and proceeds to another floor. Once on-board passengers select one or more destination floors using a panel of buttons; there is one button for every floor. The elevator has a display which shows passengers the current floor of the elevator. There is also a pair of buttons on the elevator control panel marked “open door” and “close door”. These buttons can be used by a passenger to override the default timing of the doors. The door will remain open beyond its default period if the “open door” button is held depressed; the doors can be closed prematurely by pressing the “door close” button. Inside the elevator there is also a help button linked to building safety service.
<Paragraph 2> Each elevator has a sensor that notifies it when it arrives at a floor. The elevator control system should ensure that the group of elevators services all (floor and on-board) requests expeditiously.
<Paragraph 3> Each elevator has a display and an audio system. The display shows the current floor number and warning messages that are synced with audio warnings.
Safety features:
<Paragraph 4> Help: The control system receives a “Help” alarm signal from an elevator indicating that the “Help” button has been pressed. In that case, the passenger is connected to building safety service through a voice connection. If there is no response from building safety within 5 seconds or if there is no response from a passenger a 911 emergency call is placed.
<Paragraph 5> Door obstacles: If the light sensor is interrupted when the door is closing, the control system stops the door from closing and opens it. If this occurs repeatedly over a short period of time, a warning is sounded over the audio system and a text message is displayed.
<Paragraph 6> Fire: The control system receives a “Fire” alarm signal from the building and commands all elevators to move to a safe floor. Similarly, a “Fire” alarm signal from the elevator itself will cause that elevator to go to a safe floor. In both cases an audio and text message are presented to passengers informing them of an emergency and asking them to disembark once the safe floor is reached.
<Paragraph 7> Overload: The control system receives an “Overload” alarm signal from an elevator if the sensors indicate that the passenger or cargo load exceeds the carrying capacity. In that case, the elevator does not move and an audio and a text messages are presented to passengers asking for the load to be reduced before attempting to move again.
<Paragraph 8 > Power out: The control system receives a “Power Out” alarm signal. In that case, an audio and a text messages are presented to passengers informing them of the power outage. Each elevator is then moved to a safe floor and passengers are asked to disembark via audio and text messages. The battery backup power is sufficient to do all of this.

Core Scanner

The goal of this project is to build a scanner for a version of the Core language, a pretend
language we will be discussing in class.
For this project you are given the following:
ˆ \3341 Project 1.pdf” – This handout. Make sure you read it completely and handle all
requirements in your implementation. You are encouraged to post any questions on
ˆ \main.c”, \core.h”, \scanner.h”, \scanner.c” – I have outlines the project in this les,
and give you some of the code you will need. Make no changes to to \core.h” le.
You can make changes to \main.c” as long as those changes do not change break my script.
ˆ You may create additional les to contain any additional classes or methods you want
to create.
ˆ \” – This is a script I wrote to help you test your project. It is very similar
to the script that will be used to grade your project, so if your project works correctly
with this script you are probably doing well. The only guarantee I give is that this
script will work on stdlinux.
ˆ Folder \Correct” – This contains some correct inputs and their expected outputs. The
\” script will test your code against these examples.
ˆ Folder \Error” – This contains some inputs that should generate error messages. The
\” script will test your code against these examples.
The following are some constraints on your implementation:
ˆ Do not use scanner generators (e.g. lex, ex, jlex, j ex, ect) or parser generators
(e.g. yacc, CUP, ect)
ˆ Use only the standard libraries of C. This is the reference I like to use:
Your submission should compile and run in the standard linux environment the CSE
department provides (stdlinux). I will leave it up to you to decide what IDE you will use or
if you will develope your code locally or remotely, but as a nal step before submitting your
code please make sure it works on stdlinux. Use the subscribe command – make sure
you are subscribed to GCC-10.1.0. The graders will not spend any time xing your
code – if it does not compile on stdlinux, your project will not be graded and you
will get a 0.

Your Scanner
You are responsible for writing a scanner, which will take as input a text le and output a
stream of \tokens” from the core.h enumeration. You scanner must implement the following
ˆ scanner open and scanner close: These functions open the le, nd the rst token, and
release memory when we are done scanning.
ˆ currentToken: This function should return the token the scanner is currently on, with-
out consuming that token.
ˆ nextToken: This function should advance the scanner to the next token in the stream
(the next token becomes the current token).
ˆ getId: If the current token is ID, then this function should return the string value of
the identi er. If the current token is not ID, behavior is unde ned.
ˆ getConst: If the current token is CONST, then this function should return the value
of the constant. If the current token is not CONST, behavior is unde ned.
All of these functions will be necessary for the parser you will write in the second project.
You are free to create additional functions.
To make things easier for you, you may assume no token is made of more than 20
characters. Also, I suggest using calloc to allocate memory, instead of malloc.
The input to the scanner will come from a single ASCII text le. The name of this le will
be given as a command line argument to the main function.
The scanner should process the sequence of ASCII characters in this le and should
produce the appropriate sequence of tokens. There are two options for how your scanner can
(1) the scanner can read the entire character stream from the le, tokenize it, stores all the
tokens in some list or array and calls to currentToken and nextToken simply walk through
the list
(2) the scanner reads from the le only enough characters to construct the rst token, and
then later reads from the le on demand as the currentToken or nextToken functions are
Real world scanners typically work as described in (2). In your implementation, you can
implement (1) or (2), whichever you prefer.
Once your scanner has scanned the entire le, it should return the EOS token (End Of

Invalid Input
Your scanner should recognize and reject invalid input with a meaningful error message. The
scanner should make sure that the input stream of characters represents a valid sequence of
tokens. For example, characters such as ` ‘ and ‘%’ are not allowed in the input stream. If
your scanner encounters a problem, it should print a meaningful error message to standard
out (please use the format “ERROR: Something meaningful here”) and return the ERROR
token so the main program halts.
The Language
The Core language consists of 4 kinds of strings, which you will need to tokenize:
ˆ Keywords:
and begin do else end if in integer
is new not or out procedure record then while
ˆ Identi ers:
Begins with a letter (uppercase or lowercase) followed by zero or more letters/digits.
Refer to this regular expression once we cover regular expressions:
(aj : : : jzjAj : : : jZ)(aj : : : jzjAj : : : jZj0j1j : : : j9)*
ˆ Constants:
Integers from 0 to 1009 (inclusive)
ˆ Symbols:
+ – * / := = < : ; . , ( ) [ ]
Your scanner walk through the input character stream, recognize strings from the lan-
guage, and return the appropriate token from the enumeration in \” or \”.
If there is any situation in which it is unclear to you which token should be returned, please
ask for clari cation on Piazza.
Write your scanner with these rules in mind:
1. The language is case sensitive, and the keywords take precedence over the identi ers.
For example, \begin” should produce the token BEGIN (not ID), but \bEgIn” should
produce the token ID.
2. Strings in the language may or may not be separated by whitespaces. For example the
character stream may contain the string \x=10″ or the string \x = 10″, and both of
these should generate the token sequence ID EQUAL CONST.
3. Always take the greedy approach. For example, the string \whilewhile” should produce
an ID token instead of two WHILE tokens, string “123” should produce a single CONST
token, and string \:=” should produce ASSIGN.

4. Keyword/identi er strings end with either whitespace or a non-digit/letter character.
For example:
(a) the string \while (” and the string \while(” should both result in the WHILE and
LPAREN tokens.
(b) the string \while 12″ should result in the WHILE and CONST tokens, but the
string \while12″ should result in the ID token.
5. Constant strings end with any non-digit character. For example:
(a) the string \120while” or \120 while” should result in the CONST and WHILE
6. Symbols may or may not be separated from other strings by whitespace. For example:
(a) String \++while<= =12=” should result in the token sequence ADD ADD
Let me know if you think of any situations not covered here.
Testing Your Project
I have provided some test cases. For each correct test case there are two les (for example
4.code and 4.expected). On stdlinux you can redirect the output of the main program to a
le, then use the di command to see is there is any di erence between your output and the
expected output. For an example of how to do this you can take a look at the script le
The test cases are weak. You should do additional testing with your own test cases. Feel
free to create and post additional test cases on piazza.
Project Submission
On or before 11:59 pm January 27th, you should submit to the Carmen dropbox for Project
1 a single zip le containing the following:
ˆ All your .java or .py les.
ˆ An ASCII text le named README.txt that contains:
{ Your name on top
{ The names of all les you are submitting and a brief description stating what each
le contains
{ Any special features or comments on your project
{ Any known bugs in your scanner  If the time stamp on your submission is 12:00 am on January 28th or later, you will
receive a 10% reduction per day, for up to three days. If your submission is more than 3
days late, it will not be accepted and you will receive zero points for this project. If you
resubmit your project, only the latest submission will be considered.
The project is worth 100 points. Correct functioning of the scanner is worth 65 points. The
handling of errors is worth 20 points. The implementation style and documentation are
worth 15 points.

Improving your Classes

Exercise 1: Extra Constructors

In this exercise we are going to add extra constructors. But first we do a little experiment.

In the Point class constructor and destructor, add some code that displays some text.

In the main program, make sure you use the Distance() function to calculate the distance

between two points. Run the program and count how many times the constructor and

destructor are called. Are they the same?

Now add a copy constructor to the Point class that also displays some text. Also add a

constructor that accepts x- and y-coordinates so you can create a point with the right values

without using the set functions. Use this constructor to create the point from the user input.

Run the program again and count the number of times the constructors and destructor are

called. Is the copy constructor called and is the number of constructor calls now the same as

the number of destructor calls?

We can derive two things from these results:

  1. When calling the Distance() function, the input point is copied (call by value).
  2. You will get the copy constructor ‘for free’ when you do not create one yourself.

Exercise 2: Pass by Reference

In the previous exercise, you saw that the point passed to the Distance() method was copied.

Since creating a copy is unnecessary in this case, change this function so that it passes the

input point “by reference” so that no copy is made. Pass it as “const reference” to make it

impossible to change the input point from within the Distance() function.

Run the program again. It should call the copy constructor fewer times than before.

Also test if you can change the input point in the Distance() function. This should result in a

compiler error.

Exercise 3: Function Overloading

Previously you saw that there could be more than one constructor as long as the input

arguments are different. You can do the same for normal member functions. Thus you can

rename the DistanceOrigin() function to Distance(). Also you can rename

the SetX() andGetX() functions to just X(). The same is true for the setter and getter of the y


Exercise 4: Const Functions

In the test program create a const point and try to set the x-coordinate:

const Point cp(1.5, 3.9);


Compile the program. Did you get a compiler error? It should give a compiler error because

you try to change a const object.Now replace the line that changes the x-coordinate to code that reads the x-coordinate:


Compile the program again. You will see that is still gives a compiler error even while

retrieving the x-coordinate does not change the point object. This is because the compiler

does not know that the function does not change anything. So we need to mark the x

coordinate getter as const by making it a const function. Do this also for the y-coordinate

getter and the Distance() and ToString() functions because these don’t change the point

object as well.

Recompile the application. It should now work.

Exercise 5: Line Class

In the final exercise for this chapter we are going to create a Line class. The Line class has a

start- and an end-point. So the Line class should have two Point objects as data members.

This mechanism is called “composition”. See also Figure 3.

Give the Line class the following functionality:

  • Default constructor (set the points to 0, 0).
  • Constructor with a start- and end-point.
  • Copy constructor.
  • Destructor.
  • Overloaded getters for the start- and end-point.
  • Overloaded setters for the start- and end-point.
  • A ToString() function that returns a description of the line.
  • A Length() function that returns the length of the line. Note that you can use the

distance function on the embeddedPoint objects to calculate the length. This

mechanism is called “delegation”.

Use const arguments, const functions and pass objects by reference where applicable.


Exercise 5: Line Class

In the final exercise for this chapter we are going to create a Line class. The Line class has a

start- and an end-point. So the Line class should have two Point objects as data members.

This mechanism is called “composition”. See also Figure 3.

Give the Line class the following functionality:

  • Default constructor (set the points to 0, 0).
  • Constructor with a start- and end-point.
  • Copy constructor.
  • Destructor.
  • Overloaded getters for the start- and end-point.
  • Overloaded setters for the start- and end-point.
  • A ToString() function that returns a description of the line.
  • A Length() function that returns the length of the line. Note that you can use the

distance function on the embeddedPoint objects to calculate the length. This

mechanism is called “delegation”.

Use const arguments, const functions and pass objects by reference where applicable.

The Class Concept

Exercise 1: Point Class

Now you must use C++ syntax!!

In this exercise we start creating a Point class with and x- and y-coordinates. This class will

be extended in further exercises.

In Visual Studio, create an empty “Win32 Console Application”. If you don’t check the

“Empty Project” checkbox in the wizard, Visual Studio will generate code for you and will

set the “use pre-compiled headers” on… Pre-compiled headers, which are a Visual Studio

specific option, require special attention in your code and file settings so that is why an empty

project is more appropriate.

First add a header file for the Point class with private members for the x- and y-coordinates.

Do not forget to add the #ifndef/#define/#endif statements to avoid multiple inclusion.

Also make sure you make to following public functionality (see also Figure 1):

  • Default constructor.
  • Destructor.
  • Getter functions for the x- and y-coordinates (GetX() and GetY() functions).
  • Settter functions for the x- and y-coordinates (SetX() and SetY() functions).
  • A ToString() that returns a string description of the point. Use the std::string class as

return type.









Figure 1: Point Class

Next create the source file that implements the Point class defined in the header file. The

source file must include the header file.

Making the string in the ToString() function, requires conversion of the double coordinates to

a string. Easiest is to use a std::stringstream object and the standard stream operators (as

with iostream) to create the string. This requires the “sstream” header file. Use

the str() function to retrieve the string from the string buffer. The output can be like:

“Point(1.5, 3.9)”

Finally create a test program (separate source file with a main() function) for the Point class.

It should do the following things:

  • Include the point header file. • Ask the user for the x- and y-coordinates using the std::cin object (needs the

“iostream” header file).

  • Then create a Point object using the default constructor.
  • Set the coordinates entered by the user using the setter functions.
  • Print the description of the point returned by the ToString() function.
  • Print the point coordinates using the get functions.

Exercise 2: Distance Functions

In this exercise we are going to add distance functions to the Point class. The distance

functions have the following signature:

double DistanceOrigin(); // Calculate the distance to the origin (0, 0).

double Distance(Point p); // Calculate the distance between two points.

Add the definitions to the header file and implement the functions in the source file. Use

the std::sqrt() function from the “cmath” header file to implement the Pythagoras algorithm.

Extend the main program to print the distance between the origin and another point and test











Figure 2: Point Class with Distance() functions

Input and Output

Exercise 1

Create a C-program that reads the characters from the keyboard and shows them on

screen (the inputted characters should only be displayed when the user hits ‘enter’, line

by line).

When ^A is entered, the program must end properly. Then the following message will

appear: “CTRL + A is a correct ending.”

Tip: getchar() reads and putchar() writes the type int. The value of ^A is 1.

Exercise 2

Alter the last program of exercise 1 in such a way that the output doesn’t go to the screen

but is written to a file. The file to write to must be specified by the user.


Write a C-program that prints the contents of a struct called Article. An Article has the

following characteristics:

  • Article number
  • Quantity
  • Description (20 characters)

The test program must create an Article of which the contents are assigned at

initialization level.

Printing the Article is done with a Print() function. This function gets the address of the

structure as a parameter.

Tip: Suppose that p is the pointer to the structure. It will allow the fields to be printed

by (*p).fieldname or p->fieldname.

Pointers and Arrays

Exercise 1

Try to create a function Swap(). This function must exchange the value of two variables.

For example: if i=123 and j=456, then i=456 and j=123 after the Swap() function has

been called. The variables i and j are declared, initialised and printed in the

function main(). This problem can be solved by using pointers as arguments for

the Swap()function.

Exercise 2

The following program reads a string with a 30 character maximum. Implement

the Length() function. The function Length() must determine the length of the string.

Give Length() the address of the array as argument.

Note: your Length() function should be similar to the built-in strlen() function so your

job is to mimic that function without using it.

EOF is used in the function main(). This means End-of-File and is discussed later on in

this document.

In DOS, EOF can be entered by the key combination Ctrl-z (often written as ^Z). With

^Z (Say: control Z) is meant pressing the control-key and the z-key simultaneously.

The Preprocessor

Write a C-program that contains two print macro calls. The first prints the variable a, the

second prints the variables a and b. Printing happens by the use of the PRINT1 and

PRINT2 macros that accept arguments. These macros must be defined in an include-file.

The variables a and b gets their value in the function main().

Name the program “Macro.c” and the include-file “Defs.h”. Don’t forget to implement

the mechanism to avoid multiple inclusion of the header file.


Question 1 (Delay, 18%).

As shown in the figure below, a file of size F = 1000 + S bytes is transmitted on an end-to-end connection over four links, where S is the last three digits of your student number. For example, if your student number is 490123456, then S = 456 and F = 1456 bytes.

Each link is 100 km. The signal prorogation speed is 2 × 108 m/s. Assume that a header of 40 bytes is added to each packet. The bandwidth of all links is R = 1 Mbps at the beginning. The nodes use the store-and-forward scheme. (Ignore processing delays at each node.)

(0) What is your student number? Warning: If you use another student’s number as S value to answer the question, the following sub-questions will not be marked and you will get 0 in Question 1.

(1) How long does it take to transmit the file if the whole file is transmitted as a single packet. Now assume that the bandwidth of link B − C and D − E become 0.5 Mbps. Answer (2)–(4).

(2) Repeat (1).

(3) We would like to break the file into smaller packets to decrease the overall delay in the store-and-forward scheme. Assume that each time you break the file to make a new packet, you have to add 40 bytes as the header of the new packet. Repeat (2) when we break the file into N = 4 packets.

(4) What should be the optimal size of the packets to have the minimum overall delay to deliver the whole file? Find the overall delay. Hint: Since the link B − C has a smaller bandwidth compared with A − B, packets could be queued for some time!

A multithreaded malloc

A multithreaded malloc

1 Introduction
Your task in this assignment is to implement a multithreaded malloc i.e. we
should be able to use it in a multithreaded application. The basic require-
ment is of course that it is thread safe, that it still works even if two threads
us it at the same time. This is of course very easy to solve by having one
central lock that protects any data structures that are used by the module.
It is a bit harder to allow multiple threads to actually use the malloc module