4.5.2Пометка элементов с оберткой

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

struct Element {

int item;

bool exists;

};

const int size=10;

Element numbers[size];

void init() {

for (int i=0; i<size; i++) {

numbers[i].exists = false;

}

}

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

void print() {

for (int i=0; i<size; i++) {

if (numbers[i].exists) {

cout << numbers[i].item << " ";

}

}

cout << endl;

}

Остальные функции реализуются аналогично.

int find(int x) {

for (int i=0; i<size; i++) {

if (numbers[i].exists && numbers[i].item==x) {

return i;

}

}

return -1;

}

int getEmptyPosition() {

for (int i=0; i<size; i++) {

if (!numbers[i].exists) {

return i;

}

}

return -1;

}

void add(int x) {

int pos = getEmptyPosition();

if (pos != -1) {

numbers[pos].item=x;

numbers[pos].exists=true;

} else {

cout << "No place\n";

}

}

void remove(int x) {

int pos = find(x);

if (pos != -1) {

numbers[pos].exists=false;

} else {

cout << "No such element\n";

}

}

4.5.3Реализация стека на основе массива

Стек (stack) – это динамическая структура данных, позволяющая добавлять элементы в конец и удалять из конца. Стек называют LIFO-структурой (Last In – First Out, последний вошел – последний вышел). Стек – это стопка, и лучше представлять ее себе как стопку чего-то тяжелого, например, стопку кирпичей: вы можете положить кирпич сверху, но вытащить кирпич из середины, из-под других кирпичей – нет. Концепция стека используется в ряде алгоритмов, таких как обход графа в глубину, рекурсия, алгоритмы с возвратом и др.

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

Для реализации стека нам потребуются следующие элементы:

• массив для хранения содержимого стека (обозначим его через contents);

• переменная, отвечающая за текущее количество элементов (n);

• константа, равная максимальному количеству элементов в стеке (max_size).

const int max_size=10;

string contents[max_size];

int n=0;

Изначально стек пуст и n==0. Новый элемент добавляется на первую свободную позицию от начала, которая определяется значением переменной n. После этого n увеличивается на единицу. Например, при n==0 первая свободная позиция имеет индекс 0, при n==1 ее индекс равен 1 и т.д. Напомним, что индексы массива нумеруются с нуля. Таким образом, все элементы стека расположены в начале массива, и вывод элементов имеет следующий вид:

void print() {

for (int i=0; i<n; i++) {

cout << contents[i] << " ";

}

cout << endl;

}

Количество выводимых элементов определяется переменной n, поэтому в зависимости от количества добавленных и удаленных элементов эта процедура будет работать по-разному. Теперь посмотрите на реализацию операции добавления, которая для стека называется специальным образом – push(), затолкнуть.

void push(string x) {

contents[n] = x;

n++;

}

В эту функцию лучше добавить проверку на заполненность стека:

void push(string x) {

if (n==max_size) {

cout << "Stack is full\n";

} else {

contents[n] = x;

n++;

}

}

Для удаления элемента достаточно уменьшить n на единицу, что позволит пометить последний элемент как удаленный. После этого операция вывода элементов не захватит этот элемент. Перед удалением желательно проверить, не является ли стек пустым. Для удаления элемента из стека существует специальное название – pop().

void pop() {

if (n==0) {

cout << "Stack is empty\n";

} else {

n--;

}

}

Наконец, рассмотренные операции можно оформить в виде меню:

for (;;) {

cout << "1 - Print\n2 - Push\n3 - Pop\n";

cout << "0 - Exit\nYour choice - ";

int choice; cin >> choice;

string newstr;

switch(choice) {

case 1 : print(); break;

case 2 :

cout << "New string: ";

cin >> newstr;

push(newstr);

print();

break;

case 3 : pop(); print(); break;

case 0 : exit(EXIT_SUCCESS);

default : cout << "Error\n";

}

system("pause"); system("cls");

}