🗊Презентация Вектор Айлиффа( Ilife)

Вектор Айлиффа (Iliffe)

Адресация элементов с помощью векторов Айлиффа (для массива А[2..4,-3..-1,0..1]) по строкам

Упражнение Вычислите количество указателей, требуемое для построения иерархии векторов Айлиффа для матрицы порядка n, с диапазоном индексов [l1,h1], [l2,h2], …, [ln,hn], с элементами, расположенными “по строкам”

// c l a s s "m a t r i x 3 l I l" // c l a s s "m a t r i x 3 l I l" template <class el> class matrix3lIl : public matrix3l<el> { protected: el*** va; // pointer to Iliffes vectors ierarhy public: matrix3lIl(int l1, int h1, int l2, int h2, int l3, int h3): matrix3l<el>(l1, h1, l2, h2, l3, h3) { int i1, i2 , d, step; d=-l3; step=h3-l3+1; va = new el**[h1-l1+1] - l1; for(i1=l1; i1<=h1; i1++) { *(va+i1) = new el*[h2-l2+1] - l2; for(i2=l2; i2<=h2; i2++, d+=step) *(*(va+i1)+i2)=V+d; } } matrix3lIl(char* file_name, int l1, int h1, int l2, int h2, int l3, int h3): matrix3l<el>(file_name, l1, h1, l2, h2, l3, h3) { int i1, i2 , d, step; d=-l3; step=h3-l3+1; va = new el**[h1-l1+1] - l1; for(i1=l1; i1<=h1; i1++) { *(va+i1) = new el*[h2-l2+1] - l2; for(i2=l2; i2<=h2; i2++, d+=step) *(*(va+i1)+i2)=V+d; } } el& elem(int i1, int i2, int i3) { nopadd+=3, nopmul+=0; return *(*(*(va+i1)+i2)+i3); }   };

Результат работы программы Matrix-vector A: 0. A 1. B 2. C 3. D 4. E 5. F 6. G 7. H 8. I 9. J 10. K 11. L 12. M 13. N 14. O 15. P 16. Q 17. R   End of vector. Press any key ... Matrix A i1=2 A B C D E F i1=3 G H I J K L i1=4 M N O P Q R   End of matrix. Press any key ... N op. +/- 54, N op. x/: 0

Упражнения Перегрузите в классе matrix3lIl operator []. Сравните время доступа к элементам матрицы с использованием определяющего вектора и методом Айлиффа.

Адресация элементов с помощью векторов Айлиффа (для массива А[2..4,-3..-1,0..1]) по столбцам

Упражнение Вычислите количество указателей, требуемое для построения иерархии векторов Айлиффа для матрицы порядка n, с диапазоном индексов [l1,h1], [l2,h2], …, [ln,hn], с элементами, расположенными “по строкам”.

// // // c l a s s "m a t r i x 3 c I l" // template <class el> class matrix3cIl : public matrix3c<el> { protected: el*** va; // pointer to Iliffes vectors ierarhy public: matrix3cIl(int l1, int h1, int l2, int h2, int l3, int h3): matrix3c<el>(l1, h1, l2, h2, l3, h3) { int i3, i2 , d, step; d=-l1; step=h1-l1+1; va = new el**[h3-l3+1] - l3; for(i3=l3; i3<=h3; i3++) { *(va+i3) = new el*[h2-l2+1] - l2; for(i2=l2; i2<=h2; i2++, d+=step) *(*(va+i3)+i2)=V+d; } } matrix3cIl(char* file_name, int l1, int h1, int l2, int h2, int l3, int h3): matrix3c<el>(file_name, l1, h1, l2, h2, l3, h3) { int i3, i2 , d, step; d=-l1; step=h1-l1+1;   va = new el**[h3-l3+1] - l3; for(i3=l3; i3<=h3; i3++) { *(va+i3) = new el*[h2-l2+1] - l2; for(i2=l2; i2<=h2; i2++, d+=step) *(*(va+i3)+i2)=V+d; } } el& elem(int i1, int i2, int i3) { nopadd+=3, nopmul+=0; return *(*(*(va+i3)+i2)+i1); } };

Результат работы программы Matrix-vector A: 0. A 1. B 2. C 3. D 4. E 5. F 6. G 7. H 8. I 9. J 10. K 11. L 12. M 13. N 14. O 15. P 16. Q 17. R   End of vector. Press any key ... Matrix A i3=0 A D G B E H C F I i3=1 J M P K N Q L O R End of matrix. Press any key ... N op. +/- 54, N op. x/: 0

Упражнение Перегрузите в классе matrix3cIl operator [].

Симметричные массивы Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n2, а лишь n*(n+1)/2 её элементов.

Для работы с симметричной матрицей разрабатываются следующие процедуры преобразования индексов матрицы в индекс вектора, формирования вектора и записи в него элементов верхнего треугольника элементов исходной матрицы, получения значения элемента матрицы из ее упакованного представления. При таком подходе обращение к элементам исходной матрицы выполняется опосредованно, через указанные функции.

Разреженные массивы Различают два типа разреженных массивов: массивы, в которых местоположения элементов со значениями отличными от фонового, могут быть математически описаны; массивы со случайным расположением элементов

Массивы с математическим описанием местоположения нефоновых элементов К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, могут быть математически описаны, т. е. в их расположении есть какая-либо закономерность. Элементы, значения которых являются фоновыми, называют нулевыми; элементы, значения которых отличны от фонового, - ненулевыми.

для работы с разреженным массивом разрабатываются функции: для преобразования индексов массива в индекс вектора; для получения значения элемента массива из ее упакованного представления по двум индексам (строка, столбец); для записи значения элемента массива в ее упакованное представление по двум индексам.

Пример Пусть имеется двумерная разреженная матрица, в которой все ненулевые элементы расположены в шахматном порядке, начиная со второго элемента. Для такой матрицы формула вычисления индекса элемента в линейном представлении будет следующей : L=((y-1)*XM+x)/2) где L - индекс в линейном представлении; x, y - соответственно строка и столбец в двумерном представлении; XM - количество элементов в строке исходной матрицы.

Разреженные массивы со случайным расположением элементов К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, не могут быть математически описаны, т. е. в их расположении нет какой-либо закономерности

Представление разреженным матриц методом последовательного размещения Пусть есть матрица А размерности 5*7, в которой из 35 элементов только 10 отличны от нуля 0 0 6 0 9 0 0 2 0 0 7 8 0 4 10 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 3 0 0 5

Представление разреженных матриц методом связанных структур Для представления разреженных матриц требуется базовая структура вершины (рис.3.6), называемая MATRIX_ELEMENT ("элемент матрицы"). Поля V, R и С каждой из этих вершин содержат соответственно значение, индексы строки и столбца элемента матрицы. Поля LEFT и UP являются указателями на следующий элемент для строки и столбца в циклическом списке, содержащем элементы матрицы. Поле LEFT указывает на вершину со следующим наименьшим номером строки.