Способы организации данных: пользовательский тип данных - структура

Содержание:

ВВЕДЕНИЕ

Создание очень сложных программных продуктов, к примеру, разного рода информационных систем (ИС), требует подготовки квалифицированных разработчиков, которые в совершенстве могут владеть современными методами для построения систем по обработке данных.

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

С иной стороны, необходимо выбирать способ представления обработанных данных с учетом всех возможностей языка программирования (ЯП) и персонального компьютера (ПК).

Стоит отметить, что в разных языках программирования применяются специальные способы для выделения объемов памяти для хранимой информации, который часто называют динамическим.

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

В таких случаях почти всегда используется динамическое распределение применяемой памяти.

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

Объект курсовой работы – структурированные типы данных.

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

Цель исследования – рассмотреть главные понятия и операции со структурами.

Согласно указанной цели, выделим основные задачи, которые выдвигаются в рассматриваемой работе:

– рассмотреть основные определения о структурировании данных с точки зрения программирования;

– выполнить анализ принципов обработки структур;

– дать характеристику нелинейным структурам;

– рассмотреть односвязные динамические списки в С++;

– выполнить реализацию основных алгоритмов по работе со структурами на практике.

Исследованиями в данном направлении долгое время занимались ученые: Бочков С. Т.[2], Липпман Т. К. [8], Страуструп П. [13]

1. ПОНЯТИЕ О ПРОГРАММИРОВАНИИ И СТРУКТУРИРОВАНИИ ДАННЫХ

1.1.Определение, понятия и классификация языков программирования

В отличие от классических человеческих языков, ЯП более простые, так как они состоят из ограниченной численности слов, предназначенных исключительно для использования при записи алгоритмов.

Стоит заметить, что также они могут различаться, по близости к пониманию для обычного человека, по выразительным способностям и простоте. [3]

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

В данном случае любая фраза (часть кода), что описывается на ЯП также должна подчинятся синтаксису языка.

Практически все современные программы, написанные на ЯП высокого уровня вводятся в компьютер при применении обычного текста, а сам ПК, зная, о свойствах написанного кода программы преобразует его в машинный код. [5]

Обычно, такие языки программирования создаются и для удобства решения задач для определенного направления.

К примеру, язык программирования под названием Алгол (рисунок 1) создавался в свое время средствами и инструментами международной ассоциацией ученых по написанию и публикации в журналах разных алгоритмов.

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

Для решения всех основных задач в направлении коммерции со временем был специально создан язык, который имел название КОБОЛ, для обработки текстовых документов использовался ПРОЛОГ, при реализации процесса обучения студентов навыкам программирования были придуманы ЛИСП, БЕЙСИК, при выполнении математических вычислений – ФОРТРАН, в облегчении процесса программирования для аппаратной части ПК – язык С++. [10]

Ученые и инженеры в данное время работают над созданием универсального специального языка, на котором возможно описывать самые разные алгоритмы.

В то же время, активно может развиваться направление машинных специальных языков, имеющее использование только в строго определенных областях.

Все ЯП также занимают самое разное промежуточное положение, которое характеризуется состоянием между естественными и формализованными ЯП. [5]

Основные назначение для практически всех языков программирования – являться средством для выполнения программирования:

– реализовывать программы;

– писать программы на ПК.

Практически все ЯП используются в секторе формирования и описания алгоритмов, а также выполнения их в последующем на ПК, алгоритм при этом может также записываться с различным уровнем его детализации. [20]

Конкретная степень детализации для алгоритма также зависит от того, насколько учитывается архитектура компьютера при процессе написании программ.

Очень часто полагают, что опытные программисты могут писать программные продукты не для определенного ПК, а некоторой вычислительной машины (в общих понятиях). [4]

Чем больше деталей непосредственно в вычислительных устройствах ПК будет в описании, тем будет ниже уровень его абстракции.

На одном с высших уровней абстракции может содержаться полное представление для ПК как о фоннеймановской машине, что состоит с основных частей:

– памяти;

– устройств для ввода/вывода;

– процессора.

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

ОС представляет собой специальный программный комплекс при реализации управления практически всеми устройствами ПК. [8]

В нынешнее время очень популярными ОС считаются:

– Microsoft Windows;

– Linux;

– UNIX.

В случае, когда абстрактной вычислительной машине можно добавить операционную систему – в результате получим так называемую виртуальную машину. [12]

Различные программы могут быть написаны для любой абстрактной машины или виртуальной машины, а также будут создаваться некоторые основные трансляторы, среды для разработки ПО.

Для написания программ на низких уровнях языков программирования используются специальные ЯП, которые называются низкоуровневыми.

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

Практически все языки таких уровней являются машинными кодами, ассемблерами. Ассемблер имеет также несколько более применяемых способов создания программных продуктов.[1]

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

Программа оказывается также связанной к определенной архитектуре. Все это можно посчитать недостатками для программирования в ЯП низкого уровня.

Самым главным и основным преимуществом будет является возможность «выжать» с ресурсов компьютера практически все его возможности.

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

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

Самыми основоположными объектами для императивных языков являются:

– переменные;

– стандартные алгоритмические конструкции;

– операторы присваивания.

Императивные ЯП привязываются к традиционной архитектуре фон Неймана. [6]

Для всех ЯП функционального направления применяются функции, значения для которых определяются с непосредственным указанием параметров.

Все традиционные операторы, переменные при этом не рассматриваются.

В программных продуктах, что написаны с использованием логических ЯП, нет какого-то фиксированного или определенного порядка для реализации разных правил алгоритма.

Сам выбор подходящей для этого последовательности операций алгоритма будет возлагаться на саму систему. [9]

Объектно-ориентированные языки в значительной степени могут упростить программирование с использованием объектно-ориентированного программирования.

Delphi – многофункциональный язык, созданным на основе языка Object Pascal. Он также является очень популярным из-за наличия диалектов и многих компиляторов.

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

В целом, ЯП Delphi является императивным, объектно-ориентированным.

Именно с использованием ЯП Delphi созданы программы The KMPlayer, AIMP, Light Alloy, Total Commander, графический интерфейс для программы Skype.

Само наличие большого количества таких диалектов является также и достоинством, и определенным недостатком указанного языка, ведь программу, что написана с его помощью, другой компилятор не всегда сможет открыть. [12]

Язык С++ – один из самых основных объектно-ориентированных ЯП, невероятно популярный до нынешнего времени, который просто обязан изучить каждый современный программист.

Стоит отметить, не нужно начинать изучение принципов программирования с указанного ЯП, хотя со временем С++ будет наиболее используемым. [8]

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

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

ЯП также создан на основании одних из ранних языков, он в себя впитал их наработки, стал совершеннее. [2]

К тому же он обновляется постоянно, а самая последняя версия выпущена в 2014 г.

Основные положительные характеристики:

– простота;

– многофункциональность;

– минимализм.

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

Visual Basic фирмы Microsoft используют многие опытные программисты, поскольку большинство на нём познавало начала работы в началах программирования. Он очень многофункционален, прост, а также прекрасно подходит к быстрому проектированию программ. [4]

Он имеет все возможности по созданию ПО, также можно конструировать удобный пользовательский интерфейс программы.

VB применяют профессионалы из Microsoft для создания разного рода своих программ.

1.2.Определение, типы и предназначение структур данных

Необходимым условием для хранения информации непосредственно в памяти ПК является возможность преобразования ее в подходящую для обработки компьютером форму.

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

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

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

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

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

Можно показать много случаев, где у информации видно явную структуру.[20]

Наглядным примером этого служат книги, которые имеют разное содержания. Они разбиваются на страницы, главы и параграфы, имеют, как правило, свое оглавление, другими словами, интерфейс пользования.

В широком смысле рассматриваемого понятия, структуру имеет всякое живое существо.

Методы хранения информации, которые называют «простыми», то есть, неделимыми на разные составные части, предпочтительнее выучить вместе с определенным языком программирования (ЯП), либо же углубляться непосредственно в суть их работы.

Структуры данных можно применять в качестве информационных массивов, что предназначаются для непосредственного проектирования программного обеспечения. [15]

Стоит отметить, что структурированные данные имеют свою специфическую форму текстов, чисел и могут в себе содержать более сложные структуры (рисунок 1):

Рис. 1. Пример древоподобной структуры

Стоит отметить, что с понятием структуры данных в программировании тесно связан термин «тип данных». Виды применяемых данных при написании программ показаны на рисунке 2:[10]

Рис. 2. Типы данных

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

Стоит отметить, что много средств, для описания почти всех ЯП, есть возможность ссылаться в поэлементном варианте, пользуясь только названием [4].

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

Под структурой информации понимается множество составных элементов информации, а также перечень связей между ними. [8]

Такое определение описывает полностью все подходы и реализации структуризации, где по каждому определенному заданию будут отведены аспекты для его решения.

Рассмотрим типы структур данных, которые используются в программировании.

Физическая структура данных имеет возможность отражать методологию физического и логического описания их в постоянной памяти ПК. Она называется структурой хранения (другими словами, внутренней) структурой предоставления данных.

Рассмотрение с такой точки зрения структур данных не обращая внимание на учет представлений их в машинном коде, называют их абстрактной структурой.

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

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

Другой важнейший признак, по которому можно структурировать данных – характер упорядоченности для её элементов. [12]

По данному также структуры делятся на: (рисунок 3):

Рис. 3. Категории структур

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

Рис. 4. Классификация структур по характеру связей

В зависимости от указанной выше характеристики для взаимного расположения всех структуры в оперативной памяти, все современные структуры данных, которые называются линейными, еще можно разделить на несколько категорий [16]:

– векторы;

– массивы;

– стеки;

– строки;

– очереди.

Типичным примером нелинейной структуры являются многофайловые списки, графы, деревья. [3]

В современных ЯП очень тесно связывается определение "структуры " с термином "формат данных".

1.3.Характеристика структурных форматов данных

Простые структурные типы данных называют еще примитивами или же базовыми МД. Они являются так называемой отправной точкой для непосредственного применения структур в программных проектах.

В ЯП иногда применяются простые структуры, описывающиеся с применением таких базовых типов [6].

К таким типам можно отнести (рисунок 5):

Рис. 5. Простые структуры данных

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

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

Когда при объявлении массива заранее неизвестен его полный размер, то под его компоненты резервируется сразу максимальный возможный объем памяти.

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

К ним можно отнести:

– массивы;

– структуры;

– множества.

Рассмотрим некоторые с перечисленных структур.

Вектор (или одномерный массив) – это структура данных, которая располагает конкретной численностью элементов базового формата данных [3].

Каждый такой компонент вектора может имеет уникальный свой номер в рамках применения заданного вектора.

Такой номер называют индексом.

Обращение к элементу можно реализовать по имени, номеру элемента массива.

Под массивом понимается специальная структура данных, характеризующаяся: [6]

– фиксированным перечнем элементов;

– каждый из компонентов имеет уникальный набор значений индексов;

– общее количество всех рассмотренных индексов описывает размерность массива;

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

2. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

2.1. Принцип обработки динамических структур

Часто в больших программных проектах надо применять данные, в которых размер и структура должны меняться непосредственно при процессе работы.

Все динамические массивы выделяют память под свои компоненты только в процессе их обработки.

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

– ссылок;

– поля данных.

Ссылка (или указатель) – это адрес других узлов такого же типа, с которыми этот узел логически связан. [9]

В языке программирования С++ для организации ссылок применяется переменная-указатели.

При добавлении узла в указанную структуру формируется новый блок памяти, а потом посредством ссылок устанавливаются связи нового элемента с существующими.

Для обозначения самого последнего элемента в цепи применяются нулевые ссылки (обозначаются NULL).

Достоинство применения ссылок состоит в следующем:

– возможность обеспечения изменчивости информации;

– размер структур ограничен только доступным объёмом оперативной ПК;

– при рассмотрении иных логических последовательностей для компонентов динамической структуры не нужно переместить всю информацию в оперативной памяти, а возможно только выполнить перенаправление указателей на нее. [18]

Также, вместе с рассмотренным фактом, ссылки имеют также некоторые недостатки:

– работа с указателями выполняется разработчиками, которые имеют более высокую квалификацию;

– на поля ссылок будет расходоваться также некоторый объем дополнительной памяти;

– выполнение непосредственного доступа к элементам структур во времени может быть не эффективным.

Динамический список – упорядоченная совокупность, которая состоит из некоторого количества элементов (не обязательно постоянного), с которыми применяются операции по добавлению и удалению узлов в список (рисунок 6)[2].

Рис. 6. Схема динамического списка

Каждый элемент списка содержит ссылку на следующий элемент за ним. У последнего элемента списка поле ссылки содержит указатель NULL.

Чтоб не потерять список, надо где-то (в основном, в переменной) хранить адрес первого его узла – его называют «головой» списка.

Стоит отметить, что в программе надо объявлять 2 новых формата данных, к примеру, узел Node и указатель PNode.

Узел представляется структурой, которая содержит сразу три поля:

– строку;

– целое число;

– указатель на аналогичный узел.

Ниже, на рисунке 7 приведена классическая структура односвязного списка. В структуре, которая рассмотрена ниже, поле inf реализуется как информационное поле или данные, а next – это указатель на следующий узел структуры.

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

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

Рис. 7. Структура линейного односвязного списка

Многие проблемы при обработке односвязных списков вызваны тем, что невозможно в них перейти к прошедшему элементу.

Возникает естественная задача: как хранить в памяти ссылки не лишь на следующий, а и на предыдущий компонент списка.

Для выполнения доступа к списку применяется не одна переменная-указатель, а сразу две – ссылка на первый элемент списка (к примеру, Head) и на последний элемент – Tail.

Стоит заметить, что эту возможность может обеспечить только 2-связный список, в котором использованы 2 указателя: [14]

– на предыдущий элемент;

– на следующий элемент.

В крайних элементах расмотренных списков соответствующие указатели могут содержать значения nil (рисунок 8).[1]

Рис.8. Схема 2-связного списка

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

Указанное применение 2-х указателей для узлов значительно усложняет архитектуру списка, приводит также к разным дополнительным объемам памяти, обеспечивает выполнение всех команд, операций с обрабатываемой списочной структурой. [7]

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

При непосредственной работе с списочной структурой односвязного типа указатели последнего элемента часто указывают на первый элемент списка (рисунок 9). [11]

Рис.9. Описание циклических списков

Линейные списки применяются широко в разного рода приложениях, где все требования непредсказуемы с точки зрения размера памяти, который применяется, также есть нужный для корректного хранения информации; при этом большое число сложнейших команд и операций для имеющихся данных, исключений элементов и включений их. [5]

2.2.Нелинейные динамические структуры

Нелинейным разветвляющимся списком называют такой динамический список, узлами у которого являются уже созданные ранее списки (рисунок 10) [13].

Рис.10. Схема нелинейного разветвленного списка

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

Граф – совокупность узлов (или вершин) и соединяющих их дуг (ребер).

Если дуги являются направленными, то такой граф называют ориентированным или направленным графом (орграфом) (рисунок 11) [2].

Рис.11. Пример графа

На рисунке 12, показаны несколько примеров самых простейших графов:

Рис.12. Примеры графов

При определении структуры ориентированного графа общее количество его ребер, входящих практически в любой с узлов, называют входной полустепенью, выходящих – выходной полустепенью. [17]

Цепью называется определенная последовательность ребер, которые соединяют (возможно даже не соседние) вершины динамической структуры. В направленном графе рассмотренная последовательность ребер называется путем.

Граф является связным, если в нем существует цепь между всеми парами вершин.

Если же граф не связный, его можно разбивать на k связных элементов – в таком случае называется k-связным.

В разных практических задачах рассматриваются часто взвешенные графы, где каждому ребру приписывается определенный вес (длина).

Такой граф является сетью.

Циклом называют цепь с какой-нибудь вершины в нее саму.

Стоит отметить, что дерево – это граф, характеризующийся такими свойствами:[19]

1. Существует один единственный узел, на который не ссылаются иные элементы – корень (рисунок 13).

Рис.13. Дерево

2.Начиная с корневого элемента, следуя по определенной последовательности, можно качественно осуществлять доступ практически к всем элементам.

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

а) б)

Рис.14. Примеры матриц смежности

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

3. ИСПОЛЬЗОВАНИЕ ЯЗЫКА ВЫСОКОГО УРОВНЯ ДЛЯ РЕАЛИЗАЦИИ ДИНАМИЧЕСКИХ СТРУКТУР

3.1. Пример реализации структур в С++ – односвязные списки

Рассмотрим далее списковые динамические структуры и их обработку в С++.

Как было ранее указано, список – динамическая структура данных, где несколько полей являются адресом (ссылкой, указателем) на иные структуры аналогичного типа.[19]

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

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

В памяти все используемые одномерные массивы, к примеру, с целочисленными параметрами, размещаются последовательно в памяти, то есть, по соседству.

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

Элементы динамических списков часто располагаются в памяти несколько хаотично.

Указанный факт предоставляет хорошую возможность для беспрепятственного выполнения манипуляции практически с любым числом узлов списка.

Список, который имеет разные числовые значения в памяти можно расположить так (рисунок 14) [17]:

Рис.14. Размещение узлов списка

Стрелки на рисунке 13 указывают последовательность размещения элементов.

Для выполнения работы с узлами списка так, как и в любой связной структуре данных, надо выполнить определение места нахождения требуемого элемента. [1]

В этом случае часто хранят только адреса (указатели) первого элемента (first).

Далее для всех элементов есть необходимость «знать», именно где будет размещен узел, который за ним расположен

Заметим, что к всем элементам можно легко добраться, начиная с самого первого и т.д.

В приведенном выше рисунке 14 элемент, имеющий значение 1 может «направить» нас на место, где размещен узел со значением 8 и т.д.

Чтобы «найти» элемент, который имеет значение 1, надо обратится к первому элементу (4), узнать адрес следующего (-5), потом узнать остальные адреса.

Наглядно списки изображены таким образом (рисунок 15):

Рис.15. Пример списка

3.2. Операции с элементами динамической структуры в С++

Рассмотрим пример с описанием основных операций и функции для обработки линейного односвязного списка.

//заголовочные файлы

#include <conio.h>

#include <iostream>

//объявление пространства имен

using namespace std;

//оглашение структуры ls

struct ls

{

int dat;

ls *next;

};

//описание указателей

ls * last, *first;

//функция, выполняющая просмотр списка

void print_ls()

{

ls *s=first;

cout<<"List: ";

while(s!=0)

{

cout<<s->dat<<"_";

s=s->next;

}

cout<<endl;

}

// добавления узлов в конец динамического списка

void a_end(int y)

{

ls *s=new ls;

s->dat=y;

c->next=NULL;

//проверка наличия первого элемента

if(first==0)

first=s;

else

last->next = s;

last = s;

}

//функция для добавления узлов в начало

void a_beg(int y)

{

ls *s=new ls;

s->dat=x;

s->next=0;

//наличние первого элемента

if(first==0)

{

first=s;

last=s;

}

else

s->next = first;

first = s;

}

// добавление узлов в середину линейного списка

void a_mid(int u, int y)

{

ls *s=new ls;

ls *s1;

s->dat=y;

s->next=0;

if(first==0)

first=s;

else

{

s1=first;

while(s1!=0)

{

if (s1->dat==u)

{

s->next=s1->next;

s1->next=s;

}

s1=s1->next;

}

}

}

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

void d_beg()

{

ls *s=first;

first=first->next;

delete s;

}

// удаление элементов с конца

void d_end()

{

ls *s=first;

ls *s1;

while (s->next!=last)

s=s->next;

last=s;

s1=last->next;

delete s1;

s->next=0;

}

//

int main()

{

int y,N;

cout<<"N = ";

cin>>N;

cout<<"List: ";

for(int j=0;j<N;j++)

{

cin>>y;

a_beg(y);

}

//Вызов пользовательских функций

// добавление элементов в середину линейного списка

a_mid(3,11);

//печать

print_list();

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

d_beg();

//печать

print_list();

// удаление элементов с конца

d_end();

{

//печать

getch();

print_list();

return 0;

}

}

Получим (рисунок 16):

Рис.16. Результат

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

Также рассмотрены главные функции для обработки классических динамических структур, разработана программа для демонстрации их.

ЗАКЛЮЧЕНИЕ

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

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

При обработке программ вычислительной машиной они практически всегда оперируют с некоторым объемом информации, которая хранится в ячейках памяти.

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

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

В курсовой работе решены следующие задачи:

– рассмотрены основные определения о структурировании данных с точки зрения программирования;

– выполнен анализ принципов обработки структур;

– дана характеристика нелинейным структурам;

– рассмотрены односвязные динамические списки в С++;

– выполнена реализация основных алгоритмов по работе со структурами на практике.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Аммерааль Л. STL для программистов на С++: Пер. с англ. — М.: ДМК, 2017. — 240 с.
2. Бочков С. О., Субботин Д. М. Язык программирования Си для персонального компьютера. — М.: Радио и связь, 2016. — 384 с.
3. Бобровский С. Самоучитель програмирования на языке C++ в среде Borland C++ Builder М.: ИНФРА-М, 2015.–251 c.
4. Бруно Бабэ. Просто и ясно о Borland C++: Пер. с англ. - Москва: БИНОМ, 2014. – 400с.
5. Джосьютис Н. М. C++. Стандартная библиотека. Для профессионалов: Пер. с англ. — СПб.: Питер, 2014. — 730 с.
6. Керниган Б. В., Ритчи Д. М. Язык программирования Си: Пер. с англ. — 3-е изд. — СПб.: Невский Диалект, 2014. — 352 с.
7. Липпман С. Б. Основы программирования на C++: Пер. с англ. — М.: Вильямс, 2013. — 256 с.
8. Липпман С. Б., Лажойе Ж. Язык программирования С++. Вводный курс: Пер. с англ. — 3-е изд. — М.: ДМК, 2016. — 1104 с.
9. Лишнер Р. STL. Карманный справочник: Пер. с англ. — СПб.: Питер, 2015. — 187 с.
10. Мейерс С. Эффективное использование STL: Пер. с англ. — СПб.: Питер, 2013. — 224 с.
11. Оллисон Ч. Философия С++. Практическое программирование. С.Петербург 2014. – 608 с.:ил.
12. Послед Б.С. Borland C++ Builder 6. Разработка приложений баз. М.: 2013г. -360 г.
13. Стенли Б. Липпман. C++ для начинающих: Пер. с англ. 2тт. - Москва: Унитех; Рязань: Гэлион, 2013. – 345с.
14. Страуструп Б. Язык программирования C++: Пер. с англ. — 3-е спец. изд. — М.: Бином, 2013. — 1104 с.
15. Страуструп Б. Дизайн и эволюция языка C++. Объектно- ориентированный язык программирования: Пер. с англ. — М.: ДМК пресс, Питер, 2013. — 448 с.
16. Холингворт Д. Учебник по программированию в среде С++ Builder 5. – Наука.–М.: 2015. –865 с.
17. Юпашников A.M. Программирование в среде C++ Builder. — М.: МИФИ, 2014. – 360 c.
18. Эккель Б. Философия C++. Введение в стандартный C++: Пер. с англ. — 2-е изд. — СПб.: Питер, 2014. — 572 с.
19. Эккель Б., Эллисон Ч. Философия C++. Практическое программирование: Пер. с англ. — СПб.: Питер, 2014. — 608 с. с. 1 (из 2)
20. STL — стандартная библиотека шаблонов C++: Пер. с англ. / П. Плаугер, А. Степанов, М. Ли, Д. Массер. — СПб.: БХВ-Петербург, 2014. — 656 с.