СПО в российских школах

Февраль 25, 2011

BASIC-256. Глава 17

Методические материалы
Автор: Владимир Черный

Продолжаем публиковать перевод книги Джеймса Рено. Эту главу перевел Владимир Черный.
Оглавление:

Глава 17 Стеки, очереди, списки и сортировка

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

Стек

Стек, наиболее общая структура данных, используемая программистами во многих задачах. Стек работает как колода карт в игре «сумасшедшая восьмерка»¹. Когда вы добавляете данные в стек, они добавляются сверху (называется «push»²) и эти данные расположены в стеке над другими. Когда вы хотите получить информацию из стека, то можете взять только самый верхний элемент, открывая доступ к нижележащему (называется «pop»³). Рисунок 27 демонстрирует эту схему.

Рис. 27 Что такое стек

Операции со стеком также можно описать как «последним пришел, первым ушел», или как принято в англоязычных странах «last in, first out» сокращенно LIFO. Последнее добавленное в стек значение, будет следующим, которое из него извлечено. Программа 94 организует стек используя массив и указатель на последний добавленный элемент. В подпрограмме «pushstack» вы увидите как с помощью изменения размеров массива реализуется теоретически произвольный размер стека.

1 # stack.kbs 2 # реализация стека, используя массив 3 4 dim stack(1) # массив для хранения стека в начале 5 nstack = 0 # количество элементов стека 6 7 value = 1 8 gosub pushstack 9 value = 2 10 gosub pushstack 11 value = 3 12 gosub pushstack 13 value = 4 14 gosub pushstack 15 value = 5 16 gosub pushstack 17 18 while nstack > 0 19 gosub popstack 20 print value 21 end while 22 23 end 24 25 popstack: # 26 # получаем значение верхнего элемента стека и помещаем его в переменную value 27 if nstack = 0 then 28 print "стек пуст" 29 else 30 nstack = nstack - 1 31 value = stack[nstack] 32 end if 33 return 34 35 pushstack: # 36 # помещает число в переменную стека 36 # помещает число в переменную стека 37 # увеличивает размер стека, если он уже полон 38 if nstack = stack[?] then redim stack(stack[?] + 5) 39 stack[nstack] = value 40 nstack = nstack + 1 41 return
Программа 94 Стек
5 4 3 2 1
Пример вывода программы 94 Стек

Очередь

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

Рисунок 28 Что такое очередь

Термины enqueue и dequeue используются для обозначения процессов добавления нового элемента в хвост очереди и удаления элемента из головы очереди соответственно. Иногда очередь описывают, как «первым пришел, первым ушел» или на английском языке FIFO («first in, first out»). Пример в программе 95 использует массив и два указателя, для отслеживания «головы» и «хвоста» очереди.

1 # queue.kbs 2 # реализация очереди через массив 3 4 # размер очереди в любой момент времени 5 queuesize = 4 6 # массив для элементов очереди 7 dim queue(queuesize) 8 # Положение следующего входящего элемента (указатель на хвост) 9 tail = 0 10 # Положение в очереди возвращаемого элемента (указатель на голову) 11 head = 0 12 # количество элементов в очереди 13 inqueue = 0 14 15 value = 1 16 gosub enqueue 17 value = 2 18 gosub enqueue 19 20 gosub dequeue 21 print value 22 23 value = 3 24 gosub enqueue 25 value = 4 26 gosub enqueue 27 28 gosub dequeue 29 print value 30 gosub dequeue 31 print value 32 33 value = 5 34 gosub enqueue 35 value = 6 36 gosub enqueue 37 value = 7 38 gosub enqueue 39 40 # очищение очереди 41 while inqueue > 0 42 gosub dequeue 43 print value 44 end while 45 46 end 47 48 dequeue: # 49 if inqueue = 0 then 50 print "очередь пуста" 51 else 52 inqueue = inqueue - 1 53 value = queue[head] 54 print "удаление элемента value=" + value + " из положения=" + head + " в очереди=" + inqueue +" элементов" 55 # перемещение указателя на начало. Если мы в конце массива, переходим к началу. 56 head = head + 1 57 if head = queuesize then head = 0 58 end if 59 return 60 61 enqueue: # 62 if inqueue = queuesize then 63 print "очередь заполнена" 64 else 65 inqueue = inqueue + 1 66 queue[tail] = value 67 print "добавляемый элемент value=" + value + " в положение=" + tail + " в очереди=" + inqueue +" элементов" 68 # перемещаем указатель конца очереди, если достигли конца, переходим к началу. 69 tail = tail + 1 70 if tail = queuesize then tail = 0 71 end if 72 return
Программа 95 Очередь
добавляемый элемент value=1 в положение=0 в очереди=1 элементов добавляемый элемент value=2 в положение=1 в очереди=2 элементов удаление элемента value=1 из положения=0 в очереди=1 элементов 1 добавляемый элемент value=3 в положение=2 в очереди=2 элементов добавляемый элемент value=4 в положение=3 в очереди=3 элементов удаление элемента value=2 из положения=1 в очереди=2 элементов 2 удаление элемента value=3 из положения=2 в очереди=1 элементов 3 добавляемый элемент value=5 в положение=0 в очереди=2 элементов добавляемый элемент value=6 в положение=1 в очереди=3 элементов добавляемый элемент value=7 в положение=2 в очереди=4 элементов удаление элемента value=4 из положения=3 в очереди=3 элементов 4 удаление элемента value=5 из положения=0 в очереди=2 элементов 5 удаление элемента value=6 из положения=1 в очереди=1 элементов 6 удаление элемента value=7 из положения=2 в очереди=0 элементов 7
Пример вывода программы 95 Очередь

Связный список

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

Связный список, это последовательность элементов, содержащих данные и указатель на следующий элемент в списке. Кроме этих элементов нам необходимо иметь указатель на первый объект списка. Мы назовем первый элемент списка «голова». Взгляните на рисунок 29, где видно, как каждый объект списка указывает на другой.

Рисунок 29 Связный список

Преимущество связных списков над массивом в том, что можно с легкостью добавлять или удалять его элементы. Чтобы стереть элемент списка достаточно поменять указатель у предыдущего элемента на последующий (см. рисунок 30) и освобождение элемента так, чтобы его можно было использовать.

Рисунок 30. Удаление элемента списка.

Добавление нового элемента тоже просто. Надо создать элемент и связать его с предыдущим и последующим элементом в списке. Рисунок 31 иллюстрирует этот процесс.

Рисунок 31 Добавление элемента в связный список.

Связные списки обычно рассматривают как простейшие структуры данных. В языке BASIC мы не можем выделять память так как это делается в большинстве языков, поэтомы мы имитируем поведение списка через массивы. В программе 96 мы используем массив data$ для хранения текста в списке, массив nextitem для хранения указателей на следующий элемент списка и freeitem массив для хранения стека свободных (неиспользуемых) индексов.

1 # linkedlist.kbs 2 # Cвязный список через массивы 3 # наибольшее количество элементов списка 4 n = 8 5 # данные для элементов списка 6 dim data$(n) 7 # указатели на следующий элемент списка 8 dim nextitem(n) 9 # список (стек) свободных элементов 10 dim freeitem(n) 11 12 # начальный стек свободных элементов 13 for t = 0 to n-1 14 freeitem[t] = t 15 next t 16 lastfree = n-1 17 18 # начало списка - -1 = указатель "в никуда" 19 head = -1 20 21 # список из 3 элементов 22 text$ = "Голова" 23 gosub append 24 text$ = "еще" 25 gosub append 26 text$ = "нечто" 27 gosub append 28 gosub displaylist 29 gosub displayarrays 30 gosub wait 31 32 print "удаляем второй элемент" 33 r = 2 34 gosub delete 35 gosub displaylist 36 gosub displayarrays 37 gosub wait 38 39 print "вставляем элемент 1" 40 r = 1 41 text$ = "что-то" 42 gosub insert 43 gosub displaylist 44 gosub displayarrays 45 gosub wait 46 47 print "вставляем элемент 2" 48 r = 2 49 text$ = "кое-что" 50 gosub insert 51 gosub displaylist 52 gosub displayarrays 53 gosub wait 54 55 print "удаляем элемент 1" 56 r = 1 57 gosub delete 58 gosub displaylist 59 gosub displayarrays 60 gosub wait 61 62 end 63 64 wait: ## ждем ввода 65 input "нажмите ввод? ", garbage$ 66 print 67 return 68 69 # показываем список следуя связям 70 displaylist: 71 print "Список..." 72 k = 0 73 i = head 74 do 75 k = k + 1 76 print k + " "; 77 print data$[i] 78 i = nextitem[i] 79 until i = -1 80 return 81 82 # Показываем сохраненные в массивах данные: что и как 83 displayarrays: 84 print "массивы..." 85 for i = 0 to n-1 86 print i + " " + data$[i] + " ->" + nextitem[i] ; 87 for k = 0 to lastfree 88 if freeitem[k] = i then print " <<свободно"; 89 next k 90 if head = i then print " <<голова"; 91 print 92 next i 93 return 94 95 # вставить в text$ в позицию r 96 insert: 97 if r = 1 then 98 gosub createitem 99 nextitem[index] = head 100 head = index 101 else 102 k = 2 103 i = head 104 while i <> -1 and k <> r 105 k = k + 1 106 i = nextitem[i] 107 end while 108 if i <> -1 then 109 gosub createitem 110 nextitem[index] = nextitem[i] 111 nextitem[i] = index 112 else 113 print "Нельзя вставить после конца списка" 114 end if 115 end if 116 return 117 118 # удалить элемент r из связного списка 119 delete: 120 if r = 1 then 121 index = head 122 head = nextitem[index] 123 gosub freeitem 124 else 125 k = 2 126 i = head 127 while i <> -1 and k <> r 128 k = k + 1 129 i = nextitem[i] 130 end while 131 if i <> -1 then 132 index = nextitem[i] 133 nextitem[i] = nextitem[nextitem[i]] 134 gosub freeitem 135 else 136 print "нельзя удалить после конца списка" 137 end if 138 end if 139 return 140 141 # добавляем text$ в конец связного списка 142 append: 143 if head = -1 then 144 gosub createitem 145 head = index 146 else 147 i = head 148 while nextitem[i] <> -1 149 i = nextitem[i] 150 end while 151 gosub createitem 152 nextitem[i] = index 153 endif 154 return 155 156 # освобожденный элемент из index добавляем к стеку свободных элементов 157 freeitem: 158 lastfree = lastfree + 1 159 freeitem[lastfree] = index 160 return 161 162 # сохраняем значение text$ в data$ и возвращаем указатель на новое положение 163 createitem: 164 if lastfree < 0 then 165 print "нет свободного места" 166 end 167 end if 168 index = freeitem[lastfree] 169 data$[index] = text$ 170 nextitem[index] = -1 171 lastfree = lastfree - 1 172 return
Программа 96 Связный список.

Перепишите программу 96 чтобы реализовать стек и очередь через связный список.

Медленно и не эффективно — сортировка пузырьком

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

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

Рис. 32 Блок-схема пузырьковой сортировки

1 # bubblesort.kbs 2 # реализация простой сортировки 3 4 # Пузырьковая сортировка один из самых медлительных 5 # алгоритмов для сортировки, но он прост для понимания 6 # и реализации. 7 # 8 # Алгоритм Пузырьковой сортировки состоит из 9 # 1. Просмотра всех элементов массива с перестановкой 10 # соседних значений так, что меньшее значение 11 # перемещается вперед. 12 # 2. Шаг 1 повторяется многократно, пока не прекратятся 13 # перестановки (массив отсортирован) 14 # 15 16 dim d(20) 17 18 # Заполняем массив случайными 19 # неотсортированными данными 20 for i = 0 to d[?]-1 21 d[i] = rand * 1000 22 next i 23 24 print "*** До сортировки ***" 25 gosub displayarray 26 27 gosub bubblesort 28 29 print "*** Отсортировано ***" 30 gosub displayarray 31 end 32 33 displayarray: 34 # распечатка значений массива 35 for i = 0 to d[?]-1 36 print d[i] + " "; 37 next i 38 print 39 return 40 41 bubblesort: 42 do 43 sorted = true 44 for i = 0 to d[?] - 2 45 if d[i] > d[i+1] then 46 sorted = false 47 temp = d[i+1] 48 d[i+1] = d[i] 49 d[i] = temp 50 end if 51 next i 52 until sorted 53 return
Программа 97 Пузырьковая сортировка

Лучшая сортировка — сортировка вставками

Сортировка вставками — еще один алгоритм сортировки данных. Обычно он быстрее чем пузырьковая сортировка, но в худшем случае может занять столько же времени.

Сортировка вставками получила свое название из-за принципа работы. Во время сортировки просматривает массив элементов (от index=1 до length-1) и вставляет значение в правильное положение, по отношению к предыдущим уже отсортированным элементам массива. Рисунок 33 демонстрирует этот принцип.

Рис. 33 Сортировка вставкой, шаг за шагом.

1 # insertionsort.kbs 2 # реализация эффективной сортировки 3 4 dim d(20) 5 6 # заполнение массива случайными данными 7 for i = 0 to d[?]-1 8 d[i] = rand * 1000 9 next i 10 11 print "*** Без сортировки ***" 12 gosub displayarray 13 14 gosub insertionsort 15 16 print "*** Отсортировано ***" 17 gosub displayarray 18 end 19 20 displayarray: 21 # Печать данных массива 22 for i = 0 to d[?]-1 23 print d[i] + " "; 24 next i 25 print 26 return 27 28 insertionsort: 29 # цикл по массиву начиная со второго элемента 30 # берем текущий элемент и вставляем его 31 # в правильное (по сортировке) место 32 # среди цепочки предыдущих отсортированных элементов 33 34 # двигаясь в обратном направлении от текущего положения 35 # и сдвигая элементы с большим значением 36 # для получения места для текущего элемента в правильном 37 # месте (в уже частично отсортированном массиве) 38 39 for i = 1 to d[?] - 1 40 currentvalue = d[i] 41 j = i - 1 42 done = false 43 do 44 if d[j] > currentvalue then 45 d[j+1] = d[j] 46 j = j - 1 47 if j < 0 then done = true 48 else 49 done = true 50 endif 51 until done 52 d[j+1] = currentvalue 53 next i 54 return
Программа 98. Сортировка вставкой.

Перепишите программу 98 используя связные списки как в программе 96

Узнайте про другие алгоритмы сортировки и реализуйте их на BASIC-256

—————————————————
¹ Можно сравнить стек с магазином патронов у автомата или автоматического пистолета (прим. переводчика)

² В данном случае слово «push» можно перевести как «продавить», что очевидно, если сравнивать стек с магазином, а добавление информации с помещением патрона в магазин. (прим. переводчика)

³ вытолкнуть (прим. переводчика)

============================

Где скачать BASIC-256:

Для дистрибутивов ALT Linux

ветка 4.0 basic256-0.9.6-alt5.M40.1.i586.rpm
ветка 4.1 basic256-0.9.6-alt5.M41.1.i586.rpm
ветка p5 basic256-0.9.6-alt5.M50P.1.i586.rpm
ветка 5.1 basic256-0.9.6-alt5.M51.1.i586.rpm

Windows версия
http://basic256.org (http://www.sourceforge.net/projects/kidbasic)

Как установить BASIC-256 в Linux

Для Альт Линукс: настроить репозиторий и обновить/установить пакет через synaptic или apt
Для rpm-based дистрибутивов: rpm -Uvh <имя_пакета>.rpm

Подписаться на комментарии RSS 2.0. You can leave a response, or trackback from your own site.

BASIC-256. Глава 17

Глава 17 Стеки, очереди, списки и сортировка