Разреженные матрицы Опции

[Camel_Toe]

Поможите кто может !!!! Препод задал такую задачу: разместить разреженную матрицу в динамической памяти с помощью линейных списков. Не могли бы вы мне сказать, что такое разреженная матрица и как ее разместить в динамической памяти. Если можно, то сразу на паскале . БУду очень признателен за любую помощь, так как сам я это сделать увы не смогу.

[GLuk]

Что такое динамическая память я ишшо может и знаю, а вот разреженная матрица... (есть лишь преположение, что это матрица которую разрядили  ;))??

[zx1024]

Версия:
Список из координат элемента матрицы и его значения.
Т.е. (x, y, info).
Т.к. матрица разреженная, не должно занимать много места.

[GLuk]

2zx1024 Может быть, но тогда получается, что понятие линейный список уже имеет место быть... а может это и нелинейный список.
А линейный список тогда получается что-то по типу:
A[1,1..X] - первый линейный список.
A[2,1..D] - второй линейный список.
A[3,1..F] - третий линейный список.
..................................................................

[Camel_Toe]

А как ее разместить в динамической памяти ??? Ну считал я с файла какието значения, а как их в динамическую память разместить???

[GLuk]

Попробуй что-то типа GetMem or New... до 64Кб в режиме 8086 проца

[Camel_Toe]

В продолжении темы. Препод задал такую задачу: найти след разреженной матрицы. След-сумма собственных чисел. Матрицу надо сделать насколько я понял, с использованием линейного списка, с размещением ее в динамической памяти. А как это сделать?? никто бы не мог привести код программы. Люди, помогите!!!!! Я проболел весь сентябрь, лекций нет, друзья помочь не могут(у них свои задачи). Я не поверю, что на сайте посвященном паскалю, не найдется ни одного хорошего(и очень доброго, понимающего) программиста, который не мог бы сделать эту задачу. Я буду очень благодарен.
ЗЫ: кстати этот сайт мне посоветовал мой друг, однажды кто то из форума ему очень помог, и он сдал паскаль на 5. Надеюсь, что этот ктото поможет и мне.

[Fire_Rage]

Если вы мне объясните, что такое разреженая матрица, то я смогу помочь.
Знаю, что такое динамичнская память.

[GLuk]

См. 3-4 пост сверху, больше вариантов на данный момент нет, во всяком случае у меня.
И, кстати, у препода нельзя спросить, что такое разреженные матрицы??

[Camel_Toe]

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

[Fire_Rage]

Ну тогда первая задача лёгкая.

Код

const n=1000;
type mass:[1..n,1..n]of integer;
      list:^node
      node:record
               k:integer;
               next:list;
              end;
var
mas:mass;
head:list;
i,g:integer;

begin
 new(head);
 head^.next:=nil;
 for i:=1 to n do
      for g:=1 to n do if mas[i,g]<>0
                                 then begin
                                          new(head^.next);
                                          head:=head^.next;
                                          head^.k:=mas[i,g];
                                          head^.next:=nil;
                                         end;
end.

Сообщение отредактировано: volvo - 17.12.2004 18:24

[Fire_Rage]

А след матрицы я думаю ты сам найдёш.(Я так и не понял- искать по списку или по матрице?)

[Nightmare]

> const n=1000;
> type mass:[1..n,1..n]of integer;
> var  
>  mas:mass;

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

[Camel_Toe]

Все значения ненулевых элементов и их "координаты" в матрице надо брать из внешнего файла.  Как я понял, сначала надо считать данные в некий массив, а потом с помощью указателей на его элементы найти сумму диаг.элементов исходной матрицы. Вот этото я и не понял как делать
2Fire-Rage: пасибки  за код, а можеш сделать чтоб из файла считывались значения ??

[Атавин Т. А.]

2zx1024 Может быть, но тогда получается, что понятие линейный список уже имеет место быть... а может это и нелинейный список.
А линейный список тогда получается что-то по типу:
A[1,1..X] - первый линейный список.
A[2,1..D] - второй линейный список.
A[3,1..F] - третий линейный список.
..................................................................

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

[Атавин Т. А.]

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

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

[volvo]

Атавин Т. А.,
очень мудрое решение, поднять тему, которой почти полтора года...