设计实现抽象数据类型“有理数”

【PS】： 由于笔者的能力水平有限，如果遇到相关错误或者存在歧义的地方，欢迎在下方评论区留言或者加我QQ1633497269联系笔者，如果你觉得这篇文章对你有帮助，那么不妨动动你的小手点赞收藏转发，让更多的人看到这篇文章。你们的支持是我更新的动力(≧∇≦)/

题目

设计实现抽象数据类型“有理数”
设计并上机实现抽象数据类型“有理数”，有理数的基本操作包括：两个有理数的加、减、乘、除等（包括有理数的创建和输出）。
要求：
- 有理数的类型，我们可以构造成一个结构体类型，这个结构体由两个整数构成，分别表示有理数的分子和分母。
- //标识符命名不要用拼音，如：int fz; int fm;
- 在初始化或创建一个有理数时，可以给出有理数的分子和分母来创建一个有理数；
- 也可以给出一个小数形式的有理数，来计算对应的分子分母来创建一个有理数（可设置一个允许的计算误差）。
- 以分数形式创建有理数时，要处理分母为零的异常情况。
- 输出不能有类似于4/4、3/6这样的结果数据。
- 要有能根据用户输入选择不同运算的菜单选择界面。
- 确定处理的数据元素属性，构造数据类型
- 函数的参数（传值、传地址）
- 函数的返回值（有返回值，无返回值void）
- 可以自己写.h头文件（构造数据类型，设计相关运算）（.h也可以在其他位置引用）（不熟悉.h的可以不写）
- 低级错误：= or == , a=b还是b=a，中文符号or英文符号……
- 函数的功能尽可能独立，尽量不用全局变量，降低函数之间的耦合度
- 不要写重复的代码（代码冗余） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分析

这里我们的有理数可以使用分数来表示，这样有理数的加减运算就变成了分数的加减运算，这样极大的减少了代码量，提高代码的复用性和可读性。我们可以把四则运算分别封装成对应的函数即：add，sub，mul，div，需要进行四则运算时，调用相应的函数即可，考虑到分数可能不是最简的，我们需要写一个函数Reduction ，该函数是用来对四则运算后的结果进行约分，由于在约分过程中需要使用最大公约数，所以我们需要写一个求最大公约数的函数：gcd。实现有理数创建函数：Create，输出函数：show。由于需求上需要为用户提供菜单，所以我们还需要写一个菜单。
具体代码详解如下：

创建有理数的数据结构

typedef struct Fraction {
    int Molecule;   //分子
    int Denominator;    //分母
} Fraction;
1
2
3
4

Init初始化有理数

这里我们传的是引用&，可以提高代码的运行速度。

void Init(Fraction &F) {
    F.Denominator = 0;
    F.Molecule = 0;
}
1
2
3
4

gcd最大公约数

利用双目运算符和递归求解最大公约数，这里就不过多赘述，不懂的同学可自行学习。

int gcd(int a, int b) {//递归求最大公约数
    return b == 0 ? abs(a) : gcd(b, a % b);
}
1
2
3

Reduction约分函数

Fraction Reduction(Fraction &F) {//对分数进行约分
    int GCD = gcd(F.Molecule, F.Denominator);
    F.Molecule /= GCD;
    F.Denominator /= GCD;
    return F;
}
1
2
3
4
5
6

add加法运算

Fraction add(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Denominator + F2.Molecule * F1.Denominator;
    temp.Denominator = F1.Denominator * F2.Denominator;
    return Reduction(temp);
}
1
2
3
4
5
6

sub减法运算

Fraction sub(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Denominator - F2.Molecule * F1.Denominator;
    temp.Denominator = F1.Denominator * F2.Denominator;
    return Reduction(temp);
}
1
2
3
4
5
6

mul乘法运算

Fraction mul(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Molecule;
    temp.Denominator = F2.Denominator * F1.Denominator;;
    return Reduction(temp);
}
1
2
3
4
5
6

div除法运算

注意当第一个数为正数，第二个数为负数时，如果不加入判断，除法的结果可能会出现错误，这是因为第二个数在转换成分数时，分子是负数，进行乘法运算时，会导致结果的分母出现负数。这是我们不希望看到的，所以需要加入判断。

Fraction div(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Denominator;
    temp.Denominator = F1.Denominator * F2.Molecule;
    if(temp.Denominator<0){
        temp.Molecule = -temp.Molecule;
        temp.Denominator = -temp.Denominator;
    }
    return Reduction(temp);
}
1
2
3
4
5
6
7
8
9
10

Create创建函数

用户的输入规则为分数和小数，如果是负数需要把-写在最前面，如果用户输入的为整数 比如2，则需要写成 2.0，分数写成1/3，-4/7的格式，这里我们需要使用c++的string类
先检索输入的数中是否含有. 没有则为分数（输入非法会报错）
对于分数，我们只需要对输入的字符串进行操作，/ 左边就是分子Molecule，右边是分母Denominator。
而对于小数，是将小数点左右的数提取为两个整数
分子 = 整数部分扩大相应的倍数再加上原来的小数部分（整数）
分母 = 扩大的倍数
扩大的倍数=10^{（最后一个数字的索引`-`小数点的索引）}
这里用到了一些库函数，具体作用如下：
这里需要使用stoi 函数，这里不使用stof 函数，是因为会产生精度问题，例如2.33在转换成浮点数会变成2.329999，那么再扩大时就会产生错误。

string str;
str.find('c');//在字符产str中寻找字符c，如果没有返回-1如果找到了返回第一次出现的索引
str.substr(a,b) //从索引a位置开始返回长度为b的子串。如果没有b表示返回从a到末尾的子串
str.size()//返回字符串串的长度
stoi(str)//讲str转换成int类型
pow(a,b)//a的b次方
1
2
3
4
5
6

Fraction Create() {
    string temp;
    printf("Please enter a rational number or fraction:\n");
    printf("Notes: For example you can enter -1/3 or -0.33 or 0.33 (please round to two decimal places)\n");
    printf("please enter:\n");
    cin >> temp;
    Fraction F;
    int index_of = (int)temp.find('.');
    if (index_of != -1) {
        if (temp[0] != '-') {
            int num = (int)temp.size() - 1 - index_of;//扩大倍数的指数，即小数点需要像右移动的位数
            int INTEGER = stoi(temp.substr(0, index_of));//indexof的长度正好就是小数点前字串的长度
            int DECIMAL = stoi(temp.substr(index_of + 1));
            F.Molecule = INTEGER * (int) pow(10, num) + DECIMAL;
            F.Denominator = 1 * (int) pow(10, num);
        } else {
            int num = (int)temp.size() - 1 - index_of;
            int INTEGER = stoi(temp.substr(1, index_of));
            int DECIMAL = stoi(temp.substr(index_of + 1));
            F.Molecule = INTEGER * (int) pow(10, num) + DECIMAL;
            F.Molecule = -F.Molecule;
            F.Denominator = 1 * (int) pow(10, num);
        }

    } else {
        int index = (int)temp.find('/');
        F.Molecule = stoi(temp.substr(0, index));
        F.Denominator = stoi(temp.substr(index + 1));
    }
    return F;

}
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

show输出函数

void show(Fraction &F) {
    if (F.Denominator == 1)//如果分子为1，则只输出分子，不输出分母
        printf("%d", F.Molecule);
    else if (F.Denominator == 0)//分母不能为）
        printf("ERROR");
    else
        printf("%d/%d\n", F.Molecule, F.Denominator);
}
1
2
3
4
5
6
7
8

main函数及Menu

int main() {
    char k;
    cout << "Four arithmetic operations codes:\n"
            "A = Addition\n"
            "S = Subtraction\n"
            "M = Multiplication\n"
            "D = Division\n"
            "R = Renter" << endl;
    Fraction F1, F2, F3;
    Init(F1);
    Init(F2);
    F1 = Create();
    F2 = Create();
    for (;;) {
        cout << "\nPlease enter Four arithmetic operations codes:" << endl;
        cin >> k;
        switch (k) {
            case 'A': {
                F3 = add(F1, F2);
                show(F3);
                break;
            }
            case 'S': {
                F3 = sub(F1, F2);
                show(F3);
                break;
            }
            case 'M': {
                F3 = mul(F1, F2);
                show(F3);
                break;
            }
            case 'D': {
                F3 = div(F1, F2);
                show(F3);
                break;
            }
            case 'R': {
                Init(F1);
                Init(F2);
                F1 = Create();
                F2 = Create();
                break;
            }
            default:
                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

整体代码

#include <bits/stdc++.h>

using namespace std;

typedef struct Fraction {
    int Molecule;   //分子
    int Denominator;    //分母
} Fraction;

void Init(Fraction &F);

Fraction Create();

int gcd(int a, int b);

Fraction Reduction(Fraction &F);

Fraction add(Fraction &F1, Fraction &F2);

Fraction sub(Fraction &F1, Fraction &F2);

Fraction mul(Fraction &F1, Fraction &F2);

Fraction div(Fraction &F1, Fraction &F2);

void show(Fraction &F);

int main() {
    char k;
    cout << "Four arithmetic operations codes:\n"
            "A = Addition\n"
            "S = Subtraction\n"
            "M = Multiplication\n"
            "D = Division\n"
            "R = Renter" << endl;
    Fraction F1, F2, F3;
    Init(F1);
    Init(F2);
    F1 = Create();
    F2 = Create();
    for (;;) {
        cout << "\nPlease enter Four arithmetic operations codes:" << endl;
        cin >> k;
        switch (k) {
            case 'A': {
                F3 = add(F1, F2);
                show(F3);
                break;
            }
            case 'S': {
                F3 = sub(F1, F2);
                show(F3);
                break;
            }
            case 'M': {
                F3 = mul(F1, F2);
                show(F3);
                break;
            }
            case 'D': {
                F3 = div(F1, F2);
                show(F3);
                break;
            }
            case 'R': {
                Init(F1);
                Init(F2);
                F1 = Create();
                F2 = Create();
                break;
            }
            default:
                return 0;
        }
    }
}

void Init(Fraction &F) {
    F.Denominator = 0;
    F.Molecule = 0;
}

Fraction Create() {
    string temp;
    printf("Please enter a rational number or fraction:\n");
    printf("Notes: For example you can enter -1/3 or -0.33 or 0.33 (please round to two decimal places)\n");
    printf("please enter:\n");
    cin >> temp;
    Fraction F;
    int index_of = (int) temp.find('.');
    if (index_of != -1) {
        if (temp[0] != '-') {
            int num = (int) temp.size() - 1 - index_of;
            int INTEGER = stoi(temp.substr(0, index_of));
            int DECIMAL = stoi(temp.substr(index_of + 1));
            F.Molecule = INTEGER * (int) pow(10, num) + DECIMAL;
            F.Denominator = 1 * (int) pow(10, num);
        } else {
            int num = (int) temp.size() - 1 - index_of;
            int INTEGER = stoi(temp.substr(1, index_of));
            int DECIMAL = stoi(temp.substr(index_of + 1));
            F.Molecule = INTEGER * (int) pow(10, num) + DECIMAL;
            F.Molecule = -F.Molecule;
            F.Denominator = 1 * (int) pow(10, num);
        }

    } else {
        int index = (int) temp.find('/');
        F.Molecule = stoi(temp.substr(0, index));
        F.Denominator = stoi(temp.substr(index + 1));
    }
    return F;

}

int gcd(int a, int b) {//递归求最大公约数
    return b == 0 ? abs(a) : gcd(b, a % b);
}

Fraction Reduction(Fraction &F) {//对分数进行约分
    int GCD = gcd(F.Molecule, F.Denominator);
    F.Molecule /= GCD;
    F.Denominator /= GCD;
    return F;
}

Fraction add(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Denominator + F2.Molecule * F1.Denominator;
    temp.Denominator = F1.Denominator * F2.Denominator;
    return Reduction(temp);

}

Fraction sub(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Denominator - F2.Molecule * F1.Denominator;
    temp.Denominator = F1.Denominator * F2.Denominator;
    return Reduction(temp);
}

Fraction mul(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Molecule;
    temp.Denominator = F2.Denominator * F1.Denominator;;
    return Reduction(temp);
}

Fraction div(Fraction &F1, Fraction &F2) {
    Fraction temp;
    temp.Molecule = F1.Molecule * F2.Denominator;
    temp.Denominator = F1.Denominator * F2.Molecule;
    if(temp.Denominator<0){
        temp.Molecule = -temp.Molecule;
        temp.Denominator = -temp.Denominator;
    }
    return Reduction(temp);
}

void show(Fraction &F) {
    if (F.Denominator == 1)
        printf("%d", F.Molecule);
    else if (F.Denominator == 0)
        printf("ERROR");
    else
        printf("%d/%d\n", F.Molecule, F.Denominator);
}

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

本文为作者原创，仅供学习使用。如有错误可联系作者。联系方式QQ：1633497269