Нульсвязные списки - раздел Информатика, Информатика Лабораторный практикум По программированию На Турбо-Паскале К Таким Спискам Относятся Стек, Очередь И ...
К таким спискам относятся стек, очередь и дек. В отличие от прочих типов списков, по которым можно перемещаться, используя находящиеся в звеньях указатели, в нульсвязных списках доступны только элементы на одном или обоих концах. Только после удаления из такого списка доступного элемента, можно получить доступ к следующему элементу, который теперь становится крайним в списке.
В нульсвязных списках нет заглавных звеньев. У них есть только начало и конец. Началом (или начальным звеном) называется звено, которое можно взять из списка, концом – звено, после которого можно добавить в список новый элемент (новое звено).
В языке Паскаль нет средств, позволяющих описывать переменные типа нульсвязных списков. Их приходится моделировать односвязными списками с запретом перемещения по указателям звеньев. Работа с нульсвязными списками выполняется, только используя специальные процедуры и функции. Обычно достаточно использовать функцию проверки не пуст ли список и две процедуры: добавления элемента к списку и выбора элемента из списка (с удалением выбираемого звена).
Рассмотрим варианты нульсвязных списков.
Стек – это нульсвязный список, иногда называемый очередью, с правилом обслуживания LIFO ( Last In – First Out – последним пришел – первым ушел). У стека начало и конец – это одно и то же звено, обычно называемое вершиной стека.
Создание пустого стека – это, по сути, создание указателя на вершину стека (N), и присвоение ему значения nil. Этот указатель в дальнейшем играет роль адреса начала и конца стека текущего звена.
Для добавления элемента данных в стек необходимо составить процедуру, получающую в качестве параметров указатель на вершину стека N и собственно данные Dt. Процедура должна создать динамическую переменную типа звена стека, в поле указателя перенести значение из указателя вершины стека, в поле данных записать значения Dt и в указатель на вершину стека записать адрес созданной динамической переменной. Процедура должна вернуть эту новую вершину стека.
Процедура выбора из стека последнего введенного звена выполняется наоборот: в переменную для выбираемых данных переносятся значения поля
Dt, новое значение указателя на вершину стека берется из поля ссылки на следующее звено, а старая вершина стека удаляется процедурой
Dispose. В обоих процедурах используется рабочий указатель на звено стека. Описатели типов для стека полностью совпадают с описателями односвязного списка.
Очередь – нульсвязный список с правилом обслуживания FIFO ( First In – First Out – первым пришел – первым ушел).
Для работы с очередью необходимы такие же процедуры, как и для стека. При создании пустой очереди указателям N и K присваивается значение nil. Процедурам добавления в очередь и выбора из очереди приходится передавать указатели на оба конца, так как при создании первого звена, его адрес необходимо занести в оба указателя, а при удалении последнего звена очереди, обоим указателям надо присвоить значение nil.
Дек – это нульсвязный список, в котором добавление и выбор элементов возможен с любого конца. Его можно рассматривать как двусторонний стек или двустороннюю очередь. Название (deque) расшифровывается как double-ended queue – очередь с двумя концами.
Проще всего дек моделировать двусвязным линейным списком, по которому запрещено перемещаться. Формально для него приходится составлять две процедуры добавления и две процедуры удаления элементов, находящихся на первом и втором концах дека. На практике процедуры добавления можно объединить в одну, используя дополнительный признак – к какому концу добавляется элемент. Хотя оба конца дека равноправны, для определенности одну сторону будем называть началом, обозначая указателем
NK, а вторую –концом, с обозначением
KN.
Обе процедуры удаления элемента также можно объединить в одну. В процедуру добавления (удаления) элемента таким образом придется передавать указатели на оба конца списка, данные (или адрес, куда их поместить при удалении) и признак, в начало ли идет добавление. В зависимости от того, какая сторона будет указана в списке параметров первой, с той и будет производиться работа. Вторая сторона необходима при занесении первого или удалении последнего звена из дека. Примеры этих процедур разобраны в контрольном варианте № 31.
Примеры процедур по добавлению и удалению элементов нульсвязных списков приведены в разобранном ниже контрольном варианте.
Все темы данного раздела:
На Турбо-Паскале
Санкт-Петербург
УДК 681.3.06
Требования к программе
Программа должна содержать комментарий с указанием названия работы, номера варианта, фамилии студента и номера группы Аргументы задавать операторами присваивания значений. П
Общие пояснения
Данная работа, как и все последующие, предполагает написание программы на языке Паскаль. Поскольку это первая работа по составлению программы, ниже приводится общая структура и правила написания пр
Требования к программе
· Программа должна содержать комментарий по форме, указанной в работе № 1.
· Константа, встречающаяся в задании два или более раз, должна быть использована в программе в форме именованной
Общие пояснения
1.Алгори
Формирование таблицы идентификаторов
В задании упоминаются: двумерный массив вещественного типа, количество строк (М<=7), количество столбцов (N<=7), входной текстовый файл, номер столбца с мини
Алгоритм
Должен содержать следующие шаги:
Открытие входного и выходного файлов. Текстовый входной файл связывается с набором данных с вещественными числами 'D:LAB1DATF.TXT' и
Текст программы.
PROGRAM SortNum;
{ Программа Лабораторной работы N 5
Вариант N 31.
А.Я.Умненькая, ст. гр. Я-007 }
VAR
M,N,Jmin,i,j,i1,ki : integer;
Amin,Pr : r
Содержимое файла результатов UMNIK5.RES
Исходный массив из 7x7 элементов
-2.20 -6.93 0.20 8.97 8.09 5.38 7.82
5.43 15.33 13.60 9.32 17.38 17.70 16.26
13.13 13.78 20.59 17.91 15.16 19.02 21.66
Вопросы, изучаемые в работе
· Изучение понятия рекуррентных соотношений.
· Применение алгоритмов вычисления элементарных функций как сумм бесконечного числа слагаемых.
· Продолжение изучения организации итер
Требования к программе
Программа должна содержать комментарий с указанием названия работы, № варианта, фамилии студента и № группы. Значения, отмеченные в таблице вариантов символом "*" в програм
Общие пояснения
Для приближенных вычислений значений некоторых функций используется метод представления этих функций в виде ряда бесконечного числа слагаемых.
Если неизвестная функция разложена в ряд
Рассмотрение метода решения
Расчет суммы будем проводить по рекуррентной формуле: S=S+C, т.е. новое значение суммы S есть старое значение суммы S + очередное слагаемое
Алгоритм
Должен содержать следующие шаги:
1. Задание исходных данных в разделе констант (для A и B);
2. Ввод исходных данных (Dx и
Текст программы.
program Tabl_Of_Fx;
{
Программа Лабораторной работы N 6 Вариант N 31.
Использование рекуррентных формул в итеративных циклах.
А.Я.Умненькая, ст.
Результаты расчета
Файл UMNIK6.RES будет в этом случае содержать:
Исходные данные
Интервал X: [-0.05 0.04],
Шаг X:0.010, шагов: 9, точность: 1.0E-0006
Результаты р
Общие пояснения к использованию процедур и функций.
Процедуры и функции пользователя являются двумя видами подпрограмм, которые необходимо описать в разделе описаний основной программы (или предварительно поместить в личную библиотеку) и вызывать по
Механизм параметров
В список параметров включаются исходные данные для работы процедуры/функции (входные параметры) и, если надо, указания, куда поместить результаты работы процедуры (выходные параметры).
Сущ
Текст программы.
PROGRAM KorrMas;
{ Лабораторная работа N 7 Вариант N 31
Обработка массива
А.Я.Умненькая, ст. гр. Я-007 }
TYPE
Massiv = array[1..13,1..10
Вопросы, изучаемые в работе
Изучение строения и использование процедур, функций, раздела Graph, используемого при выводе на экран информации в графической форме. Работа с цветом. Прое
Графический режим экрана
Чтобы использовать графику в программах на Турбо-Паскале необходимо научиться планировать размещение на экране выводимой информации (т.е. разобраться в алгоритме вывода графических объектов на экра
Алгоритмы построения графиков на экране
Графический режим может использоваться как для произвольного рисования (когда с помощью графических процедур проводятся отрезки прямых линий или дуги эллипсов через выбираемые точки экрана), так и
Стандартный модуль работы с графическим экраном Graph
1) назначение модуля
Подключаются процедуры и функции по работе с экраном в графическом режиме, т.е. когда доступной становится любая точка (пиксель) экрана. Для их использования необходим
Алгоритм
1.Задание констант, стандартных значений;
2.Ввод исходных данных;
3.Печать исходных данных;
4.Расчет характеристик функций;
5.Открытие графики с проверкой правил
Текст программы
Program Graph_work;
{ Программа Лабораторной работы N 8.
Вариант N 31.
Построение графика функции.
А.Я.Умненькая, ст. гр. Я-007 }
Uses Graph,Crt,Print;
Вопросы, изучаемые в работе
Разработка программы с динамическим выделением памяти. Работа с переменными комбинированного типа - записями. Работа с переменными ссылочного типа - указателями. Пр
Требования к программе
Программа должна содержать комментарий с указанием названия работы, № варианта, фамилии студента и № группы. Все созданные в программе динамические переменные в конце должны быть уда
Общие пояснения
Переменные, которые описываются в разделе описаний (VAR), называются статическими. Память для них выделяется перед началом выполнения программы, и во время выполнения программы не
Односвязные списки
Пример организации односвязного списка приведен ниже.
Type
Z=Record {комбинированный тип для данных}
a: String; {строковое поле}
b, c: Integer; {поле целых чисел
Двусвязные списки
В двусвязных списках базовый комбинированный тип S для указателей типа P будет иметь два адресных поля: поле ls ссылки на следующую запись списка
Описание файлов с данными
В данной работе предлагается использовать два типа файлов с исходными данными. Оба файла содержат одну и ту же информацию, но хранят ее в разной форме. Файл с именем Dan.dat предст
Алгоритм
Укрупненные шаги алгоритма основной программы приведены под заголовком "содержание программы" (при оформлении отчета, алгоритмы следует включить в блок-схему программы). Рассмотрим строен
Текст программы
Program Lab_9;
{ Программа Лабораторной работы N 9
Динамические переменные. Списки.
Вариант N 31.
А.Я.Умненькая, ст. гр. Я-007}
TYPE data = record {опис
Главное меню
При входе в интегрированную среду системы программирования Турбо-Паскаль (для этого достаточно вызвать модуль turbo.exe), сразу становится доступным главное меню, которое расположено в самой верхне
Команды опции File.
Open: выбор и открытие файла с исходным текстом для редактирования.
После активизации опции Open на экране появляется диалоговое окно, в котором находится список файлов те
Команды опции Edit.
Команды этого режима предназначены для различных операций с редактируемыми текстами – выделение фрагментов текста, удаления, копирования и перемещения их в любое нужное место. Выделение фрагментов
Команды опции Search.
Команды этого режима предназначены для поиска любой последовательности символов в редактируемых текстах.
Find – (поиск) – при выборе этой опции на экране появляется диалог
Команды опции Run.
Команды опции Run позволяют проводить компиляцию, компоновку и выполнение программы, а также осуществлять прогоны программы в различных отладочных режимах.
Run – ко
Команды опции Compile.
Выполняют компиляцию и компоновку Вашей программы, сформируют загрузочные файлы, а в случае необходимости сохраняют их на диске.
Compile –компиляция программы или модуля,
Команды опции Debug.
В режиме Debug можно пользоваться большими возможностями отладчика, встроенного в среду программирования Турбо-Паскаль 6.0. К ним в первую очередь относятся средства работы с окнами наблюден
Команды опции Options.
Меню Options предназначено для управления режимами компиляции и компоновки программ, написанных на Турбо-Паскале, для определения параметров интегрированной среды и, в частности, встроенного
Команды опции Window.
Это команды управления окнами. В системе программирования Турбо-Паскаль 6.0 могут быть открыты окна редактирования, наблюдений, вывода, помощи и браузера. Каждое из них может быть развернуто
Команды опции Help.
Служат для получения справочной информации по любым аспектам языка Турбо-Паскаль и его интегрированной среды. Эта информация, хранящаяся в файле TURBO.HLP, открывается в специальном окне, которое н
Меню окна редактирования
В состав этого меню входят четыре опции меню Edit – Cut, Copy, Paste и Clear; опция меню Help –Topic search; опция меню Run
Меню окна наблюдений
В состав этого меню входят шесть опций: Add, Modify, Remove, Clear all, Enable и Disable.
Add служит для добавления выражения в окно наблюдений. Любое выражение, пр
Основные команды встроенного редактора текста
Таблица 35. Список горячих клавиш
Горячая клавиша
Функция
Опция меню
F1
Открытие окна с подсказками
Сообщения об ошибках на шаге выполнения
Сообщения об ошибках на шаге выполнения имеют следующий формат:
Run-time error < номер > at < сегмент >:< смещенне >,
где < номер > – номе
Новости и инфо для студентов