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;

}

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

Висновки

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


 

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

38032. Структура HTML-документа. Создание элементарной WEB-страницы 502 KB
  Для работы с этими текстами был создан специальный протокол HTTP Hyper Text Trnsfer Protocol были обозначены основные элементы языка разметки HTML. Язык HTML развился из стандартного обобщенного языка описания документов SGML и является его производной созданной для разметки текстовых документов. Существуют разные суждения о том считать HTML языком программирования или нет. С точки зрения программистов он имеет достаточно простой синтаксис и довольно легок в изучении но с другой стороны для простого пользователя иногда постижение...
38033. Форматирование текста 44.5 KB
  Форматирование текста Цель работы: используя теги разбивки текста логического и физического форматирования текста создать страницу по данному образцу. Теги разбивки текста h1 т h1 h2 т h2 h3 т h3 h4 т h4 h5 т h5 h6 т h6 заголовки стилей 1 2 3 4 5 6. Атрибут: lign= задает положение текста абзаца на строке. Значения: left выровнять текст по левому краю center выровнять текст по центру right выровнять текст по правому краю.
38034. Работа с цветом фона страницы и цветом шрифта. Задание бегущей строки 159.5 KB
  Работа с цветом фона страницы и цветом шрифта. Контейнер описания шрифта может быть помещен в любой другой контейнер. задает имя шрифта или несколько возможных шрифтов. Броузер берет последующий шрифт если у него нет предыдущего; size= задает размер шрифта.
38035. Нумерованные и маркированные списки 60.5 KB
  Сдвиг один Сдвиг другой Сдвиг сякой Хочу обратить ваше внимание что это прописано без параметра type но при помощи тэга ul : ul li Сдвиг один li ul ul ul li Сдвиг другой li ul ul ul ul ul li Сдвиг сякой li ul ul ul Списки могут быть и вложенными: как это выглядит: Код: тема 1 подтема 1 подтема 2 подподтема подтема 3 тема 2 UL LI тема 1 OL LI подтема 1 LI подтема 2 OL strt= 10 LI подподтема OL LI подтема 3 OL LI тема 2 UL Оформление списков может нумероваться...
38036. Вставка изображений на WEB-страницу 274.5 KB
  Если картинка лежит в поддиректории то ссылка на неё будет выглядеть так img src= путь к картинке название картинки.расширение картинки Для вашего удобства кладите картинку в ту же директорию что и документ тогда путаницы будет меньше и записывать короче img src= название картинки.расширение картинки Если картинка лежит на уровень выше а документ находится в поддиректории то ссылка на неё будет такой: img src= . название картинки.
38037. Гиперссылки 138.5 KB
  href= т ссылка. Атрибуты: href= задает URL адрес. Чтобы по ссылке в левом кадре открылся файл в правом кадре конструкция ссылки в файле загруженном в левый кадр должна быть такой: href= имя файлаимя метки trget= правый указатель ссылки где: имя файла имя файла загружаемого в правый кадр имя метки имя метки в этом файле. Принципы прописывания пути здесь такие же как в случае с картинками: 1 href= prf.
38038. Интегрирование мультимедиа на WEB-страницу 260.5 KB
  Если на странице обнаружен элемент embed или object то производится попытка использовать один из имеющихся плагинов для вывода мультимедиафайла в окне браузера. Применяется созданный компанией Netscpe и получивший широкое распространение элемент embed . Например: embed nme= Moviel src= moviel.com quicktime downlod embed ПРИМЕЧАНИЕ Internet Explorer 5.