рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Образование
- /
- ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Реферат Курсовая Конспект
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР. - раздел Образование, СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Методы Последовательного Размещения Для Представления Разреженных Ма...
Методы последовательного размещения для представления разреженных
матриц обычно позволяют быстрее выполнять операции над матрицами
и более эффективно использовать память, чем методы со связанными
структурами. Однако последовательное представление матриц имеет
определенные недостатки. Так включение и исключение новых элемен-
тов матрицы вызывает необходимость перемещения большого числа
других элементов. Если включение новых элементов и их исключение
осуществляется часто, то должен быть выбран описываемый ниже ме-
тод связанных структур.
Метод связанных структур, однако, переводит представляемую
структуру данных в другой раздел классификации. При том, что ло-
гическая структура данных остается статической, физическая струк-
тура становится динамической.
┌───────┬───────┐ Для представления разреженных мат-
│ LEFT │ UP │ риц требуется базовая структура вершины
├────┬──┴──┬────┤ (рис.3.6), называемая MATRIX_ELEMENT
│ V │ R │ C │ ("элемент матрицы"). Поля V, R и С каж-
└────┴─────┴────┘ дой из этих вершин содержат соответс-
Рис.3.6. Формат вер- твенно значение, индексы строки и
шины для представле- столбца элемента матрицы. Поля LEFT и
ния разреженых матриц UP являются указателями на следующий
элемент для строки и столбца в циклическом списке, содержащем
элементы матрицы. Поле LEFT указывает на вершину со следующим на-
именьшим номером строки.
На рис. 3.7 приведена многосвязная структура, в которой ис-
пользуются вершины такого типа для представления матрицы А, опи-
санной ранее в данном пункте. Циклический список представляет все
строки и столбцы. Список столбца может содержать общие вершины с
одним списком строки или более. Для того, чтобы обеспечить ис-
пользование более эффективных алгоритмов включения и исключения
элементов, все списки строк и столбцов имеют головные вершины.
Головная вершина каждого списка строки содержит нуль в поле С;
аналогично каждая головная вершина в списке столбца имеет нуль в
┌───┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐ ┌──┬──┐
│ │ ─┼┐│ │ ┼┐│ │ ─┼┐│ │ ┼┐│ │ ┼┐│ │ ┼┐│ │ ┼┐
├──┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│├─┬┴┬─┤│
│ │0│ │││ │0│ │││ │0│ │││ │0│ │││ │0│ │││ │0│ │││ │0│ ││
└──┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│└─┴─┴┬┘│
┌───────────┼─┼─────┼─┼─────┼─┼─────┼─┼─────┼─┼─┐ │ │ │ │
┌┼─┬──┐ │ │ └─┘┌──┬─┼┐│ │ │┌──┬─┼┐│ │ └─┘ │ │
│ │ ├──────┼─┼────────┼─ │ ├┼─────┼─┼┼─ │ ├┼─┘ │ │
├─┬┴┬─┤ │ │ ├─┬┴┬─┤│ │ │├─┬┴┬─┤│ │ │
│ │ │0│ │ │ │6│1│5││ │ ││9│1│5││ │ │
└─┴─┴─┘ │ │ └─┴─┴┬┘│ │ │└─┴─┴┬┘│ │ │
┌───────────┼─┼─────────────┼─┼─────┼─┼─────┼─┼─────────────┼─┼┐
┌┼─┬──┐┌───┬─┼┐│ │ │┌──┬─┼┐│┌──┬─┼┐│ ┌──┬─┼┐││
│ │ ├┼─ │ ├┼─────────────┼─┼┼─ │ ├┼┼─ │ ├┼────────┼─ │ ├┼┘
├─┬┴┬─┤├──┬┴┬─┤│ │ │├─┬┴┬─┤│├─┬┴┬─┤│ ├─┬┴┬─┤│
│ │ │0││2 │2│1││ │ ││4│2│4│││8│2│5││ │4│2│7││
└─┴─┴─┘└──┴─┴┬┘│ │ │└─┴─┴┬┘│└─┴─┴┬┘│ └─┴─┴┬┘│
┌───────────┼─┼─┐ │ │ │ │ └─┘ │ │
┌┼─┬──┐┌───┬─┼┐│ │ │ │ │ │ │ │
│ │ ├┼─ │ ├┼─┘ │ │ │ │ │ │
├─┬┴┬─┤├──┬┴┬─┤│ │ │ │ │ │ │
│ │ │0││10│3│1││ │ │ │ │ │ │
└─┴─┴─┘└──┴─┴┬┘│ │ │ │ │ │ │
┌───────────┼─┼─────────────┼─┼─┐ │ │ │ │
┌┼─┬──┐ └─┘ ┌───┬─┼┐│ │ │ │ │ │
│ │ ├────────────────┼─ │ ├┼─┘ │ │ │ │
├─┬┴┬─┤ ├──┬┴┬─┤│ │ │ │ │
│ │ │0│ │12│4│3││ │ │ │ │
└─┴─┴─┘ └──┴─┴┬┘│ │ │ │ │
└─┘ │ │ │ │
┌───────────────────────────────────┼─┼─────────────────────┼─┼┐
┌┼─┬──┐ ┌──┬─┼┐│ ┌──┬─┼┐││
│ │ ├─────────────────────────┼─ │ ├┼────────────────┼─ │ ├┼┘
├─┬┴┬─┤ ├─┬┴┬─┤│ ├─┬┴┬─┤│
│ │ │0│ │3│5│4││ │5│5│7││
└─┴─┴─┘ └─┴─┴┬┘│ └─┴─┴┬┘│
└─┘ └─┘
Рис. 3.7. Многосвязная структура для представления матрицы A
поле R. Строка или столбец, содержащие только нулевые элементы,
представлены головными вершинами, у которых поле LEFT или UP ука-
зывает само на себя.
Может показаться странным, что указатели в этой многосвязной
структуре направлены вверх и влево, вследствие чего при сканиро-
вании циклического списка элементы матрицы встречаются в порядке
убывания номеров строк и столбцов. Такой метод представления ис-
пользуется для упрощения включения новых вершин в структуру.
Предполагается, что новые вершины, которые должны быть добавлены
к матрице, обычно располагаются в порядке убывания индексов строк
и индексов столбцов. Если это так, то новая вершина всегда добав-
ляется после головной и не требуется никакого просмотра списка.
– Конец работы –
Эта тема принадлежит разделу:
СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Массивы Логическая структура фиксированным набором элементов... Операции... Важнейшая операция физического уровня над массивом доступ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.021 сек.
Новости и инфо для студентов