Модульность


Тело

12 11 10 8 6 5 4 4 0 -3

12 11 10 8 6 5 4 4 0-3

Рассмотрим программу, реализующую данный алгоритм.

int vec[10]={ 11, 4, -3, 5, 10, 8, 12, 6, 4, 0 } ;

int i, j, max, nmax ;

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

{

max=vec[i] ;

nmax=i ;

for ( j=i ; j<10 ; i++)

if ( max< vec[j]) {

max=vec[j] ;

nmax=j ;

}

vec[nmax]=vec[i] ;

vec[i]=max ;

}

for ( i=0 ; i<10 ; i++) printf(“%d “, vec[i]) ;

Очевидно, если ввести с экрана любой другой вектор, то алгоритм будет работать и для него.

 

  1. Пузырьковая сортировка.

Рассмотрим вектор 11 4 -3 5 10 8 12 6 4 0 отсортируем его значения по убыванию.

Рассмотрим пару соседних элементов, 11 4, если предыдущий меньше последующего, то переставим их местами, в противном случае оставим все без изменения и перейдем к соседней паре 4 -3. Продолжая таким образом двигаться по вектору, к концу первого прохода «всплывет» самый маленький элемент.

11 4 5 -3 10 8 12 6 4 0

11 4 510 -3 8 12 6 4 0

11 4 510 8 -3 12 6 4 0

11 4 510 8 12 -3 6 4 0

11 4 510 8 12 6 -3 4 0

11 4 510 8 12 6 4 -3 0

11 4 510 8 12 6 4 0 -3

Далее алгоритм повторяется с первого до предпоследнего элемента, «всплывает» следующий самый маленький.

11 5 10 8 12 6 4 4 0 -3

Теперь два последних элемента стоят на своих местах, повторяем процесс, не доходя два элемента до конца и т. д. пока не останется на первом месте самый большой элемент.

11 5 10 8 12 6 4 4 0 -3

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

 

3. Сортировка вставкой.

Рассмотрим вектор 11 4 -3 5 10 8 12 6 4 0 отсортируем его значения по убыванию.

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

11 4 -3 5 10 8 12 6 4 0 оставляем на месте, теперь рассмотрим упорядоченный вектор из двух

11 4 -3 5 10 8 12 6 4 0 элементов, найдем в нем место третьего. Опять остается на месте.

11 5 4-3 10 8 12 6 4 0 А вот - 5 нужно вставить между 11 и 4, после чего вектор из четырех

элементов будет упорядочен. Дальше ищем место - 10 и т. д. пока

12 11 10 8 6 5 4 4 0 -3весь вектор не станет упорядоченным.

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

 

 

МАТРИЦЫ.

 

Оператор описания целочисленной матрицы, состоящей из 3-х строк и 4-х столбцов:

int matr[3][4] ;

Например такая матрица:

1 2 3 4 элементы матрицы задаются так: matr[0][0] - 1

5 6 7 8 matr[0][1] - 2

9 10 11 12 matr[1][0] - 5

matr[2][3] - 12

Номера строки и столбца отсчитываются от 0, поэтому последний элемент в матрице размерностью 3 на 4 - matr[2][3]. В памяти элементы матрицы располагаются линейно по строкам.

Имя матрицы определяет адрес элемента matr[0][0].

matr одно и тоже &matr[0][0] одно и тоже matr[0]

matr[1] одно и тоже &matr[1][0] одно и тоже matr+4

*(matr +6) одно и тоже *(matr[1]+2) одно и тоже matr[1][2] одно и тоже 7

 

Ввод и вывод матрицы осуществляется так:

 

  1. Инициализация.

int matr[3][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} } ;

int matr[3][4] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 } ;

 

  1. Ввод.

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

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

scanf(“%d”, &matr[i][j]) ;

 

 

  1. Вывод.

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

{

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

printf(“%d ”, matr[i][j]) ;

printf(“\n”) ;

}

Рассмотрим задачу: найти в матрице максимальный элемент.

{

int matr[5][5], i, j, max ;

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

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

scanf(“%d”, &matr[i][j]) ;

max=matr[0][0] ;

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

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

if ( max<matr[i][j]) max=matr[i][j] ;

printf(“%d”, max) ;

}

Примечание: подумать, что нужно сделать, чтобы вывести не только значение max, но и его «адрес» - индексы.

Еще одна интересная задача – транспонирование матрицы.

Математически это означает переворачивание матрицы на бок, замена строк столбцами.

Исходная транспонированная

3 7 3 5 8 3 2 1 1

2 5 6 7 9 7 5 4 2

1 4 4 5 8 3 6 4 3

1 2 3 4 5 5 7 5 4

8 9 8 5

Для квадратной матрицы транспонирование – это перестановка местами элементов с симметричными индексами, т.е. matr[i][j] переставляется с matr[j]i], а элементы главной диагонали остаются на месте.

Рассмотрим программу реализующую данный алгоритм.

#include<stdio.h>

#include<conio.h>

main()

{

int matr[5][5], i, j, k ;

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

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

scanf(“%d”, &matr[i][j]) ;

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

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

{

k=matr[i][j] ;

matr[i]j]=matr[j][i] ;

matr[j]i]=k ;

}

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

{ for ( j=0 ; j<5 ; j++)

printf(“%d ”, matr[i][j]) ;

printf(“\n”) ;

}

}

 

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

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

#include<stdio.h>

#include<conio.h>

main()

{

int matr[10][10], i, j, k ;

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

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

scanf(“%d”, &matr[i][j]) ;

for (k=0 ; k<10 ; k++) // перебор строк

for ( i=0 ; i<8 ; i++) // пузырьковая сортировка каждой строки матрицы по убыванию

for ( j=0 ; j<9-i; j++)

{

if( matr[k][j]<matr[k][j+1] ) {

x=matr[k][j] ;

matr[k][j]=matr[k][j+1] ;

matr[k][j+1]=x ;

}

}

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

{ for ( j=0 ; j<10 ; j++)

printf(“%d ”, matr[i][j]) ;

printf(“\n”) ;

}

}

Попробуйте выполнить следующие задачи:

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

2. Проверить является ли вектор нулевым, т.е. состоит из одних нулевых элементов.

Идея решения – сосчитать количество нулевых элементов в векторе, если это количество равно размеру вектора, то он нулевой.

 

СТРОКИ.

 

Строкой – называется текстовый вектор, для которого не обязательно указывать размерность с признаком конца ‘\0’.

Описание строки.

char a[] ;

Описание и инициализация строки. Будет создана строка из 20 символов, 19 значащих и ‘\0’.

char a[]=”произвольная строка “ ;

Если бы мы создавали текстовый вектор, то аналогичное действие выглядело бы так:

Char a[19]={‘п’,’р’,’о’,’и’,’з’,’в’,’о’,’л’,’ь’,’н’,’а’,’я’,’ ’,’с’,’т’,’р’,’о’,’к’,’а’ } ;

Чтобы из него сделать строку нужно в конец добавить ‘\0’.

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

char a[] ;

scanf (“%s”, a) ; // введутся все символы до первого пробела в конце добавится ‘\0’.

printf (“%s”, a) ; // выведутся все символы до первого пробела.

char a[81] ;

gets (a) ; // введутся любые символы до нажатия “enter” в конце добавится ‘\0’.

puts (a); ; // выведутся все символы содержащиеся в строке до ‘\0’.

Имя строки а – адрес нулевого элемента, i-й элемент можно достать так:

*(a+i) одно и то же a[i].

Длину произвольной текстовой строки – h можно определить так:

For ( h=0 ; *(a+h)!=’\0’ ; h++) ;

Это же реализует стандартная функция из библиотеки #include<string.h>

h=strlen(a) ;

Можно описать массив из строк и ввести его:

char text[10][81] ;

for ( i=0 ; i<=9 ; i++) gets( text[i]) ;

 

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

Посчитать число вхождений каждого различного символа в строке.

#include<stdio.h>

#include<string.h>

main()

{

int h, sh, i, j ;

char text[]=”произвольная фраза “, ch ;

h=strlen(text) ;

for ( i=0 ; i<h ; i++) // цикл по количеству символов в строке

{

ch=text[i] ; // ch – символ для поиска копий

if(ch!=’-‘) { for (j=i+1, sh=1 ; j<=h ; j++ ) // цикл поиска повторов, sh – количество копий,

if ( ch==text[j] ) { sh++ ; text[j]=’-‘ ; } // вычеркивание копий

printf ( “\n%c %d”, ch, sh ) ;

text[i]=’-‘ ;

}

}

}

Найти в строке слово максимальной длинны:

#include<stdio.h>

#include<string.h>

main()

{

int h, ss=0, i=0, j=0, maxlen=0 ; // maxlen –текущая максимальная длина строки

char text[81], word[10]=’\0’;

gets(text) ;

h=strlen(text) ;

 

while ( i<=h ) // перебираем все символы строки

{

if ( (*(text+i)==’ ‘)||(i==h) // если обнаружен пробел, т.е. конец слова или конец строки

if ( maxlen<(i-ss)) // если maxlen меньше длины текущего слова,

{

maxlen=i-ss ; // то запоминаем новую длину

for ( j=0 ; j<maxlen ; j++ ) *(word+j)=*(text+ss+j) ; // запоминаем слово

ss=i ; // конец предыдущего слова

}

i++ ;

}

puts (word) ;

}

 

ПОДПРОГРАММЫ.

 

 

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

Все программы на С состоят из подпрограмм, с главной подпрограммой - main() мы уже встречались. Она выглядит так:

 

 

main()

{

операторы реализующие алгоритм.

}

 

Первая строка – заголовок функции далее в{} ее тело.

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

Иначе заголовок главной функции можно записать так:

void main( void )

void – означает отсутствие, в первом случае результата функции во втором параметров. При отсутствии перед именем функции в ее заголовке типа результата берется по умолчанию int.

main()

Поэтому при таком оформлении функции транслятор требует оператор - return 1 ;

 

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

 

тип результата ИМЯ( тип параметр1,тип параметр2,…тип параметрК)

{формальные параметры

return результат ;

}

 

Если нет результата, а есть эффект, то в теле функции нет оператора return.

 

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

ИМЯ( параметр1, параметр2,… параметрК)

фактические параметры

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

scanf (“%d”, &a) ; // вызов функции самостоятельный оператор, у нее нет результата.

h=strlen(text) ; // результат выполнения функции присваивается переменной.

printf (“%d”, strlen(text)) ; // два вызова разных функций, один внутри другого.

 

Выполняется правило - формальные и фактические параметры соответствуют друг другу по количеству, типу и порядку следования.

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

 

#include< > #include< >

int func( int a) // подпрограмма int func( int ) ; // декларация

{ main() // главная программа

int b ; {

… int k, s ;

return b ; …

} k=func(s) ;

main() // главная программа }

{ int func( int a) // подпрограмма

int k, s ; {

… int b ;

k=func(s) ; …

… return b ;

} }

 

Для чего нужны подпрограммы? Они реализуют два важнейших принципа программирования: