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;

}

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

Висновки

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


 

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

71813. ПОНЯТИЕ, СОДЕРЖАНИЕ И КОНСТИТУЦИОННО-ПРАВОВЫЕ ОСНОВЫ ЗАЩИТЫ ПРАВ ЧЕЛОВЕКА ОТ ПРИЧИНЕНИЯ МОРАЛЬНОГО ВРЕДА 184.5 KB
  Основной закон России Конституция исходит из признания высшей ценностью человека его прав и свобод ст. Право лица на восстановление его нарушенного интереса возмещение имущественного ущерба и компенсацию морального вреда гарантированно статьей 46 Конституции и может быть...
71814. НАЛОГ КАК КАТЕГОРИЯ НАЛОГОВОГО ПРАВА 92 KB
  Одной из актуальных проблем налогового права выступает необходимость скорейшего совершенствования и унификации понятийного аппарата в сфере правового регулирования налогообложения. Обращаясь в связи с этим к рассмотрению налогово-правовой категории налога необходимо...
71815. ЭВОЛЮЦИЯ НАЛОГОВО-ПРАВОВЫХ МЕТОДОВ РЕГУЛИРОВАНИЯ ЭКОНОМИКИ СУБЪЕКТА РОССИЙСКОЙ ФЕДЕРАЦИИ С НАЧАЛА 90-Х ГОДОВ XX ВЕКА 145 KB
  В начале 90-х годов произошло существенное изменение роли налогов в экономике России. наделение субъектов Федерации самостоятельными источниками доходов и самостоятельными направлениями их расходования.
71816. ОРГАНИЗАЦИОННО-ТАКТИЧЕСКИЕ ОСНОВЫ РАБОЧЕГО И ЗАКЛЮЧИТЕЛЬНОГО ЭТАПОВ НАЛОЖЕНИЯ АРЕСТА НА ИМУЩЕСТВО 103.5 KB
  Рабочий этап наложения ареста на имущество складывается из трех последовательно сменяющих друг друга стадий предварительной обзорной и детальной. Предварительная стадия включает в себя ряд последовательно выполняемых действий в число которых входят: прибытие на место производства...
71817. Банковская система и её роль в национальной экономике. Особенности её развития в РБ 483.22 KB
  Объект исследования банковская система в Республике Беларусь. Предмет исследования деятельность банков в рамках национальной банковской системы. Цель работы: изучить состояние а также выявить перспективы банковской системы в Республике Беларусь.
71818. Проектирование системы отопления в доме отдыха поездных бригад на узловой станции 361 KB
  Исходные данные для проектирования Теплотехническая часть Наружная стена (НС) Наружные и входные двери (НДВ) Бесчердачное перекрытие-потолок (ПТ) Перекрытие над неотапливаемым подвалом (ПЛ) Окна и балконные двери (ОК) Результаты теплотехнических расчетов Определение потерь теплоты помещениями...
71819. Тяговый электродвигатель НБ-514 70.46 KB
  Двигатель тяговый НБ-514 предназначен для индивидуального привода колесных пар электровозов переменного тока через двухстороннюю жесткую косозубую передачу. Подвеска тягового электродвигателя опорно-осевая.
71820. Разработка САУ процессом копчения продуктов 156.5 KB
  В данном курсовом проекте описывается анализ и синтез САУ процессом копчения продуктов с регулятором в контуре управления. Составляются математическое описание объекта управления исполнительных и измерительных устройств.
71821. Понятия информационной технологии, эволюция их роль в развитии экономики и обществе 93.8 KB
  Целью исследования является определение роли информационных технологий в формировании социальное пространства. Достижение цели работы обусловило постановку и решение следующих взаимосвязанных задач: охарактеризовать этапы развития компьютерных технологий...