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


 

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

84174. ИММУНОДЕФИЦИТЫ 24.57 KB
  Синдром Вискотта Олдрича наследственное рецессивное заболевание связанное с X хромосомой которое характеризуется экземой тромбоцитопенией и иммунодефицитом. Дефицит Тлимфоцитов может развиваться в ходе болезни при этом уровень IgM в сыворотке снижен. Атаксиятелеангиоэктазия наследственное заболевание передающееся аутосомно рецессивно характеризуемое мозжечковой атаксией телеангйоэктазией кожи и дефицитами Тлимфоцитов Ig и IgE.
84175. ХИМИЧЕСКИЙ ОНКОГЕНЕЗ 25.72 KB
  Канцерогенные вещества это вещества которые достоверно вызывают образование опухоли или по крайней мере вызывают увеличение частоты заболеваемости раком. Большинство канцерогенных химических веществ вызывают изменения в ДНК включающее повреждение пуриновых и пиримидиновых оснований делецию хромосом разрывы цепей и образование перекрестных связей. Небольшое количество канцерогенных химических веществ действуют эпигенетически т.
84176. ОНКОГЕНЕЗ 24.74 KB
  Ультрафиолетовое излучение играет роль в возникновении различных видов рака кожи включая плоскоклеточный рак базальноклеточный рак и злокачественную меланому. Поэтому грудные дети с респираторным дистресссиндромом подвергались лучевой терапии шеи для уменьшения размеров тимуса что привело к возникновению у большого количества этих детей папиллярного рака щитовидной железы через 15 25 лет. Торотраст радиоактивный препарат накапливается в печени и увеличивает риск возникновения нескольких типов рака печени включая ангиосаркому...
84177. УЧЕНИЕ ОБ ОПУХОЛЯХ 25.15 KB
  Признаки дисплазии. Изменения цитоплазмы: цитоплазматические нарушения при дисплазии возникают изза нарушения нормальной дифференцировки; увеличение скорости деления клеток; нарушенное созревание диспластические эпителиальные клетки сохраняют сходство с базальными стволовыми клетками несмотря на продвижение их вверх в эпителии т. Риск возникновения инвазивного рака зависит от: выраженности дисплазии; продолжительности дисплазии; локализации дисплазии. Отсутствие инвазивности: аномальная ткань при дисплазии и crcinom in situ не...
84178. МОРФОЛОГИЯ ОПУХОЛЕЙ 27.97 KB
  Паренхима собственная ткань опухоли составляющая главную ее массу и определяющая ее рост и характер. Установлено что в клетках опухоли нарушена продукция кейлонов которые в нормальных условиях регулируют митотическую активность клеток и действуют как ингибиторы клеточного деления. Это своеобразие обмена опухоли усиливает ее сходство с эмбриональной тканью в которой также преобладают явления анаэробного гликолиза. они выступают в роли маркеров опухоли; они могут привести к возникновению клинических проявлений паранеопластических...
84179. МЕТАСТАЗЫ 23.43 KB
  Метастазирование складывается из пяти этапов: проникновение опухолевых клеток в просвет кровеносного или лимфатического сосуда; перенос опухолевых клеток током крови или лимфы; остановка опухолевых клеток на новом месте; выход опухолевых в периваскулярную ткань; рост метастаза. Попадание опухолевых клеток в кровоток как полагают происходит на ранних этапах развития многих злокачественных новообразований. Метастаз возникает только тогда когда в тканях остается в живых достаточное количество опухолевых клеток.
84180. ОБЩЕЕ УЧЕНИЕ ОБ ОПУХОЛЯХ 24.77 KB
  Различают три вида роста опухоли: экспансивный; инфильтративныи; аппозиционный. Экспансивный рост опухоли обычно медленный характерен для зрелых доброкачественных опухолей. При инфильтративном росте клетки опухоли врастают в окружающие ткани и разрушают их.
84181. ЭПИТЕЛИАЛЬНЫЕ ОПУХОЛИ. ПАПИЛЛОМА 25.39 KB
  Кроме того плотность папилломе может придавать характер строения паренхимы например папилломы в которых паренхима имеет строение плоскоклеточного ороговевающего эпителия всегда по консистенции плотные. вокализуются папилломы на коже слизистых оболочках выстланных переходным или неороговевающим эпителием. Наибольшее клиническое значение имеют папилломы гортани и мочевого пузыря. Папилломы детей и подростков или ювенильные папилломы чаще всего бывают множественными папилломатоз гортани.
84182. ЭПИТЕЛИАЛЬНЫЕ ОПУХОЛИ. АДЕНОМА. КИСТЫ 26.24 KB
  КИСТЫ Аденома Кисты Аденома зрелая доброкачественная опухоль из железистого эпителия. Иногда в опухоли обнаруживаются кисты в этих случаях говорят о кисто или цистоаденоме. Макроскопически они имеют вид кисты. Различают кисты: однокамерные однополостные; многокамерные многополостные.