Замечание.
1.
Работу остальных членов-функций класса Stack рассмотрите самостоятельно.
2.
Описание класса Stack оформим в виде отдельного файла с именем stack.cpp. В дальнейшем при решении практических задач будем подключать данный файл к проекту с помощью директивы
#include "stack.cpp" после using namespace std Обратите внимание на то, что сам файл stack.cpp должен находится в той же папке, что и файл с кодом программы.
5.3. Решение практических задач с использованием стеков
1. Дан текстовый файл input.txt, в котором через пробел записаны натуральные числа.
Переписать его содержимое в файл output.txt в обратном порядке.
43
Оператор 1: определяется указатель г, который устанавливается на верхний элемент стека.
#include
using namespace std;
#include
"stack.cpp"
//подключение файла с реализацией класса Stack
int main()
{
Stack t; int i; ifstream in(
"input.txt"
); ofstream out(
"output.txt"
);
//пока не достигнут конец файла input.txt читаем из него элементы while
(in >> i)
t.Push(i);
//и помещаем их в стек
in.close(); while
(!t.Empty())
//пока стек не пуст
out << t.Pop() <<
" "
;
//извлекаем из него элементы и выводим в файл
out.close(); return
0;
}
Результат работы программы:
________input.txt_________ ________output.txt________
1 2 3 4 45 7 4 5 6 7 8 9 10 12 12 10 9 8 7 6 5 4 7 45 4 3 2 1 2. Дана последовательность натуральных чисел. Перед каждым элементом равным х вставить элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt (в первой строке файла через пробел записаны х и у, во второй - последовательность чисел), выходная последовательность целых чисел записывается в файл output.txt.
Идея решения заключается в следующем. Перепишем все числа из файла input.txt в стек. По свойству стека все числа там будут находиться в обратном порядке. Нам надо сохранить прямой порядок, а кроме того, вставить символы. Поэтому введем второй стек и будем переписывать числа из первого во второй по следующему алгоритму. Берем число первого стека, переписываем во второй стек. Далее проверяем: если это число х, то во второй стек запишем число у. Таким образом, во втором стеке числа у будут вставлены после чисел х, но при извлечении из стека порядок поменяется на противоположный
Следовательно, остается только извлекать по одному элементу из второго стека и переписывать в выходной файл.
#include
using namespace std;
#include
"stack.cpp"
//подключение файла с реализацией класса Stack
int main()
{
Stack t, t1;
//инициализируем два стека
int i, x, y;
ifstream in(
"input.txt"
); ofstream out(
"output.txt"
);
44
in >> x >> y; while
(in >> i) t.Push(i); in.close();
//пока стек t не пуст, переписываем из него числа в стек t1, вставляя
//после каждого элемента со значением х элемент со значением у
while
(!t.Empty())
{ i = t.Pop(); t1.Push(i); if
(i == x) t1.Push(y);
}
//переписываем содержимое стека t1 в выходной файл
while
(!t1.Empty())
{ out << t1.Pop() <<
" "
;
} out.close(); return
0;
}
Результат работы программы:
________input.txt_________ ________output.txt________
4 0 1 0 4 3 0 4 45 7 0 4 6 7 0 4 1 4 3 4 45 7 4 6 7 4
3. В файле находится текст, в котором имеются скобки (). Используя стек, проверить, соблюден ли баланс скобок в тексте.
Замечание. Теперь стек должен обрабатывать символы. Поэтому в классе Stack тип информационного поля стека изменяется на char. Таким же образом будут изменены типы соответствующих параметров методов класса и типы возвращаемых значений методов класса.
#include
using namespace std;
#include
"stack.cpp"
//Функция, подсчитывающая баланс скобок. Возвращает:
//0 - если баланс скобок соблюден;
//1 - если имеется лишняя открывающая скобка;
//-1 - если имеется лишняя закрывающая скобка.
int
Balans()
{
Stack t;
//описываем стек, в который из всего текста будут
//заноситься только открывающиеся скобки
ifstream in(
"input.txt"
); char c;
45
while
(in >> c)
{ switch
(c)
{ case
'(': t.Push(c); break
;
//если считанный символ (, то //записываем его в стек case
')':
//если считанный символ ), то в стеке //должна находиться соответствующая ему ( if
(t.Empty())
//если стек пустreturn -1; // возвращаем -1 - код лишней закрывающейся скобки else
//иначе выбираем из него одну открывающую скобкуt.Pop();
}
} in.close();
/* Если после того, как весь текст обработан, стек пустой, то баланс скобок в тексте соблюден -
возвращаем код 0. В противном случае, в стеке находятся открывающиеся скобки, которым не соответствуют закрывающиеся - возвращаем код 1. */ if
(t.Empty())
return
0; else return
1;
} int main()
{ ofstream out(
"output.txt"
); int i = Balans();
//вызываем функцию Balans0 //обрабатываем значение, возвращенное функцией Balans if
(i == 0) out <<
"ok"
; if
(i == 1) out <<
"error: ("
; if
(i == -1) out <<
"error: )"
; out.close(); return
0;
}
46
Результат работы программы:
________input.txt_________ ________output.txt________
(5-x*(4/x-(x+3)/(y-2)-y)-9 error: (
________input.txt_________ ________output.txt________
(5-x)*(4/x-(x+3)/(y-2)-y)-9 ok
________input.txt_________ ________output.txt________
(5-x)*(4/x-(x+3)/(y-2)-y))-9 error: )
________input.txt_________ ________output.txt________
7+9-x/2+4-b*3 ok
5.4. Применение исключений и шаблонов
В пособии [9] был рассмотрен механизм обработки исключительных ситуаций в
C++. Данный механизм очень полезен при работе со стеками. Так, извлечь элемент из стека или посмотреть значение верхнего элемента стека возможно только тогда, когда стек не пуст. Чтобы обработать указанную ситуацию, мы будет использовать следующий класс:
#include
#include
using namespace std; class
StackException
: public exception
{ public
:
StackException(
const string
& message =
""
): exception
(message.c_str()) {}
};
Данный класс оформим в отдельный файл exception.срр и подключим его к файлу stack.срр, в котором предложена реализация класса Stack.
В пособии [9] был также рассмотрен механизм создания и использования шаблонов-функций. Аналогичным образом можно создавать классы-шаблоны.
Рассмотрим подробно, как будет выглядеть класс Stack после добавления в него механизма обработки исключений и шаблонов:
#include
"exception.cpp"
//подключение класса StackException
template
<
class
Item
>
//описание класса-шаблона, где Item тип данных
class
Stack
//переданный в класс
{ struct
Element
{
Item inf;
47
Element
*next;
Element (
Item x,
Element
*p): inf(x), next(p) {}
};
Element
*head; public
:
Stack(): head(0) {} bool
Empty()
{ return head == 0;
}
Item
Pop()
{ if
(Empty())
//если стек пуст, то генерируем исключение
{
throw
StackException
(
"StackException: Pop — стек пуст"
);
} else
//иначе извлекаем элемент из стека
{
Element
*r = head;
Item i = r->inf; head = r->next; delete r; return i;
}
} void
Push(
Item data)
{ head = new
Element
(data, head);
}
Item
Top()
{ if
(Empty())
//если стек пуст, то генерируем исключение
{
throw
StackException
(
"StackException: Top — стек пуст"
);
} else
//иначе возвращаем значение верхнего элемента стека
{ return head->inf;
}
}
};
48
Замечание. Далее при объектно-ориентированной реализации списков будем использовать классы-шаблоны. Более подробно познакомиться с разработкой и использованием классов- шаблонов можно изучив дополнительную литературу [6, 7, 10, 11].
5.5.Очередь Очередь - это частный случай списка, добавление элементов в который выполняется в один конец (хвост - tail), а выборка и просмотр осуществляются с другого конца (головы - head). Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO
(fist in - fist out, первым пришел - первым вышел). Очередь проще
всего представить в виде узкой трубы, в один конец которой бросают мячи, а из другого конца они вылетают.
Понятно, что мяч, который был брошен в трубу первым, первым и вылетит.
В программировании очереди применяются при математическом моделировании, диспетчеризации задач операционной системы, буферном вводе/выводе.
Рассмотрим организацию очереди с помощью структуры, изображенной на рис.
5.4. Отличие очереди от стека в том, что у очереди два указателя: первый (head) указывает на первый элемент очереди, второй (tail) - на последний элемент.
Рис. 5.4. Очередь
Базовый элемент очереди содержит:
•
информационное поле inf, которое может быть любого типа, кроме файлового, и будет использоваться для хранения значений, например, чисел, символов, строк;
•
поле-указатель next, в котором хранится адрес следующего элемента очереди, и которое будет использоваться для организации связи элементов.
Замечание. В общем случае базовый элемент очереди может содержать несколько информационных полей
Предложенный базовый элемент очереди может быть описан следующим образом: struct
Element
{
Item inf;
//информационное поле типа ItemElement
*next;
//указатель на следующий элемент очереди Element(
Item x): inf(x), next(0) {}
//конструктор};
49
Тогда указатели на первый и последний элементы очереди могут быть описаны следующим образом:
Element
*head,*tail;
Как уже говорилось, доступ к элементам очереди возможен в двух точках: из одной точки - (головы) можно брать и просматривать элементы, во второй точке
(хвост) можно добавлять элементы. С учетом вышеизложенного представим объектно-ориентированную реализацию очереди с помощью класса Queue:
#include
"exception.cpp"
//подключаем класс QueueException, рассмотрим его позже
template
<
class
Item
>
//класс-шаблон очередь
class
Queue
{
struct
Element
{
Item inf;
Element
*next;
Element
(Item x): inf(x), next(0) {}
};
Element
*head, *tail;
//указатели на начало и конец очереди
public
:
Queue(): head(0), tail(0) {} bool
Empty()
//возвращает true, если очередь пуста, иначе false
{ return head == 0;
}
Item
Get()
{ if
(Empty())
//если очередь пуста, то генерируем исключение
throw
QueueException
(
"QueueException: get - queue empty"
); else
//иначе извлекаем элемент из головы очереди
{
Element
*t = head;
Item i = t->inf; head = t->next; if
(head ==
NULL
) tail =
NULL
; delete t; return i;
}
}
50
void
Put(
Item data)
{
Element
*t = tail;
//устанавливаем вспомогательный указатель //на последний элемент очередиtail = new
Element
(data);
//формируется новый элемент, на //который будет указывать tailif
(!head)
//если до этого очередь была пуста, то новый //элемент является и первым, и последним, поэтому //указатель head устанавливаем на tail head = tail; else t->next = tail;
//иначе новый узел помещаем в конец очереди}
};
Примечание: В языке C++, NULL – это то же самое, что и 0.
Более подробно рассмотрим базовые операции помещения элемента в очередь, предполагая, что у нас создан экземпляр класса Queue
q. Это значит, что выполнился конструктор, который создал пустую очередь с указателями: head=NULL, tail=NULL.
Первоначально добавим в очередь элемент 3, для чего выполним команду q.Put(3).
Во вспомогательном указателе t (см. реализацию функции Put) сохраняется значение указателя на последний элемент, т.е. NULL.
Затем происходит создание элемента, в информационную часть которого заносится значение 3, а в указатель next значение NULL. После чего tail становится указателем на этот элемент.
Далее производится проверка: пуста ли очередь (указывает ли head на какой- то элемент или его значение NULL)? В данном случае очередь пуста, поэтому head будет указывать туда же, куда и tail, т.е. на новый элемент со значением 3. Таким образом получили очередь из одного элемента:
51
Или я не умею пользоваться вордом, или сам ворд такой кривой... Вот откуда здесь так много пустого места? Почему отступы такие кривые? Ыыыыыыыы……
Теперь добавим в очередь элемент со значением 8, выполняя команду q.Put(8). При этом создается вспомогательный указатель, который указывает на последний (в нашем случае, единственный) элемент:
Затем происходит создание элемента, в информационную часть которого заносится значение 8, а в указатель next значение NULL. После чего tail становится указателем на этот элемент:
Далее производится проверка: пуста ли очередь (указывает ли head на какой-то элемент или его значение NULL)? В данном случае очередь не пуста, поэтому следующим за элементом, на который указывает t становится элемент, на который указывает tail.
В итоге получаем очередь из двух элементов, которые находятся в очереди в том же порядке, в каком их туда поместили.
Функция Get, которая извлекает верхний элемент из очереди, аналогична функции
Put для стека. Отличием является следующий оператор, добавленный в функцию Get: if
(head ==
NULL
) tail =
NULL
;
52
который говорит о том, что если после
удаления элемента очередь становится пустой, то и указатель tail нужно «обнулить». Разберите данную функцию самостоятельно.
Функция Empty полностью совпадает с соответствующей функцией для стека.
Замечание. Класс QueueException помещен в отдельный файл exception.срр и выглядит следующим образом:
#include
#include
using namespace std; class
QueueException
: public exception
{ public
:
QueueException(
const string
& message =
""
): exception
(message.c_str()) {}
};
5.6.
Решение практических задач с использованием очереди
1.
Даны файлы data1.txt и data2.txt, компонентами которых являются натуральные числа. Переписать содержимое файла data1.txt в файл data2.txt и наоборот без использования вспомогательного файла.
#include
#include
using namespace std;
//подключаем файл с реализацией класса-шаблона очередь
#include
"queue.срр"
int main()
{
Queue
<
int
> t; int i;
//описываем входной поток и связываем его с data1.txt
ifstream in(
"data1.txt"
);
while
(in >> i)
//пока не конец файла считываем из него числа
t.Put(i);
//кладем их в очередь
in.close();
//закрываем поток, связанный с файлом data1.txt
//описываем входной поток и связываем его с data2.txt
ifstream in1(
"data2.txt"
);
//описываем выходной поток и связываем его с data1.txt
ofstream out(
"data1.txt"
);
while
(in1 >> i)
//пока не конец файла data2.txt считываем из него числа
out << i <<
" "
;
//записываем в файл data1.txt
in1.close();
//закрываем поток, связанный с файлом data2.txt
53
out.close();
//закрываем поток, связанный с файлом data1.txt
//описываем выходной поток и связываем его с data2.txt
ofstream out1(
"data2.txt"
); while
(!t.Empty())
//пока очередь не пуста
//выбираем из нее элементы и записываем в data2.txt
out1 << t.Get() <<
"
"
;
out1.close();
//закрываем поток, связанный с файлом data2.txt
return
0;
}
Результат работы программы:
До запуска программы
___datal.txt___ ___data2.txt___
7 515 46 46 25 8 12 45 6 6
После запуска программы
___datal.txt___ ___data2.txt___
25 8 12 45 6 6 7 515 46 46 2. Дана последовательность натуральных чисел. Создать из них очередь и каждый ее элемент, равный х заменить на элемент равный у. Входная последовательность целых чисел и заданные числа х и у хранятся в файле input.txt, выходная последовательность целых чисел записывается в файл output.txt.
#include
#include
using namespace std;
//подключаем файл с реализацией класса-шаблона очередь
#include
"queue.срр"
int main()
{
Queue
<
int
> t; int i, x, y; ifstream in(
"input.txt"
); ofstream out(
"output.txt"
); in >> x >> y;
//пока файл не пуст, считываем из него очередной элемент
//если он равен х, то в очередь помещаем у, иначе исходное число
while
(in >> i)
{ if
(i == x) t.Put(y); else t.Put(i);
}
54
in.close();
//пока очередь не пуста, извлекаем из нее элементы и записываем //в выходной файлwhile
(!t.Empty())
out << t.Get() <<
" "
; out.close(); return
0;
}
Результата работы программы: ________input.txt________ _______output.txt_______
70 0 0 1 3 0 5 2 5 0 2 0 9 3 0 0 7 7 1 3 7 5 2 5 7 2 7 9 3 7 7
5.7.Однонаправленный список общего вида Мы рассмотрели частные случаи списков (стек и очередь) и их односвязную реализацию. Заметим, что стек имеет одну «точку доступа», очередь - две «точки доступа». В общем случае список можно представить в виде линейной связанной структуры с произвольным количеством «точек доступа» (см рис.5.5), что позволяет определить следующие операции над списком: инициализация списка, добавление и удаление
элемента из произвольного места списка, поиск элемента в списке по ключу, просмотр всех элементов без их извлечения списка.
Рис. 5.5. Структура однонаправленного списка с указателями head на начало списка и cur - на произвольный элемент списка
Реализация однонаправленного списка зависит от решаемой задачи и предпочтений программиста. Рассмотрим объектно-ориентированную реализацию однонаправленного списка, представленного на рис.5.5.
#include
"exception.cpp" template
<
class
Item
> class
List
{ struct
Element
{
Item inf;
Element
*next;
Element
(Item x): inf(x), next(0) {}
};
55
Element
*head;
//указатель на начало списка
int size;
//количество элементов в списке
//возвращает указатель на элемент списка с номером index
Element
* Find(
int index)
{ if
((index<1)||(index>size))
//если индекс элемента списка
{
//находится вне диапазона, то
return
NULL
;
//возвращаем NULL
} else
//иначе
{
//устанавливаем указатель на начало списка
Element
*cur = head;
for
(
int i = 1; i < index; i++)
//и перемещаемся по
списку
{
//на элемент с номером index
cur = cur->next;
} return cur;
//возвращаем указатель на требуемый элемент
}
} public
:
List(): head(0), size(0) {}
//конструктор класса
List()
//деструктор класса
{ while
(!Empty())
//пока список не пуст
Remove(1);
//удаляем первый элемент списка
} bool
Empty()
//проверка пустоты списка
{ return head == 0;
} int
GetLength()
//возвращает количество элементов в списке
{ return size;
}
//возвращает значение элемента списка по его номеру
Item
Get(
int index)
{ if
((index<1)||(index>size)) throw
ListException
(
"ListException: get — list error"
);
56
else
{
Element
*r = Find(index);
Item i = r->inf; return i;
}
}
//осуществляет вставку элемента со значением data в позицию index
void
Insert(
int index, Item data)
{ if
((index<1)||(index>size+1))
{ throw
ListException
(
"ListException: insert — list error"
);
} else
{
//создаем новый элемент
Element
*newPtr = new
Element
(data); size
= GetLength()+1;
//увеличиваем размерность списка
if
(index == 1)
//если вставку производим в позицию 1
{
//то см. рис. 5.6
newPtr->next = head; head = newPtr;
} else
//иначе см. рис. 5.7
{
Element
*prev = Find(index-1); newPtr->next = prev->next; prev->next = newPtr;
}
}
}
//осуществляет удаление элемента из списка с номером index
void
Remove(
int index)
{ if
((index<1)||(index>size))
{ throw
ListException
(
"ListException: remove — list error"
);
} else
{
Element
*cur;
//объявляем вспомогательный указатель
--size;
//уменьшаем размерность списка
if
(index==1)
//если удаляем первый элемент
{
//то см. рис. 5.8
cur = head; head = head->next;
}
57
else
//иначе см. рис.5.9{
Element
*prev = Find(index-1); cur = prev->next; prev->next = cur->next;
} cur->next =
NULL
; delete cur;
}
}
//вывод элементов списка в глобальный поток out void
Print()
{
for
(
Element
*cur = head; cur!=
NULL
; cur = cur->next)
{ out << cur->inf <<
" "
;
} out << endl;
}
};
Скачать 1.93 Mb.