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


 

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

79294. Теории мотивации трудовой деятельности 43.01 KB
  Различают первичные и вторичные потребности. Потребности можно удовлетворить вознаграждениями. Маслоу существует пять основных типов потребностей: физиологические потребности уровень 1; потребность в безопасности уровень 2; социальные потребности уровень 3; потребность в уважении и самоутверждении уровень 4; потребность в самовыражении уровень 5. Маслоу Эти потребности образуют иерархическую структуру которая определяет поведение человека причем потребности высшего уровня не мотивируют человека пока хотя бы частично не...
79295. Мотивация и стимулирование трудовой деятельности персонала 45.96 KB
  Мотивация и стимулирование трудовой деятельности персонала Система стимулирования труда персонала: общие положения и составные части. Система материального стиулирования труда и ее элементы. Основным компонентом материального стимулирования труда является система его оплаты которая осуществляется в двух формах повременной и сдельной рис. Формы оплаты труда Система оплаты труда комплекс взаимосвязанных принципов и методов определления уровня оплаты труда персонала на основе учета количественных и или качественных характеристик...
79296. Оценка результатов труда персонала организации 16.86 KB
  Оценка результатов труда персонала организации Оценка результатов труда одна из функций по управлению персоналом направленная на определение уровня эффективности выполнения работы. Оценка результатов труда является составной частью деловой оценки персонала наряду с оценкой его профессионального поведения и личностных качеств и состоит в определении соответствия результатов труда работника поставленным целям запланированным показателям нормативным требованиям. Оценка труда мероприятия по определению соответствия количества и качества...
79297. Оценка результатов деятельности подразделений управления персоналом и организации в целом 17.65 KB
  Оценка деятельности кадровой службы организации базируется на определении того насколько она способствует достижению целей организации и выполнению поставленных перед ней задач. Показатели оценки эффективности деятельности подразделений управления персоналом Показатели собственно экономической эффективности Показатели степени укомплектованности кадрового состава Показатели степени удовлетворенности работников Косвенные показатели эффективности Соотношение издержек необходимых для обеспечения организации квалифицированной рабочей силой...
79298. Оценка затрат на персонал 77.93 KB
  Они выступают в виде выплаты денежных вознаграждений дополнительных расходов на содержание персонала осуществляемых в соответствии с действующими законами и тарифными соглашениями или добровольных социальных услуг предприятия. В составе расходов на персонал можно выделить следующие группы: Общие расходы на рабочую силу складываются из прямых и косвенных затрат. Косвенные затраты обусловлены необходимостью возмещения дополнительных расходов по выплате страховых взносов в социальные фонды в том числе в фонды защиты от безработицы в связи...
79299. Оценка социальной и экономической эффективности проектов совершенствования системы и технологии управления персоналом 47 KB
  Социальная эффективность проектов проявляется в возможности достижения позитивных, а также избежания отрицательных с социальной точки зрения изменений в организации.
79300. Аудит персонала 14.12 KB
  Аудит персонала Аудит персонала система консультационной поддержки аналитической оценки и независимой экспертизы кадрового потенциала организации. Задачи аудита персонала: определить соответствие организационного и кадрового потенциала целям и стратегии развития организации; выявить соответствие деятельности персонала и структуру управления организации существующей нормативноправовой базе; определить эффективность работы с персоналом по решению задач стоящих перед персоналом организации ее руководством отдельными структурными...
79301. Теории управления о роли человека в организации 15.74 KB
  В связи с тем что теории управления персоналом человеческими ресурсами развивались вместе с различными школами управления последние наложили отпечаток на название первых. За более чем столетие период промышленной революции роль человека в организации существенно менялась поэтому развивались уточнялись и теории управления персоналом. В настоящее время различают три группы теорий: классические теории теории человеческих отношений и теории человеческих ресурсов.
79302. Трудовые ресурсы, персонал и трудовой потенциал организации 15.54 KB
  Работающие собственники и совладельцы организации включаются в состав персонала если они кроме причитающейся им части доходов получают соответствующую оплату за то что участвуют своим личным трудом в деятельности организации; обладание определенными качественными характеристиками профессией специальностью квалификацией компетентностью и др. обеспечение достижения целей организации путем установления адекватных им целей отдельного работника и создания условий для их эффективной реализации. К ним относятся: акционеры не работающие в...