Data Structure assignment 辅导



Exercise 1: CAD and Container Namespaces
To avoid name conflicts, programmers can place their classes in a namespace. For example the standard library is placed in a namespace called std. You should put your classes in your own namespace. Thus place the CAD classes (Shape,Point, Line, etc) in the namespace: YourName::CAD Place the container classes (Array) in the namespace: YourName::Containers Now access the classes in your own namespace using:
• Full class name including namespace for the Point used in the Array class. Note that you can use only the CAD part of the namespace without the YourName part because the Point is also in the YourName namespace.
• In the main program, the full namespace for Point class.
• In the main program, using declaration for using a single class (Line).
• In the main program, using declaration for a complete namespace (Containers).
• In the main program, using the Circle class by creating a shorter alias for the YourName::CAD namespace.

The Free Store

Exercise 1: Dynamically Creating Objects
Until now, we created objects on the stack. The stack is limited in size thus when creating many objects, the stack will overflow. Also arrays created on the stack can only have a fixed size determined at compile time. To overcome these problems we have to create objects on the heap using new. In the main program, create Point objects on the heap with new using the default constructor, constructor with coordinates and the copy constructor and assign it to pointer (Point*) variables. Note that you can’t directly pass a pointer variable as argument to the copy constructor. The pointer must first be dereferenced when passing it to the copy constructor. (Point* p2=new Point(*p1)). Next call the Distance() function on the pointers and try to send the Point pointers to cout. You need to dereference the pointer when passing it as argument. Don’t forget to delete the object created with new. Test the main program. Next, we will create an array of points. First ask the user for the size of the array and read it using cin. Then try to create an array on the stack using the entered size. You will see a compiler error. Arrays on the stack must have the size set at compile time. Now create the array on the heap using new. Can you use other constructors than the default constructor for the objects created in the array? Don’t forget to delete the array after use. Don’t forget the square brackets when deleting arrays! Some C++ compilers (e.g. GCC) support variable length arrays (VLA) where the size can be determined at run-time. However this is a C99 feature that is not in the C++ standard. Because VLA is not in the C++ standard you should avoid its usage since it will lead to less portable code.

Exercise 2: Creating Array of Pointers
In this exercise we make it a little more complex. With an array of Points, all points are created with the default constructor. When creating an array of pointers, each element in the array must be created separately but can be created with other constructors than the default constructor. Thus creating an array of pointers is a two step process:
• Create an array of Point pointers with 3 elements on the heap.
• Create for each element in the array a point on the heap.
• Iterate the array and print each point in the array.
• Iterate the array again and delete each point in the array.
• Delete the array itself.
Also make a drawing of the memory layout.

Exercise 3: Creating Array Class
It is easy to forget to delete memory created with new. A good practice is to let a class manage memory. Then the client of that class does not have to manage memory and can’t forget to delete memory. So instead of creating a C array with new, you can use an array class that handle memory for you. In this exercise we are going to create an array class for Point objects (see Figure 5):
• Add a source- and header file for the Array class to your current project.
• Add a data member for a dynamic C array of Point objects (Point* m_data).
• Add a data member for the size of the array.
• Add a default constructor that allocates for example 10 elements.
• Add a constructor with a size argument. The implementation should allocate the number of elements specified by thesize input argument.
• Add a copy constructor. Keep in mind that just copying the C array pointer will create an Array object that shares the data with the original Array object. Thus you need to allocate a new C array with the same size and copy each element separately.
• Add a destructor. It should delete the internal C array. Don’t forget the square brackets.
• Add an assignment operator. Keep in mind you can’t copy only the C array pointers just as in the case of the copy constructor.
• Also don’t forget to delete the old C array and allocate new memory before copying the elements. This is because C arrays can’t grow.
Further check if the source object is not the same as the this object. If you don’t check it, then a statement like arr1=arr1 will go wrong. The internal C array will then be deleted before it is copied.
• Add a Size() function that returns the size of the array.
• Add a SetElement() function that sets an element. When the index is out of bounds, ignore the “set”. We will add better error handling later.
• Add a GetElement() function. You can return the element by reference since the returned element has a longer lifetime than the GetElement() function. When the index is out of bounds, return the first element. We will add better error handling later.
• You can also add a square bracket operator. Return a reference so the [] operator can be used for both reading and writing elements. When the index is out of bounds, return the first element. We will add better error handling later.
Point& operator [] (int index);
• In the main program, test the Array class.

Exception Handling

Exercise 1: Bounds Checking Array
In the array class we created previously, the bounds checking was very basic. There was no error generated, but setting an element was ignored or the first element was returned. Obviously you want to know if there was an out of bounds error. This is possible by exception handling. Change the Array class to throw exceptions:
•In the GetElement(), SetElement() and index operator throw -1 if the index was toosmall or too big.
•In the main program, create an Array object and access an element that does not exist.Run the program. What happens?
•The exception must be caught, so place the code inside a try … catch block thatcatches an int.
•In the catch handler, print an error message.

Exercise 2: Exception Objects
Throwing an int is an easy solution. But exception handling is also object oriented and allows us to throw an object. In this exercise we will create an exception hierarchy with an ArrayException base class and an OutOfBoundsExceptionderived class as shown in Figure 3:
•You can implement both exception classes in the header file for simplicity.
•Give the ArrayException an abstract GetMessage() function that returns a std::string.
•Give the OutOfBoundsException class a constructor with an int as argument thatindicates the erroneous array index and store it in a data member.
•Override the GetMessage() function and let the implementation return a messagestring saying the given index is out of bounds.
•In the Array class, throw now a OutOfBoundsException object instead of an integer.
•Change the main program so that it catches the ArrayException base class and usesthe GetMessage() function to display an error message.


Exercise 1: Polymorphic ToString() Function
The ToString() functions of Point and Line override the ToString() from the Shape base class. We saw that we could put aPoint in a Shape* variable. But when calling the ToString() method on the Shape* variable, the function in Shape was called instead the one in Point. To make the compiler generate the required code to find out what type of object the Shape*variable is actually pointing to so it can call the right version; we need to declare the function as virtual. Thus declare the ToString() function in the Shape class as virtual and test the program again. Is the ToString() function of Point called when you use a Shape* that contains a Point now?

Exercise 2: Calling Base Class Functionality
The ToString() function of the Shape class is overridden in the derived classes. But for the derived class it is still possible to use the base class functionality. In the ToString() function of Point and Line we also want to incorporate the ID from theShape base class.
•In the ToString() method of Point, call the ToString() method of the Shape base class:std::string s=Shape::ToString();
•Append the shape description string to the point description string before returning.
•Do this also for the ToString() function in the Line class (and Circle class).
•Test the application again. Is now the ID printed when printing a point or line?

Exercise 3: Virtual Destructors
When objects are removed from memory, the destructor is called. When a derived class destructor is called, it will automatically call the base class destructor. But when you have pointers to a base class, deleting objects might not be done correctly. If not done already, print some text in the destructors of the Shape, Point and Line classes. Then test the following code:
Shape* shapes[3];
shapes[0]=new Shape;
shapes[1]=new Point;
shapes[2]=new Line;
for (int i=0; i!=3; i++) delete shapes[i];
Will the proper destructors (including the destructor of the Shape base class) be called? In this case, the derived class destructor will only be called when the destructor is declared virtual in the base class. Do this in the Shape class and run the code again. Are the proper destructors called now?

Exercise 4: Abstract Functions
Sometimes functions in the base class are only there to be overridden in the derived class. Assume that you want to draw all the shapes using the following code:
Shape* shapes[10];
shapes[0]=new Line;
shapes[1]=new Point;

shapes[9]=new Line(Point(1.0, 2.5), Point(3.4, 5.2));
for (int i=0; i!=10; i++) shapes[i]->Draw();
for (int i=0; i!=10; i++) delete shapes[i];
Create the Draw() function in the Shape base class and override it in the derived classes (point, line and if present the circle class). Simulate drawing by just printing some text. What implementation did you give the Draw() function in Shape? Shape is just an abstraction to work with various kinds of shapes like lines and circles. Shapes don’t have a physical appearance. Therefore its Draw() function will have an empty implementation. But better is to give it no implementation at all by making it a pure virtual member function:
virtual void Draw()=0;
Do this in your code. Try to create an instance of the Shape class. Is this possible? Now the Shape class is really an abstraction. You don’t make shape instances but you can still create shape pointers that point to concrete shapes like point and line. The Shape class is now an abstract base class.

Exercise 5: Template Method Pattern
In this exercise we are going to create a Print() function that is printing the shape information to the cout object. ThePrint() function can use the ToString() to obtain the string to print. You see that the implementation of Print() is in each derived class largely the same; calling ToString() and sending the result to cout. Since the ToString() function is polymorphic, we can use the polymorphic behavior in the Print() function of Shape. Thus:
•Add a Print() function to the Shape class.
•In this function, call the ToString() function and send the result to the cout object.
•In the test program, create a point and line object and call the Print() function. Does itprint the right information even when point and line do not have the Print() function?
You have now created a function for the base class (Print()) that does all the functionality common to all derived classes. Only the part of that function that is different for each derived class is delegated to a polymorphic function (ToString()). This mechanism is an often used design pattern called the “Template Method Pattern”.

Simple Inheritance

Exercise 1: Colon Syntax
The colon syntax can improve the performance of constructors. To test this, make sure that you print some text in the point’s constructors, destructor and also the assignment operator. Now, execute the following code in the test program and count the number of point constructor, destructor and assignment calls:
Line l;
Now, change the constructors in the Line class to use the colon syntax to set the start- and end-point data members and run the test program again. Is the number of point constructor, destructor and assignment calls less than before? Apply the colon syntax also for the Point class constructors and if applicable also for the Circle class.


Exercise 2: Creating Shape Base Class
It can be useful to create a hierarchy of related classes using base- and derived classes.
•Classes are related (same family)
•Common data and functionality can be put in a base class.
•You can work with derived classes as if it is the base class.
In this exercise we are going to transform the Point and Line class into a Shape hierarchy as shown in Figure 1.

First create a Shape base class.
•Add a source- and header file for a Shape class.
•Add a data member for an id number of type int.
•Add a default constructor that initializes the id using a random number. You can usethe rand() function from the “stdlib.h” header file.
•Add a copy constructor that copies the id member.
•Add an assignment operator that copies the id member.
•Add a ToString() function that returns the id as string e.g. “ID: 123”.
•Add an ID() function the retrieve the id of the shape.
Next the Point and Line classes (and the Circle class if applicable) must derive from Shape.
•Add the Shape class in the inheritance list of the Point, Line and optionallythe Circle class.
•The constructors of the Point, Line and optionally the Circle class should call theappropriate constructor in the Shapebase class.
•The assignment operator should call the assignment operator of the Shape baseclass. Otherwise the shape data will not be copied.
•Finally add code to the main program to test inheritance:

Parallel Computing and Dijkstra's Algorithm

Department of Computer Science Intro to Parallel Computing
Programming Assignment 3
Due Wednesday, October 28 at 6 pm
Dijkstra’s Algorithm
Edsger Dijkstra was a Dutch computer scientist. He is unquestionably one of the found-
ing fathers of computer science. In addition to devising Dijkstra’s algorithm, he was one
of the originators of structured programming | a precursor to modern object-oriented pro-
gramming. C, for example, is a structured programming language. He also made many
contributions to the solution of process-coordination problems in parallel computing: we’ll
learn about several later on in the course. His Wikipedia page lists more than fty funda-
mental contributions to computer science.
Dijkstra’s algorithm solves the single-source shortest path problem” in a weighted, di-
rected graph. The input consists of a weighted, directed graph and a speci ed vertex in the
graph. A directed graph or digraph is a collection of vertices and directed edges, which join
one vertex to another. A weighted dig

c语言扫雷游戏 minesweeper实现

minesweeper C 程序代写

1. (Time: 2 – 3 hours) For your final project you will be implementing the computer

game minesweeper. The game of minesweeper works as follows:

1. There is a rectangular grid of tiles

2. Hidden under some of the tiles are mines

3. Your goal is to mark all the tiles that contain mines and uncover all the tiles

4. If you uncover a tile that contains a mine you lose the game

5. If you uncover a tile that doesn’t contain a mine, it tells you how many mines

that don’t contain mines

are hidden in the eight surrounding squares

Here are some example boards with all of their contents revealed so that you can get an

idea as to what they look like.

Example 1:

2 * * 2 0

1 5 * 3 0

0 * * 2 0

0 1 2 3

Example 2:

9 0 0 0 0 0 1 1 1 0 0

8 0 0 0 0 0 1 * 1 0 0

7 0 1 1 1 0 1 1 2 1 1

6 0 1 * 1 1 1 1 1 * 1

5 0 1 1 1 1 * 1 1 1 1

4 1 1 1 0 1 1 1 0 0 0

3 1 * 1 0 0 0 0 0 0 0

2 1 1 1 0 0 0 0 0 0 0

1 1 2 1 1 0 1 1 2 2 2

0 * 2 * 1 0 1 * 2 * *

0 1 2 3 4 5 6 7 8 9


1. Name your exe

COMP2355 lab12 solution


Synchronizing Multiple Threads

In this lab you will convert your templated LList class to a SharedQueue class (you may adapt your own code or use the Lab 9 Solution). The shared queue can be safely used by many different threads without causing memory corruption. You can download the source code for this lab from Create a project called Lab12 and add the source code from t