Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
#1

Реализация расширенного класса Integer - C++

08.08.2012, 15:49. Просмотров 658. Ответов 9
Метки нет (Все метки)

Всем привет. Хочу реализовать аналог класса Integer в котором можно буде проводить операции с числами любой разрядности. Начал пока с написания функции сложения и вычитания.
Возникли вопросы:
1)Можно ли числа хранить в строках?
2)В моей программе происходит ошибка в функции ReadStr(), когда происходит перевыделение памяти 2 раз. С перегрузкой оператор new пока незнаком и пытаюсь сделать перевыделение вручную. Почему может возникать эта ошибка? Как этого избежать?
3)Может кто-нибудь посмотреть насколько корректно реализованы функции Add (сложение чисел) и Sub (вычитание чисел). Может быть где-то что-то в этих функциях и вообще в программе следует сделать как-то иначе.
За любые комментарии буду благодарен.
Вот код (если что-то непонятно, спрашивайте) :

C++
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
#include <iostream>
#include <conio.h>
using namespace std;
 
int MAX_NUMBER = 10;    
int MIN_NUMBER = 0;
 
//убирает лишние нули впереди строки
char * DeleteNull(char *str);
 
//возвращает минимальную из строк
char *MinStr(char *str1, char *str2);
 
//возвращает максимальную из строк
char *MaxStr(char *str1, char *str2);
 
//Проверка знака числа-строки
bool Sgn(char *str);
 
//изменить знак числа-строки
char * ChangeSgn(char *str);
 
//считывает строку
void ReadStr(char *str);
 
//обращение строки
void RevStr(char *str);
 
//Выравнивание строки нулями
void ExpStr(char *str, int exp);
 
//Проверка является ли символ числом от 0 до 9
bool isNumber(char ch);
 
//преобразовнаие 1 char в int
int CharToInt(char ch);
 
//сумма 2 символов чисел с учётом переноса разряда
bool SumChar(char ch1,char ch2,char &result, bool flag);
 
//разность 2 символов с учётом переноса разряда
bool SubChar(char ch1,char ch2,char &result, bool flag);
 
//Сумма чисел-строк
char * Add(const char *num1,const char *num2);
 
//Разность чисел-строк
char *Sub(const char *num1,const char *num2);
 
void main(){
    char *str1 = new char[80]; 
    char *str2 = new char[80];
 
    for(;;){
        system("cls");
    
    cout << "str2: ";
    ReadStr(str2);
    
    cout << str2;
    
    getch();
    }
}
 
//*************************************************
//реализация функций
 
void RevStr(char *str){
    char *start = &str[0];
    
    char *end = &str[strlen (str)-1];
    char t;
 
    while(end > start){
        t = *start;
        *start = *end;
        *end = t;
        end--; start++;
    }
}
 
void ExpStr(char *str, int exp){
    int i = strlen(str);
 
    if(!Sgn(str)){
        ExpStr(str+1,exp);
    }else{
        RevStr(str);
        
        while(strlen(str) != exp){
            str[i++] = '0';
            str[i] = 0;
        }
        RevStr(str);
    }
}
 
bool Sgn(char *str){
    if(*str == '-') return false;
    return true;
}
 
bool isNumber(char ch){
    if(ch >= '0' && ch <= '9') return true;
    return false;
}
 
int CharToInt(char ch){
    if(isNumber(ch)) return ch-'0';
    return -1;
}
 
bool SumChar(char ch1,char ch2,char &result, bool flag){
    int i = (flag)? CharToInt(ch1) + CharToInt(ch2) + 1:
        CharToInt(ch1) + CharToInt(ch2);
 
    if(i < MAX_NUMBER){
        result = i + '0';
        return false;
    }else{
        result = (i % 10) +'0';
        return true;
    }
}
 
char *MinStr(char *str1, char *str2){
    if(strlen(str1) > strlen(str2)) return str2;
    else if(strlen(str1) < strlen(str2)) return str1;
    else return 0;
}
 
char *MaxStr(char *str1, char *str2){
    if(strlen(str1) > strlen(str2)) return str1;
    else if(strlen(str1) < strlen(str2)) return str2;
    else return 0;
}
 
char * Add(const char *str1, const char *str2){
    char *num1 = new char[strlen(str1)+1];
    char *num2 = new char[strlen(str2)+1];
 
    
    strcpy(num1,str1);
    strcpy(num2,str2);
 
    bool flag = false;
    bool sgn1 = Sgn(num1);
    bool sgn2 = Sgn(num2);
 
    if(!sgn1 && sgn2){  
        num1++;
        return DeleteNull(Sub(num2,num1));
    }else if(sgn1 && !sgn2){
        num2++;
        return DeleteNull(Sub(num1,num2));
    }else if(!sgn1 && !sgn2) {
        num1++;
        num2++;
        return DeleteNull(ChangeSgn(Add(num1,num2)));
    }
    
    if(MinStr(num1,num2))
        ExpStr(MinStr(num1,num2),strlen(MaxStr(num1,num2)));
    ExpStr(num1,strlen(num1)+1);
    ExpStr(num2,strlen(num2)+1);
        
    int i;
    char *result = new char[strlen(num1) + 1];
        
    RevStr(num1);
    RevStr(num2);
 
    for(i=0; i < strlen(num1); i++)
        flag = SumChar(num1[i],num2[i],result[i],flag);
 
    result[i] = 0;
    RevStr(result);
    
    DeleteNull(result);
    
    return result;
}
 
bool SubChar(char ch1,char ch2,char &result, bool flag){
    int i = (flag)? CharToInt(ch1) - CharToInt(ch2) -1:
        CharToInt(ch1) - CharToInt(ch2);
 
        if(i < MIN_NUMBER){
        result = MAX_NUMBER + i + '0';
        return true;
    }else{
        result = i +'0';
        return false;
    }
}
 
char * Sub(const char *str1,const char *str2){
    char *num1 = new char[strlen(str1)+1];
    char *num2 = new char[strlen(str2)+1];
    strcpy(num1,str1);
    strcpy(num2,str2);
 
    bool sgn1= Sgn(num1);
    bool sgn2 = Sgn(num2);
    bool flag = false;
    bool flag_max;
 
    if(!sgn1  && sgn2){
        num1++;
        return DeleteNull(ChangeSgn(Add(num2,num1)));
    }else if(sgn1 && !sgn2){
        num2++;
        return DeleteNull(Add(num1,num2));
    }else if(!sgn1 && !sgn2){
        num1++;
        num2++;
        return DeleteNull(Sub(num2,num1));
    }
    
    if(MinStr(num1,num2))
        ExpStr(MinStr(num1,num2),strlen(MaxStr(num1,num2)));
 
    flag_max = (*num1 >= *num2)? true:false;
    
    int i;
    char *result = new char[strlen(num1) + 1];
    
    RevStr(num1);
    RevStr(num2);
 
    if(flag_max){
        for(i=0; i < strlen(num1); i++)
            flag = SubChar(num1[i],num2[i],result[i],flag);
    }else{
        for(i=0; i < strlen(num1); i++)
            flag = SubChar(num2[i],num1[i],result[i],flag);
        result[i++] = '-';
    }
    
    result[i] = 0;
    RevStr(result);
    
    DeleteNull(result);
    
    return result;
}
 
 
 
char * ChangeSgn(char *str){
    char *result = new char[strlen(str) + 2];
 
    if(Sgn(str)){
        result[0] = '-';
        result[1] = 0;
        strcat(result,str); 
 
 
        return result;
    }
    else
        return str + 1;
}
 
 
char * DeleteNull(char *str){
    int i;
    char *result = new char[strlen(str) + 2];
    
    i=0;
 
    if(!Sgn(str)){
        i++;
        strcpy(result,"-");
    }
 
    while(str[i] == '0' && strlen(str + i) > 1)
        i++;
    
    if(!Sgn(str))
        strcpy(result + 1, str+i);
    else
        strcpy(result,str+i);
    strcpy(str,result);
    return str;
}
 
void ReadStr(char *result){
    
    int max_size = 10;
    char ch;
    int memory_size = 0;
 
    delete []result;
    result = new char[max_size + 1]; 
 
    while((ch = getchar())!='\n'){
        result[memory_size] = ch;
        
        memory_size++;
        if(memory_size == max_size){
            char *new_str = new char[memory_size];
            strcpy(new_str,result);
            
            delete []result;
            
            max_size*=2;
            result= new char[max_size];
            strcpy(result,new_str);
        }
 
    }
 
    result[memory_size] = 0;
}
Добавлено через 1 минуту
Вот ещё вопрос (не по теме): если, какая-то функция довольно громоздкая и её можно разбить на подфункцию, стоит ли делать такое разбиение, если подфункций может получится много?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.08.2012, 15:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация расширенного класса Integer (C++):

Реализация классов integer, double - C++
Есть задания реализовать класс integer,double,char производные от абстрактного класса Number. Определить между этими классами все...

Реализация класса на базе класса Stack с возможностью !индексирования! - C++
Помогите пожалуйста!!! Нужно реализовать на базе класса stack другой класс с возможностью индексирования, а именно: Например 1 - й...

Реализовать методы класса Sint (secure integer) - C++
Доброго времени суток всем. Задание такое: Реализовать методы класса Sint (secure integer). Класс должен представлять все возможности...

Реализация класса - C++
Помогите понять пожалуйста. Пример из Дейтела: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &quot;GradeBook.h&quot; using namespace...

реализация класса - C++
Дано: класс &quot;Фильмы&quot; (название, жанр, главные роли). Вопрос: Возможно ли такой подход к реализации? class films { string...

Реализация класса - C++
Спроектировать и реализовать класс BigInt, позволяющий хранить целые числа в диапазоне , и производить набор основных операций с ними. ...

9
ValeryS
Модератор
6709 / 5118 / 482
Регистрация: 14.02.2011
Сообщений: 17,206
08.08.2012, 15:52 #2
Цитата Сообщение от bgm313 Посмотреть сообщение
Хочу реализовать аналог класса Integer в котором можно буде проводить операции с числами любой разрядности.
прямо уж любой у строк тоже есть ограничения
сделай массив int-ов или char-ов
можно выделять динамически
0
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
08.08.2012, 16:00  [ТС] #3
Цитата Сообщение от ValeryS Посмотреть сообщение
прямо уж любой у строк тоже есть ограничения
сделай массив int-ов или char-ов
можно выделять динамически
Ну хорошо пускай это будут числа разрядностью не более 10000 символов. Я думаю что в куче для них местечко найдётся, но память должна выделять по мере необходимости. У мнея кака-то ошибка в функции Read()
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.08.2012, 17:06 #4
Цитата Сообщение от bgm313 Посмотреть сообщение
Можно ли числа хранить в строках?
Можно, но тратить по байту на цифру не айс. Эффективнее всего запихивать по девять десятичных цифр в один int (или 18, если система 64-битная) и хранить число как массив таких интов.

Цитата Сообщение от bgm313 Посмотреть сообщение
2)В моей программе происходит ошибка в функции ReadStr(), когда происходит перевыделение памяти 2 раз. С перегрузкой оператор new пока незнаком и пытаюсь сделать перевыделение вручную. Почему может возникать эта ошибка? Как этого избежать?
Откройте для себя std::string, считывайте числа в неё, а потом преобразуйте в свой формат из готовой string с известной длиной и т. п.

Цитата Сообщение от bgm313 Посмотреть сообщение
Вот ещё вопрос (не по теме): если, какая-то функция довольно громоздкая и её можно разбить на подфункцию, стоит ли делать такое разбиение, если подфункций может получится много?
Много легко читаемых функций всяко лучше одной функции, в которой много строчек.
1
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
08.08.2012, 17:46  [ТС] #5
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Можно, но тратить по байту на цифру не айс. Эффективнее всего запихивать по девять десятичных цифр в один int (или 18, если система 64-битная) и хранить число как массив таких интов.

Если число хранить как вы предлагаете, то как проводить операции над большими числами, например если требуется сложить 2 числа:9999999999999999999999999999999999999999999999999999999999999999
и 77777777777777777777777777888888888888888811111111
сначала надо числа выровнять (дополнить нулями).
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.08.2012, 18:12 #6
Естественно. С представлением в виде символов придётся делать то же самое.

Числа представляется как
[9 999999999 999999999 999999999 999999999 999999999 999999999 999999999]
[77777 777777777 777777777 777888888 888888888 811111111]
Потом выполняется анализ длин чисел старших "цифр" на предмет переноса. Тут его не будет, так что достаточно столько же "цифр", сколько в большем числе (восемь). Резервируем это место:
[0, 0, 0, 0, 0, 0, 0, 0]
И складываем:
[0, 0, 0, 0, 0, 0, 0, 999999999 + 811111111] => [0, 0, 0, 0, 0, 0, 1, 811111110]
[0, 0, 0, 0, 0, 0, 1 + 999999999 + 888888888, 811111110] => [0, 0, 0, 0, 0, 1, 888888888, 811111110]
И так далее.
1
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
08.08.2012, 19:06  [ТС] #7
Вот смотрите, начал писать заново класс integer. Использую ваши рекомендации по хранению числа:
Вот так нормально будет или нет:

C++
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
#include <iostream>
using namespace std;
 
//перевод строки в число
int StrToInt(char *str,int len){
    if(len == 0 && len > 8) len = 8;
    
    int i = 0;
    int result = 0;
    
    while(str[i] && i < len){
        result *= 10;
        result += (str[i] - '0');
        i++;
    }
    
    return result;
}
 
class Integer{
    static const int amount = 8;     //количество цифр в массиве
    int *val;                        //здесь храним число
public:
    Integer(char *str);              //конструктор с инициализацией числа
};
 
Integer::Integer(char *str){
    int size = strlen(str) / 8 + 1;  //опеределим сколько блоков цифр требуется
    
    val = new int[size];             //выделим требуемыую память под блоки цифр
 
    
    int i, start;
    
    //записываем число
    for(i=0, start = 0; i < size; start+=8, i++){
        val [i]=StrToInt(str + start,amount);
    }
}
 
void main(){
 
    Integer("123456789987654312123");
}
Добавлено через 2 минуты
Может быть делать блоки побольше, чем 8 цифр?

Добавлено через 2 минуты
9 цифр достаточно будет.

Добавлено через 10 минут
Вот появился вопрос: если хранить число в массиве типа int, то для сложения чисел число надо записать в строку и далее выполнить операцию суммы?

Добавлено через 51 секунду
С суммой то, всё просто, а вот операция умножения?
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.08.2012, 19:35 #8
Для сложения вы их складываете поциферно, с переносами, как обычно. Соль в том, что цифры у вас теперь не от 0 до 9, а от 0 до 999999999.

Умножение — попробуйте сначала простое умножение в столбик по типу:
Код
       1  2  3
       4  5  6
--------------- 
 0  0  6 12 18  (1*6  2*6  3*6)
 0  5 10 15  0  (1*5  2*5  3*5  << 1)
 4  8 12  0  0  (1*4  2*4  3*4  << 2)
---------------
 0  0  7  3  8  (выполняем переносы)
 0  6  1  5  0
 4  9  2  0  0
---------------
 4 15 10  8  8  (складываем столбики)
---------------
 5  6  0  8  8  (и ещё раз переносы)
1
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
08.08.2012, 19:51  [ТС] #9
Как вы думаете может быть числа лучше взять в диапазоне от 0 до 99999999 (8 цифр), а оставшиеся 2 места использовать в качестве флага переноса?
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.08.2012, 20:14 #10
А в том и штука: 999 999 999 + 999 999 999 = 1 999 999 998. 1 999 999 998 прекрасно влазит в int, потому и можно девять цифр брать. Флагом переноса работает условие (число >= 1000000000), если надо перенос, ты мы вычитаем миллиард и добавляем единицу в следующий разряд.

Для умножения инта, естессно, не хватит. Надо long, только он способен вместить 999 999 999 * 999 999 999 = 999 999 998 000 000 001 < 2^60.
0
08.08.2012, 20:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.08.2012, 20:14
Привет! Вот еще темы с ответами:

Реализация класса - C++
Так как только начал изучать с++, возникает вопрос: есть задание : Реализовать класс IntArray. Разработать тестовую программу для...

Реализация класса и вектор - C++
Всем привет! test.cpp(главный файл) /* * @pay - зарплата сотрудника * @countEl - позиция элемента в контейнере */ #include...

Реализация класса стека - C++
Приветствую! Пробую написать класс стека, но работает не совсем так, как задумывалось. Что-то не так с получением значения // Êëàññ...

Реализация класса Directory - C++
Информационная запись о файле в каталоге содержит поля: имя файла, расширение, дата и время создания, атрибуты &quot;только чтение&quot;, &quot;скрытый&quot;,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru