資料結構 HW2 Paper work

2024-11-04 約 2724 字預計閱讀 6 分鐘閱讀次數：11

作者

4112064214 | 侯竣奇 | 電資學士班

答案僅供參考，如有錯誤歡迎指正。

1. Overload operator< for class Rectangle.

 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;
}

執行結果：

/datastructure-hw2-paperwork/q1_result.webp

2. Write a function to compare two ordered list.

 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;
}

執行結果：

/datastructure-hw2-paperwork/q2_result.webp

3. Modify function Add

The modification is shown below, reduces the size of c.termArray to c.terms prior to termination.
Yes, with this modification we can dispense with the data member capacity.

 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;
}

4. Write a C++ function that multiplies two polynomials.

假設第一個多項式 $A$ 有 $m$ 項、第二個多項式 $B$ 有 $n$ 個項，則：

基本運算
- 外層迴圈 $m$ 次
- 內層迴圈 $n$ 次
- 共 $mn$ 次
結果處理
- 每次 $m*n$ 階需尋找是否已存在相同指數的項
  - 多項式最多可能有 m*n 個項
  - 每次搜尋最差需要 $O(mn)$ 次比較
- 找不到相同指數的項需要 NewTerm 時
  - 複製最多需要耗費 $O(mn)$ ，因為結果最多會有 $m*n$ 項

故時間複雜度約為 $O(m^2*n^2)$

 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;
}

5. Write a C++ functions to input and output a sparse martrix.

operator>> 的時間複雜度： $O(1)$
operator<< 的時間複雜度： $O(rows*cols)$

  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;
}

執行結果：

/datastructure-hw2-paperwork/q5_result.webp

6. Write an algorithm that takes two strings x, y and return -1, 0, or +1.

 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;
}

7. Compute the failure function for each of the following patterns.

 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;
}

執行結果：

/datastructure-hw2-paperwork/q7_result.webp

如果你喜歡這篇文章，歡迎點擊下方的 Like 拍手給我鼓勵，LikeCoin 官方會再發放實質獎勵給創作者喔！（註冊 Liker 完全免費）

更新於 2024-11-04

閱讀原始文檔

程式, C++

返回 | 主頁

目錄

資料結構 HW2 Paper work

作者

1. Overload operator< for class Rectangle.

2. Write a function to compare two ordered list.

3. Modify function Add

4. Write a C++ function that multiplies two polynomials.

5. Write a C++ functions to input and output a sparse martrix.

6. Write an algorithm that takes two strings x, y and return -1, 0, or +1.

7. Compute the failure function for each of the following patterns.