1385

Структуры и алгоритмы обработки данных

Практическая работа

Информатика, кибернетика и программирование

Формирование практических навыков организации и использования при решении задач динамических структур данных. Изучение наиболее распространенных алгоритмов решения задач с использованием сложных структур данных.

Русский

2013-01-06

234.5 KB

51 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ»

Факультет информационных технологий

Кафедра технологий программирования

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА

По дисциплине

«Структуры и алгоритмы обработки данных»

Проверила

Кеда И. С.

Автор работы

студентка гр. 10 ИТ-3

Пикуль С. А.

Полоцк 2011

Содержание

Введение...................................................................................................................3

1. Задача № 1. ..........................................................................................................4

1.1. Постановка задачи и ее анализ........................................................4

1.2. Описание структур данных..............................................................4

1.3. Проектирование программы............................................................4

1.4. Результаты отладки и тестирования................................................5

2. Задача № 2. ..........................................................................................................6

2.1. Постановка задачи и ее анализ........................................................6

2.2. Описание структур данных..............................................................6

2.3. Проектирование программы............................................................6

2.4. Результаты отладки и тестирования ...............................................8

3. Задача № 3. ..........................................................................................................9

3.1. Постановка задачи и ее анализ........................................................9

3.2. Описание структур данных..............................................................9

3.3. Проектирование программы............................................................9

3.4. Результаты отладки и тестирования .............................................10

4. Задача № 4..........................................................................................................11

4.1. Постановка задачи и ее анализ......................................................11

4.2. Описание структур данных............................................................11

4.3. Проектирование программы..........................................................11

4.4. Результаты отладки и тестирования .............................................13

Заключение.............................................................................................................14

Список использованных источников...................................................................15

Введение

Цели расчетно-графической работы:

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

Расчетно-графическая работа выполняется на языке программирования Pascal.

Язык программирования ПАСКАЛЬ, названный в честь французского учёного Блёза Паскаля, разработан профессором Института Швейцарской высшей политехнической школы Никлаусом Виртом в 1970 г. Затем в него был внесён ряд изменений и в 1979 г. Группой автором был опубликован окончательный вариант языка. Он удовлетворяет требованиям структурного программирования и отличается завершённостью и концептуальной однородностью. Язык содержит хороший набор структур данных (простые переменные, массивы, записи и т.д.) и позволяет формализовать более простые и эффективные алгоритмы. Несмотря на появление новых технологий Паскаль, во многом задуманный как язык для обучения, и на сегодняшний день остаётся одним из самых удобных средств для изучения программированию. Это определяет его популярность среди широкой аудитории начинающих программистов: школьников и студентов.

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

  1.  Задача № 1. Разработать программу с реализацией двусвязного списка.

1.1. Постановка задачи:

Ввести натуральное число N. Создать два упорядоченных двусвязных списка из N элементов. Построить третий список, который содержит без повторений элементы, одновременно содержащиеся в обоих списках. Операции со списком реализовать подпрограммами.

      Анализ:

Для решения поставленной задачи нам понадобится 3 двусвязных списка:  два содержащих N чисел, введенных пользователем, и один, содержащий без повторений элементы, одновременно содержащиеся в обоих списках.

1.2. Описание структур данных:

 В данной задаче представлен двусвязный список. Двусвязный список – список по элементам которого можно перемещаться в две стороны (в отличие от односвязного).

1.3.Проектирование:

Программа работает по следующему принципу. Обработка списков выплняется в двух процедурах: Process и Add_into_list3. Сначала в процедуре Process происходит сравнение двух списков. Элементы, которые есть в обоих списках отправляются в процедуру Add_into_list3 для дальнейшей обработки. В процедуре Add_into_list3 происходит сравнение поступивших элементов с элементами третьего списка. Эсли в третьем списке такие элементы есть, происходит выход из процедуры. Если же такие элементы в третьем списке не обнаружены, происходит добавление их в третий список процедурой Add. Листинг основных процедур и функций приведен ниже:

Procedure Process (lst1,lst2:list;var lst3:list);   //передаются 3 списка

var

  tmp_el: pel;

begin

    while lst1.head<>nil do //проход по первому списку

          begin

               tmp_el:=lst2.head;  //создание копии второго списка

               tmp_el^.next:=lst2.head^.next;  

               tmp_el^.prev:=lst2.head^.prev;

               while tmp_el<>nil do  //проход по копии втрого списка

                     begin

                          if lst1.head^.data=tmp_el^.data then  //сравнивание элементов первого и                    второго списка, если они равны, то

                             begin

                                  Add_into_list3(lst3,tmp_el^.data);  //вызов процедуры

                                  break;  //выход из цикла

                             end;

                          tmp_el:=tmp_el^.next; //переход к следующему

                     end;

               lst1.head:=lst1.head^.next;  //переход к следующему

          end;

end;

Procedure Add_into_list3(var lst:list; val:integer);  //передается список и элемент

var

  tmp_el: pel;  

begin

    tmp_el:=lst.head;  //создание копии списка

    if lst.head <> nil then  //проход по списку

       begin

            tmp_el^.next:=lst.head^.next;  

            tmp_el^.prev:=lst.head^.prev;

       end;

    while tmp_el<>nil do  //проход по списку

          begin

               if tmp_el^.data=val then  //если элементы равны

                  begin

                       exit;  //выход из процедуры

                  end;

               tmp_el:=tmp_el^.next; //переход у следующему

          end;

    add(lst,val);  //добавление элемента в третий список

end;

1.4. Результаты отладки и тестирования:

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

                                                                                                рис.  1

Во время тестирования программы серьёзных сбоев не было обнаружено.

Отладка производилась по ходу тестирования программы.

  1.  Задача № 2. Разработать программу с реализацией хеш-таблиц.

2.1. Постановка задачи:

Проверить, являются ли одинаковыми две открытых хеш-таблицы М1 и М2 (хеш функция h(k)= k mod n, где k – элемент, n – количество строк таблицы).

      Анализ:

Для решения этой задачи нам понадобятся 2 хеш-таблицы,заполнение которых будет производить пользователь.

2.2. Описание структур данных:

Хеш-таблица представляет собой обычный массив со специальной адресацией, задаваемой некоторой функцией (хеш-функцией).

2.3. Проектирование:

Принцип работы программы заключается в следующем. Сравнение таблиц происходит в процедуре Comparison. В нее передаются две исходные, уже заполненные пользователем, хеш-таблицы. Затем происходит нахождение размера (количества элементов) обеих таблиц. Если размеры не равны, происходит выход из процедуры, т.к хеш-таблицы различного размера не могут быть равны. Пользователю выводится сообщение, что хеш-таблицы не равны. Если размер обеих хеш-таблиц одинаковый, происходит дальнейшее сравнение каждого элемента таблиц. Затем выводится сообщение пользователю о результате. Данный алгоритм в виде кода:

procedure COMPARISON( table1: mas; table2:mas);  //передаются две хеш-таблицы

var

 i,tmp,size1,size2: integer;

 p1,p2: pnode;

begin

 tmp:=1;  //отвечает за итоговый результат. Если 1-таблицы равны, 0-не равны

 i:=1;

 size1:=0;

 size2:=0;

 while i<>10 do  //проход по таблице

       begin

            if table1[i]<>nil then  //если элемент не пуст

               inc(size1);  //увеличение размера

            inc(i);  //увеличение счетчика

       end;

 i:=1;

 while i<>10 do  //проход по таблице

       begin

            if table2[i]<>nil then  //если элемент не пуст

               inc(size2);  //увеличение размера

            inc(i);  //увеличение счетчика

       end;

  if size1<>size2 then  //если размеры не равны

     tmp:=0  //переменная равна 0-таблицы не равны

  else

      begin

           for i := 1 to 10 do  //проход по таблице

               begin

                    p1 := table1[i];  //определюнный список таблицы

                    p2 := table2[i];  // определюнный список таблицы

                    while ((p1 <> nil) and (p2 <> nil)) do  //пока элемент не пуст

                          if (tmp=1) then  //если ранее таблицы были равны

                             if (p1^.inf = p2^.inf) then  //если элементы равны

                                begin

                                     p1 := p1^.next;  //переход к следующему

                                     p2 := p2^.next;  //переход к следующему

                                end

                             else

                                 begin

                                      tmp:=0;  //переменная равна 0

                                      p1 := p1^.next;  //переход к следующему

                                      p2 := p2^.next;  //переход к следующему

                                 end;

               end;

        end;

  if tmp=1 then  //вывод результата

     writeln('Таблицы равны')

  else

      writeln('Таблицы не равны');

end;

2.4. Результаты отладки и тестирования:

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

                                                                                       рис.  2

Если пользователь выбирает сравнение таблиц, программв их сравнивает и выводит результат на экран (рис. 3, рис. 4).

                                                                             рис.  3

      

                                                                               рис.  4

Во время тестирования программы серьёзных сбоев не было обнаружено.

Отладка производилась по ходу тестирования программы.

  1.  Задача № 3. Разработать программу с реализацией бинарного дерева

3.1. Постановка задачи:

Посчитать в бинарном дереве количество слов, оканчивающихся на согласную букву.

      Анализ:

Для решения данной задачи нам понадобится такая динамическая структура данных как бинарное дерево.

3.2. Описание структур данных:

 Дерево - это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. Корень – это начальный узел дерева. Лист – это узел, из которого не выходит ни одной дуги. Бинарное дерево – дерево, в котором каждый узел имеет максимум по два сына.

3.3. Проектирование:

Заполнение дерева элементами работает по следующему принципу: элемент с минимальной длиной является самым левым листом дерева, с максимальной длиной – самым правым. Решение задачи происходит в процедурах Search и Check. В процедуре Search происходит перебор всех элементов дерева и перенос их в процедуру Check. В процедуре Check элементы походят проверку, заканчиваются они на согласную или нет. Результат выводится на экран. Если элементов, удовлетворяющих условиям поиска, нет, пользователю сообщается об этом. Листинг основных процедур и функций приведен ниже:

procedure Search(Tree: PNode);  //передается дерево

begin

    if Tree = nil then  // если дерево пусто

       begin

            exit;  //выход из поцедуры

       end;

    Check(tree^.data,k);  //запуск процедуры проверки

    Search(Tree^.left);  //переход к следующему элементу

    Search(Tree^.right);  // переход к следующему элементу

end;

Procedure Check(str:string; var k:integer);

var i:integer;

begin

    if ((ord(str[length(str)])<>117)  and (ord(str[length(str)])<>121)

         and (ord(str[length(str)])<>111) and (ord(str[length(str)])<>105)

and (ord(str[length(str)])<>101) and (ord(str[length(str)])<>97)

and (ord(str[length(str)])<>251) and (ord(str[length(str)])<>255)

and (ord(str[length(str)])<>254)  and (ord(str[length(str)])<>253)

and (ord(str[length(str)])<>243) and (ord(str[length(str)])<>238)

and (ord(str[length(str)])<>232) and (ord(str[length(str)])<>229)

and (ord(str[length(str)])<>224)) and ((ord(str[length(str)])<>65)  

and (ord(str[length(str)])<>69) and (ord(str[length(str)])<>73)

and (ord(str[length(str)])<>79) and (ord(str[length(str)])<>85)

and (ord(str[length(str)])<>89) and (ord(str[length(str)])<>192)

and (ord(str[length(str)])<>197) and (ord(str[length(str)])<>200)

and (ord(str[length(str)])<>206) and (ord(str[length(str)])<>211)

and (ord(str[length(str)])<>219) and (ord(str[length(str)])<>223)

and (ord(str[length(str)])<>221) and (ord(str[length(str)])<>222) ) then //проверка, если последняя буква не гласная

       begin

         writeln(str);  //вывод строки

         inc(k);  //увеличение счетчика-количества слов, удовлетворяющих условию

       end;

end;

3.4. Результаты отладки и тестирования:

При запуске программы на экран выводится основное меню. Пользователь выбирает нужный ему пункт меню. На рис. 5 показано заполнение дерева элементами. На рис. 6 показан вывод заполненного дерева. На рис. 8 показан результат поиска. 

  рис.  5

           рис.  6

           рис.  7

Во время тестирования программы серьёзных сбоев не было обнаружено.

Отладка производилась по ходу тестирования программы.

  1.  Задача № 4. Разработать программу по отысканию медианы массива

4.1. Постановка задачи:

 Поиск медианы массива.

      Анализ:

В этой задаче будем использовать  массив целых чисел.

4.2. Описание структур данных:

 Массив – это последовательность однотипных данных, объединенная общим именем, элементы (компоненты) которой отличаются (идентифицируются) индексами. Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов.

4.3. Проектирование:

Медиану массива будем находить следующим образом. Отыщем средний элемент массива (средний не по значению, а по расположению в массиве), затем найдем слева от этого элемента элемент больший его по значению, справа - меньший и поменяем их местами, и т. д. Если с одной из сторон мы найдем какой-нибудь элемент, а со второй нет, то меняем найденный элемент со средним. Поиск будет продолжаться до тех пор, пока слева от среднего элемента не будут находиться все элементы меньше, а справа больше него. Листинг представлен ниже:

var

  i,left,right,buff,c,n:integer;

  a:array[1..100] of integer;

  flag:boolean;

begin

writeln('Введите N');  //вывод на экран диалога

readln(n);  // ввод N-количества элементов массива

for i:=1 to n do  //заполнение массива

   begin

        readln(a[i]);  //чтение элементов массива

   end;

c:= round((i+1)/2);  //с-средний индекс (по расположению) массива

left:= c-1;  //вспомогательный индекс с левой стороны

right:= c+1;  // вспомогательный индекс с правой стороны

flag:= true;  //логическая переменная

while flag=true do

     begin

  flag:= false;  

  while (left>= 1) and (a[left]< a[c]) do dec(left);  //нахождение элемента с левой стороны массива по отношению к с, который меньше a[с]

  while (right<= i) and (a[right]> a[c]) do inc(right);  //нахождение элемента с правой стороны массива по отношению к с, который больше a[с]

  if (right<= i) and (left>= 1) and (a[left]> a[c]) and (a[right]< a[c]) then  //перестановка элементов( элемент слева, который больше a[c] и элемент справа, меньший a[c])

     begin

     buff:= a[right];  

     a[right]:= a[left];  

     a[left]:= buff;  

     flag:= true;  

         end;

  if (left>= 1) and (a[left]> a[c]) and (right= i+1) then  // перестановка элементов (элемента слева, большего a[c], и a[c])

     begin

     buff:= a[c];  

     a[c]:= a[left];

     a[left]:= buff;

     flag:= true;

        end;

  if (right<= i) and (left= 0) and (a[right]< a[c]) then  // перестановка элементов (элемента справа, меньшего a[c], и a[c])

      begin

     buff:= a[c];  

     a[c]:= a[right];  

     a[right]:= buff;  

     flag:= true;

  end;

 left:= c-1;  //возвращение на прежние позиции для нового обхода

 right:= c+1;  //возвращение на прежние позиции для нового обхода

end;

Writeln('Медиана массива равна ', a[c]);  //вывод результата на экран

end.

4.4. Результаты отладки и тестирования:

Пользователь вводит количество элементов массива и элементы массива. Программа выводит на экран медиану массива.(рис. 8)

                                                                            рис.  8

Во время тестирования программы серьёзных сбоев не было обнаружено.

Отладка производилась по ходу тестирования программы.

Заключение

В расчетно-графической работе решена задача работы с динамическими структурами данных, а также вывода информации по определённому запросу на экран в определённой форме. Для реализации программы был создан понятный интерфейс программы, который обеспечит легкую работу с программой. Освоены навыки работы с модулем CRT (использовался для работы с клавиатурой  и для создания интерфейса программы). Разработан алгоритм решения поставленной задачи. По этому алгоритму на языке Pascal составлена и отлажена программа, проведено её тестирование, результат которого показал, что поставленная задача успешно решается, что программа не имеет каких-либо ошибок и сбоев.

Список использованной литературы:

1. Н. Вирт “Алгоритмы и структуры данных” Москва 1989г. 360 стр.

2. Альфред В. Ахо “Структуры данных и алгоритмы” Москва 2000г. 384 стр.

3. Дж. Макконнелл “Основы современных алгоритмов” Москва 2004 г. 368                стр.

9


 

А также другие работы, которые могут Вас заинтересовать

77660. Нанотехнологии в медицине 990 KB
  Человечество всегда стремилось к прогрессу и с древних времён искало способы лечить болезни и продлевать жизнь. Люди пытались излечивать болезни разными способами - если в XX веке умели решать проблемы на клеточном уровне, то в наше время уже научились решать их на атомном и молекулярном.
77661. История и эволюция инфографики 109 KB
  Выявить значения инфографики как средства совершенствования информации Составить периодизацию истории инфографики Определить особенности и области применения инфографики на различных этапах её развития...
77662. Теория «трех штилей» в учении и поэзии М. В. Ломоносова 134.5 KB
  Актуальность настоящей работы определяется необходимостью проследить «связующую нить» между теоретическими взглядами на стилистическую дифференциацию единиц русского языка М. В. Ломоносова и их практическим воплощением в поэзии автора теории.
77664. РАБОТА СЕКРЕТАРЯ-РЕФЕРЕНТА – ЛИЧНОГО ПОМОЩНИКА РУКОВОДИТЕЛЯ 69.68 KB
  В России должность секретаря появляется в XVIII веке сначала как должность личного секретаря императора в Толковом словаре В. Понятие секретарь сегодня достаточно сложное и имеет много градаций -– от секретаря-помощника руководители секретаря-референта ученого секретаря...
77666. Противоречия техногенной цивилизации 97.5 KB
  Если инженерное техническое проектирование имеет дело с разработкой процессов описанных в естественных или технических науках то другие виды проектирования архитектурное градоcтроительное дизайнерское организационное и т.