Загрузка...
Учебная работа. Контрольная работа: Информационные данные
Оглавление:
Введение. 2
ТЕОРЕТИЧЕСКАЯ часть. 2
1.
Информация и данные. 2
2.
Систематизация структур данных. 2
3.
Главные структуры данных. 2
Обыкновенные структуры данных. 2
Статические структуры данных. 2
Полустатические структуры данных. 2
Динамические структуры данных. 2
Нелинейные структуры данных. 2
Заключение. 2
ПРАКТИЧЕСКАЯ часть. 2
Общая черта задачки. 2
Описание метода решения задачки. Ошибка! способности работы, сведения о окружающем нас мире, т.е. собирало информацию. Вначале информация передавалась из поколения в поколение в виде преданий и устных рассказов. Появление и развитие книжного дела позволило передавать и хранить информацию в наиболее надежном письменном виде. Открытия в области электро энергии привели к возникновению телеграфа, телефона, радио, телевидения — средств, позволяющих оперативно передавать и копить информацию. Развитие прогресса определило резкий рост инфы, в связи, с чем вопросец о её сохранении и переработке становился год от года острее. С возникновением вычислительной техники значительно упростились методы хранения, а основное, обработки инфы. Развитие вычислительной техники на базе процессоров приводит к совершенствованию компов и программного обеспечения. Появляются программки, способные обработать огромные потоки инфы. При помощи таковых программ создаются информационные системы. Целью хоть какой информационной системы является обработка данных о объектах и явлениях настоящего мира и предоставление подходящей человеку информации о их.
В данной работе рассматривается что такое информация и данные, чем они различаются; как информация перебегает в структурированные данные. Рассматриваются такие понятия, как «тип данных», «структура данных», «модель данных» и «база данных». В главный части работы приводится систематизация структур данных, широкая информация о физическом и логическом представлении структур данных всех классов памяти ЭВМ : обычных, статических, полустатических, динамических и нелинейных; также, информация о вероятных операциях над всеми перечисленными структурами.
ТЕОРЕТИЧЕСКАЯ часть
Информация и данные
В информатике различают два понятия «данные» и «информация». Данные представляют собой информацию, находящуюся в формализованном виде и созданную для обработки техническими системами. Под информацией понимается совокупа представляющих энтузиазм фактов, событий, явлений, которые нужно зарегистрировать и обработать. информация в отличие от данных – это то, что нам любопытно, что можно хранить, копить, использовать и передавать. Данные лишь хранятся, а не употребляются. Но как данные начинают употребляться, то они преобразуются в информацию. В процессе обработки информация меняется по структуре и форме. Признаками структуры является связь частей инфы. структура инфы классифицируется на формальную и содержательную. Формальная структура инфы нацелена на форму представления инфы, а содержательная – на содержание.
Виды форм представления инфы:
1. По способу отображения:
символьная (знаки, числа, буковкы); графическая (изображения); текстовая (набор букв, цифр) и звуковая.
2. По месту возникновения
: внутренняя (выходная) и наружная (входная)
3. По стабильности
: неизменная и переменная
4. По стадии обработки
: первичная и вторичная.
сейчас можно отдать наиболее конкретное определение данных на машинном уровне представления инфы. Независимо от содержания и трудности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, либо битов, а их значениями являются надлежащие двоичные числа. Для человека обрисовывать и изучить сколько-либо сложные данные в определениях последовательностей битов очень неловко. Наиболее большие и содержательные, нежели бит, «строй блоки» для организации случайных данных получаются на базе понятия «структуры данного».
систематизация структур данных
Структуры данных служат материалами, из которых строятся программки. Как правило, данные имеют форму чисел, букв, текстов, знаков и наиболее сложных структур типа последовательностей, списков и деревьев.
Для четкого описания абстрактных структур данных и алгоритмов программ употребляются такие системы формальных обозначений, именуемые языками программирования, в каких смысл всякого предложения обусловится буквально и совершенно точно. Посреди средств, представляемых практически всеми языками программирования, имеется возможность ссылаться на элемент данных, пользуясь присвоенным ему именованием. Выбор правильного представления данных служит ключом к удачному программированию и может в основном сказываться на производительности программки, чем детали применяемого метода. Навряд ли когда-нибудь покажется общая теория выбора структур данных.
Под
в общем случае соображают огромное количество частей данных и огромное количество связей меж ними. Такое определение обхватывает все вероятные подходы к структуризации данных, но в каждой определенной задачке употребляются те либо другие его нюансы. Потому вводится доборная систематизация структур данных, направления которой соответствуют разным нюансам их рассмотрения. До этого чем приступать к исследованию определенных структур данных, дадим их общую систематизацию по нескольким признакам.
отражает метод физического представления данных в памяти машинки и именуется еще
,
либо
.
Рассмотрение структуры данных без учета её представления в машинной памяти именуется
либо
. В общем случае меж логической и соответственной ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в какой она обязана быть отражена. Вследствие этого различия есть процедуры, осуществляющие отображение логической структуры в физическую и напротив. Эти процедуры обеспечивают доступ к физическим структурам и выполнение над ними разных операций.
Различаются обыкновенные (базисные, примитивные) структуры (типы) данных и встроенные (структурированные, композитные, сложные).
именуются такие структуры данных, которые не могут быть расчленены на составные части, огромные, чем биты.
именуются такие структуры данных, составными частями которых являются остальные структуры данных — обыкновенные либо в свою очередь встроенные. Встроенные структуры данных конструируются программером с внедрением средств интеграции данных, предоставляемых языками программирования.
Зависимо от отсутствия либо наличия очевидно данных связей меж элементами данных следует различать
(векторы, массивы, строчки, стеки, очереди) и
(связные списки).
Очень принципиальный признак структуры данных — её изменчивость — изменение числа частей либо связей меж элементами структуры. По признаку изменчивости различают структуры
,
и
. систематизация структур данных по признаку изменчивости приведена на рис. 1.
Рис. 1.
систематизация структур данных
Базисные структуры данных, статические, полустатические и динамические свойственны для оперативки и нередко именуются
. Файловые структуры соответствуют структурам данных для наружной памяти.
2-ой принципиальный признак структуры данных — нрав упорядоченности её частей. По этому признаку структуры можно разделять на
. Зависимо от нрава обоюдного расположения частей в памяти, линейные структуры можно поделить на
(векторы, строчки, массивы, стеки, очереди) и
(односвязные, двусвязные списки). Пример нелинейных структур — многосвязные списки, деревья, графы.
В языках программирования понятие «структуры данных» тесновато соединено с понятием «типы данных». Любые данные, т.е. константы, переменные, значения функций либо выражения, характеризуются своими типами.
информация по любому типу совершенно точно описывает:
1) структуру хранения данных обозначенного типа, т.е. выделение памяти и иной;
2) огромное количество допустимых значений, которые может иметь тот либо другой объект описываемого типа;
3) огромное количество допустимых операций, которые применимы к объекту описываемого типа.
Главные структуры данных
Обыкновенные структуры данных
именуют также простыми либо базисными структурами. Эти структуры служат основой для построения наиболее сложных структур. В языках программирования обыкновенные структуры описываются ординарными (базисными) типами. К таковым типам относятся:
. В предстоящем изложении мы будем ориентироваться на язык PASCAL. Структура обычных типов PASCAL приведена на рис 2.1
(через запятую указан размер памяти в б, требуемый для размещения данных соответственного типа). В остальных языках программирования набор обычных типов может несколько различаться от обозначенного.
Рис. 2.
Структура обычных типов PASCAL
Числовые типы
При помощи целых чисел быть может представлено количество объектов, являющихся дискретными по собственной природе (т.е. счетное число объектов).
В отличии от порядковых типов (все целые, символьный, логический), значения которых постоянно сопоставляются с рядом целых чисел и, как следует, представляются в памяти машинки полностью буквально,
Битовые типы
В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Почаще всего такие задачки появляются в системном программировании, когда, к примеру, отдельный разряд связан с состоянием отдельного аппаратного переключателя либо отдельной шины передачи данных и т.п. Данные такового типа представляются в виде набора битов, упакованных в байты либо слова, и не связанных вместе. Операции над таковыми данными обеспечивают доступ к избранному биту данного.
Логические типы
Значениями логического типа BOOLEAN быть может одна из за ранее объявленных констант false (ересь) либо true (правда). Данные логического типа занимают один б памяти. При всем этом значению false соответствует нулевое
Символьный тип
Значением символьного типа char являются знаки из некого предопределенного огромного количества. В большинстве современных индивидуальных ЭВМ сиим обилием является ASCII (American Standard Code for Information Intechange — южноамериканский обычный код для обмена информацией). Это огромное количество состоит из 256 различных знаков, упорядоченных определенным образом и содержит знаки больших и строчных букв, цифр и остальных знаков, включая особые управляющие знаки. Допускается некие отличия от эталона ASCII, а именно, при наличии соответственной системной поддержки это огромное количество может содержать буковкы российского алфавита. б. Код от 0 до 255 в этом б задает один из 256 вероятных знаков ASCII таблицы.
Перечислимый тип
Перечислимый тип представляет собой упорядоченный тип данных, определяемый программером, т.е. программер перечисляет все значения, которые может принимать переменная этого типа. значения являются неповторяющимися в границах программки идентификаторами, количество которых не быть может больше 256.
Интервальный тип
один из методов образования новейших типов из уже имеющихся — ограничение допустимого спектра значений некого обычного скалярного типа либо рамок описанного перечислимого типа. Определяется заданием малого и наибольшего значений спектра. При всем этом меняется спектр допустимых значений по отношению к базисному типу, но адресок ячейки памяти. При программировании на низком уровне — в машинных кодах, на языке Ассемблера и на языке C, который специально нацелен на системных программистов, работа с адресами составляет значительную часть программных кодов. При решении прикладных задач с внедрением языков высочайшего уровня более нередкие случаи, когда программеру могут пригодиться указатели:
1) По мере необходимости представить одни и те же физические данные, как данные разной логической структуры.
2) При работе с динамическими структурами данных.
Статические структуры данных
Статические структуры относятся к уровню непримитивных структур, которые представляют собой структурированное огромное количество простых, базисных, структур. к примеру, вектор быть может представлен упорядоченным обилием чисел. Так как по определению статические структуры различаются отсутствием изменчивости, память для их выделяется автоматом — как правило, на шаге компиляции либо при выполнении — в момент активизации того программного блока, в каком они описаны. Выделение памяти на шаге компиляции является настолько комфортным свойством статических структур, что в ряде задач программеры употребляют их для представления объектов, владеющих изменчивостью. к примеру, когда размер массива неизвестен заблаговременно, для него резервируется очень вероятный размер.
Статические структуры в языках программирования соединены со структурированными типами. Структурированные типы в языках программирования являются теми средствами интеграции, которые разрешают строить структуры данных сколь угодно большенный трудности. К таковым типам относятся: массивы, записи (в неких языках — структуры) и огромного количества (этот тип реализован не во всех языках).
Векторы
Вектор (одномерный массив) — структура данных с фиксированным числом частей 1-го и такого же типа. Любой элемент вектора имеет неповторимый в рамках данного вектора номер. Воззвание к элементу вектора производится по имени вектора и номеру требуемого элемента.
Массивы
Логическая структура.
Массив — таковая структура данных, которая характеризуется: фиксированным набором частей 1-го и такого же типа; любой элемент имеет неповторимый набор значений индексов; количество индексов определяют мерность массива (два индекса — двумерный массив, три индекса — трехмерный массив, один индекс — одномерный массив либо вектор); воззвание к элементу массива производится по имени массива и значениям индексов для данного элемента. Иными словами, массив — это вектор, любой элемент которого — вектор.
Физическая структура
— это размещение частей массива в памяти ЭВМ . Для варианта двумерного массива, состоящего из
строк и
столбцов физическая структура представлена на рис. 3.
Рис. 3.
Физическая структура двумерного массива из (k1-n1+1) строк и (k2-n2+1) столбцов
Многомерные массивы
хранятся в непрерывной области памяти. Размер слота определяется базисным типом элемента массива. количество частей массива и размер слота определяют размер памяти для хранения массива. Принцип распределения частей массива в памяти определен языком программирования. Так в FORTRAN элементы распределяются по столбцам — так, что резвее изменяется левые индексы, в PASCAL — по строчкам — изменение индексов производится в направлении справа влево.
Особые массивы.
На практике встречаются массивы, которые в силу определенных обстоятельств могут записываться в память не вполне, а отчасти. Это в особенности животрепещуще для массивов так огромных размеров, что для их хранения в полном объёме памяти быть может недостаточно. К таковым массивам относятся
и
.
Симметричные массивы.
Двумерный массив, в каком количество строк равно количеству столбцов именуется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, именуется симметричной.
Разреженные массивы.
Разреженный массив — массив, большая часть частей которого равны меж собой, так что хранить в памяти довольно только маленькое число значений хороших от основного (фонового) значения других частей. Различают два типа разреженных массивов:
1) массивы, в каких местоположения частей со значениями хорошими от фонового, могут быть математически описаны;
2) массивы со случайным расположением частей.
Огромного количества
Логическая структура:
Огромное количество — таковая структура, которая представляет собой набор неповторяющихся данных 1-го и такого же типа. Огромное количество может принимать все значения базисного типа. Базисный тип не должен превосходить 256 вероятных значений. Потому базисным типом огромного количества могут быть byte, char и производные от их типы.
Физическая структура:
Огромное количество в памяти хранится как массив битов, в каком любой бит показывает является ли элемент принадлежащим объявленному огромному количеству либо нет. Т.о. наибольшее число частей огромного количества 256, а данные типа огромное количество могут занимать не наиболее 32-ух б.
Числовые огромного количества.
Обычный числовой тип, который быть может базисным для формирования огромного количества — тип byte.
Символьные огромного количества.
Символьные огромного количества хранятся в памяти также как и числовые огромного количества. Разница только в том, что хранятся не числа, а коды ASCII знаков.
Огромное количество из частей перечислимого типа.
Огромное количество, базисным типом которого есть перечислимый тип, хранится также, как огромное количество, базисным типом которого является тип byte. Но, в памяти занимает пространство, которое зависит от количества частей в перечислимом типе.
Огромное количество от интервального типа.
Огромное количество, базисным типом которого есть интервальный тип, хранится также, как огромное количество, базисным типом которого является тип byte. В памяти занимает пространство, которое зависит от количества частей, входящих в объявленный интервал.
Записи
Запись — конечное упорядоченное огромное количество полей, характеризующихся разным типом данных. Полями записи могут быть встроенные структуры данных — векторы, массивы, остальные записи. Записи являются очень комфортным средством для представления программных моделей настоящих объектов предметной области, обычно, любой таковой объект владеет набором параметров, характеризуемых данными разных типов.
Таблицы
Таблица — непростая встроенная структура. С физической точки зрения таблица представляет собой вектор, элементами которого являются записи. Логической индивидуальностью таблиц будет то, что доступ к элементам таблицы делается не по номеру (индексу), а по ключу — по значению 1-го из параметров объекта, описываемого записью-элементом таблицы.
— это свойство, идентифицирующее данную запись во огромном количестве однотипных записей. Ключ может врубаться в состав записи и быть одним из её полей, но может и не врубаться в запись, а рассчитываться по положению записи. Таблица может иметь один либо несколько ключей. Главный операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Так как поиск быть может существенно наиболее действенным в таблицах, упорядоченных по значениям ключей, достаточно нередко над таблицами нужно делать операции сортировки.
Время от времени различают таблицы с фиксированной и с переменной длиной записи. Разумеется, что таблицы, объединяющие записи совсем схожих типов, будут иметь фиксированные длины записей. Таблицы с записями переменной длины обрабатываются лишь поочередно — в порядке возрастания номеров записей.
Полустатические структуры данных
Полустатические структуры данных характеризуются последующими признаками: они имеют переменную длину и обыкновенные процедуры её конфигурации; изменение длины структуры происходит в определенных границах, не превышая какого-то наибольшего (предельного) значения.
Если полустатическую структуру разглядывать на логическом уровне, то о ней можно сказать, что это последовательность данных, сплетенная отношениями линейного перечня. Доступ к элементу может осуществляться по его порядковому номеру. Физическое одной стороны перечня, именуемого верхушкой стека. Используются и остальные наименования стека — магазин и очередь, функционирующая по принципу LIFO (Last — In — First- Out — «крайним пришел — первым вышел»).
Главные операции над стеком — включение новейшего и исключение элемента из стека. Полезными могут быть также вспомогательные операции: определение текущего числа частей в стеке и чистка стека. Некие создатели разглядывают также операции включения/исключения частей для середины стека, но структура, для которой вероятны такие операции, не соответствует стеку по определению.
Для наглядности разглядим маленькой пример, демонстрирующий принцип включения частей в стек и исключения частей из стека. На рис. 4.1 (а, б ,с) изображены состояния стека:
а) пустого;
б, в, г) опосля поочередного включения в него частей с именами ‘A’, ‘B’, ‘C’;
д, е) опосля поочередного удаления из стека частей ‘C’ и ‘B’;
ж) опосля включения в стек элемента ‘D’.
Рис. 4.
Включение и исключение частей из стека
Как видно из рис.
4
, стек можно представить, к примеру, в виде стопки книжек (частей), лежащей на столе. Присвоим каждой книжке свое заглавие, к примеру A,B,C,D… Тогда в момент времени, когда на столе книжек нет, про стек аналогично можно сказать, что он пуст, т.е. не содержит ни 1-го элемента. Если же мы начнем поочередно класть книжки одну на другую, то получим стопку книжек (допустим, из
книжек), либо получим стек, в каком содержится
частей, при этом верхушкой его будет являться элемент
. Удаление частей из стека осуществляется аналогичным образом т. е. удаляется поочередно по одному элементу, начиная с верхушки, либо по одной книжке из стопки.
Очереди FIFO
Очередью FIFO (First — In — First- Out — «первым пришел — первым вышел») именуется таковой поочередный перечень с переменной длиной, в каком включение частей производится лишь с одной стороны перечня (эту сторону нередко именуют концом либо хвостом очереди), а исключение — с иной стороны (именуемой началом либо головой очереди).
Главные операции над очередью — те же, что и над стеком — включение, исключение, определение размера, чистка, неразрушающее чтение.
Деки
Дек — особенный вид очереди. Дек (от англ. deq — double ended queue, т.е очередь с 2-мя концами) — это таковой поочередный перечень, в каком как включение, так и исключение частей может осуществляться с хоть какого из 2-ух концов перечня. Личный вариант дека — дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека подобны логической и физической структуре круговой FIFO-очереди. Но, применительно к деку целенаправлено гласить не о начале и конце, а о левом и правом конце.
Операции над деком: включение элемента справа, слева; исключение элемента справа, слева; определение размера; чистка.
Строчки
Строчка — это линейно упорядоченная последовательность знаков, принадлежащих конечному огромному количеству знаков, именуемому алфавитом. Строчки владеют последующими необходимыми качествами: их длина, как правило, переменна, хотя алфавит фиксирован; обычно воззвание к символам строчки идет с какого-либо 1-го конца последовательности, т.е принципиальна упорядоченность данной для нас последовательности, а не её индексация; в связи с сиим свойством строчки нередко именуют также цепочками; почаще всего целью доступа к строке является не отдельный её элемент (хотя это тоже не исключается), а некая цепочка знаков в строке.
Говоря о строчках, обычно имеют в виду текстовые строчки — строчки, состоящие из знаков, входящих в алфавит какого-нибудь избранного языка, цифр, символов препинания и остальных служебных знаков.
Базисными операциями над строчками являются: определение длины строчки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения.
Операция определения длины строчки имеет вид функции, возвращаемое
Динамические структуры данных
Динамические структуры по определению характеризуются отсутствием физической смежности частей структуры в памяти непостоянством и непредсказуемостью размера (числа частей) структуры в процессе её обработки. Для установления связи меж элементами динамической структуры употребляются указатели, через которые инсталлируются очевидные связи меж элементами. Такое структура; в общем случае информационное поле само является встроенной структурой — вектором, массивом, записью и т.п.;
2. поле связок, в каком содержатся один либо несколько указателей, связывающий данный элемент с иными элементами структуры;
Когда связное задачки, для конечного юзера «видимым» делается лишь содержимое информационного поля, а поле связок употребляется лишь программистом-разработчиком.
Плюсы связного представления данных: в способности обеспечения значимой изменчивости структур; размер структуры ограничивается лишь легкодоступным объёмом машинной памяти; при изменении логической последовательности частей структуры требуется не перемещение данных в памяти, а лишь корректировка указателей.
вкупе с тем связное правило, наиболее высочайшей квалификации от программера; на поля связок расходуется доборная память; доступ к элементам связной структуры быть может наименее действенным по времени.
Крайний недочет является более серьёзным и конкретно им ограничивается применимость связного представления данных.
Связные линейные списки.
Перечнем именуется упорядоченное огромное количество, состоящее из переменного числа частей, к которым применимы операции включения, исключения. Перечень, отражающий дела соседства меж элементами, именуется
. Если ограничения на длину перечня не допускаются, то перечень представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных. Графически связи в перечнях комфортно изображать при помощи стрелок.
На рис. 5.1
приведена структура односвязного перечня. На нем поле INF — информационное поле, данные, NEXT — указатель на последующий элемент перечня. Любой перечень должен иметь особенный элемент, именуемый указателем начала перечня, который по формату отличен от других частей. В поле указателя крайнего элемента перечня находится особый признак
, свидетельствующий о конце перечня.
Рис. 5.1.
Структура односвязного перечня
Но, обработка односвязного перечня не постоянно комфортна, потому что отсутствует возможность продвижения в обратную сторону. Такую возможность обеспечивает
, любой элемент которого содержит два указателя: на последующий и предшествующий элементы перечня. структура линейного двухсвязного перечня приведена на рис. 5.2, где поле NEXT — указатель на последующий элемент, поле PREV — указатель на предшествующий элемент. В последних элементах надлежащие указатели должны содержать
, как и показано на рис. 5.2.
Для удобства обработки перечня добавляют еще один особенный элемент — указатель конца перечня. наличие 2-ух указателей в любом элементе усложняет перечень и приводит к доп затратам памяти, но в то же время обеспечивает наиболее действенное выполнение неких операций над перечнем.
Рис. 5.2.
структура двухсвязного перечня
Разновидностью рассмотренных видов линейных списков является круговой перечень, который быть может организован на базе как односвязного, так и двухсвязного списков. При всем этом в односвязном перечне указатель крайнего элемента должен указывать на 1-ый элемент; в двухсвязном перечне в первом и крайнем элементах надлежащие указатели переопределяются, как показано на рис.5.3.
При работе с таковыми перечнями несколько упрощаются некие процедуры, выполняемые над перечнем. Но, во время просмотра такового перечня следует принять неких мер предосторожности, чтоб не попасть в нескончаемый цикл.
Рис. 5.3.
структура кругового двухсвязного перечня
Линейные списки находят обширное применение в приложениях, где непредсказуемы требования на размер памяти, нужной для хранения данных; огромное число сложных операций над данными, в особенности включений и исключений. На базе линейных списков могут строится стеки, очереди и деки. один из указателей всякого элемента перечня задает порядок оборотный к порядку, устанавливаемому иным указателем, то таковой двусвязный перечень будет линейным. Если же один из указателей задает порядок случайного вида, не являющийся оборотным по отношению к порядку, устанавливаемому иным указателем, то таковой перечень будет нелинейным.
В обработке нелинейный перечень определяется как неважно какая последовательность атомов и списков (подсписков), где в качестве атома берется хоть какой объект, который при обработке различается от перечня тем, что он структурно неразделим.
Нелинейные структуры данных
Графы
Граф — это непростая нелинейная многосвязная динамическая структура, отображающая характеристики и связи сложного объекта.
Многосвязная структура владеет последующими качествами: на любой элемент (узел, верхушку) быть может случайное количество ссылок; любой элемент может иметь связь с хоть каким количеством остальных частей; любая связка (ребро, дуга) может иметь направление и вес.
В узлах графа содержится информация о элементах объекта. Связи меж узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они именуются
, ребра без стрелок —
.
Граф, все связи которого направленные, именуется
либо
; граф со всеми неориентированными связями —
; граф со связями обоих типов —
. Примеры изображений графов даны на рис. 6
.
а). ((A,B),(B,A)) б). (< A,B >,< B,A >).
Рис.6.
Граф неориентированный (а) и направленный (б).
Для нацеленного графа число ребер, входящих в узел, именуется
узла, выходящих из узла —
. количество входящих и выходящих ребер быть может хоть каким, в том числе и нулевым. Граф без ребер является
. Если ребрам графа соответствуют некие значения, то граф и ребра именуются
.
именуется граф, имеющий параллельные (соединяющие одни и те же верхушки) ребра, в неприятном случае граф именуется
.
Путь в графе — это последовательность узлов, связанных ребрами; простым именуется путь, в каком все ребра различны, обычным именуется путь, в каком все верхушки различны. Путь от узла к себе именуется циклом, а граф, содержащий такие пути —
.
Два узла графа смежны, если существует путь от 1-го из их до другого. Узел именуется инцидентным к ребру, если он является его верхушкой, т.е. ребро ориентировано к этому узлу.
Логически структура-граф быть может представлена матрицей смежности либо матрицей инцидентности.
Деревья
Дерево — это граф, который характеризуется последующими качествами:
1. Существует единственный элемент (узел либо верхушка), на который не ссылается никакой иной элемент — и который именуется
(рис. 7; 8 —
— корешки).
2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно выполнить доступ к хоть какому элементу структуры.
3. На любой элемент, не считая корня, имеется единственная ссылка, т.е. любой элемент адресуется единственным указателем.
рис. 7.
Дерево рис. 8.
Лес
Заглавие «дерево» проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи меж парой узлов дерева именуется обычно
. Те узлы, которые не ссылаются ни на какие остальные узлы дерева, именуются
либо терминальными верхушками (рис. 7; 8 —
— листья). Узел, не являющийся листом либо корнем, считается промежным либо
(нетерминальной либо внутренней верхушкой).
Деревья необходимы для описания хоть какой структуры с иерархией. Классические примеры таковых структур: генеалогические деревья, десятичная систематизация книжек в библиотеках, иерархия должностей в организации и т. д.
во — это таковой ациклический орграф (направленный граф), у которого одна верхушка, именуемая корнем, имеет полустепень захода, равную 0, а другие — полустепени захода, равные 1. Направленное дерево обязано иметь по последней мере одну верхушку. Изолированная верхушка также представляет собой направленное дерево.
Верхушка нацеленного дерева, полустепень финала которой равна нулю, именуется
(висящей)
либо листом; все другие верхушки дерева именуют верхушками ветвления. Длина пути от корня до некой верхушки именуется
(номером яруса) данной для нас верхушки. Уровень корня нацеленного дерева равен нулю, а уровень хоть какой иной верхушки равен расстоянию (т.е. модулю разности номеров уровней вершин) меж данной для нас верхушкой и корнем. Направленное дерево является ациклическим графом, все пути в нем тривиальны.
З
аключение
Структуры данных – это абстрактные структуры либо классы, которые употребляются для организации данных и предоставляют разные операции над этими данными.
В данной работе были описаны структуры данных всех классов памяти ЭВМ : обычных, статических, полустатических, динамических и нелинейных, также, информация о вероятных операциях над всеми перечисленными структурами. При помощи операций можно организовывать поиск, сортировку и редактирование данных. методы анализа эффективности использования структур данных важны для подсчета времени выполнения разных операций структур данных и являются полезным инвентарем при выбирании той либо другой структуры данных для определенной программистской задачки.
Мы разглядели вопросец о значимости структур данных и о том, как они влияют на эффективность алгоритмов. Выбор правильного представления данных служит ключом к удачному программированию и может в основном сказываться на производительности программки, чем детали применяемого метода. Для определения того, как структуры данных влияют на производительность программ, необходимо разглядеть, как можно строго проанализировать разные операции, выполняемые структурами данных. Навряд ли когда-нибудь покажется общая теория выбора структур данных.
Стоит добавить, что совокупа структур данных и операций их обработки составляет модель данных, которая является ядром хоть какой базы данных. Модель данных представляет собой огромное количество структур данных, ограничений целостности и операций манипулирования данными. При помощи модели данных могут быть представлены объекты предметной области и связи меж ними. База данных основывается на использовании иерархической, сетевой либо реляционной модели, на композиции этих моделей либо на неком их подмножестве.
ПРАКТИЧЕСКАЯ часть
Общая черта задачки
Разглядим последующую задачку.
Вариант 21
1. Выстроить таблицы по приведенным данным о доходах членов семьи (рис. 21.1, 21.2) и о расходах семьи (рис. 21.3) за квартал.
2. Заполнить таблицу на рис. 21.4 числовыми данными о доходах семьи за квартал, выполнив объединение по расположению данных.
3. Составить таблицу планирования бюджета семьи на квартал (рис. 21.5).
4. По данным о бюджете семьи на квартал (рис. 21.5) выстроить гистограмму.
Доходы Чижовой М.А. за 1 квартал 2006 г., руб.
Наименование доходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Заработная плата
4000
3000
2200
3200
Остальные поступления
—
500
—
1000
Сумма дохода за месяц
Рис. 21.1.
Доходы Чижовой М.А. за квартал
Доходы Чижова А.С. за 1 квартал 2006 г., руб.
Наименование доходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Заработная плата
7000
7000
7500
7400
Остальные поступления
1200
500
500
1000
Сумма дохода за месяц
Рис. 21.2.
Доходы Чижова А.С. за квартал
Расходы семьи Чижовых за 1 квартал 2006 г., руб.
Наименование расходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Коммунальные платежи
630
670
700
800
Оплата электроэнергии
100
100
120
120
Оплата телефонных счетов
195
195
195
195
Расходы на питание
2500
2500
2600
3000
Остальные расходы
1000
1000
1500
2000
Погашение кредита
4000
4000
4000
4000
Суммарный расход за месяц
Рис. 21.3.
Расходы семьи Чижовых за квартал
Доходы семьи Чижовых за 1 квартал 2006 г.
Наименование доходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Заработная плата
Остальные поступления
Суммарный Доход за месяц
Рис. 21.4.
Доходы семьи Чижовых за квартал
бюджет семьи Чижовых за 1 квартал 2006 г.
Наименование
Сентябрь
Октябрь
Ноябрь
Декабрь
Суммарный Доход за месяц
Суммарный расход за месяц
Остаток
Рис. 21.5.
бюджет семьи Чижовых за квартал
2. Практическая часть
Расмотрим последующую задачку:
1. Выстроить таблицы по приведенным данным о доходах членов семьи (табл. 1, 2) и о расходах семьи (табл. 3) за квартал.
Доходы Чижовой М. А. за 1 квартал 2006 г., руб.
Наименование доходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Заработная плата
4000
3000
2200
3200
Остальные поступления
-
500
-
1000
Сумма дохода за месяц
Таблица
1
Доходы Чижовой М. А. за квартал
Доходы Чижова А. С. за 1 квартал 2006 г., руб.
Наименование доходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Заработная плата
7200
7000
7500
7400
Остальные поступления
1200
500
500
1000
Сумма дохода за месяц
Таблица
2
Доходы Чижова А. С. за квартал
Расходы семьи Чижовых за 1 квартал 2006 г., руб.
Наименование расходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Коммунальные платежи
630
670
700
800
Оплата электроэнергии
100
100
120
120
Оплата телефонных счетов
195
195
195
195
Расходы на питание
2500
2500
2600
3000
Остальные расходы
1000
1000
1500
2000
Погашение кредита
4000
4000
4000
4000
Суммарный расход за месяц
Таблица
3
Расходы семьи Чижовых за квартал
2. Заполнить таблицу 4 числовыми данными о доходах семьи за квартал, выполнив консалидацию по расположению данных.
Доходы семьи Чижовых за 1 квартал 2006 г., руб.
Наименование доходов
Сентябрь
Октябрь
Ноябрь
Декабрь
Заработная плата
Остальные поступления
Сумма дохода за месяц
Таблица
4
Доходы семьи Чижовых за квартал
3. Составить таблицу планирования бюджета семьи на квартал (табл. 5).
Бюджет семьи Чижовых за 1 квартал 2006 г., руб.
Наименование
Сентябрь
Октябрь
Ноябрь
Декабрь
Суммарный Доход за месяц
Суммарный расход за месяц
Остаток
Таблица
5
бюджет семьи Чижовых за квартал
4. По данным о бюджете семьи на квартал (табл. 5) выстроить гистограмму.
1. Запустить табличный микропроцессор MS Excel.
2. Сделать книжку с именованием «Бюджет».
3. Лист 1 переименовать в лист с заглавием Доходы.
4. На рабочем листе Доходы
MSExcel сделать таблицы «Доходы Чижовой М. А. за квартал» и «Доходы Чижова А. С. за квартал».
5. Заполнить таблицы доходов начальными данными (рис. 2.1).
Набросок 2.
1
Размещение таблиц доходов
на рабочем листе Доходы
MS Excel
6. Лист 2 переименовать в лист с заглавием Расходы.
7. На рабочем листе Расходы
MS Excel сделать таблицу расходов семьи Чижовых за квартал.
8. Заполнить таблицу расходов начальными данными (рис. 2.2)
Набросок 2.
2
Размещение таблиц расходов
на рабочем листе Расходы
MS Excel
9. Заполнить строчку Сумма дохода за месяц
таблиц «Доходы Чижовой М. А. за 1 квартал 2006 г., руб.» и «Доходы Чижова А. С. за 1 квартал 2006 г., руб.», находящихся на листе Доходы
последующим образом:
Занести в ячейку С6 формулу:
=С4+С5
Размножить введенную в ячейку С6 формулу для других ячеек (с С4 по F4 и с С12 по F12) данных строк.
Таковым образом будет автоматом подсчитаны суммы дохода за месяц (рис. 2.3).
Набросок 2.
3
Автоматический подсчет суммы доходов за месяц
10. Заполнить строчку Суммарный расход за месяц
таблицы «Расходы семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Расходы
последующим образом:
Занести в ячейку С10 формулу:
=СУММ(C4:C9)
Размножить введенную в ячейку С10 формулу для других ячеек (с С10 по F10) данной строчки.
Таковым образом будет автоматом подсчитана сумма расхода за месяц (рис. 2.4).
Набросок 2.
4
Автоматический подсчет суммы расходов за месяц
11. Лист 3 переименовать в лист с заглавием Итоги.
12. На рабочем листе Итоги
MS Excel сделать таблицу «Доходы семьи Чижовых за 1 квартал 2006 г., руб.»
13. Заполнить строчки Заработная плата, Остальные поступления, Сумма дохода за месяц
таблицы «Доходы семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги
последующим образом:
Занести в ячейку С4 формулу:
=Доходы!C4+Доходы!C10
Размножить введенную в ячейку С4 формулу для других ячеек (с С4 по F6) данной таблицы.
Таковым образом будут автоматом подсчитана сумма дохода за месяц (рис. 2.5).
Набросок 2.
5
Автоматический подсчет суммы доходов за месяц
14. На рабочем листе Итоги
MS Excel сделать таблицу «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.»
15. Заполнить строчку Суммарный Доход за месяц
таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги
последующим образом:
Занести в ячейку С11 формулу:
=C6
Размножить введенную в ячейку С11 формулу для других ячеек (с С11 по F11) данной таблицы.
16. Заполнить строчку Суммарный расход за месяц
таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги
последующим образом:
Занести в ячейку С12 формулу:
=Расходы!C10
Размножить введенную в ячейку С12 формулу для других ячеек (с С12 по F12) данной таблицы.
17. Заполнить строчку Остаток
таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.», находящейся на листе Итоги
последующим образом:
Занести в ячейку С13 формулу:
=C11-C12
Размножить введенную в ячейку С13 формулу для других ячеек (с С13 по F13) данной таблицы.
Таковым образом будет заполнена таблица «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.» (рис. 2.6)
Набросок 2.
6
Автоматическое наполнение таблицы «бюджет семьи Чижовых за 1 квартал 2006 г., руб.
»
18. Лист 4 переименовать в лист с заглавием гистограмма.
19. По данным таблицы «Бюджет семьи Чижовых за 1 квартал 2006 г., руб.» на листе гистограмма
построим гистограмму (рис. 2.7).
Набросок 2.
7
Гистограмма
Перечень использованной литературы
1. БаронД. Введение в языкипрограммирования. М.: мир, 1980.- 190 с.
2. ВиртН. Методы и структурыданных./ Пер. с англ. — М.: мир, 1989. – 360 с.
3. Гуда А. Н., Бутакова М. А., Нечитайло Н. М., Чернов А.В. Информатика. Общий курс: Учебник / Под ред. академика ран В. И. Колесникова. – М.: Издательско-торговая компания «Дашков и К»; Ростов на дону н/Д: Наука-Пресс, 2007. – 400 с.
4. Каймин В. А. Информатика: Учебник. — М.: ИНФРА-М, 2000. — 232 с.
5. Кубенский, А. А.. Структуры и методы обработки данных. Объектно-ориентированный подход и реализация на С++ / А. А. Кубенский. – Спб: БХВ-Петербург, 2004. – 464 с.
6. Лэгсам Й., Огенстайн М.. Структуры данных для индивидуальных ЭВМ – М: мир, 1989. – 586 с.
7. Модели и структуры данных В. Д. Далека, А. С. Деревянко, О. Г. Кравец, Л. Е. Тимановская. Учебное пособие. Харьков: ХГПУ, 2000. — 241с.
8. Организация и обработка структур данных в вычислительных систем: Учебное пособие для вузов. Костин А.Е., Шаньгин В.Ф. 1987. — 248 с.
9. Советов Б. Я.. Информационные технологии. Учебник для студентов вузов. 2006. — 263 с.
10. Уоллес Вонг. Базы программирования для «чайников». Диалектика. Москва – Санкт-Петербург – Киев. 2001. – 335 с.
11. Хоор К. О структурной организации данных. В сб. «Отдал У., Дейкстра Э., Хоор К. Структурное программирование». /Пер. с англ. — М.: мир, 1975. – 197 с.
]]>