Методические указания по информатике
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Обработка структур данных. Методические указания к выполнению лабораторных работ по дисциплине «Системное программирование»

Цель методических указаний – оказание помощи студентам в выполнении лабораторных работ по дисциплине. Методические указания содержат краткое изложение основных теоретических положений, примеры обработки рассматриваемых структур данных, задания на лабораторные работы, порядок их выполнения и требования к отчетам, а также список рекомендованной литературы.

Содержание

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 элементов структуры.

Преобразование линейного списка удаление элемента 2 a)

Преобразование линейного списка включение элемента 1'. б)

Рисунок 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

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство

Агрономия

Преподавателям

Юридические темы

Google