Файл: Садовников, В. И. Потоки информации в системах управления.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.10.2024

Просмотров: 70

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

П р и л о ж е н и е 1

Упорядочение данных методом сортировки

по основанию системы счисления

В настоящем приложении рассматривается метод сортировки по основанию системы счисления [Л. 48, 103], который применяется для упорядочения наименований СК, записанных на ОИЯ искусственного уровня (например, § 3-8). Возможен случай, когда наименование компоненты (код компоненты) занимает несколько ячеек памяти. В результате сортировки коды упорядочиваются по величине. Сор­ тировка может производиться как по всей длине кода, так и по выделенной группе старших разрядов. Для этого с каждым кодом массива, подлежащего сортировке, задаются две константы: п, и I}. Константа п, задает общую длину кода kj, константа /,• определяет число старших разрядов кода, по которым выполняется сортировка. Под kj здесь будем понимать не только код компоненты на ОИЯ искусственного уровня, но и ту информацию, которую может нести с собой данная компонента, например код документа, в котором она записывается, порядковый номер этой компоненты внутри докумен­ та и др. Сортировка производится по основанию 8. В оперативной памяти отводится 8 групп (карманов) ячеек. На внешнем ЗУ также отводится 8 карманов магнитной ленты (МЛ), причем каждая лен­ та-карман делится на два участка. Запись рассортированных компо­ нент производится попеременно на первый и второй участок лентыкармана. Например, при сортировке по нечетным разрядам запись ведется на первый участок, а при сортировке по четным разрядам — на второй.

В каждом коде исходного массива выделяется младший вось­ меричный разряд, подлежащий сортировке. В зависимости от вели­ чины разряда весь код компоненты вместе с относящейся к нему информацией записывается в соответствующий карман в МОЗУ. После того как все коды распределены по карманам МЛ, произво­ дится сортировка содержимого каждого кармана по следующему разряду и т. д.

Перед сортировкой очередного /-го кода по г разряду проверя­ ется соотношение r>lj. Если это соотношение выполняется, то /-й код записывается в массив, отведенный для записи отсортированных кодов, и в последующей сортировке не участвует.

В, зависимости от дальнейшего использования отсортированные коды могут быть записаны одним из двух рассмотренных ниже способов.

Пусть исходная информация, подлежащая сортировке, представ­ лена табл. П1-І. В ячейке, предшествующей каждому коду kj, запи­ сываются константы П] и Ц. Сортировка выполняется по части кода,

обозначенной qj. Оставшаяся часть кода, по которой сортировка не производится, обозначена через г,-. В табл. П1-1 первый и четвертый,

 

 

Т а б л и ц а П1-1

п,

Л

 

042

222

201

204

 

 

205

207

000

 

о,

N,

п2

it

 

021

223

 

212

216

220

 

D,

/V,

«3

и

 

021

223

 

217

230

231

 

Оз

Л^з

П і

и

 

042

222

201

204

 

 

210

211

216

 

о *

ЛГ*

 

 

Т а б л и ц а П1-2

021

223

 

212

216

220

 

о 2

 

021

223

 

217

230

231

229

 

 

П р о д о л ж гн и п т а б л . П 12

 

D3

Кг

 

 

1

042

222

201

204

 

 

205

207

000

 

Dy

Ку

 

 

1

042

222

201

204

 

 

210

211

216

 

D4

к ,

 

 

1

 

 

Т а б л и ц а П1-3

021

223

 

212

216

220

 

0 ,

N„

217

230

231

 

D3

Na

 

 

1

042

222

201

204

 

 

205

207

000

 

Dy

Ky

210

211

216

 

Dy

Ky

 

 

1

•/40

второй и третий коды имеют равные qj. При записи первым спосо­ бом все четыре кода, упорядоченные по qj, запишутся полностью (табл. П1-2). Коды отделяются признаком і. При записи вторым спо­ собом равные </Д</і = <к; дг—</з) запишутся по одному разу, за ними запишутся соответственно значения гі и /ч; гг и г3 (табл. П1-3). Группы кодов с разными значениями qj отделяются признаком I.

Форма записи отсортированных кодов задается некоторой кон­ стантой. Если константа равна 1, то коды записываются по форме табл. 1-2, если константа равна 0 — по форме табл. Ш-3.

Приложение 2

Формирование стандартных таблиц методом слияния массивов

В данном приложении рассматривается метод сортировки, кото­

рый можно применить для

формирования стандартных таблиц

с использованием данных

некоторых других таблиц (например,

§ 3-4).

Информация, содержащаяся в таблицах в зависимости от их использования записывается группами кодов по п ячеек. Например, в табл. 3-18 информация записана группами по 3 ячейки: оператор, документ, компонента; в табл. 3-12, 3-14, 3-20, 3-22 — по две ячейки, в табл. 3-16 — по одной ячейке. Сортировка информации выполняет­ ся по содержимому первой ячейки каждой группы.

Процесс сортировки делится на два последовательных этапа

[Л. 48, 104].

1. Сортировка данных внутри каждого массива. Для этого в опе­ ративную память последовательно массивами по т чисел вызывается сортируемая таблица. Каждый массив упорядочивается последова­ тельным сравнением кодов и записывается на внешний накопитель на прежнее место.

2. Слияние массивов в один упорядоченный список слов. Для

этого

в

оперативную

память

в ячейки

(гінач,

dBS,ч + т) и

( Ь нач,

Ьнач+ т )

последовательно

парами массивов вызывается сор­

тируемая

таблица. Параллельным сравнением начальных кодов

в группах

ячеек из 1-го и 2-го массивов выявляется меньший код и

вместе

со

своей

группой записывается в

рабочий массив (сНач>

Спйч+ т). Такая операция повторяется до тех пор,

пока

1 и 2-й мас­

сивы не просмотрятся

полностью.

Массивы

(сНач,

сИач+ /п) записы­

ваются на рабочую МЛ. После просмотра всей исходной таблицы она запишется на рабочей ленте группами массивов. Каждая группа состоит из двух массивов длиной по т ячеек и представляет собой один упорядоченный список слов. Далее за исходную таблицу при­ нимается таблица, записанная на рабочей МЛ и процесс слияния повторяется. Сливаются попарно группы массивов. Для этого в опе­ ративную память вызываются первые массивы из каждой группы сливающихся массивов. Если в результате сравнения кодов из обеих массивов окажется, что один из массивов просмотрен полностью, на его место вызывается следующий массив из той же группы масси­ вов и т. д. После каждого слияния число массивов в группе удваи­ вается. В результате последнего слияния получается одна группа массивов — один упорядоченный список слов. При последнем слиянии

231

Смотрите также файлы