- •Предисловие
- •Раздел 1. Полный курс программирования на стандартном языке Си Глава 1. Базовые понятия языка
- •1.1. Алфавит, идентификаторы, служебные слова Алфавит
- •Идентификатор
- •Служебные (ключевые) слова
- •1.2. Константы и строки
- •Символы, или символьные константы.
- •Целые константы.
- •Вещественные константы.
- •Предельные значения и типы арифметических констант.
- •Целые константы и выбираемые для них типы
- •Данные вещественных типов
- •Нулевой указатель.
- •Строки, или строковые константы.
- •1.3. Переменные и именованные константы Переменная как объект.
- •Определение переменных.
- •Предельные значения переменных.
- •Основные типы данных
- •Инициализация переменных.
- •Именованные константы.
- •1.4. Операции
- •Знаки операций.
- •Приоритеты (ранги) операций
- •Унарные (одноместные) операции.
- •1.5. Разделители
- •Квадратные скобки.
- •Круглые скобки.
- •Запятая.
- •Точка с запятой.
- •Двоеточие.
- •Многоточие.
- •Звездочка.
- •Обозначение присваивания.
- •Признак препроцессорных средств.
- •1.6. Выражения и приведение арифметических типов
- •Отношения и логические выражения.
- •Присваивание (выражение и оператор).
- •Приведение типов.
- •Правила преобразования типов
- •Правила стандартных арифметических преобразований
- •Выражения с поразрядными операциями.
- •Условное выражение.
- •Глава 2. Введение в программирование на языке си
- •2.1. Структура и компоненты простой программы
- •Текст программы и препроцессор.
- •Структура программы.
- •Функция форматированного вывода.
- •Программы печати предельных констант.
- •Применимость вещественных данных.
- •Выделение лексем из текста программы.
- •2.2. Элементарные средства программирования Деление операторов языка Си на группы.
- •Программа оценки машинного нуля.
- •Трассировочная таблица
- •Ввод данных.
- •Вычисление объема цилиндра.
- •Сумма членов ряда Фибоначчи.
- •2.3. Операторы цикла Три формы операторов цикла.
- •Приближенное значение экспоненты.
- •Оператор break.
- •Сумма отрезка степенного ряда.
- •Оператор continue.
- •Суммирование положительных чисел.
- •2.4. Массивы и вложение операторов цикла Массивы и переменные с индексами.
- •Вычисление среднего и дисперсии.
- •Упорядочение в одномерных массивах.
- •Инициализация массивов.
- •2.5. Функции Определение функций.
- •Функция для вычисления объема цилиндра.
- •Функция для вычисления скалярного произведения векторов.
- •Обращение к функции и ее прототип.
- •Вычисление биномиального коэффициента.
- •Вычисление объема цилиндра
- •Вычисление площади треугольника.
- •Скалярное произведение векторов.
- •2.6. Переключатели
- •Глава 3. Препроцессорные средства
- •3.1. Стадии и команды препроцессорной обработки
- •Стадии препроцессорной обработки.
- •Директивы препроцессора.
- •3.2. Замены в тексте Директива #define.
- •Цепочка подстановок.
- •3.3. Включение текстов из файлов
- •3.4. Условная компиляция Директивы ветвлений.
- •Операция defined.
- •3.5. Макроподстановки средствами препроцессора
- •Моделирование многомерных массивов.
- •Отличия макросов от функций.
- •Препроцессорные операции в строке замещения.
- •3.6. Вспомогательные директивы
- •Препроцессорные обозначения строк.
- •Реакция на ошибки.
- •Пустая директива.
- •Прагмы.
- •3.7. Встроенные (заранее определенные) макроимена
- •Глава 4. Указатели, массивы, строки
- •4.1. Указатели на объекты Адреса и указатели.
- •Операции над указателями.
- •Арифметические операции и указатели.
- •Указатели и отношения.
- •4.2. Указатели и массивы Указатели и доступ к элементам массивов.
- •Массивы динамической памяти.
- •Функции для выделения и освобождения памяти
- •Массивы указателей и моделирование многомерных массивов.
- •"Матрица" со строками разной длины.
- •4.3. Символьная информация и строки
- •Ввод-вывод символьных данных.
- •Внутренние коды и упорядоченность символов.
- •Строки, или строковые константы.
- •Строки и указатели.
- •Глава 5. Функции
- •5.1. Общие сведения о функциях Определение функции.
- •Описание функции и ее тип.
- •Вызов функции.
- •5.2. Указатели в параметрах функций Указатель-параметр.
- •Имитация подпрограмм.
- •5.3. Массивы и строки как параметры функций Массивы в параметрах.
- •Резюме по строкам-параметрам.
- •5.4. Указатели на функции Указатели при вызове функций.
- •Указатели на функции как параметры
- •Указатель на функцию как возвращаемое функцией значение.
- •Библиотечные функции с указателями на функции в параметрах.
- •5.5. Функции с переменным количеством параметров
- •Доступ к адресам параметров из списка.
- •Макросредства для переменного числа параметров.
- •Примеры функций с переменным количеством параметров.
- •5.6. Рекурсивные функции
- •5.7. Классы памяти и организация программ Локализация объектов.
- •Глобальные объекты.
- •Динамическая память
- •Внешние объекты.
- •5.8. Параметры функции main( )
- •Глава 6. Структуры и объединения
- •6.1. Структурные типы и структуры Производные типы.
- •Структурный тип.
- •Определение структур.
- •Выделение памяти для структур.
- •Инициализация и присваивание структур.
- •Доступ к элементам структур.
- •6.2. Структуры, массивы и указатели Массивы и структуры в качестве элементов структур.
- •Массивы структур.
- •Указатели на структуры.
- •Указатели как средство доступа к компонентам структур.
- •Указатели на структуры как компоненты структур.
- •6.3. Структуры и функции
- •Имитация абстрактных типов данных.
- •6.4. Динамические информационные структуры Статическое и динамическое представление данных.
- •Односвязный список.
- •Рекурсия при обработке списка.
- •6.5. Объединения и битовые поля Объединения.
- •Битовые поля.
- •Глава 7. Ввод и вывод
- •7.1. Потоковый ввод-вывод
- •7.1.1. Открытие и закрытие потока
- •7.1.2. Стандартные файлы и функции для работы с ними
- •Ввод-вывод отдельных символов.
- •Ввод-вывод строк.
- •Форматный ввод-вывод.
- •Спецификаторы форматной строки для функции форматного вывода
- •Спецификаторы форматной строки для функции форматного ввода
- •7.1.3. Работа с файлами на диске
- •Двоичный (бинарный) режим обмена с файлами.
- •Строковый обмен с файлами.
- •Позиционирование в потоке.
- •Трехъязычный словарь "Цифры
- •7.2. Ввод-вывод нижнего уровня
- •7.2.1. Открытие / закрытие файла
- •7.2.2. Чтение и запись данных
- •7.2.3. Произвольный доступ к файлу
- •Глава 8. Примеры разработки программ
- •8.1. Программа с объектами разных классов памяти Постановка задачи.
- •Программная реализация.
- •8.2. Структуры и обработка списков в основной памяти Постановка задачи.
- •Функция main( ).
- •Функция init( ) - "Инициализировать базу данных".
- •Функция delete() - "Удалить все сведения о сотруднике из базы данных".
- •Функция fr( ) - "Возвратить освобожденный элемент в список свободных элементов".
- •Функция input( ) - "Ввести в базу данных сведения о новом сотруднике".
- •Функция print( ) - "Печать списка занятых элементов".
- •Сохранение (восстановление) базы данных.
- •8.3. Сортировка на основе бинарного дерева Статические и динамические данные.
- •Управление динамической памятью.
- •Сортировка с помощью бинарного дерева.
- •Печать результатов сортировки.
- •Раздел 2. Выполнение программ в разных операционных системах Глава 9. Подготовка и выполнение программ
- •9.1. Подготовка программ в операционной системе unix
- •9.1.1. Команда make
- •Формат файла описаний зависимостей модулей.
- •Формат команды make.
- •Макроопределения.
- •Встроенные правила.
- •9.1.2. Библиотеки объектных модулей
- •Стандартные библиотеки.
- •Создание и сопровождение собственных библиотек.
- •9.2. Сборка и выполнение программ в интегрированной среде Turbo с 2.0
- •9.2.1. Состав системы программирования Turbo с 2.0
- •9.2.2. Экран интегрированной среды Turbo с 2.0
- •9.2.3. Система меню среды Turbo с 2.0
- •9.2.4. Настройка среды Turbo с
- •Создание рабочего каталога.
- •Установка в среде Turbo с 2.0 полных имен каталогов.
- •Настройка параметров управления проектом.
- •9.5. Окно определения проекта
- •Сборка и выполнение программы.
- •1. Команды управления курсором:
- •2. Команды вставки и удаления:
- •3. Команды обработки блоков текста:
- •4. Дополнительные команды:
- •9.3.2. Экран интегрированной среды
- •9.3.3. Система меню интегрированной среды
- •Задание полных имен основных и рабочего каталогов.
- •Выбор стандарта языка Си.
- •Установка параметров подсистемы Make.
- •Создание проекта.
- •Задание аргументов командной строки.
- •Сохранение параметров настройки интегрированной среды.
- •Сборка и выполнение программы.
- •Работа в интегрированной среде в последующих сеансах.
- •Раздел 3. Практикум по программированию на языке Си Глава 10. Задачи по программированию
- •10.1. Ознакомительная работа
- •10.2. Итерационные методы и ряды
- •Варианты заданий по итерационным методам и рядам
- •10.3. Работа со строками. Указатели, динамические одномерные массивы
- •10..1. Варианты задач по обработке строк*
- •10.3.2. Рекомендации по обработке строк
- •10.3.3. Пример выполнения задания по обработке строк
- •10.4. Многомерные динамические массивы с переменными размерами
- •10.4.1. Варианты задач для 1-й части задания по многомерным массивам (правила формирования многомерного массива)
- •10.4.2. Варианты для 2-й части задания по многомерным массивам
- •10.4.3. Пример выполнения задания по многомерным динамическим массивам
- •10.5. Функции и указатели
- •10.6. Функции и массивы
- •10.7. Работа со структурами
- •10.7.1. Варианты структур для выполнения работы
- •10.8. Списки и деревья
- •10.8.1. Списки
- •10.8.2. Деревья
- •Приложение 1. Таблицы кодов ascii
- •Коды управляющих символов (0 31)
- •Символы с кодами 32 127
- •Символы с кодами 128 255 (Кодовая таблица 866 - ms-dos)
- •Символы с кодами 128 255 (Кодовая таблица 1251 - ms Windows)
- •Приложение 2. Константы предельных значений
- •Приложение 3. Стандартная библиотека функций языка Си
- •Функции для работы с терминалом в текстовом режиме (файл conio.H)
- •Специальные функции
- •Литература
- •Содержание
- •Раздел 1. Полный курс программирования на стандартном языке Си 4
- •Глава 1. Базовые понятия языка 4
- •Глава 2. Введение в программирование на языке си 33
- •Глава 3. Препроцессорные средства 73
- •Глава 4. Указатели, массивы, строки 91
- •Глава 5. Функции 114
- •Глава 6. Структуры и объединения 155
- •Глава 7. Ввод и вывод 186
- •Глава 8. Примеры разработки программ 218
- •Раздел 2. Выполнение программ в разных операционных системах 256
- •Глава 9. Подготовка и выполнение программ 256
- •Раздел 3. Практикум по программированию на языке Си 282
- •Глава 10. Задачи по программированию 282
- •Подбельский Вадим Валерьевич Фомин Сергей Сергеевич программирование на языке си
- •101000, Москва, ул. Покровка, 7 Телефон (095) 925-35-02, факс (095) 925-09-57
8.2. Структуры и обработка списков в основной памяти Постановка задачи.
Постановка задачи. Рассмотрим задачу, в которой весьма целесообразен структурный тип данных. Предположим, что в памяти ЭВМ необходимо хранить сведения о сотрудниках некоторого учреждения и иметь возможность выдавать справки по личному составу, а также корректировать сохраняемые данные при изменениях сведений. Таким образом, нужна несложная база данных о сотрудниках. Для каждого сотрудника должно быть указано (в скобках определен тип переменной):
• фамилия (char[ ]);
• название отдела (char[ ]);
• номер отдела (int);
• оклад (int);
• код должности (int);
• название должности (char[ ]);
• дата поступления на работу (char[ ]).
Предположим также, что штатным расписанием установлена граница - не более 100 сотрудников, а при работе с этой базой данных потребуются следующие функции:
• ввод сведений о новом сотруднике;
• удаление сведений о сотруднике;
• вывод на экран дисплея текущего состояния базы данных с ранжированием информации о сотрудниках по одному из следующих признаков:
- по окладам;
- по отделам;
- по алфавиту (по фамилиям);
- по датам поступления на работу.
Сведения о сотруднике для данной задачи будем определять с помощью структуры такого структурного типа:
Напомним, что приведенное описание не определяет структуру с именем person. Вводится только "формат" входящих в структуру данных, и этот формат как структурный тип обозначается именем person.
В нашей задаче запись о сотруднике учреждения (эта запись оформляется в виде конкретной структуры) должна быть элементом массива, содержащего сведения о всех сотрудниках. Массив структур определяется следующим образом:
Это определение отводит память для 100 индексированных переменных с общим именем st, каждая из которых является структурой типа person. Заметим, что, как и все массивы, массивы структур индексируются, начиная с 0.
Если необходимо вывести на экран дисплея значение заработной платы сотрудника, идущего в списке под номером 4, это можно сделать следующим образом:
Как и другие объекты программ на языке Си, структуры имеют адрес — номер байта, начиная с которого структура размещается в основной памяти. Со структурой можно связать указатель, объявив его стандартным образом. Например:
где point - указатель на структуру типа person.
Описав указатель на структуру, можно присвоить ему адрес конкретной структуры того же типа: point = &st[3];. После такого определения значения указателя появляется еще одна возможность доступа к элементам структуры. Ее обеспечивает операция '->', позволяющая обратиться к любому элементу структуры, с которой в данный момент связан указатель. Например, к тому же элементу st[3].price можно теперь обратиться, используя конструкцию point->price.
Напомним возможность применения указателя в уточненном имени элемента структуры. Операция раскрытия ссылки позволяет обратиться к объекту, который адресует указатель, в частном случае - на структуру. Таким образом, выражение (*point).price (обратите внимание на необходимость скобок, так как операция раскрытия ссылки '*' относится только к указателю point и ее приоритет ниже, чем у операции '.') эквивалентно point->price и st[3].price.
После того как определен состав сведений об одном сотруднике и эта информация описана в виде структурного типа, необходимо определить способ хранения структур. Одним из вариантов хранения совокупности однотипных структур является массив фиксированного размера. Однако такая форма реализации базы данных не всегда удобна. Во время работы с массивами, в которых записи размещены последовательно и, как правило, упорядочены по некоторому признаку, возникают проблемы, связанные с реорганизацией таких массивов при добавлении или удалении записей. Реорганизации массива можно избежать, если хранить записи базы данных в связных списках.
Техника работы со связными списками предполагает в случае ввода новой записи запрашивать для нее у операционной системы дополнительный объем памяти, а при удалении записи - возвращать соответствующий участок памяти операционной системе.
При программировании на языке Си для этой цели можно (как мы демонстрировали выше) использовать соответственно функции malloc( ), calloc( ) и free( ), но в рассматриваемом случае, учитывая небольшой объем базы данных и учебный характер программы, будем использовать связный список с фиксированным количеством (100) элементов, формируя его из заранее выделенного массива. Чтобы записи с информацией о сотрудниках можно было связать в список, необходимо в структуру, которая описывает сведения об одном сотруднике, ввести указатель на следующий элемент списка. Довольно часто используют двунаправленные списки, в которых каждый элемент списка содержит указатели как на предыдущий, так и на последующий элемент. Схема двунаправленного связного списка, состоящего из трех элементов, приведена на рис. 8.3.
Рис. 8.3. Пример двунаправленного связного списка из трех элементов в основной памяти
В примере предполагается использовать структурный тип person. Для того чтобы можно было связать отдельные структуры в список, в структурный тип необходимо добавить два указателя:
• на предыдущий элемент списка (prior);
• на следующий элемент списка (next).
Полное описание структурного типа person будет иметь вид:
Последние две строки (см. рис. 8.3) определяют указатели (prior и next) на структуры типа person, т.е. в качестве элементов структуры используются указатели на структуру того же типа. Так как список сотрудников располагается в основной памяти в массиве, содержащем фиксированное количество (100) экземпляров структур типа person, а функции динамического распределения памяти не используются, примем следующие технические решения:
• при подготовке массива структур (т.е. при инициализации базы данных) все элементы массива объединяются в список свободных элементов;
• список занятых элементов вначале пуст;
• при заполнении базы данных в качестве буферного используется первый из свободных элементов массива структур, в него записываются сведения об очередном сотруднике. Затем этот элемент включается в список занятых элементов. Таким образом, в массиве структур будут находиться два связных списка: список свободных элементов и список занятых элементов.
Замечание. Вводимый список сотрудников должен быть упорядочен по алфавиту;
• при удалении сведений о сотруднике из базы данных освободившийся элемент удаляется из списка занятых элементов и возвращается в список свободных элементов.
На рис. 8.4 изображен в рабочем состоянии массив структур, содержащий сведения о сотрудниках. Указатели в первых и последних элементах списков, не указывающие соответственно на предыдущий и следующий элементы, получают значение, равное NULL.
Рис. 8.4. Рабочее состояние массива структур (в списке свободных элементов сейчас только 2 элемента)
Схема, приведенная на рис. 8.5, поясняет процесс удаления элемента из списка занятых элементов. Был удален элемент под номером 2. Физически он остается на месте, но входит после удаления в другой список (свободных элементов), так как указатели на предыдущий и последующий элементы получили другие значения.
Теперь можно приступить к разработке функций, реализующих операции по обслуживанию базы данных. Для этого понадобятся следующее функции:
main( ) - главная функция;
init( ) - инициализация (подготовка) базы данных;
input( ) - ввод сведений о новом сотруднике;
delete( ) - удаление сведений о сотруднике;
print( ) - распечатка базы данных;
save( ) - запись базы данных в файл;
load( ) - загрузка базы данных из файла.
Рис. 8.5. Состояние массива структур после удаления элемента 2 из списка занятых элементов