Динамические структуры данных. Списки (Структура программы и языка программирования)

Содержание:

ВВЕДЕНИЕ

Прежде, чем перейти к основной теме курсовой работы, хотелось бы найти ответ на вопрос: «Зачем нужно программирование?».

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

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

Существует множество языков программирования, которые применялись ранее и применяются по сей день, вот лишь некоторые из них: Фортран, Алгол, Pascal, Python, Java, С, Basic и др.

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

Прежде, чем перейти к теме курсовой «Динамические структуры данных. Списки» рассмотрим общие понятия написания программы.

1. Структура программы и языка программирования

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

Например:

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков).

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

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

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

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

1. компоненты программы находятся в памяти. В принципе, память является общей для них всех, но логически она разделяется на области, именуемые сегментами. Прежде всего, это сегмент данных, содержащий, естественно, данные программы. Алгоритмическая компонента (выражения, операторы) также находится в памяти в собственном сегменте команд;
2. одновременное нахождение в памяти «алгоритма» и данных соответствует принципу хранимой программы. Перед загрузкой в память эти же компоненты находятся в программном файле, который представляет собой точную копию представления программы в памяти – «образ памяти». Это позволяет рассматривать всю программу (в том числе и алгоритм) как данные для работы других программ, например, трансляторов;
3. набор операций, выполняемый в программе, соответствует системе команд процессора, на котором она выполняется. Сюда же входят команды, которые обеспечивают заданный в программе порядок действий (операторов).

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

1. средства описания данных: определение типов данных (форма представления) и переменных;
2. набор операций над основными типами данных (включая ввод-вывод), а также средства записи выражений;
3. набор операторов, определяющих различные варианты порядка выполнения выражений в программе (последовательность, условие, повторение, блок);
4. средства разбиения программы на независимые части – модули (функции, процедуры), взаимодействующие между собой через программные интерфейсы.

Определение программы уже давно дано в простой формуле: «Программа = алгоритм + данные». Но в ней алгоритм и данные не просто «складываются» в одно целое как независимые части, но являются двумя взаимозависимыми элементами. [1]

1. Язык С++. История возникновения

C++ компилируемый язык программирования общего назначения, сочетает свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его предшественником, языком программирования Cи, наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Название «язык программирования C++» происходит от языка программирования C, в котором унарный оператор ++ обозначает инкремент переменной.

Язык программирования C++ широко используется для разработки программного обеспечения. А именно, создание разнообразных прикладных программ, разработка операционных систем, драйверов устройств, а также видео игр и многое другое. Существует несколько реализаций языка программирования C++ — как бесплатных, так и коммерческих. Их производят проекты: GNU, Microsoft и Embarcadero (Borland). Проект GNU — проект разработки свободного программного обеспечения (СПО).

Язык программирования С++ был создан в начале 1980-х годов, его создатель сотрудник фирмы Bell Laboratories — Бьёрн Страуструп.

Он придумал ряд усовершенствований к языку программирования C, для собственных нужд, т.е. изначально не планировалось создания языка программирования С++. Ранние версии языка С++, известные под именем «Cи с классами», начали появляться с 1980 года. Язык C, будучи базовым языком системы UNIX, на которой работали компьютеры фирмы Bell, является быстрым, многофункциональным и переносимым. Страуструп добавил к нему возможность работы с классами и объектами, тем самым зародил предпосылки нового, основанного на синтаксисе С, языка программирования. Синтаксис C++ был основан на синтаксисе C, так как Бьёрн Страуструп стремился сохранить совместимость с языком C.

В 1983 году произошло переименование языка из «Cи с классами»в «язык программирования C++». В него были добавлены новые возможности: виртуальные функции, перегрузка функций и операторов, ссылки, константы и многое другое. Его первый коммерческий выпуск состоялся в октябре 1985 года. Язык программирования C++ является свободным, то есть никто не обладает на него правами. [2]

1. Типы данных и переменные

Для обработки данных их необходимо хранить в памяти. При этом к этим данным надо как-то обращаться. Обычно люди обращаются друг к другу по имени, такой же способ используется в программировании: каждой ячейке памяти (или группе ячеек) дается свое собственное имя. Используя это имя можно прочитать информацию из ячейки и записать туда новую информацию.

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

С точки зрения компьютера все данные в памяти – это числа (более точно – наборы нулей и единиц). Тем не менее, вы (и компьютер) знаете, что с целыми и дробными числами работают по-разному. Поэтому в каждом языке программирования есть разные типы данных, для обработки которых используются разные методы. Например:

• целые переменные – тип int (от английского integer – целый), занимают 4 байта в памяти;
• вещественные переменные, которые могут иметь дробную часть (тип float – от английского floating point – плавающая точка) , занимают 4 байта в памяти
• символы (тип char – от английского character – символ), занимают 1 байт в памяти

Любую переменную, которые вы будете использовать в программе, необходимо объявлять сказать компьютеру, чтобы он выделил для неё ячейку памяти нужного размера и присвоил ей имя. Переменные обычно объявляются в начале программы. Для объявления надо написать название типа переменных (int, float или char), а затем через запятую имена всех объявляемых переменных. При желании можно сразу записать в новую ячейку нужное значение, как показано в примерах ниже. Если переменной не присваивается никакого значения, то в ней находится «мусор», то есть то, что было там раньше. [3]

Пример:

int a; // выделить память под целую переменную a

float b, c; // две вещественных переменных b и c

int Tu104, Il86=23, Yak42; // три целых переменных, в Il86 сразу записывается число 23

float x=4.56, y, z; // три вещественных переменных,в x сразу записывается число 4.56

char c, c2='A', m; // три символьных переменных, в c2 сразу записывается символ 'A'

1. Динамические структуры данных. Списки

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

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

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

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

• 1. Линейные списки

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

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

Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически:

Рисунок 1. Линейный список F

Например, F1=< 2,3,1>,F2=< 7,7,7,2,1,12 >, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0.

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

• найти элемент с заданным свойством;
• определить первый элемент в линейном списке;
• вставить дополнительный элемент до или после указанного узла;
• исключить определенный элемент из списка;
• упорядочить узлы линейного списка в определенном порядке.

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

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

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

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

float d[100]; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d[0]=7; d[1]=10; l=2;

Полученный список хранится в памяти согласно схеме:

Рисунок 2. Последовательное хранение линейного списка

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

Описание структуры и указателя в этом случае может имееть вид:

Рисунок 3. Код описания структуры и указателя

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

Рисунок 4. Применение функции malloc для выделения памяти

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рисунке:

Рисунок 5. Связное хранение линейного списка

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

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

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

Рисунок 6. Описание двусвязного списка

Графическая интерпретация метода связанного хранения списка F=< 2,5,7,1 > как списка с двумя связями приведена на рисунке:

Рисунок 7. Список с двумя связями

Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:

Рисунок 8. Вставка нового узла

Удаление элемента, следующего за узлом, на который указывает p

Рисунок 9. Удаление элемента

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

Схема циклического хранение списка F=< 2,5,7,1 > приведена на рисунке ниже [4]:

Рисунок 10. Схема циклического хранения списка

ЗАКЛЮЧЕНИЕ

Рассмотренная тема наглядно показывает насколько широк выбор инструментов для программирования. Алгоритмизация процесса позволяет четко спланировать сценарий дальнейшей техники написания кода, что приведет в конечном итоге с ожидаемому результату, а соблюдение правил оформления программного кода облегчит процесс отладки приложения. Прогресс не стоит на месте – в руках ИТ-специалистов появляется все больше инструментов для автоматизации тех или иных процессов. Главная задача – научиться правильно и рационально ими распорядится, чтобы на свет появилось очередное необходимое обществу приложение или программа, не только выполняющее свою функцию, но и отличающееся высоким быстродействием. А это, в свою очередь, возможно только при грамотном использовании оперативной памяти. Ведь всем знакома ситуация, когда в критический момент нужная именно в этот момент программа начинает «подвисать», что ведет к сбою в работе нервной системы пользователя.

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

1. Сайт Новосибирского государственного университета http://ermak.cs.nstu.ru/ (Дата обращения 08.08.2016)
2. Электронный учебник программирования на языках С и С++ http://cppstudio.com/post/1984/ (Дата обращения 08.08.2016)
3. К.Поляков. Программирование на языке С, 1995-2012, с.7
4. Рекомендованное учебное пособие для изучения дисциплины «Программирование».