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

1.Условие задания

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

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

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

.1 Проблемы с организацией данных

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

а) Память выделена на этапе компиляции:

const int N = 5;x1[N];

б) Память выделена на этапе исполнения программы с помощью операции new:

int *x2;n;{

cout << "n=";

cin >> n;

}while(n <= 0);

x2 = new int[n];

Теперь массивы x1 и x2 можно использовать, например, задать значения элементам этих массивов.

Но в обоих случаях после того, как память под массивы выделена, мы не можем изменять размеры этих массивов по своему усмотрению. Если быть более точным, то это справедливо только для случая а). Для варианта б) проблему решить можно. Но какой ценой?! Приведём возможную программную реализацию изменения размера динамического массива:

//пусть k - новый размер массиваk = n + 1;

// выделяем новый участок памяти необходимого размера

int *t = new int[k];

// переписываем в него содержимое исходного массива x2

for(int i = 0; i < k && i < n; i++)

t[i] = x2[i];

// освобождаем память, на которую указывал x2[]x2;

// настраиваем x2 на новый участок памяти= t;

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

.2 Определение и классификация динамических структур данных

Для того, чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать наши данные не в массив, а в нечто другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных.

Каждый элемент динамических структур данных состоит из собственно данных и одного или нескольких указателей, ссылающихся на аналогичные элементы. Это позволяет добавлять в динамическую структуру новые данные или удалять какие-то из имеющихся, не затрагивая при этом другие элементы структуры.

Кроме того, динамические структуры позволяют нам организовать данные так, чтобы их представление в программе было максимально приближено к тому, как эти данные выглядят в реальности. Так, для моделирования обслуживания очереди к кассе в магазине лучше всего подойдет динамическая структура данных под названием «очередь», а не пресловутый массив, а для представления сети автомобильных дорог массив вообще неприемлем. Здесь нужна именно «сеть».

Динамические структуры данных бывают линейные и нелинейные. В линейной динамической структуре данные связываются в цепочку. К линейным структурам относятся списки (односвязные, двухсвязные, кольцевые), стеки, очереди (односторонние, двухсторонние, очереди с приоритетами). Организация нелинейных структур более сложная. Нелинейные структуры представляются, как правило, в виде дерева (каждый элемент имеет некоторое количество связей, например, в бинарном дереве каждый элемент (узел) имеет ссылку на левый и правый элемент).

Рассмотрим более подробно некоторые виды динамических структур.

.3 Линейный односвязный список

Линейный список - это динамическая структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Графически линейный список можно представить следующим образом:

Более подробно этот вид рассмотрим в 3 части.

.4 Двухсвязные линейные списки

Как мы уже говорили, линейные списки могут быть односвязными и двухсвязными.

Каждый элемент односвязного списка кроме собственно данных содержит поле с адресом следующего элемента. Работу с такими списками мы только что рассмотрели.

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

.5 Кольцевой список

Кольцевой список - это список, у которого последний элемент связан с первым. Кольцевой список можно сделать как односвязным, так и двухсвязным. Рассмотрим вкратце односвязный кольцевой список.

Схема кольцевого списка представлена на рисунке ниже (используем те же данные, что и для ранее рассмотренного односвязного списка, т.е. список из чисел 3, 5, 1, 9):

2.6 Очередь

Очередь - это линейная динамическая структура данных, для которой выполняется правило: добавление новых данных возможно только в конец этой структуры, а удаление (извлечение) - только с начала. В англоязычной литературе этот принцип называется FIFO (First Input - First Output, т.е. первый пришёл - первый ушёл).

Примером из реальной жизни может быть очередь из покупателей к кассе в магазине.

Как не трудно понять, очередь - это линейный список, для которого определены всего две основные операции: добавление в конец и извлечение с начала. Значит, удобно иметь два указателя: на начало и конец этой динамической структуры. Но списки бывают односвязные и двухсвязные. Какой использовать? Подойдёт только двухсвязный список. В этом можно будет убедиться при рассмотрении основных алгоритмов для работы с очередью.

На рисунке ниже показано графическое представление очереди. Как и в предыдущих темах, очередь будем строить из целых чисел, например: 3, 5, 1.

Всё это не так сложно реализовать самостоятельно, поэтому ни каких программных примеров не приводится.

3.Стеки

Определение стека

Стек - динамическая структура данных, для которой выполняется правило: последним пришёл - первым ушёл. Таким образом, и дополнение новых данных, и извлечение их из стека всегда выполняется с одной стороны.

Вершина стека - эта та его часть, через которую ведётся вся работа. На вершину стека добавляются новые элементы, и с вершины стека снимаются (удаляются) элементы.

В общем, стек - это односвязный список, для которого определены только две операции: добавление и удаление из начала списка.

Примером стека может служить коробка, в которую сверху укладывают книги. Извлекать книги также приходится сверху.

Операции со стеком

Рассмотрим основные и дополнительные действия со стеком. Для работы используем структуры Data и Stek:

struct Data

{

int a;

};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.

2. Извлечение из стека. Здесь снова аналогия с ассемблером (команда pop выталкивает целое число из стека).

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; // Перенастройка вершины

delete t; // Удаление ненужного элемента

return true;

}

Пример вызова функции:

Data y;(Pop(&u, x))

{

y = x;

cout << "y=" << y.a << endl;

}

Дополнительные действия со стеком - распечатка стека (можно взять алгоритм для работы с односвязным списком) и чтение с вершины стека. Чтение напоминает извлечение, но при этом данные из стека не удаляются. Вот возможный вариант реализации:

bool Read(Stek **u, Data &x)

{

if(*u == NULL)

{

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.

Для работы со стеками в программе реализованы все необходимые методы:

·void vvod(Avto &x) - ввод данных

·void Print(Stek *u) - функцияпечати

·void dobavlenie(Stek **u, Avto &x) - добавление новой записи в стек

·bool Zabiraem(Stek**u, Avto &x) - функция удаление элемента из стека

·void vyezjaet_iz_garaja(Stek**u) - функция выезда автомобиля из гаража

·void Clear(Stek **u) - очистка всего стека

5.Листингпрограммы

#include <iostream>

#include <windows.h>

#include <string.h>namespace std;hConsole=GetStdHandle(STD_OUTPUT_HANDLE);

Avto

{

char marka[10];

};Stek

{

Avto a;

Stek *next;

};

bufer [255];*rus (char*s)

{

CharToOem (s, bufer);

return bufer;

}

vvod(Avto &x)

{

cin>>x.marka;

}

Print(Stek *u)

{

int k=0;

Stek *p = u;

if(p==0)

{

cout<<rus("nВГаражеНЕТмашин!!!")<<endl;

return;

}

while(p)

{

p->a.marka;

p = p->next;

k++;

}

cout<<rus("ntВгараже"); if(k<5) cout<<k<<rus(" машины")<<endl;

else cout<<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;

delete t;

return true;

}

vyezjaet_iz_garaja(Stek**u)

{

Stek *v=NULL;

Avto x;

char n[7];

cout<< rus("nt Введите машину, которая выезжает:");

cin>>n;

while(*u)

{

if(Zabiraem(u, x))

{

if(strcmp(n, x.marka)==0)

{

cout<< rus(" машина") << n; cout<<rus(" уехала!!!");

while(Zabiraem(&v, x)) /// возвращаем элементы из стека V в стек U

dobavlenie(u, x);

return;

}

else

{

dobavlenie(&v, x);

}

}

else break;

}

SetConsoleTextAttribute(hConsole, 12);

cout <<rus(" ВгаражеНЕТмашины")<<n<<endl;

SetConsoleTextAttribute(hConsole, 7);

while(Zabiraem(&v, x))

dobavlenie (u, x);

}

Clear(Stek **u)

{

if(*u == 0) return;

Stek *p = *u;

Stek *t;

while(p)

{

t = p;

p = p->next;

delete t;

}

*u = 0;

}

main()

{

SetConsoleTextAttribute(hConsole, 10);

cout << "t***** * ***** * * * *" << endl;

cout << "t* * * * * * * * * * " << endl;

cout << "t* * * * * * * *** " << endl;

cout << "t* ***** ***** ***** *** " << endl;

cout << "t* * * * * * * * * " << endl;

cout << "t* * * * * * * * *" << endl;

SetConsoleTextAttribute(hConsole, 7);

cout << "n" << endl;

Stek *u=NULL;

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;

cout<<rus(" * 0. Выход")<<endl;

cout<<rus(" ***********************")<<endl;

cout<<rus("ntЗадайте действие: ");

cin>>n;

SetConsoleTextAttribute(hConsole, 7);

switch (n)

{

case 1: cout<<rus("Введитеновоеавто: ");vvod(x);

dobavlenie(&u, x); cout<<rus("nАвтоДобавлено!an"); break;

case 2: Print(u); break;

case 3: Print(u); vyezjaet_iz_garaja(&u); break;

case 0: Clear(&u); break;

default: SetConsoleTextAttribute(hConsole, 12);

cout<<rus("Нет такого ЧИСЛА!!!")<<endl;

SetConsoleTextAttribute(hConsole, 7);

}

cout<<endl;

}while (n!=0);

return 0;

}

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

1.И.Ш. Хабибуллин Программирование C++: Пер. с англ. - 3-е изд. - СПб.: БХВ-Петербург, 2006. - 512 с.

2.Сайт: www.victor192007.narod.ru

.Конспект лекций по дисциплине «Программирование на языках высокого уровня».