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


 

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

39562. Подбор оборудования и проектирование здания Багаевской МГЭС 4.3 MB
  В качестве исходных данных при составлении гидрометеорологической характеристики были использованы материалы многолетних наблюдений Гидрометеослужбы, а также «Основные положения правил использования водных ресурсов Цимлянского водохранилища на р. Дон» и архивные материалы проектных организаций, проводивших изыскания на участке проектирования в предыдущие годы.
39563. Анализ вопросов гражданско-правового регулирования арендных отношений 138.9 KB
  Договор аренды входит в группу сделок, регулирующих отношения по передаче имущества во временное пользование. В отличие от договоров по передаче имущества в собственность, договор аренды не влечет смены титула собственника, а, следовательно, в правовом смысле он оформляет такие отношения товарообмена
39564. Разработка модели анализа структуры затрат на услуги ООО «Противо Пожарная защита» 2.68 MB
  В экономической литературе можно найти множество вариантов снижения затрат на предприятии, однако комплексного подхода для разработки модели анализа структуры затрат на услуги предприятия нет. В связи с этим разработка такой модели является важным и актуальным шагом в изучении экономики предприятия.
39565. Загрузка синхронного транспортногой модуля STM – RR или STM – 1 1.62 MB
  Объединяются 1300 каналов тональной частоты и 6 каналов звукового вещания первого класса в системе с временным разделением каналов и 8ми разрядной импульснокодовой модуляцией. Рассчитать временные и частотные характеристики нарисовать структурную схему объединения и разделения каналов с учетом плезиохронной цифровой иерархии. Рассчитаем частоты дискретизации для каналов ТЧ и звукового вещания. Определим общее число каналов.
39566. Организационная схема предприятия «Вольво» ОАО «Белмагистральавтотранс» 377 KB
  Проверка давления включения и отключения регулятора давления 2. Проверка стояночного тормоза и запорного клапана 3. Проверка педали и тормозного клапана Проверки снаружи 4. Проверка крепления кабины гидросистемы запорных устройств решетки радиатора и механизма подъема кабины 5.
39567. Проект компрессора высокого давления с гладкой проточной частью для ТРДД с тягой 140 кН 1.34 MB
  Описание конструкции КВД 7 3.Описание конструкции КВД. КВД осевой левого вращения восьмиступенчатый приводится во вращение турбиной газогенератора. КВД состоит из следующих узлов: входного направляющего аппарата ВНА; корпуса с направляющим аппаратом 1 ст.
39568. БЛОК УПРАВЛЕНИЯ ВАКУУМНОЙ СИСТЕМЫ УСКОРИТЕЛЯ ЭЛЕКТРОНОВ УРТ-1 12.63 MB
  БЛОК УПРАВЛЕНИЯ ВАКУУМНОЙ СИСТЕМЫ УСКОРИТЕЛЯ ЭЛЕКТРОНОВ УРТ1 ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА БАКАЛАВРА Пояснительная записка 210100. ЭКСПЕРИМЕНТАЛЬНАЯ УСТАНОВКА БЛОК УПРАВЛЕНИЯ ВАКУУМНОЙ СИСТЕМОЙ. Объект исследования: автоматизация контроля и управления вакуумной системы наносекундного ускорителя электронов. Цель работы: разработка блока управления вакуумной системой ускорителя электронов создание программного обеспечения для персонального компьютера предназначенного для управления и отладки блока управления.
39569. Проект мероприятий по увеличению объема реализации услуг предприятия туристического бизнеса ООО «Флагман Груп» г. Москва 238.77 KB
  Основным видом деятельности ООО «Флагман Груп» является осуществление туристической деятельности как внутри Российской Федерации, так и за рубежом.