75668

Лінійні динамічні структури. Списки

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

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

На початку програми виводиться список, створений у програмі. Список записується у файл output.txt. Після натиснення клавіші відбувається сортування списку за значенням числового поля-ключа (тут поле вік (age)) за допомогою функції

Украинкский

2015-01-24

365.01 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №4 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013


Тема: Лінійні динамічні структури. Списки.

 

Мета:  Засвоїти знання про лінійні динамічні структури даних на прикладі реалізації АТД Список. Сформувати уміння і навички обробки списків.

Завдання:

Варіант № 9 (1). Реалізувати процедуру побудови списку, значущі елементи якого зберігаються у файлі F

а) F: File of Record Key: Integer; Data: Real End; зі збереженням порядку розташування елементів у файлі. Оцінити складність алгоритму за часом.

б) F: File of Record Key: Integer; Data: Real End; Список повинен бути упорядкований за значеннями полів Key. Оцінити складність алгоритму за часом.

Опис алгоритму виконання

На початку програми виводиться список, створений у програмі. Список записується у файл output.txt. Після натиснення клавіші відбувається сортування списку за значенням числового поля-ключа (тут поле вік (age)) за допомогою функції Person::Sort(). Відсортований список записується у файл sorted_1.txt. Після того з підготовленого файлу input.txt виводяться нові елементи у список (додаються до існуючого списку). Після сортування вже нового списку, доповнений і впорядкований, він записується у файл sorted_2.txt.

Складність алгоритму

Складність алгоритму дорівнює О( 8N2 + 3N + 4) від деякого часу виконання T.  


Блок-схема алгоритму

 


Лістинг програми

#include <iostream>

#include "string"

#include "fstream"

using namespace std;

class Person

{

protected:

public:

int age;  // key

float weight;  // data

static Person *begin; // pointer to the beginnig of list

Person *next;  // pointer to the next element of list

public:

Person(int _age, float _weight);

Person(void);

Person(const Person &arg);

virtual ~Person(void);

virtual void Show(void);

static void Add(Person *n);

static void ShowList();

static void Sort(void);

friend ofstream & operator<< ( ofstream &out, Person *a);

friend ifstream & operator>> ( ifstream &in, Person *a);

};

Person *Person::begin;

Person::Person(int _age, float _weight): age(_age), weight(_weight)

{

next=0;

}

Person::Person(void)

{

   next=0;

}

Person::Person(const Person &arg)  //copy ctor

{

   age=arg.age;

   weight=arg.weight;

   next=0;

}

Person::~Person(void)

{

}

void Person::Show(void)

{

   cout<<"Age: "<<age<<" weight: "<<weight<<endl;

}

void Person::Add(Person *n)

{

Person *a;

if(begin!=0)

{

 a = begin;

 while(a->next!=0)

 {

  a=a->next;

 }

 a->next=n;

}

else

{

 begin = n;

}

}

void Person::ShowList()

{

Person *a;

a = begin;

while (a!=0)

{

 a->Show();

 cout<<endl;

 a=a->next;

}

}

void Person::Sort(void)

{

   Person *current=begin;

   bool isDone=false;

   while(!isDone)

   {

       Person *prev=0;

       isDone=true;

       current=begin;

       while(current->next!=0)

       {

           if(current->age > current->next->age)

           {

               isDone=false;

               if(prev==0)

               {

                   begin=current->next;

                   current->next=begin->next;

                   begin->next=current;

                   prev=begin;

               }

               else

               {

                   Person *temp=current->next->next;

                   prev->next=current->next;

                   prev=current->next;

                   prev->next=current;

                   current->next=temp;

               }

           }

           else

           {

               prev=current;

               current=current->next;

           }

       }

   }

}

ifstream & operator>> ( ifstream &in, Person *a)

{

if (a!=0)

{

 string st;

 in>>st;

 in>>a->age;

         in>>st;

 in>>a->weight;

 in>>st;

}

   return in;

}

ofstream & operator<< ( ofstream &out, Person *a)

{

   a = a->begin;

while (a!=0)

{

out<<"Age: \n"<<a->age<<endl;

out<<"Weight: \n"<<a->weight<<endl;

out<<"~~~~~~~~~~~~~~~~";

if(a->next!=0)

       out<<endl;

   a=a->next;

}

return out;

}

int main()

{

   cout<<"\tList of data: \n\n";

Person *a; a= new Person(9, 24.3);

Person *b; b= new Person(5, 30.8);

Person *c; c= new Person(6, 33.5);

Person *d; d= new Person(7, 36.5);

Person::Add(a);

Person::Add(b);

Person::Add(c);

   Person::Add(d);

Person::ShowList();

Person *p = a;

   ofstream out("output.txt");

out<<p;

out.close();

   cout<<"\nTo sort list press 1: ";

   int com=0;

   cin>>com;

   if(com!=1) return 0;

   cout<<"\n------- Sorted list by key (age)-------\n\n";

Person::Sort();

Person::ShowList();

ofstream outsort("sorted_1.txt");

outsort<<p;

outsort.close();

   cout<<"\nTo load list from file press 1: ";

   com=0;

   cin>>com;

   if(com!=1) return 0;

   ifstream inp("input.txt");

   while(!inp.eof())

   {

       Person *p=new Person();

       inp>>p;

       Person::Add(p);

   }

   inp.close();

cout<<"\n------- List from file -------\n\n";

Person::ShowList();

   cout<<"\nTo sort list press 1: ";

   com=0;

   cin>>com;

   if(com!=1) return 0;

   cout<<"\n------- Sorted list from file by key (age)-------\n\n";

Person::Sort();

Person::ShowList();

ofstream outsort_2("sorted_2.txt");

outsort_2<<p;

outsort_2.close();

cout<<endl;

delete a;

delete b;

delete c;

delete d;

return 0;

}

Результат виконання

Висновки

Засвоїли знання про лінійні динамічні структури даних на прикладі реалізації АТД Список. Сформували уміння і навички обробки списків. В результаті виконання лабораторної роботи побудовано структуру даних список, значущі елементи якого зберігаються у файлі.


 

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

82558. Движение военно-исторической реконструкции в России (на примере Екатеринбургского военно-исторического клуба «Горный щит») 170.32 KB
  Воспитание патриотизма на примерах истории рубежа XX – XXI вв. сопряжено с рядом негативных явлений, охвативших часть общества. К ним можно отнести психологические потрясения, пронизывавшие Россию в последние 15-20 лет; разрушение прежних нравственных ориентиров российского общества...
82559. СОВЕРШЕНСТВОВАНИЕ ПРАВОВОГО РЕГУЛИРОВАНИЯ ИПОТЕЧНЫХ ОТНОШЕНИЙ В РОССИЙСКОЙ ФЕДЕРАЦИИ 394.5 KB
  Правовое регулирование ипотеки. Общая характеристика правового регулирования ипотеки. Коллизии правового регулирования ипотеки зданий сооружений расположенных на земельном участке. Правовое регулирование ипотеки зданий и земельного участка.
82560. Разработка алгоритма подсчета контрольных сумм в RAID-подобных массивах с ненадежными и медленными каналами связи между устройствами хранения данных 229.55 KB
  Одним из возможных применений могут быть системы хранения данных СХД. В распределенных СХД появляется проблема передачи данных между устройствами если они расположены далеко друг от друга или соединены медленными и не надежными каналами связи.
82561. Моделирование процессов полирования оптических деталей на станках с ЧПУ 12.23 MB
  Объектом моделирования включает в себя процесс полирования поверхности оптических деталей а также автоматизацию анализа входных данных с поверхности линзы расчёта оптимального способа обработки оптических деталей генерации и записи кода ISO для станка с ЧПУ.
82562. Быстрое сравнение по образцу и обучение в глубину с помощью диаграмм решений 259.19 KB
  Машинное обучение – раздел информатики изучающий методы построения моделей, способных обучаться. Различают два типа обучения: обучение по прецедентам, или индуктивное обучение, т.е. выделение закономерностей в экспериментальных данных, и дедуктивное обучение, предполагающее формализацию знаний экспертов.
82563. Разработка мероприятий, направленных на повышение рентабельности ООО Поликлиника «А-3» 943.5 KB
  Целью любого предприятия является прибыль, она же, соответственно, является и важнейшим объектом экономического анализа. Однако сам размер прибыли не может охарактеризовать эффективность использования предприятием своих ресурсов. Одним из основных показателей, характеризующих эффективность работы предприятия, является рентабельность.
82564. Определение апостолом Петром теологической концепции несправедливого страдания последователей Иисуса Христа 518.08 KB
  Автор работы выбрал Первое Послание святого Апостола Петра потому, что тема страданий в этом Послании встречается чаще, чем в других книгах Нового Завета. Первое Послание наиболее подходит для рассмотрения данной темы, т.к. Апостол Пётр, предвидя грядущие страдания последователей Иисуса Христа...
82565. Совершенствование системы оценки и аттестации персонала на предприятии (на примере ООО «ПромСтройТорг») 469 KB
  При переходе к рынку происходит медленный отход от иерархического управления, жесткой системы административного воздействия, практически неограниченной власти к рыночным взаимоотношениям, отношениям собственности, базирующимся на экономических методах управления.
82566. PR-ПРОДВИЖЕНИЕ ФЕРМЕРСКИХ ПРОДУКТОВ НА ТЕРРИТОРИИ МОСКВЫ И МОСКОВСКОЙ ОБЛАСТИ В ПЕРИОД С 2012 ПО 2013 ГОД 3.36 MB
  Сегодня у компании уже есть четыре точки сбыта в разных районах Москвы отработанная система заказов через сайт компании с доставкой по Москве база постоянных клиентов и самое главное - перспективы для дальнейшего роста. Предмет: PR-инструменты в сфере продвижения фермерских продуктов на опыте компании Пенка.