Рисунок 6- Обход дерева

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

   Прохождение бинарного дерева сверху: обработать корень, пройти левое поддерево, пройти правое поддерево.

   Прохождение слева направо: пройти левое поддерево, обработать корень, пройти правое поддерево.

   Прохождение дерева снизу: пройти левое поддерево, пройти правое поддерево, обработать корень. 

3. Критерий выдачи 

   Критерий  выдачи - формальное правило, в соответствии с которым в информационном массиве определяются документы, подлежащие выдаче в ответ на поступивший в системе запрос.

   Различают три вида критериев выдачи, формулируемых  в терминах теории множеств При этом поисковые образы и предписания запросов понимаются как множества лексических единиц ИПЯ.

   Критерий "на совпадение". Для выдачи требуется, чтобы лексические единицы поискового образа документа и поискового предписания  совпадали, т.е. M_g=M_d.

   Критерий "на включение" или "на вхождение". В ответ на запрос выдаются те документы, поисковые образы которых включают целиком поисковые предписания запроса. Если поисковый образ документа представить в виде множества M_d, а поисковое предписание M_g, то сообщение выдается, когда M_g M_d.

   Критерий "на пересечение" требует не полного, а частичного совпадения лексических  единиц документа и запроса, т  е. пересечение поисковых образов: M_g M_d.

СОДЕРЖАНИЕ  КУРСОВОГО ПРОЕКТА

 
         

1. Составить блок-схему и программу на алгоритмическом языке для решения поставленной задачи согласно варианту.
2. Получить результаты.
3. Провести анализ полученных результатов и сделать выводы.

СОДЕРЖАНИЕ  ОТЧЕТА

 

Отчет должен содержать:

1. Задание на курсовой проект в полном объеме. Постановку задачи.
2. Описание работы программы
3. Листинг программы.
4. Результаты работы программы.
5. Выводы по полученным результатам.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ 

1. Расскажите  об особенностях:

• цепной поисковой стратегии;
• узловой поисковой стратегии;
• гнездовой поисковой стратегии;
• стратегии последовательного просмотра;
• стратегии последовательного деления на части;
• стратегии способа разделителей;
• стратегии «метода свертывания кодов»;
• стратегии линейной интерполяции;
• стратегии «серийного упорядоченного поиска»;
• стратегии обхода снизу;
• стратегии обхода сверху.

 

2. Расскажите  об организации массивов:

• последовательно-смежной структурой;
• списковой структурой;
• матрицей;
• деревьями.

3. Расскажите  о критериях выдачи информации:

• на совпадение;
• на включение;
• на пересечение.

ИНДИВИДУАЛЬНЫЕ  ЗАДАНИЯ

 

Составить алгоритм и написать программу: 

Примеры решения

 

Вариант 1 

   Создание  списка Т(I), I=1,5, поиск и удаление k-ro элемента k=2, выдача списков Т(I) по критерию выдачи "на пересечение".

   Программа написана на языке Pascal.

   Описание  массивов и переменных:

Т(25) - массив фамилий, состоит из 5 подмассивов. Первый подмассив Т(I), I=1,5 организуется списковой стратегией организации массивов, в нем же идет поиск k-ro элемента и его удаление.

ADR(25) - массив адресов - состоит из 5 подмассивов адресов.

А(3) - массив фамилий, вводимых в массив Т(I), I=1,5.

В(5) - массив кодов каждого из 5 подмассивов  Т.

Ll(2), L2(2), L3(2), L4(2), L5(2) - указатели списков подмассивов Т.

LAVS 1(2), LAVS2(2), LAVS3(2), TLAVS4(2), LAVS 5(2) - указатели списков пустых ячеек подмассивов Т.

ITEM - вспомогательная переменная.

SCH - счетчик подсписков/подмассивов. 

Описание  работы головной программы. 

Шаг 1: /блоки 1-3/ - начало и ввод массивов.

Шаг 2: /блоки 4-9/ - в этих блоках формируем массив Т(I), I=1,5. Сначала в пустые ячейки этого массива вводим элементы массива А. При этом счетчик непустых ячеек массива Т увеличивается, а пустых уменьшается с каждым шагом на 1.

Шаг 3: /блоки 10, 11/ - задаем k=2, ищем этот элемент в списке Т(I), I=1,5, удаляем его. При этом в адресную ячейку предыдущего элемента ставим адрес, стоявший раньше в адресной ячейке элемента k, а в адресную ячейку удаленного элемента ставится 0.

Шаг 4: /блоки 12-16/ - для дальнейшей работы с программой задаемся счетчиком подмассивов Т(I). 4 раза обращаемся к подпрограмме POD4 (для проверки подмассивов Т(I), I=6, 25). Конец головной программы. 

Описание  работы подпрограммы POD4. 

Шаг 1: /блоки 1-3/ - начинаем подпрограмму, переводим элементы массива В в строку символов STR.

Шаг 2: /блоки 4-20/ - организуем цикл I=1,3. Сравниваем по одному элементы STR(l) с STR(SCH). Если они не равны, то печатаем сообщение, что условие на пересечении не выполняется, идем на конец подпрограммы и вместе с этим увеличиваем SCH на 1. Если они равны, то присваиваем переменной L нужное нам значение и печатаем, что условие на пересечении выполнено. Печатаем списки, для которых это условие выполняется. Идем на конец программы, увеличивая также при этом значение SCH на 1.

Шаг 3: /блоки 21, 22/ - увеличение значений счетчика и конец подпрограммы POD4. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Блок-схема  головной программы (вариант  №1) 

 

Блок-схема  подпрограммы POD4 

   

 

Исходные массивы:

Т: a b c d e f g h i j k l m n o p q r s t u v w x y

ADR: 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

A: a b с

В: 1 2 1 3 4

L1: 1 2   LAVS1: 1 2

L2: 3 4   LAVS2: 3 4

L3: 5 6   LAVS3: 5 6

L4: 7 8   LAVS4: 7 8

L5: 9 0   LAVS5: 9 0 

Результаты поиска: 

   Условие на пересечение выполнено для  списков Т1 и Т. 

Текст программы:

uses crt;

var

  t:array[1..25] of string[20];

  adr:array[1..25] of integer;

  a:array[1..3] of string[20];

  b:array[1..5] of integer;

  l1,l2,l3,l4,l5:array[1..2] of integer;

  lavs1,lavs2,lavs3,lavs4,lavs5:array[1..2] of integer;

  item,sch:integer;

  i,k,l:integer;

  strl,strsch,r:string;

procedure pod4(var sch:integer);

begin

  strl:='';

  strsch:='';

  str(b[1],r);

  strl:=strl+r;

  str(b[sch],r);

  strsch:=strsch+r;

  i:=1;

  if strl=strsch then

  begin

    writeln('Условие на пересечение выполнено для списков Т1 и Т');

    if sch=2 then l:=l2[1];

    if sch=3 then l:=l3[1];

    if sch=4 then l:=l4[1];

    if sch=5 then l:=l5[1];

    writeln('Исходный список. Код = ',b[l]);

    for i:=l1[1] to l1[1]+4 do

    begin

      writeln('T[',i,']= ',T[i]);

      writeln('ADR[',i,']= ',ADR[i]);

    end;

    writeln;

    writeln('Список на пересечение. Код = ',b[sch]);

    for i:=l to l+4 do

    begin

      writeln('T[',i,']= ',T[i]);

      writeln('ADR[',i,']= ',ADR[i]);

    end;

  end;

  sch:=sch+l;

end; 

begin

  clrscr;

  for i:=1 to 25 do

  begin

    write('Bведите T[',i,']:');

    readln(T[i]);

    write('Введите  ADR[',i,']:');

    readln(adr[i]);

  end;

  for i:=1 to 3 do

  begin

    write('Введите  A[',i,']: ');

    readln(a[i]);

  end;

  for i:=1 to 5 do

  begin

    write('Введите  B[',i,']: ');

    readln(b[i]);

  end;

  for i:=1 to 2 do

  begin

    write('Введите  LAVS1[',i,']: ');

    readln(lavs1[i]);

    write('Введите  LAVS2[',i,']: ');

    readln(lavs2[i]);

    write('Введите  LAVS3[',i,']: ');

    readln(lavs3[i]);

    write('Введите  LAVS4[',i,']: ');

    readln(lavs4[i]);

    write('Введите  LAVS5[',i,']:');

    readln(lavs5[i]);

  end;

  for i:=1 to 2 do

  begin

    write('Введите  L2[',i,']: ');

    readln(l2[i]);

    write('Введите  L3[',i,']: ');

    readln(l3[i]);

    write('Введите  L4[',i,']: ');

    readln(l4[i]);

    write('Введите  L5[',i,']: ');

    readln(l5[i]);

  end;

  l1[1]:=lavs1[1];

  l1[2]:=0;

  i:=0;

  repeat

    i:=i+1;

    t[lavs1[1]]:=a[i];