Файл: Связные списки,стеки, очереди.doc

Листинг программы, использующей очередь.

Program ………..;

Type ….{ описание типов для реализации очереди}

…….

Var N:integer;

HeadQueue: TQueue; // HeadQueue – указатели на очередь

FileName:string; // имя файла с данными

F:text; // файловая переменная

begin

InitQueue(HeadQueue); // инициализация очереди

Write(‘Введите имя файла с данными’);

Readln(FileName);

Assign(F,FileName); // связываем файловую переменную f с именем файла FileName

Reset(F); // открываем файл для чтения

While not Eof(F) do

begin

Read(F,N) ; // читаем из файла число в переменную N

If N>=0 then InQueue(HeadQueue,N) // помещаем число N в очередь

else Writeln(N); // иначе выводим на экран

end;

Close(f);

While not QueueIsEmpty(HeadQueue) do // пока очередь не пуст, будем извлекать

// данные и печатать на экране

begin

Writeln(OutQueue(HeadQueue));

end;

Readln;

end.

Задачи.

1. Реализовать функцию поиска элемента Е в односвязном списке L.

2. Реализовать процедуру обмена местами двух элементов списка SwapEtems(Pl, P2: PElem), где P1 и Р2 — указатели на элементы, путем переустановки ссылок в списке.

3. Подсчитать число максимальных элементов списка.

4. Найти среднее значение элементов списка.

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

6. Исключить из списка элементы, содержащие заданное число.

7. В списке A хранится информация о людях (фамилия, имя, отчество, профессия). Имеется список В, содержащий перечень профессий. Удалить из списка А тех людей, чья профессия не указана в списке В.

8. Дан список штучных товаров, хранящихся на складе (наименование, цена). В списке могут присутствовать одинаковые товары. Необходимо:

1. составить прайс-лист на товары (список, содержащий перечень различных товаров и цен на них);

2. вычислить среднюю цену на каждый товар;

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

9. Имеется N городов. Задан список пар городов (i,j), между которыми существует прямая дорога. Напечатать список городов, которые напрямую сообщаются с более чем тремя городами.

10. Дан список слов. Из каждой группы подряд идущих одинаковых слов оставить только одно.

11. Дан текстовый файл. Распечатать слова, имеющие максимальную длину.

12. Дан текстовый файл. Провести частотный анализ слов.

13. Дан текстовый файл с целыми числами. Распечатать сколько какое число встречается раз.

14. Дан список вещественных чисел. Проверить, упорядочены ли числа по убыванию.

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

16. Дан список вещественных чисел. Проверить, образуют ли числа, хранящиеся в списке арифметическую прогрессию.

17. Дан список вещественных чисел. Проверить, образуют ли числа, хранящиеся в списке геометрическую прогрессию.

18. Описать процедуру, которая вставляет в список, элементы которого упорядочены по неубыванию, новый элемент так, чтобы сохранялась упорядоченность.

19. Написать процедуру слияния двух упорядоченных списков из целых чисел в один упорядоченный список.

20. Даны два стека. Используя операции Извлечь, Занести и функцию ПустЛиСтек подсчитать общее число элементов в стеках. В качестве вспомогательных структур разрешается использование переменных целых типов. Алгоритм должен предусматривать восстановление исходного расположения элементов в стеках.

21. Распечатать возрастающие серии последовательности целых чисел в обратном порядке (серия — упорядоченная подпоследовательность максимальной длины).

22. Дан текстовый файл А. Переписать его содержимое в файл В, удалив при этом слова, длина которых меньше заданной.

23. Дан текстовый файл А. Переписать его содержимое в файл В, перенося при этом в конец каждой строки все входящие в нее знаки препинания.

24. Даны две очереди X и Y, содержащие вещественные числа. Из каждой очереди одновременно извлекается по одному числу, х и у соответственно. Если х < у, то число (х + у) помещается в конец очереди X, иначе число (х–у) помещается в конец очереди Y. Необходимо определить число шагов, через которое одна из очередей станет пустой.

25. В текстовом файле записаны целые числа. Распечатать сначала положительные числа, а потом отрицательные (порядок следования должен остаться без изменения).

26. В текстовом файле записаны целые числа. Распечатать сначала положительные числа, а потом отрицательные (порядок следования должен стать обратным)

27. Проверить правильность расстановки скобок в арифметическом выражении с использованием стека. По правилам записи арифметических выражений первой должна закрываться последняя открывающая скобка, и число открывающих и закрывающих скобок должно совпадать. В выражениях используются круглые, квадратные и фигурные скобки. Предусмотреть ошибки: несоответствие скобок (a*k[d-l}) и непарные скобки (несоответствие числа открывающих и закрывающих)