Конспект лекций Губарь (839213), страница 7
Текст из файла (страница 7)
Такдвумерный массив, обычно называемый матрицей и представленный в видетаблицы 1.2, состоит из трех одномерных массивов, в каждом из которых почетыре компоненты.Т а б л и ц а 1.2Двумерный массив1231234a11a21a31a12a22a32a13a23a33a14a24a34В этой таблице 34 три строки и четыре столбца. Любой из двенадцатиэлементов такого массива представляется в виде aij, где первый индекс iуказывает номер строки таблицы и изменяется от одного до трех, а второйиндекс j – номер столбца и изменяется от одного до четырех.
На пересеченииопределенныхстрокиистолбцавклеткетаблицыинаходитсясоответствующая компонента. Этот двумерный массив можно было бытрактовать и несколько иначе: он состоит из четырех одномерных массивов, вкаждом из которых по три элемента. Все зависит от того, как мы будем«просматривать» таблицу: по строкам или по столбцам. Важно, что в обоихслучаях наш массив содержит 12 компонент.Запись является неоднородной упорядоченной статической структуройпрямогодоступа,используемойдляхранениялогическисвязаннойинформации. Она представляет собой набор, как правило, разнотипныхполей, объединенных общим именем, которые могут идентифицироватьсяили адресоваться как по имени записи, так и по именам полей.
При работе ссовокупностью записей имя поля состоит из двух частей (имя записи, а такжесобственное имя этого поля), то есть является составным. В терминологиибаз данных запись и поля иногда определяют как кортеж и атрибутысоответственно. По сравнению с массивом запись можно считать болееуниверсальным типом структурированных данных, поскольку она являетсянеоднородной структурой.
С другой стороны, массив – более гибкаяструктура, поскольку индексы его элементов можно вычислять, а именаполей записи – нельзя.Принципиально иным типом структурированных данных являетсямножество,котороетрактуетсявматематикекакнеупорядоченнаясовокупность неповторяющихся объектов. Над множествами определеныследующиеоперации:проверкапринадлежностиэлементаданномумножеству, объединение множеств (аналог операции сложения), пересечениемножеств (операция умножения) и теоретико-множественная разность(вычитание множеств). Следует отметить, что размер множества заранее нефиксируется, хотя обычно ограничивается конкретной компьютернойреализацией (например, в нем может содержаться не больше, чем 255элементов).Крометого,доступклюбомуэлементумножестваосуществляется единственным путем: проверкой его принадлежностиданному множеству.Теперьперейдемкрассмотрениюболеесложныхтиповструктурированных данных и начнем с файлов или очередей, но сначала нампридется уточнить само понятие «файл».Дело в том, что этот распространенный термин применяется винформатике в различных смыслах.
Первоначально им стали обозначатьпоследовательный набор данных, а также команд, то есть программу,хранящихся на внешних носителях, основными из которых в то время быламагнитная лента. Но в английском языке это слово имеет несколько значений:архив, картотека, комплект, очередь, подшитые бумаги, ряд и т.д.
В данномслучае мы идентифицируем файл с понятием очереди.Итак, очередь – это однородная линейно упорядоченная динамическаяструктурапоследовательногодоступа,благодарячемусущественноезначение приобретает так называемая дисциплина обслуживания очереди.Естественно предложить два варианта пополнения очереди компонентами(записи) и их извлечения (чтения) из очереди. В первом случае новыйэлемент добавляется в «хвост», а считывание компонентов осуществляется сголовы очереди. Это соответствует принципу «первым пришел – первымобслужен» (английская аббревиатура FIFO – «first-in, first-out»). Во второмслучае новый элемент также добавляется, конечно, в «хвост», нообслуживание очереди начинается именно с него, то есть первая компонентаочереди «выходит» из нее последней. Другими словами, при этомреализуется принцип «последним пришел – первым обслужен» или LIFO –«last-in, first-out».
Структура, в которой реализован последний вариантобслуживания, называется стеком или магазином (по аналогии с магазиномстрелкового оружия), поэтому структуру, соответствующую первому случаю,иногда называют обратным магазином.До сих пор мы рассматривали сложные структуры, элементы которых, вопределенном смысле, были равноправны. Однако часто специфика задачитребует использования данных, которые связаны между собой отношениемподчинения. Хорошим примером такой структуры является генеалогическоедерево, корень которого – имя конкретного человека, на следующем уровнерасполагаются имена его родителей, затем – имена родителей его родителей ит.д.
Описанная структура представляет собой двоичное дерево, поэтомуподобные структуры данных называются древовидными или иерархическими.Список также является примером подобного рода структур, в нем кромесобственно данных хранятся и адреса элементов, поэтому любой элементсписка состоит из информационной и адресной частей. Первая частьсодержит данные, вторая – указатели на следующие элементы. Списокпредставляет собой основную конструкцию языка Лисп (это названиепроисходит от английского Lisp, list processing – обработка списков). Онявляется упорядоченной последовательностью, элементами которой могутбыть как простейшие данные, называемые в Лиспе атомами, так и другиесписки или подсписки. Эта структура данных позволяет представлятьиерархическую связь с помощью системы строго соответствующих другдругу открывающих и закрывающих скобок или с использованиемопределенной точечной нотации. Благодаря этому списки являются основнымсредством представления знаний, например, с помощью вложенных списковможно записать анкетные данные любого человека.Наконец, следует отметить, что некоторые языки программированияпозволяютобразовыватьизрассмотренныхструктурразнообразныесуперпозиции, то есть совмещать их.
Например, такая суперпозиция какфайл записей обычно используется при формировании баз данных и работе сними.Контрольные вопросы1. Как осуществляется восприятие информации человеком?2. Что характеризует совокупность свойств информации?3. Что понимается под информационным сообщением?4.
Какие существуют уровни рассмотрения сообщений?5. Что такое тезаурус и как его объем влияет на количествовоспринимаемой человеком информации?6. Что такое дезинформация?7. Что является минимальным количеством информации?8. Как принцип дихотомического деления можно использовать припоиске информации?9. Какие коэффициенты используются при переходе от одной единицыизмерения информации к другой?10.Как определяется вероятность события, наступившего в результатенекоторого эксперимента?11.Как энтропия связана с неопределенностью ситуации?12.Почемулогарифмическаяфункцияпринимаетсязамерунеопределенности опыта?13.Чем структурный подход к измерению количества информацииотличается от статистического подхода?14.Что такое условная энтропия?15.Чем данные отличаются от информации?16.Что такое числа конечной точности?17.Как можно классифицировать структурированные данные?18.Почему двумерный массив обычно называется матрицей?19.Какие существуют дисциплины обслуживания очередей?20.Что хранит любой элемент списка?21.Что такое суперпозиция структур данных?2.
Числа в компьютере и действия над ними2.1. Непозиционные и позиционные системы счисленияС давних времен люди выполняли элементарные подсчёты, связанные сжитейскими потребностями. Наиболее древние числительные, к которымможно отнести один, два, пять, десять, двадцать, видимо, связаны с самымиестественными счётными приспособлениями – пальцами рук и ног.В древнем Египте стали использоваться привычные для нас числовыекомпоненты – единицы, десятки, сотни и тысячи, а числа, обозначаемыеиероглифами, представлялись в виде суммы стандартных слагаемых.Древнеримскаясистема,построеннаяпотакомужепринципу,представляет собой более сложную модель, в которой используютсяследующие обозначения:1 = I, 5 = V, 10 = X, 50 = L, 100 = C, 500 = D, 1000 = M.Если меньшее число расположено справа,то оно увеличивает значениепредыдущего слагаемого, а если слева – то уменьшает.
Например,МСМХLVI = 1000+900+40+5+1 = 1946.Запись чисел не очень сложна,но арифметические действия вдревнеримской системе выполнять весьма затруднительно. В настоящеевремя она иногда используется для представления натуральных чисел.Под системой счисления можно понимать искусственный язык,специальнопредназначенныйдляпредставлениячисел.Различаютнепозиционные и позиционные системы счисления. В непозиционныхсистемах,ккоторымотносятсяупомянутыедревнеегипетскаяидревнеримская системы, значение каждой цифры в изображении числа независит от позиции, которую эта цифра занимаетпозиционных – зависит.в записи числа, вДревнейшая из известных нам позиционных систем счисления –вавилонская шестидесятеричная система, основание которой равно 60, тоесть одна и та же цифра (а всего их 60) в последующем (левом) разрядезначит в 60 раз больше, чем в предыдущем.
В дальнейшем древниевавилоняне упростили свою систему, перейдя к двенадцатеричной системесчисления. Поскольку они обладали большими познаниями в областиастрономии, так ими было вычислено движение всех пяти известных тогдапланет солнечной системы, то, вероятно поэтому, отголоски их системсчисления дошли до наших дней. Ведь в году у нас 12 месяцев, а не 10,циферблат часов содержит 12 чисел, в одном часе 60 минут и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
