Определение и объявление функций пользователя. Лекция 10 по алгоритмизации и программированию презентация

Лекция 10

Определение(описание) и объявление функций пользователя Определение(описание) и объявление функций пользователя I. Описание функции: заголовок; тело функции. <Описание функции>::=<Заголовок функции> {<Тело функции>} <Заголовок функции>::= <Тип результата> <Имя функции> (<Описание параметров>) <Тип результата>::=void | <Базовые типы> |  <Структурированные типы> <Имя функции>::=<Идентификатор> <Список параметров>::=<Тип> <Имя> [, <Список параметров>] | ПУСТО Если тип результата отличен от void, то в теле функции обязательно должен присутствовать оператор return <значение>; , где <значение> – имя переменной, выражение или константа. Оператор return передает управление вызывающей программе. <Объявление функции>::=<Заголовок функции>;

Какая задача реализована в этом фрагменте? Какая задача реализована в этом фрагменте? Фрагмент программы: int a[100]; int j,i,n,r; for (i=1;i<n;i++) { r=a[i];j=i-1; while(j>=0&&r<=a[j]) {a[j+1]=a[j];j--;} a[j+1]=r; }

Сортировка двоичными (бинарными) вставками Модификация метода вставок. Пусть элементы массива с А[1] по А[i-1] уже отсортированы. Нужно вставлять в отсортированную последовательность элемент А[i]. Для поиска места, куда нужно вставлять данный элемент сравниваем его со средним элементом из A[1] …A[i-1], и , если он меньше среднего элемента, то его место ищем в левой половине массива А[1]…A[i-1], иначе в правой половине. Причем дальнейший поиск осуществляем аналогичным способом: методом деления интервала пополам.

void sort_bin_insert (int *a, int n) // Сортировка бинарными вставками void sort_bin_insert (int *a, int n) // Сортировка бинарными вставками { int x,left,right,sred; for (int i=1; i<n; i++) { if (a[i-1]>a[i]) { x=a[i]; // x – включаемый элемент left=0; // левая граница отсортированной части массива right=i-1; // правая граница отсортированной части массива do { sred = (left+right)/2; // sred – новая "середина" последовательности if (a[sred]<x ) left= sred+1; else right=sred-1; } while (left<=right); // поиск ведется до тех пор, пока левая граница не окажется правее правой границы for (int j=i-1; j>=left; j--) a[j+1]= a[j]; a[left]= x; } } }

Алгоритм слияния Объединить («слить») упорядоченные фрагменты массива A: A[k],...A[m] и A[m+1],..., A[q] в один A[k],..., A[q], естественно, тоже упорядоченный (kmq). Основная идея решения состоит в сравнении очередных элементов каждого фрагмента, выяснении, какой из элементов меньше, переносе его во вспомогательный массив D (для простоты) и продвижении по тому фрагменту массива, из которого взят элемент. При этом следует не забыть записать в D оставшуюся часть того фрагмента, который не успел себя «исчерпать».

#include <iostream> #include <iostream> #include <locale.h> using namespace std; void Sl(int m[],int k,int q) // или ...int *a { // k – нижняя граница упорядоченного фрагмента // q – верхняя граница фрагмента int i,j,t,mid,d[20]; i=k; mid=k+(q-k)/2; j=mid+1; t=1; while (i<=mid && j<=q) { if (m[i]<=m[j]) {d[t]=m[i]; i++;} else { d[t]=m[j]; j++;} t++; } // Один из фрагментов обработан полностью, осталось перенести в D остаток другого фрагмента while (i<=mid) { d[t]=m[i]; i++; t++;} while (j<=q) { d[t]=m[j]; j++; t++;} for (i=1;i<=t-1; i++) m[k+i-1]=d[i]; }

// Рекурсивная реализация сортировки слиянием // Рекурсивная реализация сортировки слиянием void Sort_Sl(int *m, int i,int j) { int t; if (i<j) // Обрабатываемый фрагмент массива состоит более, чем из одного элемента if (j-i==1) { if (m[j]<m[i]) // Обрабатываемый фрагмент массива состоит из двух элементов*) { t=m[i]; m[i]=m[j]; m[j]=t;};} else { // Разбиваем заданный фрагмент на два Sort_Sl(m,i,i+(j-i)/2); // рекурсивные вызовы процедуры Sort_Sl Sort_Sl(m,i+(j-i)/2+1,j); Sl(m,i,j); } }

Двумерные массивы Двумерный массив (матрица) – одномерный массив одномерных массивов. <тип элементов> <имя массива>[количество][количество]; Указывается количество элементов в одномерном массиве, а потом указывается количество элементов в одномерных массивах.

Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца.

Схема выделения памяти под двумерный массив int A[20][5]; Элементами первого одномерного массива являются адреса, а второго – целые значения.

При формирование матрицы сначала выделяется память для массива указателей на одномерные массивы, а затем в цикле с параметром выделяется память под n одномерных массивов. При формирование матрицы сначала выделяется память для массива указателей на одномерные массивы, а затем в цикле с параметром выделяется память под n одномерных массивов. /*выделение динамической памяти под двумерный динамический массив*/ int** form_matr(int n,int m) { //выделение памяти под массив указателей int **matr=new int*[n]; for(int i=0;i<n;i++) //выделение памяти для массива значений matr[i]=new int [m]; //возвращаем указатель на массив указателей return matr; }

Освобождение памяти из-под динамического двумерного массива производится в обратном порядке: for(int i=0;i<n;i++) delete [] matr[i]; delete [] matr;

Если двумерный массив является формальным параметром функции, то его можно описывать двумя способами: Если двумерный массив является формальным параметром функции, то его можно описывать двумя способами: int **A // ** – указатель, значением которого будет адрес int A[ ][<максимальное количество>] Например, int A[ ][5]

Обращение к элементам двумерного массива A[i][j] *(*(A+i)+j)

Если при описании двумерного массива задаются значения элементов, то можно не указывать только количество строк: Если при описании двумерного массива задаются значения элементов, то можно не указывать только количество строк: int b[ ][5]={{1,2,3,,4}, {5,6,7,8,9}, {10,11,12}};

// Заполнение массива по строкам // Заполнение массива по строкам for ( i = 0; i < N; i++ ) for ( j = 0; j < M; j++ ) {cout << “A[“<<i<<“][“<<j<<“]=“; cin >>b[i][j]; }

// Печать по строкам // Печать по строкам for ( i = 0; i < N; i++ ) { for ( j = 0; j < M; j++ ) cout << b[i][j]<<“ “; cout <<endl; } // Печать по столбцам for ( j = 0; j < M; j++ ) { for ( i = 0; i < N; i++ ) cout << b[i][j]<<“ “; cout <<endl; }

// Суммирование // Суммирование sum = 0; for ( i = 0; i < N; i++ ) for ( j = 0; j < M; j++ ) sum += A[i][j];

Матрица А: Матрица А: 12 14 67 45 32 87 45 63 69 45 14 11 40 12 35 15 Максимальный элемент A[2,2]=87 Минимальный элемент A[3,4]=11

#include <iostream> #include <iostream> #include<cstdlib> using namespace std; void main() { int const N=10; int const M=15; int a[N][M]; int i,j, max,k=0; max=a[0][0]; for(i=0; i<N; i++) for(j=0; j<M; j++) { cout<<"? "; cin>>a[i][j]; } max=a[0][0]; k=1; for(i=0; i<N; i++) for(j=0; j<M; j++) if(a[i][j]==max) k++; else if(a[i][j]>max) {max=a[i][j]; k=1;} cout<<"k="<<k<<endl; }

Если количество строк и столбцов в двумерном массиве одинаковое, то такой массив называется квадратным. Например, при n=4: Если количество строк и столбцов в двумерном массиве одинаковое, то такой массив называется квадратным. Например, при n=4: a00  a01  a02  a03 a10  a11  a12  a13 a20  a21  a22  a23 a30  a31  a32  a33 Диагонали: i=j – главная диагональ.Элементы: a[i][i], a[j][j]; i+j=n–1 – побочная диагональ. Элементы: a[i][n-1-i], a[n-1-j][j].

Перебор элементов матрицы

#include <iostream> #include <iostream> #include<cstdlib> using namespace std; void main() { int const N=10; int a[N][N]; int i,j, k; for(i=0; i<N; i++) for(j=0; j<N; j++) { cout<<"? "; cin>>a[i][j]; } for(i=0; i<N; i++) for(j=0; j<i; j++) {k=a[i][j]; a[i][j]=a[j][i]; a[j][i]=k;} for(i=0; i<N; i++) {for(j=0; j<N; j++) cout<<a[i][j]<<“ “; cout<<endl; } }