загрузка...

4271

Программирование на языке Си. Методические указания и контрольные задания

Книга

Информатика, кибернетика и программирование

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

Русский

2012-11-15

257.07 KB

141 чел.

1.1 Общая информация

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

Большинство трансляторов языка Cи - компиляторы. Система программирования языка включает препроцессор, компилятор, редактор связей, библиотекарь, редактор текста, отладчик и интегрированную управляющую среду.

1.2. Алфавит языка Си

В языке Си используются наборы символов:

1) прописные (A,B,C,…….,Y,Z) и строчные (a,b,c,………,y,z) буквы латинского алфавита;

2) арабские цифры от 0 до 9;

3) специальные символы:

+ (плюс),  - (минус),   (звездочка ),  / (дробная черта),  = (равно),  > больше),  < ( меньше),  ; (точка с запятой ),  & (амперсанд ),  [ ] (квадратные скобки),  { } (фигурные скобки),  ( ) (круглые скобки),  _ (знак подчеркивания),   (пробел ),  . (точка),  , (запятая), : (двоеточие),  # (номер),  % (процент),  ~ (поразрядное отрицание),  ? (знак вопроса),  ! (восклицательный знак),  \ (обратный слэш);  ^ - (исключающее ИЛИ);  ~ (тильда);

4) управляющие последовательности (escape-последовательности)

 1.3. Типы данных

В языке C применяются данные двух категорий: простые (скалярные) и сложные (составные) типы данных. К основным (базовым) типам данных относятся целочисленный (int), вещественный с одинарной точностью (float), вещественный с двойной точностью (double), символьный (char) типы. Используя модификаторы signed/unsigned (знаковый/беззнаковый) и модификаторы длины short/long (короткий/длинный) из базовых типов данных можно получить дополнительные типы. Величины символьного типа возможно использовать для работы с короткими целыми числами, представимыми как коды символов. Размеры и возможные диапазоны базовых типов данных приведены в таблице 1:

Таблица 1

Наименование типа

Тип данных

Размер, байт

Диапазон значений

Символьный

char

1

-128…127 (0…255)

Целый

int

2

-32768…32767

Короткий

short

2(1)

-32768…32767(-128…127)

Длинный

long

4

-2147483648…2147483647

Беззнаковый целый

unsigned int

2

0…65535

Беззнаковый длинный

unsigned long

4

0…424967295

Вещественный

float

4

1,17*10-38…3,37*1038

Вещественный с двойной точностью

double

8

2,23 *10-308   1,67 *10308

Язык Си допускает преобразование типов, выполняемое или неявно (автоматически), или явно. Неявное преобразование выполняется, когда в выражениях величины одного типа смешиваются с величинами другого. В языке Си разрешается автоматическое преобразование типов с потерей точности (из типа int к типу char, из типа double к типу int). Оператор явного преобразования типов применяется, когда необходимо получить точное значение выражения: double x=(double) 11/2.

Сложные типы данных подразделяются на массивы, структуры (struct), объединения (union), перечисления (enum).

Декларирование объектов

Перед использованием все объекты (переменные, массивы и т.д) должны быть объявлены. При объявлении (декларировании) объекты можно инициализировать (задать начальные значения).

При декларировании объектов в языке Си используются их идентификаторы, которые могут включать цифры, латинские прописные и строчные буквы, символ подчеркивания (_). Первый символ идентификатора не может быть цифрой. В языке Си буквы нижнего регистра (a….z) отличаются от букв верхнего регистра (A ….Z). Принято использовать в идентификаторах переменных строчные буквы, а в именованных константах – прописные.

Например:    const float  PI=3.1415926;

  float          pi=3.14;

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

Например:     int       j=10, m=3, n;

                      float    c=-1.3, l=-10.23, ;

  double y=-17.2e-208

  char a=’a’;

  char s[10]=”i_like_C!”

 1.4. Функции вывода информации

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

Функция putchar() – вывод одиночного символа без перехода на новую строку.

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

Функция printf() – для форматированного вывода данных. Ее формат:

рrintf (<управляющая строка>, <список аргументов>);

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

Спецификация преобразования имеет вид:

% <флаг> <размер поля . точность> спецификация

где флаг может принимать следующие значения:

- выравнивание влево выводимого числа;

+   выводится знак положительного числа;

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

точность – задает точность числа, т. е. количество цифр в его дробной части;

спецификация указывает вид выводимой информации.

Таблица 2. Основные форматы функции печати.

Формат

Тип выводимой информации

%d

десятичное целое число

%c

один символ

%s

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

%e

число с плавающей точкой (экспоненциальная запись)

%f

число с плавающей точкой (десятичная запись)

%u

десятичное число без знака

%o

восьмеричное число без знака

%x

шестнадцатеричное число без знака

Для длинных чисел (long, double) – используется дополнительный формат l.

Например: %ld - длинное целое, %lf – вещественное число с удвоенной точностью.

При необходимости вывода символа % его нужно указать 2 раза.

Управляющая строка может содержать следующие управляющие символы:

\n – переход на новую строку;

\t – горизонтальная и \v – вертикальная табуляция;

\b – возврат назад на один символ;

\r – возврат в начало строки;

\f – прогон бумаги до начала новой страницы;

\a – звуковой сигнал;

\ddd – ASCII символ в 8-ричном  представлении;

\xhhh – ASCII символ в 16-ричном  представлении;

\? – знак вопроса.

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

Например: printf ("Значение числа pi равно%f.\n", pi);

printf ("x=%-8.4f, s=%5d, y=%8.2f ", x, s, y);

1.5. Функции ввода информации

Для ввода информации в языке Си используются следующие функции:

Функция getch ()–  для ввода одиночных символов.

Функия gets ()–  ввод строки символов до нажатия клавиши ENTER.

Функция scanf() предназначена для форматированного ввода информации любого вида. Общий вид функции:

scanf (<управляющая строка>, < список адресов>);

Функция scanf(), в отличие от функции printf(), использует в списке адресов указатели на переменные, т.е. их адреса. Для обозначения указателя перед именем переменной записывается символ &, обозначающий адрес переменной. Для ввода значений строковых переменных символ & не используется. При использовании формата %s строка вводится до первого пробела. Вводить данные можно как в одной строке через пробел, так и в разных строках.

Пример:

int course_of_study;

float grant;

char name[20];

     printf ( "Укажите ваш курс, стипендию, имя \n");

     scanf  ( "%d%f", &course_of_study, &grant);

     scanf  ( "%s", name);   /* & отсутствует при указании имени массива символов */

Функция scanf() заканчивает ввод информации при появлении пробела либо при нажатии на клавишу ENTER. В отличие от нее, функция gets() позволяет вводить информацию, содержащую пробелы.

1.6. Стандартные математические функции

Для подключения математических функций используется директива #include <math.h>. Аргументы x, y и результат имеют тип double, параметр n имеет тип int. Аргументы тригонометрических функций задаются в радианах.

Таблица 3

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

Имя функции в языке

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

Имя функции в языке

sqrt(x)

arcsin(x)

asin(x)

|x|

fabs(x)

arccos(x)

acos(x)

ex

exp(x)

arctg(x)

atan(x)

xy

pow(x,y)

arctg(x/y)

atan2(x,y)

ln(x)

log(x)

sh(x)=1/2 (ex-e-x)

sinh(x)

lg10(x)

log10(x)

ch(x)=1/2 (ex+e-x)

cosh(x)

sin(x)

sin(x)

tgh(x)

tanh(x)

cos(x)

cos(x)

Остаток от деления x на y

fmod(x,y)

tg(x)

tan(x)

Наименьшее целое >=x

ceil(x)

Наибольшее целое <=x

floor(x)

1.7. Этапы создания программы.

Разработку и отладку программы осуществляют с помощью специального программного комплекса — системы программирования. Система программирования включает:

  1. Язык программирования;
  2. Интегрированную среду;
  3. Редактор связей (компоновщик);
  4. Библиотеки различного назначения.

Основные этапы создания программы в IDE Borland C++

  1. Настройка опций среды программирования;
  2. Набор исходного текста программы;
  3. Компиляция программы
  4. Компоновка программы
  5. Отладка программы
  6. Запуск программы на исполнение

Текст программы на языке программирования называют исходным модулем (англ. source code, *.cpp).

Объектный модуль (object code,*.obj) результат обработки исходного кода компилятором. Объектный модуль не является самостоятельной единицей и не может быть выполнен.

Исполняемый модуль (*.exe )создается компоновщиком (linker) в результате объединения отдельных объектных модулей и подсоединения необходимых функций стандартной библиотеки.

Стандартная библиотека (library) набор программ для выполнения часто встречающихся задач, в т.ч. и математических функций; модули библиотеки хранятся в откомпилированном виде.

  1.  Среда программирования

Для работы с программой на языке Си необходимо наличие интегрированной среды разработки (IDE). Интегрированная среда – это программа, имеющая встроенный редактор текстов, подсистему помощи, подсистему работы с файлами, подсистему управления компиляцией и редактированием связей, встроенный отладчик, библиотеки заголовочных файлов, библиотеки функций; программы-утилиты. IDE дает возможность получить исполнимый файл (ЕХЕ-файл), не используя другие программы. Для выполнения заданий требуется наличие среды программирования Borland C++. Загружается среда при запуске файла ..\BORLANDC\BIN\ВС.ЕХЕ.

Задание опций интегрированной среды

При работе в IDE необходима настройка нужных опций (дополнительных параметров). Для изменения опций, заданных по умолчанию, используются команда меню Options\Directories, имеющая следующие поля ввода:

  1.  Include Directories — поле используется для задания директориев заголовочных файлов (C:\BORLANDC\INCLUDE). При необходимости возможно задание нескольких директориев, разделяемых символом ‘;’.
  2.  Library Directories — поле используется для задания директориев, содержащих файлы библиотек функций (*.LIB) и объектный файл загрузчика (COM.OBJ).
  3.  Output Directory — поле используется для задания директория, содержащего файлы с расширениями *.OBJ, *.EXE, *.MAP. Если поле не содержит информации, используется текущий директорий.

Для настройки опций компилятора выбирается команда меню Options\Compiler. Наиболее важные опции задаются командой Code Generation, где выбирается используемая модель памяти. Для большинства программ, разрабатываемых в используемой среде, выбирается модель памяти SMALL.

На Рис.1 отображено основное окно системы:

Верхняя строка окна – это главное меню. Опции меню позволяют обратиться к подменю и выбрать соответствующую команду.

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

Выбрать любую клавишу из команд меню можно одним из трех способов:

(1) нажать клавишу F10 и с помощью управляющих клавиш со стрелками выбрать необходимую команду; (2) установить курсор мыши на любое ключевое слово меню и нажать левую кнопку мыши; (3) для быстрого вызова команды использовать «горячие» клавиши и их сочетания..

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

Операции с окнами возможны либо с помощью команд главного меню, либо с помощью горячих клавиш, либо «мышью». Основные операции:

  1. Закрытие окна (активного);
  2. Переключение между окнами;
  3. Изменение размеров окна;
  4. Переключение между текстовым и графическим режимами работы;

  1.  Набор и редактирование текста программы

Набор текста программы можно выполнить встроенным редактором текста или любым другим текстовым редактором (с помощью Notepad). Файлы исходных текстов программ на языке Си имеют расширение *.cpp. Переключение в режим редактирования выполняется автоматически при выборе команды New в меню File или при открытии файла. Для работы с отдельными символами или блоками текста (выделенное подсветкой подмножество символов) применяют команды меню или сочетания клавиш.

  1.  Компиляция, редактирование связей, запуск программы на выполнение.

До начала компиляции и запуска программы следует сохранить набранный текста во избежание его потери при возможном зависании компьютера. Borland C++ включает разнообразные библиотеки функций для управлениями файлами, выполнения ввода-вывода данных, и других действий. Прототипы функций (заголовки с описанием типов формальных параметров и типа возвращаемого функцией значения), макроконстанты, связанные с библиотечными функциями, объединяют в заголовочные файлы, имеющие расширение h. Необходимые для компиляции файлы включаются в текст программы препроцессорной директивой #include, затем текст программы передается непосредственно на обработку компилятору.

Компиляция исходного текста программы осуществляется либо через команду Compile (либо Alt+F9). Команда Make EXE file также запускает программу на компиляцию, и при отсутствии синтаксических ошибок автоматически запускает компоновщик для получения ЕХЕ-файла. Еще одна возможность для запуска программы на компиляцию – команда Run (Ctrl+F9). После успешной компиляции и компоновки полученный ЕХЕ-файл запускается на выполнение.

При написании и вводе текста программы возможны ошибки. Существует две категории ошибок:

  1.  Errors (ошибки) означают серьезную ситуацию, дальнейшая работа невозможна.
  2.  Warnings (предупреждения) означают возможное слабое место в программе, могущее привести к неверным результатам.

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

  1.  Отладка программы

В процессе отладки возможно:

  1.  Осуществлять пошаговое выполнение программы с анализом промежуточных результатов;
  2.  Проверка значения отдельных переменных в ходе выполнения программы»

Пошаговое выполнение программы возможно

с заходом в тело функции при ее вызове в тексте программы (Run\Trace into или F7);

выполнение функции как обычной команды без трассировки по тексту функции (Run\Step over или F8).

Для ускорения процесса отладки используется команда Run\Go to cursor (F4).

Для наблюдения за изменением значений переменных в ходе выполнения программы используется подменю Debug\Watches\Add watch (или Ctrl+F7).

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

Программа на языке Си состоит из директив препроцессора, объявлений глобальных переменных, одной или нескольких функций, cреди которых одна главная (main) функция первой получает управление и руководит дальнейшей работой программы. Комментарий в программе – любая последовательность символов, заключенная между парой символов /*  */ (многострочный комментарий) или после пары символов // и до конца строки (однострочный комментарий)

Общая структура программы на языке Си имеет вид:

<директивы препроцессора>

<определение типов пользователя – typedef>

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

<определение глобальных объектов>

<функции>

Функции, в свою очередь, имеют структуру:

<класс_памяти> <тип> <имя функции> (<объявление параметров>)

{   – начало функции

  <определение локальных объектов>

  <инструкции (команды)>

}   – конец функции

Перед компиляцией программы на языке Си автоматически выполняется предварительная (препроцессорная) обработка текста программы перед компиляцией.

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

- все препроцессорные директивы должны начинаться с символа #, расположенного в первой позиции

- сразу за символом # должно следовать наименование директивы, указывающее текущую операцию препроцессора.

Наиболее распространены директивы #include и #define.

Директива #include используется для подключения к программе заголовочных файлов (обычных текстов) с декларацией стандартных библиотечных функций.

#include <stdio.h> – подключение разделов библиотек, осуществляющих ввод-вывод данных;

#include <conio.h> – функции работы с консолью;

#include <graphics.h>– графические функции;

#include <math.h> – раздел библиотеки с математическими функциями.

Директива #define создает макроконстанту, ее действие – весь файл.

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


2. Задания и методические указания

2.1. Программирование линейных вычислительных процессов. Разветвляющиеся алгоритмы.

Минимально возможная программа на языке Си выглядит таким образом:

Листинг 1.

 main()

{

 return 0; /* комментарий заключен в двухсимвольные ограничители */

}

Функции начинаются с имени, за которым следует пара круглых скобок. За именем функции следует блок операторов, заключенный в фигурные скобки (в данном случае один оператор return). Каждый оператор должен заканчиваться точкой с запятой.

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

  1.  Полная форма: имя_переменной =выражение;

 Например:  y=(x+2)/(3*x)-5;

С помощью одного оператора можнo присвоить одно значение нескольким переменным

x=y=z=0;  /*т.е. x=0, y=0, z=0*/

z=(x=y)*5; /*сначала переменной x присваивается значение переменной y, далее вычисляется выражение x*5, результат присваивается переменной  z*/.

  1.  Сокращенная форма: имя_переменной операция=выражениe;

Например: x*=5;    /* x=x*5; */

s+=7;    /* s=s+7; */

y/=x+3;       /* y=y/(x+3);  */

В языке Си существует операции уменьшения (--) и увеличения (++) значения переменной на 1. Операции могут быть префиксные (++i, --i) и постфиксные (i++, i--). В случае префиксной операции сначала выполняется сама операция (изменяется значение i), потом вычисляется выражение. В случае постфиксной операции сначала вычисляется выражение, затем изменяется значение.

Например: b=7;

n=1;

если c=b*++n;    /* n=n+1; c=b*n;    т.е. c=14 */

если c=b*n++;   /* c=b*n; n=n+1;    т.е. c=7 */

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

  1.  Операторы перехода

Оператор условного перехода if применяется для выбора одной из ветвей вычислений.

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

if (условие ) оператор1;

else оператор2;

Например:  if(x>y) max=x;

else max=y;

Если оператор1 или оператор2 содержат два и более операторов, то они заключаются в фигурные скобки { } (составной оператор). В сокращенной форме записи вторая часть оператора (else оператор2;) может отсутствовать, и в случае ложности условия управление передается на следующий за if оператор. Если оператор1 и оператор2 в свою очередь являются операторами if, то такой оператор называют вложенным. При этом ключевое слово else принадлежит ближайшему предшествующему if.

Общий вид вложенного оператора:  if (условие1) оператор1;

else if(условие2) оператор2;

else  оператор3;

Например:  найти наибольшее значение из трех чисел  x,y,z.

if (x>y)

if (x>z) max=x;

else max=z;

else if(y>z) max=y;

else max=z;

В качестве условий используют следующие операции отношений: < (меньше), <= (меньше или равно), > (больше), >= (больше или равно), != (не равно), = = (равно).

Общий вид условия:

<выражение_1> <знак_операции> <выражение_2>

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

! (отрицание или логическое НЕТ), && (конъюнкция или логическое И), || (дизъюнкция или логическое ИЛИ) (перечислены в порядке убывания приоритетов).

Например:   (0<x)&&(x<=100)

   ((!x)&&(y>0)||((z==1)&&(k>0))

Выражения вычисляются слева направо, пары символов не разделяются.

  1.  Триадный оператор (оператор условного перехода ?:). Его форма:     

имя_переменной =условие ? выражение_1 : выражение_2;

Если условие истинно, то переменной присваивается результат выражения_1, иначе – выражения_2.

Например:  найти наибольшее из двух чисел:   max=a>b ? a : b;

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

if (условие) выражение_1; else выражение_2

  1.  Оператор выбора switch

Общая форма оператора выбора:

switch(выражение)

{ case const1: операторы; break;

   …

  case constN: операторы; break;

  default: операторы;

}

где const1…constN - целые или символьные константы; default - выполняется, если результат выражения не совпал ни с одной константой (может отсутствовать); break -oператор завершения работы switch. После выполнения одной из ветвей case все остальные ветви будут опущены. Оператор switch проверяет, совпадает ли значение выражения с одной из приведенных ниже констант. При совпадении выполняются операторы, стоящие после совпавшей константы.

Например: 

switсh(i)

{ case 1:  f=pow(x,2); break;

case 2:  f=fabs(x);    break;

case 3:  f=sqrt(x);     break;

default: printf(“Ошибка!”);

  exit(1);  }

Рассмотрим пример реализации линейного алгоритма средствами языка Си.

Листинг 2. Вычислить  

#include <stdio.h> /* подключение заголовочных файлов, содержащих функции ввода-вывода */

#include <conio.h> /* подключение заголовочных файлов, содержащих функции работы с консолью */

#include <math.h> /* подключение заголовочных файлов, содержащих математические функции */

#define x 2.444 /* x=2.444 */

#define y 0.00869 /* y=0.00869 */

#define z -130.0 /* z=-130 */

void main(void) /* Заголовок главной функции */

{   /* Начало функции */

double rez,dop,a,b,c; /* Декларирование переменных */

clrscr( );   /* Очистка экрана */

puts(" ЛАБОРАТОРНАЯ РАБОТА N1 - ЛИНЕЙНАЯ ПРОГРАММА ");

dop=fabs(y-x);

a=pow(x,y+1)+exp(y-1);

b=1+x*fabs(y-tan(z));

c=0.5*pow(dop,2)-pow(dop,3)/3;

rez=a/b*(1+dop)+c;

printf("\a\n ОТВЕТ: %lf, Press any key...", rez);

getch( );    /* ЗАДЕРЖКА ДО НАЖАТИЯ ЛЮБОЙ КЛАВИШИ */

}    /* Конец функции */

Выполните приведенную программу и убедитесь в правильности работы:

ОТВЕТ:-0.49871

Листинг 3. Вычислить значение функции F. Вывести сообщение о том, по какой ветви

происходило вычисления функции.

/*__________________________________*/

#include <conio.h>

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#define A 1

#define C 3

double max(double m,double n)    /* функция max с параметрами m и n */ 

{      /* для поиска максимального */

if (m>n) return m    /* значения */

else return n;

}

double min(double m, double n)  /* функция min с параметрами m и n */ 

{      /* для поиска минимального */

if (m<n) return m;    /* значения */ 

 else return n;

}

void main()

{

double x,y,f;      /* декларирование переменных x,y,f */

clrscr();   

puts("Введите значения x и y");

scanf("%lf %lf",&x,&y);  /* ввод значений х и у */

if ((x>0)&&(y<0))

{ f=(A*x+tan(C*y))/(5-2*x);

 puts("F=(а*x+tg(c*y))/(5-2*x)"); }

else if ((x<0)&&(y>0))

{

f=max(pow(x,2.0/3.0),cos(y*y));          /*  вызов функции max */

 puts("F=max(pow(x,2/3),cos(y*y))");

}

else if ((x>0)&&(y>0))

{

f=min(0.5*x-2*pow(sin(y),2),exp(y));     /*  вызов функции min */

puts("F=min(0.5*x-2*pow(sin(y),2),exp(y))");

}

else

{ puts("Функция F не определена\n Press any key...");

getch();

exit(1);  /* ПРИНУДИТЕЛЬНОЕ ЗАВЕРШЕНИЕ ПРОГРАММЫ */

}

printf("ОТВЕТ: F=%lf,\n Press any key...\n",f);   /* ВЫВОД РЕЗУЛЬТАТА */

getch();

}

Задача1. Варианты

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

1.1. , где

1.2.  где

1.3.  где

1.4.   где

1.5.  где

1.6.   где

1.7.   где

1.8. ,  где

1.9. ,   где

1.10.

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

1.11. ,

1.12. ,

1.13. ,

1.14. Ввести три числа x,y,z. Вычислить

a)r=max(min(x,y),z);   b)r=max(x,0)+min(y,z) ;  c)r=min(x,y,0)+max(y,z) ;

d) произведение двух наименьших из 3 чисел

1.15. Ввести четыре числа a,b,c,d. Расположить их  по возрастанию

1.16. Даны длины 3 отрезков A,B,C. Определить возможность построения треугольника и его вид (разносторонний, равнобедренный, равносторонний)

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

1.18. Ввести целое число, представляющее оценку по 10-балльной системе. Вывести «не явился», «неуд.», «удовл.», «хорошо», «отлично» в зависимости от оценки и получить аналог оценки в 5-бальной системе

1.19. Даны 2 вещественных числа x,y. Вывести “Y” или “N” в зависимости от того, принадлежит ли точка плоскости с координатами (x,y) кольцу, ограниченному окружностями с радиусами r  и R (r<R) с общим центром в точке с координатами (a, b)

1.20. Даны два вещественных числа x,y. Если точка плоскости с координатами (x,y) принадлежит треугольнику с вершинами в точках (-2,0), (0,2), (2,0), то обе координаты увеличить в 10 раз, в противном случае x=x-10, y=y-10.


2.2. Программирование циклических алгоритмов

Язык Си имеет три оператора для организации цикла.

  1.  Оператор цикла for

Основная форма оператора цикла for имеет вид:

for (выражение_1; выражение_2; выражение_3 )

оператор;

где  выражение_1 –начальное значение параметра цикла;

выражение_2 – проверка условия на продолжение цикла;

выражение_3 – изменение параметра цикла (коррекция параметра);

оператор – простой или составной оператор языка Си.

Схема работы оператора: вычисляется выражение_1, затем проверяется выражение_2, и в случае «истины» выполняется циклический участок программы, затем производится коррекция параметра, и так до тех пор, пока выражение_2 не примет значение «ложь».

Например:  for (k=1; k<5; k++)  

printf(“\n %d”, k);

В результате выполнения этого оператора печатаются в столбик цифры от 1 до 4.

В качестве параметра цикла можно использовать переменную любого базового типа. Например:   for(ch=’a’; ch<=’z’; ch++) /* вывод на экран букв */

   printf(“ %c”,ch);  /* латинского алфавита */

Досрочное прерывание цикла возможно следующими способами:

- по дополнительному условию;

- используя операторы:

  1.  break;  - завершения работы цикла, в котором находится break, управление передается на первый после цикла выполняемый оператор;
  2.  exit(int Kod); - происходит выход из программы; 
  3.  return;    - осуществляется выход из функции;
  4. с помощью оператора безусловного перехода goto <метка>;

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

Передавать управление извне вовнутрь цикла запрещается.

Любое из выражений цикла for в круглых скобках может отсутствовать, но символ «;» опускать нельзя.

Например: int i=0;

for(; i<3; i++)

puts(“Hello!”);

  1.  Оператор цикла  while

Основная форма циклического оператора с предусловием while:

while (условие)

оператор;

где оператор – это простой, составной или пустой оператор.

Цикл выполняется до тех пор, пока условие принимает значение «истина». Если изначально результат вычисления условия равен 0, цикл while не выполнится ни разу

Например: int i=0;

while(i<3)

{ puts(“Hello!”); i++); }

  1.  Оператор цикла do…while

Основная форма циклического оператора с постусловием do…while:

do

оператор;

while (условие);

где оператор – это простой, составной или пустой оператор.

Поскольку в цикле do…while условие проверяется в конце цикла, то цикл будет выполнен хотя бы один раз. Цикл будет выполняться до тех пор, пока условие не примет ложное значение.

Например: int i=0;

  do

{ puts(“Hello!”); i++); }

while (i<3);

В циклах типа while и do…while допустимы те же способы досрочного выхода из цикла и досрочное завершение текущего шага цикла, как и в операторе for. Внутри циклов while и do…while необходимо предусмотреть изменение переменных, входящих в условие, для предотвращения бесконечного цикла

Например: int i;

for (i=1;i<=300;i++)  /* печать целых чисел, кратных 5 */

{

if (i%5!=0) continue; /* ПЕРЕХОД К СЛЕДУЮЩЕЙ ИТЕРАЦИИ */

printf(“%5d”,i);

}

Пример бесконечного цикла:

 for (; ;) оператор;

Вложенные циклы

В случае вложенных циклов один цикл находится внутри другого, например:

 for(i=n;i<in;i++)

  for(j=m;j<jm;j++)

   оператор;

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

Пример:  int i,j;

for(i=1;i<10;i++)   /* печать таблицы умножения */

{     /* целых чисел */

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

printf(“\n %d*%d=%2d”, i, j, i*j);

  printf(“\n”);

}

Пример использования оператора for:

Листинг 4. Вычислить . На печать программа должна выводить промежуточные и окончательный результаты.

/*__________________________________*/

#include <stdio.h>

#include <conio.h>

void main(void)

{ float s;

int k,N;

clrscr( );    

 puts(“Введите N”);

 scanf(“%d”,&N);

 for (s=0, k=1; k<=N; k++) /* В заголовке цикла можно выполнять */

 {    /* двойное присваивание */

  s+=1.0/k;

 printf(" \n k=%d s=%f ", k, s);

}

printf("\n ОТВЕТ:  s=%f, Press any key...",s);

 getch( );

}

Пример использования оператора while:

Листинг 5. Вводить координаты точек плоскости до тех пор, пока не будет введена точка с координатами (1000, 1000). Найти координаты точек, принадлежащих области из первой или третьей четверти, ограниченной окружностями радиуса 3 и 1 с центром в начале координат

/*__________________________________*/

#include <conio.h>

#include <stdio.h>

#define PI   3.14159265358

int main()

{ int k=0;

float x,y;

clrscr();

puts("x=1000, y=1000 ----exit\n");

scanf("%f %f",&x,&y);  /* ВВОД КООРДИНАТ ПЕРВОЙ ТОЧКИ */

printf("%5d|%9.4lf|%9.4lf|                  |\n",1,x,y);

x=a+h; i=2;

while (!(x= =1000 && y= =1000)) do

{

if ((x*x+y*y<=9 && x*x+y*y>=1) && (x>0 &&  y>0 || x<0 && y<0)) k++ ;

scanf("%f %f",&x,&y); /*ВВОД КООРДИНАТ ТОЧЕК В ЦИКЛЕ*/

}

printf("\nk=%d \nPress any key...",k);

getch();

return 0;

}

Задача2. Варианты

Составить программу для определения таблицы значений функции Y в диапазоне [a,b] изменения аргумента х с шагом h. Значения a, b, h вводятся с клавиатуры. Таблица должна содержать следующие столбцы: порядковый номер, значение аргумента x, значение функции, сообщение о возрастании или убывании функции, разность двух соседних значений функции. Определить максимальное и минимальное значения функции.

2.1.   a=-1,5; b=1,5; h=0,2.

2.2.   a=0,7; b=1,8; h=0,1.

2.3.     a=-0,5; b=2,5; h=0,2.

2.4.     a=-0,9; b=2,7; h=0,3.

2.5.     a=-2; b=0,8; h=0,2.

2.6.     a=-1,9; b=2,7; h=0,3.

2.7.     a=-0,4π; b=0,4π; h=0,5.

2.8.     a=-0,3π; b=1,3π; h= π/10.

2.9.     a=-π/2; b= π/2; h=π/10.

2.10.   a=π; b=2π; h= π/15.

2.11. Дано действительное число а. Найти среди чисел 1, 1+1/2, 1+1/2+1/3+… первое, большее а.

2.12. Для заданного n вычислить .

2.13. Вычислить с точностью =10-4 значение бесконечной суммы

используя операторы for, while

2.14. Вычислить с заданной точностью =10-5 значение по формуле

Даны действительные числа х и eps. Вычислить приближенно значение бесконечной суммы S. Приближение считается полученным, если найдена сумма нескольких слагаемых, и очередное слагаемое оказалось по модулю меньше eps (значение eps=10-5).

2.15.

2.16.

2.17.

2.18.

2.19.

2.20.


2.3. Программирование с использованием одномерных массивов и строк символов

Массивом называют совокупность переменных одного типа, имеющую имя. Доступ к элементу массива производится по имени массива и индексу (целое число), указываемому в квадратных скобках. Индексы у массивов в языке Си начинаются с 0. В программе одномерный массив объявляется следующим образом:

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

где размер – количество элементов одномерного массива.

Размер массива может задаваться константой или константным выражением. Нельзя задавать массив переменного размера, для этого существует отдельный механизм – динамическое выделение памяти.

Например:

int a[5]; /* объявления массива целого типа с элементами a[0], a[1],…a[4] */

В языке Си не проверяется выход индекса за пределы массива. Корректность использования индексов элементов массива контролируется программистом.

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

Например:

char a[]={‘a’, ‘b’,’c’,’d’, ‘e’}; /* 5 элементов */

int a[5]={2,4,6,8,10} /*  декларация массива целого типа с инициализацией значений*/

Если в группе {…} список значений короче, то оставшимся элементам присваивается 0.

Пример работы с одномерным массивом

Листинг 6. В массиве а целого типа найти индекс и значение максимального элемента и переставить его с первым элементом. Подсчитать количество положительных и отрицательных элементов данного мaссива.

/*_____________________________________*/

#include <stdio.h>

#include <conio.h>

void main(void)

{ int a[4]={-1,-20,4,100};  /* объявление массива с инициализацией */

     /* индексы принимают значения от 0 до 3 */

int i,index,max,zam,kp,ko;

clrscr();

puts("\n ИСХОДНЫЙ МАССИВ\n");

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

 printf("%d  ",a[i]);     /* вывод элементов исходного массива */

max=a[0]; kp=0; ko=0;

 for (i=1; i<4; i++)

 { if (a[i]>max)

{    max=a[i]; index=i;     }

 }

zam=a[index]; a[index]= a[0]; a[0]=zam;

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

 {  if (a[i]<0) ko++;

   else kp++;

}

puts("\n РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ\n");

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

printf("%d  ",a[i]);   /* Вывод элементов массива */

printf("\n  положительных элементов массива: %d \n",kp);

printf(" \n  отрицательных  элементов массива: %d,\n\n Press any key...",ko);

getch();

}

Строки, как одномерные массивы символов

Наиболее частым применением одномерных массивов в языке Си являются строки, поскольку отдельного типа данных «строка символов» нет. Работа со строками реализована путем использования одномерных массивов типа char, т.е. строка символов – это одномерный массив типа char, заканчивающийся нулевым байтом (символом с кодом 0). Для нулевого байта определена символьная константа ´\0´(признак окончания строки или нуль-терминатор). Поэтому при объявлении символьных массивов следует задавать размер, достаточный для хранения всех символов строки, и нуль-терминатора: описание: char a[7] означает, что строка содержит шесть символов, а последний байт отведен под нулевой.

Строковая константа в языке Си – это набор символов, заключенных в двойные кавычки. Например: “Лабораторная работа 3”. В конце строковой константы явно указывать символ ´ \0 ´ не нужно, так как это сделает компилятор.

Строки можно инициализировать при объявлении, например:

 char S1[10]=”123456789”, S2[]=”12345”;

в последнем случае размер строки будет установлен по количеству символов.

Для ввода строки с клавиатуры используются стандартные библиотечные функции, прототипы которых приведены в файле <stdio.h>.

Функция scanf( ) вводит значения для строковых переменных со спецификатором ввода %s. При этом функция scanf() вводит символы до появления первого символа “пробел”.

Функция gets( ), обеспечивает ввод строки с пробелами внутри этой строки. При этом ввод строки символов завершается нажатием клавиши ENTER.

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

Вывод строк производится функциями printf( ) или puts( ). Обе функции выводят символьный массив до первого нулевого байта. Функция printf( ) не переводит курсор после вывода на начало новой строки, его следует предусмотреть в строке формата. Функция puts( ) автоматически переводит курсор после вывода строковой информации в начало новой строки.

Операции над строками (массивами символов) выполняются с использованием стандартных функций, прототипы которых размещены в  файле <string.h>. Наиболее часто используемые функции:

  1. Функция strcpy(S1, S2) - копирует содержимое строки S2 в строку S1.
  2. Функция strcat(S1, S2) - присоединяет строку S2 к строке S1 и помещает ее в массив, где находилась строка S1. Нулевой байт, который завершал строку S1, заменяется первым символом строки S2.
  3. Функция strcmp(S1, S2) сравнивает строки S1 и S2 и возвращает значение 0, если строки равны (содержат одно и то же число одинаковых символов); значение <0, если S1<S2; значение >0, если S1>S2.
  4. Функция strlen(S) возвращает длину строки, при этом завершающий нулевой байт не учитывается.
  5.  Функция strstr(S1, S2) возвращает указатель на первое вхождение строки S2 в строку S1.
  6.  Функция strchr(S1, S2) возвращает указатель на первое вхождение символа S2 в строку S1.
  7.  Функции преобразования строки S в число — возвращается число, записанное в строке S, или нуль, если строка не является записью числа:

Целое:   int atoi(S);

Длинное целое long atol(S);

Действительное double atof(S).

8. Функции преобразования числа V в строку S — в строке S формируется запись целого числа V в системе счисления с основание kod:

Целое:   itoa(int V, char S, int kod);

Длинное целое ltoa (long V,char S, int kod);

9. Операция sizeof(параметр) вычисляет размер памяти в байтах, отводимый под объект. Здесь параметр – тип объекта или его идентификатор (но не имя функции!):

sizeof(int)   результат 2 байта;

int b[5]; sizeof(b)  результат 10 байт;

int c[3][4]; sizeof(c) результат 24 байт

Пример работы со строковыми данными 

Листинг 7. В программе  значение строки вводится с клавиатуры, затем введенная строка распечатывается в обратном порядке.

/*__________________________________*/

#include <stdio.h>

#include <string.h>

#include <conio.h>

void main(void)

{ char s[100];  /* объявление символьного массива */

    nt i, k;

clrscr();

puts(" Введите исходную строку");

 gets(s);

k=strlen(s);

 puts("  РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ\n");

 for (i=k; i>=0; i--)

printf("%c",s[i]); /* вывод элементов массива в обратном порядке */

printf("\n Press any key...");

getch();

}

Указатели и операции над адресами

Обращение к объектам любого типа как операндам операций в языке C может проводиться:

- по имени;

- по указателю (косвенная адресация).

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

Указатель объявляется следующим образом:

<базовый тип> *<имя>;

Здесь базовый тип – это тип переменной, адрес которой будет содержать указатель. Имени указателя должна предшествовать звездочка «*».

Например: int *a, *d;  /* указатели a, d можно инициализировать */

   /* адресами целочисленных переменных     */

float *f; /* указатель f можно инициализировать */

 /* адресами вещественных переменных */.

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

- определяется местоположение в оперативной памяти переменной типа указатель;

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

- производится обращение к участку памяти по выделенному адресу для проведения некоторых действий.

Пример 1:

int x,      /* переменная типа int */

*y;     /* указатель на элемент данных типа int */

y=&x;     /* y есть адрес переменной x */

*y=1;     /* косвенная адресация указателем поля x  ИЛИ */

/* “по указанному адресу записать 1”, т.е. x=1  */

Пример 2:

int i, j=8, k=5, *y; /* в одном объявлении можно смешивать простые переменные */

/* и переменные-указатели */

y=&i;

*y=2;     /* i=2  */

y=&j;   /* переустановили указатель на переменную j */

*y+=i;  /* j+=i ,  т.е.  j=j+1 -> j=j+2=10 */

y=&k;   /* переустановили указатель на переменную k */

k+=*y;  /* k+=k, k=k+k = 10 */

(*y)++;   /* k++,  k=k+1 = 10+1 = 11  */

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

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

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

Например:

float p[100]; /* объявлен массив p из 100 элементов с плавающей точкой */

float *q; /* объявлен указатель на тип данных с плавающей точкой */

int i;  /* объявлена переменная целого типа */

Если выполнить операцию q=&p[0] (или q=a); то следующие обращения к i-ому элементу массива эквивалентны: p[i], *(q+i), *(p+i).

Итак, имя массива без указания квадратных скобок есть адрес нулевого элемента массива, поэтому с помощью указателей можно использовать две эквивалентные формы выражений для доступа к элементам массива: q[i]  и *(q+i). Первая форма привычнее и удобна для чтения, вторая – эффективнее по быстродействию.

Очевидно, что следующие выражения также эквивалентны:

&q[0] то же что и &(*q) то же что и q . /* адрес */

*q       то же что и q[0]   /* значение по адресу */

Если переменная q указывает на очередной элемент массива p, то (q+1) указывает на следующий элемент, при этом выполняется соответствующее масштабирование для приращения адреса с учетом длины объекта

Пример работы с указателями

Листинг 8. Упорядочить по алфавиту массив строк (не более 20) длиной не более 10 символов в каждой

/*______________________________*/

#include <conio.h>

#include <stdio.h>

#include <string.h>

void main()

{ char s[20][10],r[10]; int i,j,n;

clrscr();

puts(“enter number of strings”); scanf(“%d”,&n);

for (i=0;i<n;i++) scanf(“%s”,*(s+i));

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

  for (j=(i+1);j<n;j++)

if (strcmp(*(s+i),*(s+j))>0)

{ strcpy(r,*(s+i));  strcpy(*(s+i),*(s+j));   strcpy(*(s+j),r);  }

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

printf(“\n%s”,*(s+i));

getch();

}

Задача3. Варианты

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

3.1. В одномерном массиве из n вещественных элементов вычислить:

- сумму отрицательных элементов массива;

- произведение элементов массива, расположенных между максимальным и минимальным элементами.

3.2. В одномерном массиве из n целых элементов вычислить:

- произведение элементов массива с четными номерами;

- сумму элементов массива, расположенных между первым и последним нулевыми элементами

3.3. В одномерном массиве из n вещественных элементов вычислить:

- сумму элементов массива с нечетными номерами;

- сумму элементов массива, расположенных между первым и последним отрицательными элементами

3.4. В одномерном массиве из n вещественных элементов вычислить:

- максимальный элемент массива;

- сумму элементов массива, расположенных до последнего положительного элемента

3.5. В одномерном массиве из n вещественных элементов вычислить:

- минимальный элемент массива;

- сумму элементов массива, расположенных между первым и последним положительными элементами.

3.6. В одномерном массиве из n вещественных элементов вычислить:

- произведение положительных  элементов массива;

- сумму элементов массива, расположенных до минимального элемента.

3.7. В одномерном массиве из n вещественных элементов вычислить:

- произведение отрицательных  элементов массива;

- сумму положительных элементов массива, расположенных до максимального элемента.

3.8. В одномерном массиве из n целых элементов найти произведение элементов массива, удовлетворяющих условию

3.9. Найти, сколько элементов целочисленного массива A={a[i]} удовлетворяют условию

3.10. Найти самую длинную последовательность элементов массива A={a[i]}, образующих геометрическую прогрессию.

3.11. Элементы заданного массива A={a[i]}  циклически сдвинуть на K позиций вправо.

3.12. Найти сумму всех элементов массива до первого нуля и его номер.

3.13. Дано число N целого типа. Определить, симметрично ли оно (12321). Записать три последние цифры в одномерный массив.

3.14. Массив преобразовать следующим образом: все числа из отрезка [0, 1] увеличить в 10 раз, отрицательные уменьшить в (-2) раза, остальные уменьшить в 5 раз.

3.15. Ввести с клавиатуры строку символов. Программа должна определить длину введенной строки L, и, если длина L четная, то удаляются все числа, которые делятся на 2.

3.16. Ввести с клавиатуры строку символов. Программа должна определить длину введенной строки L, и, если длина L нечетная, то удаляется символ, стоящий посередине строки.

3.17. Выяснить, имеются ли среди символов S1…Sn некоторой строки все буквы, входящие в слово DOS.

3.18. Ввести с клавиатуры строку символов. Признак окончания ввода строки – нажатие клавиши "Ввод". Составить программу для замены в строке длиной К каждого второго символа на символ $.

3.19. Ввести с клавиатуры строку символов. Программа должна определить длину введенной строки L, и, если длина L>10, то удаляются все цифры

3.20. Ввести с клавиатуры строку символов. Программа должна определить длину введенной строки L, и, если длина L<10, то удаляются все A...Z.


2.4. Программирование с использованием многомерных массивов.

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

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

<тип><имя>[<размер 1 >][<размер 2 >]…[<размер N>]=

{{список начальных значений}, {список начальных значений},…};

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

Например, двумерный массив float b[2][3], содержащий 6 элементов, расположенных в 2 строках и 3 столбцах, в памяти представляется как два подряд расположенные одномерные массивы, в каждом из которых по 3 элемента:

в первом элементы   b[0][0], b[0][1], b[0][2],

во втором элементы b[1][0], b[1][1], b[1][2].

Многомерные массивы инициализируются так же, как и одномерные, но при этом каждое измерение заключается в свои фигурные скобки. Например, инициализация начальными значениями массива целого типа, состоящего из 3 строк и 4 столбцов, выглядит так:

int a[3][4] = {{0,1,2,0},{9,-2,0,0},{-7,1,6,8}};

Если в какой-то группе {…} отсутствует значение, то соответствующему элементу присваивается 0. Предыдущее определение будет эквивалентно следующему:

int a[3][4] = {{0,1,2},{9,-2},{-7,1,6,8}};

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

 for(i=0;i<5;i++)  /*ВВОД ДВУМЕРНОГО МАССИВА */

 for(j=0;j<4;j++) /* ЦЕЛОГО ТИПА int a[5][4] */

 scanf(“%d”,&a[i][j]); /* каждое измерение в своих квадратных скобках */

Пример программы обработки элементов двумерного массива

Листинг 9. Создать двумерный массив целых чисел NxM с помощью генератора случайных чисел, и вывести на экран в форме матрицы. N, M ввести с клавиатуры:

/*__________________________________________ */

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define rnd  (rand()/32768.0)  /* функция rand() генерирует случайное число */ 

/* от 0 до максимального целого; rnd – от 0 до 1 */

void main(void)

{  int i,j,n,m,a[50][50];

puts(“\n Input n, m:”);  scanf(“%d %d”,&n,&m);

printf(“\n Array a \n”);

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

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

 { a[i][j]=rnd*10-5;  /* числа в диапазоне от –5 до 5 */

 printf(“%d%c“, a[i][j], (j==m-1)?’\n’:’  ‘); /* тернарная операция */

}

getch();

}

Указатели на указатели

Для массивов с большим числом измерений также справедлива связь указателей и массивов. Например, двухмерный массив float c[3][4] можно рассматривать как массив трех массивов размерностью по четыре элемента в каждом. В памяти компьютера последовательно размещаются “строки” элементов. Обратиться к элементу c[i][j] можно и по-другому: *(*(c+i)+j), при этом объявление этого массива указателем должно выглядеть так: float**name. Таким образом, имя двухмерного массива можно определить как «указатель на указатель» — это ячейка оперативной памяти, в которой хранится адрес указателя на какую либо переменную. Признак такого типа данных – повторение символа «*» перед идентификатором переменной. Количество символов «*» определяет уровень вложенности указателей друг в друга. При объявлении указателей на указатели возможна их одновременная инициализация.

Например: int a=5;

int *p1=&a;

int **pp1=&p1;

int ***ppp1=&pp1;

Присвоим целочисленной переменной а новое значение: a=10. Тогда

*p1=10; **pp1=10; ***ppp1=10;

Для доступа к области памяти, отведенной под переменную а, можно использовать и индексы. Справедливы следующие соотношения:

*p1 <-> p1[0]; **pp1 <-> pp1[0][0];  ***ppp1 <-> ppp1[0][0][0]

Аналогичные соотношения справедливы и для массивов с любым числом измерений.

Таким образом, указатели на указатели – это имена многомерных массивов

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

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

Функции для выделения и освобождения динамически распределяемой памяти находятся в библиотеке alloc.h. Рассмотрим основные из них:

void *calloc(unsigned n, unsigned m); - возвращает указатель на начало области памяти для размещения n элементов по m байт каждый, при неудачном завершении возвращает значение NULL;

void *malloc(unsigned n);  - возвращает указатель на блок памяти длиной n байт, при неудачном завершении возвращает значение NULL;

void *realloc(void *bf, unsigned n); - изменяет размер ранее выделенной памяти с адресом начала bf на n байт;

void free(void *bf); - освобождает ранее выделенный блок памяти с адресом bf;

coreleft(void); - возвращает значение объема неиспользованной памяти.

При динамическом распределении памяти часто применяется операция sizeof(), с помощью которой можно определить размер участка памяти под объект в байтах:

Например: float *x;    /* Указатель массива типа float */

int n;        /* Количество элементов массива */

 x=(float*)calloc(n,sizeof(float));  /* Захват  памяти для n элементов */

 free(x)     /* Освобождение памяти */

Пример динамического размещения одномерного массива

Листинг 10. Получить массив действительных чисел размером n и вывести на экран.

/*____________________________*/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<alloc.h>

void main(void)

{ int i,n; float *a;

puts(“\n Input n:”);  scanf(“%d”,&n);

printf(“\n Свободная память -%d”,coreleft());

a=(float*)calloc(n,sizeof(float));  /* захват памяти */

printf(“\n Array a \n”);

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

{ *(a+i)=(float)random(10);   /* случайные числа в диапазоне от 0 до 10 */

printf(“  %d“, a[i]);

}

printf(“\n Память после захвата -%d”,coreleft());

free(a);     /* освобождение памяти */

getch();

}

Задача4. Варианты

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

4.1. Сформировать вектор из суммы элементов строк и найти их среднее арифметическое

4.2. Сформировать вектор из наименьших значений элементов строк и найти их среднее арифметическое.

4.3. Сформировать вектор из разностей наименьших и наибольших значений элементов столбцов.

4.4. Найти сумму элементов строки, в которой расположен наименьший элемент.

4.5. Сформировать вектор из суммы модулей отрицательных нечетных элементов в каждом столбце

4.6. Найти сумму всех элементов матрицы и заменить ею все диагональные элементы.

4.7. Получить новую матрицу путем деления всех элементов данной матрицы на ее наибольший по модулю элемент.

4.8. Заменить нулями все элементы матрицы, расположенные на главной диагонали и выше ее.

4.9. Дана вещественная матрица A(N,M). Упорядочить ее строки по неубыванию наибольших элементов в строках матрицы.

4.10. Элемент матрицы назовем седловой точкой, если он наименьший в своей строке и наибольший (одновременно) в своем столбце (или наоборот, наибольший в строке и наименьший в столбце). Для заданной целой матрицы A(N,M) напечатать индексы всех ее cедловых точек.

4.11. Определить, является ли заданная матрица A(N,N) магическим квадратом, т.е. такой, в которой сумма элементов во всех строках и столбцах одинакова.

4.12. Для заданной целой матрицы A(N,N) найти сумму наименьших элементов ее нечетных строк и наибольших элементов ее четных строк.

4.13. Сменить знак минимального элемента матрицы A(N,N), если он находится выше главной диагонали.

4.14. Сменить знак максимального элемента матрицы A(N,N), если он находится ниже побочной диагонали.

4.15. Задана целочисленная матрица A(N,N), состоящая из 0 и 1. Повернуть элементы на 90о  по часовой стрелке.

4.16. В массиве A(N,M) поменять местами столбцы, содержащие максимальный и минимальный элементы.

4.17. В массиве A(N,M) поменять местами строки, содержащие максимальный и минимальный элементы.

4.18. В массиве A(N,M) удалить строку с максимальной суммой четных элементов.

4.19. В массиве A(N,M) удалить столбец с минимальным произведением элементов.

4.20. В массиве A(N,M) расположить строки в порядке возрастания их минимальных элементов


2.5. Функции пользователя

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

Описание функции производят в начале программного файла в виде:

<тип_результата>  <имя_функции>(<тип> <параметр1>, …<тип>   <параметр2>);

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

Например: float fun(int, float, int, int);  /* задание прототипа */

Полное определение функции имеет следующий вид:  

<тип_результата> <имя_функции>(список параметров)

    {

   код функции

     }

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

Оператор return вызывает немедленный выход из данной функции и возврат в вызывающую ее функцию. Этот оператор также используется для возврата результата работы функции. В теле функции может быть несколько операторов return, а может и не быть ни одного. В таких случаях возврат в вызывающую ее функцию происходит после выполнения последнего оператора. Основная функция программы (main) обычно возвращает целочисленное значение. return 0.

Пример: определить наименьшее из двух целых чисел:

 int  mini(int x, int y)

 { int t;

  if (x<y) t=x;

  else t=y;

  return t;

}

Можно реализовать эту же функцию с помощью тернарного оператора:

 mini(int x, int y)

 {

return (x<y)? x : y;

}

По умолчанию возвращаемый результат имеет тип int.

Если функция не возвращает никакого значения, она должна быть описана как функция типа void (пустая). Если у функции отсутствует список параметров, то при объявлении такой функции в круглых скобках также указывают ключевое слово void. Например, заголовок основной функции должен выглядеть так: void main(void).

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

<имя_функции>(список_аргументов)

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

Классы памяти и правила областей действия

В языке Си различают три типа переменных: глобальные, локальные переменные и формальные параметры. Область видимости (действия) локальных переменных – блоки, где они объявлены. При выходе из блока локальная переменная теряется.

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

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

В языке Си каждая переменная принадлежит к одному из четырех классов памяти – автоматическая или локальная (auto), внешняя или глобальная (extern), статическая (static), регистровая (register). Тип памяти указывается одним из приведенных ключевых слов, стоящим перед указанием типа переменной: register int a. Если класс памяти для переменной не указан, она относится к классу auto. Автоматические переменные по отношению к функциям являются внутренними, или локальными. Они начинают существовать при входе в функцию и уничтожаются при выходе из нее.

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

Значения регистровых переменных- помещаются во внутренние регистры процессора с целью их интенсивного использования, для регистровых переменных допустимы два типа: int, char.

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

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

Пример функции, в которой меняются местами значения аргументов x и y:

void swap(int *x, int *y) /* x и y – указатели */

{ int t;

t=*x;  *x=*y; *y=t; /* здесь(*x) и (*y) – значения, на которые указывают указатели */

}

Фрагмент кода с обращением к данной функции :

#include <stdio.h>

main (void)

void swap(int*, int*); /* описание прототипа */

int a, b;

puts(“enter a,b->”); scanf(“%d%d”,&a,&b);

printf(“\n a=%d, b=%d\n”, a, b);

swap(&a, &b);  /* обращение к функции */

printf(“\n a=%d, b=%d”, a, b);

}

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

Когда функция вызывает себя, она называется рекурсивной. Пример рекурсивной функции – вычисление факториала числа n!=1*2*3*…*n:

 int fac(int n)

 { int b;

 if (n= =1) return 1;

 b=fac(n-1)*n;

return n; }

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

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

Листинг 11. Ввести массив NxN целых чисел; и в функции посчитать сумму его положительных элементов через обращение к функции

/*_______________________________________*/

#include <stdio.h>

#include <conio.h>

void sum(int, int b[ ][50]); /* Описание прототипа функции */

void main(void)

{int a[50][50];  int i,j,N;

clrscr();

puts("\n Введите размер массива N (до 50)\n");

scanf(“%d”,&N);

printf("\n Введите данные \n");

 for(i=0; i<N; i++)

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

 {

printf("\n a[%d][%d]=", i+1, j+1);

scanf("%d", &a[i][j]);

}

 sum(N,a);   } /* Обращение к функции */

}

void sum(int n, int b[ ][50])  /* Описание функции sum */

{ int i,j,s;

puts("ФУНКЦИЯ ");

for (s=0,i=0; i<n; i++)

{

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

if (b[i][j]>0)  s+=b[i][j];

printf("\a\n  СУММА = %d, Press any key... ",s);

getch();

}

Задача5. Варианты

Значение аргумента x меняется от a до b с шагом h. Для каждого x найти значения функции Y(X), суммы S(x) (ее разложение в ряд c заданной точностью =1.e-6) и вывести в виде таблицы. В основной программе организовать ввод исходных данных (a, b, h), обращение к функции, вывод результатов. Вычисления Y(x), S(x) реализовать в виде функций. Указание: a b.

5.1. ,   

5.2. ,  

5.3. ,  

5.4. ,  

5.5.   

5.6. ,   

5.7. ,  

5.8. ,  

5.9. ,

5.10.,   

5.11.,  

5.12. ,  

5.13.Даны отрезки a,b,c,d. Для каждой тройки этих отрезков, из которых можно построить треугольник, вычислить площади треугольников по формуле , где (x,y,z – стороны).

5.14.Дано натуральное число N. Определить, если это возможно, пару натуральных чисел x, y, таких что .

5.15. Дано натуральное число N (N  99). Выяснить, верно ли, что N2 равно кубу суммы цифр числа N.

5.16. Натуральное число из n цифр является числом Армстронга, если сумма его цифр, возведенных в n-ю степень, равна самому числу (как, например, 153=13+53+33 ). Получить все числа Армстронга, состоящие из двух, трех и четырех цифр

5.17. Дано натуральное число N. Удалить из записи числа N цифры 0 и 5, оставив прежним порядок остальных цифр (например, из числа 59015509 получить число 919).

5.18. Дана строка символов. Выделить в ней все цифры, записать в массив.

5.19. Дана строка символов. Выделить в ней все строчные буквы латинского алфавита, записать в массив.

5.20. Задана целочисленная матрица A(N,M). Определить номер столбца (столбцов), содержащего только положительные элементы. При отсутствии такого столбца вывести сообщение.


2.6. Программирование алгоритмов с использованием структур

Запись или структура – это объединение одного или более логически связанных данных разных типов (переменных, массивов, указателей и т.п.). Структурный тип данных определяется описанием:

struct имя_структуры { /* вначале следует ключевое слово struct */

тип_элемента_1 имя_элемента_1, …, тип_элемента_n имя_элемента_n;

      };

При описании без последующего списка никакой памяти не выделяется, просто определяется шаблон структуры Для выделения памяти под структуру надо определить структурную переменную:

struct имя_структуры имя_переменной;

Например: struct gr   /* имя структуры */

{ char fio[10];   /* элемент структуры 1 */

int est[25]:   /* элемент структуры 2 */

int nomer;   /* элемент структуры 3 */

} gruppa1;   /* имя структурной переменной */

struct gr gruppa2;  /* объявление структурной переменной */

struct gr *sved;  /* объявление указателя на структуру */

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

Например:  struct date { int day,month,year;} *BirthDay;

struct date d[5]={ { 1,3,1980 },

  { 5,1,1990 },

 { 1,1,2002 } };

Для ввода значений элементов структур можно использовать оператор ввода scanf.

Над структурами допускаются следующие операции:

1) Взятие адреса структуры. Адрес структуры может быть получен путем применения операции указатель (&) к структурной переменной.

2) Доступ к элементу структуры можно выполнить с помощью операций:

точка (.) —прямой доступ — в виде  имя_структуры.имя_элемента

или      (*указатель_структуры).имя_элемента

стрелка ( -> ) — доступ по указателю — в виде

указатель_структуры->имя_элемента

Например: (*BirthDay).day=11; (*BirthDay).month=10; (*BirthDay).year=2000;

или  BirthDay-> day=11; BirthDay-> month=10; BirthDay->year=2000.

Замечание: круглые скобки в первом варианте необходимы, т.к. точка (.) имеет более высокий приоритет, чем звездочка (*).

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

Пример использования структур

Листинг 12. Ввести сведения о студентах учебной группы (до 50), включающие фамилию, номер группы, 3 экзаменационные оценки. Рассчитать средний балл и выполнить поиск по первой букве фамилии.

/*______________________________________________*/

#include <stdio.h>

#include <string.h>

#include <conio.h>

#include <iostream.h>

struct Spisok {

char FIO[20];  /* поле для ФИО студента */

char GR[10];  /* поле для номера группы */

 int MARK[3];  /* поле для оценок */

 float BALL;

 } *sved;

/* описание подпрограммы, в которой вводятся сведения о студенте */

 void VVEDI(int nom,struct Spisok *sved)

{printf("\n Enter info about %d student" ,(nom+1)); /* текущий номер введенной информации */

puts("\n FIO -> ");

fflush(stdin);  /* функция  очистки буфера ввода */

gets(sved->FIO);

puts(" Grup number ->");

fflush(stdin);

gets(sved->GR);

float s=0;

for(int i=0;i<3;i++)

{ printf("\n mark %d = ",i+1);

 scanf(“%d”,&(sved->Ot[i]));

 s+=sved->Ot[i]; /* подсчет суммы оценок */

}

sved->BALL=s/3.;   /* подсчет среднего балла */

}

void main(void)  /* заголовок основной программы */

{ struct Spisok Stud[50];  /* массив для списка группы */

int i, N;

char letter;

clrscr();

puts("\n Vvedi kol-vo < 50 ");

scanf(“%d”,&N);

for(i=0;i<N;i++)  

VVEDI(i,&Stud[i]); /* обращаемся к процедуре ввода сведений */

puts(“\nSpisok Students");

for(i=0;i<N;i++)

printf("\n %20s %10s %4.2f",Stud[i].FIO, Stud[i].GR, Stud[i].BALL);

puts("\n Poisk FIO po bukve. Vvedi bukvu: ");

scanf(“%c”,&letter);

puts("\n  Sveden o Students");

int kod_p=0;

for(i=0;i<N;i++)

if(Stud[i].Fio[0]==letter) /* операция сравнения: 2 знака равенства */

{ kod_p=1;

 printf("\n %20s %10s %4.2f",Stud[i].FIO, Stud[i].GR, Stud[i].BALL);

}

if (kod_p==0) cout << " HET СВЕДЕНИЙ!";

("\n РАБОТА ПРОГРАММЫ ЗАВЕРШЕНА! Press any key...");

getch();

}

Элементами структуры могут быть одна или несколько структурных переменных. Рассмотрим примеры программ работы со сложными структурами.

Листинг 13.  Передача элементов структуры в функцию

/*_____________________________________________*/

#include <conio.h>

#include <stdio.h>

#define k 2  /* т.е. k=2 */

#define PE  printf("\n ..СУММА АВАНСА ЗА %d МЕСЯЦА......",k);

 #define PE1 printf("\n=======================================");

 #define PE2 printf("\n");

struct fund

{ char *mes_avans1;

float avans1;

char *mes_avans2;

float avans2;

};

float sum(float x, float y)

{ clrscr(); PE; PE1; PE2;

return(x+y);

}

void main()

{ static struct fund st={"AUGUST",

600,

"OCTOBER",

800

};

float res;

res=sum(st.avans1, st.avans2);

printf(" \n Total sum is %8.2f rub.",res);

PE2; PE1;

getch();

}

Задача6. Варианты

6.1. Описать структуру с именем STUDENT, содержащую следующие поля:

  1. фамилия и инициалы;
  2. номер группы;
  3. успеваемость (массив из 5 элементов);

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа STUDENT;
  2. отсортировать записи по возрастанию номера группы;
  3. вывести фамилии и номера групп для студентов со средним баллом выше 8;
  4. если таковых нет, вывести соответствующее сообщение.

6.2. Описать структуру с именем STUDENT, содержащую следующие поля:

  1. фамилия и инициалы;
  2. номер группы;
  3. успеваемость (массив из 5 элементов);

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа STUDENT;
  2. отсортировать записи по возрастанию среднего балла;
  3. вывести фамилии и номера групп для студентов, имеющих оценки 8 и 9;
  4. если таковых нет, вывести соответствующее сообщение.

6.3. Описать структуру с именем STUDENT, содержащую следующие поля:

  1. фамилия и инициалы;
  2. номер группы;
  3. успеваемость (массив из 5 элементов);

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа STUDENT;
  2. отсортировать записи по алфавиту;
  3. вывести фамилии и номера групп для студентов, имеющих хотя бы одну оценку 6;
  4. если таковых нет. Вывести соответствующее сообщение.

6.4. . Описать структуру с именем STUDENT, содержащую следующие поля:

  1. фамилия и инициалы;
  2. номер группы;
  3. успеваемость (массив из 5 элементов);

Написать программу, выполняющую следующие действия:

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

6.5. Описать структуру с именем STUDENT, содержащую следующие поля:

  1. фамилия и инициалы;
  2. номер группы;
  3. успеваемость (массив из 5 элементов);

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа STUDENT;
  2. упорядочить записи по алфавиту;
  3. вывести список студентов, фамилии которых начинаются с буквы A, и их оценки по всем предметам.

6.6. Описать структуру с именем STUDENT, содержащую следующие поля:

  1. фамилия и инициалы;
  2. номер группы;
  3. успеваемость (массив из 5 элементов);

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа STUDENT;
  2. вычислить общий средний балл всех студентов;
  3. вывести список студентов со средними баллами выше общего среднего балла.

6.7. Описать структуру с именем BELAVIA, содержащую следующие поля:

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

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа BELAVIA;
  2. отсортировать записи по возрастанию номера рейса;
  3. вывести номера рейсов и типы самолетов, вылетающих в пункт назначения, название которого соответствует введенному с клавиатуры;
  4. если таких рейсов нет, вывести соответствующее сообщение.

6.8. Описать структуру с именем BELAVIA, содержащую следующие поля:

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

Написать программу, выполняющую следующие действия:

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

6.9. Описать структуру с именем EMPLOYEE, содержащую следующие поля:

  1. фамилия и инициалы работника;
  2. название занимаемой должности;
  3. год поступления на работу;

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти структур типа BELAVIA;
  2. отсортировать фамилии в алфавитном порядке;
  3. вывести фамилии работников, чей стаж работы превышает значение, введенное с клавиатуры;
  4. если таких  нет, вывести соответствующее сообщение

6.10. Описать структуру с именем TRAIN, содержащую следующие поля:

  1. название пункта назначения;
  2. номер поезда;
  3. время отправления;

Написать программу, выполняющую следующие действия:

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

6.11. Описать структуру с именем TRAIN, содержащую следующие поля:

  1. название пункта назначения;
  2. номер поезда;
  3. время отправления;

Написать программу, выполняющую следующие действия:

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

6.12. Описать структуру с именем TRAIN, содержащую следующие поля:

  1. название пункта назначения;
  2. номер поезда;
  3. время отправления;

Написать программу, выполняющую следующие действия:

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

6.13. Описать структуру с именем NOTE, содержащую следующие поля:

  1. фамилия, имя;
  2. номер телефона;
  3. дата рождения (массив из трех чисел);

Написать программу, выполняющую следующие действия:

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

6.14. Описать структуру с именем NOTE, содержащую следующие поля:

  1. фамилия, имя;
  2. номер телефона;
  3. дата рождения (массив из трех чисел);

Написать программу, выполняющую следующие действия:

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

6.15. Описать структуру с именем NOTE, содержащую следующие поля:

  1. фамилия, имя;
  2. номер телефона;
  3. дата рождения (массив из трех чисел);

Написать программу, выполняющую следующие действия:

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

6.16. Описать структуру с именем PRICE, содержащую следующие поля:

  1. название товара;
  2. название магазина, где продается товар;
  3. стоимость товара.

Написать программу, выполняющую следующие действия:

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

6.17. Описать структуру с именем PRICE, содержащую следующие поля:

  1. название товара;
  2. название магазина, где продается товар;
  3. стоимость товара.

Написать программу, выполняющую следующие действия:

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

6.18. Описать структуру с именем ORDER, содержащую следующие поля:

  1. расчетный счет плательщика (включая фамилию);
  2. расчетный счет получателя;
  3. перечисляемая сумма.

Написать программу, выполняющую следующие действия:

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

6.19. Описать структуру с именем ATS, содержащую следующие поля:

  1. фамилия и имя абонента;
  2. адрес;
  3. номер телефона.

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти элементов типа ATS
  2. упорядочить записи по возрастанию номеров телефонов;
  3. вывести на экран список абонентов дома, адрес которого вводится с клавиатуры;
  4. упорядочить список по алфавиту.

6.20. Описать структуру с именем ATS, содержащую следующие поля:

  1. фамилия и имя абонента;
  2. адрес;
  3. номер телефона.

Написать программу, выполняющую следующие действия:

  1. ввод данных в массив, состоящий из десяти элементов типа ATS
  2. упорядочить записи в алфавитном порядке по названию улицы;
  3. все номера телефонов, начинающиеся с цифры x (вводится с клавиатуры), заменить на номера, начинающиеся с цифры y (вводится с клавиатуры);


2.7. Файлы в языке Си

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

Прежде, чем получить возможность чтения или записи информации в файл, его нужно открыть для доступа. Это можно сделать, например, с помощью библиотечной функции fopen(“строка1”, “строка2”). Она связывает физический файл на носителе, путь к которому указывается в строке1, например С:\\WORK\\LR7.CPP, с внутренним логическим именем, которое далее используется в программе. В строке2 указываются коды режимов доступа к открываемым файлам (табл.). Логическое имя – это указатель на файл, т.е. на область памяти, где хранится информация о файле. Указатели на файлы необходимо объявлять. Формат объявления такого указателя следующий:

FILE  *указатель на файл;

Здесь FILE – имя типа, описанное в стандартном определении stdio.h.

Например.

  FILE  *f;

  f=fopen ("С:\\WORK\\LR7.CPP ", "w");

Символ "w" определяет право доступа к открываемому файлу. В данном случае открывается файл LR7.СPP в папке С:\WORK только для записи.

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

 Таблица

Символ

Описание

r

Файл открывается только для чтения. Если нужного файла на диске нет, то возникает ошибка.

w

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

a

Файл открывается в режиме только для записи с добавлением новой информации в конец файла. Чтение информации из файла не разрешено

r+

Существующий файл открывается для чтения и записи

w+

Создается новый файл для чтения и записи. Существующий файл с тем же именем перезаписывается

a+

То же, что и для a, только запись можно выполнять в любое место файла. Доступно и чтение файла.

t

Файл открывается в текстовом режиме. Указывается поле r, w, a, r+, w+, a+.

b

Файл открывается в двоичном режиме. Указывается поле r, w, a, r+, w+, a+.

Файлы в языке Си бывают двух видов: текстовые и двоичные. Текстовые файлы широко распространены, но являются лишь одним из видов файлов. Двоичные файлы оптимальны по скорости доступа к данным (не требуют преобразования из текстового формата в двоичный, и обратно) и по экономии памяти (значение переменной в текстовой форме может занимать гораздо больше места, включая управляющие символы «перевод строки», «возврат каретки»).

По умолчанию файл открывается в текстовом режиме. Если при открытии файла произошла ошибка, функцией fopen() возвращается значение NULL.

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

После работы с файлом, доступ к файлу необходимо закрыть. Закрывает файл в языке Си функция fсlose:  fclose (f);

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

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

Посимвольный ввод-вывод для текстовых файлов

В операциях посимвольного ввода-вывода происходит прием одного символа из файла или передача одного символа в файл.

Функция

Действие функции

int  fgetс(FILE *fp)

Чтение и возврат символа из открытого файла

int getc(FILE *fp)

Те же действия: символ из файла, переведенный в int

int fputс(int ch, FILE *fp)

Записывает в файл код символа ch

int putс(int ch, FILE *fp)

Те же действия: записывает в файл символ, переведенный в unsigned char

Построчный ввод-вывод для текстовых файлов

В операциях построчного ввода-вывода за один прием происходит перенос из файла (или в файл) строк символов.

Функция

Действие функции

char *gets (char *S)

Читает байты из файла stdin и записывает их в строку S до тех пор, пока не встретит символ '\n', который заменяется на нуль–терминатор; возвращает s или NULL

char *fgets (char *S, int m, FILE *fp)

Извлекает байты из файла fp, и записывает их в строку S до тех пор, пока не встретит символ '\n', или пока не будет считано m байтов.

int fputs (char *S, FILE *fp)

Записывает в файл байты из строки S до тех пор, пока не встретится нуль-терминатор; возвращает неотрицательное целое или EOF в случае ошибки

int puts (char *S)

Записывает в файл stdout байты из строки S до тех пор, пока не встретится нуль-терминатор, который в файле заменяется на символ '\n'.

Замечание: В отличие от puts(), функция fputs() не добавляет в результирующую строку символ перехода ‘\n’ на новую строку. Поэтому после fputs() следует вызвать функцию fputс() с символом новой строки в качестве аргумента: fputc(‘\n’,fp).

Блоковый ввод-вывод

В операциях блокового ввода-вывода работа происходит с целыми блоками информации. Функции блокового (прямого) ввода-вывода удобны для работы с бинарными файлами.

Функции

Действие функции

int fread (void *ptv, int size, int n, FILE *fp)

Считывает n блоков по size байт каждый из файла fp, в область памяти, на которую указывает указатель ptv (необходимо заранее отвести память под считываемый блок); возвращает количество считанных объектов.

int fwrite (void *ptv, int size, int n, FILE *fp)

Записывае n блоков по size байт каждый из области памяти, на которую указывает ptv, в открытый файл fp.

Для работы с текстовыми файлами обычно используют функции fprintf(), fscanf(), где в качестве первого аргумента задана переменная типа FILE*.

Например:

fprintf(f1,”%d + %d = %5d”,a1,a2,a1+a2); /* записать в файл 2 переменные и их сумму */

fscanf(f1,”%f%f”,&a1,&a2);   /* прочитать из файла 2 переменные */

Пример работы с файлами.

Листинг 14. Сформировать целочисленный бинарный файл, записать в конец новые данные, сохранить и вывести на печать:

/*___________________________*/

#include <stdio.h>

#include <conio.h>

void main(void)

{ int a=1, b=20, c, d;

FILE *in, *out, *add;

 clrscr();

/* ........ ЗАПИСЬ ЧИСЕЛ В ФАЙЛ ......*/

in=fopen("С:\\lr7.dat","wb");

 fprintf(in,"%d %d \n",a,b); /* пробел в спецификации формата обязателен! */

fclose(in);

puts("ЧИСЛА a, b ЗАПИСАНЫ В ФАЙЛ");

puts("Press any key...");

getch();

/* .........ЧТЕНИЕ ЧИСЕЛ ИЗ ФАЙЛА ........*/

out=fopen("C:\\lr9.dat","rb");

if (!out)  {

 puts(“Ошибка открытия файла! ”);

 getch();  exit(1);

 }

fscanf(out,"%d%d", &a, &b);

printf("\n a=%d, b=%d ", a, b);

fclose(out);

puts("\n ЧИСЛА ПРОЧИТАНЫ ИЗ  ФАЙЛА");

 puts("Press any key...");

getch();

/* ......... ДОПОЛНЕНИЕ  ФАЙЛА ..........*/

add=fopen("lr9.dat","a");

puts("ВВЕДИТЕ ЧИСЛА ЦЕЛОГО ТИПА c и d");

 scanf("%d%d",&c,&d);

fprintf(add,"%d %d  \n",c,d);

printf("\n c=%d d=%d \n ",c,d);

fclose(add);

puts("ЧИСЛА c и d ДОПИСАНЫ В ФАЙЛ");

 puts("Press any key...");

getch();

/* ......... ЧТЕНИЕ ЧИСЕЛ ИЗ ФАЙЛА ........*/

out=fopen("lr9.dat","rb");

 fscanf(out,"%d%d%d%d", &a, &b, &c, &d);

printf("\n a=%d b=%d ", a, b);

printf("\n c=%d d=%d ", c, d);

fclose(out);

puts("\n РАСШИРЕННЫЙ  ФАЙЛ!");

puts("Press any key...");

getch();

}

Листинг 15. Сформировать бинарный файл, содержащий сведения: ФИО, оценки, средний балл. Вывести содержимое на печать.

/*_________________________________*/

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

struct Sved{

char fio[20];

int ots[3];

float sb;

} zap;

FILE *Fzap;

void main(void)

{ int i, j, size=sizeof(Sved),N; float s;

clrscr();

Fzap=fopen(“с:\\myf.dat”,”wb”); /* создать файл для записи в двоичном режиме */

puts(“Vvedi kol-vo zapisei “);

scanf(“%d”,&N);

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

{ puts(“ vvedi FIO  “);

scanf(“%s”,zap.fio);

puts(“ vvedi 3 otsenki”);

for (s=0,i=0; i<3; i++)

{ scanf(“%d”,&zap.ots[i]); s=s+zap.ots[i];  }

zap.sb=s/3.0;

fwrite(&zap, size, 1, Fzap);

}

fclose(Fzap);

Fzap=fopen(с:\\myf.dat”,”rb”);  /* чтение информации из бинарного файла */

if (!Fzap)

{ puts(“can’t open it! ”); exit(1);  }

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

{ fread(&zap, size, 1, Fzap);

 printf(“%20s %2d %2d %2d %5.2f \n”,zap.fio, zap.ots[0],zap.ots[1],zap.ots[2],zap.sb);

}

 fclose(Fzap);

getch();

}

Задача7. Варианты

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

7.1. Список товаров, имеющихся на складе, включает

  1. наименование товара;
  2. количество единиц товара;
  3. цену единицы товара;
  4. дату поступления товара на склад.

Написать программу, выводящую в алфавитном порядке список товаров, хранящихся более одного месяца, стоимость которых превышает 10000 руб. Если таких нет, вывести соответствующее сообщение

7.2. В справочной автовокзала хранится расписание движения автобусов. Для каждого рейса указаны

  1. номер рейса;
  2. тип автобуса;
  3. пункт назначения;
  4. время отправления;
  5. время прибытия на конечный пункт

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

7.3. На междугородней АТС информация о разговорах содержит

  1. дату разговора;
  2. код и название города;
  3. время разговора;
  4. тариф;
  5. номер телефона в этом городе
  6. номер телефона абонента;

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

7.4. Для книг, хранящихся в библиотеке, задаются:

  1. регистрационный номер книги;
  2. автор;
  3. название;
  4. год издания;
  5. издательство;
  6. количество страниц

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

7.5. Информация о сотрудниках предприятия содержит:

  1. Ф.И.О;
  2. номер отдела;
  3. должность;
  4. дату начала работы;

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

7.6. Создать файл, содержащий сведения о месячной заработной плате сотрудников отдела. Каждая запись содержит поля

  1. фамилия сотрудника;
  2. наименование отдела;
  3. размер заработной платы за месяц;

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

7.7. Создать файл, содержащий сведения о телефонах абонентов. Каждая запись содержит поля

  1. фамилия абонентов;
  2. год установки телефона;
  3. номер телефона;

На печать вывести информацию следующего вида:

  1. по вводимой с клавиатуры фамилии абонента выдается номер телефона;
  2. определяется количество установленных телефонов с года, значение которого вводится с клавиатуры).

7.8. Создать файл, содержащий сведения о сдаче студентами сессии. Структура записи:

  1. номер группы,
  2. фамилия студента,
  3. оценки по трем экзаменам и трем зачетам (зачет – незачет).

На печать вывести:

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

7.9. Создать файл, содержащий сведения об ассортименте обуви в магазине. Структура записи:

  1. артикул (начинается с буквы Д для женской обуви, М для мужской, П для детской);
  2. наименование;
  3. количество;
  4. стоимость одной пары

На печать вывести информацию:

  1. о наличии и стоимости обуви артикула Х (вводится с клавиатуры);
  2. ассортиментный список женской обуви с указанием наименования и имеющегося в наличии числа пар каждой модели

7.10. Создать файл, содержащий сведения об ассортименте игрушек в магазине. Структура записи:

  1. название;
  2. цена;
  3. количество;
  4. возрастные границы (от 0 до 2, от 2 до 5, от 5 до 7 и т.д.);

На печать вывести информацию:

  1. название игрушек для детей от 1 года до 3 лет;
  2. стоимость самой дорогой игрушки и ее название.

7.11. Создать файл, содержащий данные о сканерах. Структура записи:

  1. модель;
  2. цена;
  3. горизонтальный размер области сканирования;
  4. вертикальный размер области сканирования;
  5. оптическое разрешение

На печать вывести информацию:

  1. модели сканеров с ценой не выше введенной с клавиатуры;
  2. информацию о сканерах с максимальным оптическим разрешением, упорядоченную по цбыванию.

7.12. Создать файл, содержащий данные о ноутбуках. Структура записи:

  1. модель;
  2. цена;
  3. размер диагонали дисплея;
  4. частота процессора;
  5. объем диска

На печать вывести информацию:

  1. данные о ноутбуках с частотой процессора выше 120 МГц, упорядоченные по убыванию цены;
  2. данные о ноутбуках, объем HDD которых меньше 1 Гбайт, упорядоченных по алфавиту

7.13. Составить программу, которая записывает в файл S сначала компоненты файла F, затем компоненты файла G с сохранением порядка.

7.14. Написать программу, которая перепишет с сохранением порядка следования компоненты файла F в файл G, а компоненты файла G в файл F (использовать вспомогательный файл).

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

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

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

7.18. Переписать компоненты символьного файла FS в файл GS, заменив при этом каждый восклицательный знак на точку, а каждое двоеточие – тремя точками.

7.19. Компоненты файла F – натуральные числа. Переписать из него в файл G все удвоенные нечетные числа.

7.20. Составить программу записи из файла F в файл G всех четных чисел, а файл H – всех нечетных чисел.


2.8. Сортировка данных

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

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

Прямые сортировки

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

void swap(int *x, int *y)

{  int t= *x;

 *x=*y ;

 *y=;  }

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

  1.  Пузырьковая сортировка (сортировка простым обменом)

Алгоритм метода состоит в следующем:

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

Например:

Шаг

Элементы массива

44

23

67

11

20

79

50

1

11

44

23

67

20

50

79

2

11

20

44

23

67

50

79

3

11

20

23

44

50

67

79

4

11

20

23

44

50

67

79

5

11

20

23

44

50

67

79

6

11

20

23

44

50

67

79

Листинг 16: Функция bubble() сортирует входной массив методом простого обмена.

/*___________________________________*/

void * bubble(int a[], int n) /* сортировка  пузырьковым  методом */

{int i,j;

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

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

if (a[j] > a[j+1])

swap(&a[j], &a[j+1]); }

Пузырьковая сортировка выполняется при количестве сравнений Q=(n2-n)/2, где n- количество сортируемых значений, и не требует дополнительной памяти. Но алгоритм неэффективен при работе с большими массивами. К тому же число проходов (n-1) может оказаться избыточным (массив может оказаться упорядоченным за меньшее число шагов), поэтому при практической реализации используют различные модифицированные методы сортировки «пузырьком».

  1.  Сортировка методом выбора

Алгоритм метода состоит в следующем:

Находится наименьший элемент исходного массива и помещается на место первого, а первый элемент - на место минимального;

Просматривается подмассив от второго элемента до конца, выбирается минимальный элемент и помещается на второе место, а второй элемент – на место минимального.

Процесс повторяется с оставшимися (n-2), (n-3), …элементами, пока в конце списка не окажется самый большой элемент.

Листинг 17. Функция select() сортирует массив методом выбора.

/*________________________________*/

void select( int s[], int n) /* сортировка методом  выбора */

{ int i,j,k;

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

{ for (k=i, j=i+1; j<n; j++)

   if (s[j]<s[k])

   k=j;

   swap(&s[k], &s[i]); }

}

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

  1.  Сортировка вставкой

Сущность метода сортировки вставками (или метода прямого включения) состоит в следующем: элементы их неотсортированной части выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. На первом шаге выполняется сортировка первых двух элементов массива. Далее к ним добавляется третий элемент, который займет позицию в соответствии со своим значением. Затем добавляется четвертый элемент и т.д. Алгоритм, реализующий данный метод, будет состоять из (n-1) прохода, где n – количество элементов массива.

Листинг 18. Функция insert() реализует сортировку вставкой.

void insert(int s[], int n) /* сортировка  методом   вставки */

{  int i,j;

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

{j=i;

 while (s[j] < s[j-1] && j>=1)

 { swap(&s[j], &s[j-1]); j--; }

}

}

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

Улучшенные сортировки

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

  1.  Cортировка методом Шелла.

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

Расстояния между сравниваемыми элементами могут выбираться по-разному. На практике хорошо себя зарекомендовала последовательность расстояний между сортируемыми элементами 9, 5, 3, 2, 1 или 31, 15, 7, 3, 1. Обязательным условием является то, что последний шаг должен равняться 1.

Листинг 19. Функция ShellSort() реализует сортировку методом Шелла

void ShellSort(int s[], int n) /* сортировка методом Шелла */

{ int i, j, k, temp;

 int gap;   /* текущее расстояние между сравниваемыми элементами */

 int d[] = {9, 5, 3, 2, 1};

for (k=0; k<5; k++)

{ gap=d[k];

  for (i=gap; i<n; i++)

 { temp=a[i];

  for (j=i-gap; temp<a[j] && j>=0; j -=gap) a[j+gap]=a[j];

  a[j+gap]=temp;  }

}

}

Число операций сравнения в методом Шелла пропорционально n log(n), а время выполнения сортировки пропорционально n1.2, что значительно меньше зависимости n2, характерном для прямых сортировок.

  1.  Быстрая сортировка

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

Пример упорядочения набора значений на основе алгоритма быстрой сортировки. Элемент разбиения (выделен полужирным курсивом) должен быть помещен на свое окончательное место в массиве.

37, 2, 6, 4, 89, 8, 10, 12, 68, 45 /* движемся справа и находим элемент < чем 37 */

12, 2, 6, 4, 89, 8, 10, 37, 68, 45 /* движемся слева начиная с элемента сразу за */

    /* подчеркнутым и находим элемент > чем 37 */

12, 2, 6, 4, 37, 8, 10, 89, 68, 45 /* движемся справа начиная с элемента перед 89 */

    /* и находим элемент < чем 37 */

12, 2, 6, 4, 10, 8, 37, 89, 68, 45

и т.д.

Быстрая сортировка требует дополнительной памяти порядка log2(N) для выполнения рекурсивной функции, однако средняя производительность быстрой сортировки выше, чем у всех рассмотренных ранее методов. Алгоритм быстрой сортировки выбирается за основу в большинстве универсальных сортирующих утилит.

Задача8. Варианты

Во всех перечисленных вариантах предусмотреть заполнение массива с помощью генератора случайных чисел. Вывести исходную матрицу и преобразованную.

8.1. Дана матрица целых чисел X[5,5]. Упорядочить элементы в строках по возрастанию (обменом).

8.2. Дана матрица целых чисел X[5,5]. Упорядочить элементы в строках по убыванию (обменом).

8.3. Дана матрица целых чисел X[5,5]. Упорядочить строки по возрастанию элементов первого столбца (выбором).

8.4. Дана матрица целых чисел X[5,5]. Упорядочить строки по убыванию элементов первого столбца (обменом).

8.5. Дана матрица целых чисел X[5,5]. Упорядочить элементы столбцов по возрастанию (обменом).

8.6. Дана матрица целых чисел X[5,5]. Упорядочить элементы столбцов по убыванию (выбором).

8.7. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по убыванию, а сами строки по возрастанию элементов 1-го столбца (выбором).

8.8. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по возрастанию, а сами строки по возрастанию суммы элементов строк (обменом).

8.9. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по неубыванию, а сами строки по убыванию максимальных элементов строк (использовать сортировку вставками).

8.10. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по невозрастанию, а сами строки по возрастанию элементов 5 столбца (использовать сортировку вставками).

8.11. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по неубыванию, а сами строки по убыванию минимальных элементов строк (использовать пузырьковую сортировку).

8.12. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по невозрастанию, а сами строки по возрастанию произведения элементов строк (использовать пузырьковую сортировку).

8.13. Дана матрица целых чисел X[5,5]. Упорядочить элементы столбцов по возрастанию, а сами столбцы по возрастанию произведения четных элементов столбцов. Использовать пузырьковую сортировку.

8.14. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк по убыванию, а сами строки по возрастанию характеристик строк (характеристикой строки матрицы называется сумма ее положительных четных элементов). Использовать сортировку обменом.

8.15. Дана матрица целых чисел X[5,5]. Упорядочить элементы строк с четными номерами по убыванию, а элементы строк с нечетными номерами по возрастанию. Использовать пузырьковую сортировку.

8.16. Дана матрица целых чисел X[5,5]. Расположить элементы побочной диагонали по убыванию. Использовать пузырьковую сортировку

8.17. Дан массив целых чисел X[10]. Отсортировать элементы массива на четных позициях по возрастанию. Использовать любой из методов сортировки

8.18. Дан массив целых чисел X[10]. Отсортировать элементы массива на нечетных позициях по убыванию. Использовать любой из методов сортировки.

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

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


3. Контрольные работы и требования по их выполнению

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

 Таблица 3.1.

Предпослед цифра № зач. книжки

Последняя цифра номера зачетной книжки

0

1

2

3

4

5

6

7

8

9

0

2.3, 3.5, 4.7, 5.9, 6.11, 7.13, 8.15

2.4, 3.6, 4.8, 5.10, 6.12, 7.14, 8.16

2.5, 3.7, 4.9, 5.11, 6.13, 7.15, 8.17

2.6, 3.8, 4.10, 5.12, 6.14, 7.16, 8.18

2.7, 3.9, 4.11, 5.13, 6.15, 7.17, 8.19

2.8, 3.10, 4.12, 5.14, 6.16, 7.18, 8.20

2.9, 3.11, 4.13, 5.15, 6.17, 7.19, 8.1

2.10, 3.12, 4.14, 5.16, 6.18, 7.20, 8.2

2.11, 3.13, 4.15, 5.17, 6.9, 7.1, 8.3

2.12, 3.14, 4.16, 5.18, 6.10, 7.2, 8.4

2

2.11, 3.20, 4.8, 5.1, 6.4, 7.7, 8.9

2.12, 3.19, 4.9, 5.2, 6.5, 7.8, 8.10

2.13, 3.18, 4.10, 5.3, 6.6, 7.9, 8.11

2.14, 3.17, 4.11, 5.4, 6.7, 7.10, 8.12

2.15, 3.16, 4.12, 5.5, 6.8, 7.11, 8.13

2.16, 3.15, 4.13, 5.6, 6.9, 7.12, 8.14

2.17, 3.14, 4.14, 5.7, 6.10, 7.13, 8.15

2.18, 3.13, 4.15, 5.8, 6.11, 7.14, 8.16

2.19, 3.12, 4.16, 5.9, 6.12, 7.15, 8.17

2.20, 3.11, 4.17, 5.10, 6.13, 7.16, 8.18

3

2.13, 3.2, 4.5, 5.9, 6.8, 7.9, 8.2

2.14, 3.3, 4.6, 5.10, 6.9, 7.10, 8.3

2.15, 3.4, 4.7, 5.11, 6.10, 7.11, 8.4

2.16, 3.5, 4.8, 5.12, 6.11, 7.12, 8.5

2.17, 3.6, 4.9, 5.13, 6.12, 7.13, 8.6

2.1, 3.7, 4.10, 5.14, 6.13, 7.14, 8.7

2.2, 3.8, 4.11, 5.15, 6.14, 7.15, 8.8

2.3, 3.9, 4.12, 5.16, 6.15, 7.16, 8.9

2.4, 3.20, 4.13, 5.17, 6.16, 7.17, 8.19

2.5, 3.2, 4.17, 5.19, 6.1, 7.7, 8.9

4

2.6, 3.3, 4.18, 5.20, 6.2, 7.8, 8.10

2.7, 3.4, 4.19, 5.1, 6.3, 7.9, 8.11

2.8, 3.5, 4.20, 5.2, 6.4, 7.10, 8.12

2.9, 3.6, 4.1, 5.3, 6.14, 7.11, 8.13

2.10, 3.7, 4.2, 5.4, 6.15, 7.12, 8.14

2.11, 3.8, 4.3, 5.5, 6.16, 7.13, 8.15

2.12, 3.9, 4.4, 5.6, 6.17, 7.14, 8.16

2.13, 3.10, 4.5, 5.7, 6.18, 7.15, 8.17

2.14, 3.11, 4.6, 5.8, 6.19, 7.16, 8.18

2.15, 3.12, 4.7, 5.9, 6.20, 7.17, 8.19

5

2.10, 3.8, 4.9, 5.11, 6.13, 7.18, 8.9

2.16, 3.13, 4.8, 5.10, 6.1, 7.18, 8.3

2.17, 3.14, 4.9, 5.11, 6.2, 7.19, 8.4

2.18, 3.15, 4.10, 5.12, 6.3, 7.20, 8.5

2.19, 3.16, 4.11, 5.13, 6.4, 7.1, 8.6

2.9, 3.11, 4.19, 5.6, 6.9, 7.5, 8.1

2.20, 3.17, 4.12, 5.14, 6.5, 7.2, 8.7

2.3, 3.18, 4.13, 5.15, 6.6, 7.3, 8.8

2.13, 3.8, 4.11, 5.9, 6.16, 7.1, 8.2

2.4, 3.19, 4.14, 5.16, 6.7, 7.4, 8.9

6

2.5, 3.20, 4.15, 5.17, 6.8, 7.5, 8.8

2.6, 3.3, 4.16, 5.18, 6.9, 7.6, 8.9

2.7, 3.4, 4.17, 5.19, 6.10, 7.7, 8.4

2.8, 3.7, 4.19, 5.1, 6.11, 7.8, 8.4

2.9, 3.8, 4.20, 5.2, 6.12, 7.9, 8.5

2.10, 3.9, 4.8, 5.3, 6.3, 7.10, 8.15

2.16, 3.10, 4.9, 5.13, 6.11, 7.13, 8.5

2.17, 3.11, 4.10, 5.14, 6.12, 7.14, 8.6

2.18, 3.12, 4.11, 5.15, 6.13, 7.15, 8.7

2.19, 3.13, 4.12, 5.16, 6.14, 7.5, 8.2

7

2.20, 3.14, 4.13, 5.17, 6.4, 7.6, 8.3

2.2, 3.15, 4.14, 5.18, 6.5, 7.7, 8.4

2.3, 3.16, 4.15, 5.19, 6.6, 7.8, 8.5

2.4, 3.17, 4.16, 5.1, 6.7, 7.9, 8.6

2.5, 3.18, 4.17, 5.2, 6.8, 7.10, 8.7

2.6, 3.19, 4.18, 5.3, 6.9, 7.11, 8.8

2.7, 3.20, 4.4, 5.4, 6.10, 7.12, 8.9

2.8, 3.2, 4.5, 5.5, 6.11, 7.13, 8.10

2.9, 3.3, 4.6, 5.6, 6.12, 7.14, 8.11

2.10, 3.4, 4.7, 5.7, 6.13, 7.15, 8.12

8

2.11, 3.5, 4.8, 5.8, 6.14, 7.16, 8.13

2.12, 3.6, 4.9, 5.9, 6.15, 7.17, 8.14

2.13, 3.7, 4.10, 5.11, 6.1, 7.7, 8.11

2.14, 3.8, 4.11, 5.12, 6.2, 7.8, 8.12

2.15, 3.9, 4.12, 5.13, 6.3, 7.9, 8.13

2.16, 3.10, 4.13, 5.14, 6.4, 7.4, 8.14

2.17, 3.11, 4.14, 5.15, 6.5, 7.5, 8.15

2.18, 3.12, 4.15, 5.16, 6.17, 7.5, 8.5

2.19, 3.13, 4.16, 5.17, 6.1, 7.6, 8.4

2.9, 3.17, 4.18, 5.19, 6.2, 7.7,8.4

9

2.10, 3.18, 4.19, 5.1, 6.3, 7.8,8.9

2.11, 3.19, 4.1, 5.2, 6.4, 7.9, 8.10

2.12, 3.20, 4.2, 5.3, 6.5, 7.10, 8.11

2.13, 3.2, 4.5, 5.6, 6.6, 7.11, 8.13

2.14, 3.3, 4.6, 5.7, 6.7, 7.12, 8.14

2.15, 3.4, 4.7, 5.8, 6.8, 7.13, 8.15

2.16, 3.5, 4.8, 5.9, 6.9, 7.14, 8.16

2.18, 3.6, 4.9, 5.10, 6.11, 7.15, 8.6

2.19, 3.7, 4.10, 5.11, 6.11, 7.16, 8.7

2.9, 3.17, 4.4, 5.7, 6.11, 7.6, 8.9

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


ЛИТЕРАТУРА

Основная литература

  1. Керниган Б.В., Ритчи Ф.М. Язык программирования С. 2-е изд., – М.: Финансы и статистика, 1992
  2. Дейтел П., Дейтел Х. Как программировать на С. М.: Бином, 2002.
  3. Прата С. Язык программирования С. Лекции и упражнения. Учебник – СПб.: 2002
  4. Юлин В.А., Булатова И.Р. Приглашение к Си. – Мн.: Высш.шк., 1990
  5. Демидович Е.М. Основы алгоритмизации и программирования. Язык Си. – Мн.: Бестпринт, 2003
  6. Подбельский В.В. Язык С++, - М.: ФиС, 2001

Дополнительная литература

  1. Керниган Б., Пайк Р. Практика программирования. СПб.: «Невский диалект», 2001
  2. Касаткин А.И. Профессиональное программирование на языке Си: Справ. Пособие. – Мн.:Выш.шк., 1990.
  3. Шмидский Я.К. Программирование на языке С/C++ – М.: Диалектика, 2003
  4. Павловская Т.А., Щупак Ю.А. Структурное программирование: Практикум – СПб: Питер, 2003


Приложение А.

a)

 б)

  в)

г)

  д)

 е)

ж)

з)

и)

к)

                          л)

                            

м)

Рис. Элементы блок-схем алгоритмов.

Приведенные графические символы обозначают:

а) данные — ввод данных с любого устройства или их вывод на любое устройство;

б) ручной ввод — ввод данных с клавиатуры;

в) данные — вывод данных на печать;

г) дисплей — вывод данных на экран;

д) диск — чтение данных с диска и запись данных на диск;

е) процесс — выполнение операций; расчет;

ж) предопределенный процесс — использование отдельных подпрограмм;

з) подготовка — организация циклических процессов с заданным числом повторений;

и) решение — выбор направления выполнения алгоритма (соответствует условному оператору);

к) терминатор — начало/конец алгоритма либо программы;

л) соединитель — указание связи между отдельными частями;

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


Данной работой Вы можете всегда поделиться с другими людьми, они вам буду только благодарны!!!
Кнопки "поделиться работой":

 

А также другие работы, которые могут Вас заинтересовать

57577. Презентація проекту «Роде мій, красний» 41.5 KB
  Повторити значення слів рід родина рідня; дати поняття про щасливу сім’ю; навчити учнів складати родовідне дерево; виховувати повагу до членів сім’ї історії традицій своєї сім’ї.
57578. Свята та розваги в дошкільному навчальному закладі 67 KB
  Методика ознайомлення дітей з довкіллям у дошкільному навчальному закладу. Мовленнєвий розвиток дітей від народження до 7 років. Отже розглядаючи нормативноправові документи з дошкільної освіти можна стверджувати...
57579. Вертолет Ми-8 1.42 MB
  В данной дипломной работе мне предстоит разобрать силовую установку, ознакомиться с ее особенностями. Описать отказ (выключение) одного двигателя в полете, особенности летной и технической эксплуатации, технологию работы членов экипажа в особых случаях полета.
57580. Сучасний урок – цікавий урок 75 KB
  Метою сучасного заняття стає вже не нагромадження знань а пошукова діяльність спрямована на формування вмінь і навичок щодо орієнтації в інформаційному просторі.
57581. "Любовь – это жизнь, это главное…" Тема кохання в ліриці В. В. Маяковського 114.5 KB
  Маяковський під час футуристичного турне приїжджає до Одеси. Маяковський просить благає дати йому ковток води в жаркій пустелі: Мария Имя твоё я боюсь забытькак поэт боится забытькакоето в муках ночейрождённое слововеличием равное Богу.
57582. ЗАСТОСУВАННЯ ДИФЕРЕНЦІАЛЬНОГО ЧИСЛЕННЯ В ЕКОНОМІЦІ 148.5 KB
  Традиційно практичне застосування похідної використовується при дослідженні функції розв’язуванні задач фізичного чи геометричного змісту. Яким же буде оптимальний обсяг випуску для фірми...
57583. Пісня - душа народу 63 KB
  Взагалі хто і навіщо придумав пісню Чому люди співають радіють і сумують разом з нею Чому старовинні пісні що прийшли до нас із глибини віків і досі живуть у народі Чи уявляєте ви хоча б один свій день без пісні що звучить на вулиці вдома...
57584. Сучасність в музиці 40 KB
  Мета: на прикладі нової музики покращувати вміння аналізувати її; розвивати вокальнохорові навички плавне звуковедення мяке наспівне звучання. Вчити вдумливо ставитися до всякого музичного матеріалу...
57585. Пейзаж – жанр живопису. Створення етюду-малюнку «Дощова хмара» 64 KB
  Мета. Продовжувати ознайомлювати учнів з пейзажним жанром живопису, монохромним живописом; технікою малювання по вологому папері. Вчити виявляти задум в композиції...