1)Односвязные линейные списки

Связный список – структура, элементы которой имеют один и тот же формат и связаны друг с другом с помощью указателей, хранящихся в самих элементах.

В односвязном списке каждый элемент состоит из двух различных по назначению полей: содержательного поля (поле данных) и служебного поля (поля указателя), где хранится адрес следующего элемента .Поле указателя последнего элемента списка содержит нулевой указатель, свидетельствующий о конце списка.

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

Логическая структура линейного односвязного списка:

Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель текущего элемента списка.

Логическая структура элемента линейного односвязного списка:

Данные или указатель на данные, указатель на следующий элемент списка.

Основные операции над линейным односвязным списком:

перемещение по списку;

включение элемента в линейный односвязный список ;

исключение элемента из линейного односвязного списка;

извлечение содержательного поля любого элемента;

изменение содержательного поля любого элемента;

подсчет количества элементов списка;

слияние линейных односвязных списков (частный случай операции включения

линейного односвязного списка);

выделение линейного односвязного подсписка.

Продвижение в линейном односвязном списке возможно только в одном направлении. Результаты выполнения операций включения элемента в линейный односвязный список и исключения элемента из линейного односвязного списка – линейный односвязный список.

На языке Паскаль линейный односвязный список может быть описан следующим образом:

TYPE

ptr=^Node;

Node=record

x:<базовый тип>;

next:ptr;

end;

var b:ptr;

Доступ к элементу списка осуществляется следующей командой: b:^.x. Например, для того чтобы обратиться к третьему элементу списка необходимо: b^.next^.x.

2) Записи. Организация, размещение. Записи с вариантами.

Запись – структурированный тип данных, состоящий из фиксированного числа компонентов одного или нескольких типов.

Объявление

Type

<имя типа>=record

<идентификатор поля> : <тип компонента>;

…

<идентификатор поля> : <тип компонента>

End;

Var <идентификатор> : <имя типа>;

Для доступа к полям записи используется переменная типа запись, у которой составное имя ( <переменная>.<название поля>).

Обращение к запиписи

With <переменная типа запись> do <оператор>;

Паскаль допускает, то что поле записи может быть записью, тогда with тоже будет вложенным. (with <запись1>,<запись2>do)

Запись с вариантами

Обычно запись имеет строгую структуру. Иногда это серьёзно ограничивает их применение. Поэтому в паскале есть тип записи, который содержит произвольное число вариантов структуры. Такие записи называются записями с вариантами. Данная запись состоит из фиксированной и вариантной частей.

Фиксированная часть используется так же как обычно. Вариантная часть формируется при помощи оператора case. Он задает особое поле – поле признака, которое определяет какой из вариантов сейчас будет активен. Константа, которая служит признаком, задает вариант записи и называется константой выбора

Объявление

Type

Rec=record

Case <поле признака> <имя типа> of

<константа1> : (поле … : тип);

<константа2>: (поле … : тип)

End;

Билет 30

1 ВОПРОС: Двухсвязные линейные списки и кольца, операции над ними.

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

двухсвязный список,- список каждый элемент которого содержит два указателя: как на следующий, так и на предыдущий элементы списка.

Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются.

В памяти список представляет собой совокупность дескриптора и одинаковых по размеру и формату записей, размещенных произвольно в некоторой области памяти и связанных друг с другом в линейно упорядоченную цепочку с помощью указателей. Запись содержит как информационные поля, так и поля указателей на соседние элементы списка, причем некоторыми полями информационной части могут быть указатели на блоки памяти с дополнительной информацией, относящейся к элементу списка. Дескриптор списка реализуется в виде особой записи и содержит такую информацию о списке, как адрес начала списка, код структуры, имя списка, текущее число элементов в списке, описание элемента и т.д.

Ниже рассматриваются некоторые простые операции над линейными списками.

Перебор элементов списка. Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка - ко всем до конца списка или до нахождения искомого элемента.

В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же, как и перебор в односвязном списке), так и в обратном. В последнем случае параметром процедуры должен быть tail - указатель на конец списка, и переход к следующему элементу должен осуществляться по указателю назад:

Current := Current->prev;

В кольцевом списке окончание перебора должно происходить не по признаку последнего элемента - такой признак отсутствует, а по достижению элемента, с которого начался перебор. Алгоритмы перебора для двусвязного и кольцевого списка мы оставляем читателю на самостоятельную разработку.

2 ВОПРОС: Сортировка и поиск информации. Методы внутренней сортировки.

Сортировкой является такая перестановка элементов (в массиве), после которой они оказываются упорядоченными требуемым образом. Элементы размещаются так, чтобы, во-первых, вычисления требующие определенного порядка расположения данных, могли выполняться эффективно, во-вторых, результаты имели осмысленный вид, в третьих, последующие процессы бы пригодные исходные данные. Примером сортировки может служить упорядочение по алфавиту. Поиск заключается в отыскании элемента (в массиве), значение которого совпадает с ключом поиска. Примером поиска служит отыскание элемента данных, включающего фамилию и адрес, по заданной фамилии. Поиском заданного значения в массиве приходится заниматься очень часто. При этом задается аргумент поиска (тема, автор, ключевое слово, страница и т.д.) и требуется определить положение в массиве такого элемента, у которого значение ключа (например, имя автора или номер страницы) совпадает с аргументом. Если порядок расположения данных в массиве неизвестен, то нет более эффективного метода, чем простой последовательный поиск (сканирование), при котором ключ каждого элемента данных сравнивается с аргументом поиска некоторым регулярным образом. При этом для поиска в массиве из N значений в среднем приходится выполнить N/2 сравнений.Предложить методы более быстрого поиска можно только в том случае, если данные определенным образом упорядочены. Например, тот факт, что в телефонном справочнике записи упорядочены по алфавиту, позволяет нам очень быстро находить нужную фамилию и номер телефона.Универсальным методом быстрого поиска в упорядоченном множестве данных является бинарный поиск, при котором число сравнений, выполняемых для поиска в массиве из N значений, в среднем пропорционально log2(N). Сравним это число со средним числом сравнений в простом методе последовательного поиска, которое пропорционально N:N 10 100 1000 log2(N) 3,3 6,6 9,9т.е., например, в книге из 1000 страниц при последовательном поиске какой-либо страницы приходится сделать в среднем 500 шагов, а при бинарном поиске нужная страница будет гарантированно найдена за 10 шагов.Очевидно, дополнительные затраты на упорядочение множества данных (сортировку) более чем окупаются при применении бинарного поиска. Метод бинарного поиска заключается в последовательном делении множества данных на две равные части - отсюда и название "бинарный" (двоичный). Первоначально областью поиска считается все множество; из него извлекается средний элемент, ключ которого сравнивается с аргументом поиска. Если они совпали, то поиск на этом успешно завершается, но если они не совпадают, то аргумент поиска может быть больше или меньше ключа среднего элемента. Тогда в зависимости от способа упорядочения данных в качестве области поиска выбирается первая или вторая половина множества, из нее извлекается средний элемент и его ключ сравнивается с аргументом поиска. Этот процесс продолжается до тех пор, пока не приведет либо к успеху, либо к неудаче. Традиционно методы сортировки делят на внутренние и внешние. Внутренние методы – это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти процессора.

Билет 21