Обработка структур данных. Методические указания к выполнению лабораторных работ по дисциплине «Системное программирование»
Цель методических указаний – оказание помощи студентам в выполнении лабораторных работ по дисциплине. Методические указания содержат краткое изложение основных теоретических положений, примеры обработки рассматриваемых структур данных, задания на лабораторные работы, порядок их выполнения и требования к отчетам, а также список рекомендованной литературы.
Содержание
1. Общие положения, порядок выполнения лабораторных работ и требования к отчетам
2. Классификация структур данных
3. ЛАБОРАТОРНАЯ РАБОТА №1. Формирование и обработка линейных списковых структур данных
4. ЛАБОРАТОРНАЯ РАБОТА № 2. Формирование и обработка табличных структур данных
5. ЛАБОРАТОРНАЯ РАБОТА № 3. Формирование и обработка древовидных структур данных
Библиографический список
Приложение А. Пример программы обработки двунаправленного списка на языке С++.
3. ЛАБОРАТОРНАЯ РАБОТА №1. Формирование и обработка линейных списковых структур данных
Цель работы: изучение принципов организации и программирование основных операций, выполняемых с линейными списковыми структурами.
3.1. Линейные структуры данных. Основные теоретические положения
Линейные структуры, в соответствии с [1,2], - это множество, состоящее из n≥0 записей X1, X2, ... , Xn, структурные свойства которого определяются одномерным относительным положением записей: X1 является первой записью; если 1 < k < n, то k-ой записи Xk предшествует (k-1)-ая Xk-1, а за ней следует (k+1)-ая Xk+1; Xn является последней записью.
Одной из самых распространенных линейных статических структур является одномерный массив. Для хранения массива в памяти, как правило, используется ее последовательное распределение, подразумевающее размещение элементов массива в последовательных ячейках памяти. Местоположение массива в памяти определяется адресом его первого элемента.
Для хранения динамической линейной структуры используется более гибкая схема, называемая связанным распределением. Каждая запись динамической линейной структуры, называемой списком, содержит указатель на следующую запись. Такой список называется однонаправленным (односвязным). Указатель последней записи равен коду признака конца списка, а указатель на первую запись задается дополнительным параметром, называемым переменной связи. Если в каждый элемент списка добавить еще один указатель – на предыдущий элемент, то получится двунаправленный список (двусвязный). Тип списка принципиально не влияет на реализацию операций, поэтому далее ограничимся рассмотрением односвязных списков, а в Приложении А приведем пример программы обработки двунаправленного списка.
Пусть каждый элемент списка содержит два поля: INFO, содержащее значение элемента данных Xk, и LINK, содержащее адрес следующего элемента Xk+1. Переменную связи назовем FIRST. Введенные обозначения будем использовать в программных иллюстрациях операций над списками.
Связанное распределение требует дополнительное пространство в памяти для связей. Но при его использовании существенно упрощаются такие операции над линейной структурой, как удаление ее элемента и включение в нее нового элемента, которые сводятся, как показано на рисунке1, к изменению соответствующих полей LINK элементов структуры.
a)
б)
Рисунок 1 - Преобразование линейного списка
a) удаление элемента 2;
б) включение элемента 1'.
Особенно полезны списковые структуры в тех случаях, когда в памяти ЭВМ требуется разместить несколько динамически изменяющихся структур данных (массивов, строк, таблиц и т. д.) с заранее неизвестным числом элементов. Кроме того, использование списков целесообразно, когда требуется упорядочить элементы данных без их физического перемещения или связать воедино элементы данных, размещенные в разных местах памяти [1-4].
Для описания динамических структур данных удобным средством многих языков программирования являются переменные - указатели.
Приведем примеры реализации прохода списковой структуры, включения в нее нового элемента и удаления из нее элемента средствами языка Паскаль. При этом будем полагать, что список задается переменной связи FIRST и описание списковой структуры имеет вид:
type
NLINK=^LIST;
LIST=record
INFO:integer;
LINK:NLINK
end;
var FIRST:NLINK;
Процедура прохода списка LISTPRINT выполняет вывод всех его элементов, начиная с элемента, указанного FIRST, и заканчивая элементом, содержащим nil в поле LINK.
procedure LISTPRINT(FIRST:NLINK);
var
BASE:NLINK;
begin
BASE:=FIRST;
while BASE<>nil do
begin
writeln(BASE^.INFO);
BASE:=BASE^.LINK
end; end;
Процедура включения элемента LISTADD добавляет в список новый элемент после элемента с заданным номером K, если в списке не менее K элементов. В противном случае элемент добавляется к списку в качестве последнего. Поле данных нового элемента при этом заполняется значением, заданным переменной NEWINFO.
procedure LISTADD(K, NEWINFO:integer; var FIRST:NLINK);
var
I:integer;
NEWNODE, BASE:NLINK;
begin
new(NEWNODE);
NEWNODE^.INFO:=NEWINFO;
if FIRST<>nil then
begin
BASE:=FIRST;
for I:=1 to K-1 do
if BASE^.LINK<>nil then BASE:=BASE^.LINK;
NEWNODE^.LINK:=BASE^.LINK;
BASE^.LINK:=NEWNODE;
end
else begin FIRST:=NEWNODE; NEWNODE^.LINK:=nil;
end; end;
Процедура удаления элемента LISTDEL удаляет из списка элемент с заданным номером K, если в списке не менее K элементов. В противном случае процедура не изменяет структуру списка.
procedure LISTDEL(K:integer; var FIRST:NLINK);
var
I:integer;
DELNODE, BASE:NLINK;
begin
if FIRST<>nil then
begin
BASE:=FIRST;
for I:=1 to K-2 do
if BASE<>nil then BASE:=BASE^.LINK;
DELNODE:=BASE^.LINK;
BASE^.LINK:=DELNODE^.LINK;
end; end;
В программировании часто встречаются линейные структуры, в которых включение и исключение или доступ к значениям производятся только в первой или последней записи. Эти структуры имеют специальные названия: стек, очередь, дек [1,2].
При работе с этими структурами будем полагать, что процедура извлечения элемента предполагает и его удаление.
СТЕК - линейная структура, в которой все включения и исключения и всякий доступ делаются в одном конце структуры.
Из стека всегда извлекается "младший" элемент из имеющихся в списке, т. е. тот, который был включен позже других. Этот элемент называют вершиной стека.
Приведенная ниже процедура включения элемента в стек STACKADD полагает стек заданным указателем TOP на его вершину, а поле данных нового элемента заполняет значением, заданным переменной NEWINFO.
procedure STACKADD(NEWINFO:integer; var TOP:NLINK);
var
NEWNODE:NLINK;
begin
new(NEWNODE);
NEWNODE^.INFO:=NEWINFO;
NEWNODE^.LINK:=TOP;
TOP:=NEWNODE;
end;
Процедура STACKSEL выбирает элемент из стека, заданного указателем TOP на его вершину, и возвращает его значение через переменную Х.
procedure STACSEL(var TOP:NLINK; var X:INTEGER);
var P:NLINK;
begin
if TOP<>nil then begin P:=TOP; X:=TOP^.INFO;
TOP:=TOP^.LINK;
dispose(P);
end; end;
ОЧЕРЕДЬ - линейная структура, в которой все включения производятся на одном конце структуры, а все исключения и доступ на другом ее конце. Очередь задается двумя указателями: на первую запись (указатель начала очереди) и на последнюю запись (указатель конца очереди). Приведем процедуру включения элемента в очередь QADD, указатель конца которой передается через параметр R, а значение поля данных нового элемента - через параметр NEWINFO.
procedure QADD(NEWINFO:integer; var R:NLINK);
var
NEWNODE:NLINK;
begin
new(NEWNODE);
NEWNODE^.INFO:=NEWINFO;
NEWNODE^.LINK:=nil;
if R<>nil then R^.LINK:=NEWNODE;
R:=NEWNODE;
end;
Процедура QSEL выбирает элемент очереди, заданной указателями L начала и R конца, и возвращает его значение через переменную Х.
procedure QSEL( var R, L:NLINK; var X:integer);
var P:NLINK;
begin
if L<>R then begin P:=L; X:=L^.INFO;
L:=L^.LINK;
dispose(P);
end; end;
ДЕК - это линейная структура, в которой включение и исключение элементов и доступ к элементам возможны на обоих концах структуры. Очевидно, что для реализации этих действий необходимо задавать, с какого конца требуется выполнить операцию.
3.2. Задание на лабораторную работу
Разработать программу формирования списка и выполнения заданной операции с ним. В программе предусмотреть вывод элементов исходного списка и, если необходимо, результирующего списка.
Коды вариантов задания приведены в таблице 3.1. Первая компонента кода варианта задания задает операцию, вторая - тип списка.
Таблица 3.1- Варианты задания
|
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
|
код |
1_1 |
2_1 |
3_1 |
4_1 |
5_1 |
6_1 |
|
№ варианта |
7 |
8 |
9 |
10 |
11 |
12 |
|
код |
7_1 |
8_1 |
9_1 |
10_1 |
11_1 |
12_1 |
|
№ варианта |
13 |
14 |
15 |
16 |
17 |
18 |
|
код |
1_2 |
2_2 |
3_2 |
4_2 |
5_2 |
6_2 |
|
№ варианта |
19 |
20 |
21 |
22 |
23 |
24 |
|
код |
7_2 |
8_2 |
9_2 |
10_2 |
11_2 |
12_2 |
Заданная операция:
1. Упорядочить элементы списка по убыванию.
2. Добавить элемент после элемента с номером k.
3. Вставить элемент перед элементом с номером k.
4. Удалить элемент с номером k.
5. Удалить элементы, информационное поле которых равно x.
6. Удалить элемент, предшествующий элементу с номером k.
7. Переставить k - ый и k +1-ый элементы списка.
8. Удалить элемент, следующий за элементом с номером k .
9. Переставить первый и k-ый элементы списка.
10. Найти сумму положительных элементов списка и записать ее последним элементом.
11. Добавить элемент после элемента, информационное поле которого равно x.
12. Заменить элемент, информационное поле которого равно x.
Тип списка:
1. – однонаправленный;
2. – двунаправленный.
3.3. Контрольные вопросы
Дать определение динамических структур данных. Какие структуры данных называются линейными? Какую структуру имеют элементы однонаправленного и двунаправленного списков? Как выполняется операция удаления элемента из списка? Как выполняется операция вставки элемента в список? Дать определение стека. Дать определение очереди.
Скачать полный текст Методички zip