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

Команда ALT Linux рассказывает о внедрении свободного программного обеспечения в школах России
Февраль 25, 2011

BASIC-256. Глава 17

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

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

Где взять BASIC-256

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

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

Стек

Стек, наиболее общая структура данных, используемая программистами во многих задачах. Стек работает как колода карт в игре «сумасшедшая восьмерка»1. Когда вы добавляете данные в стек, они добавляются сверху (называется «push»2) и эти данные расположены в стеке над другими. Когда вы хотите получить информацию из стека, то можете взять только самый верхний элемент, открывая доступ к нижележащему (называется «pop»3). Рисунок 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

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

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

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

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

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

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

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

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

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

Оставьте комментарий