Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Tattoquardas
0 / 0 / 0
Регистрация: 22.10.2011
Сообщений: 21
#1

Мультисписки - C++

14.10.2012, 13:11. Просмотров 977. Ответов 2
Метки нет (Все метки)

Подскажите пожалуйста, как представить разреженную матрицу в виде мультисписков. Хотя бы сам алгоритм.
Разряженная матрица - матрица, в которой нулевых эелементов больше, чем ненулевых.
Кака добавлять элементы в эту матрицу? Что делать с нулевыми?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
14.10.2012, 14:31     Мультисписки #2
(Легенда к той картинке матрицы внизу.)

Массивы слева и сверху — это массивы указателей на первые элементы. Слева — указатели на первые элементы (самые левые) строк. NULL, если строка пустая. Справа — первые элементы (самые верхние) столбцов. NULL, если столбец пустой. Справа и снизу они же (для удобства).

Голубые связи между элементами — ссылки на следующий в строке.

Красные связи между элементами — ссылки на следующий в стобце.

Зелёные связи между элементами и правым массивом — связи от последнего элемента в строке к соответствующему указателю на первый элемент в этой же строке.

Синие связи между элементами и нижним массивом — то же самое для столбцов.

Следовательно, каждая строка и каждый столбец образуют список-кольцо элементов, составляющих этот столбец или строку.

Вставка-удаление должны править оба кольца: для строки и для столбца. Для вставки надо найти две пары элементов: которые будут слева-справа от нового и сверху-снизу от него. И вставить элемент как в обычный список, но только в два сразу. Для удаления принципиально то же самое.

Чтобы выяснить индексы конкретного элемента, спускаемся вниз и вправо по красным и голубым ссылкам, пока не дойдём до тех индексных массивов. Можно индексы сразу хранить в элементе, а те зелёные и синие связи справа и снизу заменить на NULLы, чтобы не делать кольцо.
Миниатюры
Мультисписки  
Nick Alte
Эксперт С++
1628 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,931
Завершенные тесты: 1
14.10.2012, 14:32     Мультисписки #3
Нулевые элементы, очевидно, не хранить. Представить строку матрицы в виде списка пар "индекс элемента - значение". Хранить строки в виде списка, из которого исключены полностью нулевые строки, тоже в виде пар "номер строки - список элементов". Добавлять - найти в списке нужный номер строки, если нету - создать и вставить в список. В этот список аналогично занести элемент (или изменить, если такой там уже есть). Если заносимое значение 0, то наоборот - удалить элемент из списка, затем, если строка осталась пустой, и саму строку.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru