Главная страница
Навигация по странице:

  • Логический тип - BOOLEAN

  • Указательный тип -POINTER

  • Получение абсолютного адреса из

  • 4. КЛАССИФИКАЦИЯ СТРУКТУР ДАН- НЫХ

  • 34. Сортировка методом прямого включения

  • Алгоритм сортировки методом прямо- го включения без барьера

  • Алгоритм сортировки методом прямо- го включения с барьером

  • Сmax = n(n

  • 6. ПОНЯТИЕ СПИСКОВОЙ СТРУКТУРЫ. СТЕК. К полустатическим структурам данных относят стеки, деки и очереди. Списки

  • Операции, производимые над стека

  • Empty(S) if i = 0 then empty = true else empty = false endif return Pop(S)

  • A) целый (integer) b) вещественный (real)


    Скачать
    НазваниеA) целый (integer) b) вещественный (real)
    АнкорAISD.pdf
    Дата25.03.2020
    Размер
    Формат файлаpdf
    Имя файлаAISD.pdf
    ТипДокументы
    #175
    страница1 из 6
      1   2   3   4   5   6

    1. ТИПЫ ДАННЫХ
    В математике принято классифицировать переменные в соответствие с некоторыми важными характеристиками. Мы разли- чаем вещественные, комплексные и ло- гические переменные, переменные, представляющие собой отдельные зна- чения, множества значений или множе- ства множеств. В обработке данных по- нятие классификации играет такую же, если не большую роль. Мы будем при- держиваться того принципа, что любая константа, переменная, выражение или функция относятся к некоторому типу.
    Фактически тип характеризует множест- во значений, которые может принимать некоторая переменная или выражение и которые может формировать функция.
    В большинстве языков программирова- ния различают стандартные типы данных и типы, заданные пользователем. К стан- дартным относят 5 типов:
    a) целый (INTEGER);
    b) вещественный (REAL) ;
    c) логический (BOOLEAN);
    d) символьный (CHAR);
    e) указательный (POINTER).
    К пользовательским относят 2 типа:
    a) перечисляемый;
    b) диапазонный.
    Любой тип данных должен быть охарак- теризован областью значений и допусти- мыми операциями над этим типом Дан- ных.
    Целый тип - INTEGER
    Этот тип включает некоторое подмноже- ство целых, размер которого варьируется от машины к машине. Если для представ- ления целых чисел в машине использу- ется n разрядов, причем используется дополнительный код, то допустимые чис- ла должны удовлетворять условию -2
    '<= х< 2 .
    Считается, что все операции над данны- ми этого типа выполняются точно и соот- ветствуют обычным правилам арифмети- ки. Если результат выходит за пределы представимого множества, то вычисления будут прерваны. Такое событие называ- ется переполнением.
    Числа делятся на знаковые и беззнако- вые. Для каждого из них имеется свой диапазон значений: а)(0..2
    n
    -1) для без знаковых чисел
    Рис. 1.1
    При обработке машиной чисел, исполь- зуется формат со знаком. Если же ма- шинное слово используется для записи и обработки команд и указателей, то в этом случае используется формат без знака.
    Операции над целым типом: a) Сложение. b) Вычитание. c) Умножение. d) Целочисленное деление. e) Нахождение остатка по модулю. f) Нахождение экстремума числа (мини- мума и максимума) g) Реляционные операции (операции сравнения) (<,>,<=,>=, =,<>)
    Примеры: Adiv В = С
    Amod В = D С* B + D = A
    7 div 3 = 2 7 mod 3 = 1
    Во всех операциях, кроме реляционных, в результате получается целое число.
    Вещественный тип - REAL
    Вещественные типы образуют ряд под- множеств вещественных чисел, которые представлены в машинных форматах с плавающей точкой. Числа в формате с плавающей точкой характе- ризуются целочисленными значениями мантиссы и порядка, которые опре- деляют диапазон изменения и количество верных знаков в представ- лении чисел вещественного типа.
    X = +/- М * q
    (+/-P)
    - полулогарифмическая форма представления числа, показана на рисунке 2.
    937,56 = 93756 * 10
    -2
    = 0,93756 * 10 3
    Рис. 1.2
    Удвоенная точность необходима для того, чтобы увеличить точность мантиссы.
    Логический тип - BOOLEAN
    Стандартный логический тип Boolean
    (размер-1 байт) представляет собой тип данных, любой элемент которого может принимать лишь 2 значения: True и
    False.
    Над логическими элементами данных выполняются логические операции. Ос- новные из них: a) Отрицание (NOT) b) Конъюнкция (AND) c) Дизъюнкция (OR)
    Логические значения получаются также при реляционных операциях с целыми числами.
    Символьный тип – CHAR
    Тип CHAR содержит 26 прописных латин- ских букв и 26 строчных, 10 арабских цифр и некоторое число других гра- фических символов, например, знаки пунктуации.
    Подмножества, букв и цифр упорядочены и "соприкасаются", т.е.
    ("А"<= х)&(х <= "Z") - х представляет собой прописную букву
    ("0"<= х)&(х <= "9") - х представляет собой цифру Тип CHAR содержит некото- рый непечатаемый символ, пробел, его можно использовать как разделитель.
    Операции: a) Присваивания b) Сравнения c) Определения номера данной литеры в системе кодирования. ORD(W
    i
    ) d) Нахождение литеры по номеру. CHR(i) e) Вызов следующей литеры. SUCC(W
    i
    ) f) Вызов предыдущей литеры. PRED(W
    i
    )
    Указательный тип -POINTER
    Переменная типа указатель является физическим носителем адреса величины базового типа.
    Стандартный тип- указатель Pointer дает указатель, не свя- занный ни с каким конкретным базовым типом. Этот тип совместим с любым другим типом-указателем.
    Операции: a) Присваивания b) Операции с беззнаковыми целыми числами.
    При помощи этих операций можно вы- числить адрес данных. В машинном виде эти типы занимают максимально возмож- ную длину.
    Например:
    ABCD:1234 - значение указателя в ше- стнадцатеричной системе счисления - относительный адрес. Первое число
    (ABCD) - адрес сегмента Второе число
    .(1234) - адрес внутри сегмента.
    Получение абсолютного адреса из
    относительного:
    Для получения абсолютного адреса не- обходимо произвести сдвиг адреса сег- мента влево, и к полученному числу прибавить адрес внутреннего сегмента.
    Например:
    1) Сдвигаем ABCD на один разряд влево.
    Получаем ABCD0.
    2) Прибавляем 1234. Полученный ре- зультат и является абсолютным адресом.
    ABCD0 1234
    ---------
    ACF04 – абсолютный адрес данного чис- ла.
    Наиболее важной характеристикой явля- ется изменчивость структуры во време- ни.
    По признаку физического размещения структуры данных различают оператив- ные и файловые структуры. Структуры данных, размещаемые в оперативной памяти, называют оперативными струк- турами. Файловые структуры соответст- вуют структурам данных внешней памя- ти. Оперативная память является быст- рой, а внешняя — медленной.
    2. СТАНДАРТНЫЕ и пользовательские ти- пы
    Все типы данных можно разделить на две группы: скалярные и структурированные
    (составные). Скалярные типы, в свою очередь, делятся на стандартные и поль- зовательские.
    Стандартные типы данных предлагаются пользователям разработчиками системы.
    К ним относятся целочисленные, вещест- венные, литерные, булевские типы дан- ных и указатели.
    Пользовательские типы данных разраба- тываются пользователями системы про- граммирования.
    3. СТРУКТУРЫ ДАННЫХ
    Структуры данных - это совокупность элементов данных и отношений между ними. При этом под элементами данных может подразумеваться как простое дан- ное так и структура данных. Под отно- шениями между данными понимают функциональные связи между ними и указатели на то, где находятся эти дан- ные.
    Графическое представление элемента структуры данных.
    Элемент отношений - это совокупность всех связей элемента с другими элемен- тами данных, рассматриваемой структу- ры.
    S:=(D,R)
    Где S - структура данных, D - данные и R
    - отношения.
    Как бы сложна ни была структура дан- ных, в конечном итоге она состоит из простых данных.
    Внутренний мир ЭВМ далеко не так прост, как мы думаем. Память машины состоит из миллионов триггеров, которые обрабатывают поступающую информа- цию.
    Мы, занося инф-цию в компьютер, пред- ставляем еѐ в каком-то виде, который на наш взгляд упорядочивает данные и придаѐт им смысл. Машина отводит поле для поступающей инф-ции и задаѐт ей какой-то адрес. Т.о. получается, что мы обрабатываем данные на логическом уровне, как бы абстрактно, а машина делает это на физическом уровне.
    4. КЛАССИФИКАЦИЯ СТРУКТУР ДАН-
    НЫХ
    Структуры данных классифицируются:
    1. По связанности данных в структуре:
    - если данные в структуре связаны очень слабо, то такие структуры называются
    несвязанными (вектор, массив, строки, стеки)
    - если данные в структуре связаны, то такие структуры называются связанными
    (связанные списки)
    2. По изменчивости структуры во време- ни или в процессе выполнения програм- мы:
    - статические структуры - структуры, неменяющиеся до конца выполнения программы (записи, массивы, строки, вектора)
    - полустатические структуры (стеки, де- ки, очереди)
    - динамические структуры - происходит полное изменение при выполнении про- граммы
    3. По упорядоченности структуры:
    - линейные (вектора, массивы, стеки, деки, записи)
    - нелинейные (многосвязные списки, древовидные структуры, графы)
    Наиболее важной характеристикой явля- ется изменчивость структуры во времени.
    Векторы
    Самая простая статическая структура - это вектор. Вектор - это чисто линейная упорядоченная структура, где отношение между ее элементами есть строго выра- женная последовательность элементов структуры (рис. 2.5).
    Каждый элемент вектора имеет свой ин- декс, определяющий положение данного элемента в векторе. Поскольку индексы являются целыми числами, над ними можно производить операции и, таким образом, вычислять положение элемента в структуре на логическом уровне досту- па. Для доступа к элементу вектора, дос- таточно просто указать имя вектора
    (элемента) и его индекс .
    Для доступа к этому элементу использу- ется функция адресации, которая фор- мирует из значения индекса адрес слота, где находится значение исходного эле- мента. Для объявления в программе век- тора необходимо указать его имя, коли- чество элементов и их тип (тип данных)
    Пример: var
    Ml: Array [1..100] of integer; M2: Array
    [1...10] of real;
    Вектор состоит из совершенно однотип- ных данных и количество их строго оп- ределено.
    2.3.2 Массивы
    В общем случае элемент массива - это есть элемент вектора, который сам по себе тоже является элементом структуры
    (рис. 2.6).
    Для доступа к элементу двумерного мас- сива необходимы значения пары индек- сов (номер строки и номер столбца, а пересечении которых находится эле- мент). На физическом ровне двумерный массив выглядит также, как и одномер- ный вектор), причем трансляторы пред- ставляют массивы либо в виде строк, либо в виде столбцов.
    5. ЗАПИСИ И ТАБЛИЦЫ.
    Запись представляет из себя структуру данных последовательного типа, где элементы структуры расположены один за другим как в логическом, так и в фи- зическом представлении. Запись предпо- лагает множество элементов разного ти- па. Элементы данных в записи часто на- зывают полями записи.
    Логическая структура записи может быть представлена как
    В графическом виде, так и в табличном.
    Операции над записями:
    1.Прочтение содержимого поля записи.
    2. Занесение информации в поле записи.
    3. Все операции, которые разрешаются над полем записи, соответствующего типа.
    При задании таблицы указывается коли- чество содержащихся в ней записей.
    Пример:
    Type ST = Record
    Num: Integer; Name: String[15];
    Fak: String[5]; Group: String[10];
    Angl: Integer; Physic: Integer; var Table: Array [1...19] of St;
    Элементом данных таблицы является запись. Поэтому операции, которые про- изводятся с таблицей - это операции, производимые с записью.
    Операции с таблицами:
    1. Поиск записи по заданному ключу.
    2. Занесение новой записи в таблицу.
    Ключ - это идентификатор записи. Для хранения этого идентификатора отводит- ся специальное поле.
    Составной ключ - ключ, содержащий бо- лее двух полей.
    34. Сортировка методом прямого
    включения
    Элементы мысленно делятся на уже гото- вую последовательность a1,...,ai-1 и ис- ходную последовательность. При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной по- следовательности извлекается i-й элемент и перекладывается в готовую последова- тельность, при этом он вставляется на нужное место.
    Алгоритм этой сортировки таков:
    fori = 2 to n
    x = a(i)
    находим место среди а(1)…а(i) для включения х
    nexti
    Алгоритм сортировки методом прямо-
    го включения без барьера
    for i = 2 to n
    x = a(i)
    for j = i - 1downto1
    if x < a(j)
    then a( j + 1) = a(j)
    else go to L
    endif
    next j
    L: a( j + 1) = x
    next i
    return
    Недостатком приведенного алгоритма яв- ляется нарушение технологии структурно- го программирования, при которой неже- лательно применять безусловные перехо- ды. Если же внутренний цикл организо- вать как цикл while , то необходима по- становка «барьера», без которого при отрицательных значениях ключей проис- ходит потеря значимости и «зависание» компьютера.
    Алгоритм сортировки методом прямо-
    го включения с барьером
    for i = 2 to n
    x = a(i)
    a(0) = x {a(0) - барьер}
    j = i - 1
    while x < a(j ) do
    a( j +1) = a(j )
    j = j - 1
    endwhile
    a( j +1) = x
    nexti
    return
    Эффективность
    Минимальные оценки числа сравнений
    Cminи перемещений Mmin встречаются в случае уже упорядоченной исходной по- следовательности элементов, наихудшие же оценки Сmax и Mmax- когда они пер- воначально расположены в обратном по- рядке.
    Количество сравнений в худшем случае, когда массив отсортирован противопо- ложным образом,
    Сmax = n(n - 1)/2, то есть порядок
    О (n2). Количество перестановок
    Mmax = Cmax + 3(n-1), то есть порядок
    О (n2). Если же массив уже отсортиро- ван, то число сравнений и перестановок минимально: Cmin = n-1; Mmin = 3(n-
    1).
    6. ПОНЯТИЕ СПИСКОВОЙ СТРУКТУРЫ.
    СТЕК.
    К полустатическим структурам данных относят стеки, деки и очереди.
    Списки
    Это набор связанных элементов данных, которые в общем случае могут быть раз- ного типа.
    Пример списка:
    Е
    1
    ,
    Е
    2
    ,......... Е
    n
    ,... n> 1 и не зафиксиро- вано.
    Количество элементов списка может ме- няться в процессе выполнения програм- мы. Различают 2 вида списков:
    1) Несвязные
    2) Связные
    В несвязных списках связь между эле- ментами данных выражена неявно. В связных списках в элемент данных зано- сится указатель связи с последующим или предыдущим элементом списка.
    Стеки, деки и очереди - это несвязные списки. Кроме того, они относятся к по- следовательным спискам, в которых не- явная связь отображается их последова- тельностью.
    Стеки
    Очередь вида LIFO (LastInFirstOut - По- следним пришел, первым ушел), при ко- торой на обслуживание первым выбира- ется тот элемент очереди, который по- ступил в нее последним, называется сте- ком. Это одна из наиболее употреб- ляемых структур данных, которая оказы- вается весьма удобной при решении раз- личных задач.
    В силу указанной дисциплины обслужи- вания, в стеке доступна единственная его позиция, которая называется верши- ной стека - это позиция, в которой нахо- дится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам на- ходится в вершине стека. Выбрать эле- мент можно только из вершины стека; при этом выбранный элемент исключает- ся из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранный из него элементом
    (структура с ограниченным доступом данным).
    Графически стек можно представить сле- дующим образом:
    Рис. 2.12
    Первый элемент заносится вниз стека .
    Выборка из стека осуществляется с вер-
    шины, поэтому стек является структурой с ограниченным доступом
    Операции, производимые над стека-
    ми:
    1. Занесение элемента в стек.
    Push(S,x), где S - идентификатор стека, x - заносимый элемент.
    2. Выборка элемента из стека.
    Pop(S)
    3. Определение пустоты стека.
    Empty(S)
    4. Прочтение элемента без его выборки из стека.
    StackTop(S)
    5. Определение переполнения стека (для полустатических структур)
    Full(S)
    i = указательвершины
    Push(S,x)
    i = i+1
    S(i) = x return
    Pop(S)
    x = S(i) i = i -1 return
    Empty(S)
    if i = 0 then ―пусто‖
    Stop return endif
    Full(S)
    if i = maxS then ―переполнение‖
    Stop return endif
    StackTop(S)
    x = S(i) return
    Pop(S) if i = 0 then ―пусто‖
    Stop return endif
    X = S(i) i = i -1 return
    Empty(S)
    if i = 0 then empty = true else empty = false endif return
    Pop(S)
    Empty(S) if empty = true then ―пусто‖
    Stop return endif x = S(i) i = i -1 return
    Push(S,i)
    if i = maxS then ―переполнение‖
    Stop return endif i = i+1
    S(i) = x return
    7. ОЧЕРЕДЬ.
    Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются зака- зы на то или иное обслуживание. В про- граммировании имеется структура дан- ных, которая называется очередью. Эта структура данных используется напри- мер, для моделирования реальных оче- редей с целью определения их характе- ристик при данном законе поступления заказов и дисциплине их обслуживания.
    По своему существу очередь является полустатической структурой - с течением времени и длина очереди, и состав могут изменяться.
    На рис. 2. 13 приведена очередь, содер- жащая четыре элемента — А, В, С и D.
    Элемент А расположен в начале очереди, а элемент D — в ее конце. Элементы мо- гут удаляться только из начала очереди, то есть первый помещаемый в очередь элемент удаляется первым. По этой при- чине очередь часто называют списком, организованным по принципу «первый размещенный первым удаляется» в про- тивоположность принципу стековой ор- ганизации — «последний размещенный первым удаляется».
    Дисциплину обслуживания, в которой заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди), называется FIFO
    (FirstInFirstOut - Первым пришел, первым ушел). Очередь открыта с обеих сторон.
    Таким образом, изъятие компонент про- исходит из начала очереди, а запись - в конец. В этом случае вводят два ука- зателя: один - на начало очереди, вто- рой - на ее конец.
    Реальная очередь создается в памяти
    ЭВМ в виде одномерного массива с ко- нечным числом элементов, при этом не- обходимо указать тип элементов очере- ди, а также необходима переменная в работе с очередью.
    Физически очередь занимает сплошную область памяти и элементы следуют друг за другом, как в последовательном спи- ске.
      1   2   3   4   5   6


    написать администратору сайта