乐趣区

关于后端:CS110数据结构

Homework 4 — Math
CS110/EIE110/LP101 2020 Fall
Macau Univ. of Sci. and Tech.
Instructor: Zhiyao Liang

1 Introduction

Math is important for a student. We have learned fundamental arithmetic operators of + – * / in our primary schools, and we have learned
recently the operation of matrix multiplication in Linear Algebra. In this homework, we want to write a C program that can help students to lean
these important math operations by solving problems like what are shown in the above pictures 1
.

2. Knowledge points

The emphasized knowledge aspects in this homework include the following:
Struct
Enum
Use malloc() or calloc() to dynamically create objects on the heap memory.
Linked list (singly linked list)
Function with array arguments.
Multi-dimensional array.
Design and implement functions.
File reading and writing.
Design a program with multiple files.
The main function with command line arguments.
Friendly interaction between the computer and the user.
User’s menu of choices
Show friendly and clear messages to a user.
Clear input queue when needed. This is a technique to avoid input confusion.
When user’s input is wrong, show some error message, and ask the user to do input again.
We will write a C program that will perform different operations on strings. The program is organized using multiple functions and files.
Algorithms: matrix multiplication.
2 Introduction of tasks of this homework
2.1 Arithmetic problems
The program will let a user (a student) do exercises of arithmetic problems. For example, consider the following 5 problems:
11 + 25 = ?
79 – 32 = ?
80 * 20 = ?
45 / 9 = ?
79 + 21 = ?
These problems can be saved in a file. A possible choice of the file content is using 3 sequences of strings: a sequence of numbers, a sequence of
operators, and a sequence of numbers, like the following:
11 79 80 45 79

      • / +
  • 32 20 9 21
    We want the program to be able to do the following
    Create new problems. For example, in order to generate 5 problem, then program can generate a list of 5 random integers, and a list of 5
    random operators, and a list of 5 random integers.
    Write the created problems into some file, so that they can be used again later.
    Read a list of problems from a file which contains some problems that are written into the file by this program earlier.
    Modify the list of problems, like
    Adding a problem to the list.
    Deleting a problem from a list.
    Changing a problem in a list. For example, changing 79 – 32 to 79 + 57 .
    2.1.1 Hints on a list of arithmetic problems.
    We will use linked lists to record the arithmetic problems, not arrays. A sequence of problems (each problem has the form
    number1 operator number2 ) can be recorded in two ways using lists
  • Using three linked lists with the same length.
    a list of number1
    a list of operators
    a list of number2
  • Using just one linked list, where each node contain the three pieces of information of a problem: number1, operator, and number2. You can
    make them as three members in a structure of a node; Or you can create a structure Problem containing the three members while Problem
    is a member of a node.
    The following hints are on the file that saves a sequence of problems.
    The format of the file can be decided by you. One choice that is shown above is using three lines.
    It can be easier to open a file for reading and writing in text mode by a call like fopen(filename, mode) .
    To read an integer from a file, we can use fscanf(fileName, “%d”, &varName) .
    To read an operator from a file, we can use fscanf(fileName, “%s”, charArrayName) , this will read a string with one character (besides the
    null character).
    To write an integer or an operator into a file, we can use the corresponding calls of the fprintf() function. Make sure that the numbers and
    operators are separated by at least a single white space character in the file.
    To generate a random integer, we can call the rand() or srand() functions. An introduction to use these function can be found at:
    https://www.dummies.com/progr…
    2.2 Matrix multiplication
    A matrix can be represented by different ways, including the at least the following:
    A two-dimensional array, where the two dimensions correspond to the number of rows and columns of the matrix respectively.
    A structure containing three members:
    the number of rows
    the number of columns
    the sequence of integers in the matrix, which is a one-dimensional array, or a pointer to the first element of such an array. We know the
    idea that multi-dimensional array can be represented by a one-dimensional array.
  • Tasks of the program.
    3.1 User menu
    When the program runs, an user sees a menu containing choices like the following:
    a: create a sequence of arithmetic problems.
    b: show a sequence arithmetic problems.
    c: save a sequence arithmetic problems to a file.
    d: load a sequence arithmetic problems from a file.
    e: add a problem to the sequence of arithmetic problems.
    f: change a problem in the a sequence of arithmetic problems.
    g: delete a problem from the sequence of arithmetic problems.
    h: show the correct answers of the sequence of arithmetic problems.
    i: create a problem of matrix multiplication problem.
    j: show the correct answer of the matrix multiplication problem.
    q: quit
    The tasks related to theses choices are described in details in the following sections.
    3.2 Data storage
    The program should have (at least) the following data in memory:
    Storage of a sequence of arithmetic problems. Linked lists should be used. As described earlier, you can use three linked lists or just one
    linked list. When a new sequence of problems is created they are saved in these lists; When a sequence of problems are loaded from a file,
    they are saved in these lists and the previous data in these lists will be deleted.
    Storage of three matrixes: two matrixes participate in a multiplication, while the other record the result to be computed.
    A file name. The file to write problems into and read problems from.
    3.3 File name
    The file name should be given from command-line arguments. For example, when the program has been compiled and an executable file
    myProgram.exe is generated (on Windows), then the command-line command:
    myProgram problems.txt
    specifies that the file name is problems.txt . The file with the name may or may not exist. When you write new data into this file, you can decide if
    the data will be appended to this file, or the file’s content will be deleted and replaced the new data.
    3.4 Choice a
    The number of problems should be decided in the program, maybe some symbolic constant.
    A sequence of arithmetic problems will be generated, whose numbers and operators are randomly chosen.
    The generated problems is saved in memory using linked lists.
    3.5 Choice b
    The sequence of arithmetic problems are printed on screen in some clear and proper way. The nodes in the list will be accessed one by one. If the
    list is empty, print some message saying that no problem is created.
    3.6 Choice c
    A file stream should be opened using fopen() , better with a text mode argument. The sequence of arithmetic problems will be written to the
    stream. The format of the file should be proper.
    3.7 Choice d
    This is the opposite operation of Choice c. The file content is read from a file stream and saved into some list (or lists) of node. Before reading from
    the stream, make sure that its reading position should be at the beginning of the file (maybe call the rewind() function) The previously saved data
    in the lists should be released (free() ).
    3.8 Choice e
    Create new arithmetic problem, record it as some node and append the node to the list. If you use three linked lists, then three nodes should be
    appended to the three lists.
    3.9 Choice f
    Find the middle node in the list. If there are 9 nodes in the list, then the middle one is the 5
    th node. If there are 10 nodes in the list, then the 5
    th or
    6
    th node is the middle one. Replace the problem data in the node with some random number and operator.
    3.10 Choice g
    Find the middle node in the list and delete it. The space of the deleted node should be released. The left neighbor and right neighbor of the deleted
    node should be connected to make the list unbroken.
    3.11 Choice h
    Print the correct answers of the sequence of arithmetic problems. Especially, for division, you can either show some floating point number with
    decimal point, or show some fraction. For example, the result of 4 / 6 can be printed as 0.6666 or 2/3 .
    [Bonus] If you can show the result of division as some mostly-reduced form of fraction. When number2 of the division is 0, show that the answer is
    undefined or Infinity .
    3.12 Choice i
    Create two matrixes of integers. The size of the two matrixes (number of rows and columns) can be decided by you. But the number of rows of
    matrix A should be the same as the number of columns of matrix B, otherwise, some error message should be printed.
    Record the two matrixes in some proper way, that has been discussed in Section 2.2.
    The integers of the matrixes can be randomly generated, or input from a user, you can decide which way.
    3.13 Choice j
    Define a function matrix_multiply() that has parameters representing 2 matrixes and compute the result of matrix multiplication. You can define
    the proper parameters according to your way of recording a matrix.
    The result of matrix multiplication should be recorded as another a matrix, then be printed in some clear way.
    3.14 Choice q
    Close any opened file stream. Free all space allocated on heap. Then quit and end the program.
    3.15 free() and fclose()
    When some storage dynamically allocated on the heap memory will not be used anymore, its memory space should be released by calling
    free() . Especially, the nodes in a list should be released somewhere in the program.
    When a file stream is not used, it should be closed by calling with fclose() .
    3.16 Bonus choices
    Some bonus points will be given if you can do the following extra tasks:
    Implement some menu choice so that a user can provide answers to the arithmetic problems, and some grade will be printed according to the
    correct answer.
    Implement some menu choice so that a user can provide answer to the problem of matrix multiplication, and some result can be printed
    saying whether the answer is correct or not.
    Implement some menu choice so that the created matrix problem can be saved to, or loaded from some file.
    3.17 Other requirements
    Design functions properly. Arrange your code in several .c or .h files. Compile and test your program. For using library functions, check the related
    documents on some website like https://en.cppreference.com or cplusplus.com
    Submission
    Upload your files at the webpage address of this homework on Moodle.
    The uploaded files can include only the following:
    The source files (.c and .h files),
    An optional document file (.txt, .md, .docx) describing your work, like: what features of the homework are achieved; what are the
    remaining problems; how did you solve the difficulties that you met, some screen record of compiling and running the program …
    About homework submission in a group:
    at most 3 students can form a group to submit the homework. You can surely do the homework alone.
    One group only need to submit the homework by once by one student. The other members do not need to submit anything, or just
    submit one .txt file saying who are the members of the group and who submitted the homework.
    In each file that you submit, record the names in Chinese (if you are not an international student) and English letters, classes of each
    student, last 5 digits of student ID, as comments. For example:
退出移动版