Очередь – это связный список, закон построения которого следующий: новый элемент всегда ставится в конец списка, а удаление элемента происходит из его начала [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