МАТРИЦЫ
Величина Dm:
Пример
Разреженный строчный формат
Сложение разреженных векторов с использованием расширенного вещественного накопителя
Сложение разреженных векторов с использованием расширенного вещественного накопителя
Сложение разреженных векторов с использованием расширенного целого массива указателей
Диагональная схема хранения ленточных матриц
Диагональная схема хранения ленточных матриц
Профильная схема хранения симметричных матриц
Профильная схема хранения симметричных матриц
Профильная схема хранения симметричных матриц
Связанные схемы разреженного хранения
Связанные схемы разреженного хранения
Связанные схемы разреженного хранения
Схема Ларкума для хранения симметричных матриц с ненулевыми диаг. элементами
Схема Ларкума для хранения симметричных матриц с ненулевыми диаг. элементами
ДАННЫЕ ДИНАМИЧЕСКОЙ СТРУКТУРЫ
Логическая структура стека
Схема физической структуры стека
Схема простейшей и кольцевой очереди
Схема физической структуры очереди
354.50K
Category: programmingprogramming

Матрицы. Логическая структура стека

1. МАТРИЦЫ

2.

Пусть задан произвольный n-мерный массив
B i1 : k1 , i2 : k2 , ..., in : kn
Адрес произвольного элемента:
B j1 , j2 , ..., jn
ADDR B j1, j2 , ..., jn ADDR B i1, i2 , ..., in
n
n
m 1
m 1
l * im Dm l * jm Dm

3. Величина Dm:

при отображении строками :
Dm km 1 im 1 1 * Dm 1 ,
m n 1,...,1 Dn 1,
при отображении столбцами :
Dm km 1 im 1 1 * Dm 1 ,
m 2,..., n D1 1.

4. Пример

А
MATR
ADDR(MATR(2,4,1))
ADDR(MATR(2,4,1))-102
3
2
4
1
3
6
5
l * i1D1 i2 D2 i3 D3
l1D1 , l2 D2 и i3 D3
30
10
2
INTEG
MATR(2:3,4:6,1:5)
2

5.

MATR(2:3,4:6,1:5)
Dm km 1 im 1 1 * Dm 1 , m n 1,...,1 Dn 1
D3=1
D2=(5-1+1)*1=5
D1=(6-4+1)*5=15
l * i1D1 i2 D2 i3 D3 102.
2*(2*15+4*5+1*1)

6.

Пусть начальный адрес массива MATR=1000.
Тогда его элемент с индексами 2, 5, 4 будет
располагаться по адресу :
ADDR(MATR(2,5,4))=ADDR(MATR(2,4,1))-
102+30*2+10*5+2*4=1000-102+118=1016.

7. Разреженный строчный формат

8. Сложение разреженных векторов с использованием расширенного вещественного накопителя

9. Сложение разреженных векторов с использованием расширенного вещественного накопителя

10. Сложение разреженных векторов с использованием расширенного целого массива указателей

Скалярное умножение двух разреженных векторов
с использованием массива указателей

11. Диагональная схема хранения ленточных матриц

Здесь - полуширина, а 2 +1 – ширина ленты.
Лентой матрицы А называется множество
элементов, для которых i-j .
Верхняя полулента состоит из элементов,
находящихся в верхней части ленты, т.е. таких, что
0<i-j ;
Массив имеет размеры n*( +1).

12. Диагональная схема хранения ленточных матриц

1
2
3
А
4
5
6
7
1 2 3 4
1 0 0 0
0 2 8 9
0 8 3 0
0 9 0 4
0 0 0 10
0 0 0 0
0 0 0 0
5 6 7
0 0 0
0 0 0
0 0 0
10 0 0 ;
5 11 12
11 6 0
12 0 7
0 0 1
0 0 2
0 8 3
AN I , J 9 0 4
0 10 5
0 11 6
12 0 7

13. Профильная схема хранения симметричных матриц

Для каждой строки i
симметричной
матрицы А
положим
i i jmin i
Схема Дженнингса
1
2
3
А
4
5
6
7
1 2 3 4
1 0 0 0
0 2 8 9
0 8 3 0
0 9 0 4
0 0 0 10
0 0 0 0
0 0 0 0
5 6 7
0 0 0
0 0 0
0 0 0
10 0 0
5 11 12
11 6 0
12 0 7

14. Профильная схема хранения симметричных матриц

Оболочка матрицы А – это множество элементов
, для которых
a ij
0 i j i
В строке i оболочке принадлежат все элементы со
столбцовыми индексами от j min i до i-1, всего i
элементов.
Диагональные элементы не входят в оболочку.
Профиль матрицы А определяется как число
элементов в оболочке:
profile A i
i

15. Профильная схема хранения симметричных матриц

Позиция
AN
IA
= 1 2 3 4 5 6 7 8 9 10 11 12 13 14
= 1 2 8 3 9 0 4 10 5 11 6 12 0 7
= 1 2 4 7 9 11 14
1
2
3
А
4
5
6
7
1 2 3 4
1 0 0 0
0 2 8 9
0 8 3 0
0 9 0 4
0 0 0 10
0 0 0 0
0 0 0 0
5 6 7
0 0 0
0 0 0
0 0 0
10 0 0
5 11 12
11 6 0
12 0 7

16. Связанные схемы разреженного хранения

17. Связанные схемы разреженного хранения

18. Связанные схемы разреженного хранения

19. Схема Ларкума для хранения симметричных матриц с ненулевыми диаг. элементами

А11
0
0
0
0
0
А22
0
0
0
А13
0
А33
0
0
А14
0
0
А44
0
0
А25
А35
0
А55

20. Схема Ларкума для хранения симметричных матриц с ненулевыми диаг. элементами

1.й вход
2.й вход
А11
А22
А13
Nil
Nil
А14
А 25
Nil
А 33
3.й вход
А 35
А44
4.й вход
5.й вход
0
А22
0
0
0
А13
0
А33
0
0
А14
0
0
А44
0
0
А25
А35
0
А55
Nil
Nil
Nil
Nil
Nil
А55
А11
0
0
0
0
Nil
Nil

21. ДАННЫЕ ДИНАМИЧЕСКОЙ СТРУКТУРЫ

Списком называется линейно-упорядоченная
последовательность элементов данных Е(1),
Е(2),..., Е(n)
последовательный список - последовательное
расположение элементов списка
динамически связанный список упорядоченность элементов задается с помощью
специальных указателей
Стек (список LIFO — Last In First Out)

22. Логическая структура стека

23. Схема физической структуры стека

24. Схема простейшей и кольцевой очереди

FIFO—First In First Out

25. Схема физической структуры очереди

English     Русский Rules