МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ
РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
Кафедра «Математическое обеспечение вычислительных систем»
ОТЧЕТ
по лабораторному практикуму
по дисциплине «Структуры и алгоритмы обработки данных»
(часть 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 = setof '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 = setof '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; //запоминаем адрес первого элемента ЛОС
ifq= Nilthen {проверяем ЛОС на пустоту и если он пустой
выводим сообщение о том, что ЛОС пустой
и выводим варианты дальнейшей работы
программы}
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 {проверяем, с каким типом данных происходит
работа программы}
Ifst = 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
Whileq<>Nildo {проходим по всему ЛОС пока не дойдем до
указателя конца списка (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;
fori:= 1 tolength(w) do {запускаем цикл проверки числа на корректность ввода, число введено, как строка. По этому мы можем поэлементно проверить каждую цифру}
begin
b:= ['0','1','2','3','4','5','6','7','8','9']; //множество состоящее из цифр
c:=w[i]; {берем каждую цифру из числа проходя от первой до последней}
if (cinb) or (c='-') and (i=1) then {сравниваем есть ли цифра из введенного числа во множестве заданных цифр и проверяем какое число было введено, отрицательное или положительное и не стоит ли знак минус в середине числа}
else
a:= 1; {если число не корректно делаем пометку для дальнейшей проверки}
end;
ifa = 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}