Labs¶

约 1292 个字 104 行代码 1 张图片预计阅读时间 6 分钟

Assignment 1 StudentⅠ¶

Write a program that asks you for 10 records of students. Each record consists of a name (w/o space) and scores for three courses (in integer, 1 to 5). Output a list as follows and calculate the average score (in float) of each student and each course. Output the lowest and highest score for each course.

no      name    score1  score2  score3  average
1       K.Weng  5       5       5       5
2       T.Dixon 4       3       2       3
3       V.Chu   3       4       5       4
4       L.Tson  4       3       4       3.66667
5       L.Lee   3       4       3       3.33333
6       I.Young 4       2       5       3.66667
7       K.Hiro  4       2       1       2.33333
8       G.Ping  4       4       4       4
9       H.Gu    2       3       4       3
10      J.Jon   5       4       3       4
        average 3.8     3.4     3.6
        min     2       2       1
        max     5       5       5

Evaluation standard

The result correctness
C++ code quality (compact and reasonable)
Comments quality (clean and accurate)
C functions like printf and scanf are not allowed

Required Files: Source code

Optional Files: CMakeLists.txt (for cmake build)

Assignment 2 StudentⅡ¶

Write a CLI program that reads scoring records of students and prints out a summary sheet in the same format as the last homework, Students I.

The user can input an arbitrary number of students. Each student can take an arbitrary number of courses. Each record consists of the course id/name and the score the student got. Please note that a student usually won't choose every available course.

Evaluation standard

C++ code quality (clean, compact, and reasonable)
Comments quality

Required Files

Please prepare a zip package including the following items：

The source code
A text file containing your test data

Assignment 3 Adventure¶

The Story

Adventure is a CLI game. The player has to explore a castle, which consists of several levels and many rooms. The task of the player is to find the room where the princess is prisoned and take her to leave!

There are many types of rooms, and each type has distinct exits. Note that there is a monster in one of the rooms, whose exact location is unknown. But once the player meets the monster, the game is over.

The program always shows information about the room into which the player enters: the name of the room, how many exits are there, and the names of all the exits. For example, the player is in the lobby of the castle when the game starts, and the program outputs:

Welcome to the lobby. There are 3 exits: east, west and up.
Enter your command:

Then the player can input the command go followed by the name of the exit that he/she would like to pass through, e.g.,

go east

Consequently, the player goes into the room to the east. The program gives information about that room, like what is shown above for the lobby. This process repeats.

During this process, if the player enters a room with a monster, the program shows a message, and the game is over. Likewise, once the player enters the secret room where the princess is, the program shows the conversation between the role and the princess. After that, she is ready to leave with the player. Then the player has to find their way out. The only way to leave the castle is via the lobby.

To simplify the implementation, all the printed messages and the user input are shown in English.

Evaluation standard

C++ code quality (clean, compact, and reasonable)
Comments quality
At least three different kinds of rooms
At least five rooms
The room with the monster or princess is randomly set

Required Files

Please prepare a zip package including the following items：

The source code
A text input file with your test data

Assignment 4 Personal Diary¶

Requirements

The Personal Diary is a CLI (Command Line Interface) software that consists of four programs:

pdadd 
pdlist [ ]
pdshow 
pdremove

pdadd is used to add an entity to the diary for the date. If an entity of the same date is in the diary, the existing one will be replaced. pdadd reads lines of the diary from the stdin, line by line, until a line with a single . character or the EOF character (Ctrl-D in Unix and Ctrl-Z in Windows).
pdlist lists all entities in the diary ordered by date. If start and end dates are provided through command line parameters, it lists entities between the start and the end only. This program lists to the stdout.
pdshow prints the content of the entity specified by the date to the stdout.
pdremove removes one entity of the date. It returns 0 on success and -1 on failure.

The software stores the diary in one data file, and reads it to the memory at the beginning of each program, and stores it back to the file at the end of the process.

Evaluation standard

C++ code quality (clean, compact, and reasonable)
Comments quality
Common classes and functions should be shared between programs
These programs are physically independent, so direct interaction is not permitted
These programs are able to work together by means of redirection
These programs are able to be used in a shell/batch script

Files to submit

Please prepare a .zip package including the following items：

The source code
A shell/batch script with several use cases for your software (cover all programs)

Assignment 5 Fraction¶

Requirements

Write a class that represents a fraction number like 2/3.

The functions below have to be implemented for this class:

Default ctor
Ctor takes two integers as parameters
Copy ctor
Arithmetical operators: + - * /
Relational operators: < <= == != >= >
Typecast to double
To string
Inserter and extractor for streams
Conversion from a finite decimal string like: 1.414

Evaluation standard

C++ code quality (clean, compact, and reasonable)
Comments quality

Files to submit

Please prepare a .zip package including all the source files (including the Fraction class and some typical usages for tests)

Assignment 6 Vector¶

Requirements

Given the declaration of a class template Vector as shown below, implement the bodies of all the member functions. Please also write a main function to test all the facilities of the class Vector.

template <class T>
class Vector {
public:
  Vector();                      // creates an empty vector
  Vector(int size);              // creates a vector for holding 'size' elements
  Vector(const Vector& r);       // the copy ctor
  ~Vector();                     // destructs the vector 
  T& operator[](int index);      // accesses the specified element without bounds checking
  T& at(int index);              // accesses the specified element, throws an exception of
                                 // type 'std::out_of_range' when index <0 or >=m_nSize
  int size() const;              // return the size of the container
  void push_back(const T& x);    // adds an element to the end 
  void clear();                  // clears the contents
  bool empty() const;            // checks whether the container is empty 
private:
  void inflate();                // expand the storage of the container to a new capacity,
                                 // e.g. 2*m_nCapacity
  T *m_pElements;                // pointer to the dynamically allocated storage
  int m_nSize;                   // the number of elements in the container
  int m_nCapacity;               // the total number of elements that can be held in the
                                 // allocated storage
};

Evaluation standard

C++ code quality (clean, compact, and reasonable)
Comments quality
Test coverage

Files to submit

Please prepare a .zip package including all the source files (including the Vector class and various use cases).

Assignment 7 STL allocator + memory pool¶

STL Allocator Interface

An allocator is used by standard library containers as a template parameter :

template < class T, class Alloc = allocator<T> > class vector;
template < class T, class Alloc = allocator<T> > class list;

What does an allocator class have? Typically, it possesses:

typedef void _Not_user_specialized;
typedef _Ty value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef true_type propagate_on_container_move_assignment;
typedef true_type is_always_equal;

pointer address(reference _Val) const _NOEXCEPT
const_pointer address(const_reference _Val) const _NOEXCEPT
void deallocate(pointer _Ptr, size_type _Count)
_DECLSPEC_ALLOCATOR pointer allocate(size_type _Count)
template<class _Uty> void destroy(_Uty *_Ptr)
template<class _Objty, class _Types>
void construct(_Objty *_Ptr, _Types&&... _Args)

The above interface is just shown for illustration, please refer to std::allocator for the latest specification.

Memory Pool

STL provides you a default std::allocator, but you can implement your own to replace it. For example, you can design a memory pool to speed up the dynamic allocation of a large number of small blocks (e.g., 8 bytes, 16 bytes, ...), and to reduce memory fragmentation.

Figure 1: Mem pool using block based allocation strategy.

Requirements

Implement your own memory allocator for STL vector.
The allocator should optimize the memory allocation speed using memory pool.
The allocator should support arbitrary memory size allocation request.

How to Test Your Allocator

Basically, you should:

Create more than ten thousand vectors with different number of elements.
Pick up 1000 random vectors and resize the vectors with random sizes.
Release all the vectors.

Feel free to extend the following code skeleton for your own tests (good test is a bonus):

#include <iostream>
#include <random>
#include <vector>

// include header of your allocator here
template<class T>
using MyAllocator = std::allocator<T>; // replace the std::allocator with your allocator
using Point2D = std::pair<int, int>;

const int TestSize = 10000;
const int PickSize = 1000;

int main()
{
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<> dis(1, TestSize);

  // vector creation
  using IntVec = std::vector<int, MyAllocator<int>>;
  std::vector<IntVec, MyAllocator<IntVec>> vecints(TestSize);
  for (int i = 0; i < TestSize; i++)
    vecints[i].resize(dis(gen));

  using PointVec = std::vector<Point2D, MyAllocator<Point2D>>;
  std::vector<PointVec, MyAllocator<PointVec>> vecpts(TestSize);
  for (int i = 0; i < TestSize; i++)
    vecpts[i].resize(dis(gen));

  // vector resize
  for (int i = 0; i < PickSize; i++)
  {
    int idx = dis(gen) - 1;
    int size = dis(gen);
    vecints[idx].resize(size);
    vecpts[idx].resize(size);
  }

  // vector element assignment
  {
    int val = 10;
    int idx1 = dis(gen) - 1;
    int idx2 = vecints[idx1].size() / 2;
    vecints[idx1][idx2] = val;
    if (vecints[idx1][idx2] == val)
      std::cout << "correct assignment in vecints: " << idx1 << std::endl;
    else
      std::cout << "incorrect assignment in vecints: " << idx1 << std::endl;
  }
  {
    Point2D val(11, 15);
    int idx1 = dis(gen) - 1;
    int idx2 = vecpts[idx1].size() / 2;
    vecpts[idx1][idx2] = val;
    if (vecpts[idx1][idx2] == val)
      std::cout << "correct assignment in vecpts: " << idx1 << std::endl;
    else
      std::cout << "incorrect assignment in vecpts: " << idx1 << std::endl;
  }

  return 0;
}

Evaluation Standard

c++ code quality (clean, compact and reasonable)
comments quality
correctness and running performance of the allocator

Files to Submit

Please prepare a .zip package including the following items：

the source code (including the testing code)
makefile (for Mac or Linux users) or .exes (for Windows users, with necessary .dlls if you use MinGW) or CMakeLists.txt