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;

}

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

Висновки

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


 

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

17320. Робота з XML-документами 22.45 KB
  Парадигми програмування Кредит 2 Лабораторна робота 6. Робота з XMLдокументами Мета роботи: Створення і обробка XMLдокументів Завдання для самостійної роботи 1. Виконати приклади лекцій 910 і продемонструвати їхню роботу. 2. Створити проекти з аналогічною функц...
17321. Основы XML 470 KB
  PAGE 13 Лекция 7. Основы XML План 1. Определение и структура XMLдокумента 2. Создание XMLдокумента 3. Способы отображения XMLдокумента. 4. Правила создания корректного XMLдокумента 1. Определение и структура XMLдокумента Любой документ можно представи
17322. Работа с XML в .NET 399.72 KB
  Лекция 8. Работа с XML в .NET План 1. Классы для работы с XML .NET 2. Чтение и запись потоков данных Xml 2.1. Использование класса XmlReader 2.2. Методы чтения данных 2.3. Контроль типов данных при чтении Xmlдокумента 3. Создание XMLдокумента в Visual Studio 1. Классы для работы с XML .NET Мно
17323. Создание XML-документов в .NET 123.45 KB
  Лекция 9. Создание XMLдокументов в .NET План 1. Использование класса XmlWriter запись потоков данных Xml 2. Использование DOM в .Net 2.1. Чтение XMLдокумента с помощью XmlNodeList 2.2. Вставка элементов узлов в XML документ 3. Обработка атрибутов 3.1. Извлечение атрибутов с помощью XmlRead...
17324. Элементы функционального программирования в C# 115.85 KB
  Лекция 10. Элементы функционального программирования в C План 1. Элементы функционального программирования в C 2. Делегаты 3. Лямбдавыражения и лямбдафункции 1. Элементы функционального программирования в C Даже из названия функциональное программирован...
17325. Язык LINQ 145.16 KB
  Лекция 11. Язык LINQ План 1. Основы языка LINQ 2. LINQ: обобщения и интерфейсы 3. Основные операции запроса 4. Преобразования данных с LINQ 5. Связи типов в операциях запроса 6. Синтаксис запроса или синтаксис метода 1. Основы языка LINQ Language Integrated Query LINQ проект Microsoft по ...
17326. LINK to SQL 251.7 KB
  Лекция 11. LINK to SQL 10.1.2.1. Общие сведения После ознакомления с основными аспектами работы с запросами в C можно рассмотреть конкретный тип поставщика LINQ LINQ to SQL. Отображение реляционных данных на объектную модель всегда было одной из наиболее сложных проблем при построе...
17327. ПАРАДИГМИ ПРОГРАМУВАННЯ 3.17 MB
  ПАРАДИГМИ ПРОГРАМУВАННЯ Конспект лекцій 8.080401: Інформаційні управляючі системи та технології Освітньокваліфікаційний рівень магістр ТЕМА 1. ПАРАДИГМА ІМПЕРАТИВНОГО ПРОГРАМУВАННЯ Лекція 1. Огляд парадигм програмування 1.1 Базові поняття і визначення Перш ...
17328. ПРЕДМЕТ І ЗАВДАННЯ КУРСУ ПОЛІТЕКОНОМІЇ 85.5 KB
  ПРЕДМЕТ І ЗАВДАННЯ КУРСУ ПОЛІТЕКОНОМІЇ 1. Предмет курсу Економічне життя суспільства є надзвичайно багатогранним. Його вивчає система економічних наук які включають науки про загальні закони економічного розвитку галузеві економічні науки науки що розглядають конкр...