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

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

е£а   Д

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

681.3(07) К289

СТ. Касюк

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

Конспект лекций

Челябинск 2010

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Южно-Уральский государственный университет

Кафедра информатики

681.3(07) К289

СТ. Касюк

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

Конспект лекций

Челябинск

Издательский центр ЮУрГУ

УДК 681.3(075.8) ББКЧ23.я7 К289

Одобрено учебно-методической комиссией факультета экономики и управления

Рецензенты: д.т.н. B.C. Жабреев, к.т.н. В.Л. Федяев

Касюк, СТ.

СТ. Касюк. — Челябинск: Издательский центр ЮУрГУ, 2010. — 175 с. Учебное пособие по курсу программирования на языке Си написано в соответствии… Цель пособия состоит в поэтапном формировании у учащихся знаний о методах составления программ и выработке навыков…

ПРЕДИСЛОВИЕ

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

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

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

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

В пособии даны программные реализации стеков, списков, очередей и деревьев. Кроме того, приведены программы с использованием динамических информационных структур из книги КерниганаБ. и Ритчи Д. «Язык программирования Си». Раздел сортировки и поиска разработан несколько подробнее других разделов, так приведены прикладные алгоритмы обработки данных, примеры сортировки и поиска данных, расчетные характеристики алгоритмов.

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

Глава 1. Язык программирования Си

Введение в язык Си

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

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

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

Позиции языка Си++ в современном мире. Современные языки программирования:

• Си++ — язык системного программирования;

• Java — язык программирования для Internet и мобильных систем;

• Visual Basic — язык разработки Windows-приложений;

• Delphi — объектно-ориентированный язык Object Pascal. Практически все используемые в мире ключевые программные средства, в

том числе компиляторы, операционные системы, СУБД, системы телекоммуникаций написаны на Си++. Несколько примеров: а) практически все программные продукты Microsoft (Windows XP, Office XP, Internet Exploer, MS SQL Server и др.), б) ведущие продукты Adobe Systems (Photoshop, Acrobat и др.), в) базовые компиляторы Sun, г) графическая оболочка KDE для Linux, д) многие компоненты Mac OS X и т.д. Не вызывает сомнений подавляющее превосходство Си++ в области встроенных систем и индустрии компьютерных игр (Doom III, StarCraft и др.). На Си++ реализованы ведущие поисковые Web-системы и крупнейшие Web-порталы: Google, Yahoo, Amazon и др. Создатель Си++ Бьерн Страустроп приводит следующие аргументы в пользу языка: «Си++ является наилучшим языком для многих приложений, где требуется системное программирование, имеются определенные ограничения по ресурсам и выдвигаются серьезные требования к производительности. Одним из примеров служит Google, другим — встроенные системы для миниатюрных устройств».

Язык Си был разработан американцем Деннисом Ритчи в исследовательском центре Computer Science Research Center of Bell Laboratories корпорации AT&T в 1972 г. Первоначальная реализация Си была выполнена на ЭВМ PDP-11 фирмы DEC для создания операционной системы UNIX. Позже он был перенесен в среду многих операционных систем, обособился и существует независимо от любой из них. Программы, написанные на языке Си, как правило, можно перенести в любую другую операционную систему или на другой компьютер либо с минимальными изменениями, либо вовсе без них.

Диалекты языка Си.Первое описание языка Си дал его автор Деннис Ритчи совместно с Брайном Керниганом в книге «Язык программирования Си». Однако, описание не было строгим и содержало ряд неоднозначных моментов. Разработчики трактовали язык по-разному. Фактически, долгое время стандартом языка служила его реализация в UNIX. Сейчас существуют десятки реализаций языка программирования Си. Они поддерживают разные диалекты языка.

В 1983 г. при Американском Институте Национальных Стандартов (American National Standart Institute — ANSI) был создан комитет по стандартизации языка Си. В 1989 г. был утверждён окончательный вариант стандарта. Однако на сегодняшний день большинство реализаций языка Си не поддерживают стандарт в полном объёме.

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

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

Имя функции — это коллективное имя группы объявлений и операторов, заключенных в фигурные скобки. За именем функции в круглых скобках указываются параметры функции.

Пример функции

 

/*	Первая программа	на Си	. */
#include <stdio.h>
main() г
i	printf("n Здравствуй,	язык	Си!");
}	/* Вывод на экран	сообщения	*/

Результат работы программы

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

Пример программы из нескольких функций

 

#директивы пр	епроцессора
main() {
}
function {	_1(..	.)
}
function {	_2 ( . .	.)
}
function {	n ( . .	.)
}

Функция main может вызывать для выполнения любую другую функцию. Функции function_1, function_2, ..., function_n могут вызвать любую функцию, кроме функции main. Функцию main нельзя вызывать изнутри программы, она является управляющей.

Объекты языка Си и их типы

Имя объекта — это последовательность не более 32 символов а—z, A—Z, О—9 и «_» (подчеркивания). Начальный символ имени не должен быть цифрой.… Помимо имени, каждый объект имеет тип. Указание типа необходимо для того,… Основные типы и размеры данных:

Пример объявления объектов

 

int n;	/*	Переменная п целого типа. */
float xl;	/*	Переменная xl типа с плавающей	точкой.	*/
char a;	/*	Переменная а символьного типа.	*/

Простые объекты

Константа — это ограниченная последовательность символов алфавита языка (лексема), представляющая собой изображение фиксированного (неизменяемого)… Константы бывают следующие: 1) числовые, 2) символьные и 3) строковые. Числовые константы делятся на целые и вещественые.

Пример

50000U —константа типа unsigned int

Константе 50000U выделяются 2 байта вместо четырех, как было бы при отсутствии суффикса. В этом случае, т.е. для unsigned int, знаковый бит используется для представления одного из разрядов кода числа и диапазон значений становится от 0 до 65535.Суффикс L (или /) позволяет выделить целой константе 4 байта.

Совместное использование в любом порядке суффиксов U (или и)иЬ (или /) позволяет приписать целой константе тип unsigned long, и она займет в памяти 32 разряда, причем знаковый разряд будет использоваться для представления разряда кода (а не знака).

Пример

OLU — целая константа типа unsigned long длиной 4 байта

2424242424UL — константа типа unsigned long

Вещественные константы

Константа с плавающей точкой (вещественная константа) всегда представляется числом с плавающей точкой двойной точности, т. е. как имеющая тип double, и состоит из следующих частей [2]:

• целой части — последовательности цифр;

• десятичной точки;

• дробной части — последовательности цифр;

• символа экспоненты е или Е;

• экспоненты в виде целой константы (может быть со знаком).

• Любая часть (но не обе сразу) из нижеследующих пар может быть опущена:

• целая или дробная часть;

• десятичная точка или символ е (Е) и экспонента в виде целой константы.

Примеры

 

345.

3.14159

2.1Е5

.123ЕЗ

4037е-5

По умолчанию компилятор присваевает вещественному числу тип double.

Если программиста не устраивает тип, который компилятор приписывает константе, то тип можно явно указать в записи константы с помощью следующих суффиксов: F (или/) —float для вещественных, U (или и) — unsigned для целых, L (или /) — long для целых и вещественных.

Примеры:

• 3.14159F — константа типа float, занимающая 4 байта;

• 3.14L — константа типа loung double, занимающая 10 байт.

Символьные константы

Символьная константа — это один символ или обратная косая черта и символ, заключенные в апострофы (одинарные кавычки), например: 'z', ' V, ' t' и так далее. Обратная косая черта (слэш) и символ служат для обозначения управляющих символов, не имеющих графического представления, например, 'п' — переход на новую строку, 't' — табуляция. Все символьные константы имеют тип char и занимают в памяти по 1 байту. Значением символьной константы является числовое значение её внутреннего кода.

Строковые константы

Строковая константа — это последовательность символов, заключенная в кавычки, например: "Это строковая константа". Кавычки не входят в строку, а лишь ограничивают её. Технически, строковая константа представляет собой массив символов и по этому признаку может быть отнесена к разряду сложных объектов языка Си. Однако, строковую константу удобнее рассмотреть вместе с другими константами.

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

Поскольку строковая константа состоит из символов, то она имеет тип char. Количество ячеек памяти, необходимое для хранения строковой константы на единицу больше количества символов в ней. Следует отчетливо понимать, что символьная константа и строка из одного символа не одно и то же: Y не есть "х". Первое — это символ, использованный для числового представления буквы х, а второе — строковая константа, содержащая символ х и ''. Если в программе строковые константы записаны одна за другой через разделители, то при выполнении программы они будут «склеены».

Переменные

Переменная — лексема, представляющая собой изображение изменяемого объекта.

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

Пример

тип переменной имя переменной;

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

Пример

int i; /* i - счетчик циклов */

Общий случай объявления переменных

тип переменных имя переменной 1,

имя переменной 2,

имя переменной п;

При объявлении переменных им можно задавать начальные значения — производить инициализацию.

Пример

тип переменной имя переменной = значение;

Примеры

 

int i=0, к, n, m=l;
float x=314.159E-2,	у;
char а='а';

Операции

Над объектами в языке Си могут выполняться различные операции [2]:

1) арифметические;

2) логические;

3) адресные;

4) операции отношения;

5) операции присваивания.

Результат выполнения операции — всегда число.

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

Арифметические операции

Основные двухместные операции, расположенные в порядке уменьшения приоритета:

1) умножение — «*»;

2) деление — «/»;

3) сложение — «+»;

4) вычитание и арифметическое отрицание — «-»;

5) целочисленное деление (вычисление остатка от деления) — «%». Самый высокий приоритет у операции «умножение», самый низкий у

операции «целочисленное деление».

Основные одноместные операции:

1) приращение на единицу — «++»;

2) уменьшение на единицу — «—».

Результат вычисления выражения, содержащего операции «++» или «—», зависит от того, где расположен знак операции (до объекта или после него). Если операция расположена до переменной, то сначала происходит изменение значения переменной на 1, а потом выполняется какая-то операция; если — после переменной, то сначала выполняется операция, а потом значение переменной изменяется на 1.

Примеры:

• а*++Ь — если а=2 и Ь=3, то результат вычислений равен 8, а Ь=А;

• а*Ь++ — если а=1 и Ь=3, то результат вычислений равен 6, а Ь=4.

Логические операции

Логических операций в языке Си три:

1) «&&» — логическое «И» (конъюнкция);

2) «||» — логическое «ИЛИ» (дизъюнкция);

3) «!» — логическое «НЕ» (отрицание).

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

Адресные операции

Адресные операции:

1) определение адреса — «&»;

2) обращение по адресу — «*». Адресные операции являются унарными.

Операции отношения

Операции отношения:

1) равно — « == »;

2) не равно — « != »;

3) меньше — « < »;

4) больше — « > »;

5) меньше или равно — « <= »;

6) больше или равно — « >= ».

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

Операция присваивания

Операция присваиваниявыполняется следующим образом:

1) вычисляется выражение в правой части;

2) тип результата преобразуется к типу объекта в левой части;

3) результат записывается по адресу, где находится объект.

Пример

объект = <выражение>;

Ввод и вывод информации

Функция print/ — функция форматированного вывода. Она переводит данные из внутреннего кода в символьное представление и выводит полученные…

Общая форма записи функции printfQ

Строка форматов состоит из следующих элементов: 1) управляющих символов; 2) текста, который выводится на экран;

V — вертикальная табуляция;

4) 'Ь' — возврат на символ;

V — возврат на начало строки;

Форматы нужны для того, чтобы указывать вид, в котором информация будет выведена на экран. Отличительной чертой формата является наличие символа… Основные форматы: 1) %d— целый формат со знаком;

Пример

printf("n Здравствуй, язык Си!");

Результат работы программы

Здравствуй, язык Си!

Пример

а=5;

printf("n Значение переменной а=%о!.",а);

Результат работы программы

Значение переменной а=5.

Пример

х=2.78;

printf("n Значение переменной x=%f",x);

Результат работы программы

Значение переменной х=2.780000

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

Пример

У=3;

printf("n Значение переменной у=%10.7f",х);

Результат работы программы

В программе 10 — общее количество позиций под значение переменной; 7 — количество позиций после десятичной точки. Функция форматированного ввода данных с клавиатуры scan/ выполняет чтение… Общая форма записи функции scan/

Пример программы

 

scanf("%d", &m);
/* Ввести целое число и присвоить	*/
/* его значение переменной т.	*/
scanf("%lf", &xl);
/* Ввести значение переменной xl,	*/
/* имеющей тип double.	*/

§1.7. ОператорыУсловный оператор if Общая форма записи

if(< выражение>) <оператор 1>;

[else

<оператор 2>;]

Если выражение истинно, то выполняется <оператор 1>, если выражение ложно, то выполняется <оператор 2> (при наличии опции else). Оператор z/может быть вложенным.

Пример

 

if	(key ==	1)
	printf("n	Выбран первый	пун]	<т ") ;
el	зе if (key	==	2)
	printf(	"n Выбран	ВТ	орой	пункт");
	else
	printf(	"n Первый	и	вторе	эй	пункты	не
			выбраны") ,

Возможно использование оператора if без опции else. При использовании обеих форм оператора z/Ъпция else связывается с последним оператором if.

Пример

 

if	(key!= l) if (key ==	2)
	printf(	"n	Выбран	второй	пункт");
	else
	printf(	"n	Первый и	второй	пункты	не
	выбраны	") ;

Если <onepamopl> или <оператор2> должны состоять из нескольких операторов, то необходимо использовать составной оператор (блок).

Пример

if (key =

{

n=n+l; m=l+r;

}else

{

m=m-1;

n=l-r; }

Оператор ветвления switch

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

Общая форма записи

  <оператор1>; break; case <константное выражение2>: <оператор2>; break; default: } … Оператор выполняется следующим образом: 1) вычисляется выражение в скобках оператора switch;

Общая форма записи

Если выражение истинно (т. е. не равно нулю), то выполняется оператор или группа операторов, входящих в цикл while; затем выражение проверяется… Цикл while — цикл с предусловием, поэтому вполне возможно, что тело цикла не…

Пример

 

к=5;
п=10;
while(к<п)
{
printf("k=%d n=%dn",	к,	п) ;
к+=2;
к=к+2;
п++;
}

Цикл do...while

Общая форма записи

do <оператор>; while(<выражение>);

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

Пример

 

printf("п	Введите число	10") ;
do	scanf(	"%d",&number);
whi	le(number !=10);

Пример

 

do
{
	printf("	Введите	n>0");
	scanf("%	d", &n);
}
while (n<0)	r

Цикл for Общая форма записи

for( <инициализация>; <проверка условия>; <коррекция> ) <оператор>;

Цикл for — цикл с фиксированным числом повторений. Для организации такого цикла должны рассматриваться три операции:

• инициализация счетчика;

• сравнение его величины с некоторым граничным значением;

• изменение значения счетчика при каждом прохождении тела цикла.

Эти три операции записываются в скобках и разделяются точкой с запятой. Первое выражение служит для инициализации счетчика. Инициализация осуществляется только один раз — когда цикл for начинает выполняться. Второе выражение — для проверки условия перед каждым возможным выполнением тела цикла. Когда выражение становится ложным (равным нулю), цикл завершится. Третье выражение вычисляется в конце каждого выполнения тела цикла. Счетчик может как увеличиваться, так и уменьшаться.

Пример

 

 

main () { int num;
for( num=l; num<=5; num++ )
printf(" % 5d % 5d n",	num,	num*num);
}

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

Пример

for (х=1;у<=35;у=5*х++ +10)

printf ("%10d %10о! п", х, у);

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

Пример

 

к=2;
for( n=3; k<=25;	)
{
к = к*п;
}

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

Пример

for(i=0, j=l; i<n; i++, j=i);

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

Пример

 

for (	i=	= 0;	i<n;	i++)
{
	for	( j =	=0; j	<n; j	+ +)
	{
	}
}

Рекомендации по выбору цикла

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

Операторы break и continue

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

Пример

while(<выражение>; {

break;

Пример

while(<выражение>^ {

continue;

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

Пример

 

main ( )
{
	int i,	j;
	float	k;

 

	printf(" Введите j");
	scant("%d", &j );
	for {	( i = -5; i <= 5; i++)
	if( i==0 )
		continue;
}	}	printf("n %d/%d =%f ",	j Д,	k=j/i);

Оператор безусловного перехода goto Общая форма записи

goto метка;

метка : <оператор> ;

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

Пример

 

if	(	size	>	12)
	gc	)tO	a;
el	se
	gc	)tO	b;
а:	cost	=	cost*3;
fl	ag=	= 1;
b:	s=	= cons	t*	'flag;

Использование goto в программе крайне нежелательно, так как он усложняет логику программы. Язык Си реализован таким образом, что можно программировать без оператора goto.

Функции

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

Определение функции

Каждая функция в языке Си должна быть определена, т. е. должны быть указаны:

• тип функции;

• имя функции;

• информация о формальных параметрах;

• тело функции.

Существует два формата определения функции — современный стиль определения функции и старый стиль определения функции [5].

Современный стиль определения функции

 

 

тип функции имя функции	(объявление формальных
	параметров через
{ /* тело функции */	запятую)
return(<выражение>); }

Старый стиль определения функции

параметров через запятую) объявление формальных параметров; {

5 -

=г :

ж

I «9 Г-

Х1

Х2

Хп

 

ЧЁРНЫЙ ЯЩИК

типФункция

(тип Х1, тип Х2....... тип Хп)

{ тело функции }

Р

Возврат значения в точку вызова return <выражением

Рис. 1.1. Схема работы функции

Пример функции вычисления факториала

#include <stdio.h> /* Определение функции factorial()*/ double factorial(double i)

{

double j,k;

k=l;

for (j=2;j<i+l;j=j+l)

k=k*j; return k; /* Возврат в программу */ /^вычисленного значения */ }

/* Главная функция*/ main()

{

double i;

printf("n Введите целое числоп");

scant("%lf",&i);

printf("n%lf!=%lfn",i,

factorial (i)); }

Результат работы программы

7.0000001=5040.000000 Вызов функций Общий вид вызова функции имя функции(<список фактических параметров>);

Пример использования return в середине функции

void function() {

return; }

В примере оператор return завершает выполнение функции function и передает управление в вызывающую функцию. Никакое значение при этом не передается.

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

Пример функции определения максимума из двух чисел: а = b*max(xy);

 

int max(int a,	int b)
{
if (a>b)
return	(a) ;
else
return	(b) ;
}

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

Пример функции, не возвращающей значения: spravka(a);

 

void spravka	(float a)
{
}

Прототипы функций

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

Пример объявления функции модуля числа

int abs(int); int abs(int i);

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

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

При программировании на языке Си широко используются библиотечные функции. Эти функции были предварительно разработаны и записаны в состав системы программирования. Прототипы библиотечных функций находятся в специальных заголовочных файлах с расширением h (head), которые необходимо подключать с помощью директивы Mnclude.

Рассмотрим пример программы генерации таблицы чисел 2^й.

Пример программы

 

#include <stdio.h>
int power(int base; int index);
/* int	power(int, int); - второй вариант	объявления
функции	power().*/
main ()
{
int	i;
for	( i=0; i <= 10; i++ )
{	printf("%d, ", power(2,i));
}
}
int power(int base; int index)
{
int	if p;
p=l	r
for	( i=0; i <= 10; i++ )
{	p = p * base;
}
return (p);
}

Результат работы программы

1, 2, 4, 8, 16, 32, 64, 128, 252, 504,

Схема программы представлена на рис. 1.2.

( начало 1

F начало J

                              … Объявле­ние Р, i I

Формальные параметры функции

I Р=2 | i<=index;H-i- |

Цикл

return p;

I начало I

а)

6)

Рис. 1.2. Схема программмы: а — функция main; б — функция возведения в степень power

Препроцессор

Работа препроцессора осуществляется с помощью специальных директив (команд). Они отмечаются знаком «решетка» — «#». Основными директивами… Директива Mnclude позволяет включать в текст программы указанный файл. Если… Mnclude "func.c" . Можно также задать путь к файлу. Если имя файла записано в угловых скобках «<> »,…

Пример

#include <math.h> #include "fact.с"

Директива #define позволяет вводить в текст программы макроопределения.

Общая форма записи

#define что менять на что менять

Замена будет произведена на нулевом этапе компиляции. Символы «что менять» будут изменены на символы «на что менять».

Пример

#include <stdio.h> #define pi 3.1459265 main ()

{

double x,y;

printf("n введите угол в радианах"); scanf("%lf", &x);

y=(180*x)/pi;

printf("n синус угла %lf в градусах %lf равен", у, sin(x));

}

Математические функции

Основные математические функции стандартной библиотеки [4] приведены в табл. 2.2. Таблица 1.2 Основные математические функции

Специальные операции

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

1) операция вычисление размера объекта sizeof,

2) операция «запятая» — « , ».

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

Общая форма записи

sizeof(объект)

Пример программы

 

 

#include <stdio.h>
#define pi	3.14159625
main() { int x;
printf(	"n Размер	памяти	под	целое	число	с	Id	байт.",
sizeof(	int));
printf(	"n Размер	памяти	под	тип	double	%d	байт.",

	sizeof(double));
	printf("n Размер	памяти под переменную %d байт.",
	sizeof(x));
	printf("n Размер	памяти под константу pi %d байт.",
}	sizeof(pi));

Операция «запятая»( « , » ) предназначена для связывания между собой выражений. Список, разделенный запятой, трактуется как единое выражение и вычисляется слева направо.

Пример

 

main()
{
int x=3, у;
у=3, 4*х;
printf ("n Значение y=%d.",	у);
}

Результат работы программы

Значение у=12

Пример

main()

{

int i, b;

for (i=0, b=l; i <= 5;i++

{

b=b+i;

printf("n Значение b=%d.",b);

 

Результат работы программы

Значение b=l

Значение b=2

Значение b=3

Значение	Ь=	= 4.
Значение	Ь=	=5.
Значение	Ь=	= 6.

Глобальные и локальные объекты

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

Пример программы

#include <stdio.h> void autofunc(void)

{

int k=l;

printf("n k = %u", k); k=k+l; }

main()

{

int i;

for(i = 0; i<=5; i++) autofunc();

}

Результат работы программы

 

к=
к=
к=
к=
к=
к=

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

Пример

 

#include <stdio.h>
int k=l;
void autofunc(void)
{
	printf("n k = %u'	', k);
	k=k+l;
}
main()
{	int i;
	for (i = 0; i<=5;	i + +)
	autofunc ();
}

Результат работы программы

 

k =
k =
k =
k =
k =

к = б

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

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

 

#include <stdio.h>
int func(int xl, int x2)
{
int y;
y=xl+x2;
return(y);
}
main()
{
int xl, x2;
c=func( xl, x2);
/* вызов функции	*/
}

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

 

#include <stdio.h>
int xl, x2;
int func(void)
{
y=xl+x2;
return(y);
}
main()
{
xl=...; /*	изменение значений	*/
Xz, •••/' /	глобальных */
/*	переменных */

	...
	c=func() ;	/*	вызов функции */
}

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

Модификация объектов

Модификатор unsigned. Предназначен для того, чтобы объявлять переменные типов short, int, long беззнаковыми. Если переменную сделать беззнаковой, то…

Пример

-32768 <= int i <= 32768

О <= unsigned int i <= 65535

Пример

unsigned int i; unsigned long j;

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

Пример

 

main()
{
int i,j;
long k;
i= 30000;
j= 20000;
k= i+j; /^ОШИБКА!!	i -k /

printf("n%d+%d=%ld", i , j, k) ; }

Несмотря на то, что к объявлена как long, результат вычисления выражения

i+J получается типа int, поскольку / и j объявлены как int. В то же время значение

выражения выходит за границу типа int. Для того, чтобы не было ошибки,

необходимо модифицировать переменные следующим образом:

k=(long)i+(long]j;.

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

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

Пример

extern тип объект 1, объект 2, ... ,объект п;

Модификация расположения объектов в оперативной памяти

Если объект расположен по некоторому фиксированному адресу, то он называется статическим (типичный пример — глобальные переменные). Объект, который располагается в произвольном месте оперативной памяти,… Переменные, объявленные с модификатором static сохраняют свои значения при входе и выходе из функции, однако не…

Пример

 

#.	include <stdio	.h>
void stat(	void)
{
	static	int k=	= 1;
	printf	("t	k=%d"	,k) ;
	k++;
}

main()

{ int i;

for( i=0; i<5; i++) stat (); }

Результат работы программы

Переменная к в функции stat зафиксирована в оперативной памяти. Инициализация к проводится только один раз — при первом вызове функции переменной к… Модификатор register. Модификатор предназначен для того, чтобы поместить…

Пример

register int i;

Объявление переменных с модификатором register приводит к помещению переменной в регистр, если регистр свободен.

Модификатор const предназначен для объявления объектов как неизменяемых. Объекту, который объявлен с данным модификатором, можно присвоить только одно значение.

Пример

const double pi = 3.14159265;

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

Указатели

объект. Указатели широко используются при программировании на языке Си. Программы с указателями — короткие и очень эффективные. Указатели… 1) для доступа к ячейкам оперативной памяти и создания новых объектов в ходе… 2) для доступа к сложным элементам данных;

W.

указатель Р

Рис. 1.3. Графическое представление указателя Указатель, как и любая переменная, должен быть объявлен.

Общая форма объявления указателя

тип *имя объекта;

Пример объявления указателя

int *p; char *p;

Тип указателя — это тип переменной, адрес которой он содержит. Для работы с указателями в Си определены две операции:

1) операция «*» (звездочка) — позволяет сгенерировать значение объекта по
его адресу;

2) операция «&» (амперсант) — позволяет определить адрес объекта.
Операция «&» выдает адрес объекта, так что запись

р=&с; присваивает переменной р адрес ячейки, в которой размещается значение переменной с.

Операция «*», применённая к указателю, выдает значение объекта, на который данный указатель ссылается, например:

к=*р; —переменной к присваивается значение, размещенное по адресу, содержащемуся в указателе/?.

Пример

#include <stdio.h> main ()

{

int a, *b;

a=134; b=&a;

printf("n Значение переменной а равно %d.", a); printf("n Адрес переменной а равен %p.", &а); printf("n Данные по адресу указателя b равны

%d.",*b); printf("n Значение указателя b равно %p.",b); printf("n Адрес расположения указателя b равен

%p.", &b) ; }

Результат работы программы

Модели памяти

Системы программирования для шестнадцатибитной среды DOS предоставляют шесть стандартных моделей памяти [4]: 1) крошечную (tiny); 2) маленькую (small);

Массивы

Массив — это упорядоченная последовательность величин, обозначаемая одним именем. Упорядоченность заключается в том, что элементы массива… контейнеров повешен ярлык с именем массива data. Контейнеры в такой…

Возрастание адресов

>

 

. . .

...

п-2

п-1

...

Массив data[n], n — константа

Рис. 1.4 Пример

data[2]=32;

/^Второму элементу массива */ /*с именем data присваивается */ /^значение 32.*/

Элементы массива могут употребляться в программе так же, как и простые переменные.

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

Общая форма объявления массива

тип имя[размер массива];

Пример

float data[245];

Здесь массив содержит 245 элементов типа float: data[0], data[], data[2], ..., data[244].

Связь массивов и указателей

Имя массива фактически является константой-указателем на начальный адрес данных — на адрес расположения элемента массива с нулевым индексом.

Графическое представление массива в памяти ЭВМ представлено на рис. 1.5, где data — адрес начала массива; sizeojidatd) — размер массива data в байтах; sizeojifloat) — размер памяти под один элемент массива в байтах; р и р! — указатели для работы с массивом.

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

Возрастание адресов

о

Адрес

Начала

массива

Массивdata

 

о

р1 =data р2 = р1 + i

4 *

 

дпошаШЭЕ!

П-1

 

_Р2-р1

-I

Sizeof(float)

sizeof(data) ■*i Рис. 1.5

Общая форма инициализации массива при объявлении

 

тип

имя[п]

={ значение 1, значение 2, значение 3, • • • i значение п};

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

Пример инициализации массива

# include <stdio.h> main ()

{

int data [5] ={5, 4, 3, 2, lb-float a[ ]={3, 4, 2, 7, 18, 90}; char p[ ]={'f, 'f, 'c', 't', ^f'}; char *q;

q=p-

printf("n Размер массива data %u байт.", sizeof(data));

printf("n Размер массива a%u байт.", sizeof(a] printf("n Размер массива p%u байт.", sizeof(p] printf("n Адрес массива р равен %р.", р); printf("n Адрес в указателе q равен %р.", q);

}

Цикл последовательного ввода значений элементов массива удобно организовать с помощью оператора/ог.

Пример

#include <stdio.h> main ()

{

int data[5], *p, j; p=data;

for (j=0; j<=4; j++)

{

printf("n Введите элемент массива" printf("data[%d] = ",j); scanf("%d", p+j);

Передача массива в функцию

Обычно параметры функций в языке Си передаются как копии. Если внутри функции произойдет изменение значения параметра, то это никак не отразится на… Рассмотрим пример программы, в которой функция modify увеличивает на 1…   #include <std io .h>   void modify(i { int i; …

Многомерные массивы

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

Общая форма объявления многомерного массива

[индекс 2] [индекс п]; Элементы многомерного массива располагаются в последовательных ячейках оперативной памяти по возрастанию адресов.…

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

  # include <std. LO . h>           main (… Ошибка, содержащаяся в программе, одна из наиболее распространенных. По… инициализирована, то в ней хранится неизвестное число, и запись *х=6 приводит к тому, что по неизвестному адресу…

Динамическое распределение памяти под массивы

Пример 1.Рассмотрим работу с массивом без динамического распределения оперативной памяти. main () {

J-

Графическое представление размещения двухмерного массива в

оперативной памяти представлено на рис. 1.7.

 

 

 

 

 

 

Указатель b	Память ЭВМ b=(f loat*) m a 11 oc{s izeof (f loat)*n*m); Строка 1 Строка 2 Строка п
=й	1 2 3|... m|1 |2 3 ... m........................ |1 |2 3 |... m
m*sizeof{fl	n*m*sizeof(float)

Рис. 1.7

Программа

{ float *b; int n, m, i, j ;

Массивы указателей

Рассмотрим вначале как можно разместить в оперативной памяти матрицу со строками одинаковой длины.Чтобы создать в памяти ЭВМ двухмерный массив…

Ьш,

где / — номер строки;7 — номер столбца.

МАССИВ

УКАЗАТЕЛЕЙ

*Ь[п]

ХРАНЕНИЕ

АДРЕСОВ

СТРОК

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

				Строка 0
			■ т ш	m-1
		Строка 1
			■ ■ ■	m-1
		^ьц][1] обращение к
■ ш ш	элементу массива Строка п-2
п-2
			■ ■ ■	m-1
		Строка п-1
п-1
		1	...	m-1

m - количество столбцов

n - количество строи

Рис. 1.8

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

#include <alloc.h> #include <stdio.h> main()

float **b;

int n, m, i, j ;

printf ("n Введите количество строк: п="); scanf ("%d", &n);

printf ("n Введите количество столбцов: m="); scanf ("%d", &m);

b=(float**)malloc( n*sizeof(float*) ); /*Выделяется блок оперативной памяти */ /*для хранения адресов строк матрицы.*/ /* Используется двойная косвенная адресация.*/

for(i=0; i<=n-l; i++)

*/ Ь.*/

b[i]=(float*)malloc( n*sizeof(float) ); /*B цикле динамически выделяются блоки*/ /*оперативной памяти под строки. Адреса /*строк записываются в массив указателей

for(i=0; i<=n-l; i++) for(j=0; j<=m-l; j++)

{

printf ("n введите элемент b[%d][%d]=",

i + 1, j+1);

scanf ("%f", &b[i][j] ) ; }

for(i=0; i<=n-l; i++) for(j=0; j<=m-l; j++) {

b[i] [j]= /* обработка массива */

}

}

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

размеры строк. Фрагмент программы, в которой реализуется динамическое размещение такой матрицы приведен ниже [12].

#include <stdio.h> #include <alloc.h> main()

{

float **b; int i, j, n; int *m;

printf("n Введите количество строк: п= "); scant("%u", &n);

b=(float **)malloc( n*sizeof(float*) ); m=(int *)malloc( n*sizeof(int) );

for(i=0; i<=n-l; i++)

{

printf("n Введите длину строки: m[%u]=", i+1);

scant("%u", m+i) }

for(i=0; i<=n-l; i++)

b [i] = (float*)malloc( m[i]*sizeof(float) );

for(i=0; i<=n-l; i++) for(j=0; j<=m[i]-l; j++)

{

ii

printf("n Введите элемент b[%u][%u]

i+1, i+1);

scant("%f", &b[i][j]); }

for(i=0; i<=n-l; i++) for(j=0; j<=m[i]-l; j++) {

b[i] [j]= . . . }

Графическое представление двухмерного массива со строками разной длины представлено на рис. 1.9.

МАССИВ

УКАЗАТЕЛЕЙ

*Ь[п]

ХРАНЕНИЕ

АДРЕСОВ

СТРОК

О

П-2

П-1

Строка О

Т

Строка

т[1]-1

Строка 2

т[2]-1

Строка п-2

т[п-2]

С т р ока п-1

т[0]-1

т[п] - массив для хранения размеров строк

л - количество строк

т[п-1]

Рис. 1.9 §1.23. Структуры

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

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

Пример — строка платёжной ведомости, которая содержит следующие сведения о работнике: полное имя, адрес, зарплату и так далее.

Таким образом, структура — сложный тип данных, составленный из простых типов.

Общая форма объявления структуры

После закрывающей фигурной скобки « } » в объявлении структуры обязательно ставится точка с запятой.

Пример объявления структуры

 

St	ruct	date
{
	int	day;
	int	month;
	int	year;
};

Элементы структуры располагаются в памяти ЭВМ в том же порядке, в котором они объявляются.

При объявлении структур, их разрешается вкладывать одну в другую.

Пример

 

 

St {	ruct persone
char	fam[20]	r
	char	im[2 0];
	char	ot[20];
	struct date	bd;
};

Здесь одним из элементов структуры persone является структура типа date с именем структурной переменной bd (birthday).

Инициализация структуры может осуществляться двумя способами:

• присвоение значений элементам структуры в процессе объявления переменной, относящейся к типу структуры;

• присвоение начальных значений элементам структуры с использованием функций print/n scan/.

В первом случае инициализация осуществляется по следующей форме:

struct тип структуры имя переменной= {значение элемента 1, значение элемента 2,

значение элемента п};.

Второй случай не отличается от способа инициализации объектов языка Си уже известных типов.

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

имя_переменной.имя_элемента.

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

Пример

struct complex_type

{

double real;

doubl imag; } number;

В этом примере элементами структуры будут переменные number.real и number imag.

Пример 1.Объявление и инициализация структуры

 

 

/*	Объявление структуры	comput	er, */
/*	состоящей из	двух элементов	: model и memor	y.*/
St {	ruct computer
char model[30];
};	int memory;
/*	Объявление и	инициализация	переменной*/
/*	Elecom типа computer.	*/
St	ruct computer	Elecom =	= {"IBM	PC	Pentium 4",	1024};

Пример 2.Объявление и инициализация структуры

 

 

 

#include <stdio.h>
main () { /^Объявление структуры типа data.
*/
struct data { int day;
char month[10];

 

int year; };
/^Объявление структуры типа person;*/
/*одним из элементов структуры person*/
/^является структурная переменная bo! типа	data.*/
struct person { char fam[20];
char im[20];
char ot[20];
struct data bd; };
/^Объявление структурной переменной indl*	/
/*типа person.*/
struct person indl;
printf ("n Укажите через Enter фамилию,	имя,
отчество,");
printf ("n День, месяц и год рождения гражданина
indln");
/* Ввод сведений о гражданине indl. */
scant ("%s%s%s%d%s%d", indl.fam, indl.im,	indl.ot,
&indl.bd.day, &indl.bd.month. &indl.bd.ye	ar) ;
/* Вывод сведений о гражданине indl. */
printf ("nn Сведения о гражданине indl:	nn");
printf ("Фамилия, имя, отчество: t%s %s	%st n",
indl.fam, indl.bd.month, indl.be }	.year);

Объединения

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

Общая форма объявления объединения

{ тип имя объекта 1; тип имя объекта 2; тип имя объекта п; } имя переменной;

Пример

 

 

 

#include <stdio.h>
union data record { char s[4];
int i;
char c;
} data;
main () { printf("пРазмер памяти под
объединение data record
%d байтп", sizeof(data));
printf("пАдреса переменных:	ns t %pn%i t %p n

%c t %p n", data.s,&data.i,&data.c]

Результат работы программы

Размер памяти под объединение data record 4 байт

Адреса переменных: s 0552 i 0552 с 0552

Битовые поля

В Си под объект типа unsigned int, как правило, отводится два байта памяти, т. е. 16 разрядов. Эти 16 разрядов (бит) можно разбить на битовые поля,…

РАЗРЯДНАЯ СЕТКА

P^Tl P^Tir^Tl П^ПРГЯ1 ГГоЦпэ~пГ^Г1 ПП1 ГёЦr^Hn^Tl Г^ИГ^ИГП1

S

J L

JL

J L

j

J L

Рис. 1.10

Здесь под переменные / и s выделено по два бита памяти, под переменные р и к по три бита, под переменную j шесть бит. При работе с битовыми полями нужно внимательно следить за тем, чтобы значение переменной не потребовало памяти больше, чем под неё выделено.

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

Программа

  2;   unsigned j 6;   unsigned к 3;   unsigned p …   = 3;   my field.j = 20; … В результате выполнения программы в ячейке памяти будет размещен код, показанный на рис. 1.11.

РАЗРЯДНАЯ СЕТКА

наш

15ЦГТ4] ЩЩ

0 0 0 0

еюаааа

[31 [21

I _ Is. I _ К

О о

1 1

 

JL

JL

J L

JL

J

Рис. 1.11. Содержимое участка памяти, отведенного под структуру struct field type

На экран будет выведено следующее число:

1-2¹¹ + 1-2 ⁹+ 1-2 ⁶+ 1-2 ⁴+ 1-2¹ + 1-2 ° = 2643.

Указатели и структуры

Возможны три способа доступа к полям [4]: 1) <выражение>.<идентификатор>, где <выражение> — значение… 2) <выражение> -> <идентификатор>, где <выражение> — указатель на структуру или объединение;…

Пример

 

 

/*	Объявление структуры	типа book.*/
St {	ruct book
char title [15];
	char author [15];
};	float value ;
/*	Объявление массива ст	руктур типа book,*	/
/*	состоящего из 100 элементов. */
/*	Имя массива libry. */
St	ruct book libry [100];
/*	Объявление указателя	на структуру типа	book.*/
St	ruct book *p;
/*	Инициализация указателя р адресом*/
/*	0-го элемента массива	структур типа	book	*/
р=	&libry[0];

Для организации работы с массивом можно использовать указатель р или имя массива:

1) (*р).value, что равнозначно записи libry[0].value; 2)р-> value, что равнозначно записи libry[0].value.

Инициализация структур без указателя

Инициализация массива структур при помощи указателя р

Указатель р содержит адрес начала массива— адрес нулевого элемента массива структур типа book. Используя р, можно осуществить доступ к каждому полю… p=p + i;. Графическое представление массива структур в памяти ЭВМ показано на рис. 1.12.

Классификация функций ввода-вывода

Функции ввода-вывода позволяют:

1) читать данные из файлов и устройств ввода информации;

2) записывать данные в файлы и выводить их на устройства вывода информации.

Существуют три класса функций ввода-вывода:

1. Функции ввода-вывода верхнего уровня.Для данных функций характерен потоковый ввод-вывод информации.

2. Функции ввода-вывода для консольного терминала и порта.Ввод и вывод осуществляется путем непосредственного обращения к устройствам персонального компьютера.

Функции ввода-вывода нижнего уровня.

При считывании из файла информация сначала загружается в буфер, а затем записывается в переменные и массивы, определенные в программе (рис. 1.13). … Буферизация используется для того, чтобы снизить количество обращений к… Для отражения особенностей организации ввода-вывода информации вводится специфическое понятие «поток».

Программа

Поток — это абстрактное понятие, относящееся к любому переносу данных от источника данных к получателю данных. Ввод информации от источника… Потоков в языке Си пять. Когда программа будет начинать выполняться,… • стандартный ввод (stdin);

Функции ввода-вывода высокого уровня

До сих пор мы использовали только две функции из стандартной библиотеки функций ввода-вывода: 1) функцию print/— функцию форматированного вывода; 2) функцию scan/— функцию форматированного ввода.

Пример

 

printf ("n %s %s %sn", "Я",	"учусь",	"в ЮУрГУ");
char *а="Я учусь в ЮУрГУ";
printf(a);

Пример

#include <stdio.h>

main ()

{

char namel[40], name2[ll]; int count;

printf("Введите два именип"); count = scant("%s%4s",namel,name2); printf ("n Введено %d имени %s и %s n", count, namel, name2); }

Результат работы

 

Введите	два имени
Саша <Enter>
Александр	<Enter>
Введено		имени Саша	и	Алек

Функция scanfQ

Функции scanf работает со строками через формат %s. Данные читаются из стандартного потока stdin; чтение строки символов производится до тех пор,… Продолжаем рассматривать функции ввода и вывода из стандартной библиотеки… Рассмотрим функции, позволяющие осуществлять текстовый ввод и вывод. Текстовый ввод-вывод имеет дело с потоком литер…

Пример

c=getchar ();

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

Функция putchar записывает символ с кодом с в выходной поток stdout. Обращение к putchar приводит к печати одной литеры. Например, putcharic) выводит на экран одиночный символ с кодом с.

int putchar(с); int с;

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

Программа

#include <stdio.h>

main()

{

int a;

a=getchar();

while(a!=EOF)

{

putchar(a);

a=getchar(); }

}

Работа программы

          начало     ■ i   …     ■'     … Рис. 1.14

Работа с файлами данных

При открытии файла с помощью функции /open возвращается указатель на структуру типа FILE, который можно использовать для последующих операций с…   #include <stdio.h>     … Функция /open открывает файл, имя которого задается аргументом пате, и связывает с ним поток для выполнения операций…

Пример

fclose(f);

Функция feof определяет достигнут ли конец файла. Если конец достигнут, то операция чтения будет возвращать значение EOF до тех пор, пока поток не будет закрыт.

#include <stdio.h> int feof(f); FILE *f;

Возвращаемое значение:

1)0 — если конец файла не найден;

2) ненулевое значение, если достигнут конец файла.

Функции ввода-вывода, работающие с файлами

  #inc lude <stdio .h> int fgetc(f);   FILE *f; … Возвращаемое значение: 1) код прочитанного символа;

Функции обработки строк

Основные функции стандартной библиотеки string.h [4]: • char *strcat(s, ct) — присоединяет ct к s; возвращает s; • char *strncat{s, ct, n) — присоединяет не более п литер ct к s, завершая s литерой ''; возвращает s;

S;

• char *strncpy(s, ct, n) — копирует не более п литер строки ct в строку s; возвращает s; дополняет результат литерами '', если литер в ct больше п;

• int strcmpics, ct) — сравнивает cs с ct; возвращает значечние, меньшее нуля, если cs меньше ct; значение, равное нулю, если строка cs эквивалентна строке ct; и значение, большее 0, если cs больше ct;

• int strncmp(cs, ct, n) — сравнивает не более п литер cs и ct; возвращает значение, меньшее 0, если cs меньше ct; О, если строка cs эквивалентна строке ct; и значение, большее 0, если cs больше ct;

• int strlen{s) — выдает число символов в строке s без учета нулевого символа конца строки;

• char *strlwr(s) — переводит всю строку s в нижний регистр (в строчные буквы);

• char *strset(s, с) — заполняет всю строку s в верхний регистр (в прописные буквы);

• char *strdup(s) — вызывает функцию malloc и отводит место под копию s;

• char *strset(s, с) — заполняет всю строку символами, код которых равен значению с;

• char *strnset(s, с, п) — заменяет первые п символов строки s на символы, код которых равен значению с;

• char *strpbrk(s, t) — просматривает строку s до тех пор, пока не встретится символ, содержащийся в t;

• int strspn{s, i) — возвращает длину начального сегмента строки s, который состоит исключительно из символов, содержащихся в строке t.

Работа со строками

1) как строковые константы; 2) как массивы символов; 3) через указатель на символьный тип;

Результат работы

Подожди немного, отдохнешь и ты.

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

while( ^reason != '' ) /^Останов в конце строки.*/

{

putchar( *(reason++) );

}

/^Печать символа*/

/*и перемещение указателя.*/

Результат работы

Явное задание размера памяти.При объявлении массива можно указать: char ml[36] = "В полдневный жар в долине Дагестана"; вместо char ml[ ] = "В полдневный жар в долине Дагестана"; . Число… Массивы символьных строк

Пример

char *name;

scanf("%s", name);

Данная программа содержит ошибку, поскольку ЭВМ запишет строку по неизвестному адресу, так как *пате не инициализирован. Возможно «зависание» компьютера.

Пример

 

char	-k	name;
name	=	(char	*)mall	oc	(10);
scan	f (	II Q. _ II О О f	name);

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

 

char	-k	name;
name	=	(char	*)malloc	(10);
scan	f (	"%9s",	name);

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

Функция gets получает строку от стандартного устройства ввода системы. Функция читает символы до тех пор, пока не встретится символ новой строки 'п', который создается при нажатии клавиши <Enter>. Функция берет все символы до (но не включая) символа новой строки, присоединяет к ним нулевой символ '' и передает строку вызывающей программе [4].

/^Получение имени №1.*/ main ( )

{

char name[81]; /^Выделение памяти под строку.*/

printf("Привет, как вас зовут?п");

gets (name);

/*Размещение имени по адресу name.*/

printf("Хорошее имя, %s.n" , name); }

Функция примет любое имя (включая пробелы) длиной до 80 символов.

 

 

/^Получение имени №2.*/
main ( ) { char name[80];
char *ptr;
printf("Привет, как вас	зовут?п");
ptr = gets(name);
printf("%s? Ax! %s!n", }	name, ptr);

Получился диалог

Функция scan/. Основное различие между scarify gets заключается в том, как они определяют, что достигли конца строки; scan/ предназначена скорее для… Существует два варианта использования функции scan/[4]: 1. Если применять формат %s, строка вводится до (но не включая) следующего пустого символа (пробел, табуляция или…

Программа

Два примера работы программы

Введите, пожалуйста, два имени:

Наталья Анна <Enter>

Я считал 2 имени Наталья и Анна.

Введите, пожалуйста, 2 имени.

Наталья Кристина <Enter>

Я считал 2 имени Наталья и Кристи.

Во втором примере были считаны только первые 6 символов от Кристины, так как использовался формат %6s.

Если с клавиатуры вводится только текст, лучше применять функцию gets. Она проще в использовании, быстрее и более компактна. Функция scanf предназначена в основном для ввода смеси типов данных в некоторой стандартной форме. Например, если каждая вводимая строка содержит наименование инструмента, количество его на складе и стоимость каждого инструмента, можно использовать функцию scanf

В следующем примере размер массива символов запрашивается у оператора.

Пример

int n;

char *p;

printf(	"пСколько	букв	в	Вашем	имени?" ) ;
scanf (	"%u", &n);
p=(char	*)malloc( n+1 ),
printf(	"пВведите	Ваше	имя: ");
scanf("	%s", p);

Вывод строк

Для вывода строк наиболее часто используют функции puts и printf.

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

Программма

  strl [ ]="Ma( :сив инициализирован мной."; char *str2="Указатель …

Результат работы программы

Я строка #define. Массив инициализирован мной. Указатель инициализирован мной.

Результат работы программы

Содержимое памяти ЭВМ

Строка сим''олов''

Программа объединения двух строк [14]

#include <stdio.h>

#include <string>

char flower[40];

char addition[]="ы хорошо пахнут";

/^массив добавка*/

main()

{

puts("Назовите ваш любимый цветок"); gets(flower);

strcat(flower,addition);

puts(flower); }

Результат работы программы

Замечание: массив flower должен содержать достаточно места, чтобы поместить addition. Программа сравнения двух строк [14] #include <stdio.h> #include <string.h> #define reply "Грант"

Логический тип данных в языке Си

1) истина — (1 или TRUE); 2) ложь — (0 или FALSE). На первый взгляд логического типа данных в языке Си нет. К этому выводу можно прийти, если рассматривать типы…

Программа

 

#include <stdio.h>
main()
{
printf("!2=%u",	!2);
}

Результат работы программы

Логические операции «И», «ИЛИ» и «НЕ» позволяют создавать функции алгебры логики Y=f(X,X2,...,Xn), в которой XI, XI, ...., Хп — логические переменные,… Пример.Представим, что нам необходимо сконструировать устройство для запуска двигателя лифта. Для этого необходимо…

Программная реализация стека

  Кннга2     f V     Книга (N-2)  

Значение указателя

На стек

-------- v--------

Стек (структура, состоящая ш int info н указателя на саму себя)

Анализ работы функции push приведен ниже. Шаг1. С помощью строки STACK*stl = NULL; объявляется указатель, который содержат адрес структуры типа stack. Указатель st инициализируется значением константы…

Блок памяти

Адрес 2024 Адрес 2026

new item=2024 info=1200nest=*s next=NULL

В указатель stl помещается число new item

stl=2024 Рис. 1.23 Для иллюстрации работы программы построим таблицу (табл. 2.6).

Результат работы программы

Резюме: 1. Каждый элемент стека содержит два поля: поле информации info и поле… 2. Поле адреса содержит указатель на следующий элемент стека.

Глава 2. Структуры данных

Введение в структуры данных

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

Переменные, массивы, структуры, объединения при объявлении получают имя и тип — под них выделяются ячейки оперативной памяти, в которые можно записывать некоторые значения. Таким образом, данные объекты имеют неизменяемую (статическую) структуру. Существует, однако, много задач, в которых требуются данные с более сложной структурой. Для них характерно, что в процессе вычислений изменяются не только значения объектов, но даже и сама структура хранения информации. Поэтому такие объекты стали называть динамическими информационными структурами. Их компоненты на некотором уровне детализации представляют собой объекты со статической структурой, т. е. они принадлежат к одному из основных типов данных. Эта глава посвящена проектированию объектов с динамической структурой, анализу и работе с ними [1,3,8,11].

Стек

Стекомназывается упорядоченный набор элементов, в котором размещение новых и удаление существующих элементов происходит с одного конца, называемого вершиной. Иными словами, в стеке реализуется дисциплина обслуживания LIFO (last input — first output; первым вошел — последним вышел) [11].

Над стеком реализованы следующие операции [3, 8, 11]:

1) помещение элемента в стек push(,s, /), где s — стек, / — помещаемый элемент;

2) удаление элемента из стека / = pop(s);

3) определение верхнего элемента без его удаления / = stacktop(s), которая эквивалентна операциям / = pop(s) и push(,s, /);

4) определение пустоты стека emty(,s), которая возвращает true, если стек пустой к false в противном случае.

Существует несколько способов реализации стека:

1) с помощью одномерного массива конечного размера, распределенного статически;

2) с помощью одномерного массива, распределенного динамически;

3) в виде связанного списка.

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

#defme NMAX100 struct stack

{ float elem[NMAX;

integer top;

}; ,

где NMAX— максимальное количество элементов в стеке; elem — массив из NMAX чисел типа float, предназначенный для хранения элементов стека; top — индекс элемента, находящегося на вершине стека.

Пример.Необходимо написать программу-калькулятор, вычисляющую значение выражения, записанного в постфиксной форме [7]. При записи выражения допускаются операции « + », « - », « * », « / » и знак « = » — для выдачи результата. Выражение типа

(1-2)*(4+5) запишется в следующем виде:

12-45 + * — круглые скобки при этом не нужны.

Реализация оказывается весьма простой. Каждый операнд помещается в стек; когда поступает знак операции, нужное количество операндов вынимается из стека, к ним применяется операция и результат направляется обратно в стек. Так, в приведенном выше примере 1 и 2 помещаются в стек и затем заменяются их разностью, -1. После этого 4 и 5 вводятся в стек и затем заменяются своей суммой 9; далее числа -1 и 9 заменяются в стеке на их произведение, равное -9. Операция «=» печатает верхний элемент стека, не удаляя его (так что промежуточные вычисления могут быть проверены).

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

while(поступает операция или операнд, а не конец файла) if( число )

поместить его в стек else if( операция )

вынуть операнды из стека выполнить операцию поместить результат в стек else

ошибка

Операции «взять из стека» и «послать в стек» реализуем в виде функция. Добавим механизм обнаружения и нейтрализации ошибок [7].

/^максимальный размер оператора*/ /^признак числа*/

#include<stdlib.h> #include<stdio.h> #include<ctype.h> #include<math.h> #include <string.h> #define MAXOP 100 #define NUMBER 0 #define IDENTIFIER 1 #define TRUE 1 #define FALSE 0 int Getop(char s[]); void push(double val); double pop(void);

void showTop(void);

void duplicate(void) ;

void swapltems(void);

void clearStack();

void dealWithName(char s[] ) ;

int main(void)

{

int type; double op2; char s[MAXOP]; int flag = TRUE;

while((type = Getop(s)) != EOF)

{

switch(type)

{

case NUMBER:

push(atof(s));

break; case IDENTIFIER:

dealWithName(s);

break; case ' + ' :

push(pop () + pop () );

break; case ' * ' :

push(pop () * pop () );

break;

case '- ' :
op2 = pop();
push(pop()- op2);
break;
case '/':
op2 = pop ();
if(op2)
push(pop() / op2);
else
printf("пОшибка! Деление на ноль.");
break;
case ' % ' :
op2 = pop();
if(op2)
push(fmod(pop(), op2));
else
printf("пОшибка! Деление на ноль.");
break;
case ' ? ' :
showTop();
break;
case '# ' :
duplicate ();
break;
case '~' :
swapltems();
break;
case ' ! ' :
clearStack();
case 'n':
printf("nt%.8gn", pop () );
break;
default:
printf("пОшибка! Неизвестная операция. %s	An",
s) ;
break; }
} return EXIT SUCCESS;
}

Поскольку операции «+» и «*» коммутативны, то порядок, в котором операнды берутся из стека, не важен. Однако, в случае операций «-» и «/» левый и правый операнды должен различаться. Так, в строке

push(pop() -popQ);

порядок, в котором выполняются обращения к рор() не определен. Для гарантии правильного порядка первое значение из стека присваивается ор2.

 

 

 

 

#define MAXVAL 100	/^максимальная глубина стека*/
int sp = 0;	/* позиция следующего свободного */
	/* элемента стека*/
double val[MAXVAL];	/* стек */
/* push: поместить f	в стек */
void push(double f) { if(sp < MAXVAL)
val[sp++] = f;
else
printf("пОшиб	ка: стек полон, элемент %д не
помещается!n", f) ; }
/*pop: взять значение с вершины стека.*/
double pop(void) { if(sp > 0)
return val[--s	р] ;
else { printf("пОшиб
ка! Стек пуст. п");
return 0.0; } }

Стек и индекс стека которые должны быть доступны для push и pop определены вне этих функций. Но так как в main не используют ни стек, ни индекс, то они скрыты от main.

Займемся реализацией getop — функции, получающей следующий оператор или операнд. Требуется пропустить пробелы и табуляции; если следующая литера — не цифра и не десятичная точка, то выдать ее; в противном случае накопить цепочку цифр с десятичной точкой, если она есть, и выдать признак числа NUNBER в качестве результата.

int getch(void); void unGetch(int);

/* Getop() получает следующий int Getop(char s[])

{

int i = 0; int c; int next; /*size_t len;*/

/* пропуск пробела */ while((s[0] = с = getch()) s[l] = '';

if(isalpha(c))

{

i = 0;

while(isalpha(s[i++] =

с = getch(); s[i - 1] = ''; if(c != EOF)

unGetch(c); return IDENTIFIER;

оператор или операнд */

с == 't') ;

) )

 

/* He число, но, возможно, if(!isdigit(с) && с != '.' return с;

if(с == '-')

{

next = getch();

if(!isdigit(next) && ne

{

return c;

}

с = next;

} else

с = getch();

while(isdigit(s[++i] = c))

с = getch();
if(c =='.') /* н

while(isdigit(s[++i] =

содержит унарный минус */ && с != '-')

t ! =

капливаем дробную часть */ = getch()))

ПО

	r
	s[i] =	'';
	if(c !=	EOF)
	unGetch(c) ;
	return	NUMBER;
}
s[i	]='';
if	(c!=EOF)
ung	etch (c) ;
ret	urn NUMBER	•
}

Как работают функции getch и ungetchl Во многих случаях программа не может определить прочла ли она все, что требуется, пока не прочтет лишнего. Поэтому getch читает очередную литеру из ввода, ungetch отправляет «лишнюю» литеру назад.

Поскольку функции совместно используют буфер и индекс, то они являются внешними по отношению к ним.

 

 

 

#с!е	;fine BUFSIZE 100
char buf[BUFSIZE];
int	. bufp = 0;
/*	Getch: получить символ. *	/
int { }	. getch(void)
return (bufp > 0) ? buf [-	-bufp]:	getchar	О ;
/*	unGetch: поместить символ	назад	в стек.	*/
voi {	о! unGetch (int с)
if(bufp >= BUFSIZE)
	printf("nUnGetch: слишком много символов.n");
	else
}	buf[bufp++] = c;

Функции showTop, dublicate, swapltem, clearStack и dealWithName.

void showTop(void)

if(sp > 0)

printf("На вершине стека лежит: %8gn", val[sp-l]); else

printf("Стек пуст!п"); }

void duplicate(void)

{

double temp = pop();

push(temp); push(temp);

void swapltems(vo

{

double iteml = double item2 =

push(iteml); push(item2);

id)

pop(); pop();

void clearStack(void)

{

sp = 0;

}

/^Функция работы с математическими функциями.*/ void dealWithName(char s[])

{

double op2;

if( 0 == strcmp(s, "sin"))

push(sin(pop())); else if( 0 == strcmp(s, "cos"))

push(cos(pop ())); else if (0 == strcmp(s, "exp"))

push(exp(pop ())); else if(!strcmp(s, "pow"))

{

op2 = pop ();

push(pow(pop (), op2) );

}

else

printf("Функция %s не поддерживаетсяО.n", s); }

Однонаправленные связанные списки

Элемент списка называется узлом. Каждый узел содержит два поля: поле информации info и поле следующего адреса ptrn. Поле адреса хранит указатель на…   1st|         …   [nfo ptrn —^ info ptrn   ... —+■ Info …

Операции над списком

1. Размещение произвольного элемента в начало списка [11]

 

p=getnode();	Выделение места под узел.
	Запись в переменную р адреса узла.
info(p)=x;	Запись значения х
	в информационную часть узла.
ptrn(p)=lst;	Подключение узла к началу списка.
lst=p;	Установка указателя
	1st на новый узел.

2. Удаление первого элемента списка [11]

 

p=lst;	Установка указателя р
	на начало списка.
lst=ptrn(p);	Установка 1st
	на второй элемент списка.
x=infо(р);	Сохранение данных
	из удаляемого узла в переменной х.
freenode(p);	Освобождение памяти,
	занятой под первый узел.

3. Размещение элемента после узла с адресом р [11].Новый элемент вследствие однонаправленности списка может помещаться только после узла, адрес которого известен. Поэтому для вставки узла необходимо поступить следующим образом: новый элемент размещаем после старого, затем меняем указатели. Пусть операция insafter(p, x) означает операцию вставки элемента со значением х после/?.

Операция insafter(p, x)

 

g=getnode();	Выделяем память под узел.
info(g)=x;	Записываем в новый узел значение х.
ptrn(g)=ptrn(p);	Записываем в адресную часть
	нового узла указатель
	на элемент, следующий за р.
ptrn(p)=g;	Записываем в адресную часть
	узла р указатель д.

4. Удаление элемента после узла с адресом р [11].В однонаправленном связанном списке можно удалить только элемент, следующий за данным узлом. Пусть default(/?, x) — операция удаления элемента со значением х, следующего за узлом с адресом/?.

Операция default(p, x)

g=ptrn(p); Установка указателя р на адрес

элемента, следующего за р.

x=info(g);	Сохранение данных из
	удаляемого узла в переменной х.
ptrn(p)=ptrn (g);	Подключение узла р к узлу,
	следующему за удаляемым.
freenode(g);	Освобождение участка
	оперативной памяти, занятой
	под узел д.

Примеры

1. Из списка 1st удаляются все элементы, равные 4. Имеем два указателя: р — для просмотра списка; q — указатель на элемент перед р. Используем операции удаления: pop — из начала списка; default — из середины списка.

q=NULL; /^инициализация указателя*/

p=lst; /^текущий указатель на начало списка*/

while (p!=NULL)

{

if (info(p) == 4) if (q==NULL)

{

/*удалить первый элемент*/ x=pop(1st); freenode(p); p=lst;

} else

{

/^передвинуть р и удалить элемент,*/ /*следующим за node(q)*/ p=ptrn(p); default(q, x);

} else

{

/^продолжить просмотр, передвинуть р и q*/ q=p;

p=ptrn(p); } }

2. Список 1st упорядочен по возрастанию. Вставить х, не нарушая упорядоченность. Используем операции push для добавления элемента к началу списка, insafter — внутрь списка.

q=NULL;

p=lst;

while((p!=NULL) && (x>info(p))

{

q=p; p=ptrn(p);

}

/^размещаем х*/

if(q == NULL)

push(1st, x); /^поместить в начало списка*/ else

insafter(q, x) ;

Однонаправленные циклические списки

Циклический связанный список— это список, в котором последний узел связан с первым узлом [11]. Чтобы превратить линейный список в циклический…   1st ----------------------------------- »■ …   info pirn —*■ info ptrn ----- и- ... —и- mfo ptrn …

Двунаправленные связанные списки

(рис. 2.3) [8, И]: • один указатель установлен на предшествующий элемент; • другой указатель установлен на следующий элемент. Двунаправленный список может быть линейным и циклическим (рис.…

Ptrnl

Info

Ptm2

Ptrnl

Info

Ptrn2

 

ptrnl

info

ptrn2

ЦИКЛИЧЕСКИЙ ДВУНАПРАВЛЕННЫЙ СПИСОК

Рис. 2.4. Графическое представление двунаправленных связанных списков Двунаправленные списки имеют следующее удобное свойство [11]: если р —… left(right(p))=p=right(left(p)),

Удаление узла

free(p);

Перемещение на следующий элемент списка Однонаправленный список

 

р=	=Р"	->ptrn;
Двунаправленный список
Р= Р=	=Р" =Р"	->ptrnl; ->ptrn2;	/^перемещение /^перемещение	влево вправе	*/ */

Примеры работы со списками

Определение количества узлов в линейном однонаправленном списке (рис. 2.5).

p=lst;

k=0;

while(p!=NULL)

{

k++; p=p->ptrn;

}

printf("nB списке %о! узлов. ",k);

 

 

1st—^			ptrn=NULL
info	ptrn	► ... *■	info	ptrn

Рис. 2.5. Линейный однонаправленный список

Включение узла в двунаправленный связанный список после элемента с адресом р (рис. 2.6).

p2=(struct NODE*)malloc(sizeof(struct NODE));

p3=p->ptrn2; p->ptrn2=p2; p2->ptrnl=p; p2->ptrn2=p3; p3->ptrnl=p2; p2->info=x;

Рис. 2.6

3. Удаление узла с адресом р из двунаправленного связанного списка (рис. 2.7).

x=p->infо; q=p->ptrnl; r=p->ptrn2; q->ptrn2=r; r->ptrnl=q; free(p);

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

lst=(struct NODE*)malloc(sizeof(struct NODE;

lst->ptrnl=NULL;

lst->info=...;

pl=lst;

for(i=l;i<=n-l;i++)

{

pl->ptrn2=(struct NODE*)

malloc(sizeof(struct NODE)); p2=pl;

pl=pl->ptrn2; pl->info=...; pl->ptrnl=p2;

} pl->ptrn2=NULL;

Пример.Рассмотрим реализацию списка с двойными связями. Каждый узел содержит три поля: обратный указатель В, прямой указатель F и данные info (рис. 2.8). Рассматриваемый список является циклическим.

 

 

 

+
В	info	F	—*■	В	info	F		В	info	F
						+

Рис. 2.8. Пример Определим структуру, представляющую узел списка.

Узел списка

struct NODE

{

struct listnode *pred;

/^обратный указатель*/ struct listnode *succ;

/*прямой указатель*/ char data[NAME_SIZE];

/*поле данных*/ };

Разработаем программу, которая упорядочивает имена в поле info по алфавиту. Функция main в диалоге запрашивает вводимые имена и вызывает функцию insert, которая образует узел для очередного имени и включает его в соответствующее место списка.

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

Функция insert просматривает список, пока не найдет место для имени.

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

#include <stdio.h> #define NAME_SIZE 30

struct NODE

{

struct listnode*pred;

struct listnode*succ;

char data[NAME_SIZE]; };

main()

{

char name [NAME_SIZE];

struct NODE *root; /^Голова списка.*/

struct NODE *np; /^Используется при просмотре.*/

/*3анять блок памяти для головы списка и иницилизировать его так, чтобы он показывал сам на себя.*/ root=malloc(sizeof(struct NODE) ) ;

root->pred= root->succ=root; root->data[0]='' ;

/^Создать связанный список имен.*/ for ( ; ; )

{

printf ("имя:");

gets (name);

if (strcmp(name), "конец")==0)

break; if (insert(root, name)==0)

{

printf ("не хватает динамической памяти п"); exit(1); } } /^Изобразить содержимое списка.*/

for (np=root->succ; np!=np->succ) printf ("имя=%з n", np->data);

printf ("работа закончена п"); }

/^Зарезервировать память для нового узла списка; скопировать в него имя и вставить новый узел в список в алфавитном порядке. Возвратить либо указатель на новый узел, либо NULL, если для создания узла не хватило памяти.*/

struct NODE *insert (node, name); struct NODE *node; /*Голова списка.*/ char *name;

{

NODE *np; /*Узел списка.*/ NODE *newnode;

/*Узел, вставленный в список.*/

/*Просматривать список, пока не обнаружится узел, поле info которого имеет значение, большее введенного имени или равное ему.*/

for (np=node->succe; (np!=node) &&

strcmp (name, np->data)>0); np=np->succe);

/^Зарезервировать память для нового узла; поместить введеное имя в его поле info и вставить новый узел перед тем, на который показывает указатель пр.*/

if( (newnode=malloc(sizeof(struct NODE)))!=0 ) {

strncpy(newnode->data, name, №ME_SIZE);

newnode->succ=np;

newnode->pred=np->pred;

/^Изменить прямой указатель в узле, предшествующем вставленному (теперь он должен показывать на вставленный узел) и изменить обратный указатель в узле, следующем за вставленным.*/

(newnode->pred)->succ=newnode; np->pred=newnode; }

return (newnode); }

Очереди

Для очереди определены три простейшие операции: • insert(g, х) — помещает элемент х в конец очереди q, где q — указатель на… • х = remove(g) — удаляет элемент х из очереди q;

КАССА

 

НАБЛЮДАТЕЛЬ

Операция empty(q)

J

ПОКУПАТЕЛИ

z

Операция insert(q,x)

 

с^°г

операция x=remove(q)

ТОРГОВЫЙ ЗАЛ

#define Maxg 5 float git[Maxg]; frnt=l; rear=0;

Пример

х = git[0] ;

for(i=0; i<rear-l; i + +[ {

git [i

git[i+1];

rear-

Переменной frnt не требуется, так как первый элемент — начало очереди. Для пустой очереди rear = 0. Метод непроизводителен, так как требует перемещение оставшихся элементов.

Другой способ предлагает рассматривать массив в виде циклического связанного списка. Недостаток — трудно определить, когда очередь пуста, так как условие rear <frnt не выполняется.

Рассмотрим следующий пример (рис. 2.11). Одним из способов решения проблемы является соглашение о том, что frnt является индексом элемента, предшествующего первому элементу. В этом случае для пустой очереди frnt = rear.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

	e	5-ти элементный		е	frnt=3
4 3 2	масив. Если необходимо разместить элемент f, то он пишется в первую	4 3 2	rear=1 rear<frnt, rear=1 rear<fmt, но
d	d
с	с
			f	очередь
	позицию.	не пуста
frnt=		frnt-
rear=0	rear=3

Рис. 2.11. Пример

Инициализация очереди

Операция empty if(frnt == rear) empty=l; else empty =0; Операция remove

Функции, реализующие операции работы с очередью

int empty()

{

if (frnt ==rear) return 1;

else return 0; }

float remove()

{

if(empty() == 1)

{

printf("Очередь пуста."); return 0.0;

} else

{

if(frnt == (Maxq-1)) frnt=0; else frnt++; return git[frnt]; } }

void insert(float x)

{

if(rear == (Maxq-1)) rear = 0;

else rear++;

if(rear == frnt)

printf("Переполнение!");

else git[rear]=x; }

Реализация очереди на базе однонаправленного связанного списка

Однонаправленный связанный список можно рассматривать в качестве очереди поскольку (рис. 2.12): а) определены начало и конец списка, б) задан порядок расположения узлов.

info

ptrn —■*

t

frnt

Начало очереди

info

ptrn

ptrn=NULL —■*! info ptrn

rear

Конец очереди

FIFO (FIRST INPUT — FIRST OUTPUT)

1. Операция проверки пустоты очереди empty if(frnt == NULL && rear == NULL; printf("Очередь пуста."); … 2. Операция удаления элемента из очереди remove (рис. 2.13)

Rear

ptrn=NULL ---►I info ptrn i

Rear

Конец очереди

Рис. 2.14

Недостатки представления очереди и стека в виде связанного списка:

• Элемент списка занимает в оперативной памяти больше места, чем элемент массива.

• Требуется дополнительное время на обработку списка: необходимо выделять блоки оперативной памяти под узлы и изменять значения указателей.

Бинарные деревья

Общепринятый способ изображения бинарного дерева представлен на рис. 2.15: дерево состоит из 9 узлов; А — корень; левое поддерево имеет корень В;… Узел у, который находится непосредственно под узлом х, называется потоком х;…  

Узел дерева

{ char *word; /^указатель на поле info*/ struct tnode *left; /*левый потомок*/ struct tnode *right; /*правый потомок*/

Функция обхода дерева слева направо

 

 

 

void { i {	postorder (struct node	*t)
f( t!=NULL)
postorder (t->left);
	postorder (t->right);
} }	P(t) ;

Функция обхода дерева снизу вверх

  f (t!=NULL)     inorder (t->left);     P(t)… Здесь Р — операция, которую надо выполнить с узлом; t — указатель на дерево.

Глава 3. Сортировка и поиск

Введение в поиск

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе. Найти некоторую запись из этого набора — вот классическая задача программирования, вокруг которой сгенерировано множество идей [1, 3, 9, 10, 13].

Пусть мы имеем таблицу, состоящую из записей (табл. 3.1). Первое поле каждой записи содержит ключ (например, табельный номер); второе — фамилию и так далее. Ключом может любое поле записи.

Таблица 3.1

 

	Иванов
	Андреев
	Сидоров
	Петров

Основная задача поиска — найти запись с заданным ключом.

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

Последовательный поиск

Наиболее примитивный, а значит, и наименее эффективный, способ поиска— это обычный последовательный просмотр записей таблицы [9,11]. Метод применяется к таблице, организованной как массив. Предложим, что к— массив из п ключей; г— массив записей такой, что k(i) — ключ для записи r(i); key — аргумент поиска. Запишем в переменную search наименьшее целое число /, такое, что k(i) = key, если такое / существует, и -1 в противном случае.

Алгоритм последовательного поиска

Некоторым улучшением этой идеи является метод транспозиции: каждый запрос к записи сопровождается сменой мест этой и предшествующий записи; в итоге… На подобной идее основан и метод перемещения в начало: каждый запрос к записи…

Поиск в упорядоченной таблице

Индексно-последовательный поиск.В дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной [9, 11]. Каждый… Алгоритм индексно-последовательного поиска прост. Предположим, что к — массив…

Алгоритм поиска

if (i==ind_size) high=n; else high=pindex[i];

Алгоритм поиска

{ mid=(int)(low+high)/2; if (key==k[mid]) {

Хеширование таблиц

Поясним это на примере. Пусть в файле прямого доступа лежит структура со следующими полями (табл. 3.2): 1) номер накладной, 2) грузоотправитель, 3)… представляет собой довольно длинное целое число; в нашем примере это ключ.… Таблица 3.2 Поля структуры

Введение в сортировку

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке.

Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве. Следовательно, методы сортировки важны особенно при обработке данных [1, 3, 9, 10, 13].

Зависимость выбора алгоритма от структуры данных — явление довольно частое, и в случае сортировки она настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов (внутренняя сортировка) и сортировка файлов (внешняя сортировка). Массивы обычно располагаются в оперативной памяти, для которой характерен быстрый произвольный доступ; файлы хранятся в более медленной, но более вместительной внешней памяти, на дисках.

Введем некоторую терминологию [3]. Пусть даны элементы ai,ci2, ...,a_n. Сортировка означает перестановку элементов в таком порядке а^, ^аю., ■■■,^кп-, что при заданной упорядочивающей функции f(x) справедливо отношение

f(a_xl)<f(a_xl)<...<f(a_m).

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

struct item

{ int key;

описание других компонент;

}; ,

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

Сортировка массивов.Основное требование к методам сортировки массивов — экономное использование памяти. Это значит, что перестановки элементов нужно выполнять на том же месте оперативной памяти, где они находятся, и что методы, которые пересылают элементы из массива А в массив В, не представляют интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов, проводят в соответствии с их эффективностью, т.е. быстродействием. Удобная мера эффективности получается при подсчете числа необходимых сравнений ключей С и пересылок элементов М. Эти параметры зависят от числа сортируемых элементов п. Хорошие алгоритмы сортировки требуют порядка nlogn сравнений.

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

Методы сортировки массивов можно разбить на три класса [3]:

1) сортировка включениями;

2) сортировка выбором;

3) сортировка обменом.

Сравним эти методы. Используем массив а, описанный следующим образом:

int nambers[n; .

Сортировка с помощью прямого включения

  44^12 42 94 18 06 67   ♦   44| 14294 18 06 67

Функция сортировки с помощью метода прямого включения

{ int i, j , index; for (i=l; i < array_size; i++)

Сортировка с помощью прямого выбора

Метод сортировки основан на следующих правилах [1, 3, 9, 10, 13]:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом а₀.

3. Затем эти операции повторяются с оставшимися п- элементами, п-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.

На рис. 3.3 приведен процесс сортировки этим методом.

Начальные ключи

и

И 67

 

061 142

 

94 ЕЯ 44

Ш42"Э41Я

 

 

т

ЕЯ94

 

42 Ш 55 ЕЛ 67

 

 

441*194

 

 

94 67

 

I I

Рис. 3.3. Пример сортировки Алгоритм формулируется следующим образом

for(i=0; i<n-l; i++) {

присвоить к индекс наименьшего элемента из a[i] ..а[п-1] ; поменять местами a[i] и а[к];

}

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

Функция сортировки прямым выбором

{ int i, j; int min, temp;

Сортировка с помощью прямого обмена

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

Функция сортировки прямым обменом

{ int i, j , temp; for( i = 0; i < array size; i++

Рис. З.4. Пример сортировки

Анализ алгоритма [3]. Число сравнений в алгоритме прямого обмена

С = (п²-п)/2,

а минимальное, среднее и максимальное число перемещений элементов равно со отв етств енно

М_тЫ = О, Мер = 3(п² - п)/2, М_тах = 3(п²-п)/4. Резюме:«обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия. Далее мы рассмотрим улучшенные методы сортировки.

Сортировка включениями с убывающим приращением

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

Функция сортировки Шелла

    increment = 3;   while (increment > 0) {   for (i=0; i < array_size; i++) {

Сортировка

| 44 | 18 | 06 | 42 | 94 | 55 | 12 |~67"

 

Сортировка

| 06 | 18 | 12 | 42 | 44 | 55 || 94 |~б7

XXAKKKK7

Сортировка

Рис. 3.5. Пример сортировки Шелла Приводимая программа не ориентирована на некую определенную последовательность… ht=;

Сортировка с помощью дерева

Рис. 3.6. Повторяющиеся наборы среди двух ключей На втором шаге спускаемся по пути, указанному наименьшим ключом и исключаем его, последовательно заменяя на «дыру»,…

ВЫБОР НАИМЕНЬШЕГО КЛЮЧА

  Рис. 3.7

Пирамидальная сортировка

a[i] <a[2*i]; a[f<a[2*i+ 1]. Отсюда следует, что а[] — минимальный элемент пирамиды. Сначала расположим исходный массив в пирамиде, а затем пересортируем элементы.… Рис. 3.8

Быстрая сортировка

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

Функция быстрой сортировки

{ q_sort(numbers, 0, array_size - 1); }

Сравнение методов сортировки массивов

Для усовершенствованных методов сортировки нет простых и точных формул. Существенно, однако, что в случае сортировки Шелла вычислительные затраты… Опытным путем были получены следующие результаты [3]: 1. Пузырьковая сортировка наихудший метод из всех сравниваемых.

Сортировка файлов методом прямого слияния

Основной применяемый метод — сортировка слиянием. Слияние означает объединение двух (или более) последовательностей в одну упорядоченную… Метод заключается в следующем [3]: 1. Последовательность а разбивается на две половины: b ис.

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

Об, 67

Первый шаг: разбиение дает две последовательности

Об, 67

Слияние в упорядоченные пары дает последовательность

44, 94, 18, 55', Об, 12', 42, 67

Новое разбиение пополам и слияние упорядоченных пар дает последовательность

Об, 12, 44, 94', 18, 42, 55, 67

Третье разбиение и слияние приводят к нужному результату

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

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

j=n; k=n+l; l=2*n;

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

2. Болски, М.И. Язык программирования Си: справочник / М.И. Болски; пер. с англ. СВ. Денисенко. — М.: Радио и связь, 1988. — 96 с. 3. Вирт, Н. Алгоритмы и структуры данных/Н. Вирт; пер. с англ. — М.: Мир,… 4. Бочков, СО. Язык программирования Си для персонального компьютера / СО. Бочков, Д.М. Субботин. — М.: Радио и…

ОГЛАВЛЕНИЕ

Предисловие..................................................................................................... 3

Глава 1. Язык программирования Си

§1.1. Введение в язык Си............................................................................ .. 4

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

§1.2. Объекты языка Си и их типы............................................................. 7

§1.3. Простые объекты................................................................................ .. 7

§1.5. Операции............................................................................................. 11

§1.6. Ввод и вывод информации................................................................ .. 13

§1.7. Операторы.......................................................................................... .. 15

§1.8. Функции.............................................................................................. .. 23

§1.9. Прототипы функций........................................................................... 28

§1.10. Препроцессор................................................................................... 30

§1.11. Математические функции................................................................. 32

§1.12. Специальные операции..................................................................... 33

§1.13. Глобальные и локальные объекты................................................... .. 35

§1.14. Модификация объектов.................................................................... 38

§1.15. Указатели.......................................................................................... 40

§1.16. Модели памяти................................................................................. .. 43

§1.17. Массивы............................................................................................ 44

§1.18. Передача массива в функцию.......................................................... ... 49

§1.19. Многомерные массивы..................................................................... .. 50

§1.20. Динамическое распределение памяти.............................................. 52

§1.21. Динамическое распределение памяти под массивы........................ 54

§1.21. Массивы указателей......................................................................... .. 57

§1.22. Структуры........................................................................................ 60

§1.23. Объединения..................................................................................... 63

§1.25. Битовые поля.................................................................................... ... 65

§1.26. Указатели и структуры.................................................................... .. 66

§1.27. Классификация функций ввода-вывода........................................... 70

§1.28. Функции ввода-вывода высокого уровня....................................... .. 71

§1.29. Работа с файлами данных................................................................ .. 75

§1.30. Функции обработки строк............................................................... .. 80

§1.31. Работа со строками........................................................................... 81

§1.31. Логический тип данных.................................................................... .. 93

§1.32. Программная реализация стека....................................................... 95

Глава 2. Структуры данных

§2.1. Введение в структуры данных........................................................... .. 105

§2.1. Стек..................................................................................................... .. 105

§2.2. Однонаправленные связанные списки........................... .. 113

§2.3. Однонаправленные циклические списки.......................... 116

§2.5. Двунаправленные связанные списки............................ .. 117

§2.6. Очереди................................................ .. 125

§2.7. Бинарные деревья............................................................................... ... 131

Глава 3. Сортировка и поиск

§3.1. Введение в поиск................................................................................. ... 139

§3.1. Последовательный поиск.................................................................... 139

§3.2. Поиск в упорядоченной таблице....................................................... ... 140

§3.3. Хеширование таблиц.......................................................................... 142

§3.5. Введение в сортировку...................................................................... 144

§3.6. Сортировка с помощью прямого включения.................................... .. 145

§3.7. Сортировка с помощью прямого выбора......................................... ... 147

§3.8. Сортировка с помощью прямого обмена......................................... ... 149

§3.9. Сортировка включениями с убывающим приращением.................. 151

§3.10. Сортировка с помощью дерева....................................................... 153

§3.11. Пирамидальная сортировка............................................................. ... 154

§3.11. Быстрая сортировка.......................................................................... 160

§3.12. Сравнение методов сортировки массивов...................................... ... 163

§3.13. Сортировка файлов методом прямого слияния.............................. 164

Библиографический список............................................................................. .. 173

Электронное издание

Сергей Тимурович Касюк

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

Конспект лекций

Издательский центр Южно-Уральского государственного

университета

Подписано в печать 09.04.2010. Формат 60x84 1/16. Усл. печ. л. 10,23. Уч.-изд. л. 10,38. Заказ 109.