24. Стеки и очереди

Цель работы - закрепление навыков работы со структурами данных

24_Стеки и очереди.pdf

Задания и указания по их выполнению

Задание 1. Реализуйте стек на массиве в соответствии с предложенным ниже интерфейсом

#define NMAX 100

#define TYPE char

#define FTYPE "%3c,"

typedef struct Stack {

int top;

TYPE data[NMAX];

} stack;

int isempty(stack *s);// проверить, если стек пуст {top==0} вернуть 1, иначе 0

int isfull(stack *s);// проверить, если стек полон {top==NMAX-1} вернуть 1, иначе 0

int push(stack *s, TYPE a);//поместить элемент а в стек {top=top+1, data[top]=a}, если стек не полон

TYPE pop(stack *s);// вернуть элемент {data[top]}, удалив его из стека {top=top-1}, если стек не пуст

TYPE top(stack *s);//вернуть значение элемента в вершине стека {return data[top]}

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

Для вывода содержимого стека на экран (без его изменения) воспользуйтесь функцией:

void display(stack *s) {

int i = s->top;

while (i>0)

printf(FTYPE, s->data[i--]);}

Задание 2. Реализуйте очередь на связанном списке в соответствии с предложенным ниже интерфейсом

struct Node {

TYPE data;

struct Node * next;

};

typedef struct {

struct Node *queue;

struct Node * front;

struct Node * back;

} queue_list;

void enQueue(queue_list *que, TYPE element);//добавить элемент в очередь

TYPE deQueue(queue_list *que);//извлечь элемент из очереди

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

Пример программы работы с очередью

Задание 3. Выполните один из вариантов индивидуальных заданий

1. Напишите программу, заполняющую стек числами, введенными с клавиатуры и затем меняющую местами верхнюю и нижнюю половины стека ( т.е. из стека 1 – 2 – 3 – 4 должен получиться стек 4 – 5 – 6 – 1 – 2 – 3). При этом можно пользоваться только функциями Push и Pop и другим стеком.

2. Определите правильность расстановки скобок в веденном пользователем арифметическом выражении. Возможно использование скобок трех типов: круглые скобки (), квадратные скобки [] и фигурные скобки {}.

3. Напечатать текстовый файл, расположив слова в строках в обратном порядке.

4. Дана строка вида s*w (s, w – строки из символов, не содержащих символа *). Чтение разрешено по одному символу. Проверить, является ли строка w обратной строке s. Например, для случая s = ABCDEF, w =FEDCBA ответ положительный.

5.Вычислите арифметическое выражение. Выражение содержит бинарные операции + и -. В качестве операндов для простоты используются цифры от 0 до 9. Выражение является синтаксически правильным (нет скобок и порядок действий не меняется) и заканчивается знаком =. Например, 5+3-9= Используйте два стека: стек операций, элементы которого имеют тип char и стек операндов, содержащий элементы целого типа.

6. Напишите программу, формирующую очередь целых чисел и затем удаляющую из нее все числа, меньшие заданного числа (Использовать только enQueue() и deQueue()

7. Напишите программу, определяющую, является ли введенная строка символов палиндромом (то есть читается ли она одинаково слева направо и справа налево).

8. За один просмотр файла, элементами которого являются целые числа, и без использования дополнительных файлов переписать его элементы в другой файл так, чтобы первоначально были записаны все числа, меньшие заданного, а затем все числа из отрезка [a, b] и все остальные. Взаимный порядок чисел в каждой из групп должен быть сохранен. (Числа последовательно считываются из файла. Если очередное число меньше а, то оно записывается в файл, если оно принадлежит отрезку [a, b], то заносится в первую очередь, иначе – во вторую. После завершения чтения в выходной файл записываются числа из первой и второй очередей)

9. Содержимое текстового файла f, разделенного на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в него цифры в обратном порядке.

10. Содержимое текстового файла f, разделенного на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в него цифры с сохранением порядка их следования.

Google Sites

Report abuse