Выбор структуры хранения полинома

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

При выполнении работы можно использовать следующее понимание полинома. Полином состоит из мономов. Каждый моном характеризуется коэффициентом Coef и степенями переменных A, B, C: Coef*x^Ay^Bz^C. Величину степеней переменных можно ограничить значением 9. При таком предположении максимально возможное количество мономов в полиноме - 1000. Полином разрежен, если по сравнению с максимально возможным количеством мономов он имеет относительно небольшое количество отличных от нуля коэффициентов. Например, у полинома P(x,y,z) отличных от нуля коэффициентов всего 4.

При манипуляции разреженными полиномами эффективной структурой хранения являются списки. При этом каждое звено списка хранит моном с отличным от нуля коэффициентом.

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

В результате операций (например, сложения) может быть получен полином, у которого нет отличных от нуля коэффициентов. Структура хранения такого нулевого полинома не должна отличаться от структуры хранения прочих полиномов.

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

Таким образом, с учетом вышеизложенного, рекомендуется следующая структура хранения полиномов. Полиномы упорядочиваются по убыванию степеней мономов. Для определения старшинства мономов вводится следующее правило. Во-первых, фиксируется старшинство переменных. Будем считать, что x - самая старшая переменная, затем следует y, затем z. Для каждого монома определим его "свернутую степень" (индекс). Для монома x^Ay^Bz^C. индекс равен A*10²+B*10¹+C*10⁰ (по условию задачи A, B и C не выше 9). Старшим считается моном с большей свернутой степенью. Например, x³y старше xy⁷z⁶, так как 310 больше 176.

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

Структура хранения нулевого полинома

Примеры структур хранения полиномов

первое звено списка. Первым звеном списка является так называемое "головное " звено (голова списка), поле свернутой степени которого равно -1. Нулевой полином представляется только головой списка.

Структуры хранения полиномов P(x,y,z), Q(x,y,z) и их суммы показаны на рисунке.