Лабораторная работа 2. ОДНОСВЯЗНЫЕ И ДВУСВЯЗНЫЕ ЛИНЕЙНЫЕ СПИСКИ

Задание

Опишите классы-списки, необходимые для решения задачи, указанной в вашем варианте задания, и реализуйте его методы.

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

Варианты заданий

  • 1. Описать односвязный линейный список, каждый элемент которого представляет собой запись, состоящую из двух полей: символ и количество его повторений в тексте. Сформировать список из заданного текста. Для создания списка использовать метод вставки в список в отсортированном порядке.
  • 2. Сложение длинных чисел. Используя двусвязные циклические списки сложить два числа: х =134557952499317879 и у = 79349864365110 . Числа разбить на группы по девять цифр, которые будут являться элементами списка. Результат сложения занести в циклический список.
  • 3. Задача Джозефуса. По кругу стоит группа людей. С терминала вводятся число п и фамилия человека, с которого начинается счет. Начиная с введенной фамилии, по кругу отсчитывается п человек, /7-й выбывает из круга и т.д. Выводить фамилии исключаемых из круга людей. Задачу решить, используя односвязный циклический список.
  • 4. Создать два односвязных циклических списка с целочисленными элементами. Переписать в односвязный линейный список элементы с совпадающими значениями.
  • 5. Описать односвязный циклический список символов. Реализовать метод вставки, который выполняет вставку отсутствующего в списке символа в его конец и перемещение в начало элемента с присутствующим в списке значением. Продемонстрировать работу метода.
  • 6. Проверить правильность расстановки скобок (круглых, квадратных, фигурных и угловых) в арифметическом выражении. Для слежения за скобками воспользоваться односвязным циклическим списком.
  • 7. Описать двусвязный линейный список строк. Реализовать метод вставки, который выполняет вставку отсутствующего в списке символа в его конец и перемещение на один элемент к началу списка элемента с присутствующим в списке значением.
  • 8. Из односвязного списка с фамилиями студентов двух групп сформировать два циклических по группам, причем вставка в циклические списки должна выполняться в отсортированном порядке.
  • 9. С использованием односвязного циклического списка определить правильность вложения циклов в программе на языке Бейсик, состоящей из произвольного количества последовательно расположенных или вложенных инструкций:
  • 10 FOR х=а ТО b STEP с
  • 30 NEXT с где х — переменная цикла. Для каждого цикла выводить сообщение вида: «Цикл по х открыт», «Цикл по х закрыт».
  • 10. Создать односвязные списки студентов двух групп с полученными на экзаменах оценками. Сформировать в алфавитном порядке односвязный циклический список студентов, получивших отличные оценки.
  • 11. Сформировать линейный список строк. Исключить из него последние три элемента. Скопировать в двусвязный циклический список вторую половину его элементов, начиная с конца.
  • 12. С использованием односвязного циклического списка определить правильность вложения циклов в программе на языке Бейсик, состоящей из произвольного количества последовательно расположенных или вложенных инструкций:
  • 10 FOR х=а ТО b STEP с
  • 30 NEXT с

где х — переменная цикла, один оператор NEXT может завершать одновременно несколько вложенных циклов (например: NEXT x,y,z). Для каждого цикла выводить сообщение вида: «Цикл по х открыт», «Цикл по х закрыт».

  • 13. Описать односвязный циклический список, тип значения элемента которого — запись из двух полей: символ и количество его повторений в тексте. Сформировать список из заданного текста. Переписать в линейный список элементы с русскими буквами.
  • 14. Сформировать два двусвязных циклических списка с элементами — фамилиями клиентов. Удалить из первого списка клиентов, находящихся в двух списках.
  • 15. Сформировать циклический список целых чисел. Скопировать элементы исходного списка в линейный список таким образом, чтобы они были расположены в нем в порядке, обратном к исходному.
  • 16. Сформировать двусвязный список, каждым элементом которого являются сведения о студенте (фамилия, номер группы, год рождения). Переписать в двусвязный циклический список студентов заданной группы в порядке, обратном их расположению в исходном списке.
  • 17. Сформировать два циклических списка целых чисел. Слить их в один список, так чтобы в нем были только различные элементы.
  • 18. Описать односвязный циклический список, тип значения элемента которого — запись из двух полей: символ русского алфавита и количество его повторений в тексте. Сформировать список из заданного текста. С использованием односвязного линейного списка расположить элементы исходного списка в обратном порядке.
  • 19. С использованием односвязного циклического списка смоделировать работу очереди, создав необходимые подпрограммы — надстройки. Продемонстрировать их работу.
  • 20. Сформировать два списка с фамилиями клиентов. Слить оба списка в циклический, расположив клиентов через одного.
  • 21. Сформировать два односвязных списка целых чисел. Слить их в односвязный циклический список так, чтобы элементы были расположены по возрастанию значений.
  • 22. В односвязном циклическом списке, каждый элемент которого является совокупностью двух целых значений, заменить нулевыми все элементы с заданной суммой.
  • 23. Создать линейные списки студентов двух групп с фамилиями, расположенными в алфавитном порядке (с использованием метода вставки в список в отсортированном порядке). Слить их в один циклический список.
  • 24. По кругу стоит группа людей. С терминала вводятся число п и фамилия человека, с которого начинается счет. Начиная с введенной фамилии, по кругу отсчитывается п человек, п-й выбывает из круга и т.д. Выводить фамилии исключаемых из круга людей. Решить задачу с использованием двусвязного циклического списка.
  • 25. Описать односвязный линейный список, тип значения элемента которого — запись из двух полей: символ и количество его повторений в тексте. Сформировать список из заданного текста. Реализовать метод вставки, выполняющий вставку отсутствующего в списке символа в его конец и перемещение на один элемент к началу списка элемента с присутствующим в списке значением.
  • 26. Сформировать два двусвязных циклических списка с элементами — фамилиями клиентов. Слить эти списки в один, таким образом, чтобы он включал в себя фамилии клиентов поочередно из каждого из исходных списков в обратном порядке.
  • 27. Распределить элементы циклического списка по двум линейным спискам следующим образом: в первый список помещаются элементы с начала циклического списка, а во второй — с его конца.
  • 28. Описать двусвязный список строк и реализовать метод возвращения адреса первого с конца и первого с начала элемента с заданным значением. Исключить второй с начала и второй с конца элемент со значением «дом».
  • 29. Реализовать методы возвращения адреса элемента двусвязного циклического списка по его номеру, начиная от начала и от конца списка. С использованием этих методов поменять местами третий с начала элемент списка с третьим с конца.

По кругу стоит группа людей. С терминала вводятся число п и фамилия человека, с которого начинается счет. Начиная с введенной фамилии, в обратную сторону по кругу отсчитывается п человек, /7-й выбывает из круга и т.д. Выводить фамилии исключаемых из круга людей. Задачу решить, используя двусвязный циклический список.

Пример выполнения задания

Сформировать односвязный список из вещественных элементов, хранящихся в файле LW2Dat.txt.

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

//Лабораторная работа 2. Линейные списки.

// Выполнил Сергеев Андрей, группа 999.

// Формирование списка и исключение заданных элементов. //Исходные данные - элементы списка - в файле LW2Dat.txt //Результаты работы помещаются в файл LW2Res.txt program LW2;

{$APPTYPE CONSOLE}

uses

SysUtils,

SymplyLists in 'SymplyLists.pas'; //модуль односвязных списков function WinDOS(const s:string):string;

//Перекодировка русских символов строки s из ANSI в ASCII // Текст подпрограммы в примере выполнения работы 1 end; // WinDOS

var

// экземпляр линейного списка // экземпляр циклического списка //указатель на элемент списка // файлы исходных данных и результатов // знач. текущего и исключаемого эл-тов // количество элементов списка

List : t?st;

CircleList : tCircleList;

Item : pltem; fDat, fRes : Text;

LstVal, DelVal : tValue; quan : Word; begin

Assign(fDat, 'LW2Dat.txt'); Reset(fDat);

Assign(fRes, 'LW2Res.txt'); Rewrite(fRes);

WriteLn(fRes, 'Поиск и удаление заданных эл-тов в списке');

// Создание экземпляров List и CircleList List := t?st.Create; CircleList := tCircle?st.Create;

// Формирование линейного списка while not SeekEof(fDat) do

begin

Read(fDat, LstVal);

List.lnsertHead(LstVal);

end;

quan:= List.Size;

// Вывод элементов линейного списка в файл результатов WriteLn(fRes, 'Сформирован список из quan,' элементов:'); List.WriteTo(fRes);

Write(WinDos('3Ha4eHne исключаемого элемента? ')); ReadLn(DelVal);

WriteLn(fRes, 'Значение исключаемого элемента = DelVal:5:1);

// Поиск и исключение из списка элементов со значением DelVal

repeat

ltem:= List.Search(DelVal);

if ltem<>nil

then List.Delete(ltem);

until ltem=nil;

//Вывод в файл элементов измененного линейного списка WriteLn(fRes, 'Из списка исключено quan - List.Size,' элементов,',

'осталось', List.Size,' элементов:'); List.WriteTo(fRes);

// Перенесение оставшихся элементов в циклический список

while not List.Empty do begin

LstVal:= List.DeleteHead;

CircleList.lnsertRear(LstVal);

end;

WriteLn(fRes, 'Элементы линейного списка перенесены в ',

'циклический, состоящий из ', CircleList.Size,' элементов:'); // Вывод элементов циклического списка в файл результатов CircleList.WriteTo(fRes);

List.Free; CircleList.Free;

Close(fDat); Close(fRes); end.

 
< Пред   СОДЕРЖАНИЕ     След >