// Two non-empty integer arrays are stored in files // "ina.txt" and "inb.txt". The program reads both // arrays from files, allocating memory in the heap. // Then the program sorts each array and calculates // a number of different elements in it, writing // different elements into the beginning of array // in ascending order. Finally, the program outputs // into the file "output.txt" those elements of // the first array that do not belong to the second. #include void sort(int *a, int n); bool inputArray(const char *fileName, int **a, int *n); int reduce(int *a, int n); int main() { int *a, *b; int n, m; if (!inputArray("ina.txt", &a, &n)) { return -1; } if (!inputArray("inb.txt", &b, &m)) { return -1; } if (n == 0 || m == 0) return -1; int n0 = reduce(a, n); // n0 is the number of different elements in a int m0 = reduce(b, m); // m0 is the number of different elements in b // Write to the file "output.txt" those elements of // the array a that do not belong to b FILE *out = fopen("output.txt", "w"); if (out == NULL) { perror("Could not open the output file"); return -1; } // fprintf(out, "%d %d\n", n0, m0); // Invariant: // a[i] > b[0], ..., b[k-1] && // a[i] <= b[k] int i = 0; int k = 0; // Ensure the implementation of invariant // before the main loop while (k < m0 && a[i] > a[k]) { ++k; } while (i < n0) { // Invariant: a[i] > b[k-1] && a[i] <= b[k] if (k >= m0 || a[i] < b[k]) { // The element a[i] does not belong to the array b fprintf(out, "%d ", a[i]); } ++i; if (i >= n0) break; // Ensure the implementation of invariant while (k < m0 && a[i] > b[k]) { ++k; } } fprintf(out, "\n"); fclose(out); // Release a memory delete[] a; delete[] b; return 0; } bool inputArray(const char *fileName, int **a, int *n) { FILE *f = fopen(fileName, "r"); if (f == NULL) return false; // Count the number of elements in the file int x; int m = 0; while (fscanf(f, "%d", &x) == 1) { ++m; } rewind(f); if (m == 0) { // Empty file fclose(f); return false; } // Allocate a memory for array int *arr = new int[m]; // Input elements for (int i = 0; i < m; ++i) { fscanf(f, "%d", arr + i); } fclose(f); *a = arr; *n = m; return true; } int reduce(int *a, int n) { if (n == 0) return 0; sort(a, n); int k = 1; // Number of different elements for (int i = 1; i < n; ++i) { // Invariant: // i >= k && // a[0] < a[1] < ... < a[k-1] if (a[i] > a[k-1]) { if (i != k) { a[k] = a[i]; } ++k; } } return k; } // Bubble Sort void sort(int *a, int n) { bool sorted = false; while (!sorted) { sorted = true; for (int i = 0; i < n-1; ++i) { if (a[i] > a[i+1]) { // Swap elements int tmp = a[i]; a[i] = a[i+1]; a[i+1] = tmp; sorted = false; } } } }