Учебное пособие Чебоксары 2008 удк 004. 657 П 36
| Контрольные вопросы Лабораторная работа 3. Поиск в таблице значений Необходимые исходные сведения Варианты заданий Блок-схема алгоритма |
Смотрите также:
- Учебное пособие Владимир 2011 удк 657. 1: 69 ббк 65. 052. 253. 1
- Учебное пособие Новомосковск 2008 удк 93/99
- Учебное пособие Краснодар 2012 удк 159. 9+37. 01]: 378. 147 Ббк 74. 00
- Учебное пособие москва 2012 удк 32. 001 Ббк 66. 0
- Учебное пособие Новосибирск 2012 удк 330. 4 (075. 8) К. э н., доцент М. В. Облаухова
- Учебное пособие Санкт-Петербург 2010 удк 616-058: 93/99+61(06) isbn 57645-0189
- Учебное пособие Томский политехнический университет 2009 удк 000000 ббк 00000
Каким образом можно представить тип данных Дерево?
Какие особенности у типа данных Бинарное дерево? Где они применяются?
Как можно представить бинарное дерево?
Какие существуют способы прохождения бинарных деревьев? Где они применяются?
Какие существуют алгоритмы, использующие тип данных Дерево?
В чем состоит смысл алгоритма сортировки с прохождением бинарного дерева?
В чем состоит смысл алгоритма сортировки методом турнира с выбыванием?
Каким образом бинарные деревья применяются для сжатия информации?
Как представляются выражения с помощью деревьев?
Как используется тип данных Сильноветвящееся дерево? Каково применение сильноветвящихся деревьев?
Каким образом можно представить тип данных Граф?
Какие существуют алгоритмы, использующие тип данных Граф?
размер неявно указывается путем добавления концевого символа, больше этот символ нигде не употребляется. Обычно для этой цели используется “непечатаемый” символ со значением 00h (для дальнейшего важно, что это минимальный символ из всего множества символов);
размер явно хранится в качестве первого элемента массива, т.е. строка s имеет следующий вид: s = s0, s1, s2, ..., sM-1. Здесь s1, ..., sM-1 – фактические символы строки, а s0 = Chr(M). Такой прием имеет то преимущество, что размер явно доступен, недостаток же в том, что этот размер ограничен размером множества символов (256).
^ Цель работы: 1)ознакомиться с методами решения задач поиска, а именно поиска в таблице, в соответствии с данным заданием; 2)получить навыки в программировании задач поиска элементов. ^ Поиск в массиве иногда называют поиском в таблице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов. Часто встречается именно последний случай, когда массивы символов называют строками или словами. Строковый тип определяется так: String = array[0..М–1] of char. Соответственно определяется и отношение порядка для строк x и y: x = y, если xj = yj для 0 face="Symbol" =< j < M, x < y, если xi < yi для 0 face="Symbol" =< i < M и xj = yj для 0 face="Symbol" =< j < I. Для того чтобы установить факт совпадения, необходимо установить, что все символы сравниваемых строк соответственно равны один другому. Поэтому сравнение составных операндов сводится к поиску их несовпадающих частей, т. е. к поиску “на неравенство”. Если неравных частей не существует, то можно говорить о равенстве. Предположим, что размер слов достаточно мал, скажем меньше 30. В этом случае можно использовать линейный поиск и поступать таким образом. Для большинства практических приложений желательно исходить из того, что строки имеют переменный размер. Это предполагает, что размер указывается в каждой отдельной строке. Если исходить из ранее описанного типа, то размер не должен превосходить максимального размера M. Такая схема достаточно гибка и подходит для многих случаев, в то же время она позволяет избежать сложностей динамического распределения памяти. Чаще всего используются два таких представления размера строк: В последующем алгоритме поиска отдается предпочтение первой схеме. В этом случае сравнение строк выполняется так: i:=0; while (x[i]=y[i]) and (x[i]<>00h) do i:=i+1. Концевой символ работает здесь как барьер. Теперь вернемся к задаче поиска в таблице. Он требует “вложенных” поисков, а именно поиска по строчкам таблицы, а для каждой строчки последовательных сравнений – между компонентами. Например, пусть таблица T и аргумент поиска x определяются таким образом: T: array[0..N-1] of String; x: String. Допустим, N достаточно велико, а таблица упорядочена в алфавитном порядке. При использовании алгоритма поиска делением пополам и алгоритма сравнения строк, речь о которых шла выше, получаем такой фрагмент программы: L:=0; R:=N; while L m:=(L+R) div 2; i:=0; while (T[m,i]=x[i]) and (x[i]<>00h) do i:=i+1; if T[m,i] end; if R i:=0; while (T[R,i]=х[i]) and (х[i]<>00h) do i:=i+1 end; {(R Но при достаточно большом значении N можно использовать алгоритм линейного поиска и алгоритм последовательного сравнения строк. ^
Пример выполнения Задание: осуществить последовательный поиск совпадений в таблице, используя сортировку вставкой. ^  Текст программы: uses crt; type data=integer; matrix=array[1..15,1..15] of integer; vector=array[1..15] of integer; var a:matrix; x:vector; n,i,j,k:word; l,m,r:integer; found:boolean; procedure create_matrix(var a:matrix;p:word); var i,j:word; begin writeln('Матрица создана:'); for i:=1 to p do for j:=1 to p do a[i,j]:=2*(9+random(100)); end; procedure vivod_matrix(var a:matrix;p:word); var i,j:word; begin for i:=1 to p do begin for j:=1 to p do write(a[i,j]:6); writeln; end; end; procedure create_vector(var x:vector;p:word); var i:word; begin writeln('Вектор создан:'); for i:=1 to p do x[i]:=random(100); end; procedure vivod_vector(var x:vector;p:word); var i:word; begin for i:=1 to p do write(x[i]:6); writeln; end; procedure insert(var a:matrix;p:word); var i,j,k:integer; x:data; begin writeln('Сортировка вставкой:'); for k:=1 to p do for i:=2 to p do begin x:=a[k,i]; j:=i-1; while (x begin a[k,j+1]:=a[k,j]; j:=j-1; end; a[k,j+1]:=x; end; end; begin clrscr; write('Введите число элементов массива: n='); readln(n); create_matrix(a,n); vivod_matrix(a,n); writeln('Упорядоченная матрица в строках:'); insert(a,n); vivod_matrix(a,n); create_vector(x,n); vivod_vector(x,n); writeln('Совпадения элементов матрицы и вектора'); writeln('--------------------------------------'); for i:=1 to n do begin for j:=1 to n do for k:=1 to n do if a[i,j]=x[k] then writeln(x[k],': совпадение в ',i,' – й строке матрицы'); end; writeln('Нажмите любую клавишу'); readkey; end. Результаты расчетов:
|
