Форум программистов, компьютерный форум CyberForum.ru

Visual C++ (наработки есть очень большие) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Попрошайка
0 / 0 / 0
Регистрация: 11.05.2012
Сообщений: 18
06.09.2012, 19:33     Visual C++ (наработки есть очень большие) #1
Помогите за тестировать программы, пожалуйста.
Писал некоторые еще по весне, а большая часть написана на днях.
Мне просто интересно нет ли багов в программах, все компилится, но все же интересно узнать мнение более квалифицированных людей. В код добавил комменты для ясности.
Итак №1.(голова кипит уже, помогите вывести то, что записывается в память, после введения данных)
Условие: Разреженная матрица целых чисел представлена в виде виде упорядоченного (сначала по первому индексу, а затем по второму) списка (с двумя связями) триплетов. Найти минимальный по модулю элемент каждого столбца. Результат получить в виде вектора размером n.
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
#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
 
//струкутра списка
struct triplet
{
    int i;
    int j;
    int info;
    triplet *next;
};
 
//очистка списка
void Clear(triplet *list);
 
//вставка триплета (с учетом сортировки)
void Add(triplet *list, triplet *t);
 
void main()
{
    //русский язык консоли
    setlocale(LC_ALL,"Russian");
    
    //значение по умолчанию
    int defaultValue;
    cout<<"Введите элемент по умолчанию: ";
    cin>>defaultValue;
 
    //размер матрицы
    int m,n;
    cout<<"Введите количество строк матрицы: ";
    cin>>m;
    cout<<"Введите количество столбцов матрицы: ";
    cin>>n;
 
    //список триплетов
    triplet *list=new triplet;      //первый элемент не содержит значимой информации
    list->i=list->j=list->info=-1;  //используется как ссылка на список
    list->next=0;
    cout<<"Введите список триплетов. Для окончания ввода введите -1.\n";
 
    while (true)    //выход из цикла осуществляется в теле цикла
    {
        //ввод нового триплета
        triplet *t=new triplet;
 
        cin>>t->i;
        if (t->i==-1) break;    //конец ввода
 
        cin>>t->j;
        cin>>t->info;
        t->next=0;
 
        if (t->i>=m || t->j>=n) //индексация с 0
        {
            cout<<"Выход за границы матрицы. Триплет не был добавлен.\nПродолжите ввод.\n";
            delete t;   //так как триплет не добавлен, освобождаем память под него
        }
        else if (t->info == defaultValue)   //если значение - по умолчанию
        {
            cout<<"Введен триплет со значением по умолчанию, он не будет добавлен в список.\nПродолжите ввод.\n";
            delete t; //так как триплет не добавлен, освобождаем память под него
        }
        else
            Add(list,t);    //добавление триплета в список с учетов сортировки
    }
 
    //массив для минимальных элемент
    int *min=new int[n];
    //начальные значение - по умолчанию
    for (int i=0;i<n;i++)
        min[i]=abs(defaultValue);
 
    triplet *l; //для прохода по списку
 
    //поиск минимума
    l=list->next;
    while (l)       
    {
        if (min[l->j]>abs(l->info))
            min[l->j]=abs(l->info);
        l=l->next;
    }
 
    //вывод минимальных значений
    cout<<"\nМинимальные по модулю элементы в столбцах:\n";
    for (int i=0;i<n;i++)
        cout<<min[i]<<" ";
    cout<<endl;
 
    //удаление памяти,выделенной под список
    Clear(list);
    delete [] min;
 
    //задержка окна
    system("pause");
}
 
//вставка триплета
void Add(triplet *list, triplet *t)
{
    triplet *l=list;
    while (l->next && l->next->i<t->i) l=l->next;
    if (!l->next || l->next->i>t->i)    //конец списка или следующее i уже больше
    {
        t->next=l->next;
        l->next=t;
    }
    else
    {
        while(l->next && l->next->i==t->i && l->next->j<t->j) l=l->next;
        if (l->next && l->next->i==t->i && l->next->j==t->j)
        {
            cout<<"Ошибка добавления. Элемент ("<<t->i<<","<<t->j<<") уже существует и не был добавлен. Продолжите ввод.\n";
        }
        else
        {
            t->next=l->next;
            l->next=t;
        }
    }
}
 
//очистка списка
void Clear(triplet *list)
{
    triplet *l;
    while(list)
    {
        l=list;
        list=list->next;
        delete l;
    }
}

№2.(в принципе в работе уверен)
Условие: Два множества, элементами которого являются строчные буквы латинского алфавита, представлены с помощью стандартного типа SET. Найти декартово произведение этих множеств.
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
#include <cstdlib>
#include <iostream>
#include <set>
using namespace std;
 
const int size=26;
 
void main()
{
    setlocale(LC_ALL,"Russian");
 
    char *s1=new char[size+1];
    char *s2=new char[size+1];
 
    //ввод данных
 
    set <char> set1;
    set <char> set2;
 
    cout<<"Введите первый вектор (без пробелов)\n";
    cin>>s1;
    s1=strlwr(s1);
    for (int i=0;i<strlen(s1);i++)
        set1.insert(s1[i]);
 
    cout<<"Введите второй вектор (без пробелов):\n";
    cin>>s2;
    s2=strlwr(s2);
    for (int i=0;i<strlen(s2);i++)
        set2.insert(s2[i]);
 
    //вычисление декартового произведения
    set<char>::iterator i;  //итераторы для прохода по множествам
    set<char>::iterator j;
    for (i=set1.begin();i!=set1.end();++i)
        for (j=set2.begin();j!=set2.end();++j)
            cout<<"("<<*i<<","<<*j<<")\n";
 
    system("pause");
}
№3. (хоть убей не помню, алгоритм словесный, ну т.е, как происходит это преобразование, если возможно напомните, пожалуйста)
Условие: Изменить исходный способ хранения сильно ветвящегося дерева на заданный. Представление дерева на входе (из входного файла): имя вершины; ссылки на всех ее сыновей. Представление дерева на выходе: имя вершины; ссылки на левого сына, правого брата, отца.

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
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
 
//максимальное количество ветвей
const int maxChildCount=10;
 
//структура узла
struct node
{
    int info;
    int childCount; //количество детей
    int children[maxChildCount];    //дети
    node *next;
 
    node()
    {
        childCount=-1;
        next=0;
    }
};
 
//очистка списка
void Clear(node *list);
 
void main()
{
    setlocale(LC_ALL,"Russian");
 
    ifstream in("input.txt");
    if (in)
    {
        ofstream out("output.txt");
 
        //список вершин и считывание
        node *list=new node();  //первый элемент не имеет значения, используется как ссылка на список
        node *l=list;
 
        int max=0;
        //считывание
        while (!in.eof())
        {
            l->next=new node();
            l=l->next;
            //значение вершины
            in>>l->info;
            do
            {
                l->childCount++;
                in>>l->children[l->childCount];
            }
            while (l->children[l->childCount]!=0);
        }
 
        //обработка и вывод
        l=list->next;
        while(l)
        {
            out<<l->info<<" ";
            if (l->childCount>0)
                out<<l->children[0]<<" ";
            else out<<0<<" ";   //если потомков нет, выводим 0
            node *p=list;
            int i;
            bool found=false;   
            while (p->next && !found)
            {
                p=p->next;
                for (i=0;i<p->childCount && !found;i++)
                    if (p->children[i]==l->info)
                        found=true;
            }
            if (found)
                out<<p->children[i]<<" "<<p->info<<endl;
            else out<<"0 0"<<endl;  //если не нашли среди ничьих потомков
            l=l->next;
        }
 
        //очистка памяти
        Clear(list);
        in.close();
        out.close();
    }
    else cout<<"Ошибка открытия файла.\n";
 
    system("pause");
}
 
void Clear(node *list)
{
    node *l;
    while(list)
    {
        l=list;
        list=list->next;
        delete l;
    }
}
То что подается на вход:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 2 3 4 0
2 5 6 0
3 7 8 9 0
4 10 0
5 0
6 11 12 13 14 0
7 0
8 0
9 0
10 15 0
11 0
12 0
13 16 0
14 0
15 0
16 0
№4. (тоже уверен, но все равно посмотрите)
Условие:Формула, реализующая булеву функцию, задается (с клавиатуры или из текстового файла) символьным выражением с использованием связок полной системы:
! - отрицания и > - импликации.
4.1. Распознать символьную информацию, создав соответствующее данной формуле бинарное дерево.
4.2. Составить таблицу значений булевой функции.
4.3. Составить таблицу значений функции, являющейся отрицанием данной функции.

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
#include <cstdlib>
#include <iostream>;
#include <fstream>
using namespace std;
 
//узел дереваи дерево
struct node 
{
    char symbol;
    node *left, *right;
} *tree;
 
//вывод дерева на экран
void PrintTree (node *root, int r)
{
        if(root!=NULL)
        {
            PrintTree(root->right, r+2);
            for (int i=0; i < r ; i++)
                cout<<" ";
            cout<<root->symbol<<endl;
            PrintTree(root->left, r+2);
        }
}
 
//проверка скобок
bool check(char *c)
{
    int b=0;
    for (int i=0; i<strlen(c); i++)
        if (c[i]=='(') b++;
        else if (c[i]==')') b--;
    return b==0;    //при правильной расстановке скобок разница между их количествами = 0
}
 
//построение дерева по инфиксной форме записи
node *infix(char *c,int &ps)
{
    if (c[ps]=='\0') return 0;
    node *n=new node();
    if (c[ps]=='(')
    {
        ps++;
        //операция !
        if (c[ps]=='!')
            n->left=0;
        else    //переменная
            n->left=infix(c,ps);
        n->symbol=c[ps];    //операция
        ps++;
        n->right=infix(c,ps);   
        ps++;   //закрывающая скобка
    }
    else 
    {
        //переменная или константа
        n->symbol=c[ps];
        ps++;
        n->left=n->right=0;
    }
    return n;
}
 
//количество разных переменных в строке
int varCount(char *c)
{
    int res=0;
    for (int i=0;i<strlen(c)-1;i++)
    {
        if (c[i]>='a'&& c[i]<='z')
        {
            bool unique=true;
            for (int j=i+1;j<strlen(c) && unique;j++)
                if (c[i]==c[j]) unique=false;
            if (unique) res++;
        }
    }
    return res;
}
 
//возвращает массив переменных
char *var(char *c)
{
    int n=varCount(c)+1;
    char *x=new char[n];
    int k=0;
    for (int i=0;i<strlen(c)-1 && k<n;i++)
    {
        if (c[i]>='a' && c[i]<='z')
        {
            bool unique=true;
            for(int j=0;j<=k && unique;j++)
                if (c[i]==x[j]) unique=false;
            if (unique)
            {
                x[k]=c[i];
                k++;
            }
        }
    }
    x[k]='\0';
    return x;
}
 
//следующая строка переменнных
char *nextx(char *xValues)
{
    int n=strlen(xValues)-1;
    int i;
    for (i=n;i>0 && xValues[i]=='1';i--)
        xValues[i]='0';
    xValues[i]='1';
    xValues[n+1]='\0';
    return xValues;
}
 
//позиция символа в строке
int pos(char ch, char *c)
{
    int i;
    for (i=0;i<strlen(c) && c[i]!=ch;i++);
    return i;
}
 
//отрицание
char not(char a)
{
    if (a=='0') return '1';
    return '0';
}
 
//импликация
char imp(char a,char b)
{
    if (a=='0' || b=='1') return '1';
    return '0';
}
 
//вычисление значения функции при данном значении переменных
char f(node *n, char *x, char *xValues)
{
    char res;
    switch (n->symbol)
    {
    case '!':
        res=not(f(n->right,x,xValues));
        break;
    case '>':
        res=imp(f(n->left,x,xValues),f(n->right,x,xValues));
        break;
    case '1':
        res='1'; break;
    case '0':
        res='0'; break;
    default:
        res=xValues[pos(n->symbol,x)];
        break;
    }
    return res;
}
//количество строк в таблице
int rowCount(int n)
{
    int r=1;
    for (int k=0;k<n;k++)
        r*=2;
    return r;
}
 
//таблица истинности
char *buildTable(char *x)
{
    int n=strlen(x)+1;
    char *xValues=new char[n];
    for (int i=0;i<n;i++)
        xValues[i]='0';
    xValues[n-1]='\0';
    int rCount=rowCount(n-1);
    char *fValues=new char[rCount+1];
    for (int i=0;i<rCount;i++)
    {
        cout<<xValues<<"  ";
        fValues[i]=f(tree, x, xValues);
        cout<<fValues[i]<<endl;
        nextx(xValues);
    }
    fValues[rCount]='\0';
    return fValues;
}
 
//построение отрицания заданной функции
char *notf(char *fValues)
{
    int n=strlen(fValues);
    char *d=new char[n+1];
    //берем отрицания
    for (int i=0;i<n;i++)
        d[i]=not(fValues[i]);
    d[n]='\0';
    return d;
}
 
//удаление дерева
node *clearTree(node *n)
{
    if (n)
    {
        n->left=clearTree(n->left);
        n->right=clearTree(n->right);
        delete n;
    }
    return 0;
}
 
void main()
{
    //русский язык консоли
    setlocale(LC_ALL,"Russian");
    
    tree=0;
    ifstream in("формула.txt");
    char *c=new char[100];
    int ps=0;
    if (in)
    {
        //считывание формулы
        while (!in.eof() && ps<100)
        {
            in>>c[ps];
            ps++;
        }
        ps--;
        c[ps]='\0';
        cout<<"Исходное выражение: ";
        cout<<c<<endl;
        in.close();
        ps=0;
        if (check(c)) //если скобки расставлены верно
            //построение дерева
            tree=infix(c,ps);
    }
    else 
        cout<<"Файл не найден.\n";
 
    //если дерево построено
    if (tree)
    {
        cout<<"\nДерево:\n";
        PrintTree(tree,0);
        //переменные
        char *x=var(c);
        cout<<"\nТаблица истинности:\n";
        cout<<x<<"  "<<"f"<<endl;
        char *fValues=buildTable(x);
        char *notfValues=notf(fValues);
        cout<<"\nОтрицание даннной функции: ("<<notfValues<<')'<<endl;
 
        //освобождаем память
        clearTree(tree);
        delete [] x;
        delete [] fValues;
        delete []  notfValues;
    }
    else
        cout<<"Дерево не было построено.\n";
 
    cout<<endl;
    system("pause");
}
№5. (сложная задача, очень сомневаюсь)
Условие: Сравнить эффективность работы (по временному критерию) сортировок Шелла, слиянием, быстрой и древесной для числовых последовательностей с количеством элементов n=100, 1000, 10000, 100000, 1000000.

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
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <ctime>
using namespace std;
 
//структура дерева для древесной сортировки
struct node
{
    int info;
    node *left,*right;
    node()
    {
        left=right=0;
    };
};
 
//очистка дерева
void ClearTree(node *root, long &opCount);
 
//добавление в дерево
void AddToTree(node **root,int value,long &opCount);
 
//преобразование дерева обратно в массив
void TreeToArray(node *root,int ar[],int &index,long &opCount);
 
//вывод массива
void Print(ofstream&,int *ar, int size);
 
//копирование массива
int *copy(int *sourceArray,int size);
 
//сортировка Шелла
void ShellSort(int *ar,int size, long &opCount);
int increment(int inc[], int size,long &opCount);
 
//сортировка слиянием
void MergeSort(int *ar, int l,int r, long &opCount);
//слияние
void Merge(int *ar, int l,int r,int m,long &opCount);
 
//сортировка древесная
void TreeSort(int *ar, int size, long &opCount);
 
//быстрая сортировка
void QuickSort(int *ar,int first,int last, long &opCount);
 
void main()
{
    setlocale(LC_ALL,"Russian");
    ofstream out("output.txt");
    if (out)
    {
        ofstream out("output.txt");
        //размер и последовательность, ввод
        
        for (int size=100;size<=100000;size*=10)
        {
            //генерация массива
            int *sourceAr=new int[size];
            srand(time(NULL));
            for (int i=0;i<size;i++)
                sourceAr[i]=rand()%1000;
            cout<<"Размер массива: "<<size<<endl;
            out<<"Размер массива: "<<size<<endl;
            
            //время работы и количество операций
            clock_t start, finish;
            long opCount;
 
            //сортировки
 
            int *ar=copy(sourceAr,size);
            opCount=0;
            start=clock();
            ShellSort(ar,size,opCount);
            finish=clock();
            double time=(double)(finish-start)/CLOCKS_PER_SEC;
            cout<<"Сортировка Шелла: "<<time<<" "<<opCount<<endl;
            out<<"Сортировка Шелла: "<<time<<" "<<opCount<<endl;
            delete []ar;
 
            ar=copy(sourceAr,size);
            opCount=0;
            start=clock();
            MergeSort(ar,0,size-1,opCount);
            finish=clock();
            time=(double)(finish-start)/CLOCKS_PER_SEC;
            cout<<"Сортировка слиянием: "<<time<<" "<<opCount<<endl;
            out<<"Сортировка слиянием: "<<time<<" "<<opCount<<endl;
            delete []ar;
     
            ar=copy(sourceAr,size);
            opCount=0;
            start=clock();
            QuickSort(ar,0,size-1,opCount);
            finish=clock();
            time=(double)(finish-start)/CLOCKS_PER_SEC;
            cout<<"Сортировка быстрая: "<<time<<" "<<opCount<<endl;
            out<<"Сортировка быстрая: "<<time<<" "<<opCount<<endl;
            delete []ar;
             
            ar=copy(sourceAr,size);
            opCount=0;
            start=clock();
            TreeSort(ar,size,opCount);
            finish=clock();
            time=(double)(finish-start)/CLOCKS_PER_SEC;
            cout<<"Сортировка деревом: "<<time<<" "<<opCount<<endl;
            out<<"Сортировка деревом: "<<time<<" "<<opCount<<endl;
            delete []ar;
            
            cout<<endl;
            out<<endl;
            //очистка памяти исходного массива
            delete [] sourceAr;
        }
        
 
        out.close();
    }
    else
        printf("Ошибка открытия файла.\n");
    system("pause");
}
 
//сортировка древесная
void TreeSort(int *ar, int size, long &opCount)
{
    node *tree=0;
    for (int i=0;i<size;i++)
    {
        AddToTree(&tree,ar[i],opCount);
    }
    int index=0;
    TreeToArray(tree,ar,index,opCount);
    ClearTree(tree,opCount);
}
 
//преобразование дерева обратно в массив
void TreeToArray(node *root,int *ar,int &index,long &opCount)
{
    if (root==NULL) return;
    TreeToArray(root->left,ar,index,opCount);
    ar[index]=root->info;
    index++;
    opCount++;
    TreeToArray(root->right,ar,index,opCount);
}
 
//добавление в дерево
void AddToTree(node **root,int value, long &opCount)
{
    if (*root==NULL)
    {
        opCount++;
        *root=new node();
        (*root)->info=value;
        return;
    }
    if (value<(*root)->info)
        AddToTree(&(*root)->left,value,opCount);
    else
        AddToTree(&(*root)->right,value,opCount);
}
 
//очистка дерева
void ClearTree(node *root,long &opCount)
{
    opCount++;
    if (root)
    {
        ClearTree(root->left,opCount);
        ClearTree(root->right,opCount);
        delete root;
    }
}
 
//слияние
void Merge(int *ar, int l,int r,int m,long &opCount)
{
    if(l >= r || m < l || m > r) 
        return;
    
    if(r == l + 1 && ar[l] > ar[r])
    {
        int t=ar[l];
        ar[l]=ar[r];
        ar[r]=t;
        opCount+=3;
        return;
    }
 
 
    int size=r+1-l+1;
    int *tmp=new int[size];
    for (int i=0;i<size;i++)
    {
        tmp[i]=ar[l+i];
        opCount++;
    }
 
    for(size_t i = l, j = 0, k = m - l + 1; i <= r; i++)
    {
        opCount++;
        if(j > m - l)      ar[i] = tmp[k++];
        else if(k > r - l) ar[i] = tmp[j++];
        else               ar[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
    }
}
 
//сортировка слиянием
void MergeSort(int *ar, int l,int r, long &opCount)
{
    //! Условие выхода из рекурсии
    if(l >= r) return;
 
    int m = (l + r) / 2;
 
    opCount++;
 
    //! Рекурсивная сортировка полученных массивов
    MergeSort(ar, l, m,opCount);
    MergeSort(ar, m+1, r,opCount);
    Merge(ar, l, r, m,opCount);
}
 
//быстрая сортировка
void QuickSort(int *ar,int first,int last, long &opCount)
{
    int i = first;
    int j = last;
    int x = ar[(first + last) / 2];
 
    do 
    {
        while (ar[i] < x) 
        {
            i++;
            opCount++;
        }
        while (ar[j] > x) 
        {
            j--;
            opCount++;
        }
 
        if(i <= j) 
        {
            if (i < j) 
            {
                opCount+=3;
                int temp=ar[i];
                ar[i]=ar[j];
                ar[j]=temp;
            }
            i++;
            j--;
        }
    } while (i <= j);
 
    if (i < last)
        QuickSort(ar, i, last,opCount);
    if (first < j)
        QuickSort(ar,first,j,opCount);
}
 
//копирование массива
int *copy(int *sourceArray,int size)
{
    int *newAr=new int[size];
    for (int i=0;i<size;i++)
        newAr[i]=sourceArray[i];
    return newAr;
}
 
//вывод массива на экран и в консоль
void Print(ofstream &out,int *ar, int size)
{
    for (int i=0;i<size;i++)
    {
        cout<<ar[i]<<" ";
        out<<ar[i]<<" ";
    }
    cout<<endl;
    out<<endl;
}
 
//для сортировки Шелла
int increment(int inc[], int size, long &opCount)
{
    // inc[] - массив размера size, в который заносятся инкременты
    int p1, p2,p3, s;
    p1=1;
    p2=1;
    p3=1;
    s=-1;
    do  //заполняем массив по формуле Роберта Седжвика
    {
        opCount++;
        s++;
        if (s%2)
            inc[s]=8*p1-6*p2+1;
        else
        {
            inc[s]=9*p1-9*p3+1;
            p2*=2;
            p3*=2;
        }
        p1*=2;
    //заполняем массив, пока текущая инкремента хоят бы в 3 раза меньше количестваэлементов в массиве
    }while (3*inc[s]<size);
 
    //возвращаем количество элементов в массиве
    if (s>0) return s-1;
    return 0;
}
 
//сортировка Шелла
void ShellSort(int *ar,int size, long &opCount)
{
   // inc инкремент, расстояние между элементами сравнения
    // i и j стандартные переменные цикла
    // seq[40] массив, в котором хранятся инкременты
    int inc, i, j;
    int seq[1000];
    int s;//количество элементов в массиве seq[]
 
    // вычисление последовательности приращений
    s = increment(seq, size,opCount);
    
    while (s >= 0) 
    {
        //извлекаем из массива очередную инкременту
        inc = seq[s];
        // сортировка вставками с инкрементами inc
        for (i = inc; i < size; i++) 
        {
            int temp;
            temp=ar[i];
            // сдвигаем элементы до тех пор, пока не дойдем до конца или не упорядочим в нужном порядке
            for (j = i-inc; (j >= 0) && (ar[j]>temp); j -= inc)
            {
                opCount++;
                ar[j+inc]=ar[j];
            }
            // после всех сдвигов ставим на место j+inc элемент, который находился на i месте
            ar[j+inc]=temp;
        }
        s--;
    }
}
№6. (тоже сложная задача)
Условие: Прочитать исходные данные из входного текстового файла. Представив эти данные в виде массива записей с тремя полями, поочередно отсортировать массив по каждому из полей. Вывести отсортированные данные в выходной текстовый файл.
Набор данных “Обои” содержит для каждого вида обоев: серийный номер (целое значение), фоновый цвет (10 символов), вид рисунка (10 символов).
Использовать метод сортировки со средней сложностью не более O(n log(n)).

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
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
 
//структура записи
struct wallpaper
{
    int number;
    char color[10];
    char type[10];
};
 
//перестройка дерева
int AddToTree(wallpaper *ar, int k,int size,int);
 
//сортировка
void HeapSort(wallpaper *ar, int size,int);
 
//сравнение двух записей по ключу
int compare(wallpaper a,wallpaper,int);
 
//вывод на экран и в файл
void Print(wallpaper*,int,ofstream&);
 
void main()
{
    setlocale(LC_ALL,"Russian");
 
    ifstream in("input.txt");
    if (in)
    {
        //массив записей
        int size;
        in>>size;
        wallpaper *ar=new wallpaper[size];
        for(int i=0;i<size;i++)
        {
            in>>ar[i].number>>ar[i].color>>ar[i].type;
        }
        
        ofstream out("output.txt");
 
        //сортировка по серийному номеру
        HeapSort(ar,size,0);
        
        cout<<"Сортировка по серийному номеру:\n";
        out<<"Сортировка по серийному номеру:\n";
        Print(ar,size,out);
 
        //сортировка по фоновому цвету
        HeapSort(ar,size,1);
        cout<<"Сортировка по фоновому цвету:\n";
        out<<"Сортировка по фоновому цвету:\n";
        Print(ar,size,out);
 
        //сортировка по виду рисунка
        HeapSort(ar,size,2);
        cout<<"Сортировка по виду рисунка:\n";
        out<<"Сортировка по виду рисунка:\n";
        Print(ar,size,out);
 
        //освобождение памяти
        delete [] ar;
 
        //закрытие файла
        in.close();
        out.close();
    }
    else 
        cout<<"Ошбика открытия файла.\n";
 
    system("pause");
}
 
//вывод на экран и в файл
void Print(wallpaper* ar,int size,ofstream &out)
{
    for (int i=0;i<size;i++)
        {
            cout<<ar[i].number<<" "<<ar[i].color<<" "<<ar[i].type<<endl;
            out<<ar[i].number<<" "<<ar[i].color<<" "<<ar[i].type<<endl;
        }
    cout<<endl;
    out<<endl;
}
 
 
//сортировка
void HeapSort(wallpaper *ar, int size, int key)
{
    wallpaper wp;
 
    //строим дерево
    for (int i=size/2-1;i>=0;i--)
    {
        int previ=i;
        i=AddToTree(ar,i,size,key);
        if (previ!=i)
            i++;
    }
 
    //непосредственно сортировка
    for (int len=size-1;len>0;len--)
    {
        //меняем первый элемент с последним
        wp.number=ar[len].number;
        strcpy(wp.color,ar[len].color);
        strcpy(wp.type,ar[len].type);
 
        ar[len].number=ar[0].number;
        strcpy(ar[len].color,ar[0].color);
        strcpy(ar[len].type,ar[0].type);
 
        ar[0].number=wp.number;
        strcpy(ar[0].color,wp.color);
        strcpy(ar[0].type,wp.type);
 
        int i=0;
        int previ=-1;
        while(i!=previ)
        {
            previ=i;
            //перестраиваем дерево
            i=AddToTree(ar,i,len,key);
        }
    }
}
 
 
//сравнение двух налогов
int compare(wallpaper a,wallpaper b,int key)
{
    if (key==0)
    {
        if (a.number>b.number) return 1;
        if(a.number<b.number) return -1;
        return 0;
    }
 
    if (key==1)
    {
        if (strcmp(a.color,b.color)<0) return -1;
        if (strcmp(a.color,b.color)>0) return 1;
        return 0;
    }
 
    if (strcmp(a.type,b.type)<0) return -1;
    if (strcmp(a.type,b.type)>0) return 1;
    return 0;
}
 
//перестройка дерева
int AddToTree(wallpaper *ar, int k,int size,int key)
{
    if (2*k+1>=size)
        return k;
 
    int kmax=2*k+2;
 
    if (kmax<size)
    {
        if(compare(ar[kmax],ar[kmax-1],key)==-1)
            kmax--;
    }
    else
        kmax=2*k+1;
 
    if (compare(ar[k],ar[kmax],key)==-1)
    {
        wallpaper wp;
        wp.number=ar[k].number;
        strcpy(wp.color,ar[k].color);
        strcpy(wp.type,ar[k].type);
 
        ar[k].number=ar[kmax].number;
        strcpy(ar[k].color,ar[kmax].color);
        strcpy(ar[k].type,ar[kmax].type);
        
        ar[kmax].number=wp.number;
        strcpy(ar[kmax].color,wp.color);
        strcpy(ar[kmax].type,wp.type);
 
        if (kmax<size/2)
            return kmax;
        else return k;
    }
    return k;   
}
То что подается на вход:
C++
1
2
3
4
5
6
7
8
7
4 black photo
1 green flowered
6 blue plane
5 yellow plane
3 green strip
2 darkblue geometric
7 red flowered
№7.(уверен, но все равно посмотрите, пожалуйста)
Условие: . Используя те же записи, что и в задаче 6 (до сортировки!!!), организовать их в виде дерева поиска. В качестве ключа использовать значение первого поля. Перестроить дерево поиска, произведя последовательно следующие операции:
• добавив новую запись,
• удалив запись из корня.

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
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
 
//структура записи
struct wallpaper
{
    int number;
    char color[10];
    char type[10];
};
 
//структура дерева
struct Node
{
    wallpaper info;
    Node *left, *right;
};
 
//добавление в дерево
void Add(wallpaper, Node **);
 
//удаление из дерева
bool Delete(int,Node**);
 
//очистка дерева
void Clear(Node *);
 
//вспомогательная для удаления
void Changer(Node **, Node **);
 
//вывод дерева на экран
void PrintTree(Node *,int);
 
void main()
{
    setlocale(LC_ALL,"Russian");
 
    ifstream in("input.txt");
    if (in)
    {
        //дерево
        Node *Tree=0;
 
        //ввод, создание и добавление узлов в дерево
        int size;   //количество записей
        in>>size;
        for (int i=0;i<size;i++)
        {
            wallpaper wp;
            in>>wp.number>>wp.color>>wp.type;
            Add(wp,&Tree);
        }
 
        cout<<"Исходное дерево:\n\n";       
        PrintTree(Tree,0);
        cout<<endl;
 
        //добавление элемента
        wallpaper wp;
        cout<<"Введите информацию для добавления:\n";
        cout<<"Серийный номер: ";
        cin>>wp.number;
        cout<<"Фоновый цвет: ";
        cin>>wp.color;
        cout<<"Вид рисунка: ";
        cin>>wp.type;
        Add(wp,&Tree);
        cout<<"Измененное дерево:\n\n";
        PrintTree(Tree,0);
        cout<<endl;
        
        cout<<endl;
        //удаление элемента
        int number;
        cout<<"Введите серийный для удаления: ";
        cin>>number;
        cout<<"Измененное дерево:\n\n";
        Delete(number,&(Tree));
        PrintTree(Tree,0);
        cout<<endl;
 
        //очистка памяти
        Clear(Tree);
 
        //закрытие файла
        in.close();
    }
    else 
        cout<<"Ошбика открытия файла.\n";
 
    system("pause");
}
 
//добавление в дерево
void Add(wallpaper info, Node **root)
{
    if (*root!=0)
        if ((*root)->info.number>info.number)
            Add(info,&(*root)->left);
        else 
            Add(info,&(*root)->right);
    else
        {
            *root=new Node();
            (*root)->info.number=info.number;
            strcpy((*root)->info.color,info.color);
            strcpy((*root)->info.type,info.type);
            (*root)->left=0;
            (*root)->right=0;
        }
}
 
//очистка дерева
void Clear(Node *root)
{
    if (root)
    {
        Clear(root->left);
        Clear(root->right);
        delete root;
    }
}
 
//удаление из дерева
bool Delete(int number,Node** root)
{
    bool res=0;
    if (*root!=0)
    {
        if (number<(*root)->info.number)
            res=Delete(number,&(*root)->left);
        else if (number>(*root)->info.number)
            res=Delete(number,&(*root)->right);
        else
        {
            Node *buf=*root;
            if (buf->right==0)
                *root=buf->left;
            else if (buf->left==0)
                *root=buf->right;
            else Changer(&(*root)->left,&buf);
            delete buf;
            res=1;
        }
    }
    return res;
}
 
//вспомогательная для удаления
void Changer(Node **root, Node **buf)
{
    if ((*root)->right!=0)
        Changer(&(*root)->right,&(*buf));
    else 
    {
        strcpy((*buf)->info.type,(*root)->info.type);
        strcpy((*buf)->info.color,(*root)->info.color);
        (*buf)->info.number=(*root)->info.number;
        *buf=*root;
        *root=(*root)->left;
    }
}
 
void PrintTree (Node *tree, int r)
{
        if(tree!=NULL)
        {
            PrintTree(tree->right, r+3);
            for (int i=0; i < r ; i++)
                cout<<" ";
            cout<<tree->info.number<<endl;
            PrintTree(tree->left, r+3);
        }
}
Скоро на сдачу идти, вот и прошу форумчан посмотреть мои программы..)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2012, 19:33     Visual C++ (наработки есть очень большие)
Посмотрите здесь:

Печатает очень большие числа в колонке "Y"" C++
Ввести с клавиатуры 10 чисел. Если среди них есть числа большие 15, заменить их на 15. Напечатать все полученные числа. C++
Возможно ли как-то в Visual Studio 2010 проверять есть ли утечки памяти? Может есть какие-то специальные плагины для этого? C++
Просьба к тем, у кого есть visual c++ 2012 C++
C++ Ввести с клавиатуры 10 чисел. Если среди них есть числа, большие 15, заменить их на 15. Напечатать все полученные числа
C++ Есть очень много маленьких текстовых файлов необходимо слить в один файл
Очень большие числа: узнать, есть ли остаток от деления одного числа на другое C++
C++ Есть ли разница между Visual C++, Borland C++ и C++ Builder?

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
06.09.2012, 19:58     Visual C++ (наработки есть очень большие)
  #2

Не по теме:

Посмотрел все семь эпизодов. Грим и игра актёров хорошая, но в сюжет и задумку сценариста вникнуть не получилось, слишком длинно и нужно. Комментарии режиссёра тоже не особо помогли, но скрасили просмотр этой многосерийной драмы. К сожалению, бонуса с неудачными дублями показано не было. В принципе, на один раз посмотреть можно, но в личную коллекуию такое не стал бы записывать.

Yandex
Объявления
06.09.2012, 19:58     Visual C++ (наработки есть очень большие)
Ответ Создать тему
Опции темы

Текущее время: 23:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru