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;

}

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

Висновки

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


 

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

24857. Рентабельность активов и собственного капитала: расчёт, анализ, оценка 28 KB
  Рента́бельность акти́вов относительный показатель эффективности деятельности частное от деления чистой прибыли полученной за период на общую величину активов организации за период. Показывает способность активов компании порождать прибыль. Рентабельность активов индикатор доходности и эффективности деятельности компании очищенный от влияния объема заемных средств.
24858. Реструктуризация как способ повышения рыночной стоимости компании 32 KB
  Концепция управления стоимостью предприятия ориентирует менеджмент на рост рыночной стоимости компании или рост стоимости имущественного комплекса создаваемого либо развиваемого в инновационных проектах. Различают четыре основных Стандарта оценки бизнеса: обоснованной рыночной стоимости; обоснованной стоимости; инвестиционной стоимости; внутренней фундаментальной стоимости. Стандарт обоснованной рыночной стоимости предполагает что оценка производится на основе информации об имуществе рыночной конъюнктуре и т.
24859. Роль ЗК в управлении компанией 27.5 KB
  полож момент: достаточ широк возм привлеч особ при высоком кредм рейитинге орган налич залога обеспеч роста фин потенциала при необход существенно расшир активов и возраст темпов роста V хоз деят. Урнь этих риско возрт прямопропорц росту удельн веса ЗК активы сформир за счеь ЗК генерир меньшую при прочих равн услях норму П кот сниж на сумму уплачив за кредит высокая зависим ЗК от колеб конъюкт рынка сложность процедуры привлечя особенно больших ров.
24860. Синергетический эффект как рез-т слияния и поглощения 30.5 KB
  Отделение подразумевает передачу части активов и обязательств новому предприятию с последующим предоставлением акционерам материнского предприятия акций нового предприятия пропорционально их доле собственности в первоначальном предприятии. Разбивка все активы реструктурируемого предприятия разделяются между отделяемыми предприятиями и материнское предприятие перестает существовать. В данном случае материнское предприятие учреждает новое предприятие и предает ему свои активы затем продает акции нового предприятия. Данный метод...
24861. Сравнительная характеристика базовых подходов к оценке стоимости бизнеса 30.5 KB
  Существуют 3 подхода к оценке стоимости любого объекта: 1 доходный который опирается на доходность потенциально возможную к получению в будущем; 2 затратный при котором стоимость рассматривается с точки зрения понесенных издержек; 3 сравнительный рыночный при котором возможно получение стоимости оцениваемого объекта через механизм сравнения данного объекта с объектами аналогами. Определение стоимости в данном случае осуществляется по фактически проведенным сделкам. В рамках доходного подхода существуют следующие методы определения...
24862. Сравнительная характеристика типов реструктуризации 25.5 KB
  Основной причиной почему компании стремятся к реструктуризации обычно является низкая эффективность их деятельности которая выражается в неудовлетворительных финансовых показателях в нехватке оборотных средств в высоком уровне дебиторской и кредиторской задолженности. В зависимости от целевых установок и стратегии компании определяется одна из форм реструктуризации: оперативная или стратегическая. Оперативная реструктуризация способствует улучшению результатов деятельности предприятия в краткосрочном периоде и создает предпосылки для...
24863. Средневзвешенная стоимость капитала 29.5 KB
  Если организация финансируется только за счет собственного капитала то стоимость капитала определяется как норма прибыли которую компания предлагает за свои ценные бумаги для поддержания их рыночной стоимости. В случае смешанного финансирования стоимость капитала рассчитывается как средневзвешенная величина составных частей капитала. Средневзвешенная стоимость капитала является основным показателем характеризующим стоимость капитала WACC = S Wj ∙ Kj где WACC – средневзвешенная стоимость капитала Wj – удельный вес капитала jного вида...
24864. Стоимость акционерного капитала на основе модели дисконтированного денежного потока (модель Гордона) 26.5 KB
  Этот темп отражает перспективы развития бизнеса и должен быть заложен в расчёт цены акционерного капитала Сакц=Д Р1Lд дтемп прироста дивидендов. Предприятиеэмитент может не планировать прирост дивидендов а заложить в свои расчёты прогнозы более сложного уровня. Эти прогнозы могут найти отражение в самом ожидаемом размере дивидендов.
24865. Стоимость лицензии: обоснование, расчёт 30.5 KB
  Оценка лицензии необходима при: 1.куплепродаже лицензии; 2.внесении лицензии в уставный капитал; 3.