資料結構 HW2 Paper work

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// Overload operator< for class Rectangle such that r < s if and only if the area of r is less than that of s.

#include <iostream>

class Rectangle
{
public:
    // fields
    int xLow;
    int yLow;
    int height;
    int width;

    // methods
    Rectangle(int xLow = 0, int yLow = 0, int height = 0, int width = 0) : xLow(xLow), yLow(yLow), height(height), width(width) {}
    ~Rectangle() {}
    int Area() const;
    bool operator<(const Rectangle &s);
};

int Rectangle::Area() const
{
    return height * width;
}

bool Rectangle::operator<(const Rectangle &s)
{
    return (this->Area()) < (s.Area());
}

int main()
{
    std::cout << "An example of overload < for Rectangle:" << std::endl;
    // >
    std::cout << "a(0, 0, 10, 20), b(0, 0, 11, 20)" << std::endl;
    Rectangle a(0, 0, 10, 20), b(0, 0, 11, 20);
    std::cout << "result: " << bool(a < b) << std::endl;
    // ==
    std::cout << "e(0, 0, 10, 20), f(0, 0, 10, 20)" << std::endl;
    Rectangle e(0, 0, 10, 20), f(0, 0, 10, 20);
    std::cout << "result: " << bool(e < f) << std::endl;
    // <
    std::cout << "c(0, 0, 10, 20), d(0, 0, 9, 20)" << std::endl;
    Rectangle c(0, 0, 10, 20), d(0, 0, 9, 20);
    std::cout << "result: " << bool(c < d) << std::endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

// If a = (a_0, ..., a_{n-1}) and b = (b_0, ..., b_{m-1}) are ordered lists,
//  then a < b if:
//      a_i = b_i for 0 <= i < j and a_j < b_j,
//      or, if a_i = b_i for 0 <= i < n and n < m.
// Write a function that returns -1, 0, or +1, depending upon whether a < b, a = b, or a > b.
// Assume that the a_is and b_js are integer.

#include <iostream>
#include <algorithm>
#include <vector>

int compare_lists(const std::vector<int> &a, const std::vector<int> &b)
{
    size_t n = a.size();
    size_t m = b.size();

    size_t min_len = std::min(n, m);

    for (size_t i = 0; i < min_len; i++)
    {
        if (a[i] < b[i])
        {
            return -1;
        }
        else if (a[i] > b[i])
        {
            return 1;
        }
    }

    // all elements up to min_len are equal
    // compare length
    if (n < m)
    {
        return -1;
    }
    else if (n > m)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

void print_vector(const std::vector<int> &a)
{
    for (int e : a)
    {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

int main()
{
    std::cout << "Verify function:" << std::endl;
    std::vector<int> a, b;
    for (int i = 0; i < 10; i++)
    {
        a.push_back(i);
    }
    for (int i = 0; i < 11; i++)
    {
        b.push_back(i);
    }

    // -1
    std::cout << "a: ";
    print_vector(a);

    std::cout << "b: ";
    print_vector(b);
    std::cout << "compare result: " << compare_lists(a, b) << std::endl;

    // 1
    a.push_back(10);
    a.push_back(11);
    std::cout << "a: ";
    print_vector(a);

    std::cout << "b: ";
    print_vector(b);
    std::cout << "compare result: " << compare_lists(a, b) << std::endl;

    // 0
    std::cout << "a: ";
    print_vector(a);

    b.push_back(11);
    std::cout << "b: ";
    print_vector(b);
    std::cout << "compare result: " << compare_lists(a, b) << std::endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

// Modify function Add so that it reduces the size of c.termArray to c.terms prior to termination.
// With this modification, can we dispense with the data member capacity?

#include <iostream>

class Polynomial;
class Term
{
    friend Polynomial;

private:
    float coef; // coefficient
    int exp;    // exponent
};

class Polynomial
{
    // p(x) = a_0*x^{e_0} + ... + a_n*x^{e_n}; a set of ordered pairs of <e_i, a_i>,
    // where a_i is a nonzero float coefficient and e_i is a non-negative integer exponent.
public:
    Polynomial() : termArray(nullptr), terms(0) {} // Construct the polynomial p(x) = 0.
    ~Polynomial() { delete[] termArray; }
    Polynomial Add(Polynomial poly); // Return the sum of the polynomials *this and poly.
    void NewTerm(const float theCoeff, const int theExp);

private:
    Term *termArray; // array of nonzero terms
    // int capacity;    // size of termArray, we can delete it
    int terms; // number of nonzero terms
};

void Polynomial::NewTerm(const float theCoeff, const int theExp)
// Add a new term to the end of termArray
{
    Term *temp = new Term[terms + 1]; // new array, don't double the capacity
    if (termArray)
    {
        std::copy(termArray, termArray + terms, temp);
        delete[] termArray; // deallocate old memory
    }
    termArray = temp;

    termArray[terms].coef = theCoeff;
    termArray[terms++].exp = theExp;
}

Polynomial Polynomial::Add(Polynomial b)
{ // Return the sum of the polynomials *this and b.
    Polynomial c;
    int aPos = 0, bPos = 0;
    while ((aPos < terms) && (bPos < b.terms))
    {
        if (termArray[aPos].exp == b.termArray[bPos].exp)
        {
            float t = termArray[aPos].coef + b.termArray[bPos].coef;
            if (t)
                c.NewTerm(t, termArray[aPos].exp);
            aPos++;
            bPos++;
        }
        else if (termArray[aPos].exp < b.termArray[bPos].exp)
        {
            c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
            bPos++;
        }
        else
        {
            c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
            aPos++;
        }
    }

    // add in remaining terms of *this
    for (; aPos < terms; aPos++)
    {
        c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
    }
    // add in remaining terms of b(x)
    for (; bPos < b.terms; bPos++)
    {
        c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
    }
    return c;
}

int main()
{
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

// Write a C++ function that multiplies two polynomials represented as in this section.
// What is the computing time of your function?

#include <iostream>

class Polynomial;
class Term
{
    friend Polynomial;

private:
    float coef; // coefficient
    int exp;    // exponent
};

class Polynomial
{
public:
    Polynomial() : termArray(nullptr), terms(0) {}
    ~Polynomial() { delete[] termArray; }
    void NewTerm(const float theCoeff, const int theExp);
    Polynomial Multiply(Polynomial b); // New multiplication function

private:
    Term *termArray;
    int terms;
};

void Polynomial::NewTerm(const float theCoeff, const int theExp)
{
    Term *temp = new Term[terms + 1];
    if (termArray)
    {
        std::copy(termArray, termArray + terms, temp);
        delete[] termArray;
    }
    termArray = temp;
    termArray[terms].coef = theCoeff;
    termArray[terms++].exp = theExp;
}

Polynomial Polynomial::Multiply(Polynomial b)
{
    Polynomial c;

    // Multiply each term of first polynomial with each term of second polynomial
    for (int i = 0; i < terms; i++)
    {
        for (int j = 0; j < b.terms; j++)
        {
            // Calculate new coefficient and exponent
            float newCoef = termArray[i].coef * b.termArray[j].coef;
            int newExp = termArray[i].exp + b.termArray[j].exp;

            // Search if this exponent already exists in result
            bool found = false;
            for (int k = 0; k < c.terms; k++)
            {
                if (c.termArray[k].exp == newExp)
                {
                    // Add to existing term
                    c.termArray[k].coef += newCoef;
                    found = true;
                    break;
                }
            }

            // If exponent wasn't found, add new term
            if (!found && newCoef != 0)
            {
                c.NewTerm(newCoef, newExp);
            }
        }
    }
    return c;
}

int main()
{
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

// Write a C++ functions to input and output a sparse martrix.
//     These should be implemented by overloading the >> and << operators.
//     You should design the input and output formats.
// However, the internal representation should be a one dimensional array of nonzero terms as used in this section.
// Analyze the computing time of your functions.

#include <iostream>
#include <iomanip>

class SparseMatrix;
class MatrixTerm
{
    friend SparseMatrix;
    friend std::ostream &operator<<(std::ostream &os, const SparseMatrix &matrix);
    friend std::istream &operator>>(std::istream &is, SparseMatrix &matrix);

private:
    int row, col, value;
};

// A set of triples, <row, column, value>, where row and column are non-negative
//  integers and form a unique combination; value is also an integer.
class SparseMatrix
{
    friend std::ostream &operator<<(std::ostream &os, const SparseMatrix &matrix);
    friend std::istream &operator>>(std::istream &is, SparseMatrix &matrix);

public:
    // The constructor function creates a SparseMatrix with
    //  r rows, c columns, and a capacity of t nonzero terms.
    SparseMatrix(int r, int c, int t) : rows(r), cols(c), terms(0), capacity(t)
    {
        if (r < 0 || c < 0 || t < 0)
            throw std::invalid_argument("Negative dimensions or capacity");
        smArray = new MatrixTerm[capacity];
    }
    ~SparseMatrix()
    {
        delete[] smArray;
    }

private:
    int rows, cols, terms, capacity;
    MatrixTerm *smArray;
};

// Input operator overloading
std::istream &operator>>(std::istream &is, SparseMatrix &matrix)
{
    std::cout << "Enter the number of non-zero terms: ";
    is >> matrix.terms;
    if (matrix.terms > matrix.capacity)
    {
        throw std::overflow_error("Number of terms exceeds matrix capacity");
    }

    std::cout << "Enter each term as row, column value (separate by space):" << std::endl;
    for (int i = 0; i < matrix.terms; i++)
    {
        is >> matrix.smArray[i].row >> matrix.smArray[i].col >> matrix.smArray[i].value;
    }
    return is;
}

// Output operator overloading
std::ostream &operator<<(std::ostream &os, const SparseMatrix &matrix)
{
    int current_term = 0;
    for (int i = 0; i < matrix.rows; i++)
    {
        for (int j = 0; j < matrix.cols; j++)
        {
            if (current_term < matrix.terms &&
                matrix.smArray[current_term].row == i &&
                matrix.smArray[current_term].col == j)
            {
                os << std::setw(4) << matrix.smArray[current_term++].value;
            }
            else
            {
                os << std::setw(4) << 0;
            }
        }
        os << std::endl;
    }
    return os;
}
int main()
{
    try
    {
        int r, c, t;
        std::cout << "enter the rows, columns, and capacity of non-zero terms r, c, t:" << std::endl;
        std::cin >> r >> c >> t;
        SparseMatrix sm(r, c, t);
        std::cin >> sm;

        std::cout << "\nThe sparse matrix is:" << std::endl;
        std::cout << sm;
    }
    catch (const std::exception &e)
    {
        std::cerr << "Error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// If x = (x_0, ..., x_{m-1}) and y = (y_0, ..., y_{n-1}) are strings,
//  where x_i and y_i are letters of the alphabet, then
//  x is less then y if x_i = y_i for 0 <= i < j and x_j < y_j
//  or if x_i = y_i for 0 <= i <= m and m < n.
// Write an algorithm that takes two strings x, y and returns either -1, 0, or +1 if x < y, x = y, or x > y repectively.

#include <string>

int compareStrings(const std::string &x, const std::string &y)
{
    // Get the lengths of both strings
    int m = x.length();
    int n = y.length();

    // Find the minimum length between the two strings
    int minLength = std::min(m, n);

    // Compare characters until we find a difference or reach the end of a string
    for (int i = 0; i < minLength; i++)
    {
        if (x[i] < y[i])
        {
            return -1; // x is less than y
        }
        if (x[i] > y[i])
        {
            return 1; // x is greater than y
        }
    }

    // All characters up to minlength are equal
    // Now check the length
    if (m < n)
        return -1;
    if (m > n)
        return 1;
    return 0; // exactly equal
}

int main()
{
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

// Compute the failure function for each of the following patterns:
//  (a) a a a b
//  (b) a b a b a a
//  (c) a b a a b a a b b

#include <iostream>
#include <string>
#include <vector>

std::vector<int> build_failure_function(std::string &t)
{
    std::vector<int> F(t.size());
    F[0] = -1;

    for (int i = 1, pos = -1; i < t.size(); i++)
    {
        while (~pos && t[i] != t[pos + 1])
            pos = F[pos];

        if (t[i] == t[pos + 1])
            pos++;

        F[i] = pos;
    }
    return F;
}

int main()
{
    std::cout << "failure function of a: " << std::endl;
    std::string str_a = "aaaab";
    std::vector<int> a = build_failure_function(str_a);
    for (int e : a)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;

    std::cout << "failure function of b: " << std::endl;
    std::string str_b = "ababaa";
    std::vector<int> b = build_failure_function(str_b);
    for (int e : b)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;

    std::cout << "failure function of c: " << std::endl;
    std::string str_c = "abaabaabb";
    std::vector<int> c = build_failure_function(str_c);
    for (int e : c)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
    return 0;
}