Информатика. Методы программирования и структуры данных

№ 193

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Кафедра инженерной кибернетики

Е.В. Сигитов

Информатика

Методы программирования
и структуры данных

Учебное пособие

Рекомендовано редакционноиздательским
советом университета

Москва   Издательский Дом МИСиС
2008

УДК 004.4 
 
С34 

Р е ц е н з е н т  
профессор Е.А. Калашников 

Сигитов Е.В. 
С34  
Информатика. Методы программирования и структуры данных: Учеб. пособие. – М.: Изд. Дом МИСиС, 2008. – 105 с. 

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

© Государственный технологический  
университет «Московский институт 
стали и сплавов» (МИСиС), 2008 

ОГЛАВЛЕНИЕ 

1. Программирование на языке Си..........................................................5 
1.1. Структура программы...................................................................5 
1.2. Переменные. Типы данных. Выражения.....................................5 
1.3. Массивы и структуры....................................................................8 
1.4. Указатели. Динамическое распределение памяти....................11 
1.5. Определение класса памяти и область действия имен.............12 
1.6. Операторы ....................................................................................13 
1.7. Функции........................................................................................21 
1.7.1. Функция, возвращающая значение.....................................21 
1.7.2. Функция, не возвращающая значений................................22 
1.8. Файлы данных..............................................................................27 
1.9. Текстовый и графический режимы............................................29 
2. Структуры данных..............................................................................36 
2.1. Стеки и очереди...........................................................................36 
2.2. Линейные списки.........................................................................40 
Задание.............................................................................................48 
Варианты задач...............................................................................49 
Варианты данных............................................................................51 
Контрольные вопросы....................................................................51 
2.3. Деревья .........................................................................................51 
2.4. Графы............................................................................................65 
2.4.1. Способы представления графа в памяти ............................67 
2.4.2. Формирование графа............................................................68 
2.4.3. Алгоритмы обхода графа.....................................................72 
2.4.3.1. Фронтальный обход......................................................72 
2.4.3.2. Радиальный обход.........................................................76 
2.5. Сортировка...................................................................................83 
2.5.1. Сортировка методом выборки.............................................83 
2.5.2. Сортировка включением......................................................86 
2.5.3. Сортировка распределением................................................88 
2.5.4. Сортировка обменами ..........................................................90 
2.5.5. Сортировка слиянием...........................................................93 
3. Выполнение программы в интегрированной среде 
Вorland С++ 3.1 .......................................................................................98 
3.1. Экран интегрированной среды...................................................98 
3.2. Отладка программы...................................................................100 
3.2.1. Ход выполнения программы .............................................100 
3.2.2. Установка точек останова..................................................101 

3.2.3. Определение значений переменных и выражений..........101 
3.2.4. Просмотр значений переменных и выражений ...............102 
3.3. Окончание выполнения программы ........................................103 
Библиографический список.................................................................104 
 

1. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ СИ 

1.1. Структура программы 

При решении задач из различных областей используются разнообразные структуры данных. Сочетание правильного выбора расположения информации (структуры данных) и современного алгоритмического языка высокого уровня позволяет создавать эффективные 
алгоритмы и программы. 
Программа начинается перечислением директив подключения 
файлов из библиотек, необходимых при выполнении программы. 
Директива подключения файла из стандартной библиотеки имеет вид 
#include <имя файла> 
Директива #include <stdio.h> (подключение файла из стандартной библиотеки, содержащей функции, которые выполняют ввод 
– вывод) присутствует практически в любой программе. 
Далее следуют директивы определения #define (см. ниже); раздел описаний, где должны быть объявлены глобальные переменные; 
определения функций и, наконец, главная функция main(). Выполнение программы начинается с главной функции main. 

1.2. Переменные. Типы данных. Выражения 

Для именования объектов программы используются идентификаторы. Идентификатор содержит буквы, цифры и знак подчеркивания и начинается с буквы. Для внутренних переменных значащими 
является первый 31 символ. Большие и малые буквы различаются. 
Ключевые слова if, else, struct и т.п. зарезервированы и набираются малыми буквами. 
Переменная – это именованная область памяти, в которой хранятся данные определенного типа. У переменной есть имя (идентификатор) и значение. Имя служит для обращения к области памяти, в которой хранится значение. Перед использованием любая переменная 
должна быть описана. Описание переменной задает тип, класс памяти и по умолчанию область действия, т.е. в какой части программы 
ее можно использовать.  
Базовыми типами являются char (символьный, занимает в памяти 1 байт), int (целый, занимает в памяти 2 байта или 4 байта в 
зависимости от компьютера), float (вещественный, занимает в 

памяти 4 байта), double (двойной точности, занимает в памяти 8 
байтов). Базовые типы могут использоваться с квалификаторами: 
short и long применительно к целым, signed (со знаком) или 
unsigned (без знака) – к типу char или любому целому типу, 
long – к типу double. 
Перечисленные типы (называемые стандартными) можно использовать для описания переменных непосредственно: 
float x,y; 
short m; 
З а м е ч а н и е. Последнее аналогично short int m; (int 
обычно опускается). 
Строки символов не выделяются как самостоятельный тип данных, а рассматриваются как массивы символов. 
Логический тип также не выделяется в качестве самостоятельного 
типа данных, а любое ненулевое значение трактуется как “истина”, 
нулевое значение – как “ложь”. При проверке истинности различных 
условий формируется значение 1, если условие выполняется, и 0 – в 
противоположном случае. При явном использовании констант true 
и false их необходимо определить директивами: 
#define  true   1 
#define  false  0 
В любой программе требуется проводить вычисления. Для вычисления значений используются выражения, которые состоят из операндов, знаков операций и скобок. Операнды задают данные для вычислений. Операции задают действия, которые необходимо выполнить. Каждый операнд является константой или переменной или, в 
свою очередь, выражением. Операции выполняются в соответствии с 
приоритетами. Для изменения порядка выполнения операций используются круглые скобки. В выражение могут входить операнды 
любого типа, и тогда выполняется преобразование типов. По смыслу 
выражение можно подразделить на арифметическое и логическое. 
В арифметическом выражении используются операции +, –, *, /, 
% (остаток от деления для целых). Результат любой из этих операций 
будет целый, если оба операнда целые, в остальных случаях результат вещественный.  
Заметим, что в Си отсутствует операция возведения в степень. 
Возведение в любую степень, например xy, выполняется функцией 
pow(x,y), которая расположена в файле math.h . 

При вычислении арифметических выражений действуют следующие правила приведения типов:  
1) любые операнды типа char, unsigned или short преобразуются к 
типу int; 
2) если один из операндов имеет тип long double, то другой преобразуется к типу long double; 
3) если пункт 2 не выполняется, а один из операндов имеет тип 
double, то другой преобразуется к типу double; 
4) если пункты 2 и 3 не выполняются, а один из операндов имеет 
тип float, то другой преобразуется к типу float; 
5) если пункты 2–4 не выполняются, а один из операндов имеет 
тип long, то другой преобразуется к типу long; 
6) иначе оба операнда имеют тип int. 
Тип результата тот же, что тип участвующих в выражении операндов. 
Тип результата вычисления выражения можно выразить и явно: 
(тип) выражение. 
Например, n/k и (double)n/k имеют разный результат при целых n и k, так как во втором выражении дробная часть результата 
при делении не отбрасывается. 
В Си очень большое количество разнообразных операций, поэтому для правильного применения операций важно знать их приоритет 
(перечислены в порядке убывания): 
1) ()  []  .  –>;  2) *  &  –  !   ~  ++   --   sizeof;  3)  *   /   %;    4)  +   –;   
5)    <<    >>; 6)  <  >  <=   >=;  7)  = =   !=;   8)  &;  9)  ^;   10)  |;  11)  
&&;  12)  ||;   13)  ?:; 14)   =    *=    /=    +=    –=;    15)  , 
Значение и содержание каждой операции будет ясно из того контекста, где будет применена эта операция.  
В логическом выражении могут использоваться три логические 
операции: ! (отрицание), && (И), || (ИЛИ). Логическим значением 
“истина” является любое ненулевое значение, а логическим значением “ложь” – нулевое значение. В связи с этим операндами логических выражений могут быть формально и числа, а не только отношения. Операции отношения >, >=, <, <= имеют одинаковый приоритет. 
Ниже приоритет операций сравнения на равенство = = и !=. Операции отношения имеют более низкий приоритет, чем арифметические 
операции, т.е. i > j+1 то же, что и i > (j+1). Приоритет логических операций еще более низкий, т.е. в логическом выражении 
сначала вычисляются арифметические выражения, затем операции 

отношения, а затем выполняются логические операции. Логические 
операции выполняются слева направо в соответствии со следующими 
приоритетами: сначала !, далее && и, наконец, ||. Вычисления прекращаются, как только становится известна истинность результата. 

1.3. Массивы и структуры 

При использовании простых переменных каждой области памяти 
для хранения данных соответствует свое имя. Если с группой величин одинакового типа требуются произвести однообразные действия, 
им дают одно имя, а различают их по порядковому номеру. Такая 
группа образует массив. Описание массива отличается от описания 
простой переменной заданием числа его элементов, взятым в квадратные скобки. Тип элемента массива может быть одним из стандартных типов, типом другого массива, типом указателя или типом 
структуры. Элементы массива нумеруются с нуля. Для доступа к 
элементу массива после его имени указывается номер элемента (индекс) в квадратных скобках. Многомерные массивы задаются указанием каждого измерения в квадратных скобках. 
Примеры описания массивов: 
int maxs[10]; 
float Matr[4][4]; 
char Name[20]; 
Описан одномерный массив maxs из 10 элементов целого типа: 
maxs[0], maxs[1], ..., maxs[9]; двухмерный массив Matr из 16 
элементов вещественного типа: Matr[0][0], Matr[0][1], ..., 
Matr[0][3], Matr[1][0], ..., Matr[3][3] и одномерный массив 
Name из 20 элементов символьного типа: Name[0], Name[1], ..., 
Name[19]. Массив Name представляет символьную строку, состоящую из 19 символов, причем последним элементом массива должен 
быть нулевой код ‘\0’, который служит ограничителем строки (заносится автоматически). 
При обращении к элементу двухмерного массива в квадратных 
скобках указывается номер элемента по каждому измерению, например, Matr[1][2]. Для двухмерного массива можно обращаться и к 
строке, указав один индекс. Например, Matr[3] – ссылка на одномерный массив из 4 элементов, т.е. третья строка массива Matr. 
Ссылка Matr[,3]означает обращение к третьему столбцу этой матрицы. 

При описании переменных и массивов им можно присвоить начальные значения (инициализировать). Например, 
float eps = 0.00001; 
int i = 0, j = 0; 
int maxs[10]={1,3,5,-2,43,6,-8,1,0,3}; 
double Ms[2][3]={{1.0,0.2,0.8},{5.,3.1,4.9}}; 
Структура состоит из элементов различных типов, причем каждый элемент структуры имеет собственное имя. Элементы структуры 
называются полями структуры и могут иметь любой тип (простые 
переменные, массивы, структуры), кроме типа этой же структуры, но 
могут быть указателями на него. Доступ к полям структуры выполняется с помощью операции выбора . (точка) при обращении к полю 
через имя структуры и операции ─> при обращении через указатель. 
Поля структуры размещаются в оперативной памяти одно за другим 
в той последовательности, в которой перечислены в описании.  
Описание структуры имеет вид 
struct 
{ 
список описаний  
} имя; 
 
В фигурных скобках перечисляются типы и имена элементов 
структуры. Например, структура 
   struct 
   { 
    char Name[20];/*фамилия и инициалы*/ 
       struct 
     { 
      int day; /*день*/ 
      char mon[9]; /*месяц*/ 
      int year; /*год рождения*/ 
     } date;  
 
    char adress[40]; /*адрес*/ 
 
   } student; 
состоит из трех элементов (одномерного символьного массива, 
структуры и еще одного одномерного символьного массива). Второй 
элемент, в свою очередь, структура, состоящая также из трех элементов (переменной целого типа, одномерного символьного массива и 

еще одной переменной целого типа). Она содержит фамилию, дату 
рождения и адрес местожительства студента.  
Доступ к отдельному элементу структуры осуществляется по составному имени, образованному из имени самой структуры, и имени 
элемента, разделеляемых точкой. Например, student.Name – фамилия студента, а student.date.year – год его рождения. 
Описание типа структуры (“шаблон”) имеет вид 
struct имя 
 { 
  список описаний     
 }; 
“Шаблон” задает лишь схему размещения элементов структуры в 
памяти и используется при описании конкретных структур. 
Если описать тип структуры  stud 
struct stud 
 { ... }; 
(здесь  ...  обозначает то, чтó в приведенном выше описании заключено во внешних фигурных скобках), то с помощью этого типа можно описать структуру student следующим образом: 
         struct stud student; 
В Си используется еще одна форма описания типа, которая имеет 
вид 
typedef тип описатели имя типа; 
где тип – стандартный тип или тип пользователя, описатели – 
имена переменных, массивов, структур, указателей и т.д. 
Описание типа используется для того, чтобы все свойства объекта собрать в одном месте и присвоить им имя. Это имя типа может 
затем использоваться для последующих описаний конкретных объектов. Например, 
typedef  struct 
 { 
  double real; 
  double imag; 
 } Complx; 
описывает как тип структуру для комплексного числа, и в дальнейшем в программе комплексные числа можно описывать так: 
Complx  x, y, z; 

1.4. Указатели. Динамическое 
распределение памяти 

Указатель не является самостоятельным типом, он всегда связан 
с каким-либо другим конкретным типом (простой переменной, массивом, структурой). Указатель – это переменная, которая в качестве 
своего значения содержит адрес объекта определенного типа (стандартного или описанного в программе). При определении указателя 
надо стремиться выполнить его инициализацию, т.е. присвоение начального значения. 
Указатель обязательно связывается с типом того объекта, на который он ссылается. Например, описание 
int  *max; 
char  *smb; 
float  *Sum; 
определяет три указателя: max, smb и Sum, которые могут принимать значения адресов объектов целого, символьного и вещественного типа соответственно. Символ * в описании является признаком 
указателя. Указатель получает свое значение либо как значение другого указателя, либо непосредственным присвоением адреса переменной. Так, в результате выполнения оператора max = &x; указатель max получает значение адреса переменной x (типа int). Значение переменной, размещенной по адресу max, обозначается *max.  
Имя каждого массива есть указатель на первый элемент массива. 
Например, если описан массив double a[20]; то a – указатель. 
Над указателями можно выполнять некоторые операции (адресная 
арифметика). Арифметические операции с указателями автоматически учитывают размер типа величин, адресуемых указателями. Инкремент перемещает указатель к следующему элементу массива, 
декремент – к предыдущему. 
Примеры таких операций: a + i – указатель на элемент массива 
a[i], *(a + i) – значение элемента a[i]; выражение a + i 
является примером арифметических действий с указателями: целое 
значение i складывается с адресом первого элемента массива a. Значение этого выражения есть a плюс объем памяти (в байтах), занимаемый i элементами массива a; a++ – указатель на элемент массива a[1]. 
К указателям применимы также операции - (вычитание), операция -- (уменьшение на 1), если это дает адрес реального объекта. 

Если два указателя указывают на элементы одного и того же массива, то к ним применимы операции отношения. Например, p < g истинно, если p указывает на более ранний элемент массива, чем g. 
Можно использовать также указатели на структуру. Пусть, например, дано описание “шаблона” структуры 
  struct Complex 
  { 
   float real; 
 
   float imag; 
  }; 
тогда описание struct Complex *ps; является описанием указателя ps на структуру такого типа. В этом случае доступ к элементам структуры осуществляется через указатель так: 
ps->real и ps->imag или (*ps).real и (*ps).imag. 
Динамическое управление памятью осуществляют следующие 
функции, расположенные в файле alloc.h: 
1) *malloc(size); выделяет блок памяти размером size байтов и возвращает указатель на выделенный блок памяти или NULL 
при недостатке необходимого объема свободной памяти; 
2) *calloc(num,size);выполняет те же функции, что и 
malloc, но размер блока вычисляется как num*size и дополнительно выполняется обнуление выделенной памяти.  
Например, если дано описание Complx *ps;, то при выполнении оператора ps = (Complx *)malloc(sizeof(Complx)); 
выделяется блок памяти размером 16 байтов (для двух чисел типа 
double) и указателю ps присвоится адрес начала этого блока; 
3) функция free(*ptr); освобождает блок памяти, на который 
указывает ptr, для последующего использования. После выполнения функции значение указателя ptr становится неопределенным. 
Доступ к выделенным участкам динамической памяти, называемым динамическими переменными, производится только через указатели. 

1.5. Определение класса памяти 
и область действия имен 

В языке Си с каждым объектом (константы, переменные, массивы, структуры, функции) связывается область действия – часть про