КаталогИндекс раздела
НазадОглавлениеВперед


Лабораторная работа ╧13

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

1. Цель работы

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

2. Темы для предварительной проработки

3. Задания для выполнения

    Составить программу, которая решает задачу для лабораторной работы ╧9 с такими дополнительными условиями:

4. Варианты индивидуальных заданий

 1        2        3        4        5        6        7        8        9       10      
11       12       13       14       15       16       17       18       19       20      
21       22       23       24       25       26       27       28       29       30      

5. Пример решения задачи (вариант 30)

    Решение приводится со ссылками на работу ╧9.

5.1. Разработка алгоритма решения.

    Сам алгоритм решения мог бы быть тем же, что и в работе ╧9. Но обратим внимание на то, что условие этой работы несколько отлично от условия работы ╧9. Если в работе ╧9 мы имели фиксированную размерность матрицы, то тут у нас размерность матрицы заранее не известна. Составляет ли это существенное различие? Да. Если мы проверим функционирования алгоритма работы ╧9 при разных значениях размерности (S), то мы убедимся, что корректно он срабатывает только при нечетных значениях S. При четных значениях верхняя половина матрицы формируется правильно, а в нижней половине область ненулевых значений будет захватывать также и сами диагонали, что не соответствует условиям задания. Поэтому для этой работы следует пересмотреть алгоритм.

    Для элемента, который лежит на главной диагонали, индексы удовлетворяют условию: L=R, на побочной - R=S-L-1. Следовательно, для верхней половины условие попадания в ненулевую область: L < R < S-L-1, а для нижней: S-L-1 < R < L. Или, обобщая: min(L,S-L-1) < R < max(L,S-L-1) . В схеме алгоритма, которая приведена на рисунке 1, мы используем именно это условие. К тому же в схеме отражено разделение программы на две функции: главную функцию - main(), которая выполняет выделения памяти для матрицы, вызов функции заполнения матрицы и вывод результата, и функцию fill(), которая выполняет заполнение матрицы по заданным правилам.

Рисунок 1. Схема алгоритма

    В этой работе ми несколько усложним алгоритм, добавив в него проверку значения S, которое введено оператором (блоки 3 - 8). Нижняя граница для значения S - 1, поскольку матрица нулевой или отрицательной размерности просто не имеет смысла. Верхняя граница - 24, поскольку для матрицы большего размера невозможно будет обеспечить наглядный вывод (она не поместится на экране).

5.2. Представление матрицы в памяти

    Если в работе ╧9 было возможно представлять матрицу в программе как двумерный массив - естественное представление матрицы, то при условии динамического размещения в памяти ее представление уже не такое простое. Возможны три варианта размещения в памяти и представления матрицы в программе. Во всех трех вариантах очевидно, что общий объем памяти для размещения данных матрицы должен быть S2 элементов типа int.

    Вариант 1 показан на рис.2

Рисунок 2. Размещение в памяти. Вариант 1.

    Для данных матрицы выделяется необходимый объем памяти. В программе объявляется указатель на начало этой области. Тип этого указателя - int*. Таким образом, матрица является одномерным массивом и для того, чтобы по номеру строки (L) и столбца (R) определить индекс в одномерном массиве (N) следует выполнить вычисление: N=L*S+R.

    Вариант 2 показан на рис.3.

Рисунок 3. Размещение в памяти. Вариант 2.

    Память для данных матрицы выделяется так же, как и в предыдущем случае. Но дополнительно выделяется память для одномерного массива размерности S, элементы которого имеют тип int* (указатель на целое). Указатель на начало этого массива имеет тип int** (указатель на указатель на целое). В элементы этого массива записываются указатели на начала соответствующих строк в массиве данных матрицы. В этом варианте можно обращаться к данным матрицы, указывая номера строки и столбца как два индекса в массиве указателей.

    Вариант 3 показан на рис.4.

Рисунок 4. Размещение в памяти. Вариант 3

    Этот вариант отличается от предыдущего тем, что для каждой строки матрицы память выделяется отдельно (S областей памяти по S элементов в каждой), и в массив указателей заносятся указатели на соответствующие области. Таким образом, матрица необязательно занимает смежные области памяти. Можно обращаться к данным матрицы, указывая два индекса. Выделение памяти (и соответственно - освобождение) нужно выполнять в цикле. Вариант 1 обеспечивает экономию памяти, а варианты 2 и 3 - возможность "естественного" обращения к элементам матрицы. Вариант 3 позволяет рациональнее использовать память, чем вариант 2, но вариант 2 алгоритмически более простой. Мы покажем реализации алгоритма для вариантов 1 и 3.

5.3. Определение переменных программы (вариант 1)

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

    Переменные для функции main().

    Указатель на начало линейного массива, в котором размещаются данные матрицы:

    int *Ar;

    Размерность массива:

    int S;

    Общее количество элементов массива (его использование будет видно из текста программы):

    int size;

    Указатель на текущий элемент массива при его выводе:

    int *Cr;

    Счетчик выведенных элементов:

    int i;

    Параметры для функции fill().

    Указатель на начало линейного массива, в котором размещаются данные матрицы:

    int *A;

    Размерность массива:

    int s;

    Переменные для функции fill().

    Указатель на текущий элемент массива при его обработке:

    int *C;

    Номера строки и столбца:

    short l, r;

    Текущий член линейной последовательности:

    int k=1;

5.4. Разработка текста программы (вариант 1)

    Текст программы начинаем с включения файлов: stdio.h, alloc.h, stdlib.h (в последнем определены макросы max и min).

    Включаем описание функции fill() и открываем главную функцию. В главной функции объявляем ее локальные переменные, выводим приглашение и вводим значение размерности матрицы S. Размерность сравнивается с нижней и с верхней границей и, если она выходит за границы, выводится соответствующее сообщение и программа завершается (функцией exit()). Если S удовлетворяет установленным условиям, его значение выводится на экран.

    Потом выделяется память для размещения матрицы. Для этого вызывается функция malloc(). Ей передается размер памяти в байтах, который нужен для размещения S2 элементов типа int. Функция malloc() возвращает указатель на выделенную область памяти, значение этого указателя записывается в переменную Ar - это будет указатель на начало массива, в котором разместятся данные матрицы. Если значение, которое вернула функция malloc(), - пустой указатель, это признак того, что памяти не хватает, в этом случае видается сообщение и программа завершается.

    Оператор:

    fill(Ar,S);
- обращение к функции заполнения матрицы. Функции передаются: указатель на начало массива и размерность матрицы.

    После возврата управления из функции fill() уже готовая матрица выводится на экран. При выводе матрица рассматривается как линейный массив из S2 элементов. Счетчик i меняется от 0 до S2-1. Но обращение к элементам матрицы в этом цикле ведется через указатель Cr. В начальных установках этот указатель устанавливается на начало массива, а после каждой итерации увеличивается на 1, т.е. сдвигается на следующий элемент массива. Счетчик i используется для определения момента выхода из цикла, а также для перехода на новую строку экрана после вывода каждых S элементов - для этого проверяется условие: i%S==S-1.

    Последним действием в функции main() является освобождение с помощью функции free() выделенной ранее памяти.

    Функция fill() получает параметры - указатель на начало массива и размерность матрицы. Тело функции начинается с объявления ее локальных переменных, переменная k получает начальное значение при объявлении.

    Далее в функции организуются вложенные циклы для перебора строк и столбцов. Но номера строки и столбца используются не для обращения к элементам матрицы, а только для проверки, попадает ли элемент в нулевую или ненулевую область (в точном соответствии условиям, приведенным в п.5.2). Обращение к элементам матрицы ведется через указатель C, который указывает на текущий элемент матрицы. Этот указатель устанавливается на начало массива в начальных установках внешнего цикла и увеличивается на 1 в конце каждой итерации внутреннего цикла.

    Полный текст программы приведен ниже.

/***************************************************/
/*              Лабораторная работа ╧13            */
/*                      Функции                    */
/*          Пример выполнения. Вариант ╧30.        */
/*                Вариант реализации 1             */
/***************************************************/
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
void fill(int *, int);

/*** главная функция ***/
main() {
 int *Ar, /* указатель на начало массива */
     *Cr; /* текущий указатель у массиве */
 int i,   /* счетчик элементов */
     S;   /* размерность матрицы */

  /* ввод размерности */
  printf("Введите размерность матрицы >");
  scanf("%d",&S);
  /* проверка размерности */
  if (S<=0) {
    printf("Размерность слишком мала\n");
    exit(0);
    }
  if (S>24) {
    printf("Размерность слишком велика\n");
    exit(0);
    }
  printf("S=%d\n",S);
  /* выделение памяти */
  if ((Ar=(int *)malloc(sizeof(int)*S*S))==NULL) {
    printf("Недостаток памяти\n");
    exit(0);
    }
  /* обращение к функции заполнения матрицы */
  fill(Ar,S);
  /* вывод матрицы */
  for (Cr=Ar, i=0; i<S*S; Cr++,i++) {
      printf("%3d",*Cr);
      if (i%S==S-1) putchar('\n');
      }
  /* освобождение памяти */

  free(Ar);
  return 0;
}
/*** функция заполнения матрицы ***/
/* параметры: A - указатель на начало массива
              s - размерность матрицы */
void fill(int *A, int s) {
 int *C;      /* текущий указатель в массиве */
 short l, r;  /* строка и столбец */
 int k=1;     /* текущий член ЛП */
  for (l=0,C=A; l<s; l++)     /* перебор строк */
    for (r=0; r<s; r++, C++)  /* перебор столбцов */
      /* условие нулевого значения */
      if ((r>=max(l,s-l-1))||(r<=min(l,s-l-1))) *C=0;
      else *C=k++;
      /* конец перебора строк */
    /* конец перебора столбцов */
}

5.5. Отличия для варианта реализации 3

    В тексте программы для варианта реализации 3 мы для упрощения исключили все проверки корректности. Описание реализации мы ограничиваем только отличиями от варианта 1.

    Указатель Ar в функции main() тут - указатель на массив указателей, следовательно, его тип - int**. Выделение памяти ведется в несколько приемов: сначала выделяется память для массива из S указателей, а потом в цикле - S раз выделяется память для массива из S целых чисел, адреса выделенных массивов записываются в элементы массива указателей. При выводе матрицы используются i и j - номера строки и столбца и обращение к элементам матрицы ведется как к элементам 2-мерного массива.

    Первый параметр функции fill() - указатель на указатель на int. Это дает возможность использовать номера строки и столбца - l и r также и для обращения к элементам матрицы.

/***************************************************/
/*              Лабораторная работа ╧13            */
/*                      Функции                    */
/*          Пример выполнения. Вариант ╧30.        */
/*                Вариант реализации 2             */
/***************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
void fill(int far **, int);

/*** главная функция ***/
main() {
 int far **Ar; /* указатель на массив указателей */
 int i, j; /* строка и столбец */
 int S;    /* размерность матрицы */
  /* ввод размерности */
  printf("Enter S>"); scanf("%d",&S); 
  printf("S=%d\n",S);
  /* выделение памяти для массива указателей */
  Ar=(int far **)malloc(sizeof(int *)*S);
  /* выделение памяти для каждой строки 
     и заполнение массива указателей */
  for (i=0; i<S; i++) 
    Ar[i]=(int far *)malloc(sizeof(int)*S);

  /* обращение к функции заполнения матрицы */
  fill(Ar,S);
  /* вывод матрицы */
  for (i=0; i<S; i++) {
    for (j=0; j<S; printf("%3d",Ar[i][j++]) );
    putchar('\n');
    }
  /* освобождение памяти строк */
  for ( i=0; i<S; free(Ar[i++]) );
  /* освобождение памяти массива указателей */
  free(Ar);
  return 0;
}
/*** функция заполнения матрицы ***/
/* параметры: A - указатель на массив указателей
              s - размерность матрицы */
void fill(int far **A, int s) {
 short l, r; /* строка и столбец */
 short k=1;  /* текущий член ЛП */
  for (l=0; l<s; l++)    /* перебор строк */
    for (r=0; r<s; r++)  /* перебор столбцов */
      /* условие нулевого значения */
      if ((r>=max(l,s-l-1))||(r<=min(l,s-l-1))) 
        A[l][r]=0;
      else A[l][r]=k++;
      /* конец перебору строк */
    /* конец перебору столбцов */
}

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

    При отладке программы срабатывают те же соображения, которые высказаны к работе ╧9: рекомендуется вести поиск ошибок на основе анализа выведенных программой данных, но при желании можно использовать и пошаговый режим.

5.5. Результаты работы программы

    Ниже приведены два примера результатов работы программы: для четного и нечетного значений размерности.

S=10
  0  1  2  3  4  5  6  7  8  0
  0  0  9 10 11 12 13 14  0  0
  0  0  0 15 16 17 18  0  0  0
  0  0  0  0 19 20  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0
  0  0  0  0 21 22  0  0  0  0
  0  0  0 23 24 25 26  0  0  0
  0  0 27 28 29 30 31 32  0  0
  0 33 34 35 36 37 38 39 40  0

S=9
  0  1  2  3  4  5  6  7  0
  0  0  8  9 10 11 12  0  0
  0  0  0 13 14 15  0  0  0
  0  0  0  0 16  0  0  0  0
  0  0  0  0  0  0  0  0  0
  0  0  0  0 17  0  0  0  0
  0  0  0 18 19 20  0  0  0
  0  0 21 22 23 24 25  0  0
  0 26 27 28 29 30 31 32  0

5.6. Выводы

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


КаталогИндекс раздела
НазадОглавлениеВперед