Алгоритмы устойчивой сортировки

• Сортировка выбором.
• Сортировка пузырьком.
• Сортировка вставками.
• Сортировка слиянием.
• Сортировка подсчётом.

Алгоритмы неустойчивой сортировки

• Сортировка Шелла.
• Пирамидальная сортировка (сортировка кучи, Heapsort).
• Быстрая сортировка.
• Поразрядная сортировка (она же цифровая сортировка).

Непрактичные алгоритмы сортировки

• Сортировка перестановкой.

Алгоритмы, не основанные на сравнениях

• Сортировка подсчётом (Counting sort)

В языке С существуют два метода обращения к элементу массива: индексация массива и адресная арифметика.

Например, написав

pa = &a[0];

pa = a;

где pa – указатель, то получим один и тот же результат.

Так, запись *(a) аналогична записи a[0], а запись *(a+i) аналогична записи a[i]. Записи &a[i] и a+i также будут эквивалентными, т. е. и в том и в другом случае это адрес i-го элемента после элемента a[0].

Цикл сдвига элементов массива a [] размерности N влево на K позиций:

for (int g = 1; g <= K; g++)

{

  a[N] = a[0];

  for (int i = 0; i < N; i++)

         a[i] = a[i + 1];

}

 

29. Алгоритмы вставки и удаления элементов в одномерном массиве. Эффективные алгоритмы решения этих задач.

 

Задача. Удаление элемента из массива

Пусть нужно удалить из массива X, состоящего из n элементов, m-й по номеру элемент. Для этого достаточно записать (m+1)-й элемент на место элемента m, (m+2)-й на место (m+1)-го и т.д., n-1 на место (n-2) и при дальнейшей работе с этим массивом использовать n-1 элемент:

#include <iostream>

using namespace std;

int main()

{

  int X[10], N, i, m;

  cout << "N="; cin >> N; //ввод реального размера массива

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

  {

         cout << "\n X[" << i << "]="; //сообщение о вводе элемента

         cin >> X[i]; //ввод элементов массива в цикле

  }

  cout << "m="; cin >> m; //ввод номера элемента, подлежащего удалению

 

  for (i = m; i<N - 1; i++) X[i] = X[i + 1]; //удаление m-го элемента

  for (i = 0; i<N - 1; i++)

         cout << "\n X[" << i << "]=" << X[i]; //вывод массива

  N--;

  return 0;

}

Задача. Вставка элемента в массив после элемента с заданным номером .

Пусть нужно в массив X, состоящий из n элементов, вставить новый элемент со значением Y после элемента с номером m.

Для этого, во-первых, нужно заранее предусмотреть, что размерность массива будет больше, чем у изначально заданного массива. Далее необходимо сдвинуть все элементы, начиная с последнего и до элемента с номером (m+1) вправо и на место элемента с номером (m+1) вставить новый элемент Y.

#include <iostream>

using namespace std;

int main()

{

  int X[10], N, i, m, Y;

  cout << "N="; cin >> N; //ввод реального размера массива

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

  {

         cout << "\n X[" << i << "]="; //сообщение о вводе элемента

         cin >> *(X + i); //ввод элементов массива в цикле

  }

  cout << "m="; cin >> m; //ввод номера элемента, после которого осуществляется вставка

  cout << "Y="; cin >> Y; //вставляемый элемент

 

  for (i = N; i>m + 1; i--) *(X + i) = *X + i - 1); //сдвиг элементов массива

  *(X + m + 1) = Y;

  for (i = 0; i<N + 1; i++)

         cout << "\n X[" << i << "]=" << *(X + i); //вывод массива

  return 0;

}

 

30. Методы поиска: линейный и бинарный поиск. Эффективные алгоритмы решения этих задач.

 

Алгоритм линейного поиска

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

 

int LineSearch(int A[], int key)

{

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

  if (A[i] == key) return i;

  return -1;

}

Алгоритм бинарного поиска

Ход работы алгоритма, разделенный на этапы, выглядит следующим образом:

1. зона поиска (на первом шаге ей является весь массив) делиться на две равные части, путем определения ее среднего (mid) элемента;
2. средний элемент сравнивается с искомым (key), результатом этого сравнения будет один из трех случаев:

§ key<mid. Крайней правой границей области поиска становится элемент, стоящий перед средним (right ← mid-1);

§ key>mid. Крайней левой границей области поиска становится следующий за средним элемент (left ← mid+1);

§ key=mid. Значения среднего и искомого элементов совпадают, следовательно элемент найден, работа алгоритма завершается.

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

 

int BinarySearch(int A[], int key)

{

  int left = 0, right = N, mid;

  while (left <= right)

  {

         mid = left + (right - left) / 2;

         if (key<A[mid]) right = mid - 1;

         else if (key>A[mid]) left = mid + 1;

         else return mid;

  }

  return -1;

}

 

31. Алгоритмы сортировки. Сортировка простыми обменами. Шейкер-сортировка.

 

Сортировка простыми обменами (пузырёк).

Идея алгоритма заключается в следующем. Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. Всего для этого потребуется N*(N-1) сравнений.

 

void sort_bubble(int *m, int n) // Сортировка пузырьком

{

  int i, j, t;

  for (i = 0; i < n - 1; i++)

  for (j = 0; j < n - i - 1; j++)

  if (m[j]>m[j + 1])

  {

         t = m[j];

         m[j] = m[j + 1];

         m[j + 1] = t;

  }

}

Шейкер-сортировка

Перестановка элементов в шейкерной сортировке выполняется аналогично той же в пузырьковой сортировке, т. е. два соседних элемента, при необходимости, меняются местами. Пусть массив требуется упорядочить по возрастанию. Обозначим каждый пройденный путь от начала до конца последовательности через W_i, где i – номер пути; а обратный путь (от конца к началу) через -W_j, где j – номер пути. Тогда после выполнения W_i, один из неустановленных элементов будет помещен в позицию справа, как наибольший из еще неотсортированных элементов, а после выполнения -W_j, наименьший из неотсортированных, переместиться в некоторую позицию слева. Так, например, после выполнения W₁в конце массива окажется элемент, имеющий наибольшее значение, а после -W₁ в начало отправиться элемент с наименьшим значением.

void sort_sheiker(int *m, int n) 

{

  int left = 1;                // левая граница

  int right = n - 1;           // правая граница

  int j, t, k = n - 1;

  do              // Обратный проход "Пузырька" от правой границы до левой

  {

         for (j = right; j >= left; j--)

         if (m[j - 1]>m[j])

         {

                t = m[j - 1]; m[j - 1] = m[j]; m[j] = t;

                k = j;   // фиксирование индекса последнего обмена

         }

         left = k + 1;         // Левая граница

         //Прямой проход "Пузырька" от левой границы до правой

         for (j = left; j <= right; j++)

         if (m[j - 1]>m[j])

         {

                t = m[j - 1]; m[j - 1] = m[j]; m[j] = t;

                k = j;          // фиксирование индекса последнего обмена

         }

         right = k - 1;               // правая граница

  } while (left <= right);// До тех пор, пока левая граница не станет больше правой границы

}

 

32. Алгоритмы сортировки. Сортировка простым выбором. Сортировка Шелла.

 

Сортировка простым выбором

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;
2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key;
3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;
4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.

void sort_vybor(int *a, int n) // Сортировка простым выбором

{

  int k, m;

  for (int i = n - 1; i >= 0; i--)

  {

         k = i;                // Запоминаем номер и

         m = a[i];                           // значение текущего элемента

         for (int j = 0; j<i - 1; j++) // Поиск максимального элемента

         if (a[j]>m) { k = j; m = a[k]; }

         if (k != i)

         {                                   // Меняем местами с последним

                a[k] = a[i];

                a[i] = m;

         }

  }

}

Сортировка Шелла.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

void Shell(int A[], int n) //сортировка Шелла

{

  d = n;

  d = d / 2;

  while (d>0)

  {

         for (i = 0; i<n - d; i++)

         {

                j = i;

                while (j >= 0 && A[j]>A[j + d])

                {

                      count = A[j];

                      A[j] = A[j + d];

                      A[j + d] = count;

                      j--;

                }

         }

         d = d / 2;

  }

}

33. Алгоритмы сортировки. Сортировка простыми вставками. Сортировка бинарными вставками.

 

Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию (в колоде карты расположены в случайном порядке) будет следующим. Обратим внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:

1. первая и вторая карта меньше третьей;
2. первая и вторая карта больше третьей;
3. первая карта уступает значением третьей, а вторая превосходит ее;
4. первая карта превосходит значением третью карту, а вторая уступает ей.

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

void sort_insert(int *m, int n)

{

  int j, r;

  for (int i = 1; i<n; i++)

  {

         r = m[i]; // Запоминаем текущий элемент в промежуточной переменной

         j = i - 1;

         while (j >= 0 && m[j]>r)     // Ищем новое место вставки,

         {

                m[j + 1] = m[j]; j--;

         } // сдвигая на 1 элемент вправо

         m[j + 1] = r; // На освободившееся место вставляется элемент

  }

}

 

Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],..., a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

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;

         }

  }

}

 

 

34. Алгоритм слияния двух упорядоченных массивов. Сортировка слияниями.

Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.

В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:

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

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

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

Основная подпрограмма MergeSort рекурсивно разбивает и сортирует массив, а Merge отвечает за его слияние. Так можно записать псевдокод основной подпрограммы:

void Merge(int *A, int first, int last)

{

  int middle, start, final, j;

  int *mas = new int[100];

  middle = (first + last) / 2; //вычисление среднего элемента

  start = first; //начало левой части

  final = middle + 1; //начало правой части

  for (j = first; j <= last; j++) //выполнять от начала до конца

  if ((start <= middle) && ((final>last) || (A[start]<A[final])))

  {

         mas[j] = A[start];

         start++;

  }

  else

  {

         mas[j] = A[final];

         final++;

  } //возвращение результата в список

  for (j = first; j <= last; j++) A[j] = mas[j];

  delete[]mas;

};

//рекурсивная процедура сортировки

void MergeSort(int *A, int first, int last)

{

  {

         if (first<last)

         {

                MergeSort(A, first, (first + last) / 2); //сортировка левой части

                MergeSort(A, (first + last) / 2 + 1, last); //сортировка правой части

                Merge(A, first, last); //слияние двух частей

         }

  }

}

 

 

35. Алгоритмы сортировки. Пирамидальная сортировка.

 

Идею алгоритма можно описать следующим образом:

• Пи­ра­ми­да — дво­ич­ное де­ре­во, в ко­то­ром зна­че­ние каж­до­го эле­мен­та боль­ше ли­бо рав­но зна­че­ний до­чер­них эле­мен­тов.
• За­пол­нив де­ре­во эле­мен­та­ми в про­из­воль­ном по­ряд­ке, мож­но лег­ко его от­сор­ти­ро­вать (лег­че, чем ис­ход­ный спи­сок эле­мен­тов), пре­вра­тив в пи­ра­ми­ду.
• Са­мый боль­шой эле­мент пи­ра­ми­ды на­хо­дит­ся в её вер­ши­не.
• От­де­ля­ем вер­шин­ный эле­мент, и за­пи­сы­ва­ем его в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва.
• На ме­сто вер­шин­но­го эле­мен­та за­пи­сы­ва­ем эле­мент из са­мо­го ниж­не­го уров­ня де­ре­ва.
• Вос­ста­нав­ли­ва­ем (пе­ре­сор­ти­ро­вы­ва­ем) пи­ра­ми­ду.
• Са­мый боль­шой эле­мент из остав­ших­ся сно­ва в вер­ши­не. Сно­ва от­де­ля­ем его и за­пи­сы­ва­ем его в ка­че­стве пред­по­след­не­го эле­мен­та ре­зуль­та­та, и так да­лее...
• Весь фо­кус ал­го­рит­ма в том, что пи­ра­ми­да без до­пол­ни­тель­ных за­трат хра­нит­ся пря­мо в ис­ход­ном мас­си­ве. По ме­ре то­го, как раз­мер пи­ра­ми­ды умень­ша­ет­ся, она за­ни­ма­ет всё мень­шую часть мас­си­ва, а ре­зуль­тат сор­ти­ров­ки за­пи­сы­ва­ет­ся на­чи­ная с кон­ца мас­си­ва на осво­бо­див­шие­ся от пи­ра­ми­ды ме­ста.

#include <stdio.h>

 

#define MAXL 1000

 

void swap(int *a, int *b){

  int t = *a;

  *a = *b;

  *b = t; }

int main() {

  int a[MAXL], n, i, sh = 0, b = 0;

  scanf("%i", &n);

  for (i = 0; i < n; ++i) scanf("%i", &a[i]);

  while (1) {

         b = 0;

         for (i = 0; i < n; ++i) {

         if (i * 2 + 2 + sh < n) {

         if (a[i + sh] > a[i * 2 + 1 + sh] || a[i + sh] > a[i * 2 + 2 + sh]) {

         if (a[i * 2 + 1 + sh] < a[i * 2 + 2 + sh]) {

                      swap(&a[i + sh], &a[i * 2 + 1 + sh]);

                      b = 1; }

                             else if (a[i * 2 + 2 + sh] < a[i * 2 + 1 + sh]) {

                                    swap(&a[i + sh], &a[i * 2 + 2 + sh]);

                                    b = 1;                }

                      }

                }

                else if (i * 2 + 1 + sh < n)

                {

                      if (a[i + sh] > a[i * 2 + 1 + sh]) {

                             swap(&a[i + sh], &a[i * 2 + 1 + sh]);

                         b = 1;   }

                }

         }

         if (!b) sh++;

         if (sh + 2 == n) break;

  }

  for (i = 0; i < n; ++i) printf("%i%c", a[i], (i != n - 1) ? ' ' : '\n');

  return 0;

}

36. Алгоритмы сортировки. Быстрая сортировка Хоара.

 

Идея метода: весь массив делится на две равные части с использованием барьерного элемента. В правой части располагаются элементы, большие барьерного; в левой – меньшие. Если в правой части обнаруживается элемент меньший барьерного, а в левой – больший, то они меняются местами. Далее левую часть снова делим пополам, выбираем барьерный элемент и т.д.

Алгоритм быстрой сортировки удобнее реализовать, если использовать рекурсию.

Рассмотрим элемент, находящийся посередине массива М (назовем его Х). Затем начнем осуществлять два встречных просмотра массива: двигаемся слева направо, пока не найдем элемент M[i]>X и справа налево, пока не найдем элемент M[j]<X. Когда указанные элементы будут найдены, поменяем их местами и продолжим процесс "встречных просмотров с обменами", пока два идущих навстречу друг другу просмотра не встретятся. В результате массив разделится на две части: левую, состоящую из элементов меньших или равных Х, и правую, в которую попадут элементы, большие или равные Х. После такого разделения массива М, чтобы завершить его сортировку, достаточно осуществить то же самое с обеими полученными частями, затем с частями этих частей и т.д., пока каждая часть не будет содержать ровно один элемент.

Реализация указанного метода приводит к следующему (рекурсивному!) решению задачи сортировки:

void Qsort(int a[], int L, int R) // или ...int *a

{

  int i = L, j = R, w, x;

  x = a[(L + R) / 2];

  do {

         while (a[i]<x) i++;

         while (a[j]>x) j--;

         if (i <= j)

         {

                w = a[i]; a[i] = a[j]; a[j] = w;

                i++; j--;

         }

  } while (i<j);

  if (L<j) Qsort(a, L, j);

  if (i<R) Qsort(a, i, R);

}

 

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

Qsort(a,0,N-1);

 

 

37. Алгоритмы сортировки. Сортировка подсчетом. Цифровая сортировка.

 

Сортировка подсчётом

Сортировка подсчётом предполагает использование выходного массива. Идея алгоритма заключается в том, что мы просматриваем входной массив и сравниваем in[i] и in[j] элементы массива. Если in[i] > in[j], то увеличиваем значение индекса на 1 .Индекс определяет позицию элемента в выходном массиве.

void sort_podchet(int count, double *in, double *out)

{

  int i, j, k;

  for (i = 0; i &lt; count; i++)

  {

         for (j = k = 0; j &lt; count; j++)

         if (in[j] & lt in[i] || (in[i] == in[j] && i &lt; j))k++;

         out[k] = in[i];

  }

}

Цифровая сортировка

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

Поразрядная сортировка подразумевает следующее: сначала элементы сортируются по своему младшему (последнему) разряду, затем следующему (предпоследнему) и т.д. до старшего разряда, первого.

На каждой своей итерации алгоритм включает 2 этапа: распределение и сборка.

Перед сортировкой необходимо определить 2 величины:

1. width - максимальное количество разрядов в сортируемых величинах, по-другому - количество разрядов в самом длинном ключе.
2. range - количество возможных значений одного разряда ключа. Т.е. для десятичных чисел очевидно имеем – 10.

Создаются range вспомогательных списков - "карманов", т.е. на каждое возможное значение разряда элемента - по карману, т.е. по списку. Далее - первый этап распределение по карманам и на первом проходе элементы исходной последовательности помещаются в эти карманы (списки) по их младшему разряду, т.е. по самому правому числу. Какой этот самый младший разряд у элемента, в такой карман этот элемент и помещается.

Например, пусть имеем исходную последовательность из {11, 24, 9, 59, 21, 98, 76, 8}, для которой определяем width = 2, range = 10, поэтому будет 10 "карманов": список0, список1..., список9. Тогда на первом проходе карманы №2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:

• список0: 9, 8
• список1: 11, 21
• список4: 24
• список6: 76
• список8: 98
• список9: 59

Далее второй этап - сборка: просто последовательно соединяем один за другим все карманы и располагаем элементы уже в этой последовательности:
9, 8 (это был список0), 11, 21 (список1), 24 (список4), 76 (список 6), 98 (список8), 59 (список9)

Это был один проход алгоритма, соответствующий крайнему правому разряду ключа.
На следующем проходе, элементы из уже обновленной последовательности распределяются по карманам в соответствии с их вторым(т.е. предпоследним) разрядом и т.д по самого старшего, максимального, width-го разряда ключа.

 

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

 

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

< тип элементов > < имя массива > [количество] [количество];

 

Многомерные массивы задаются указанием каждого измерения в квадратных скобках. ■ Например, int a [2][3]; задает описание двумерного массива из 2 строк и 3 столбцов:

 

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

 ■ Структурная инициализация:

 ❑ int array [2][3] = {{1, 2, 3}, {2, 3, 4}};

 ❑ int mass2 [ ][2] = { {1, 1}, {0, 2}, {1, 0} };

 // Если при описании двумерного массива задаются значения элементов, то можно не указывать только количество строк

. ■ Бесструктурная инициализация:

❑ int mass2 [3][2] = {1, 1, 0, 2, 1, 0};

❑ int m[ ] [3] = { 00, 01, 02, 10, 11, 12, 20, 21, 22} ;

 

Доступ к элементам двумерного массива осуществляется как по индексу, так и с помощью указателей: ■ A[i][j] указываются все индексы ■ *(A[i]+j) используется указатель-константа на первый элемент строки (A[i] - адрес начала i-й строки массива) ■ *(*(A+i)+j) используется имя массива как адрес начала массива указателей

 

Операции возможны только над отдельными элементами массивов.

 ■ Ввод значений двумерного массива осуществляется с помощью «двойного» цикла: int a[2][3], i, j;

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

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

cin >> a[i][j];

 

Вывод элементов двумерного массива по строкам:

#include <iostream>

#include <iomanip>

using namespace std;

... for (i=0; i< 2; i++)

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

 cout << setw(4)<< a[i][j];

cout<< '/n';

}

 

Транспонирование квадратной матрицы

…

for(i=0; i<N-1; i++) 

for(j=i+1; j<N; j++)

{tmp=a[i][j]; a[i][j]=a[j][i]; a[j][i]=tmp;}

…

 Умножение матриц.

#include <iostream>

#include<cstdlib>

using namespace std;

void main()

{ int const N=10;

int a[N][N],b[N][N],d[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<N; j++)

{

cout<<"? "; cin>> b[i][j]; }

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

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

{

c[i][j]=0; for(k=0; k<N; k++)

c[i][j +=a[i][k]*b[k][j];

}

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

{

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

 cout<<c[j][j]<<“ “;

cout<<endl; 

}

}

 

Главная диагональ:

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

{

 // работаем с A[i][i] 

 }

Побочная диагональ:

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

{

 // работаем с A[i][N-1-i]  

}

Главная диагональ и под ней:

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

for( j=0; j<= i; j++ ) { // работаем с A[i][j] }

39. Двумерные массивы. Перестановка, вставка и удаление строк (столбцов) двумерного массива. Эффективные алгоритмы решения этих задач.

 

Перестановка строк

■ Перестановка двух строк, номера которых n1 и n2 заданы, выполняется следующим образом:

const int n=10;

const int m=5;

double A[n][m];

int n1, n2;

cin >> n1>> n2;

int R;

for (int j=0; j<m; j++)

//цикл по столбцам

{

 R=A[n1][j];  

 A[n1][j]= A[n2][j];  

 A[n2][j]=R;

}

 

Удаление строки

■ Удаление k-ой строки выполняется так:

const int n=10;

const int m=5;

double A[n][m];

int k;

cin >> k;

for (int i=k; i<n-1; i++)

for (int j=0; j<m; j++)

 A[i][j] =A[i+1][j];

 

Вставка строки

■ Для вставки после k-й строки матрицы новой строки необходимо:

1. объявить массив int A[n][m] с увеличенным на 1 количеством строк;

2. все строки от предпоследней до k-й переместить вниз:

for (int i=n-1; i>k+1; i--)

for (int j=0; j<m; j++)

A[i][j] =A[i-1][j];

3. на место (k+1)-й строки поместить вставляемую строку, например, одномерный массив В такой же размерности m, что и строка матрицы:

for ( int j=0; j<m; j++) 

A[k+1][j] =B[j];

 

40. Работа со строками. Стандартные функции обработки строк. Примеры.

 

Таблица 1 — Функции для работы со строками и символами
Функция	Пояснение
strlen (имя_строки)	определяет длину указанной строки, без учёта нуль-символа

Копирование строк