Назначение процедур и функций

InitList — инициализация списка.

PutList — включение элемента в список.

GetList — исключение элемента из списка.

ReadList — чтение элемента списка.

EmptyList — проверка: свободен ли список.

EndList — проверка: является ли элемент последним.

Count — возвращает количество элементов в списке.

BeginPtr — устанановка в начало списка.

EndPtr — устанановка в конец списка.

MovePtr — переход к следующему элементу.

MoveTo — переход к n-му элементу.

DoneList — удаление списка.

CopyList — копирование списка L1 в список L2.

С о д е р ж а н и е о т ч е т а

1. Тема лабораторной работы.

2. Цель работы.

3. Характеристика СД «линейный список» (п.1 задания).

4. Индивидуальное задание.

5. Тексты модулей для реализации СД «линейный список» на языках Pascal и С, тексты программ для отладки модулей, тестовые данные результат работы программ.

6. Текст программ на языках Pascal и С для решения задачи с использованием модулей, тестовые данные, результаты работы программ.

Т е о р е т и ч е с к и е с в е д е н и я

Линейный список (ЛС) — это конечная последовательность однотипных элементов (узлов).

Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться, поэтому ЛС — динамическая структура.

Над СД ЛС определены следующие основные операции:

1. Инициализация.

2. Включение элемента.

3. Исключение элемента.

4. Чтение текущего элемента.

5. Переход в начало списка.

6. Переход в конец списка.

7. Переход к следующему элементу.

8. Переход к i-му элементу.

9. Определение длины списка.

10. Уничтожение списка.

Кардинальное число СД ЛС определяется по формуле:

CAR(ЛС) = CAR(BaseType)⁰ + CAR(BaseType)¹ +… + CAR(BaseType)^max,

где CAR(BaseType) — кардинальное число элемента ЛС типа BaseType, max — максимальное количество элементов в ЛС (не всегда определено, т.к. может зависеть от объема свободной динамической памяти).

На абстрактном уровне ЛС представляет собой линейную структуру — последовательность.

На физическом уровне ЛС может быть реализован последовательной или связной схемой хранения.

Располагаться ЛС может в статической или динамической памяти. ЛС, реализованный последовательной схемой хранения, называется последовательным линейным списком (ПЛС). ЛС, реализованный связной схемой хранения, называется связным линейным списком (СЛС). Для реализации ПЛС используется вспомогательная встроенная СД — массив, элементы которого могут быть элементами ПЛС. Доступ к элементам ПЛС — прямой. Для реализации СЛС используется множество связанных элементов типа «запись», связь между которыми устанавливается с помощью поля-указателя. Элементы СЛС могут располагаться в массиве или в динамической памяти. СЛС подразделяются на односвязные линейные списки (ОЛС) и двусвязные линейные списки (ДЛС). В ОЛС каждый элемент состоит из информационного поля (поле данных) и одного поля-указателя, содержащего адрес следующего элемента. В ДЛС каждый элемент состоит из информационного поля и двух полей указателей, одно из которых содержит адрес следующего элемента в списке, а другое — предыдущего. Реализуется ОЛС, как правило, с первым фиктивным элементом, поле данных которого не используется, а ДЛС — с первым и последним фиктивным элементом. Введение фиктивных элементов позволяет упростить реализацию некоторых операций над ЛС.

Рассмотрим некоторые принципы реализации ЛС.

1. Реализация ПЛС

1.1. Последовательному линейному списку можно поставить в соответствие дескриптор, который состоит из 3-х полей:

1 — массив, на основе которого реализуется ПЛС;

2 — индекс текущего элемента;

3 — длина ПЛС.

Дескриптор располагается в статической памяти в виде переменной соответствующего типа. Массив, на основе которого реализуется ПЛС, также располагается в статической памяти.

1.2. Дескриптор ПЛС состоит из 4-х полей:

1 — указатель на массив, на основе которого реализуется ПЛС;

2 — количество элементов массива;

3 — индекс текущего элемента;

4 — длина ПЛС.

Дескриптор располагается в статической памяти в виде переменной соответствующего типа. Массив, на основе которого реализуется ПЛС, располагается в динамической памяти. Память под массив выделяется при инициализации ПЛС и количество элементов этого массива заносится во второе поле.

Элементы ПЛС могут находиться непосредственно в элементах массива, или в динамической памяти, а их адреса — в массиве.

2. Реализация ОЛС

2.1. Элементы ОЛС располагаются в динамической памяти. В статической памяти находится дескриптор ОЛС, состоящий из 3-х полей:

1 — указатель на фиктивный элемент ОЛС;

2 — указатель на текущий элемент;

3 — длина ОЛС.

Адрес фиктивного элемента определяется при инициализации.

Элемент ОЛС может содержать либо поле данных, либо адрес данных.

2.2. Элементы ОЛС располагаются в массиве. Элемент массива может содержать элемент ОЛС или быть «свободным». При включении элемента в ОЛС необходимо найти «свободный» элемент, сделать его «занятым» и включить в ОЛС. При исключении элемента нужно исключить элемент из ОЛС путем переопределения указателя предшествующего элемента на последующий и «освободить» исключенный элемент. «Свободные» элементы массива могут иметь специальный признак, отличающий их от элементов ОЛС, или могут быть объединены в список свободных элементов (ССЭ), на первый элемент которого указывает поле-указатель первого элемента массива. При включении элемента в ОЛС берется первый элемент ССЭ, а исключаемый элемент заносится в начало ССЭ.

В статической памяти находится дескриптор ОЛС, состоящий из трех полей:

1 — указатель на фиктивный элемент ОЛС;

2 — указатель на текущий элемент;

3 — длина ОЛС.

Адрес фиктивного элемента определяется при инициализации.

Элемент ОЛС может содержать либо поле данных, либо адрес данных.

3. Реализация ДЛС

3.1. В статической памяти находится дескриптор ДЛС, состоящий из 3-х полей:

1 — указатель на первый фиктивный элемент ДЛС;

2 — указатель на последний фиктивный элемент ДЛС;

3 — указатель на текущий элемент;

4 — длина ДЛС.

Адреса фиктивных элементов определяется при инициализации.

Элемент ДЛС может содержать либо поле данных, либо адрес данных и располагаться либо в динамической памяти, либо в массиве аналогично элементам ОЛС.

В заключении выполним сравнительный анализ последовательных и связных списков по эффективности хранения и выполнения операций.

1. СЛС требуют дополнительной памяти для связей.

2. Легко исключить элемент СЛС. Для исключения элемента из ОЛС достаточно лишь установить поле-указатель предшествующего элемента на последующий.

3. Время выполнения операции не зависит от положения исключаемого элемента. При исключении элемента из ПЛС обычно требуется перемещение элементов, расположенных за исключаемым, к началу списка. Чем ближе к началу списка расположен исключаемый элемент, тем больше времени требуется на выполнение операции.

4. Легко включить элемент в СЛС. Для включения элемента в ОЛС необходимо установить поле-указатель включаемого элемента на элемент, следующий за текущим, и переопределить поле-указатель текущего элемента (установить его на включаемый). Время выполнения операции не зависит от положения текущего элемента. При включении элемента в ПЛС требуется перемещения элементов, расположенных за текущим, к концу списка. Чем ближе к началу списка расположен текущий элемент, тем больше времени требуется на выполнение операции.

5. В ПЛС быстрее, чем в СЛС, выполняется обращения к i-му элементу списка, т.к. доступ к элементам ПЛС прямой, а к элементам СЛС — последовательный.

6. При использовании СЛС упрощается задача объединение двух списков или разбиение списков на части.

К о н т р о л ь н ы е в о п р о с ы

1. Что такое линейный список?

2. Определите характер изменчивости линейного списка.

3. Назовите основные операции над линейным списком.

4. Что собой представляет линейный список на абстрактном уровне?

5. Чем отличается последовательный линейный список от массива?

6. Что такое односвязный линейный список?

7. Какую структуру имеет элемент односвязного линейного списка?

8. Что такое двусвязный линейный список?

9. Какую структуру имеет элемент двусвязного линейного списка?

10. Как можно реализовать связный линейный список на массиве?

11. Какую структуру может иметь дескриптор линейного списка?

12. Зачем нужны фиктивные элементы в связных линейных списках?

13. Определите порядок функции временной сложности операции включения элемента в последовательный и связный линейный список.

14. Определите порядок функции временной сложности операции исключения элемента в последовательный и связный линейный список.

15. Определите порядок функции временной сложности операции перехода в начало последовательного и связного линейного списка.

16. Определите порядок функции временной сложности операции перехода в конец последовательного и связного линейного списка.

17. Определите порядок функции временной сложности операции перехода к следующему элементу последовательного и связного линейного списка.

18. Определите порядок функции временной сложности операции перехода к i-му элементу последовательного и связного линейного списка.

19. Определите порядок функции временной сложности линейного поиска в последовательном и связном линейном списке.

20. Какой алгоритм поиска целесообразно использовать в упорядоченном последовательном и связном линейном списке?

21. Предложите различные варианты реализации операции обмена соседних элементов в связном линейном списке.

22. Выполните сравнительный анализ алгоритмов сортировки связных линейных списков.

Л а б о р а т о р н а я р а б о т а № 6