| ЛАБОРАТОРНАЯ РАБОТА #5 ТЕМА: Списки в оперативной памяти, операции над списками
1. Цель работы Приобретение и закрепление навыков в работе со списками 2. Прорабатываемые темы Динамические линейные структуры 3. Постановка задачи Для объектов, описание и функции которых были разработаны в Лабораторной работе N4, разработать программу, обеспечивающую ввод исходных данных из файла данных (файл Лабораторной работы N4) в память, хранение их в памяти в виде неупорядоченного линейного 2-направленного списка, операции над этим списком. 4. Варианты индивидуальных заданий Для каждой области перечислены параметры объекта. Среди параметров обязательно есть ключевое алфавитное поле (например, фамилия), которое идентифицирует объект, у каждого объекта имеется также одно или несколько числовых полей, по которым вероятны обращения к объекту. Набор характеристик может быть расширен и усложнен по усмотрению исполнителя. Nпп Прикладная область Атрибуты информации
1 Отдел кадров фамилия сотрудника, имя, отчество, должность, стаж работы, оклад 2 Красная книга вид животного, род, семейство, место обитания, численность популяции 3 Производство обозначение изделия, группа к которой оно относится, год выпуска, объем выпуска, расход металла 4 Персональные ЭВМ фирма-изготовитель, тип процессора, тактовая частота, емкость ОЗУ, емкость жесткого диска 5 Библиотека автор книги, название, год издания, код УДК, цена, количество в библиотеке 6 Спутники планет название, название планеты-хозяина, год открытия, диаметр, период обращения 7 Радиодетали обозначение, тип, номинал, количество на схеме, обозначение возможного заменителя 8 Текстовые редакторы наименование, фирма-изготовитель, количество окон, количество шрифтов, стоимость 9 Телефонная станция номер абонента, фамилия, адрес, наличие блокиратора, задолженность 10 Быт студентов фамилия студента, имя, отчество, факультет, размер стипендии, число членов семьи 11 Спортивные соревнования фамилия спортсмена, имя, команда, вид спорта, зачетный результат, штрафные очки 12 Соревнование факультетов по успеваемости факультет,количество студентов, средний балл по факультету, число отличников, число двоечников 13 С/х работы фамилия студента, имя, отчество, факультет, вид работ, заработок 14 Сельхозработы наименование с/х предприятия, вид собственности, число работающих, основной вид продукции, прибыль 15 Сведения о семье фамилия студента, имя, отчество, факультет, специальность отца, специальность матери, количество братьев и сестер 16 Скотоводство вид животных, количество особей в стаде в возрасте до 1 года, количество особей 1 - 3 лет, свыше 3 лет, смертность в каждой группе, рождаемость 17 Микросхемы памяти обозначение, разрядность, емкость, время доступа, количество на схеме, стоимость 18 Описание изображения тип фигуры (квадрат, окружность и т.п.), координаты на плоскости, числовые характеристики (длина строрны, радиус и т.п.). 19 Лесное хозяйство наименование зеленого массива, площадь, основная порода, средний возраст, плотность деревьев на кв.км 20 Городской транспорт вид транспорта, номер маршрута, начальная остановка, конечная остановка, время в пути 5. Пример решения задачи
5.1 Индивидуальное задание Область: деканат. Атрибуты информации: фамилия студента; имя; отчество; год рождения; обозначение группы; средний балл в сессию. 5.2.1. Выбор метода. 1). Представление данных. Заданная структура классификаторов объекта описана в виде записи stud в файле LAB5UNIT.PAS. Для возможности увязки объектов в списке вводим тип данных lstud - в которой помимо записи stud имеются поля ссылок. lstud = record std : stud; next : studptr; prev : studptr; end; Тип данных studptr - указатель на запись lstud. 2). Модульная структура программы Описание расширенного типа данных lstud включаются в модуль LAB5UNIT.PAS. Сюда же включаются программные единицы, реализующие те же операции над элементами усложненной структуры и специфические списковые операции. Для операций с типом данных stud используйте модуль LAB4UNIT.PAS из ЛАБОРАТОРНОЙ РАБОТЫ №4 3). Инкапсуляция Внешняя программа (программа пользователя) использует тип данных lstud, при этом она не имеет прямого доступа к внутренней структуре объекта этого типа. Все операции с данными этого типа, в том числе и операции над компонентами внутренней структуры программа выполняет через посредство процедур/функций, содержащихся в модуле. 4). Состав базовых функций Для работы с типом данных lstud принимается следующий набор операций: • выделение памяти под объект типа lstud; • ввод значения объекта из текстового файла; • ввод значения объекта с консоли; • вывод значения объекта в текстовый файл; • вывод значения объекта на консоль; • сравнение объектов по фамилиям; • сравнение объектов по оценкам. Специфические списковые операции следующие: • выбор 1-го элемента списка; • удаление из списка 1-го элемента; • выбор 1-го элемента списка и удаление его из списка; • добавление элемента в начало списка; • добавление элемента в конец списка; 5.2.2. Структура программы Исходный текст программы состоит из двух модулей: модуль LAB5UNIT.PAS и модуль LAB5.PAS. Модуль LAB5UNIT.PAS имеет заголовок Unit Lab5Unit. Этот модуль в секции INTERFACE содержит описание типа данных stud и функций, реализующих операции над этим типом данных: • ListNew - выделение памяти; • ReadTLStud - ввод значения объекта из текстового файла; • ReadLStud - ввод значения объекта с консоли; • WriteTLStud - вывод значения объекта в текстовый файл; • WriteLStud - вывод значения объекта на консоль; • CompLName - сравнение объектов по фамилиям; • CompLMark - сравнение объектов по оценкам; а также функций, реализующих списковые операции: • Car - выборка головного элемента из списка; • Cdr - остаток списка; • Cadr - комбинация Car и Cdr; • Cons - присоединение эл-та к списку (в начало); • ListAppend - добавление элемента в конец списка. Модуль LAB5.PAS иимеет заголовок Program Lab54, оператором Uses к нему подключатся Unit Lab4Unit, Lab5Unit. Результатом его компиляции явится файл LAB5.EXE. В модуле помимо основной программы имееются процедуры (функции): • Include - включение в список нового элемента; • DisplList - отображение списка; • CondComp - сравнение элементов; • Find - поиск в списке; • Delete - удаление элемента; • Rev - реверс списка; • Sort - сортировка списка по алфавиту; • Xchange - однократные перестановки в списке.
5.2.3. Описание программы. 5.2.4.1. Модуль LAB5UNIT Функция ListNew предназначена для выделения памяти под переменную типа lstud. Function ListNew(f : integer) : studptr; Параметр f задает действия при нехватке памяти: аварийное завершение (f=0) или возврат значения NIL (f=1). В функции определяется (MaxAvail) размер свободной памяти и, если он меньше необходимого, выполняются действия в зависимости от значения f. При достаточном объеме памяти запрашивается память (New) и функция возвращает адрес выделенного блока. Функции ReadTLStud и ReadLStud предназначены для ввода значения одного объекта из текстового файла и с консоли соответственно. Function ReadTLStud (var tf : tfile) : studptr; Function ReadStud : studptr; tf - файл, из которого производится ввод (файл д.б.открыт). Функции возвращают введенное значение. Обе функции вызывают функцию выделения памяти ListNew,а затем в поле std новой записи типа lstud записывают значеение при помощи процедуры ReadTStud или ReadStud. Процедуры WriteTLStud и WriteLStud предназначены для вывода значения одного объекта в текстовый файл или на терминал соответственно. Procedure WriteTStud(a : studptr; var tf : tfile); Procedure WriteTStud(a : studptr); a - переменная, значение которой выводится; tf - файл, в который производится вывод (файл д.б. открыт). Процедуры вызывают процедуры WriteTStud и WriteStud соответственно, передавая им значение поля std. Функции CompLName и CompLMark предназначены для сравнение объектов по полю фамилии и оценки соответственно. Function CompLName(a, b : studptr) : integer; Function CompLMark(a, b : studptr) : integer; a и b - сравниваемые переменные. Функция Car предназначена для выборки первого элемена из списка: Function Car(list:studptr) : studptr; list - указатель на голову списка, функция возвращает указатель на первый элемент, определяемый простым присваиванием. Функция Cdr предназначена для удаления первого элемента из списка: Function Cdr(list:studptr) : studptr; Если список, на голову которого указывает list пустой, функция возвращает NIL, в противном случае - возвращает значение поля next первого элемента списка, т.е. адрес второго элемента. Функция Cadr предназначена для выборки и удаления первого элемента из списка: Function Cadr(Var list : studptr) : studptr; Возвращаемое значение всегда совпадает с указателем на голову списка (если список пустой, то и оно NIL). Если список непустой, то указатель на его голову (описанный как var в параметрах функции) сдвигается на следующий элемент списка. Функция Cons предназначена для добавления элемента в начало списка: Function Cons(list,atom : studptr) : studptr; Если указатель на добавляемый элемент atom пустой, то добавления не происходит, функция возвращает указатель на голову списка. В противном случае адрес головы списка заносится в поле next добавляемого элемента, и функция возвращает адрес добавленного элемента, который теперь стал головой списка. Функция ListAppend предназначена для добавления элемента в конец списка: Function ListAppend(list,atom : studptr) : studptr; По ветви else имеется рекурсивный вызов, но при этом вызове функции ListAppend передается список, усечнный на первый элемент. При выполнении цепочки рекурсивных вызовов управление будет передаваться на ветвь else до тех пор, пока список не опустеет. Тогда в пустой список по ветви then запишется элемент atom и начнется цепочка возвратов. При каждом возврате из рекурсии в начало списка, вернувшегося с более низкого уровня рекурсии, добавляется тот элемент, который является первым в списке list на текущем уровне. 5.2.3.2. Модуль LAB5.PAS Переменные общие для всех программных единиц модуля: • a - указатель на запись studptr, в которой формируется значение искомого ключа; • next_ptr - указатель на элемент списка, с которого продолжается поиск; • ffind - целое число; при поиске используется как признак типа ключа (1 - алфавитный / 2 - числовой ключ); при сортировке используется как признак перестановки. Основная программа. В ходе начальных установок формируется пустой указатель h на начало списка, пустое значение next_ptr, нулевое значение ffind, выделяется память под эталонную запись a (функция ListNew) и запоминается в переменной heap адрес начала кучи (функция Mark) - для освобождения памяти при завершении Затем открывается файл LAB4.TDT и в цикле до конца файла из него считываются исходные данные (функция ReadTLStud). Каждая считанная запись заносится в список (функция Include). После ввода файл LAB4.TDT закрывается, и открывается файл LAB5.TDT, из которого будет производиться дополнительный ввод. Переменная opt - код операции над списком получает начальное значение 1, далее программа входит в цикл, который продолжается до тех пор, пока opt не получит значение -1. В каждой итерации этого цикла происходит обращение к функции LIST_opt, которая позволяет выбрать выполняемую операцию и возвращает код операции, присваиваемый переменной opt. Далее программа разветвляется в зависимости от значения opt: При значении opt 1 (операция отображения списка) вызывается функция DisplList. При значении opt 2 (операция добавления нового элемента в список анализируется наличие информации в файле ft (дисковый файл LAB8.TDT), и если файл не исчерпан происходит чтение из него записи (функция ReadTLStud) и включение ее в список (функция Include). Если же файл исчерпан, на терминал выдается сообщение. При значении opt 3 (операция удаления записи по алфавитному ключу устанавливается признак алфавитного ключа ffind=1, вводится (функция LIST_abckey) и записывается в эталонную запись a поле фамилии записи stud, и вызывается функция Delete. Указатель на голову списка h корректируется по результату функции Delete. При значении opt 4 (операция удаления записи по числовому ключу устанавливается признак числового ключа ffind=2, вводится (функция LIST_intkey) и записывается в эталонную запись a поле среднего балла записи stud, и вызывается функция Delete. Указатель на голову списка h корректируется по результату функции Delete. При значении opt 5 (операция поиска по алфавитному ключу)устанавливается признак алфавитного ключа ffind=1, вводится (функция LIST_abckey) и записывается в эталонную запись a поле фамилии записи stud, и вызывается функция Find, причем параметром ей передается адрес начала списка h. Результат, возвращаемый функцией Find, не используется. При значении opt 6 (операция поиска по числовому ключу)устанавливается признак числового ключа ffind=1, вводится (функция LIST_intkey) и записывается в эталонную запись a поле среднего балла записи stud, и вызывается функция Find с параметром - адресом начала списка h. Результат, возвращаемый функцией Find, не используется. При значении opt 7 (операция поиска следующего) проверяется значение признака ffind. Если оно не установлено, то выдается звуковой сигнал, в противном случае вызывается функция Find, но с параметром next_ptr - адресом, установленном при предыдущем поиске. При значении opt 8 (операция реверс списка) вызывается функция Rev, и указатель на голову устанавливается в ее возвращаемое значение. При значении opt 9 (операция сортировки списка по алфавиту) вызывается функция Sort, и указатель на голову устанавливается в ее возвращаемое значение. При значении opt -1 (конец работы), ничего не делается, это значение opt обрабатывается в заголовке цикла. При любом другом значении opt выдается звуковой сигнал. После выхода из цикла производится общее освобождение динамически распределявшейся памяти. Функция Include предназначена для включения в список нового элемента: Function Include(list, item : studptr) : studptr; где list - указатель на голову списка, item - указатель на элемент. Выполнение этой функции сводится к вызову функции ListAppend. Процедура DisplList предназначена для отображения списка на экране терминала: Procrdure DisplList(list : studptr); где list - указатель на голову списка. Функция в цикле перебирает элементы списка, пока не встретит пустую ссылку. Каждый выбранный элемент выводится на экран процедурой WriteLStud. Функция CompCond выполняет сравнение объектов типа studptr по алфавитному или числовому ключу: Function CondComp(a,b : studptr) : integer; где a и b - сравниваемые объекты. В зависимости от значения признака ffind функция вызывает либо CompLName, либо CompLMark и возвращает из результат. Функция Find предназначена для поиска в списке по заданному ключу: Function Find(list : studptr) : studptr; где list - указатель на элемент, с которого должен начинаться поиск. Перед вызовом в переменную ffind должен быть занесен код типа ключа, а в запись a - значение ключа, которое следует искать. Функция перебирает список до те пор, пока не обнаружит признак конца. Каждый выбранный элемент сравнивается (функция CondComp) с эталонным элементом a. При удовлетворительном результате сравнения элемент выводится на экран, указатель next_ptr (для следующего поиска) устанавливается на следующий элемент списка и происходит досрочный выход из цикла с установкой возвращаемого значения в указатель на найденный элемент. При достижении конца списка выдается сообщение "Не найден", возвращаемое значение и next_ptr устанавливаются в NIL, а признак ffind сбрасывается в 0. Функция Delete предназначена для удаления из списка элемента, заданного по ключу: Function Delete(list : studptr) : studptr; где list - указатель на голову списка. Перед вызовом в переменную ffind должен быть занесен код типа ключа, а в запись a - значение ключа, которое следует искать. Функция перебирает список до те пор, пока не обнаружит признак конца или элемент с совпадающим ключем. Каждый выбранный элемент переносится в список l, который в исходном состоянии пуст (порядок следования элементов в списке l обратный). Указатель p получает значение адреса того элемента, на котором закончился поиск. Если это значение не пустое (пустое значение мы получим при достижении конца списка), то из остатка списка list удаляется первый (найденный) элемент, и освобождается занимаемая им память. При пустом значении p не делается ничего. Далее элементы, сохраненные в списке l, возвращаются в список list. Признак ffind сбрасывается в 0, а возвращаемое значение устанавливается в адрес начала списка list. Функция XChange производит просмотр списка и сравнение соседних элементов в нем. Если предыдущий элемент больше текующего, они меняются местами. Function XChange(list, a : studptr) : studptr; где list - начало списка, a - предыдущий элемент. Функция реализована с использованием рекурсии. При каждом вызове выделяется текущий элемент b. Если этот элемент NIL (конец списка), функция заносит предыдущий элемент a в пустой список и возвращает адрес этого списка. В противном случае производится сравнение предыдущего и текущего элементов. При любом результате сравнения происходит рекурсивный вызов, которому передается усеченный список list, а затем в начало списка, возвращенного рекурсивным вызовом, заносится элемент. Но если текущий элемент больше предыдущего рекурсивному вызову передается для следующего сравнения текущий элемент b, а к началу возвращаемого списка добавляется предыдущий элемент a. В противном случае предыдущий элемент передается рекурсии, а текущий добавляется в возвращаемый список, и при этом взводится признак перестановки ffind. Функция Sort предназначена для сортировка списка по алфавиту: Function Sort(list : studptr) : studptr; list - начало сортируемого списка. Тело функции состоит изцикла. В начале каждой итерации этого цикла устанавливается в 0 признак ffind, выбирается первый элемент списка, а затем происходит обращение к XChange для просмотра списка с перестановками. Если после XChange признак ffind сохранит нулевое значение, цикл прерывается, и функция Sort возвращает адрес начала отсортированного списка. Функция Rev производит изменение порядка следования элементов списка на противоположный: Function Rev(list : studptr) : studptr; В начальных установках указатель на начало второго списка l получает пустое значение. Далее в цикле выбираются элементы списка list и добавляются в начало списка l. По исчерпании списка list функция возвращает адрес начала списка l. 5.3. Исходные данные контрольного примера Для основного ввода используется файл LAB4.TDT, содержащий те же данные, что и для Лабораторной работы N4. Данные для дополнительного ввода находятся в файле LAB5.TDT, формат его содержимого такой же, как и для первого файла. 5.4. Текст программы {******************** Файл LAB5UNIT.PAS ******************} { Списковые операции над структурой данных "студент" } Unit Lab5Unit; INTERFACE uses Lab4Unit; Type studptr = ^lstud; lstud = record std : stud; next : studptr; prev : studptr; end; { Выделение памяти под новый эл-т списка } Function ListNew(f : integer) : studptr; { Выборка головного элемента из списка } Function Car(a : studptr) : studptr; { Остаток списка } Function Cdr(a : studptr) : studptr; { Комбинация Car и Cdr } Function Cadr(var a: studptr) : studptr; { Присоединение эл-та к списку (в начало) } Function Cons(a, b : studptr) : studptr; { Добавление элемента в конец списка } Function ListAppend(list, atom : studptr) : studptr; { Вывод значения эл-та списка на консоль } Procedure WriteLStud(a : studptr); { Ввод значения эл-та списка из текстового файла } Function ReadTLStud (var tf : tfile) : studptr; { Ввод значения эл-та списка с консоли } Function ReadLStud : studptr; { Вывод значения эл-та списка в текстовый файл } Procedure WriteTLStud(a : studptr; var tf : tfile); { Сравнение эл-тов по фамилиям } Function CompLName(a, b : studptr) : integer; { Сравнение эл-тов по оценкам } Function CompLMark(a, b : studptr) : integer; IMPLEMENTATION {==== Выделение памяти под новый эл-т списка ====} Function ListNew(f : integer) : studptr; Var a : studptr; begin if MaxAvailNIL then Cdr:=a^.next else Cdr:=a; end; {==== Комбинация Car и Cdr ====} { a - на входе - ук.на голову списка, на выходе - ук. на остаток; возврат - ук.на выбранный эл-т } Function Cadr(var a: studptr) : studptr; begin Cadr:=Car(a); a:=Cdr(a); end; {==== Присоединение эл-та к списку (в начало) ====} { a - ук.на голову списка; b - ук.на присоединяемый эл-т возврат - ук.на голову } Function Cons(a, b : studptr) : studptr; Var p : studptr; begin b^.next:=a; if a<> NIL then a^.prev:=b; Cons:=b; end; {==== Добавление элемента в конец списка ====} { a - ук.на голову списка; b - ук.на присоединяемый эл-т возврат - ук.на голову } Function ListAppend(list, atom : studptr) : studptr; begin if atom=NIL then ListAppend:=list else if CAR(list)=NIL then ListAppend:=Cons(list,atom) else ListAppend:=Cons(ListAppend(Cdr(list),atom),Car(list)); end; END. {********************** Файл LAB5.PAS ********************} Program LAB5; uses Lab4Unit, Lab5Unit; Var { общие переменные } a : studptr; { эталон для поиска } next_ptr : studptr; { нач.адрес поиска } ffind : integer; { поиск по алф/числ (1/2) } {=== Включение в список нового элемента ===} Function Include(list, item : studptr) : studptr; begin Include := ListAppend(list,item); end; {==== Отображение списка ========} Procedure DisplList(list : studptr); begin while Car(list)<>NIL do WriteLStud(Cadr(list)); readln; end; {===== Сравнение элементов в зависимости от ffind ======} Function CondComp(a,b : studptr) : integer; begin if ffind=1 then CondComp:=CompLName(a,b) else CondComp:=CompLMark(a,b); end; {====== Поиск в списке ============} Function Find(list : studptr) : studptr; Label L0; begin while Car(list)<>NIL do begin if CondComp(a,Car(list))=0 then begin WriteLStud(Car(list)); ReadLn; Find:=Cadr(list); next_ptr:=Car(list); goto L0; end else list:=Cdr(list); end; WriteLn('Не найден'); ReadLn; Find:=NIL; next_ptr:=NIL; ffind:=0; L0:end; {===== Удаление элемента =====} Function Delete(list : studptr) : studptr; Var l, p : studptr; begin l:=NIL; while ((Car(list)<>NIL)and(CondComp(a,Car(list))<>0)) do l:=Cons(l,Cadr(list)); p:=Car(list); if p<>NIL then begin list:=Cdr(list);Dispose(p); end; while Car(l)<>NIL do list:=Cons(list,Cadr(l)); ffind:=0; Delete:=list; end; {===== Один прогон перестановок в списке ======} Function XChange(list, a : studptr) : studptr; Var b:studptr; begin b:=Cadr(list); if b=NIL then XChange:=Cons(list,a) else begin if CompLName(a,b)>0 then begin XChange:=Cons(XChange(list,a),b); ffind:=1; end else XChange:=Cons(XChange(list,b),a); end; end; {======= Сортировка по возрастанию ===========} Function Sort(list : studptr) : studptr; Var a : studptr; begin repeat ffind:=0; a:=Cadr(list); list:=XChange(list,a); until ffind=0; Sort:=list; end; {===== Реверс списка =====} Function Rev(list : studptr) : studptr; Var l : studptr; begin l:=NIL; while list<>NIL do l:=Cons(l,Cadr(list)); Rev:=l; end; {============= Основная программа ============} Var ft : text; { Файл исходных данных } h : studptr; { Голова списка } bh : studptr; { Ук.на эл-т списка } opt : integer; { Номер выполняемой операции } heap : pointer; begin { Начальные установки } h:=NIL; next_ptr:=NIL; Mark(heap); a:=ListNew(0); ffind:=0; { Ввод основных данных из файла LAB4.TDT } assign(ft,'lab4.tdt'); reset(ft); while not Eof(ft) do begin bh:=ReadTLStud(ft); h:=Include(h,bh); end; close(ft); { Открытие файла дополнительного ввода } assign(ft,'lab5.tdt'); reset(ft); opt:=1; { Выполнение операций в интерактивном режиме } while opt>0 do begin { Выбор операции } opt:=LIST_opt(opt); case opt of 1 : { Отображение списка } DisplList(h); 2 : { Добавление элемента } begin if not Eof(ft) then begin bh:=ReadTLStud(ft); h:=Include(h,bh); end else begin WriteLn('Нет дополнительных данных'); ReadLn; end; end; 3 : { Удаление (алф.ключ) } begin ffind:=1; a^.std.family:=LIST_abckey; h:=Delete(h); end; 4 : { Удаление (числ.ключ) } begin ffind:=2; a^.std.Mark:=LIST_realkey; h:=Delete(h); end; 5 : { Поиск по алф.ключу } begin ffind:=1; a^.std.family:=LIST_abckey; bh:=Find(h); end; 6 : { Поиск по числ.ключу } begin ffind:=2; a^.std.Mark:=LIST_realkey; bh:=Find(h); end; 7 : { Поиск следующего } if ffind=0 then Beep else bh:=Find(next_ptr); 8 : { Спец функция 1 - реверс } h:=Rev(h); 9 : { Спец функция 2 - сортировка } h:=Sort(h); -1 : { Конец } ; else Beep; { Звуковой сигнал } end; end; Release(heap); { Освобождение памяти } end. ПРИМЕЧАНИЕ Для сокращения текста примера в тексте программы опущены следующие процедуры/функции: Function LIST_opt(opt : integer) : integer; - функция выводит на экран терминала меню возможных операций со списком и возвращает номер выбранной пользователем операции. Function LIST_abckey : string; - ввод алфавитного ключа. Function LIST_intkey : integer; - ввод числового ключа. Function LIST_realkey : real; - ввод числового ключа. Procedure Beep; - выдача звукового сигнала.
|
