Урок 7.2.5. Приёмы обработки массива

7.2.5. Приёмы обработки массива

Рассмотрим приемы обработки массивов на примерах программ сортировки числовых и текстовых (строковых) данных методом пузырька. Это один из простейших методов сортировки, название которого происходит из того факта, что б?льшие (меньшие) по значению элементы массива как бы всплывают вверх по массиву, подобно пузырькам газа в воде. Суть алгоритма заключается в следующем: начиная с первого, сравнивается каждая пара соседних элементов массива. Если предыдущий элемент больше последующего и массив упорядочивается по возрастанию значений, то они меняются местами. Таким образом, при первом попарном просмотре элементов массива и возможных при этом перестановках, самый большой элемент попадает на последнее место в массиве. При следующем просмотре массива этот элемент не участвует в сравнении, так как он уже находится на своем месте. При каждом последующем просмотре больший из оставшихся элементов "всплывает", занимая свое место в массиве. На последнем просмотре остается сравнить только первые два элемента в массиве и, если необходимо, поменять их местами.

Пример 1. Упорядочивание числового массива по возрастанию значений элементов:

#include <stdio.h>
#define razmer 12
main() {
int s,p,i;
int massiv[razmer]={11,10,9,8,7,6,5,4,3,2,1,0};
for (p=razmer; p>=2; p--)
   fоr (i=0; i<p-1; i++)
      if ( massiv[i] > massiv[i+1])  // Доступ к элементам */
           { s=massiv[i+1];             // через переменную */
             massiv[i+1]=massiv[i];     // с индексом. */
             massiv[i]=s;
           };
 
for(i=0; i<razmer; i++)        // Печать отсортированного массива */
      printf("%d ",*(massiv+i));  // Доступ через имя массива. */
}
 
//Результат работы программы:
 
0 1 2 3 4 5 6 7 8 9 10 11

Комментарий к программе. Оператор #define razmer 12 является директивой препроцессора и означает, что везде в программе текст razmer будет заменен на 12. Это делается для повышения наглядности программы и удобства ее модификации. В программе объявлены три переменные: i – для индексации массива, p – определяет количество просмотров массива, s – промежуточная переменная для обмена значениями элементов массива. Объявлен и инициирован массив massiv размерностью razmer. Первый цикл for с параметром цикла р определяет число проходов, необходимых для сортировки массива. Второй цикл for с параметром цикла i организует сравнение и перестановку элементов массива. Обратите внимание, что при каждом новом проходе, который стартуется первым циклом с переменной р, уменьшенной на единицу (р--), будет просматриваться на 1 элемент меньше, чем в предыдущем проходе. Последний цикл содержит в своем теле оператор printf, выводящий элементы массива на печать. Условие цикла i<razmer предписывает вывести на печать элементы массива, имеющие индексы от 0 до 11, т.е. весь массив. Воспользовавшись правилами адресной арифметики и тем, что имя массива является константой типа указатель, мы организовали вывод массива на печать не при помощи индексации, а при помощи изменения указателя на элементы массива и операции косвенной адресации.

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

Пример 2. Упорядочивание строк по алфавиту:

#include <stdio.h>
#define razmer 11
main()
{
int p,i;
char *s;
 
// Инициализация массива указателей на строки 
char *str[razmer]={
"Чехов А. Ионыч",
"Толстой Л. Детство",
"Достоевский Ф. Братья Карамазовы",
"Толстой Л. Война и мир",
"Пушкин А. Метель",
"Куприн А. Яма",
"Тургенев И. Вешние воды",
"Островский А. Гроза",
"Бунин И. Темные аллеи",
"Гоголь Н. Ревизор",
"Набоков В. Лолита"
};
 
/* Упорядочивание указателей */
for (p=razmer; p>=2; p--)
   for (i=0; i<p-1; i++)
      if (*str[i] > *str[i+1])
         {
           s=str[i+1];
           str[i+1]=str[i];
           str[i]=s;
         };
 
// Вывод на печать строк, упорядоченных по алфавиту 
for (i=0; i<=razmer; i++)
  printf("%s \n ",str[i]);
}
 
//Результат работы программы:
 
Бунин И. Темные аллеи
Гоголь Н. Ревизор
Достоевский Ф. Братья Карамазовы
Куприн А. Яма
Набоков В. Лолита
Островский А. Гроза
Пушкин А. Метель
Толстой Л. Детство
Толстой Л. Война и мир
Тургенев И. Вешние воды
Чехов А. Ионыч.

При сортировке учитывается, что коды заглавных букв русского алфавита расположены в возрастающей последовательности в соответствии с алфавитом, т.е. справедливо, что 'A'<'Б', 'Б'<'В' и т.д. Алгоритм аналогичен предыдущему, но обратите внимание, что перемещаются не сами строки, а лишь указатели на эти строки. Такой прием повышает эффективность программы, так как нет необходимости перезаписывать строки, достаточно лишь обменять значения указателей. Для того, чтобы иметь возможность обменять значения указателей, описана промежуточная переменная s типа указатель. Выражение *str[i] предписывает извлечь символ, на который ссылается указатель, т.е. первый символ i-ой строки. Заметим, что если бы массив был описан так:

char str[razmer][32]={
"Чехов А. Ионыч",
"Толстой Л. Детство",
"Достоевский Ф. Братья Карамазовы",
"Толстой Л. Война и мир",
"Пушкин А. Метель",
"Куприн А. Яма",
"Тургенев И. Вешние воды",
"Островский А. Гроза",
"Бунин И. Темные аллеи",
"Гоголь Н. Ревизор",
"Набоков В. Лолита"
};

то необходимо было бы объявить промежуточный массив на 32 символа, чтобы осуществить действительную перестановку строк, производя при этом посимвольную перезапись каждой строки.

рассказать друзьям и получить подарок

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля отмечены *

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Translate Переводчик

Подписка на новости

SmartResponder.ru
Ваш e-mail: *
Ваше имя: *

Хостинг для Wordpress сайтов