Динамические структуры данных

 

Динамические структуры данных могут создаваться, изменять свой размер и уничтожаться в процессе выполнения программы [1, 4]. Динамические структуры, как и обычные структуры, состоят из полей. Кроме информационных полей они обязательно содержат поля-указатели на свой собственный тип структуры. При этом указатель указывает на структуру целиком, а не на отдельные элементы структуры. Рассмотрим следующие динамические структуры данных: списки, очереди, стеки.

 

 

Односвязные списки

 

При работе с совокупностью данных обычно используются массивы. Их преимущество очевидно, когда используется циклическая обработка информации. Если при работе с информацией приходится менять порядок элементов, то использование массивов приводит к большим затратам времени, так как приходится перемещать значительные объёмы информации. Например, необходимо создать список фамилий (рис. 11.1).

 

	Афанасьев
	Бирюкова
	Васильева
	Миронов
	Сергеева
	Яковлева

 

Рис. 11.1. Исходный список фамилий

 

При внесении дополнительной фамилии «Баринова» (рис. 11.2), необходимо будет переместить все фамилии, начиная со второй, на одну позицию ниже. При больших списках это может занимать значительное время.

 

	Афанасьев
	Баринова
	Бирюкова
	Васильева
	Миронов
	Сергеева
	Яковлева

 

Рис. 11.2. Список с добавленной фамилией «Баринова»

 

 

Если в новом списке нужно удалить фамилию «Васильева» (рис. 11.3), то также возникает необходимость в перемещении информации, что тоже приводит к значительным затратам времени.

 

 

	Афанасьев
	Баринова
	Бирюкова
	Миронов
	Сергеева
	Яковлева

 

Рис. 11.3. Список с удаленной фамилией «Васильева»

 

Для более эффективной работы с такими списками лучше использовать структуру. Содержимое её полей можно разделить на две части. Одна содержит информацию о конкретном объекте, а другая (указатель) содержит адрес, по которому находится следующий объект. Таким образом, данный связный список представляет собой отдельные записи, связанные между собой указателями, и называется односвязным (однонаправленным) списком. Схематически его можно изобразить так, как показано на рис. 11.4, где указатель first совпадает с адресом первого элемента списка.

 

 

Рис. 11.4. Схематическое изображение односвязного списка,

представленного на рис. 11.3

 

Если нужно внести в список новую фамилию, то, двигаясь по списку, сначала необходимо определить те элементы, между которыми должна быть вставлена новая фамилия. Пусть необходимо добавить новую фамилию «Васильева», находящуюся под условным номером «7», в список, представленный на рис. 11.3. Передвигаясь по списку, определяем, что данная фамилия должна находиться между фамилиями «Бирюкова» и «Миронов».

В этом случае в поле адреса третьего элемента должен быть адрес седьмого элемента, а в поле адреса седьмого элемента необходимо занести адрес четвертого элемента (рис.11.5) [4].

 

 

Рис. 11.5. Схематическое изображение списка при добавлении новой фамилии

«Васильева» в список, представленный на рис. 11.3

 

Если необходимо удалить кого-либо из списка, то, двигаясь по списку, нужно найти этот объект и перестроить связи таким образом, чтобы данный элемент был исключен из списка. Не следует забывать, что необходимо освобождать память, выделенную под этот элемент. Пусть в списке, представленном на рис.11.5, удаляется фамилия «Афанасьев», которая идет первой в односвязном списке. Тогда следует перенастроить указатель first и освободить место, занимаемое этим объектом. Если удаляется фамилия внутри списка (например, «Миронов»), то связь объекта «7.Васильева» перенаправляется по связи удаляемого объекта.

Структура для описания таких объектов может иметь вид:

 

struct persona { char *name; // Фамилия человека

persona *next; // Указатель на следующий объект

};

 

Следует обратить внимание на то, что структура persona используется до конца ее описания. Это единственный случай нарушения принципа использовать лишь то, что описано выше. Это сделано для того, чтобы создавать такую структуру данных.

Листинг 11.1. В программе формирующий односвязный список, состоящий из фамилий, которые вводятся с клавиатуры. Отметим, что фамилии следует вводить на английском языке. Затем из сформированного списка удаляется указанная фамилия.

 

 

Файл “stdafx.h”

#pragma once

 

#define WIN32_LEAN_AND_MEAN

#include <stdio.h>

#include <tchar.h>

#include <string.h>

#include <iostream>

using namespace std;

 

Файл “Spisok.h”

// Структура, описывающая объект односвязного списка:

struct persona

{

char *name;

persona *next;

};

 

// Прототип функции, добавлябщей новый элемент в односвязный список:

persona* add_persona(persona*first, char* new_name);

 

// Прототип функции, удаляющей элемент из односвязного списка:

persona* del_persona(persona*first, char* del_name);

 

// Прототип функции печати односвязного списка:

void print_persona(persona*first);

 

//L10_1.cpp

#include "stdafx.h"

#include "Spisok.h"

persona* add_persona(persona*first, char* new_name)

{

persona*ptr,*prev,*new_el;

// Создание нового элемента списка:

new_el=new persona;

// Заполнение информационной части объекта:

(*new_el).name=strdup(new_name);

// Поле связи нулевое. В процессе встраивания оно при необходимости

// переопределяется:

(*new_el).next=NULL;

// Проверка существования связного списка:

if(first==NULL)

{

// Список пуст и элемент вносится как единственный:

first=new_el;

return first;

}

// Поиск места для нового элемента:

ptr=first;

prev=NULL;

while(ptr && strcmp((*ptr).name, new_name)<0)

{

prev=ptr;

ptr=(*ptr).next;

}

if(prev==NULL)

// Новый элемент должен добавляться в начало списка,

// так как передвижения по списку не было:

{

(*new_el).next=first;

first=new_el;

}

else

// Новый элемент добавляется в середину или в конец списка:

{

(*prev).next=new_el;

(*new_el).next=ptr;

}

return first;

}

 

void print_persona(persona*first)

{

setlocale(LC_CTYPE, ".866");

persona*ptr=first;

while(ptr!=NULL)

{

cout<<(*ptr).name<<'\n';

ptr=(*ptr).next;

}

setlocale(LC_CTYPE,"russian");

 

}

 

persona* del_persona(persona*first, char* del_name)

{

persona*ptr,*prev;

ptr=first;

prev=NULL;

// Поиск удаляемой фамилии:

while(ptr && strcmp((*ptr).name, del_name)!=0)

{

prev=ptr;

ptr=(*ptr).next;

}

if(ptr==NULL) // Фамилия не найдена

{

cout<<"Такой фамилии нет!\n";

return first;

}

if(prev==NULL)

{

// Удаляется первая фамилия списка:

first=(*first).next;

delete (*ptr).name;

delete ptr;

}

else

{

// Удаляется фамилия в середине списка или в конце его:

(*prev).next=(*ptr).next;

delete (*ptr).name;

delete ptr;

}

return first;

}

 

int _tmain()

{ char st[50];

persona *first=NULL,*ptr;

setlocale(LC_CTYPE,"russian");

// Построение односвязного списка:

cout<<"Введите фамилию ";

cin>>st;

do

{

first=add_persona(first,st);

cout<<"Введите фамилию или нажмите 0, если хотите прекратить ввод ";

cin>>st;

}while(strcmp(st, "0")!=0);

// Печать построенного списка:

print_persona(first);

cout<<"Введите удаляемую фамилию ";

cin>>st;

// Удаление фамилии из односвязного списка:

first=del_persona(first,st);

// Печать полученного односвязного списка:

print_persona(first);

cin.get();

cin.get();

 

return 0;

}

 

Результат выполнения программы листинга 11.1 представлен на рис. 11.6.

 

 

Рис. 11.6. Результат работы программы листинга 11.1

 

 

Очереди

 

Очередь – это связный список, закон построения которого следующий: новый элемент всегда ставится в конец списка, а удаление элемента происходит из его начала [4, 32]. Таким образом, очередь является структурой данных, которые организованы по принципу FIFO (First In, First Out) – «Первый пришел – первый вышел». Чтобы не ограничивать максимальное число элементов в очереди, очередь может быть реализована в виде однонаправленного списка. В этом случае объекты очереди имеют такую же структуру, как и объекты однонаправленного списка. Часть полей описывает характеристики конкретного объекта и есть поле типа указатель, которое содержит адрес следующего в очереди элемента.

С очередью связаны два указателя. Один содержит адрес объекта, находящегося в начале очереди, а другой хранит адрес последнего объекта очереди. Первый из них назовем begin, а второй end.

Листинг 11.2. В программе создается очередь из некоторых заданий, характеризующихся номером и длиной выполнения. Структуру этих объектов можно описать так:

 

struct ochered {

int number; // Номер задания

int count; // Объем задания

ochered *next; // Указатель на следующий элемент

};

 

Задания добавляются в очередь и удаляются из очереди.

 

Файл “ stdafx.h”

#pragma once

 

#define WIN32_LEAN_AND_MEAN

#include <stdio.h>

#include <tchar.h>

#include <iostream>

using namespace std;

Файл “Och.h”

struct ochered

{

int number; // Номер задания

int count; // Объем задания

ochered *next; // Указатель на следующий элемент

};

// Прототип функции постановки задания в очередь:

void add_ochered(ochered **begin, ochered **end, int nn, int dl);

// Прототип функции удаления задания из очереди:

void del_ochered(ochered **begin, ochered **end);

// Прототип функции печати содержимого очереди:

void print_ochered(ochered *begin);

Файл “Och.cpp”

#include "stdafx.h"

#include "Och.h"

void add_ochered(ochered **begin, ochered **end, int nn, int dl)

{

ochered *new_el;

// Создание нового элемента:

new_el=new ochered;

(*new_el).number=nn;

(*new_el).count=dl;

(*new_el).next=NULL;

if(*begin==NULL)

{

// Очередь пуста.Элемент добавляется как единственный:

(*begin)=(*end)=new_el;

return;

}

// Добавление нового элемента в очередь:

(**end).next=new_el;

(*end)=new_el;

}

void del_ochered(ochered **begin, ochered **end)

{

ochered *ptr;

ptr=*begin;

if(*begin==NULL)

{

// Очередь пуста:

cout<<"Очередь пуста";

return;

}

// Передвигается начало очереди:

(*begin)=(**begin).next;

// Освобождается место удаляемого элемента:

delete ptr;

}

 

void print_ochered(ochered *begin)

{

ochered *ptr=begin;

cout<<" Номер задания | Его длина"<<'\n';

while(ptr!=NULL)

{

cout.width(12);

cout<<(*ptr).number;

cout.width(18);

cout<<(*ptr).count<<'\n';

ptr=(*ptr).next;

}

}

//L11_2.cpp

#include "stdafx.h"

#include "Och.h"

int _tmain()

{

ochered *begin, *end;

int nn,dl;

setlocale(LC_CTYPE,"rus");

begin=end=NULL;

// Постановка задания в очередь:

cout<<"Введите номер задания и его длину ";

cin>>nn>>dl;

cout<<"Если хотите прекратить ввод введите номер и длину нулевыми\n";

do

{

add_ochered(&begin, &end, nn, dl);

cout<<"Введите номер задания и его длину ";

cin>>nn>>dl;

}while(nn!=0);

print_ochered(begin);

// Удаляется задание из очереди:

del_ochered(&begin, &end);

print_ochered(begin);

cin.get();

cin.get();

return 0;

}

Результат выполнения программы листинга 11.2 представлен на рис. 11.7.

Рис. 11.7. Результат работы программы листинга 11.2

Стеки

 

Стек – это связный список, закон построения которого следующий: новый элемент всегда ставится в начало списка, удаление элемента также происходит из его начала [4, 32]. Место, куда помещаются и из которого извлекаются элементы стека, называется вершиной. Таким образом, стек является структурой данных, которые организованы по принципу LIFO (Last In, First Out) – «Последний пришел – первый вышел».

Стек можно реализовать различными способами. Например, элементы стека можно разместить в массиве, либо реализовать стек в виде односвязного списка [32]. Рассмотрим реализацию стека в виде списка. В этом случае объекты стека имеют такую же структуру, как и объекты однонаправленного списка. Часть полей описывает характеристику конкретного объекта и есть поле типа указатель, которое содержит адрес следующего в стеке элемента.

Листинг 11.3. В программе создается стек для проверки правильности расстановок скобок в тексте, содержащимся в файле «input.txt» (рис. 11.7). Будем считать, что есть скобки трех видов – круглые, квадратные и фигурные.

Последовательность скобок считается правильной если [4]:

1. Это элементарная последовательность: (), {}, []

2. Пусть S – это правильно построенная последовательность. Тогда последовательности (S), {S} и [S] – правильно построенные.

3. Пусть S и R правильно построенные последовательности. Тогда последовательность SR – правильно построенная.

Алгоритм проверки правильности расстановок скобок заключается в следующем. Если текущий символ является открывающей скобкой, то он заносится в стек. Если текущий символ – закрывающая скобка, то анализируется символ, находящийся в вершине стека. Если это парная скобка, то символ удаляется из стека, а если непарная, то дается информация, что последовательность построена неправильно. Остальные символы игнорируются. В конце анализируется содержимое стека. Если он пуст, то последовательность правильно построена, иначе она построена неправильно.

 

Содержимое файла “input.txt”

 

Рис. 11.8. Информация, находящаяся в файле «input.txt»

 

//L11_3.cpp

#include <fstream>

#include <iostream>

using namespace std;

struct stek

{

char c;

stek*next;

};

stek* add_stek(stek*, char); // Прототип функции добавления элемета в стек

stek* del_stek(stek*); // Прототип функции удаления элемета из стека

 

int main()

{

char nc[3]={'(','{','['}, kc[3]={')','}',']'}, c;

int i;

setlocale(LC_CTYPE,"russian");

stek *top=NULL;

ifstream ff("input.txt");

c=ff.get();

while(!ff.eof())

{

for(i=0;i<3;i++)

if(c==nc[i])

{

top=add_stek(top, c);

break;

}

for(i=0; i<3; i++)

{

if(c==kc[i])

break;

}

if(i<3 && top!=NULL)

{

if(top->c==nc[i])

top=del_stek(top);

else

{

if(top->c!=nc[i])

{

cout<<"Последовательность построена неправильно\n";

return 0;

}

}

}

else

if(i<3 && top==NULL)

{

cout<<"Последовательность построена неправильно\n";

return 0;

}

c=ff.get();

}

ff.close();

if(top!=NULL)

cout<<"Последовательность построена неправильно\n";

else

cout<<"Последовательность построена правильно\n";

return 0;

}

stek* add_stek(stek *top, char c)

{

stek *new_el;

new_el=new stek;

new_el->c=c;

new_el->next=NULL;

if(top==NULL)

top=new_el;

else

{

new_el->next=top;

top=new_el;

}

return top;

}

stek* del_stek(stek *top)

{

stek *tmp;

tmp=top;

top=top->next;

delete tmp;

return top;

}

 

Результат выполнения программы листинга 11.3 приведен на рис. 11.9.

 

 

Рис. 11.9. Результат работы программы листинга 11.3

Листинг 11.4. В программе создаются структуры очереди и стека, хранящие символ. В файле «input.txt» хранится текст (рис. 11.10). Преобразовать его следующим образом: сначала должны идти цифры в том порядке, в котором они встречаются в файле «input.txt», а затем латинские буквы в обратном порядке, чем в файле «input.txt». Для решения этой задачи считываемые цифры следует помещать в очередь, а латинские буквы в стек. Далее необходимо извлечь информацию из очереди, а затем из стека.

Содержимое файла “input.txt”

 

Рис. 11.10. Информация, находящаяся в файле «input.txt»

//L11_4.cpp

#include <fstream>

#include <iostream>

using namespace std;

struct ochered

{

char c;

ochered *next; // Указатель на следующий элемент

};

// Прототип функции постановки в очередь:

void add_ochered(ochered **begin, ochered **end, char nc);

// Прототип функции удаления из очереди:

void del_ochered(ochered **begin, ochered **end);

struct stek

{

char c;

stek *next; // Указатель на следующий элемент

};

// Прототип функции постановки в стек:

stek* add_stek(stek *top, char nc);

// Прототип функции удаления из стека:

stek* del_stek(stek*);

// Прототип функции печати содержимого очереди:

void print_och(ochered *begin, char *sn);

// Прототип функции печати содержимого стека:

void print_stek(stek *top, char *sn);

void add_ochered(ochered **begin, ochered **end, char nc)

{

ochered *new_el;

new_el=new ochered; // Создание нового элемента

(*new_el).c=nc;

(*new_el).next=NULL;

if(*begin==NULL) // Очередь пуста.Элемент вносится как единственный

{

(*begin)=(*end)=new_el;

return;

}

// Внесение нового элемента в очередь:

(**end).next=new_el;

(*end)=new_el;

}

void del_ochered(ochered **begin, ochered **end)

{

ochered *ptr;

ptr=*begin;

if(*begin==NULL) // Очередь пуста

 

{

cout<<"Очередь пуста";

return;

}

// Передвигается начало очереди:

(*begin)=(**begin).next;

// Освобождается память, выделенная для удаляемого элемента:

delete ptr;

}

void print_och(ochered *begin, char *sn)

{

ofstream ff(sn);

ochered *ptr=begin;

while(ptr!=NULL)

{

ff<<(*ptr).c;

ptr=(*ptr).next;

}

}

stek* add_stek(stek *top, char c)

{

stek* new_el;

new_el=new stek; // Создание нового элемента

new_el->c=c;

new_el->next=NULL;

if(top==NULL) // Стек пуст.Элемент вносится как единственный

top=new_el;

else

{

// Внесение нового элемента в стек:

new_el->next=top;

top=new_el;

}

return top;

}

stek*del_stek(stek *top)

{

stek *tmp;

tmp=top;

if(top==NULL) // Стек пуст

{

cout<<"Стек пуст";

return NULL;

}

// Передвигается начало стека:

top=top->next;

// Освобождается память, выделенная для удаляемого элемента:

delete tmp;

return top;

}

void print_stek(stek *top, char *sn)

{

ofstream ff(sn,ios::app);

stek *ptr=top;

while(ptr!=NULL)

{

ff<<(*ptr).c;

ptr=(*ptr).next;

}

}

int main()

{

ifstream ff("input.txt");

char cc[81];

int i;

ochered *begin,*end;

stek *top;

begin=end=NULL;

top=NULL;

ff.getline(cc, 80);

while(!ff.eof())

{

for(i=0; cc[i]!='\0'; i++)

{

if(cc[i]>='A' && cc[i]<='z')

top=add_stek(top, cc[i]);

else

if(cc[i]>='0'&&cc[i]<='9')

add_ochered(&begin, &end, cc[i]);

}

ff.getline(cc, 80);

 

}

ff.close();

char so[8]="out.txt";

print_och(begin, so);

print_stek(top, so);

return 0;

}

Результат выполнения программы листинга 11.4 приведен на рис. 11.11.

 

 

Рис. 11.11. Результат работы программы листинга 11.4

Упражнения

 

26. В файле “input.txt” задан текст. Ввести структуру, отражающую уникальное слово и частоту его встречаемости в тексте. Создать очередь, элементы которой тип введенной структуры. Результат записать в файл.

27. В файле “input.txt” задан текст. Ввести структуру, отражающую уникальное слово и частоту его встречаемости в тексте. Создать односвязный список, содержащий слова в алфавитном порядке, и результаты записать в файл.

28. В файле “input.txt” задана последовательность чисел и символов арифметических операций (+, -, *, /). Если из файла считывается число, то оно помещается в стек. Если считывается символ, то из стека извлекаются два числа и над ними производится данная арифметическая операция (если она допустима), и результат вновь помещается в стек. Если операцию по каким-либо причинам выполнить невозможно (не хватает чисел в стеке или делитель равен нулю), то на экран выдается сообщение о причине и необходимо прекратить выполнение программы. Если чтение из файла “input.txt” заканчивается успешно, то выдать информацию о количестве проведенных операций.

29. В файле “input.txt” задан список абитуриентов ННГУ с указанием фамилии, имени и отчества, а также суммы баллов, набранных по профильным предметам. Составить односвязный список абитуриентов по убыванию суммы баллов и результаты записать в файл.

30. В файле “input.txt” задан список сотрудников фирмы с указанием даты их поступления на работу. Для описания дат создать структуру. Написать функцию сравнения двух дат. Составить односвязный список сотрудников в порядке возрастания даты их поступления на работу.

31. Для описания дат создать структуру и написать функцию сравнения двух дат. Разработать структуру для описания интервала, состоящего из двух дат. В файле “input.txt” задан список из нескольких пар дат – концов интервала. Составить из них очередь. Определить, существует ли непустое пересечение этих интервалов.

32. В файле “input.txt” задан список студентов ММФ ННГУ с указанием фамилии, имени и отчества, а также название предмета и экзаменационная оценка. Составить односвязный список студентов в алфавитном порядке с указанием среднего балла.

33. Создать структуру для описания комплексных чисел. Написать функции действий с комплексными числами (сложение, вычитание, умножение, деление, нахождение модуля). В файле “input.txt” задан список из четного числа комплексных чисел. Для каждой пары комплексных чисел выполнить все четыре арифметических действия и результат записать в файл. Если действия выполнить нельзя, вывести об этом сообщение.

34. В файле “input.txt” задан список заданий для выполнения на ЭВМ. Задание включает: номер задания, длительность выполнения (в минутах) и фамилию исполнителя. Разработать структуру заданий. Создать из заданного списка очередь на выполнение работ. Определить общее время работы в часах и минутах.

35. В файле “input.txt” задан список заданий для выполнения на ЭВМ. Задание включает: номер задания, длительность выполнения (в минутах) и фамилию исполнителя. Разработать структуру заданий. Создать односвязный список по убыванию длительности выполнения задания. Полученные данные записать в файл.

36. Для описания дат создать структуру и написать функцию проверки правильности вводимой даты. В файле “input.txt” задан список дат. При чтении из файла отмечать неправильно записанные даты и заносить их в стек. Определить число неправильно введенных дат и вывести на экран.

37. Для описания дат создать структуру и написать функцию проверки правильности вводимой даты. В файле “input.txt” задан список дат. При чтении из файла игнорировать неправильно записанные даты. Правильно записанные даты заносить в очередь. Определить число правильно введенных дат и вывести на экран.

38. Для описания дат создать структуру и написать функции: проверки правильности вводимой даты и сравнения двух дат. В файле “input.txt” задан список дат. При чтении из файла игнорировать неправильно записанные даты, а из правильно записанных дат создать односвязный список по возрастанию дат. Определить число неправильно введенных дат и вывести на экран.

39. Создать структуру очереди, хранящую символ. В файле «input.txt” задан текст. Преобразовать его следующим образом: сначала должны идти цифры в том порядке, в котором они встречаются в файле ”input.txt”, а затем буквы кириллицы в том же порядке, в котором они встречаются в файле ”input.txt”.

40. Создать структуры очереди и стека, хранящие символ. В файле ”input.txt” задан текст. Преобразовать его следующим образом: сначала должны идти латинские буквы в том же порядке, в котором они встречаются в файле ”input.txt”, а затем цифры в обратном порядке, чем в файле ”input.txt”.

41. Создать структуры очереди и стека, хранящие символ. В файле ”input.txt” хранится текст. Преобразовать его следующим образом: сначала должны идти знаки препинания (,.;:! -) в том порядке, в котором они встречаются в файле ”input.txt”, а затем буквы кириллицы в обратном порядке, чем в файле ”input.txt”.

42. Создать структуры очереди и стека, хранящие символ. В файле ”input.txt” задан текст. Преобразовать его следующим образом: сначала должны идти латинские буквы в том порядке, в котором они встречаются в файле ”input.txt”, а затем буквы кириллицы в обратном порядке, чем в файле ”input.txt”.

43. Создать структуру для описания моментов времени (часы, минуты, секунды). Написать функцию сравнения двух моментов времени. Разработать структуру для описания участников олимпиады. В файле ”input.txt” задан список участников, содержащий фамилию, имя, отчество и показанный результат. Составить односвязный список по возрастанию показанных результатов и распечатать информацию о первых шести участниках.

44. Создать структуру для описания моментов времени (часы, минуты, секунды). Написать функцию сравнения двух моментов времени. Разработать структуру для описания участников олимпиады. В файле ”input.txt” задан список участников, содержащий фамилию, имя, отчество и показанный результат. Составить односвязный список по убыванию показанных результатов и распечатать информацию о первых шести участниках.

45. Для описания дат создать структуру и написать функцию, определяющую расстояние в днях между двумя датами. В файле “input.txt” задан список фирм с указанием даты их основания. Составить односвязный список фирм в а порядке возрастания длительности их работы на текущую дату.

46. Для описания дат создать структуру и написать функцию, определяющую расстояние в днях между двумя датами. В файле “input.txt” задан список сотрудников фирмы с указанием начала их контракта и даты его окончания. Составить односвязный список сотрудников в алфавитном порядке с указанием числа дней работы в данной фирме.

47. Для описания дат создать структуру и написать функцию сравнения двух дат. Ввести структуру для описания интервала, состоящего из двух дат. В файле “input.txt” задан список сотрудников фирмы с указанием дат начала и конца их командировки, а также города, куда они были направлены. Определить, какие из сотрудников могут встретиться в командировке, и создать очередь из этих сотрудников.

48. Для описания дат создать структуру и написать функцию сравнения двух дат. В файле “input.txt” задан список продуктов, хранящихся на базе, с указанием срока годности. Создать очередь из продуктов, срок годности которых истек на данную дату. Вывести на экран список продуктов, годных к реализации.

49. Для описания дат создать структуру и написать функцию сравнения двух дат. В файле “input.txt” задан список продуктов, хранящихся на базе, с указанием срока годности. Создать стек из продуктов, годных к реализации на данную дату. Вывести на экран информацию о продуктах, срок реализации которых истек.

50. Для описания дат создать структуру и написать функции: сравнения двух дат и определения расстояния в днях между двумя датами. В файле “input.txt” задан список продуктов, хранящихся на базе, с указанием срока годности. Создать очередь из продуктов, срок годности которых истекает не позднее, чем через пять дней до заданной даты. Вывести на экран список продуктов, годных к реализации, но не вошедших в созданную очередь.

 

 

Список литературы

 

1. Ашарина И.В. Объектно-ориентированное программирование в С++: лекции и упражнения: Учебное пособие для вузов. – М.: Горячая линия – Телеком, 2008. – 320 с.

2. Бобровский С. Самоучитель программирования на языке С++ в системе Borland C++ Builder 5.0. – М.: ДЕСС КОМ, 2001. – 271 с.

3. Глушаков С.В., Коваль А.В., Смирнов С.В. Язык программирования С++: учебный курс. – Харьков: Фолио; М.: ООО «Издательство АСТ», 2001. – 500 с.

4. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368 с.

5. Девис С.Р. С++ для чайников, 6-е изд.: пер. с англ. – М.: ООО «И.Д. Вильямс», 2010. – 336 с.

6. Дейтел Х.М., Дейтел П.Дж. Как программировать на С++, 5-е изд.: пер. с англ. – М: ООО «Бином-Пресс», 2008. – 1456 с.

7. Задачи по программированию /С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина, М.И. Селюн. – М.: Наука, 1998 – 224 с.

8. Касаткин А.И., Вальвачев А.Н. От Turbo C к Borland C++. – Минск: Вышейшая школа, 1992. – 240 с.

9. Керниган Б., Ритчи Д. Язык программирования Си: пер. с англ. – СПб.: Невский Диалект, 2001. – 352 с.

10. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. – М.: Издательский дом «Вильямс», 2000. – 832 с.

11. Кузнецов М.В., Симдянов И.В. С++. Мастер-класс в задачах и примерах. – СПб.: БХВ-Петербург, 2007. – 480 с.

12. Культин Н.Б. С/С++ в задачах и примерах: 2-е изд., перераб. и доп. – СПб.: БХВ – Петербург, 2009. – 368 с.

13. Культин Н.Б. С++ Builder в задачах и примерах. – СПб.: БХВ- Петербург, 2007. – 336 с.

14. Лафоре Р. Объектно-ориентированное программирование в С++. Классика Computer Science: 4-е изд. – СПб.: Питер, 2008. – 928 с.

15. Макогон В.С. Язык программирования Си для начинающих: Учебное пособие. – Одесса: НПФ «Астропринт», 1993. – 96 с.

16. Математический энциклопедический словарь / Гл. ред. Ю.В. Прохоров; Ред. кол.: С.И. Адян, Н.С. Бахвалов, В.И. Битюцков и др. – М.: Советская энциклопедия, 1988. – 847 с.

17. Павловская Т.А. С/С++. Программирование на языке высокого уровня. – СПб.: Питер, 2007. – 461 с.

18. Павловская Т.А., Щупак Ю.А. С++. Объектно-ориентирован­ное программирование: практикум. – СПб.: Питер, 2008. – 265 с.

19. Пахомов Б.И. С/С++ и MS Visual С++ 2005 для начинающих. – СПб.: БХВ-Петербург, 2007. – 464 с.

20. Пахомов Б.И. С/С++ и MS Visual С++ 2008 для начинающих. – СПб.: БХВ-Петербург, 2008. – 624 с.

21. Перова В.И. Программирование на С++ в среде Visual Studio.NET: Учебное пособие. – Нижний Новгород: Изд-во Нижегородского госуниверситета, 2010. – 261 с.

22. Перова В.И., Чугунова Е.А. Объектно-ориентированное программирование на языке С++ в среде Visual Studio.NET: Ч. 1: Учебно-методическое пособие / Под ред. В.И. Перовой. – Нижний Новгород: Нижегородский госуниверситет, 2009. – 95 с.

23. Перова В.И., Чугунова Е.А. Объектно-ориентированное программирование на языке С++ в среде Visual Studio.NET: Ч. 2: Учебно-методическое пособие / Под ред. В.И. Перовой. – Нижний Новгород: Нижегородский госуниверситет, 2010. – 95 с.

24. Подбельский В.В. Язык Си++: учебное пособие. – М.: Финансы и статистика, 2001. – 560 с.

25. Прата С. Язык программирования С++. Лекции и упражнения, 5-е изд.: пер. с англ. – М.: ООО «И.Д. Вильямс», 2007. – 1184 с.

26. Сборник заданий по вычислительному практикуму на языке Си: Методическое пособие / Сост. В.В. Денисов, М.В. Маркина, Т.А. Сабаева, О.Г. Савихин. – Нижний Новгород: Изд-во ННГУ, 2002. – 56 с.

27. Солтер Н.А., Клеппер С.Дж. С++ для профессионалов: пер. с англ. – М.: ООО «И.Д. Вильямс», 2006. – 912 с.

28. Страуструп Б. Дизайн и эволюция С++: пер. с англ. – М.: ДМК Пресс; СПб.: Питер, 2007. – 445 с.

29. Страуструп Б. Язык программирования С++. Специальное издание: пер. с англ. – М.: ООО «Бином-Пресс», 2005. – 1104 с.

30. Тарасов В.Л. Основы программирования в С++Builder. Ч. 1: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2008. – 68 с.

31. Тарасов В.Л. Основы программирования в С++Builder. Ч. 2: Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2006. – 84 с.

32. Тарасов В.Л. Программирование на С++: Учебное пособие. – Н. Новгород: Изд-во ННГУ, 2006. – 310 с.

33. Уайс М.А. Организация структур данных и решение задач на С++. – М.: ЭКОМ Паблишерз, 2008. – 896 с.

34. Фридман А.Л. Основы объектно-ориентированного программирования на языке Си++. – М.: Горячая линия – Телеком, 2001. – 232 с.

35. Шилдт Г. Полный справочник по С++, 4-е изд.: пер. с англ. – М.: Издательский дом «Вильямс», 2006. – 800 с.

36. Шилдт Г. С++: методики программирования Шилдта: пер. с англ. – М.: ООО «И.Д. Вильямс», 2009. – 480 с.

37. Шилдт Г. Самоучитель С++: пер. с англ. – СПб.: БХВ-Петер­бург, 2001. – 688 с.