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


 

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

22682. Атоми у зовнішніх полях. Ефект Зеємана 340.5 KB
  Суть: розщеплення спектральних ліній обумовлене взаємодією атомів з магнітним полем. Розщеплення спектральних ліній в магнітному полі є наслідком розщеплення енергетичних рівнів. простий ефект : правила відбору: три лінії:лінія двікомпоненти Складний ефект: розглянемо основний і перший збуджений...
22683. Теорія молекули водню. Обмінна взаємодія 72 KB
  Тоді рня Шредінгера для електронів при фіксованих ядрах: Нульове наближення: V΄=0атоми віддалені: R= тоді V=V1 V2 . та теж буде розв΄язком: Ени нерозрізненні тоді тоді буде: сим. Тоді будуть поправки до енергії різні для сим.
22684. Принцип роботи прискорювачів заряджених частинок 42 KB
  2 R радіус орбіти частинки в магнітному полі m маса чки c швидкість світла H напруження магн. Металева сфера заряджена до великого потенціалу і частинки виходять з неї через трубку; енергія частинок десь 28 Мев. Підвищення енергії частинки частинки майже вдвічі можливе при використанні каскадних електростатичних прискорювачів. Циклотрон складається з секторних електродів дуантів перпендикулярно до яких прикладено сильне однорідне магнітне поле яке потрібне для задання циклічної траєкторії частинки.
22685. Сучасні уявлення про ядерні сили. Моделі атомного ядра 43.5 KB
  Моделі атомного ядра. де І момент інерції повний момент ядра враховує деформацію ядра при обертанні. В основі моделі лежить припущення про те що нуклони рухаються в самоузгодженому полі задача стає одночастинковою самоузгодження сили взаємодії між нуклонами замінюють на загально силовий центр тобто вводять середнє для всіх нуклонів ядра поле. Спектр ядра розбитий на групи близьких рівнів з великими проміжками між групами.
22686. Міжнародні комерційні операції 36.5 KB
  Проблеми: відбувається неодночасно тобто одна сторона в багатьох випадках кредитує іншу сторону внаслідок чого виникають ризикові ситуації фірми ризикують отримати непотрібні їм товари. Наприклад Україна експортує до Китаю товари. Китай сплачує ці товари якщо Україна закупить на певну суму виручки товари в Китаї. офсет подібний до зустрічної закупівлі тим що одна сторона погоджується придбати товари і послуги за певний суми виторгу від початкового продажу.
22687. Принципи ЗЕД 26 KB
  Принцип свободи зовнішньоекономічного підприємництва що полягає у праві субєктів зовнішньоекономічної діяльності добровільно вступати у зовнішньоекономічні звязки; праві субєктів зовнішньоекономічної діяльності здійснювати її в будьяких формах які прямо не заборонені чинними законами України; виключному праві власності субєктів зовнішньоекономічної діяльності на всі одержані ними результати зовнішньоекономічної діяльності. Принцип юридичної рівності і недискримінації що полягає у рівності перед законом всіх субєктів...
22688. Облік фінансових вкладень та консолідована звітність 209 KB
  ІНВЕСТИЦІЯ - це актив, яким володіє підприємство з метою збільшення капіталу через розподіл доходу (наприклад, відсотків, роялті, дивідендів та ренти), для зростання вартості капіталу або для інших вигод.
22689. Сальдо платіжного балансу України 30 KB
  обсяги прямих іноземних інвестицій в Україну постійно зростали. З початку 2001 року темпи надходження прямих іноземних інвестицій в Україну уповільнилися. Слід окремо наголосити на тому що значна частина інвестицій надійшла з офшорних зон.
22690. Операції з давальницькою сировиною (толінг) 29.5 KB
  Важлива підстава для віднесення операції до толінгу: сировину яка ввозиться або купується на території країни переробки переробне підприємство вносить під безмитний режим. Основні схеми толінгу: іноземний постачальник сировини оплачує вітчизняному виробникові її переробку стає власником одержаного продукту вивозить його за межі країни і продає на закордонних ринках. давальницька сировина переробляється на підприємстві даної країни з наступним експортом продукту переробки під митним контролем. Толінг: зовнішній внутрішній сировина...