Структуры и алгоритмы обработки данных
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) Кафедра «Математическое обеспечение вычислительных систем» ОТЧЕТ по лабораторному практикуму по дисциплине «Структуры и алгоритмы обработки данных» (часть 1) Группы: ВСМ-6-05 Студент: Антонов А.Е. Руководитель: Сыромятников В.П. Москва- 2007 год Лабораторная работа №1 «Кольцевые односвязные списки» Вариант № 1.18 ПОСТАНОВКА ЗАДАЧИ Сформировать линейный односвязный список (ЛОС) с заданным указателем sag, работающий с типом данных Integer. Составить программу, которая должна из заданного списка удалить первый и последний элементы. Составить программу, которая: обеспечивает ввод данных типа Integer с клавиатуры; создает линейный односвязный список из введенных данных с клавиатуры; обеспечивает диалог посредством вывода информационных сообщений и вариантов выполнения дальнейших действий; удаляет первый и последний элементы. в данной программе будут реализованы следующие возможности работы с ЛОС: 0 - Выход из программы 1 - Создание ЛОС 2 - Добавление элемента в начало списка 3 - Добавление элемента в середину списка, перед указанным значением 4 - Добавление элемента в середину списка, после указанного значения 5 - Добавление элемента в конец списка 6 - Удаление элемента в начале списка 7 - Удаление элемента ЛОС стоящего перед указанным значением списка 8 - Удаление элемента ЛОС стоящего после указанного значения списка 9 - Удаление определенного элемента в списке 10 - Удаление элемента в конце списка 11 - Удаление первого и последнего элементов ЛОС 12 - Очистка ЛОС 13 - Поиск элемента по его значению 14 - Сортировка элементов ЛОС 15 - Подсчет количества идентичных по содержанию элементов с указанным ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ Ввод данных осуществляется в диалоговом режиме. Пользователь информируется о вариантах работы в данной программе, об особенностях ввода значений в программе. Далее осуществляется ввод самого списка. Создается линейный односвязный список, с указанием на конец списка (NIL) и по мере ввода данных, ЛОС наполняется, при этом идет сортировка значений элементов по возрастанию. После ввода необходимого количества элементов и ввода нулевого значения, созданный и отсортированный ЛОС выводиться на экран. Далее, следуя указаниям программы, пользователь нажимает Enter, для продолжения работы программы, на экран выводиться перечень возможных вариантов работы в данной программе. После выбора нужного номера операции, в нашем случае (11 - Удалить первый и последний элементы ЛОС) и нажатия на Enter. Происходит удаление первого и последнего элементов ЛОС, с выводом на экран итогового вида ЛОС. ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ СТРУКТУР ДАННЫХ Для хранения данных в соответствии с постановкой задачи необходимо в программе создать Линейный Односвязный Список (ЛОС). Описание типа используемых данных Type chisla = set of '0'..'9'; {множество} TE= Integer; {описание целочисленного типа} WE= String; {описание строкового типа} PE= ^EL; {описание типа указателя} EL= Record {описание типа - запись} inf: TE; {информационная часть элемента, тип Integer} inf2: WE; {информационная часть элемента, тип String} next: PE {адресная часть элемента} End; Var Sag, {указатель начала списка} q, qq: PE; {переменные указателей} oper, st, st2: TE; {переменные целочисленного типа} w, stroka: WE; {переменные строкового типа} ОПИСАНИЕ ПОЛЬЗОВАТЕЛЬСКОГО ИНТЕРФЕЙСА Начальный вид окна программы. Для начала ввода данных в ЛОС, надо определиться с каким типом данных Вы хотели бы работать. После того, как Вы решили с каким типом данных Вы будете дальше работать, Вам нужно ввести номер варианта дальнейшей работы (1 или 2). Для выполнения условий данной лабораторной, выбираем тип Integer (тип целочисленный) предел его от -32768 до 32767. Далее, осуществляется ввод самого списка. Создается линейный односвязный список, с указанием на конец списка (NIL) и по мере ввода данных, ЛОС наполняется, при этом идет сортировка значений элементов по возрастанию. После ввода необходимого количества элементов и ввода нулевого значения, созданный и отсортированный ЛОС выводиться на экран. (Рис.2) Далее, следуя указаниям программы, пользователь нажимает Enter для продолжения работы программы, и на экран выводиться перечень возможных вариантов работы в данной программе.(Рис.3) После выбора нужного номера операции, для выполнения условий нашей задачи, выбираем (11 - Удалить первый и последний элементы ЛОС) и нажимаем на Enter. Происходит удаление первого и последнего элементов ЛОС, с выводом на экран итогового вида ЛОС.(Рис.4) Видно, что с поставленной задачей наша программа справилась. Были удалены первый и последний элементы ЛОС, а потом был выведен итоговый вид ЛОС. ЛИСТИНГ ПРОГРАММЫ Type chisla = set of '0'..'9'; //множество TE= Integer; //описание целочисленного типа WE= String; //описание строкового типа PE= ^EL; //тип указателя EL= Record //описание типа - запись inf: TE; //информационная часть элемента, тип Integer inf2: WE; //информационная часть элемента, тип String next: PE //адресная часть элемента End; Var Sag, //указатель, на начало списка q, qq: PE; //переменные указателей oper, st, st2: TE; //переменные целочисленного типа w, stroka: WE; //переменные строкового типа Procedure Print(sag: PE); {вывод ЛОС} Var q: PE; //адресная переменная Begin q:= sag^.next; //запоминаем адрес первого элемента ЛОС if q= Nil then {проверяем ЛОС на пустоту и если он пустой выводим сообщение о том, что ЛОС пустой и выводим варианты дальнейшей работы программы} begin WriteLn(rus('ЛОС пустой, выводить нечего!')); WriteLn(''); WriteLn(rus('___________________________________________')); WriteLn(rus('Что Вы хотите сделать?')); WriteLn(rus('')); WriteLn(rus('1 - Создать ЛОС')); WriteLn(rus('')); WriteLn(rus('0 - Выйти')); WriteLn(rus('')); WriteLn(rus('Введите номер требуемой операции ')); WriteLn(rus('___________________________________________')); WriteLn(''); end Else {если ЛОС не пустой продолжаем выполнение процедуры} Begin {проверяем, с каким типом данных происходит работа программы} If st = 1 then {если пользователь выбрал вариант работы, работа с типом Integer} //st = 1 - работа с типом данных, Integer Begin While q<>Nil do {проходим по всему ЛОС пока не дойдем до указателя конца списка (Nil)} Begin Write('[',q^.inf,'] '); {выводим на экран значение элемента ЛОС - тип Integer} q:=q^.next; //запоминаем адрес следующего элемента End; WriteLn; end else Begin While q<>Nil do {проходим по всему ЛОС пока не дойдем до указателя конца списка (Nil)} Begin Write('[',q^.inf2,'] '); {выводим на экран значение элемента ЛОС - тип String} q:=q^.next; //запоминаем адрес следующего элемента End; WriteLn(' '); end; End; End; Procedure Proverka (var w: WE); {проверка превышения значения типа Integer} Var a, i: TE; c: char; b: chisla; Begin w:= ''; ReadLn(w); //ввод числа с клавиатуры - тип String While (w = '') or (w='-')do {проверяем, если пользователь не ввел данные или ввел только знак минуса выводим на экран сообщения о не корректные вводе} Begin WriteLn(Rus('Вы не ввели данные или они не корректны, попробуйте еще раз')); WriteLn(' '); Proverka(w); //выполняем рекурсивный вход в процедуру End; for i:= 1 to length(w) do {запускаем цикл проверки числа на корректность ввода, число введено, как строка. По этому мы можем поэлементно проверить каждую цифру} begin b:= ['0','1','2','3','4','5','6','7','8','9']; //множество состоящее из цифр c:=w[i]; {берем каждую цифру из числа проходя от первой до последней} if (c in b) or (c='-') and (i=1) then {сравниваем есть ли цифра из введенного числа во множестве заданных цифр и проверяем какое число было введено, отрицательное или положительное и не стоит ли знак минус в середине числа} else a:= 1; {если число не корректно делаем пометку для дальнейшей проверки} end; if a = 1 then {если число не прошло проверку выводим сообщение о не корректном вводе числа} begin WriteLn(rus('Вы ввели не корректные данные !')); WriteLn(' '); Proverka(w); {выполняем рекурсивный вход в процедуру} end; if (length(w)<5) then {если длина числа меньше 5 знаков заканчиваем проверку, так как число не превышает максимального значения типа Integer, а корректность ввода мы уже проверили} else {если число больше то проверяем его дальше} begin if (length(w)>5) and (w[1]<> '-') then {если длина числа больше пяти знаков, и при этом первый знак, не знак минуса то выводим сообщение о превышении максимального значения типа Integer} begin Write(rus('Вы ввели не число или число превышающее диапазон ')); WriteLn(rus('типа Integer (-32768..32767) ')); WriteLn(''); WriteLn(rus('Введите другое число')); Proverka(w); {выполняем рекурсивный вход в процедуру} end; if (w[1]= '-') and (length(w)>4) and (w>'-32768') then {если первый знак числа, знак минуса, а число по длине меньше или равно четырем знакам или число больше чем четыре знака и в ходе сравнения строка со значением введенного числа, меньше или равна строке по значению с максимальным пределом типа Integer, то идем дальше. Иначе, выводим сообщение о превышении максимального значения типа Integer} begin Write(rus('Вы ввели не число или число превышающее диапазон ')); WriteLn(rus('типа Integer (-32768..32767) ')); WriteLn(''); WriteLn(rus('Введите другое число')); Proverka(w); {выполняем рекурсивный вход в процедуру} end; if (length(w)>4) and (w>'32767') then {если число по длине меньше или равно четырем знакам или число больше чем четыре знака и в ходе сравнения строка со значением введенного числа, меньше или равна строке по значению с максимальным пределом типа Integer, то идем дальше. Иначе выводим сообщение о превышении максимального значения типа Integer} begin Write(rus('Вы ввели не число или число превышающее диапазон '));
Страницы: 1, 2, 3
| 
