# 資料結構與物件導向程式設計 Data Structures and Object-oriented Programming (CSCS10021)

Grading:

* Lab & Quizzes (Programming, demo): 20%
* Three Programming assignments, including program demonstration: First(5%)+Second(10%)+Third(10%). There are guidelines for completing the assignments.
* Two midterms: First (10%) + Second(15%)
* One final written exam: 30%

Main Content:

* C++ Functions and Scopes
* Pointers and References
* Classes and Objects
* Data Sharing and Member Functions
* Operator Overloading
* Inheritance
* Polymorphism and Virtual Functions
* Streams and File I/O
* Template and STL
* Data structures: stack, queue, graph, map, trees, ...

## Introduction to Programming
### The Components of a Computer
#### CPU
* The ==central processing unit (CPU)== is the brain of a computer
* ==Executes intructions retrieved from memory==
* Speed is measured in megahertz (MHz)
* 1 MHz = 1 million pulses per second
ex. single core, dual core, quad core
#### Memory
* Memory stores data and program instructions of programs
* A memory unit is an ordered sequence of bytes (1 byte = 8 bits)
* A memory byte is non-empty. Its initial content may be meaningless
ex. RAM (random-access memory), SRAM (static random-access memory), DRAM (dynamic random-access memory)
#### Communication Devices
ex. modem, bluetooth, network interface controller, Wi-Fi
#### Storage Devices
:::info
**How is data stored?**

Examples of data types include:
* numbers
* characters
* strings

They are encoded as a series of bits (zeros and ones).

Digital devices have two stable states, which are referred to as zero and one.
:::
* Volatile memory loses its contents when the power is turned off
* Programs and data are permanently stored in storage devices, e.g., hard drives
* They are moved to memory when necessary
ex. Disk, CD, tape, USB flash drive
#### Input Devices
ex. keyboard, mouse
#### Output Devices
ex. monitor, printer
* The monitor dispplays text and graphics
* The resolution and dot pitch determine the quality of the monitor

### Programming Languages
#### Machine Language
* Machine language is a set of primitive instructions built into every computer for the CPU
* The instructions are in the form of binary code
* These programs are difficult to read and modify
ex. We might write an instruction in binary like the following to add two numbers:
> 1101101110011110
#### Assembly Language
A program called **assembler** is used to translate assembly language programs into machine code.

ex. We might write an instruction to add two numbers as follows:
> ADDF3, R1, R2, R3

Which is 1101101110011110 in machine code
#### High-Level Language
High-level languages are English-like and easy to learn and program.

ex. The following is a high-level language statement that computes the area of a circle with a radius of 5:
> area = 5 * 5 * 3.1415;

:::warning
High-Level Languages:
* Ada (named for Ada Lovelace)
* BASIC (Beginner All-purpose Symbolic Instructional Code)
* C (whose developer designed *B* first)
* C++ (an object-oriented language, based on *C*)
* C# (a *Java*-like language ceveloped by Microsoft)
* COBOL (COmmon Business Oriented Language)
* Delphi (*Pascal*-like visual language developed by Borland)
* FORTRAN (FORmula TRANslation)
* Java (a popular obejct-oriented language, similar to *C++*)
* Pascal (named for Blaise Pascal)
* Python
* Ruby
* Visual Basic (*BASIC*-like visual language developed by Microsoft)
:::
## C++ Basics
### "Hello World!"

#include <iostream>
using namespace std;
int main()
{
//Display "Hello World!" to the console
cout<<"Hello World!"<<endl
return 0;
}

:::warning
**::endl**
It is a function, is a manipulator. It terminates a line and flushes the buffer.

**<< "Hello World!\n"**
'\n' sends the newline character but does not flush the buffer

:::Flushing the buffer
A buffer flush is the transfer of computer data ==from a temporary storage area to the computer's permanent memory==. For instance, if we make any changes in a file, the changes we see on one computer screen are stored temporarily in a buffer.
:::

**using namespace std;**
The functions *cout* and *endl* are defined in *namespace std*.
:::

#### Namespaces
A namespace is a declarative region that provides a scope to the identifiers (e.g., functions, variables, data type, etc.)

//In A.h, we have the following:

namespace Peter {
    int a = 1;
    int foo(int n) {
        if (n <= 0) return 1;
        return n * foo(n-1);
    }
}

//In B.h, we have the following:

namespace Mary {
    int a = 0;
    int foo(int n) {
        if (n <= 0) return 0;
        return n + foo(n-1);
    }
}

#include "A.h"
#include "B.h"
#include <iostream>

using namespace Mary;
int main() {
    std::cout<<Peter::foo(5)<<std::endl;
    std::cout<<foo(5)<<std::end;
}

Avoid multiple declarations.

// In A.h, we have the following:

#indef    __A_file__    // directive
#define    __A_file__
namespace ns_A {
    int a = 1;
    int foo(int n) {
        if(n <= 0) return 1;
        return n * foo(n-1);
    }
};

#endif

#include "A.h"
#include <iostream>

using namespace ns_A, std;
int main() {
    cout<<foo(5)<<std::endl;
    
    return 0;
}

Display the message "Hello World!" on the console window.

#include <iostream>
using namespace std;
// argc: number of arguments
// argv[]: store the arguments

int main(int argc, char **argv)
{
    // Display Hello World to the console
    cout << “Hello World!" << endl;
    return 0;
}

#### Integrated Development Environments (IDEs)
* Helps rapidly develop programs
* Helps while editing, compiling, debugging, and others
* Compiles and runs program
* ex. Microsoft Visual C++, Dev-C++, Eclipse, NetBeans, etc.
#### Extending the C++ Program

#include <iostream>
**using namespace std;**
int main()
{
    cout << "Programming is fun!" << endl;
    cout << "I like programming!" << endl;
    cout << "I want to learn more..." << endl;
    return 0; // normal exit
}

We can perform mathematical computations and display the results to the console.

#include <iostream>
using namespace std;
int main()
{
    cout << (1 + 2 + 3) / 3 << endl;
    return 0;
}

#include <iostream>
int main()
{
    std::cout << (1 + 2 + 3) / 3 << std::endl;
    return 0;
}

### Display the records of students

#include <iostream>
using namespace std;
class STUDENT {
    protected:
        int score; // data field
        string name;
    public:
        void printf( ) { // member function
            cout << “Name:” << name << endl;
            cout << ‘Score:” << score << endl;
}
};
const int NUM = 80;
STUDENT s[NUM]; // 80 objects
int main() {
    ……
    for ( int i = 0; i < NUM; ++i ) s[i].printf( );
    return 0;
}

Or with easier management:

#include <iostream>
#include “student.h”
using namespace std;
const int NUM = 80;
ns_s::STUDENT s[NUM];
int main() {
    ……
    for ( int i = 0; i < NUM; ++i ) s[i].printf( );
    return 0;
}

//In student.h

#ifndef __STUDENT_RECORD__
#define __STUDENT_RECORD__

#include <iostream>
using namespace std;

namespace ns_s {
    class STUDENT {
        protected:
            int score;
            string name;
        public:
            void printf() {
                cout << “Name:” << name << endl;
                cout << ‘Score:” << score << endl;
            }
    };
};
#endif

### About Header Files

What are header files?

The two files **string** and **string.h** are not the same file:

* **string.h**: stores declaration of functions that are defined in *C*
* **string**: stores declarations of functions that are declared in *C++*

Different functions are defined in these two files.
## Lab 1
**Input format**

The input begins with an integer n on a line, which means that there are n test cases. And the first character of each following row is the command.

\+ : add two vectors.
\* : dot product of two vectors.
x : cross product of two vectors.
p : print the vector.
Each vector contains three integers.
E.g. where x, y, z [𝑥, 𝑦, 𝑧] are three integers.

**Constraints**

Use class and switch to implement.

**Output Format**

You must output the result after doing the calculation.
E.g. + 1 2 3 4 5 6 means [1, 2, 3] + [4, 5, 6] = [5, 7, 9]
If the result number is [5, 7, 9], then you have to print [5,7,9].

**Sample Input**

7
p 2 3 4
\+ 1 2 3 4 5 6
\+ 8 9 3 0 2 7
\* 1 9 14 2 5 3
\* 2 7 5 11 3 0
\x 1 2 4 2 3 5
x 10 7 3 10 7 3

**Sample Output**

[2,3,4]
[5,7,9]
[8,11,10]
89
43
[-2,3,-1]
[0,0,0]

**My Solution**

#include<iostream>
#include<vector>
using namespace std;

//implement calculation
class calculation {
public:
    vector<int> addition();
    int dotProduct();
    vector<int> crossProduct();
    vector<int> printVector();
};

vector<int> calculation::addition(){
    vector<int>v1;
    vector<int>v2;
    vector<int>v(3); //output vector
    int a; //placeholder for input element

    for(int i = 0;i < 3;i++){
        cin >> a;
        v1.push_back(a);
    }

    for(int i = 0;i < 3;i++){
        cin >> a;
        v2.push_back(a);
    }

    for(int i = 0;i < 3;i++){
        v[i] = v1[i] + v2[i];
    }

    return v;
}

int calculation::dotProduct(){
    vector<int>v1;
    vector<int>v2;
    vector<int>v(3); //new vector
    int newV; //sum of total of new vector
    int a;

    for(int i = 0;i < 3;i++){
        cin >> a;
        v1.push_back(a);
    }

    for(int i = 0;i < 3;i++){
        cin >> a;
        v2.push_back(a);
    }

    for(int i = 0;i < 3;i++){
        v[i] = v1[i] * v2[i];
    }

    newV = v[0] + v[1] + v[2];

    return newV;
}

vector<int> calculation::crossProduct(){
    vector<int>v1;
    vector<int>v2;
    vector<int>v(3); //output vector
    int a;

    for(int i = 0;i < 3;i++){
        cin >> a;
        v1.push_back(a);
    }

    for(int i = 0;i < 3;i++){
        cin >> a;
        v2.push_back(a);
    }

    //formula for cross product
    v[0] = v1[1] * v2[2] - v1[2] * v2[1];
    v[1] = v1[2] * v2[0] - v1[0] * v2[2];
    v[2] = v1[0] * v2[1] - v1[1] * v2[0];

    return v;
}

vector<int> calculation::printVector(){
    vector<int>v;
    int a;

    for(int i = 0;i < 3;i++){
        cin >> a;
        v.push_back(a);
    }

    return v;
}

int main(){
    int n;
    calculation calc;
    cin >> n;
    vector<vector<int>>outVec(n, vector<int>(3));
    vector<bool>dotFlag(n); //picks out if the output is a single integer

    for(int i = 0 ; i < n ; i++){
        char command;
        cin >> command;

        switch(command) {
            case '+':
                //addition
                outVec[i] = calc.addition();
                dotFlag[i] = false;
                break;

            case '*':
                //dot product of two vectors
                outVec[i][0] = calc.dotProduct();
                dotFlag[i] = true;
                break;

            case 'x':
                //cross product of two vectors
                outVec[i] = calc.crossProduct();
                dotFlag[i] = false;
                break;

            case 'p':
                //print the vector
                outVec[i] = calc.printVector();
                dotFlag[i] = false;
                break;
         }

    }

    for(int i = 0;i < n;i++){
        if(dotFlag[i] == false){
            cout << "[";
            for(int j = 0;j < 3;j++){
                cout << outVec[i][j];
                if(j < 2){
                    cout << ",";
                }
            }
            cout << "]" << endl;
        }else{
            cout << outVec[i][0] << endl; //used specifically for the dot product
        }
    }

    system("pause");
    return 0;
}