Лабник по СПО
.pdf
Каждый поток должен выводить на экран исходные и перемещённые элементы, цвет перемещённых элементов должен отличаться от цвета исходных элементов. Кнопка Закрасить должна выдать команду на перекрашивание тех линий, которые уже отсортированы.
Если при действующих потоках создать ещё новые потоки, то их будет сложно ликвидировать, поэтому перед новым запуском потоков нужно убедиться, что потоки не действуют.
В схеме программы введён блок 3, проверяющий, действуют потоки или нет. Для
исключения нового запуска потоков при наличии действующего потока после нажатия кнопок Пуск или Продолжить, свойству Enabled кнопок Пуск и Продолжить необходимо присвоить значение False и восстановить значение Enabled только после окончания сортировки во всех потоках, или после нажатия кнопки Стоп. Схема потока быстрой сортировки (поток 1) показана на рис.10.5.
1
Начало
2
Ввод границ Nн:=Nэн; Nк:=Nэк;
3 Расчёт
Mid:=Эл[(Nн+Nк)/2]
4
Цикл Mid
|
6 |
|
|
|
|
? |
|
|
|
5 |
|
||
|
Inc(Nн) |
Да |
Эл[Nн]<Mid |
|||
|
|
|
||||
|
|
|
Нет |
|
||
|
|
|
|
|
||
|
8 |
|
|
|
|
? |
|
|
|
7 |
|
||
|
Dec(Nк) |
Да |
Эл[Nк]>Mid |
|||
|
|
|
Нет |
|||
|
|
|
|
|||
|
|
|
|
|
|
|
|
? |
Да |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
11 |
|
|
|
|
|
|
|
|
|
||||||||
9 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
н < Nк |
|
|
|
|
Bp:=Эл[Nн] |
|
|
|
|
Эл[Nн]:=Эл[Nк] |
|
|||||||||||||||||
|
|
|
|
N |
|
|
|
||||||||||||||||||||||||||
|
|
|
|
Нет |
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Эл[Nк]:=Bp |
|
|||||||||
|
|
|
15 |
|
|
? |
Да |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
Останов |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
Нет |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рисование |
|
|
|
||||||
16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
||||||||
|
|
|
Цикл Mid |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
Nн:>=Nк |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Inc(Nн) |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dec(Nr) |
|
|||||
|
|
18 |
|
|
|
|
|
|
|
|
|
? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
Ввод границ |
|
|
17 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
Nк > Nэн |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
Nн:=Nэн; |
Да |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
Нет |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Конец |
|
|||
|
|
20 |
|
|
|
|
|
|
19 |
|
|
? |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
Ввод границ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
Nн < Nэк |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
Nк:=Nэк; |
Да |
|
|
Нет |
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
Рис.10.5. Схема потока 1 (быстрая сортировка)
221
PDF created with pdfFactory Pro trial version www.pdffactory.com
Схема потока сортировки вставкой (потока 2) показана на рис.10.6. Схема потока сортировки по весу (потока 3) показана на рис.10.7.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
Начало |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
Цикл |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
3 |
Цикл |
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
по I = 1 g Nэ |
||||||||
|
|
|
по J = Nэ g I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
4 |
|
? |
|
Нет |
|
|
|
|
10 |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
Эл[I]>Эл[J] |
|
|
|
|
|
|
|
Цикл |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|
по J = Nэ g I |
||||||
|
|
|
|
|
|
|
|
|
Да |
|
|
|
|
9 |
|
|||||||||
|
5 |
|
|
|
|
|
|
|
|
? |
|
|
|
|
|
|
J = I |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Останов |
|
|
|
|
|
|
||||
|
|
|
|
|
|
Вр:=Эл[J] |
|
|
|
11 |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
Да |
|
|
Цикл |
||||||||||
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
по I = 1 g Nэ |
|||||||
|
|
|
Эл[J]:=Эл[I] |
|
|
|
8 |
|
|
|
|
|
|
|
|
I = Nэ |
||||||||
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
Рисование |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
Эл[I]:=Вр |
|
|
|
|
|
12 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Конец |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Рис.10.6. Схема потока 2 (сортировка вставками)
1
Начало
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
Цикл |
|||||||
|
|
2 |
Цикл |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
по J = (Nэ–1) g I |
|||||||||||||
|
|
по I = 1 g Nэ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
4 |
|
? |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Эл[J]>Эл[J–1] |
|||||||||||||
|
10 |
|
|
|
|
|
|
|
9 |
Нет |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
Цикл |
|
? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Да |
|
||||||||||||
|
|
|
|
|
|
Да Останов |
|
|
|
|
5 |
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
по J = (Nэ–1) g I |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
Вр:=Эл[J] |
|||||||||||||||||||
|
|
|
|
|
|
J = I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
11 |
Цикл |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
8 |
|
|
|
|
|
|
|
Эл |
[J+1]:=Эл[J] |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
по I = 1 g Nэ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
Рисование |
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
I = Nэ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
Эл[J]:=Вр |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
12 |
Конец |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.10.7. Схема потока 3 (сортировка по весу)
Блок 15 схемы потока 1, блоки 9 схем потоков 2 и 3, проверяющие наличие команды останова, необходимы для того, чтобы можно было остановить потоки внешней командой, не дожидаясь окончания сортировки массивов. Если не производить проверку наличия команды останова внутри потоков, то будет невозможно прервать сортировку и
222
PDF created with pdfFactory Pro trial version www.pdffactory.com
закрыть программу до окончания сортировки во всех потоках. Схемы процедур рисования линий (блоки 8 схем потоков 2 и 3 и блока 13 схемы потока 1) одинаковы для всех потоков. Схема процедуры Рисование показана на рис.10.8.
1
Начало
|
|
|
|
|
5 |
|
|
|
|
||
2 |
|
|
|
|
|
|
|||||
|
|
Стирание |
|
|
|
|
Выбор |
||||
перемещаемых |
|
|
|
координат |
|||||||
|
|
|
|
линий |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
||
|
|
|
3 |
|
|
|
|||||
|
|
|
|
|
|
|
Рисование |
||||
|
|
Рисование |
|
|
|
||||||
перемещённых |
|
|
|
квадратов |
|||||||
|
|
|
|
линий |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
Квадраты |
|||
4 |
|
|
|
|
|||||||
|
|
|
|
|
|||||||
|
Квадраты |
|
|
Число = 25 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
Конец |
||||
|
|
|
|
|
|
|
|
|
|
|
|
Рис.10.8. Схема процедуры Рисование
В конце процедуры Рисование записываем цикл, рисующий 25 квадратиков. Цикл добавляем для замедления процессов, чтобы нагляднее был виден процесс сортировки и окончание работы потока.
Схема программы для реализации на языке С++
Сравнительный анализ быстродействия трёх алгоритмов сортировки произведём одновременной сортировкой одинаковых исходных массивов в трёх параллельных потоках. Схема программы показана на рис.10.9.
223
PDF created with pdfFactory Pro trial version www.pdffactory.com
1
Начало
2
Индикатор
StE := 0
|
|
11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
Останов |
|
|
|
|
|
|
|
|
3 |
|
? |
|
Да |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
потоков |
|
|
|
|
|
|
|
|
|
Выход |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
Нет |
|
|
20 |
|
|
Конец |
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Потоки?действ. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
10 |
|
|
|
|
|
|
Нет |
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
StE := 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Да |
|
|
|
|
12 |
|
? |
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пуск |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
Да |
|
|
5 |
|
|
|
|
|
? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Останов |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Да |
|
|
|
|
|||||||||
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|
|
|
|
|
|
|
|
13 |
|
|
|
? |
|
Нет |
||||||||||||
|
|
|
|
|
|
|
StE := 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
StE = 0 |
|
|
|
|
||||||||||
|
|
|
6 |
|
|
|
|
? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
Да |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Да |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Прерывание |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Создание массива |
|
|||||||||||||||||||
Окраска |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
линий |
|
|
|
|
|
|
|
|
? |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
Да |
7 |
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Перерисовка |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Создание потоков |
|
|||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нет |
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Запуск потоков |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|||||
|
|
|
|
|
|
Поток 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Поток 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Поток 3 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.10.9. Схема программы сортировки на языке С++
Потоки обозначены как подпрограммы, выполняющие сортировку в соответствии со схемами, приведёнными на рис.10.5 - 10.7, для проекта на языке Delphi.
В потоках предусмотрим возможность их запуска, остановки и обозначения отсортированной части массива в процессе сортировки. Для сравнительного анализа удобства управления процессом сортировки, в проекте, созданном на языке С++, применим систему кнопок для управления потоками, отличающуюся от системы, использованной в проекте на языке Delphi.
Переменная StE введена для того, чтобы при пуске потоков определять, нужно ли создавать новый массив или следует продолжить сортировку предыдущего массива.
Для управления процессом сортировки в программе, написанной на языке
C++ Builder, используем кнопки: Пуск, Останов, Прерывание, Перерисовка и Выход.
Обработчик нажатия кнопки Пуск должен создать массивы случайных чисел только, если
224
PDF created with pdfFactory Pro trial version www.pdffactory.com
кнопка Пуск была нажата после прерывания процесса сортировки кнопкой Прерывание. Кнопка Прерывание тоже должна останавливать потоки, но нажатие кнопки Пуск после
нажатия кнопки Прерывание должно вызывать процедуру создания новых массивов и запускать потоки сортировки новых массивов. Кнопка Останов должна останавливать потоки с возможностью продолжения сортировки массивов с того места, на котором они были остановлены. Кнопка Перерисовка должна вызвать процедуру перекрашивания тех линий, которые уже отсортированы.
Каждый поток должен выводить на экран исходные и перемещённые элементы, цвет перемещённых элементов должен отличаться от цвета исходных элементов.
Создание проекта
Создаём проект типа VCL Forms Application. Сохраняем проект в подготовленной заранее папке с именем Work10, присваиваем главному модулю имя UnitTread, а проекту - имя Threads. Присваиваем главной форме имя fmSortTr3. Размещаем на форме три холста PaintBox и три метки с названиями потоков.
Для удобства изображения линий на экране ограничим их максимальную длину 250 пикселями, а объём массива - 175 элементами. В этом случае 175 линий можно вывести на экран в прямоугольнике размером 250×350 пикселей, рисуя линии через расстояние в 1 пиксель, и разместить на форме размером 480×850 пикселей три массива и элементы управления программой.
В проекте, создаваемом для реализации на языке С++, поместим кнопки в соответствии с рис.10.10.
Рис.10.10. Главная форма программы сортировки в системе С++ Builder
225
PDF created with pdfFactory Pro trial version www.pdffactory.com
Холстам для рисования PaintBox1, PaintBox2 и PaintBox3 задаём размеры
350×250 пикселей.
В проекте, создаваемом для реализации на языке Delphi, помещаем кнопки в соответствии с рис.10.11.
Рис.10.11. Окно программы сортировки в системе Delphi
Реализация программы на языке Delphi
Написание текста проекта начнём с создания файлов потоков. Создаём класс потока командой File → New ... . В диалоговом окне New Items выбираем вкладку New и объект Thread Object. В диалоговом окне ввода вводим название класса TSortThread. Возникнет файл с пустым описанием класса TSortThread. Файл переименуем и введём ссылку на файл в блок Uses файла главной формы. В файле потоков введём ссылку на главный модуль.
Implementation
Uses UnitTread;
В разделе Var главного модуля объявим переменные для обращения к потокам и хранения массивов.
Var
fmSortTr3: TfmSortTr3; TS1, TS2, TS3 :TSortThread;
226
PDF created with pdfFactory Pro trial version www.pdffactory.com
Len1, Len2, Len3 :Array[1..175] Of Integer;
Впроцедуре OnCreate главной формы инициализируем функцию получения случайных чисел.
Procedure TfmSortTr3.FormCreate(Sender: TObject);
Begin
Randomize
End;
Вклассе потоков создаём переменную для определения номера запускаемого потока.
Public
Box1 :Byte;
Впроцедуре OnClick кнопки Пуск записываем операторы создания массивов чисел, рисования исходных массивов линий и потоков. В этой же процедуре запускаем потоки.
Procedure TfmSortTr3.BBRunClick(Sender: TObject); Var J :Byte;
Begin
BBStop.Enabled:=True;
BitBRepeat.Enabled:=False;
BBRun.Enabled:=False;
For J:=1 To 175 Do
Begin
PaintBox1.Canvas.Pen.Color:=clBtnFace;
PaintBox2.Canvas.Pen.Color:=clBtnFace;
PaintBox3.Canvas.Pen.Color:=clBtnFace; PaintBox1.Canvas.MoveTo(0, J*2+1); PaintBox1.Canvas.LineTo(200,J*2+1); PaintBox2.Canvas.MoveTo(0, J*2+1); PaintBox2.Canvas.LineTo(200,J*2+1); PaintBox3.Canvas.MoveTo(0, J*2+1); PaintBox3.Canvas.LineTo(200,J*2+1); Len1[J]:=Random(200); Len2[J]:=Len1[J];
Len3[J]:=Len1[J];
PaintBox1.Canvas.Pen.Color:=clRed;
PaintBox2.Canvas.Pen.Color:=clRed;
PaintBox3.Canvas.Pen.Color:=clRed;
227
PDF created with pdfFactory Pro trial version www.pdffactory.com
PaintBox1.Canvas.MoveTo(0, J*2+1); PaintBox1.Canvas.LineTo(Len1[J],J*2+1); PaintBox2.Canvas.MoveTo(0, J*2+1); PaintBox2.Canvas.LineTo(Len1[J],J*2+1); PaintBox3.Canvas.MoveTo(0, J*2+1); PaintBox3.Canvas.LineTo(Len1[J],J*2+1)
End; TS1:=TSortThread.Create(True); TS1.Box1:=1; TS2:=TSortThread.Create(True); TS2.Box1:=2; TS3:=TSortThread.Create(True); TS3.Box1:=3;
TS1.Resume;
TS2.Resume;
TS3.Resume
End;
Создаём процедуру рисования массивов линий в процессе сортировки. В заголовок процедуры записываем в качестве формальных параметров холст и координаты линий, передаваемые из потоков.
Procedure TfmSortTr3.CPaint
(Cv: TCanvas; X1,X2,Y1,Y2 :Byte);
Var
M,N :Byte;
C: TColor;
Begin
Cv.Brush.Style:=bsSolid;
Cv.Pen.Color:=clBtnFace;
Cv.MoveTo(0, Y2*2+1);
Cv.LineTo(200, Y2*2+1);
Cv.MoveTo(0, Y1*2+1);
Cv.LineTo(200, Y1*2+1);
Cv.Pen.Color:=clGreen;
Cv.MoveTo(0, Y2*2+1);
Cv.LineTo(X2, Y2*2+1);
228
PDF created with pdfFactory Pro trial version www.pdffactory.com
Cv.Pen.Color:=clYellow;
Cv.MoveTo(0, Y1*2+1);
Cv.LineTo(X1, Y1*2+1);
For M:=0 To 5 Do
For N:=0 To 5 Do
Begin
C:=Random(16777216);
Cv.Pen.Color:=C;
Cv.Brush.Color:=C;
Cv.Rectangle(M*3+180,N*3,M*3+185,N*3+5)
End End;
В конце процедуры записываем цикл, рисующий квадратики. Цикл добавляем для замедления процессов, чтобы был лучше виден процесс сортировки.
В модуле потока объявляем переменные для хранения координат линий.
Var
m1X1, m1X2, m1Y1, m1Y2, m2X1, m2X2, m2Y1, m2Y2, m3X1, m3X2, m3Y1, m3Y2 :Byte;
Implementation
В файле потоков создаём текст процедуры рисования линий в потоках. Процедуры PaintLine1, PaintLine2 и PaintLine3 вызывают процедуру перерисовки перемещаемых линий CPaint и передают ей координаты этих линий.
Procedure TSortThread.PaintLine1;
Begin fmSortTr3.CPaint
(fmSortTr3.PaintBox1.Canvas,m1X1,m1X2,m1Y1,m1Y2)
End;
Procedure TSortThread.PaintLine2;
Begin fmSortTr3.CPaint
(fmSortTr3.PaintBox2.Canvas,m2X1,m2X2,m2Y1,m2Y2)
End;
Procedure TSortThread.PaintLine3;
Begin
229
PDF created with pdfFactory Pro trial version www.pdffactory.com
fmSortTr3.CPaint
(fmSortTr3.PaintBox3.Canvas,m3X1,m3X2,m3Y1,m3Y2)
End;
Создаём текст процедуры быстрой сортировки.
Procedure TSortThread.QuickSort(iLo,iHi :Byte);
Var
Lo, Hi, Mid, T :Byte;
Begin
Lo := iLo;
Hi := iHi;
Mid := Len1[(Lo + Hi) Div 2];
Repeat
While Len1[Lo] < Mid Do Inc(Lo);
While Len1[Hi] > Mid Do Dec(Hi);
If Lo <= Hi Then Begin
T := Len1[Lo]; Len1[Lo] := Len1[Hi]; Len1[Hi] := T; m1X1:=Len1[Lo]; m1Y1:=Lo; m1X2:=Len1[Hi]; m1Y2:=Hi; Synchronize(PaintLine1); Inc(Lo);
Dec(Hi);
If Terminated Then Exit; // Sleep(1)
End;
Until Lo >=Hi;
If Hi > iLo Then QuickSort( iLo, Hi);
If Lo < iHi Then QuickSort( Lo, iHi);
End;
Тексты операторов сортировки по весу и вставкой записываем непосредственно в пункты 3 и 2 оператора выбора потоков через переменную Box1. В пункт 1 оператора Case Box1 записываем вызов процедуры быстрой сортировки.
230
PDF created with pdfFactory Pro trial version www.pdffactory.com