Си_Массивы.ppt

Программирование на языке СиЧасть II

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

Практикум (моделирование)
Символьные строки
Рекурсивный перебор
Матрицы
Файлы

Программирование на языке СиЧасть II

Тема 1. Массивы

Массивы

Массивы

A

массив

2

15

A[0]

A[1]

A[2]

A[3]

A[4]

A[2]

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

const int N = 5;

N

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

Еще примеры:

С присвоением начальных значений:

int A[4] = { 8, -3, 4, 6 };
float B[2] = { 1. };
char C[3] = { 'A', '1', 'Ю' };

Что неправильно?

int N = 10;
float A[N];

const int

int X[4.5];

int A[10];
A[10] = 0;

float X[5];
int n = 1;
X[n-2] = 4.5;
X[n+8] = 12.;

int X[4];
X[2] = 4.5;

float B[2] = { 1., 3.8, 5.5 };

int A[2] = { 1, 3.8 };

float

Массивы

Объявление:
Ввод с клавиатуры:
Поэлементные операции:
Вывод на экран:

printf("Введите 5 элементов массива:\n");
for( i=0; i < N; i++ ) {
printf ("A[%d] = ", i );
scanf ("%d", & A[i] );
}

A[0] =
A[1] =
A[2] =
A[3] =
A[4] =

5
12
34
56
13

for( i=0; i < N; i++ ) A[i] = A[i]*2;

printf("Результат:\n");
for( i=0; i < N; i++ )  printf("%4d", A[i]);

Результат:
10 24 68 112 26

Программа

#include
#include
main()
{
const int N = 5;
int A[N], i;
// ввод элементов массива
// обработка массива
// вывод результата
getch();
}

Задания

«4»: Ввести c клавиатуры массив из 5 элементов, найти среднее арифметическое всех элементов массива.
Пример:
Введите пять чисел:
4 15 3 10 14
среднее арифметическое 9.200
«5»: Ввести c клавиатуры массив из 5 элементов, найти минимальный из них.
Пример:
Введите пять чисел:
4 15 3 10 14
минимальный элемент 3

Программирование на языке Си Часть II

Тема 2. Максимальный  элемент массива

Максимальный элемент

Псевдокод:

// считаем, что элемент A[0] – максимальный
for ( i=1; i < N; i++ )
if ( A[i] > максимального )
// запомнить новый максимальный элемент A[i]

Максимальный элемент

max = A[0]; // пока A[0]– максимальный
iMax = 0;
for ( i=1; i < N; i++ ) // проверяем остальные
if ( A[i] > max ) { // нашли новый
max = A[i]; // запомнить A[i]
iMax = i; // запомнить i
}

A[iMax]

Заполнение случайными числами

#include // случайные числа

Целые числа в заданном интервале

int random(int N) {
return rand()% N;
}

x = random ( 100 ); // интервал [0,99]
x = random ( z ); // интервал [0,z-1]

x = random ( z ) + a; // интервал [a,z-1+a]
x = random (b – a + 1) + a; // интервал [a,b]

Заполнение случайными числами

#include
#include


main()
{
const int N = 10;
int A[N], i;
printf("Исходный массив:\n");
for (i = 0; i < N; i++ ) {
A[i] = random(100) + 50;
printf("%4d", A[i]);
}
...
}

int random(int N)
{ return rand() % N; }

Программа

#include
#include
main()
{
const int N = 5;
int A[N], i, iMax;
// заполнить случайными числами [100,150]
// найти максимальный элемент и его номер
printf("\nМаксимальный элемент A[%d] = %d",  iMax, A[iMax]);
getch();
}

Задания

«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем максимальный и минимальный элементы и их номера.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
максимальный a[4]=10
минимальный a[8]=-10
«5»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и найти в нем два максимальных элемента и их номера.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
максимальные a[4]=10, a[7]=8

Программирование на языке Си Часть II

Тема 3. Обработка массивов

Реверс массива

for ( i = 0; i < N; i++ )
// поменять местами A[i] и A[N-1-i]

Как переставить элементы?

2

3

1

4

6

?

4

6

4

x

y

c

c = x;
x = y;
y = c;

x = y;
y = x;

3

2

1

Программа

main()
{
const int N = 10;
int A[N], i, c;
// заполнить массив
// вывести исходный массив
for ( i = 0; i < N/2; i++ ) {
c = A[i];
A[i] = A[N-1-i];
A[N-1-i] = c;
}
// вывести полученный массив
}

Задания

«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить инверсию отдельно для 1-ой и 2-ой половин массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
-4 10 3 -5 4 0 1 -10 8 -6
«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить инверсию для каждой трети массива.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
10 3 -5 4 -10 8 -6 -4 7 5 0 1

Циклический сдвиг

for ( i = 0; i < N-1; i ++)  A[i] = A[i+1];

Программа

main()
{
const int N = 10;
int A[N], i, c;
// заполнить массив
// вывести исходный массив
c = A[0];
for ( i = 0; i < N-1; i ++)
A[i] = A[i+1];
A[N-1] = c;
// вывести полученный массив
}

Задания

«4»: Заполнить массив из 10 элементов случайными числами в интервале [-10..10] и выполнить циклический сдвиг ВПРАВО.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0
Результат:
0 4 -5 3 10 -4 -6 8 -10 1
«5»: Заполнить массив из 12 элементов случайными числами в интервале [-12..12] и выполнить циклический сдвиг ВПРАВО на 4 элемента.
Пример:
Исходный массив:
4 -5 3 10 -4 -6 8 -10 1 0 5 7
Результат:
1 0 5 7 4 -5 3 10 -4 -6 8 -10

Программирование на языке Си Часть II

Тема 4. Сортировка массивов

Сортировка

Метод пузырька

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

Программа (1-ый проход)

сравниваются пары
A[N-2] и A[N-1],
A[N-3] и A[N-2]
…
A[0] и A[1]

A[j] и A[j+1]

for( j = N-2; j >= 0 ; j-- )
if ( A[j] > A[j+1] ) {
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
}

0

Программа (следующие проходы)

2-ой проход

for ( j = N-2; j >= 1 ; j-- )
if ( A[j] > A[j+1] ) {
c = A[j];
A[j] = A[j+1];
A[j+1] = c;
}

1

(i+1)-ый проход

for ( j = N-2; j >= i ; j-- )
...

i

Программа

main()
{
const int N = 10;
int A[N], i, j, c;
// заполнить массив
// вывести исходный массив
for (i = 0; i < N-1; i ++){
for (j = N-2; j >= i ; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
}
}
// вывести полученный массив
}

i

Метод пузырька с флажком

do {
flag = 0; // сбросить флаг
for (j = N-2; j >= 0; j --)
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = 1; // поднять флаг
}
}
while ( flag ); // выход при flag = 0

flag = 0;

flag = 1;

( flag );

int flag;

Метод пузырька с флажком

i = 0;
do {
flag = 0; // сбросить флаг
for ( j = N-2; j >= i ; j -- )
if ( A[j] > A[j+1] ) {
с = A[j];
A[j] = A[j+1];
A[j+1] = с;
flag = 1; // поднять флаг
}
i ++;
}
while ( flag ); // выход при flag = 0

i = 0;

i

i ++;

Метод выбора

Метод выбора

N

for( i = 0; i < N-1 ; i ++ ) {
nMin = i ;
for ( j = i+1; j < N; j ++)
if( A[j] < A[nMin] ) nMin = j;
if( nMin != i ) {
c = A[i];
A[i] = A[nMin];
A[nMin] = c;
}
}

N-1

i+1

i

Задания

«4»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать его по последней цифре.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
30 11 41 32 13 14 25 76 97 58
«5»: Заполнить массив из 10 элементов случайными числами в интервале [0..100] и отсортировать первую половину по возрастанию, а вторую – по убыванию.
Пример:
Исходный массив:
14 25 13 30 76 58 32 11 41 97
Результат:
13 14 25 30 76 97 58 41 32 11

Формирование массива по условию

Примитивное решение:

const int N = 5;
int A[N], B[N];
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) B[i] = A[i];

A

B

Формирование массива по условию

int A[N], B[N], count = 0;
// здесь заполнить массив A
for( i = 0; i < N; i ++ )
if( A[i] < 0 ) {
B[count] = A[i];
count ++;
}
// вывод массива B
for( i = 0; i < count; i ++ )
printf("%d\n", B[i]);

A

B

count

Задания

Программирование на языке Си Часть II

Тема 5. Поиск в массиве

Поиск в массиве

Линейный поиск

nX = -1;
for ( i = 0; i < N; i ++)
if ( A[i] == X ) {
nX = i;
break; //выход из цикла
}

break;

nX = -1; // пока не нашли ...
for ( i = 0; i < N; i ++) // цикл по всем элементам
if ( A[i] == X ) // если нашли, то ...
nX = i; // ... запомнили номер
if (nX < 0) printf("Не нашли...")
else printf("A[%d]=%d", nX, X);

Двоичный поиск

X = 7

X < 8

8

4

X > 4

6

X > 6

Выбрать средний элемент A[c] и сравнить с X.
Если X = A[c], нашли (выход).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

Двоичный поиск

nX = -1;
L = 0; R = N-1; // границы: ищем от A[0] до A[N-1]
while ( R >= L ){
c = (R + L) / 2;
if (X = = A[c]) {
nX = c;
break;
}
if (X < A[c]) R = c - 1;
if (X > A[c]) L = c + 1;
}
if (nX < 0) printf("Не нашли...");
else printf("A[%d]=%d", nX, X);

>

Сравнение методов поиска

Задания

Программирование на языке Си Часть II

Тема 6. Массивы в процедурахи функциях

Массивы в процедурах

void Reverse ( int A[] , int N )
{
int i, c;
for ( i = 0; i < N/2; i ++ ) {
c = A[i];
A[i] = A[N-1-i];
A[N-1-i] = c;
}
}

int A[]

Массивы как параметры процедур

Массивы в процедурах

void Reverse ( int A[], int N )
{
...
}
main()
{
int A[10];
// здесь надо заполнить массив
Reverse ( A, 10 ); // весь массив
// Reverse ( A, 5 ); // первая половина
// Reverse ( A+5, 5 ); // вторая половина
}

Задания

Массивы в функциях

int Sum ( int A[], int N )
{
int i, sum = 0;
for ( i = 0; i < N; i ++ )
sum += A[i];
return sum;
}

int A[]

Массивы в процедурах и функциях

int Sum ( int A[], int N )
{
...
}
main()
{
int A[10], sum, sum1, sum2;
// заполнить массив
sum = Sum ( A, 10 ); // весь массив
sum1 = Sum ( A, 5 ); // первая половина
sum2 = Sum ( A+5, 5 ); // вторая половина
...
}

Задания

const int N = 5;
int A[N] = { 1, 2, 3, 3, 4 };

Программирование на языке Си Часть II

Тема 7. Практикум  (моделирование)

Моделирование кипения воды

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

#include
#include
#include
const int N = 100;
int X[N], Y[N], r = 3;
void Init (); // начальное положение
void Draw ( int color ); // рисуем, стираем
void Sdvig ( int dy ); // летят вверх
void Zamena (); // ушли, пришли
main()
{
initwindow (600, 400);
... // основная часть программы
closegraph();
}
... // здесь сами процедуры

Основная программа

Init(); // начальная расстановка
while ( 1 ) // зацикливание ???
{


Draw ( YELLOW ); // рисуем все пузырьки
delay ( 10 ); // ждем 10 мс
Draw ( BLACK ); // стираем все пузырьки
Sdvig ( 4 ); // вверх на 4 пикселя
Zamena(); // если за пределами экрана…
}

if ( kbhit() )
if ( getch() == 27 ) break;

Процедура Init

void Init()
{
int i;
for ( i = 0; i < N; i ++ ) {
X[i] = random(600 - 2*r) + r;
Y[i] = random(400 - 2*r) + r;
}
}

Начальная случайная расстановка:

600

Интервал для x: [r, 600-r]

400

Интервал для y: [r, 400-r]

X[i] = random(640 - 2*r) + r;

Y[i] = random(400 - 2*r) + r;

Процедуры Draw, Sdvig

Рисование и стирание:

void Draw ( int color )
{
int i;
setcolor ( color );
for ( i = 0; i < N; i ++ )
circle ( X[i], Y[i], r );
}

Сдвиг вверх:

void Sdvig ( int dy )
{
int i;
for ( i = 0; i < N; i ++ )
Y[i] -= dy;
}

Процедура Zamena

Замена вышедших за границы экрана:

400

void Zamena ()
{
int i;
for ( i = 0; i < N; i ++ )
if ( Y[i] < r ) {
X[i] = random(600 - 2*r) + r;
Y[i] = 400 - r;
}
}

Y[i]< r

Y[i] = 400 - r

Условие выхода:

Перебросить вниз:

if ( Y[i] < r ) { ... }

X[i] = random(600 - 2*r) + r;
Y[i] = 400 – r;

Задания

Программирование на языке Си Часть II

Тема 8. Символьные строки

Чем плох массив символов?

char A[4] = { 'A', '3', '[', 'Ж'};
char B[10];

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

рабочая часть

s[0]

s[1]

s[2]

s[3]

char s[80];

Объявление символьных строк

char s[80];

char s1[80] = "abc";

char qqq[] = "Вася";

Ввод и вывод символьных строк

main()
{
char q[80];
int i;
printf("Введите строку\n");
scanf( "%s", q);
i = 0;
while ( q[i] != '\0' ) {
if ( q[i] == 'а' ) q[i] = 'б';
i ++;
}
printf ( "Результат: %s ", q );
}

%s

"%s"

Ввод одного слова:



Ввод строки с пробелами:

char q[80];
printf ("Введите текст:\n");
scanf ( "%s", q );
printf ("Введено:\n%s", q );

Ввод символьных строк

Введите текст:
Вася пошел гулять
Введено: Вася

char q[80];
printf("Введите текст:\n");
gets ( q );
printf("Введено:\n%s", q );

Введите текст:
Вася пошел гулять
Введено: Вася пошел гулять

gets ( q );

Универсальный способ:



Только для одной строки:

printf ( "Результат: %s", q );

Вывод символьных строк

puts ( q );

printf ( "%s\n", q );

Задания

«4»: Ввести символьную строку и заменить все буквы "а" на буквы "б" и наоборот, как заглавные, так и строчные.
Пример:
Введите строку:
ааббссААББСС
Результат:
ббаассББААСС
«5»: Ввести символьную строку и проверить, является ли она палиндромом (палиндром читается одинаково в обоих направлениях).
Пример: Пример:
Введите строку: Введите строку:
АБВГДЕ КАЗАК
Результат: Результат:
Не палиндром. Палиндром.

Функции для работы со строками

Подключение библиотеки:

#include

char q[80] = "qwerty";
int n;
n = strlen ( q );

n = 6

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

char q1[80], q2[80];
int n;
gets ( q1 );
gets ( q2 );
n = strcmp ( q1, q2 );

Пример решения задачи

Проверка пароля

#include
main()
{
char secret[] = "123", pass[20];
printf ( "Введите пароль\n" );
gets ( pass );
if ( strcmp ( pass, secret ) != 0 )
{
printf ( "Пароль неверный" );
getch ();
return 1;
}
...
}

Основная часть программы

#include
#include
main()
{
char q[80];
int i, len, count = 0;
... // проверка пароля
printf ("Введите предложение\n");
gets ( q );
len = strlen( q );
if ( q[0] != ' ') count++;
for ( i = 0; i < len - 1; i ++ )
if ( q[i] == ' ' && q[i+1] != ' ' )
count ++;
printf ( "Найдено %d слов", count );
}

Подсказка: для вывода одного символа используйте функцию putchar(символ). Например:

Задания (везде – с паролем!)

«4»: Ввести предложение и определить, сколько слов заканчиваются на букву 'а'.
Пример:
Введите предложение: Введите предложение:
Мама мыла раму Декан пропил бутан  Найдено слов: 2 Нет таких слов
«5»: Ввести предложение и разобрать его на отдельные слова:
Пример:
Введите предложение:
Мама мыла раму
Результат:
Мама
мыла
раму

putchar(q[i]);
putchar('\n'); // переход на новую строку

Копирование строк

strcpy (string copy)

char q1[10] = "qwerty", q2[10] = "01234";

strcpy ( q1, q2 );

копирование «хвоста» строки

char q1[10] = "qwerty", q2[10] = "01234";
strcpy ( q1, q2+2 );

q2

q1

q2 = &q2[0]

q2+2 = &q2[2]

Копирование строк

копирование в середину строки

char q1[10] = "qwerty", q2[10] = "01234";
strcpy ( q1+2, q2 );

q2

q1

q1+2 = &q1[2]

char q1[10] = "qwerty", q2[10] = "01234";
strcpy ( q1+2, q2+3 );

q2

q1

q2+3 = &q2[3]

q1+2 = &q1[2]

Копирование строк

strncpy – копирование нескольких символов

char q1[10] = "qwerty", q2[10] = "01234";
strncpy ( q1+2, q2, 2 );

q2

q1

q1+2 = &q1[2]

Копирование строк

копирование строки-константы

char q1[10] = "qwerty";
strcpy ( q1+1, "ABCD");

q1

char q1[10] = "qwerty";
strcpy ( "ABCD", q1+2 );

НЕ

Копирование строк

копирование внутри одной строки

char q[10] = "012345";
strcpy ( q, q+2 );

q

char q[10] = "012345";
strcpy ( q+2, q );

q

Зацикливание и зависание компьютера!

Объединение строк

strcat (string concatenation) = копирование второй строки в конец первой

char q1[10] = "qwe", q2[10] = "0123";
strcat ( q1, q2 );

q2

q1

char q1[10] = "qwe", q2[10] = "0123";
strcat ( q1, q2+2 );

q2

q1

что-то другое

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

char q1[] = "qwer", q2[10] = "01234";
strcpy ( q1+2, q2 );

не хватает места для строки-результата

q2

q1

зацикливание при копировании в ту же строку «слева направо»

char q[10] = "01234";
strcpy ( q+2, q );

Пример решения задачи

Программа

main()
{
char fName[80];
int i;
printf("Введите имя файла\n");
gets ( fName );
i = 0;
while ( fName[i] != '.' ) {
if ( fName[i] == '\0' ) break;
i ++;
}
if ( fName[i] == '.' )
strcpy ( fName+i, ".exe" );
else strcat ( fName, ".exe" );
puts ( "Результат:" );
puts ( fName );
}

Задания

«4»: Ввести полный адрес файла (возможно, без расширения) и изменить его расширение на «.exe».
Пример:
Введите имя файла: Введите имя файла:
C:\DOC.TXT\qqq C:\DOC.TXT\qqq.com
Результат: Результат:
C:\DOC.TXT\qqq.exe C:\DOC.TXT\qqq.exe
«5»: Ввести в одной строке фамилию, имя и отчество. Вывести приветствие, где останутся имя и фамилия (см. пример).
Пример:
Введите ФИО:
Пупкин Василий Иванович
Результат:
Привет, Василий Пупкин!

Поиск в символьных строках

Указатели

char *p; // адрес любого символа или строки
int *pI; // адрес целого числа
float *pF; // адрес вещественного числа

Объявление:

Целые переменные и массивы:

int n = 6, A[5] = {0, 1, 2, 3, 4};
int *p; // указатель на целое
p = &n; // записать адрес n
*p = 20; // n = 20
p = A + 2; // записать адрес A[2] (&A[2])
*p = 99; // изменить A[2]
p ++; // перейти к A[3]
printf("Адрес: %p, число %d", p, *p);

Адрес: 6BCD:000C, значение 3

Указатели и символьные строки

char str[10] = "0123456";
char *p;
p = str;
*p = 'A';
p ++;
*p = 'B';
p ++;
strcpy ( p, "CD" );
strcat ( p, "qqq" );
puts ( p );

// указатель на символ
// или & str[0]
// "A12345"
// перейти к str[1]
// "AB2345“
// перейти к str[2]
// "ABCD"
// "ABCDqqq"

Поиск символа

char q[10] = "abcdabcd";
char *p;
int nomer;
p = strchr(q, 'b');
if ( p == NULL )
printf ( "Не нашли..." );
else {
nomer = p – q;
printf ( "Номер символа %d", nomer );
}

Поиск подстроки

char q[10] = "abcdabcd";
char *p;
int nomer;
p = strstr(q, "bcd");
if ( p == NULL )
printf ( "Не нашли..." );
else {
nomer = p – q;
printf ( "Номер первого символа %d", nomer );
}

p

Пример решения задачи

start

p

p = strstr( start, "Вася");

Программа

main()
{
char q[80], *start, *p;
int count = 0;
puts ( "Введите предложение" );
gets ( q );
start = q; // ищем с начала строки
while ( 1 ) {
p = strstr ( start, "Вася" );
if ( p == NULL ) break;
count ++;
start = p + 4; // отсюда ищем следующее слово
}
printf ( "Имя 'Вася' встречается %d раз", count );
}

Задания

«4»: Ввести предложение и заменить все имена «Вася» на «Юра».
Пример:
Введите предложение:
Вася, Вася, Вася и Вася!!!
Результат:
Юра, Юра, Юра и Юра!!!
«5»: Ввести предложение и заменить все имена «Юра» на «Вася».
Пример:
Введите предложение:
Юра, Юра, Юра и Юра!!!
Результат:
Вася, Вася, Вася и Вася!!!

Строки в процедурах и функциях

c = s[i];
s[i] = s[len-i-1];
s[len-1-i] = c;

s[i]

s[len-1-i]

Программа

void Reverse ( char s[] )
{
int len = strlen(s);
char c;
for ( i = 0; i < len/2; i ++ ) {
c = s[i];
s[i] = s[len-i-1];
s[len-1-i] = c;
}
}
main()
{
char s[] = "1234567890";
Reverse ( s );
puts ( s );
Reverse ( s + 5 );
puts ( s );
}

0987654321

0987612345

Задания

«4»: Разработать процедуру, которая переставляет пары соседних символов.
Пример:
Введите предложение:
Вася пошел гулять!
Результат:
аВясп шолег лутя!ь
«5»: Разработать процедуру, которая удаляет все лишние пробелы (в начале предложения и сдвоенные пробелы).
Пример:
Введите предложение:
Вася пошел гулять!
Результат:
Вася пошел гулять!

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

int NumDigits ( char s[] )
{
int i, count = 0;
for ( i = 0; i < strlen(s); i ++ )
if( strchr ( "0123456789", s[i] ) )
count ++;
return count;
}

if ( strchr ( "0123456789", s[i] ) != NULL )
или
if ( '0' <= s[i] && s[i] <= '9' )

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

Основная программа

int NumDigits ( char s[] )
{
...
}
main()
{
char s[80];
int n;
printf ( "Введите строку\n" );
gets ( s );
n = NumDigits ( s );
printf ( "Нашли %d цифр.", s );
}

Задания

«4»: Разработать функцию, которая определяет, верно ли, что слово – палиндром.
Пример:
Введите слово: Введите слово:
казак кунак
Результат: Результат:
Это палиндром. Не палиндром.
«5»: Разработать функцию, которая определяет, верно ли, что предложение (с пробелами) – палиндром.
Пример:
Введите предложение:
а роза упала на лапу азора
Результат:
Это палиндром.

Программирование на языке Си Часть II

Тема 9. Рекурсивный перебор

Рекурсивный перебор

0

K-1

в каждой ячейке может быть любая из 4-х букв

4 варианта

4 варианта

4 варианта

4 варианта

Количество вариантов:

Рекурсивный перебор

0

K-1

0

K-1

0

K-1

0

K-1

перебрать все варианты

перебрать все варианты

перебрать все варианты

перебрать все варианты

Процедура

0

K-1

p

s

p+1

void Rec( int p )
{
if ( p >= K ) {
puts ( s );
count ++;
return;
}
s[p] = 'Ы'; Rec ( p + 1 );
s[p] = 'Ц'; Rec ( p + 1 );
s[p] = 'Щ'; Rec ( p + 1 );
s[p] = 'О'; Rec ( p + 1 );
}

Процедура

void Rec ( int p )
{
const char letters[] = "ЫЦЩО";
int i;
if ( p >= K ) {
puts ( s );
count ++;
return;
}
for ( i = 0; i < strlen(letters); i ++) {
s[p] = letters[i];
Rec ( p + 1 );
}
}

const char letters[] = 'ЫЦЩО';

for ( i = 0; i < strlen(letters); i ++) {
s[p] = letters[i];
Rec ( p + 1 );
}

Программа

char s[80];
int K, count = 0;

main()
{
printf ( "Введите длину слов:\n" );
scanf ( "%d", &K );
Rec ( 0 );
printf ( "Всего %d слов.", count );
}

void Rec ( int p )
{
...
}

count;

Задания

Программирование на языке Си Часть II

Тема 10. Матрицы

Матрицы

1

2

3

4

5

6

c6

A[5][2]

Матрицы

A

Матрицы

Объявление:

const int N = 3, M = 4;
int A[N][M];
float a[2][2] = {{3.2, 4.3}, {1.1, 2.2}};
char sym[2][2] = { 'a', 'b', 'c', 'd' };

Ввод с клавиатуры:

for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ ) {
printf ( "A[%d][%d]=", i, j);
scanf ( "%d", &A[i][j] );
}

A[0][0]=

25

A[0][1]=

14

A[0][2]=

14

...

A[2][3]=

54

i

j

for ( j = 0; j < M; j ++ )
for ( i = 0; i < N; i ++ ) {

Матрицы

Заполнение случайными числами

for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ )
A[i][j] = random(25)- 10;

Вывод на экран

for ( i = 0; i < N; i ++ ) {
for ( j = 0; j < M; j ++ )
printf("%5d", A[i,j]);
printf("\n");
}

for ( j = 0; j < M; j ++ )
printf("%5d", A[i][j]);

Обработка всех элементов матрицы

main()
{
const int N = 3, M = 4;
int A[N][M], i, j, S = 0;
... // заполнение матрицы и вывод на экран
for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ )
S += A[i][j];
printf("Сумма элементов матрицы S=%d", S);
}

for ( i = 0; i < N; i ++ )
for ( j = 0; j < M; j ++ )
S += A[i][j];

Задания

Операции с матрицами

A[0][N-1]

A[1][1]

A[2][2]

A[N-1][N-1]

for ( i = 0; i < N; i ++ )
printf ( "%5d", A[i][i] );

A[N-1][0]

A[N-2][1]

A[1][N-2]

сумма номеров строки и столбца N-1

A[0][0]

for ( i = 0; i < N; i ++)
printf ( "%5d", A[i][ N-1-i ]);

N-1-i

Операции с матрицами

строка 0: A[0][0]
строка 1: A[1][0]+A[1][1]
...
строка i: A[i][0]+A[i][2]+...+A[i][i]

S = 0;
for ( i = 0; i < N; i ++ )
for ( j = 0; j <= i; j ++ )
S += A[i][j];

for ( j = 0; j <= i; j ++ )
S += A[i][j];

Операции с матрицами

1

3

j

A[1][j]

A[3][j]

for ( j = 0; j <= M; j ++ ) {
c = A[1][j];
A[1][j] = A[3][j];
A[3][j] = c;
}

for ( i = 0; i < N; i ++ )
A[i][3] += A[i][6];

Задания

Программирование на языке Си Часть II

Тема 11. Файлы

Файлы

Файлы

*.txt, *.log,
*.htm, *.html

*.doc, *.exe,
*.bmp, *.jpg,
*.wav, *.mp3,
*.avi, *.mpg

Текстовые

Двоичные

Папки (каталоги)

Принцип сэндвича

f = fopen("qq.dat", "r");

fclose ( f );

fscanf ( f, "%d", &n ); // ввести значение n

fprintf( f, "n=%d", n ); // записать значение n

f = fopen("qq.dat", "w");

f = fopen("qq.dat", "a");

Работа с файлами

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

12 5 45 67 56●

12 5 45 67 56●

f = fopen("qq.dat", "r");

fscanf ( f, "%d", &x );

Ошибки при открытии файла

FILE *f;
f = fopen("qq.dat", "r");
if ( f == NULL ) {
puts("Файл на найден.");
return;
}

NULL

Если файл открыть не удалось, функция fopen возвращает NULL (нулевое значение)!

!

FILE *f;
f = fopen("qq.dat", "w");
if ( f == NULL ) {
puts("Не удалось открыть файл.");
return;
}

NULL

Пример

Как определить, что числа кончились?

FILE *f;
int n, x;
f = fopen("input.txt", "r");
...
n = fscanf ( f, "%d", &x );
if ( n ! = 1 )
puts ( "Не удалось прочитать число" );

Программа

main()
{
FILE *f;
int n, x, S = 0;
f = fopen ( "input.txt", "r" );
if ( f == NULL ) {
printf("Файл не найден.");
return;
}
while ( 1 ) {
n = fscanf ( f, "%d", &x );
if ( n != 1 ) break;
S += x;
}
fclose ( f );
f = fopen ( "output.txt", "w" );
fprintf ( f, "S = %d", S );
fclose ( f );
}

Задания

В файле input.txt записаны числа, сколько их – неизвестно.

Обработка массивов

Чтение данных в массив

int ReadArray ( int A[], char fName[], int MAX )
{
int N = 0, k;
FILE *f;
f = fopen ( fName, "r" );
while ( 1 ) {
k = fscanf ( f, "%d", &A[N]);
if ( k != 1 ) break;
N ++;
if ( N >= MAX ) break;
}
fclose(f);
return N;
}

Программа

main()
{
int A[100], N, i;
FILE *f;
N = ReadArray ( A, "input.txt", 100 );
... // сортировка первых N элементов
f = fopen("output.txt", "w");
for ( i = 0; i < N; i ++)
fprintf ( f, "%d\n", A[i] );
fclose ( f );
}

int ReadArray(int A[], char fName[], int MAX)
{
...
}

Задания

В файле input.txt записаны числа (в столбик), известно, что их не более 100.

Обработка текстовых данных

Задача: в файле input.txt записаны строки, в которых есть слово-паразит "короче". Очистить текст от мусора и записать в файл output.txt.
Файл input.txt :
Мама, короче, мыла, короче, раму.
Декан, короче, пропил, короче, бутан.
А роза, короче, упала на лапу, короче, Азора.
Каждый, короче, охотник желает, короче, знать, где ...
Результат – файл output.txt :
Мама мыла раму.
Декан пропил бутан.
А роза упала на лапу Азора.
Каждый охотник желает знать, где сидит фазан.

Обработка текстовых данных

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

Алгоритм:
Открыть оба файла.
Прочитать строку.
Удалить все сочетания ", короче,".
Записать строку во второй файл.
Перейти к шагу 2.
Закрыть оба файла.

Работа с файлами

main()
{
char s[80], *p;
int i;
FILE *fIn, *fOut;
fIn = fopen("input.txt", "r");
fOut = fopen("output.txt", "w");
... // обработать файл
fclose(fIn);
fclose(fOut);
}

Обработка текстовых данных

Чтение строки s:

while ( 1 ) {
p = strstr ( s, ", короче," );
if ( p == NULL ) break;
strcpy ( p, p + 9 );
}

char s[80], *p;
FILE *fIn;
... // здесь надо открыть файл

p = fgets ( s, 80, fIn );
if ( p == NULL )
printf("Файл закончился.");
else printf("Прочитана строка:\n%s", s);

Обработка строки s:

#include

Полный цикл обработки файла

while ( 1 ) {
p = fgets ( s, 80, fIn );
if ( p == NULL ) break;
while ( 1 ) {
p = strstr ( s, ", короче," );
if ( p == NULL ) break;
strcpy ( p, p + 9 );
}
fputs ( s, fOut );
}

while ( 1 ) {
p = strstr ( s, ", короче," );
if ( p == NULL ) break;
strcpy ( p, p + 9 );
}

Задания

В файле input.txt записаны строки, сколько их – неизвестно.

Двоичные файлы

Файловые указатели

FILE *fp;

Открытие и закрытие двоичных файлов

Открытие файла

fp = fopen ( "input.dat", "rb" );

Ошибки при открытии

if ( fp == NULL ) {  printf("Файл открыть не удалось.");
}

Закрытие файла

fclose ( fp );

Чтение по блокам

Чтение в начало массива

int A[100];
n = fread ( A, sizeof(int), 100, fp );

Чтение в середину массива

int A[100];
n = fread ( A+5, sizeof(int), 2, fp );

Запись по блокам

Запись с начала массива

int A[100];
n = fwrite( A, sizeof(int), 100, fp );

Запись отдельных элементов массива

int A[100];
n = fwrite( A+5, sizeof(int), 2, fp );

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

Хранение в памяти: по строкам (Си, Паскаль)

Запись матрицы

int A[3][3];
FILE *fp = fopen("output.dat", "wb");
... // здесь заполняем матрицу
n = fwrite( A, sizeof(int), 9, fp );

Пример

#include
main()
{
const int N = 10;
int i, A[N], n;
FILE *fp;
// чтение данных и файла input.dat
for ( i = 0; i < n; i ++ )
A[i] = A[i] * 2;
// запись данных в файл output.dat
}

Работа с файлами

fp = fopen( "input.dat", "rb" );
if ( fp == NULL ) {
printf("Файл открыть не удалось.");
return;
}
n = fread ( A, sizeof(int), N, fp );
if ( n < N ) printf("Не хватает данных в файле");
fclose ( fp );

Чтение данных:

fp = fopen( "output.dat", "wb" );
fwrite ( A, sizeof(int), n, fp );
fclose ( fp );

Запись данных:

Задания