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;

}

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

Висновки

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


 

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

43451. Проектирование системы для измерения расхода по методу переменного перепада давления 147.5 KB
  Описание принципа измерения расхода по методу переменного перепада давления Расчет и выбор сужающего устройства Датчики давления серии Метран44ДД Список использованных источников Введение Одним из самых распространенных принципов измерения расхода жидкостей газов и паров является принцип переменного перепада давления на сужающем устройстве.
43452. Характеристика уровня проявления тревожности в дошкольном возрасте 1.23 MB
  Определенный уровень тревожности естественная и обязательная особенность активной деятельной личности. У каждого человека существует свой оптимальный или желательный уровень тревожности это так называемая полезная тревожность. Однако повышенный уровень тревожности является субъективным проявление неблагополучия личности.
43453. Основные направления повышения эффективности использования персонала предприятия ОАО «Рыбокомплекс» 560.76 KB
  Анализ производительности труда Достаточная обеспеченность предприятия нужными трудовыми ресурсами их рациональное использование высокий уровень производительности труда имеют большое значение для роста объема производства и повышения эффективности финансово-хозяйственной деятельности предприятия.
43454. Расчет регулирующего органа для регулирования расхода воды на баке циркуляции ц.№ 38 «АВИСМА» ФИЛИАЛ ОАО «КОРПОРАЦИЯ ВСМПО – АВИСМА» 152.5 KB
  Исполнительное устройство – это одно из звеньев автоматических систем регулирования предназначенных для непосредственного воздействия на объект регулирования. В общем случае исполнительное устройство состоит из исполнительного механизма и регулирующего органа....
43455. Исследование и программная реализация методов и алгоритмов теории графов 102.5 KB
  Расчетно-графическая работа представляет собой решение задачи по нахождению минимального пути в графе из заданной вершины x в заданную вершину y, содержащего не более чем k дуг. Расчет выполнен с помощью языка программирования Pascal 7.1 на ПК Pentium3.
43456. ПОДХОДЫ И МЕТОДЫ ФОРМИРОВАНИЯ ТАРИФОВ НА ЭЛЕКТРОЭНЕРГИЮ ДЛЯ ПРОМЫШЛЕННЫХ ПОТРЕБИТЕЛЕЙ 4 MB
  Современное состояние топливно-энергетического комплекса (ТЭК) во многом является следствием результатов осуществления экономических реформ. Наметившийся экономический рост в РФ требует увеличения инвестиций в субъекты экономики, важнейшим источником которых являются собственные средства предприятий, формируемые в основном за счет прибыли, на размер которой значительно влияет уровень тарифов на электроэнергию.
43457. Сущность основных фондов предприятия и разработка основных направлений улучшения их использования 4.09 MB
  Основные фонды участвуют в процессе производства длительное время, обслуживают большое число производственных циклов и, постепенно изнашиваясь в производственном процессе, частями переносят свою стоимость на изготовляемую продукцию, сохраняя при этом натуральную форму.
43458. Расчет параметров и выбор силового трансформатора 363.5 KB
  скорость нарастания напряжения в закр. Построение регулировочной характеристики Регулировочная харктеристика управляемого выпрямителя это зависимость средневыпрямленного значения напряжения U0 от угла регулирования . При возрастании входного напряжения U1 или уменьшении тока нагрузки увеличивают угол регулирования для поддержания постоянства напряжения в нагрузке U0 в заданных пределах. При этом реактивную составляющую напряжения короткого замыкания трансформатора и питающей сети примем равным 10.
43459. Трудовые ресурсы и их использование в СПК «Трудовик» Судиславского района Костромской области 150 KB
  Достаточная обеспеченность сельскохозяйственных предприятий необходимыми трудовыми ресурсами их рациональное использование высокий уровень производительности труда имеют большое значение для увеличения объема производства продукции и повышения эффективности производства. Значение и состояние трудовых ресурсов в России К трудовым ресурсам относится та часть населения которая обладает необходимыми физическими данными знаниями и навыками труда в соответствующей отрасли. Достаточная обеспеченность предприятий нужными трудовыми...