Матрицы со случайным расположением элементов
К данному типу относятся матрицы, у которых местоположение элементов со значениями, отличными от фонового, не могут быть математически описано, т. е. в их расположении нет какой-либо закономерности.
Пусть есть матрица А размерности 5x7, в которой из 35 элементов только 10 отличны от нуля:
Один из основных способов хранения подобных разреженных матриц заключается в запоминании ненулевых элементов в одномерном массиве записей с идентификацией каждого элемента массива индексами строки и столбца матрицы . Такой способ хранения называется последовательным представлением разреженных матриц. Однако последовательное представление разреженных матриц имеет определенные недостатки. Так, включение и исключение новых элементов матрицы вызывает необходимость перемещения большого числа существующих элементов.
Метод связанных структур переводит статическую структуру матрицы в динамическую. Эта динамическая структура реализована в виде циклических списков.
Циклический список представляет отдельную строку или столбец. Список столбца может содержать общие элементы с одним или более списком строки. Для того чтобы обеспечить использование более эффективных алгоритмов включения и исключения элементов, все списки строк и столбцов имеют головные элементы. Головной элемент каждого списка строки содержит ноль в поле Colum. Аналогично, каждый головной элемент в списке столбца имеет ноль в поле Row. Строка или столбец, содержащие только нулевые элементы, представлены головными вершинами, у которых поле Left или Up указывает само на себя.
|
|
|
ЛЕКЦИЯ 7. НОТАЦИИ АЛГЕБРАИЧЕСКИХ ВЫРАЖЕНИЙ, РЕАЛИЗАЦИ ПРЕОБРАЗОВАНИЙ И ВЫЧИСЛЕНИЙ.
Цель лекции
1.Ознакомить с формами нотаций.
2.Продемонстрировать пример использования стека.
Основные рассматриваемые вопросы:
инфиксная, префиксная, постфиксная формы записи, преобразования и вычисления.
Обычные арифметические выражения, используемые в повседневной практике и содержащие скобки называют инфиксными выражениями, поскольку знак операции располагается между операндами. Порядок выполнения действий в таких выражениях определяется старшинством опреаций и скобками. Вычисление и компиляция таких выражений подразумевает их предварительный анализ с целью выявления порядка выполнения операций. Существуют формы записи арифметических выражений без скобок, в которых порядок действий задается порядком знаков операций в выражении. Такие формы записи называются польской или бесскобочной записью. Польская запись может быть префиксной, в которой знак операции предшествует операндам, и постфиксной (обратная польская нотация ОПН), в которой знак операции следует за операндом. Вычисление и компиляция бесскобочных выражений оказывается проще, чем выражений со скобками, поскольку операции должны выполняться в порядке описания и предварительный анализ не требуется.
|
|
|
Например для выражений (a + b) * (c - d) префиксная форма будет выглядеть следующим образом *+ab-cd.
Вычисление можно представить следующим образом:
1. Просматриваем выражение слева направо, пока не найдем знак операции, за которым
следуют два операнда.
2. Выполняем операцию и результат записываем на место выбранной тройки.
3. Повторяем пункт (1), пока не получим вместо выражения один результат.
Постфиксная польская запись выражения заданного в инфексной форме
(a + b) * (c - d), будет выглядеть следующим образом ab+cd-* .
Рассмотрим вычисление выражения 7 2 3 * - (эквивалентное выражение в инфиксной нотации: 7-2*3). Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 - (результат умножения — 6, — заменяет тройку «2 3 *»). Второй знак операции — «-». Выполняется операция вычитания над операндами 7 и 6. Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.
|
|
|
Очевидное расширение обратной польской записи на унарные, тернарные и операции с любым другим количеством операндов: при использовании знаков таких операций в вычислении выражения операция применяется к соответствующему числу последних встретившихся операндов.
Особенности обратной польской записи следующие:
Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение 5 * (-3 + 8) использует знак «минус» как символ унарной операции (изменение знака числа), а выражение (10 - 15) * 3 применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись 5 3 - 8 + * (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала 5 - 3, затем 2 + 8, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его, либо ввести для операции изменения знака отдельное обозначение, например, «±»: 5 3 ± 8 + *.
|
|
|
Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение (10 - 15) * 3 в ОПН можно записать как 10 15 - 3 *, а можно — как 3 10 15 - *
Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.
Дата добавления: 2018-05-02; просмотров: 447; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!