Модели и структуры данных

Путаны Ярославля | Досуг в Оренбурге http://orenburg-dosug.com | Проститутки Хабаровска



Глава 1. Понятие структур данных и алгоритмов


    1.1. Понятие структур данных и алгоритмов
    1.1. Понятие структур данных и алгоритмов Структуры данных и алгоритмы служат теми материалами, из которых строятся программы. Более того, сам компьютер состоит из структур данных и алгоритмов. Вс...
    1.2. Информация и ее представление в памяти
    1.2. Информация и ее представление в памяти Начиная изучение структур данных или информационных структур, необходимо ясно установить, что понимается под информацией, как информация передается и ка...
    1.2.1. Природа информации
    1.2.1. Природа информации Можно сказать, что решение каждой задачи с помощью вычислительной машины включает запись информации в память, извлечение информации из памяти и манипулирование информацие...
    1.2.2. Хранение информации
    1.2.2. Хранение информации В цифровых вычислительных машинах можно выделить три основных вида запоминающих устройств: сверхоперативная, оперативная и внешняя память. Обычно сверхоперативная память...
    1.3. Системы счисления
    1.3. Системы счисления Чтобы обеспечить соответствующую основу для изучения структур данных следует обсудить существующие типы систем счислений: позиционные и непозиционные....
    1.3.1. Непозиционные системы счисления
    1.3.1. Непозиционные системы счисления Числа используются для символического представления количества объектов. Очень простым методом представления количества является использование одинаковых зна...
    1.3.2. Позиционные системы счисления
    1.3.2. Позиционные системы счисления В позиционной системе счисления используется конечное число R уникальных символов. Величину R часто называют основанием системы счисления. В позиционной систем...
    1.3.3. Изображение чисел в позиционной системе счисления
    1.3.3. Изображение чисел в позиционной системе счисления Изображение чисел в любой позиционной системе счисления с натуральным основанием R (R >1) базируется на представлении их в виде произведени...
    1.3.4. Перевод чисел из одной системы счисления в другую
    1.3.4. Перевод чисел из одной системы счисления в другую При переводе целого числа (целой части числа) из одной системы счисления в другую исходное число (или целую часть) надо разделить на основа...
    1.4. Классификация структур данных
    1.4. Классификация структур данных Теперь можно дать более конкретное определение данного на машинном уровне представления информации. Независимо от содержания и сложности любые данные в памяти ЭВ...
    Рис. 1.1. Классификация структур данных
    Рис. 1.1. Классификация структур данных Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры. В зави...
    1.5. Операции над структурами данных
    1.5. Операции над структурами данных Над любыми структурами данных могут выполняться четыре общие операции: создание, уничтожение, выбор (доступ), обновление. Операция создания заключается в выдел...
    1.6. Структурность данных и технология программирования
    1.6. Структурность данных и технология программирования Большинство авторов публикаций, посвященных структурам и организации данных, делают основной акцент на том, что знание структуры данных позв...
    1.1. Понятие структур данных и алгоритмов
    1.1. Понятие структур данных и алгоритмов Структуры данных и алгоритмы служат теми материалами, из которых строятся программы. Более того, сам компьютер состоит из структур данных и алгоритмов. Вс...
    1.2. Информация и ее представление в памяти
    1.2. Информация и ее представление в памяти Начиная изучение структур данных или информационных структур, необходимо ясно установить, что понимается под информацией, как информация передается и ка...
    1.2.1. Природа информации
    1.2.1. Природа информации Можно сказать, что решение каждой задачи с помощью вычислительной машины включает запись информации в память, извлечение информации из памяти и манипулирование информацие...
    1.2.2. Хранение информации
    1.2.2. Хранение информации В цифровых вычислительных машинах можно выделить три основных вида запоминающих устройств: сверхоперативная, оперативная и внешняя память. Обычно сверхоперативная память...
    1.3. Системы счисления
    1.3. Системы счисления Чтобы обеспечить соответствующую основу для изучения структур данных следует обсудить существующие типы систем счислений: позиционные и непозиционные....
    1.3.1. Непозиционные системы счисления
    1.3.1. Непозиционные системы счисления Числа используются для символического представления количества объектов. Очень простым методом представления количества является использование одинаковых зна...
    1.3.2. Позиционные системы счисления
    1.3.2. Позиционные системы счисления В позиционной системе счисления используется конечное число R уникальных символов. Величину R часто называют основанием системы счисления. В позиционной систем...
    1.3.3. Изображение чисел в позиционной системе счисления
    1.3.3. Изображение чисел в позиционной системе счисления Изображение чисел в любой позиционной системе счисления с натуральным основанием R (R >1) базируется на представлении их в виде произведени...
    1.3.4. Перевод чисел из одной системы счисления в другую
    1.3.4. Перевод чисел из одной системы счисления в другую При переводе целого числа (целой части числа) из одной системы счисления в другую исходное число (или целую часть) надо разделить на основа...
    1.4. Классификация структур данных
    1.4. Классификация структур данных Теперь можно дать более конкретное определение данного на машинном уровне представления информации. Независимо от содержания и сложности любые данные в памяти ЭВ...
    Рис. 1.1. Классификация структур данных
    Рис. 1.1. Классификация структур данных Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры. В зави...
    1.5. Операции над структурами данных
    1.5. Операции над структурами данных Над любыми структурами данных могут выполняться четыре общие операции: создание, уничтожение, выбор (доступ), обновление. Операция создания заключается в выдел...
    1.6. Структурность данных и технология программирования
    1.6. Структурность данных и технология программирования Большинство авторов публикаций, посвященных структурам и организации данных, делают основной акцент на том, что знание структуры данных позв...
    2. Простые структуры данных
    Простые структуры данных называют также примитивными или базовыми структурами. Эти структуры служат основой для построения более сложных структур. В языках программирования простые структуры описы...
    Рис. 2.1. Структура простых типов pascal.
    Рис. 2.1. Структура простых типов PASCAL....
    2.1.1. Целые типы
    2.1.1. Целые типы С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т.е. счетное число объектов)....
    Представление в памяти.
    Представление в памяти. Для представления чисел со знаком в ряде компьютеров был использован метод, называемый методом знака и значения. Обычно для знака отводится первый (или самый левый) бит дво...
    Таблица 2.1
    Таблица 2.1 Иными словами, диапазон возможных значений целых типов зависит от их внутреннего представления, которое может занимать 1, 2 или 4 байта. В таблице 2.1 приводится перечень целых типов,...
    Машинное представление беззнаковых типов.
    Машинное представление беззнаковых типов. К беззнаковым типам в PASCAL относятся типы BYTE и WORD. Формат машинного представления чисел типа BYTE приведен на рис 2.2. а). Например: 1). Машинное пр...
    Рис. 2.2. Формат машинного представления беззнаковых чисел
    Рис. 2.2. Формат машинного представления беззнаковых чисел Формат машинного представления чисел типа WORD приведен на рис. 2.2. б). Например: 1). Машинное представление числа 258: 257=2^8+2^1 = 00...
    Машинное представление чисел со знаком.
    Машинное представление чисел со знаком. Для представления чисел со знаком определены следующие типы SHORTINT, INTEGER, LONGINT. В приведенных типах числа хранятся в дополнительном ко- де. Напомним...
    Рис. 2.3. Формат машинного представления чисел со знаком
    Рис. 2.3. Формат машинного представления чисел со знаком На рис 2.3 s-знаковый бит числа. При этом, если s=0, то число положительное, если s=1 - число отрицательное. Цифры определяют номера разряд...
    Рис. 2.4. Формат машинного представления данных типа comp
    Рис. 2.4. Формат машинного представления данных типа COMP где s - знаковый разряд числа (если s=0,то число положительное, если s=1 - число отрицательное ) Например: машинное представление чисел в...
    2.1.2. Вещественные типы
    2.1.2. Вещественные типы В отличии от порядковых типов (все целые, символьный, логический), значения которых всегда сопоставляются с рядом целых чисел и, следовательно, представляются в памяти маш...
    Представление вещественных чисел в памяти.
    Представление вещественных чисел в памяти. В некоторых областях вычислений требуются очень большие или весьма малые действительные числа. Для получения большей точности применяют запись чисел с пл...
    Рис. 2.5. Формат представления вещественных чисел
    Рис. 2.5. Формат представления вещественных чисел Однако, чаще вместо порядка используется характеристика, получающаяся прибавлением к порядку такого смещения, чтобы характеристика была всегда пол...
    Таблица 2.2
    Таблица 2.2 Следующим компонентом представляемого в машине числа с плавающей точкой является мантисса. Для увеличения количества значащих цифр в представлении числа и исключения переполнения при у...
    Таблица 2.3
    Таблица 2.3...
    Алгоритм формирования машинного...
    Алгоритм формирования машинного представления вещественного числа в памяти ЭВМ Алгоритм формирования состоит из следующих пунктов: 1). Число представляется в двоичном коде. 2). Двоичное число норм...
    Машинное представление данных типа real
    Машинное представление данных типа REAL Формат машинного представления данных типа REAL следующий: мл. байт ст. байт а: 7 0 15 8 23 16 31 24 39 32 47 40 x....x м....м м....м м....м м....м sм...м б...
    Машинное представление данных типа single
    Машинное представление данных типа SINGLE Формат машинного представления данных типа SINGLE следующий: мл. байт ст. байт 7 0 15 8 23 22 16 31 30 24 - номера разрядов памяти м....м м....м х м...м s...
    Машинное представление данных типа double
    Машинное представление данных типа DOUBLE Формат машинного представления данных типа DOUBLE следующий: мл.байт ст.байт 7 0 15 8 23 16 31 24 39 32 47 40 55 52 51 48 63 56 м...м м...м м...м м...м м....
    Машинное представление данных типа extended
    Машинное представление данных типа EXTENDED Формат машинного представления данных типа EXTENDED следующий: мл.байт ст. байт 7 0 15 8 23 16 31 24 39 32 47 40 55 48 63 56 71 64 79 72 м..м м..м м..м...
    2.1.3. Десятичные типы
    2.1.3. Десятичные типы Десятичные типы не поддерживаются языком PASCAL, но имеются в некоторых других языках, например, COBOL, PL/1. Эти типы приме няются для внутримашинного представления таких д...
    Десятичный тип с фиксированной точкой.
    Десятичный тип с фиксированной точкой. В языке PL/1 десятичный тип с фиксированной точкой описывается в программе, как: DECIMAL FIXED (m.d) или DECIMAL FIXED (m). Первое описание означает, что дан...
    Рис.2.6. Машинное представление...
    Рис.2.6. Машинное представление десятичных чисел в упакованном формате Каждая десятичная цифра числа занимает полбайта (4 двоичных разряда) и представляется в этом полубайте ее двоичным кодом. Еще...
    Тип шаблона.
    Тип шаблона. В языке PL/1 тип шаблона описывается в программе, как: PICTURE '9...9'. Это означает, что данное представляет собой целое число, содержащее столько цифр, сколько девяток указано в опи...
    Рис.2.7. Машинное представление...
    Рис.2.7. Машинное представление десятичных чисел в зонном формате Внутримашинное представление этого типа, так называемый десятичный зонный формат, весьма близок к такому представлению данных, кот...
    2.1.4. Операции над числовыми типами
    2.1.4. Операции над числовыми типами Над числовыми типами, как и над всеми другими, возможны прежде всего четыре основных операции: создание, уничтожение, выбор, обновление. Специфические операции...
    2.2. Битовые типы
    2.2. Битовые типы...
    Представление битовых типов.
    Представление битовых типов. В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Чаще всего такие задачи возникают в системном программировании, когда, например, отдел...
    Операции над битовыми типами.
    Операции над битовыми типами. Над битовыми типами возможны три группы специфических операций: операции булевой алгебры, операции сдвигов, операции сравнения. Операции булевой алгебры - НЕ (not), И...
    2.3. Логический тип
    2.3. Логический тип Значениями логического типа BOOLEAN может быть одна из предварительно объявленных констант false (ложь) или true (истина). Данные логического типа занимают один байт памяти. Пр...
    2.4. Символьный тип
    2.4. Символьный тип Значением символьного типа char являются символы из некоторого предопределенного множества. В большинстве современных персональных ЭВМ этим множеством является ASCII (American...
    Логическая структура.
    Логическая структура. Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать переменная этого...
    Машинное представление.
    Машинное представление. Для переменной перечислимого типа выделяется один байт, в который записывается порядковый номер присваиваемого значения. Порядковый номер определяется из описаного типа, пр...
    Операции.
    Операции. На физическом уровне над переменными перечислимого типа определены операции создания, уничтожения, выбора, обновления. При этом выполняется определение порядкового номера идентификатора...
    Логическая структура.
    Логическая структура. Один из способов образования новых типов из уже существующих - ограничение допустимого диапазона значений некоторого стандартного скалярного типа или рамок описанного перечис...
    Машинное представление.
    Машинное представление. Данные интервального типа могут храниться в зависимости от верхней и нижней границ интервала независимо от входящего в этот предел количества значений в виде, представленно...
    Операции.
    Операции. На физическом уровне над переменными интервального типа определены операции создания, уничтожения, выбора, обновления. Дополнительные операции определены базовым типом элементов интервал...
    Таблица 2.4
    Таблица 2.4 Примечание: запись chr(ord(0)) в таблице следует понимать как: символ с кодом 0. А) Интервальный тип от символьного: определение кода символа и, наоборот, символа по его коду. Пусть за...
    2.7. Указатели
    2.7. Указатели Тип указателя представляет собой адрес ячейки памяти (в подавляющем большинстве современных вычислительных систем размер ячейки - минимальной адресуемой единицы памяти - составляет...
    2.7.1. Физическая структура указателя
    2.7.1. Физическая структура указателя Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. Рассмотрим в качестве примера структуру адреса в микропр...
    Рис 2.8. Вычисление полного адреса в микропроцессоре i8086.
    Рис 2.8. Вычисление полного адреса в микропроцессоре i8086. Еще раз повторим, что физическая структура адреса принципиально различна для разных аппаратных архитектур. Так, например, в микропроцесс...
    2.7.2. Представление указателей в языках программирования
    2.7.2. Представление указателей в языках программирования В программе на языке высокого уровня указатели могут быть типизированными и нетипизированными. При объявлении типизированного указателя оп...
    2.7.3. Операции над указателями.
    2.7.3. Операции над указателями. Основными операциями, в которых участвуют указатели являются присваивание, получение адреса, выборка. Присваивание является двухместной операцией, оба операнда кот...
    3. Статические структуры данных
    Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть пр...
    Логическая структура.
    Логическая структура. Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора...
    Машинное представление. Адресация элементов структур.
    Машинное представление. Адресация элементов структур. Элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяем...
    Рис. 3.1. Представление вектора в памяти
    Рис. 3.1. Представление вектора в памяти где @ Имя -адрес вектора или, что тоже самое, адрес первого элемента вектора, Sizeof(тип)-размер слота (количество байтов памяти для записи одного элемента...
    Рис. 3.2. Представление вектора m1 в памяти
    Рис. 3.2. Представление вектора m1 в памяти В языках, где память распределяется до выполнения программы на этапе компиляции (C, PASCAL, FORTRAN), при описании типа вектора граничные значения индек...
    Таблица 3.1
    Таблица 3.1 Этот вектор будет занимать в памяти: (10-5+1)*2 = 12 байт. Смещение к элементу вектора с номером 8: (8-5)*2 = 6 Адрес элемента с номером 8: @ MAS + 6. При доступе к вектору задается им...
    3.2.1. Логическая структура
    3.2.1. Логическая структура Массив - такая структура данных, которая характеризуется: фиксированным набором элементов одного и того же типа; каждый элемент имеет уникальный набор значений индексов...
    3.2.2. Физическая структура
    3.2.2. Физическая структура Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая струк...
    Рис. 3.3. Физическая структура...
    Рис. 3.3. Физическая структура двумерного массива из (k1-n1+1) строк и (k2-n2+1) столбцов Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемент...
    Таблица 3.2
    Таблица 3.2 Этот массив будет занимать в памяти: (5-3+1)*(8-7+1)*2=12 байт; а адрес элемента Mas[4,8]: @Mas+((4-3)*(8-7+1)+(8-7)*2 = @Mas+6...
    3.2.3. Операции
    3.2.3. Операции Важнейшая операция физического уровня над массивом - доступ к заданному элементу. Как только реализован доступ к элементу, над ним может быть выполнена любая операция, имеющая смыс...
    3.2.4. Адресация элементов с помощью векторов айлиффа
    3.2.4. Адресация элементов с помощью векторов Айлиффа Из выше приведенных формул видно, что вычисление адреса элемента многомерного массива может потребовать много времени, поскольку при этом долж...
    Рис. 3.4. Представление массивов с помощью векторов айлиффа
    Рис. 3.4. Представление массивов с помощью векторов Айлиффа Для массива любой мерности формируется набор дескрипторов: основного и несколько уровней вспомогательных дескрипторов, называемых вектор...
    3.2.5. Специальные массивы
    3.2.5. Специальные массивы На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько б...
    Симметричные массивы.
    Симметричные массивы. Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относ...
    Разреженные массивы.
    Разреженные массивы. Разреженный массив - массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений отличных от основного (фоновог...
    Массивы с математическим описанием...
    Массивы с математическим описанием местоположения нефоновых элементов. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, могут быть...
    Разреженные массивы со случайным расположением элементов.
    Разреженные массивы со случайным расположением элементов. К данному типу массивов относятся массивы, у которых местоположения элементов со значениями отличными от фонового, не могут быть математич...
    Представление разреженным матриц...
    Представление разреженным матриц методом последовательного размещения. Один из основных способов хранения подобных разреженных матриц заключается в запоминании ненулевых элементов в одномерном мас...
    Рис. 3.5. Последовательное представление разреженных матриц.
    Рис. 3.5. Последовательное представление разреженных матриц....
    Представление разреженных матриц методом связанных структур.
    Представление разреженных матриц методом связанных структур. Методы последовательного размещения для представления разреженных матриц обычно позволяют быстрее выполнять операции над матрицами и бо...
    Рис.3.6. Формат вершины для представления разреженных матриц
    Рис.3.6. Формат вершины для представления разреженных матриц На рис. 3.7 приведена многосвязная структура, в которой используются вершины такого типа для представления матрицы А, описанной ранее в...
    Рис. 3.7. Многосвязная структура для представления матрицы a
    Рис. 3.7. Многосвязная структура для представления матрицы A Может показаться странным, что указатели в этой многосвязной структуре направлены вверх и влево, вследствие чего при сканировании цикли...
    Логическая структура.
    Логическая структура. Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип...
    Физическая структура.
    Физическая структура. Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элемент...
    3.3.1. Числовые множества
    3.3.1. Числовые множества Стандартный числовой тип, который может быть базовым для формирования множества - тип byte. Множество хранится в памяти как показано в таблице 3.3....
    Таблица 3.3
    Таблица 3.3 где @S - адрес данного типа множество. Бит поля установлен в 1, если элемент входит в множество, и в 0 - если не входит. Например, S : set of byte; S:=[15,19]; Содержимое памяти при эт...
    3.3.2. Символьные множества
    3.3.2. Символьные множества Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов. Например, S : set of char; S:=[...
    3.3.3. Множество из элементов перечислимого типа
    3.3.3. Множество из элементов перечислимого типа Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти...
    Рис. 3.8. Распределение памяти...
    Рис. 3.8. Распределение памяти для переменной типа set of Video Если выполнить оператор S:=[CGA,SVGA], содержимое памяти при этом будет: @S+0 - 10000010 @S+1 - 00000000...
    3.3.4. Множество от интервального типа
    3.3.4. Множество от интервального типа Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает м...
    Рис. 3.9. Представление переменной типа set of s
    Рис. 3.9. Представление переменной типа set of S Для конструирования множеств интервальный тип самый экономичный, т.к. занимает память в зависимости от заданных границ. Например, Type S = 510..520...
    3.3.5. Операции над множествами
    3.3.5. Операции над множествами Пусть S1, S2, S3 : set of byte , Над этими множествами определены следующие специфические операции: 1) Объединение множеств: S2+S3. Результатом является множество,...
    3.4.1. Логическое и машинное представление записей
    3.4.1. Логическое и машинное представление записей Запись - конечное упорядоченное множество полей, характеризующихся различным типом данных. Записи являются чрезвычайно удобным средством для пред...
    Рис. 3.10. Представление в памяти...
    Рис. 3.10. Представление в памяти переменной типа record в виде последовательности полей б) в виде связного списка с указателями на значения полей записи. При такой организации имеет место быстрое...
    Рис. 3.11. Представление в памяти...
    Рис. 3.11. Представление в памяти переменной типа record в виде связного списка. Примечание: для экономии объема памяти, отводимой под запись, значения некоторых ее полей хранятся в самом дескрипт...
    3.4.2. Операции над записями
    3.4.2. Операции над записями Важнейшей операцией для записи является операция доступа к выбранному полю записи - операция квалификации. Практически во всех языках программирования обозначение этой...
    3.5. Записи с вариантами
    3.5. Записи с вариантами В ряде прикладных задач программист может столкнуться с группами объектов, чьи наборы свойств перекрываются лишь частично. Обработка таких объектов производится по одним и...
    Рис.3.12. Выделение памяти для записи с вариантами
    Рис.3.12. Выделение памяти для записи с вариантами Как видно из рисунка, под запись с вариантами выделяется в любом случае объем памяти, достаточный для размещения самого большого варианта. Если ж...
    3.6. Таблицы
    3.6. Таблицы Когда речь шла о записях, было отмечено, что полями записи могут быть интегрированные структуры данных - векторы, массивы, другие записи. Аналогично и элементами векторов и массивов м...
    3.7. Операции логического уровня...
    3.7. Операции логического уровня над статическими структурами. Поиск В этом и следующих разделах представлен ряд алгоритмов поиска данных и сортировок, выполняемых на статических структурах данных...
    3.7.1. Последовательный или линейный поиск
    3.7.1. Последовательный или линейный поиск Простейшим методом поиска элемента, находящегося в неупорядоченном наборе данных, по значению его ключа является последовательный просмотр каждого элемен...
    3.7.2. Бинарный поиск
    3.7.2. Бинарный поиск Другим относительно простым методом доступа к элементу является метод бинарного (дихотомического, двоичного) поиска, который выполняется в заведомо упорядоченной последовател...
    Таблица 3.4
    Таблица 3.4 Алгоритм бинарного поиска можно представить и несколько иначе, используя рекурсивное описание. В этом случае граничные индексы интервала b и e являются параметрами алгоритма. Рекурсивн...
    3.8. Операции логического уровня...
    3.8. Операции логического уровня над статическими структурами. Сортировка Для самого общего случая сформулируем задачу сортировки таким образом: имеется некоторое неупорядоченное входное множество...
    Сортировка простой выборкой.
    Сортировка простой выборкой. Данный метод реализует практически "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - O(N^2). Количество пересылок - N. Алгоритм с...
    Обменная сортировка простой выборкой.
    Обменная сортировка простой выборкой. Алгоритм сортировки простой выборкой, однако, редко применяется в том варианте, в каком он описан выше. Гораздо чаще применяется его, так называемый, обменный...
    Таблица 3.5
    Таблица 3.5 Очевидно, что обменный вариант обеспечивает экономию памяти. Очевидно также, что здесь не возникает проблемы "пустого" значения. Общее число сравнений уменьшается вдвое - N*(N-1)/2, но...
    Пузырьковая сортировка.
    Пузырьковая сортировка. Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности...
    Таблица 3.6
    Таблица 3.6 Еще одна модификация пузырьковой сортировки носит название шейкер-сортировки. Суть ее состоит в том, что направления просмотров чередуются: за просмотром от начала к концу следует прос...
    Сортировка шелла.
    Сортировка Шелла. Это еще одна модификация пузырьковой сортировки. Суть ее состоит в том, что здесь выполняется сравнение ключей, отстоящих один от другого на некотором расстоянии d. Исходный разм...
    Таблица 3.7
    Таблица 3.7...
    Сортировка простыми вставками.
    Сортировка простыми вставками. Этот метод - "дословная" реализации стратегии включения. Порядок алгоритма сортировки простыми вставками - O(N^2), если учитывать только операции сравнения. Но сорти...
    Пузырьковая сортировка вставками.
    Пузырьковая сортировка вставками. Это модификация обменного варианта сортировки. В этом методе входное и выходное множества находятся в одной последовательности, причем выходное - в начальной ее ч...
    Таблица 3.8
    Таблица 3.8 Хотя обменные алгоритмы стратегии включения и позволяют сократить число сравнений при наличии некоторой исходной упорядоченности входного множества, значительное число пересылок сущест...
    Сортировка упорядоченным двоичным деревом.
    Сортировка упорядоченным двоичным деревом. Алгоритм складывается из построения упорядоченного двоичного дерева и последующего его обхода. Если нет необходимости в построении всего линейного упоряд...
    Турнирная сортировка.
    Турнирная сортировка. Этот метод сортировки получил свое название из-за сходства с кубковой системой проведения спортивных соревнований: участники соревнований разбиваются на пары, в которых разыг...
    Рис.3.13. Пирамида турнирной сортировки
    Рис.3.13. Пирамида турнирной сортировки В примере 3.12 приведена программная иллюстрация алгоритма турнирной сортировки. Она нуждается в некоторых пояснениях. Построение пирамиды выполняется функц...
    Рис.3.14. Пирамида после последовательных выборок
    Рис.3.14. Пирамида после последовательных выборок Процедура Heap_Sort получает входной параметр ph - указатель на вершину пирамиды. и формирует выходной параметр a - упорядоченный массив чисел. Вс...
    Сортировка частично упорядоченным деревом.
    Сортировка частично упорядоченным деревом. В двоичном дереве, которое строится в этом методе сортировки для каждого узла справедливо следующее утверждение: значения ключа, записанное в узле, меньш...
    Рис.3.15. Частично упорядоченное дерево
    Рис.3.15. Частично упорядоченное дерево Представление дерева в виде пирамиды наглядно показывает нам, что для такого дерева можно ввести понятия "начала" и "конца". Началом, естественно, будет счи...
    Рис.3.16. Частично упорядоченное дерево, включение элемента
    Рис.3.16. Частично упорядоченное дерево, включение элемента Процедура выборки элемента несколько сложнее. Очевидно, что минимальный элемент находится в вершине. После выборки за освободившееся мес...
    Рис.3.17. Частично упорядоченное дерево, исключение элемента
    Рис.3.17. Частично упорядоченное дерево, исключение элемента Упорядоченность дерева восстановлена, но нарушено условие его сбалансированности, так как свободное место находится не в конце дерева....
    Поразрядная цифровая сортировка.
    Поразрядная цифровая сортировка. Алгоритм требует представления ключей сортируемой последовательности в виде чисел в некоторой системе счисления P. Число проходов сортировка равно максимальному чи...
    Таблица 3.9
    Таблица 3.9...
    Быстрая сортировка хоара.
    Быстрая сортировка Хоара. Данный алгоритм относится к распределительным и обеспечивает показатели эффективности O(N*log2(N)) даже при наихудшем исходном распределении. Используются два индекса - i...
    Таблица 3.10
    Таблица 3.10...
    3.8.4. Сортировки слиянием.
    3.8.4. Сортировки слиянием. Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгори...
    Сортировка попарным слиянием.
    Сортировка попарным слиянием. Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченны...
    Таблица 3.11
    Таблица 3.11...
    4.1. Характерные особенности полустатических структур
    4.1. Характерные особенности полустатических структур Полустатические структуры данных характеризуются следующими признаками: они имеют переменную длину и простые процедуры ее изменения; изменение...
    4.2.1. Логическая структура стека
    4.2.1. Логическая структура стека Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого верш...
    Рис 4.1. Включение и исключение элементов из стека.
    Рис 4.1. Включение и исключение элементов из стека. Как видно из рис. 4.1, стек можно представить, например, в виде стопки книг (элементов), лежащей на столе. Присвоим каждой книге свое название,...
    4.2.2. Машинное представление стека и реализация операций
    4.2.2. Машинное представление стека и реализация операций При представлении стека в статической памяти для стека выделяется память, как для вектора. В дескрипторе этого вектора кроме обычных для в...
    4.2.3. Стеки в вычислительных системах
    4.2.3. Стеки в вычислительных системах Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных...
    4.3.1. Логическая структура очереди
    4.3.1. Логическая структура очереди Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается"). называется такой последовательный список с переменной длиной, в котором включени...
    4.3.2. Машинное представление...
    4.3.2. Машинное представление очереди FIFO и реализация операций При представлении очереди вектором в статической памяти в дополнение к обычным для дескриптора вектора параметрам в нем должны нахо...
    4.3.3. Очереди с приоритетами
    4.3.3. Очереди с приоритетами В реальных задачах иногда возникает необходимость в формировании очередей, отличных от FIFO или LIFO. Порядок выборки элементов из таких очередей определяется приорит...
    4.3.4. Очереди в вычислительных системах
    4.3.4. Очереди в вычислительных системах Идеальным примером кольцевой очереди в вычислительной системы является буфер клавиатуры в Базовой Системе Ввода-Вывода ПЭВМ IBM PC. Буфер клавиатуры занима...
    4.4.1. Логическая структура дека
    4.4.1. Логическая структура дека Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и и...
    Рис. 4.2. Состояния дека в процессе изменения.
    Рис. 4.2. Состояния дека в процессе изменения. На рис. 4.2 в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает...








Начало