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;

}

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

Висновки

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


 

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

42987. Контроль технологических процессов при изготовлении интегральных схем 2.57 MB
  Интегральные микросхемы в настоящее время являются одними из самых массовых изделий современной микроэлектроники. Тестовые интегральные микросхемы. Удобство контроля достигается либо последовательным либо параллельным включением в электрическую цепь элементов микросхемы. Тестовые микросхемы состоят из набора нескольких сотен однотипных элементов диодов транзисторов резисторов переходов со слоя на слой пересечений проводников и др.
42988. Разработка многоканального реоофтальмографа 1.85 MB
  Представленный в данном дипломе реоофтальмограф предназначен для диагностики состояния сосудов глаза. Реоофтальмография метод позволяющий количественно оценивать изменения объемной скорости крови в тканях глаза. Такие электроды отличаются малыми габаритными размерами и соответственно малым весом хорошо контактируют с глазным яблоком не оказывают на него давления не вызывают раздражения глаза ни во время исследования ни...
42989. Расчёт и исследование системы стабилизации скорости вращения электродвигателя постоянного тока 736.5 KB
  Принципы управления регулирования на основе которых строятся автоматические системы имеют универсальный характер. Аналогичные принципы например принцип обратной связи заложены в регуляционные системы живых организмов системы управления производством обществом и т.1 Составление по принципиальной схеме структурных схем в динамике и статике Запишем передаточные функции отдельных элементов системы: тиристорный возбудитель: генератор: датчик скорости состоящий из тахогенератора и потенциометра ...
42990. Этапы разработки автоматизированного технологического комплекса для сборки подпятника с шарошкой долота 501.5 KB
  Стандартизация и менеджмент качества продукции. СТАНДАРТИЗАЦИЯ И МЕНЕДЖМЕНТ КАЧЕСТВА ПРОДУКЦИИ Выбор системы менеджмента качества и ее описание. Первой задачей построения той или иной структуры системы менеджмента качества является разработка согласование и публикация соответствующих рабочих процедур координирующих различные виды деятельности влияющие на качество в том числе: проектирование материальнотехническое обеспечение производство продукции и ее сбыт. Для того чтобы система МК выполняла свои функции в отношении...
42991. Проектирование двухступенчатого цилиндрического редуктора для эскалатора 845.5 KB
  Расчет прямозубой передачи Расчет косозубой передачи Расчет валов. Ориентировочный расчет валов Проверочный расчет валов Расчет шпоночных соединений Выбор и расчет подшипников Расчет...
42992. Повышение надежности автогрейдера путем разгрузки шарнира поворота хребтовой балки относительно подмоторной рамы гидроцилиндрами поворота хребтовой балки относительно подмоторной рамы 1.02 MB
  Описание автогрейдера При отделке земляного полотна дороги требуется произвести вырезание кюветов и профилирование поверхности и боковых откосов насыпи и выемок для придания этим элементам дорожного полотна необходимых поперечных и продольных уклонов.
42993. Информационная система Склад 1.54 MB
  Диаграммы вариантов использования предназначены для упрощения взаимодействия с будущими пользователями системы с клиентами и особенно пригодятся для определения необходимых характеристик системы.
42994. Устройство плоскостного биполярного транзистора 1.86 MB
  Движение электронов и дырок в транзисторах типа npn и pnp Поэтому сопротивление эмиттерного перехода мало и для получения нормального тока в этом переходе достаточно напряжения E1 в десятые доли вольта. Вольтамперная характеристика эмиттерного перехода представляет собой характеристику полупроводникового диода при прямом токе см. участка база эмиттер U6э существенно влияет на токи эмиттера и коллектора: чем больше это напряжение тем больше токи эмиттера и коллектора. При этом изменения тока коллектора лишь...