7. Список используемой литературы
1. Колинько П. Г. Алгоритмы и структуры данных. Часть 1: Пособие к самостоятельной работе и курсовому проектированию. Вып. 2003 (для заочников). –– СПб., 2020. — Error: Reference source not found с.
8. Приложение
#include <iostream>
#include <string>
using namespace std;
struct List {
List() { }
char d;
List * next;
List(char d, List *next = nullptr) : d(d), next(next) { }
};
int const ARRAY_MEMORY = 10; // c запасом
int const U = 10;
int const LOOP_COUNT = 6;
List* listOptions (List *a, List *b, int type) {
List* tmp = NULL;
List* start = NULL;
List* last = NULL;
List* tmp_b = b;
int k;
while(a != NULL) {
for (b = tmp_b, k = 0; b != NULL; b = b->next) {
if(a->d == b->d ) {
k = 1;
break;
}
}
if (type == 0) {
if (k == 0) {
tmp = new List;
tmp->next = NULL;
tmp->d = a->d;
if (!start) start = tmp;
if (last) last->next = tmp;
last = tmp;
}
} else {
if (k != 0) {
tmp = new List;
tmp->next = NULL;
tmp->d = a->d;
if (!start) start = tmp;
if (last) last->next = tmp;
last = tmp;
}
}
a = a->next;
}
return start;
}
List* listClear (List * x) {
List* t;
while( x != NULL ) {
t = x;
x = x->next;
delete t;
}
return NULL;
}
List* listResult (List* a, List* b, List* c, List* d) {
List* tmp1 = listOptions(b ,c , 1);
List* tmp2 = listOptions(a, tmp1, 0);
List* tmp3 = listOptions(tmp2, d, 0);
listClear(tmp1);
listClear(tmp2);
return tmp3;
}
int main () {
srand(static_cast<unsigned int>(time(nullptr)));
char A[ARRAY_MEMORY] = { NULL },
B[ARRAY_MEMORY] = { NULL },
C[ARRAY_MEMORY] = { NULL },
D[ARRAY_MEMORY] = { NULL },
E[ARRAY_MEMORY];
int wordsA,
wordsB,
wordsC,
wordsD,
wordsE = 0,
bytesA[U] = { 0 },
bytesB[U] = { 0 },
bytesC[U] = { 0 },
bytesD[U] = { 0 },
bytesE[U];
List *listA = nullptr,
*listB = nullptr,
*listC = nullptr,
*listD = nullptr,
*listE = nullptr;
// cout << endl << "Введите множества..." << endl;
char universum[] = {'0','1','2','3','4','5','6','7','8','9'};
// cout << "A = ";
// cin >> A;
for (int i = 0; i < LOOP_COUNT; i++) A[i] = universum[rand() % U];
// cout << "B = ";
//cin >> B;
for (int i = 0; i < LOOP_COUNT; i++) B[i] = universum[rand() % U];
// cout << "C = ";
//cin >> C;
for (int i = 0; i < LOOP_COUNT; i++) C[i] = universum[rand() % U];
// cout << "D = ";
//cin >> D;
for (int i = 0; i < LOOP_COUNT; i++) D[i] = universum[rand() % U];
//Преобразование строки символов в список
for (int i = 0; A[i]; ++i) {
List *e = new List(A[i], listA);
listA = e;
}
for (int i = 0; B[i]; ++i) {
List *e = new List(B[i], listB);
listB = e;
}
for (int i = 0; C[i]; ++i) {
List *e = new List(C[i], listC);
listC = e;
}
for (int i = 0; D[i]; ++i) {
List *e = new List(D[i], listD);
listD = e;
}
//Преобразование строк символов в массивы битов и машинные слова
wordsA = 0;
for (int i = 0; A[i]; ++i) {
bytesA[A[i] - '0'] = 1;
wordsA |= (1 << (A[i] - '0'));
}
wordsB = 0;
for (int i = 0; B[i]; ++i) {
bytesB[B[i] - '0'] = 1;
wordsB |= (1 << (B[i] - '0'));
}
wordsC = 0;
for (int i = 0; C[i]; ++i) {
bytesC[C[i] - '0'] = 1;
wordsC |= (1 << (C[i] - '0'));
}
wordsD = 0;
for (int i = 0; D[i]; ++i) {
bytesD[D[i] - '0'] = 1;
wordsD |= (1 << (D[i] - '0'));
}
//Операция с массивами
clock_t ta1 = clock();
int i = 0, j = 0, k = 0, n = 0;
char uBC[ARRAY_MEMORY], uAD[ARRAY_MEMORY];
const long RepeatA = 10000;
for (int cnt = 0; cnt < RepeatA; ++cnt) {
while (B[i] != '\0') {
for (k = 0, j = 0; C[j] != '\0'; j++) {
if (B[i] == C[j]) uBC[n++] = B[i];
}
i++;
}
uBC[n] = '\0';
for (i = 0, n = 0; A[i] != '\0'; i++) {
for (k = 0, j = 0; D[j] != '\0'; j++) {
if (A[i] == D[j]) k = 1;
}
if (!k) uAD[n++] = A[i];
}
uAD[n] = '\0';
for (i = 0, n = 0; uAD[i] != '\0'; i++) {
for (k = 0, j = 0; uBC[j] != '\0'; j++) {
if (uAD[i] == uBC[j]) k = 1;
}
if (!k) E[n++] = uAD[i];
}
E[n] = '\0';
}
clock_t ta2 = clock();
//Операция над списками
const long RepeatB = 1000;
clock_t tb1 = clock();
for (int cnt = 0; cnt < RepeatB; ++cnt) {
listClear(listE);
listE = listResult(listA, listB, listC, listD);
}
clock_t tb2 = clock();
//Операция над массивами битов:
const long RepeatC = 100000; //Добавляем нули, пока время не станет заметным (> секунды)
clock_t tc1 = clock();
for (int cnt = 0; cnt < RepeatC; ++cnt) {
for (i = 0; i<10; i++) bytesE[i] = (bytesA[i] && !( bytesB[i] && bytesC[i] ) && !bytesD[i]);
}
clock_t tc2 = clock();
//То же - для машинных слов
const long RepeatD = 1000000; //Добавляем нули, пока время не станет заметным (> секунды)
clock_t td1 = clock();
for (long cnt = 0; cnt < RepeatD; ++cnt) {
wordsE = wordsA & ((wordsB & wordsC) ^ 0xFFFF) & (wordsD ^ 0xFFFF);
}
clock_t td2 = clock();
// Вывод
cout << endl << "Введены множества: A = " << A
<< endl << " B = " << B
<< endl << " C = " << C
<< endl << " D = " << D;
cout << endl << "Массивы : E = " << E << " (t = " << (ta2 - ta1) << ")";
cout << endl << endl << " listA = ";
for (List * v = listA; v; v = v->next) cout << v->d;
cout << endl << " listB = ";
for (List * v = listB; v; v = v->next) cout << v->d;
cout << endl << " listC = ";
for (List * v = listC; v; v = v->next) cout << v->d;
cout << endl << " listD = ";
for (List * v = listD; v; v = v->next) cout << v->d;
cout << endl << "Списки : listE = ";
for (List * v = listE; v; v = v->next) cout << v->d;
cout << " (t=" << (tb2 - tb1) << ")";
cout << endl << endl << " bytesA = ";
for (int i =LOOP_COUNT - 1; i >= 0; --i) {
if (bytesA[i]) cout << char(i + '0');
else cout << "-";
}
cout << endl << " bytesB = ";
for (int i = LOOP_COUNT - 1; i >= 0; --i) {
if (bytesB[i]) cout << char(i + '0');
else cout << "-";
}
cout << endl << " bytesC = ";
for (int i = LOOP_COUNT - 1; i >= 0; --i) {
if (bytesC[i]) cout << char(i + '0');
else cout << "-";
}
cout << endl << " bytesD = ";
for (int i = LOOP_COUNT - 1; i >= 0; --i) {
if (bytesD[i]) cout << char(i + '0');
else cout << "-";
}
cout << endl << endl << "Биты : bytesE = ";
for (int i = LOOP_COUNT - 1; i >= 0; --i) {
if (bytesE[i]) cout << char(i + '0');
else cout << "-";
}
cout << " (t = " << (tc2 - tc1) << ")";
cout << endl << endl << "Слова : wordsE = ";
for (int i = LOOP_COUNT - 1; i >= 0; --i) {
if (wordsE&(1 << i)) cout << char(i + '0');
else cout << "-";
}
cout << " (t = " << (td2 - td1) << ")" << endl << endl;
return 0;
}