Динамические структуры данных
1. Условие задания
Гаражная стоянка имеет одну стояночную полосу, причем въезд и выезд находятся в одном конце полосы. Если владелец автомашины приходит забрать свой автомобиль, который не является ближайшим к выходу, то все автомашины, загораживающие проезд, удаляются, машина данного владельца выводится со стоянки, а другие машины возвращаются на стоянку в исходном порядке.
Написать программу, которая моделирует процесс прибытия и отъезда машин. Прибытие или отъезд автомашины задается командной строкой, которая содержит признак прибытия или отъезда и номер машины. Программа должна выводить сообщение при прибытии или выезде любой машины. При выезде автомашины со стоянки сообщение должно содержать число раз, которое машина удалялась со стоянки для обеспечения выезда других автомобилей.
2. Динамические структуры данных
. 1 Проблемы с организацией данных
фрагменты программ, показывающие оба эти способа на примере выделения памяти под одномерный массив:
а) Память выделена на этапе компиляции:
const int N = 5;x1[N];
cout << "n=";
cin >> n;
}while(n <= 0);
x2 = new int[n];
Теперь массивы x1 и x2 можно использовать, например, задать значения элементам этих массивов.
Но в обоих случаях после того, как память под массивы выделена, мы не можем изменять размеры этих массивов по своему усмотрению. Если быть более точным, то это справедливо только для случая а). Для варианта б) проблему решить можно. Но какой ценой?! Приведём возможную программную реализацию изменения размера динамического массива:
int *t = new int[k];
// переписываем в него содержимое исходного массива x2
for(int i = 0; i < k && i < n; i++)
t[i] = x2[i];
// настраиваем x2 на новый участок памяти= t;
Как не сложно понять, такой подход к решению проблемы будет занимать слишком много машинного времени. В общем-то неразумно выделять заново память под целый массив, когда нам требовался дополнительный участок всего для одного элемента.
. 2 Определение и классификация динамических структур данных
Для того, чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать наши данные не в массив, а в нечто другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных.
Каждый элемент динамических структур данных состоит из собственно данных и одного или нескольких указателей, ссылающихся на аналогичные элементы. Это позволяет добавлять в динамическую структуру новые данные или удалять какие-то из имеющихся, не затрагивая при этом другие элементы структуры.
обслуживания очереди к кассе в магазине лучше всего подойдет динамическая структура данных под названием «очередь», а не пресловутый массив, а для представления сети автомобильных дорог массив вообще неприемлем. Здесь нужна именно «сеть».
стеки, очереди (односторонние, двухсторонние, очереди с приоритетами). Организация нелинейных структур более сложная. Нелинейные структуры представляются, как правило, в виде дерева (каждый элемент имеет некоторое количество связей, например, в бинарном дереве каждый элемент (узел) имеет ссылку на левый и правый элемент).
Рассмотрим более подробно некоторые виды динамических структур.
. 3 Линейный односвязный список
Линейный список - это динамическая структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Графически линейный список можно представить следующим образом:
Более подробно этот вид рассмотрим в 3 части.
. 4 Двухсвязные линейные списки
Каждый элемент односвязного списка кроме собственно данных содержит поле с адресом следующего элемента. Работу с такими списками мы только что рассмотрели.
В двухсвязном списке каждый элемент имеет поля с данными и два указателя: один указатель хранит адрес предшествующего элемента списка, второй - адрес последующего элемента. Вполне естественно для работы с двухсвязным списком использовать два указателя, хранящие адреса начала и конца такого списка. На рисунке ниже даётся графическое представление двухсвязного списка.
. 5 Кольцевой список
Схема кольцевого списка представлена на рисунке ниже (используем те же данные, что и для ранее рассмотренного односвязного списка, т. е. список из чисел 3, 5, 1, 9):
2. 6 Очередь
Очередь - это линейная динамическая структура данных, для которой выполняется правило: добавление новых данных возможно только в конец этой структуры, а удаление (извлечение) - только с начала. В англоязычной литературе этот принцип называется FIFO (First Input - First Output, т. е. первый пришёл - первый ушёл).
Примером из реальной жизни может быть очередь из покупателей к кассе в магазине.
Как не трудно понять, очередь - это линейный список, для которого определены всего две основные операции: добавление в конец и извлечение с начала. Значит, удобно иметь два указателя: на начало и конец этой динамической структуры. Но списки бывают односвязные и двухсвязные. Какой использовать? Подойдёт только двухсвязный список. В этом можно будет убедиться при рассмотрении основных алгоритмов для работы с очередью.
Всё это не так сложно реализовать самостоятельно, поэтому ни каких программных примеров не приводится.
3. Стеки
Определение стека
Вершина стека - эта та его часть, через которую ведётся вся работа. На вершину стека добавляются новые элементы, и с вершины стека снимаются (удаляются) элементы.
В общем, стек - это односвязный список, для которого определены только две операции: добавление и удаление из начала списка.
Примером стека может служить коробка, в которую сверху укладывают книги. Извлекать книги также приходится сверху.
Рассмотрим основные и дополнительные действия со стеком. Для работы используем структуры Data и Stek:
{
{
Data d;
Stek *next;
};
В программе определяем указатель на начало будущего стека:
*u = NULL;
После этого можно начать работать со стеком.
1. Добавление в стек. Функцию добавления назовём Push() - по аналогии с командой ассемблера push, которая заносит целое число в программный стек.
void Push(Stek **u, Data &x)
{
Stek *t = new Stek; // Память под новый элемент
t->d. a = x. a; // Заполнение полей
t->next = *u; // Подключаем новый элемент к имеющимся
*u = t; // Перенастройка вершины
}
Обратиться к функции можно так:(&u, x);
где x - объект типа Data.
bool Pop(Stek **u, Data &x)
{
if(*u == NULL)
{
cout << "Pustoj stek" << endl;
return false;
}
Stek *t = *u;
x. a = t->d. a; // Получаем значения полей на вершине стека
*u = t->next; // Перенастройка вершины
}
Пример вызова функции:
Data y;(Pop(&u, x))
{
<< "y=" << y. a << endl;
}
Дополнительные действия со стеком - распечатка стека (можно взять алгоритм для работы с односвязным списком) и чтение с вершины стека. Чтение напоминает извлечение, но при этом данные из стека не удаляются. Вот возможный вариант реализации:
bool Read(Stek **u, Data &x)
{
{
cout << "Pustoj stek" << endl;
return false;
}
Stek *t = *u;
x. a = t->d. a; // Заполнение полей
return true;
}
Использование функции Read() может быть аналогичным использованию Pop().
4. Описание основных типов данных и функции для работы с ними
Для организации хранения, представления данных в программе используются 2 структуры: Avto и Stek.
Структура Avto необходима для описания всех полей, которые характеризуют один автомобиль в гараже. Она имеет следующий вид:
Avto
{
char marka[10];
};
Структура Stek необходима для организации стека. Она имеет следующий вид:
struct Stek
{
Avto a;
Stek *next;
};
где
·a - поле типа Avto, в котором хранятся сами данные;
·*next - указатель на стек того же типа, то есть Stek.
&x) - ввод данных
·void Print(Stek *u) - функцияпечати
·void dobavlenie(Stek **u, Avto &x) - добавление новой записи в стек
·bool Zabiraem(Stek**u, Avto &x) - функция удаление элемента из стека
·void Clear(Stek **u) - очистка всего стека
5. Листингпрограммы
#include <iostream>
#include <windows. h>
#include <string. h>namespace std;hConsole=GetStdHandle(STDOUTPUTHANDLE);
Avto
{
char marka[10];
};Stek
{
Avto a;
Stek *next;
};
bufer [255];*rus (char*s)
{
CharToOem (s, bufer);
return bufer;
}
&x)
{
cin>>x. marka;
}
Print(Stek *u)
{
{
<<rus("\nВГаражеНЕТмашин!!!")<<endl;
return;
}
while(p)
{
p->a. marka;
p = p->next;
k++;
}
cout<<rus("\n\tВгараже"); if(k<5) cout<<k<<rus(" машины")<<endl;
<<k<<rus(" машин")<<endl;
p = u;
SetConsoleTextAttribute(hConsole, 11);
cout<<rus("\n ГАРАЖ:")<<endl;
while(p)
{
cout<<"\t* ";
cout << p->a. marka<<endl;
p = p->next;
}
cout<<"\t********"<<endl;
SetConsoleTextAttribute(hConsole, 7);
}
dobavlenie(Stek **u, Avto &x)
{
Stek *t=new Stek;
strcpy(t->a. marka, x. marka);
t->next=*u;
*u=t;
}
Zabiraem(Stek**u, Avto &x)
{
if(*u==NULL){
return false;
}
Stek*t=*u;
strcpy(x. marka, t->a. marka);
*u=t->next;
return true;
}
vyezjaetizgaraja(Stek**u)
{
char n[7];
cout<< rus("\n\t Введите машину, которая выезжает:");
cin>>n;
while(*u)
{
{
if(strcmp(n, x. marka)==0)
{
cout<< rus(" машина") << n; cout<<rus(" уехала!!!");
&v, x)) /// возвращаем элементы из стека V в стек U
dobavlenie(u, x);
}
else
{
dobavlenie(&v, x);
}
}
else break;
}
SetConsoleTextAttribute(hConsole, 12);
<<rus(" ВгаражеНЕТмашины")<<n<<endl;
SetConsoleTextAttribute(hConsole, 7);
while(Zabiraem(&v, x))
dobavlenie (u, x);
}
Clear(Stek **u)
{
if(*u == 0) return;
Stek *p = *u;
while(p)
{
t = p;
p = p->next;
}
*u = 0;
}
main()
{
SetConsoleTextAttribute(hConsole, 10);
cout << "\t***** * ***** * * * *" << endl;
cout << "\t* * * * * * * * * * " << endl;
cout << "\t* * * * * * * *** " << endl;
cout << "\t* ***** ***** ***** *** " << endl;
<< "\t* * * * * * * * * " << endl;
cout << "\t* * * * * * * * *" << endl;
cout << "\n" << endl;
int n;
Avto x; //переменная x типа avto
do{
SetConsoleTextAttribute(hConsole, 14);
cout<<rus(" ***********************\n * \tМеню:")<<endl;
cout<<rus(" * 1. Приехала новая машина")<<endl;
cout<<rus(" * 2. Печатать гараж")<<endl;
cout<<rus(" * 3. Машина выезжает")<<endl;
<<rus(" * 0. Выход")<<endl;
cout<<rus(" ***********************")<<endl;
<<rus("\n\tЗадайте действие: ");
cin>>n;
SetConsoleTextAttribute(hConsole, 7);
switch (n)
{
case 1: cout<<rus("Введитеновоеавто: ");vvod(x);
dobavlenie(&u, x); cout<<rus("\nАвтоДобавлено!\a\n"); break;
case 2: Print(u); break;
case 3: Print(u); vyezjaetizgaraja(&u); break;
&u); break;
default: SetConsoleTextAttribute(hConsole, 12);
cout<<rus("Нет такого ЧИСЛА!!!")<<endl;
}
<<endl;
}while (n!=0);
}
1. И. Ш. Хабибуллин Программирование C++: Пер. с англ. - 3-е изд. - СПб.: БХВ-Петербург, 2006. - 512 с.
2. Сайт: www.victor192007.narod.ru
. Конспект лекций по дисциплине «Программирование на языках высокого уровня».
| 
