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;

}

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

Висновки

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


 

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

10135. Русская философия о науке 43.5 KB
  Русская философия о науке. Особенность российского науковедения образуют три возобновляющиеся идеи. 1 Наука в России воспринималась как извне пришедшее в культуру иностранное нововведение. Она была завезена в Россию Петром 1. Сомнение в органичности науки в росси...
10136. Сущность и соотношение интернализма и экстернализма как теоретических моделей развития науки 36 KB
  Сущность и соотношение интернализма и экстернализма как теоретических моделей развития науки ЭКСТЕРНАЛИЗМ его сторонники считают что основными факторами определяющими рост знания являются социальные экономические технические и культурные причины и пот
10137. Направления и уровни экстерналистского анализа науки 29.5 KB
  Направления и уровни экстерналистского анализа науки. Экстернализм рассматривает науку как часть культуры своего времени и признает что на ее содержание существенно влияют негносеологические факторы: экономика политика религия мораль искусство психология ли
10138. Сущность и соотношение кумулятивизма и антикумулятивизма как теоретически моделей развития науки 38 KB
  Сущность и соотношение кумулятивизма и антикумулятивизма как теоретически моделей развития науки. Проще всего представить развитие науки как рост знаний: наука на каждом историческом этапе приобретает некоторое количество сведений откладывает их в свою копилку на...
10139. Формирование некумулятивной теоретической модели развития науки: К.Поппер, Т.Кун, И.Лакатос 42.5 KB
  Формирование некумулятивной теоретической модели развития науки: К.Поппер Т.Кун И.Лакатос. Некумулятивная модель развития науки сформировалась в середине ХХ в. Койре один из авторов стоящих у ее истоков, другие Г.Башляр К. Поппер Т. Кун И. Лакатос Дж. Холтон.
10140. Наука как вид познания. Понятия вненаучного знания 38 KB
  Наука как вид познания. Понятия вненаучного знания. Наука как познавательная деятельность. Как и другие способы познания наука возникает из практической деятельности людей. Она является непосредственным продолжением обыденного стихийно-эмпирического познания в х...
10141. Особенности научного знания. Основные подходы к проблеме критериев научности в современной философии наук 36.5 KB
  Особенности научного знания. Основные подходы к проблеме критериев научности в современной философии наук Проблема отличия науки от других форм познавательной деятельности – это проблема демаркации т.е. поиск критериев разграничения научного и ненаучного знаний....
10142. Возникновение науки как теоретико-философская и историко-научная проблема 37 KB
  Возникновение науки как теоретикофилософская и историконаучная проблема Как своеобразная форма познания специфический тип духовного производства и социальный институт наука возникла в Европе в Новое время в XVIXVII вв. в эпоху становления капиталистического с
10143. Античная ученость: факторы формирования, особенности, предметная направленность и основные достижения 38.5 KB
  Античная ученость: факторы формирования особенности предметная направленность и основные достижения Предпосылкой возникновения научных знаний многие исследователи истории науки считают миф. В нем как правило происходит отождествление различных предметов я...