Тело
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]);
Очевидно, если ввести с экрана любой другой вектор, то алгоритм будет работать и для него.
- Пузырьковая сортировка.
Рассмотрим вектор 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 5 10 -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
Ввод и вывод матрицы осуществляется так:
- Инициализация.
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 };
- Ввод.
for (i=0; i<3; i++)
for (j=0; j<4; j++)
scanf(“%d”, &matr[i][j]);
- Вывод.
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;
} }
Для чего нужны подпрограммы? Они реализуют два важнейших принципа программирования: