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

ВВЕДЕНИЕ

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

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

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

Существует множество языков программирования, которые применялись ранее и применяются по сей день, вот лишь некоторые из них: Фортран, Алгол, 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.

---