Лекции по информатике

Подождите немного. Документ загружается.

void main(void)

{

int values[AKKAY_SIZE] = (80, 70, 90, 85, 80};

int i;

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

printf("values[%d] %d\n", i, values[i]);

}

Теперь, если понадобится изменить размер массива, можно просто изменить

значение константы ARRA Y_SIZE; в этом случае автоматически изменится как верхняя

граница цикла обработки массива, так и размер самого массива.

Символьные строки

Программисты на C++ широко используют символьные строки для хранения имен

пользователей, имен файлов и другой символьной информации.

Для объявления символьной строки внутри программы просто объявите массив

типа char с количеством элементов, достаточным для хранения требуемых символов.

Например, следующее объявление создает переменную символьной строки с именем

filename, способную хранить 64 символа (не забывайте, что символ NULL является одним

из этих 64 символов):

char filename[64];

Главное различие между символьными строками и другими типами массивов

заключается в том, как C++ указывает последний элемент массива.

Программы на C++ представляют конец символьной строки с помощью символа

NULL, который в C++ изображается как специальный символ ' '. Когда вы присваиваете

символы символьной строке, вы должны поместить символ NULL (' ') после последнего

символа в строке. Например, следующая программа ALPHABET. CPP присваивает буквы

от А до Я переменной alphabet, используя цикл for. Затем программа добавляет символ

NULL в эту переменную и выводит ее с помощью cout.

#include <iostream.h>

void main(void)

{

MMMchar alphabet [34]; // 33 буквы плюс NULL char letter;

MMMint index;

MMMfor (letter = 'A', index = 0; letter <= 'Я';

MMMletter++, index++) alphabet[index] = letter;

MMMalphabet[index] = NULL;

MMMcout << "Буквы " << alphabet;

}

Когда выходной поток cout выводит символьную строку, он по одному выводит

символы строки, пока не встретит символ NULL.

Как 'А' отличается от "А"

При рассмотрении программ на C++ вы можете встретить символы, заключенные в

одинарные кавычки (например, 'А') и символы, заключенные в двойные кавычки ("А").

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

Компилятор C++ выделяет только один байт памяти для хранения символьной константы.

Однако символ в двойных кавычках представляет собой строковую константу —

указанный символ и символ NULL (добавляемый компилятором). Таким образом,

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

В зависимости от потребностей программы может возникнуть необходимость

включения в строку знаков кавычек. Предположим, что требуется представить

следующую строку:

ОН сказал "Стоп".

Поскольку в Си двойные кавычки используются для определения строковой

константы, необходимо средство, подсказывающее компилятору присутствие кавычек в

строке. Для задания кавычки в строке используется последовательность \":

"Он сказал \"Стоп\"."

Инициализация символьной строки

Как вы уже знаете, C++ позволяет вам инициализировать массивы при

объявлении. Символьные строки C++ не являются исключением. Для инициализации

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

как показано ниже:

char title[64] = "Учимся программировать на языке C++";

Если количество символов, присваиваемое строке, меньше размера массива,

большинство компиляторов C++ будут присваивать символы NULL остающимся

элементам строкового массива. Как и в случае с массивами других типов, если вы не

указываете размер массива, который инициализируете при объявлении, компилятор C++

распределит достаточно памяти для размещения указанных букв и символа NULL:

char title[] = "Учимся программировать на языке C++";

Следующая программа INIT_STR.CPP инициализирует символьную строку при

объявлении:

#include <iostream.h>

void main(void)

{

MMMchar title[64] = "Учимся программировать на языке C++";

MMMchar lesson[64] = "Символьные строки";

MMMcout << "Книга: " << title << endl;

MMMcout << "Урок: " << lesson << endl;

}

Передача строк в функцию

Передача символьной строки в функцию подобна передаче любого массива в

качестве параметра. Внутри функции вам нужно просто указать тип массива (char) и

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

следующая программа использует функцию show_string для вывода символьной строки

на экран:

#include <iostream.h>

void show_string(char string[])

{

MMMcout << string << endl;

}

void main(void)

{

MMMshow_string("Привет, C++!");

MMMshow_string("Учусь программировать на C++");

}

Так как символ NULL указывает конец строки, функция не требует параметр,

который задает количество элементов в массиве. Вместо этого функция может

определить последний элемент, просто найдя в массиве символ NULL.

Вычисление длины строки

Известно, что символ NULL рассматривается в функциях Си обычно как символ,

обозначающий конец строки. Такие функции, как fgets и cgets, присваивают символ NULL

автоматически. В следующей программе SHOW_STR.C функция sets используется для

чтения строки символов с клавиатуры, -затем с помощью цикла for выполняется

посимвольный вывод содержимого строки до тех пор, пока не будет обнаружен символ

NULL:

#include <stdio.h>

void main (void)

{

char string[256]; // Строка для ввода пользователя

int i; // Индекс в строке

printf("Введите строку символов и нажмите Enter:\n");

gets(string);

for (i = 0; string[i] != NULL; i++) putchar(string[i]);

printf("\nЧисло символов в строке равно %d\n", i);

}

При работе программы со строками многие из выполняемых операций базируются

на количестве символов в строке. Для определения в программе количества символов

строки большинство Си-компиляторов предоставляет функцию strlen, которая возвращает

число символов в заданной строке. Функция strlen имеет следующий формат:

#include <string.h>

size_t strlen(const char string);

В следующей программе демонстрируется использование strlen:

#include <stdio.h>

#include <string.h>

void main(void)

{

char book_title[] = "1001 совет по C/C++";

printf("%s содержит %d символов\n",

book_title, strlen (book_title));

}

Копирование символьных строк

При работе со строками часто возникает потребность в копировании одной

символьной строки в другую. Для выполнения этой операции большинство Си-

компиляторов предоставляет функцию strcpy, с помощью которой символы одной строки

(строка-источник) копируются в другую строку (строку-цель):

#include <string.h>

char *strcpy(char *destination, const char *source);

В качестве результата функция strcpy возвращает указатель на начало целевой

строки. В следующей программе STRCPY.C демонстрируется использование функции

strcpy:

#include <stdio.h>

#include <string.h>

void main(void)

{

char title[] = "1001 совет по C/C++";

char book[128];

strcpy(book, title);

printf("Название книги %s\n", book);

}

Массивы строк

Можно организовать массив строк точно так же, как массив данных любого другого

типа. Но массив строк, по сути, будет являться уже массивом массивов символов.

Массив, элементы которого сами являются массивами, называется двухмерным

массивом.

Двухмерный массив можно представить себе как таблицу, имеющую ряды и

колонки. Такой массив следует определять с двумя индексами, один из которых

определяет количество рядов таблицы, а второй устанавливает количество колонок.

Ниже приведены инструкции, определяющие массив, имеющий 10 рядов и 20 колонок, то

есть содержащий 200 целочисленных переменных:

int table[10][20];

Представим себе каждый элемент как целое число, занимающее собственную

клеточку в таблице 10х20. Элемент table[0][0] находится в левом верхнем углу таблицы, а

элемент table[0][1] занимает соседнюю клетку справа в том же ряду.

Определяя массив строк, также необходимо использовать два индекса. Первый

определяет максимальное количество строк в массиве, а второй указывает

максимальную длину каждой строки. Таким образом, определение

char names[10][20];

задает десять строковых переменных names длиной не больше 19 символов в

каждой.

Если вы хотите задавать строки путем ввода значений отдельных символов,

следует использовать вложенные циклы. Внешний цикл будет повторяться 10 раз, по

одному на каждую строку, а внутренний должен иметь 19 повторов для ввода значений

одной строки.

Для того чтобы ввести символ в строку, необходимо использовать оба индекса:

name[index][index2] = letter;

Первый индекс указывает номер нужной строки внутри массива, а второй

определяет позицию символа внутри строки.

Расположение матриц в памяти

Двумерный массив можно инициировать так:

static int matr[2][5] = {{3,4,0,1,2},{6,5,1,4,9}};MM

Матрица хранится в памяти построчно, т.е. самый правый индекс в наборе

индексов массива меняется наиболее быстро.

Например, для массива char aCh[2][4] будет выделено восемь байтов памяти, в

которых в следующем порядке будут размещены элементы массива:

элемент aCh[0][0] aCh[0][1] aCh[0][2] aCh[0][3] aCh[1][0] aCh[1][1] aCh[1][2] aCh[1][3]

N байта 1 2 3 4 5 6 7 8

Трехмерный массив

При размещении трехмерного массива char aс[3][2][3] память под элементы этого

массива будет выделяться последовательно в соответствии со следующими значениями

индексов:

A000 A001 A002 A010 A011 A012 A100 A101 A102

A110 A111 A112 A200 A201 A202 A210 A211 A212

Общий объем выделяемой под массив памяти определяется как произведение

всех размерностей массива (общее число элементов), умноженное на длину типа данных

массива.

Алгоритмы сортировки массива

Пузырьковая сортировка

Расположим массив сверху вниз, от нулевого элемента - к последнему.

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути

просматриваются пары соседних элементов. Если элементы некоторой пары находятся в

неправильном порядке, то меняем их местами.

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

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

элемента, таким образом, второй по величине элемент поднимается на правильную

позицию...

Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в

ней не останется только один элемент. На этом сортировка заканчивается, так как

последовательность упорядочена по возрастанию.

#include <iostream.h>

#include <conio.h>

int main()

{int array[100],size,x,y,temp,i;

cin>>size;

for (x=0;x<size;x++)

cin>>array[x];

for (i=size;i>0;i--)

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

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

{

int b=array[j];

array[j]=array[j+1];

array[j+1]= b;

}

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

cout<<array[i]<<" ";

getch();

return 0;

}

Главным недостатком пузырьковой сортировки является количество перестановок

элементов массива.

Выборочная сортировка

Идея метода состоит в том, чтобы создавать отсортированную

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

правильном порядке. Будем строить готовую последовательность, начиная с левого

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

заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с

a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i]

(выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся

последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем

месте по праву: все меньшие элементы уже ушли влево.

Далее приведен код выборочной сортировки по возрастанию элементов.

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

подмассивы и отыскивать наименьший элемент в каждом из них. Подмассивы будут

ограничиваться с двух сторон индексами start и size-1. Правый индекс равен size-1, т.к.,

если все прочие элементы заняли свои места, наибольший элемент автоматически

оказывается в правильном расположении.

#include <iostream.h>

#include <conio.h>

main() {

int array[100], size, min_pos, i, start, min, temp;

cin>>size;

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

cin>>array[i];

start=0;

while (start!=size-1) {

min=array[start];

min_pos=start;

for (i=start; i<size; i++)

if (array [i]<min)

{

min=array[i];

min_pos=i; }

if (min_pos!=start)

temp=array[start];

array[start]=array[min_pos];

array[min_pos]=temp; }

start++;

} for (i=0; i<size; i++)

cout<<array[i]<< " ";

getch();

return 0;

}

Пузырьковая сортировка и выборочная сортировка сравнительно неэффективны,

их среднее время работы пропорционально n

, где n – количество элементов массива.

Быстрая сортировка

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является

наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:

1. из массива выбирается некоторый опорный элемент a[i],

2. запускается процедура разделения массива, которая перемещает все ключи,

меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] -

вправо,

3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно

правого,

4. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно

запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.

1. Введем два указателя: i и j. В начале алгоритма они указывают,

соответственно, на левый и правый конец последовательности.

2. Будем двигать указатель i с шагом в один элемент по направлению к концу

массива, пока не будет найден элемент array [i] >=p. Затем аналогичным образом

начнем двигать указатель j от конца массива к началу, пока не будет найден array[j]<=р.

3. Далее, если i<=j, меняем array [i] и array [j] местами и продолжаем двигать i и j

по тем же правилам.

4. Повторяем шаг 2, пока i<=j.

Теперь массив разделен на две части: все элементы левой меньше либо равны

опорному элементу, все элементы правой — больше либо равны опорному элементу.

Разделение завершено.

Проиллюстрируем работу алгоритма на примере. Исходный массив:

5 2 7 2 13 3 8 15 19

Выберем опорный элемент р. Например, пусть это будет элемент 13. 1.

Шаг 1. Меняем местами элементы в позициях 4 и 6:

5 2 7 2 8 3 13 15 19

Выбираем опорный элемент 7.

Шаг 2. Меняем местами элементы в позициях 2 и 5:

5 2 3 2 8 7 13 15 19

Выбираем опорный элемент 2.

Шаг 3. Меняем местами элементы в позициях 0 и 3:

2 2 3 5 8 7 13 15 19

Выбираем опорный элемент 8

Шаг 4. Меняем местами элементы в позициях 4 и 5:

2 2 3 5 7 8 13 15 19

Сортировка закончена, т. к. все элементы встали на свои позиции.

Далее приведен код быстрой сортировки. Быструю сортировку выполняет функция

quicksort. В качестве параметров функции выступают верхняя и нижняя границы

обрабатываемого на данном шаге подмассива.

#include <iostream.h>

#include <conio.h>

int array[100000];

void quicksort(long High, long Low)

{

long i,j;

int p, temp;

i=Low;

j=High;

p=array[(Low+High)/2];

while(array[i]<p)

i++;

while(array[j]>p) j--;

if (i<=j)

{

temp=array[i];

array[i]=array[j];

array[j]=temp;

while (i<=j);

if (j>Low) quicksort(j, Low);

if (High>i) quicksort(High, i);

}

main()

{

int size;

int i ;

cin>>size;

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

cin>>array[i];

quicksort(size-1, 0);

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

cout<<array[i]<<” “;

getch();

return 0;

}

Сортировка массива при известном интервале значений элементов

Данная сортировка применима к массиву только в том случае, если задано

некоторое число К, и все элементы массива меньше либо равны ему, т. е. для

выполнения данной сортировки необходимо знать один общий интервал, в котором лежит

каждый элемент массива. Алгоритм такой сортировки достаточно прост в реализации.

Пусть дан массив натуральных чисел, значение каждого элемента которого не

превышает девяти (табл. 1).

Таблица 1. Массив натуральных чисел

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

число ячеек в котором совпадает с числом К. В нашем случае необходимо выделить

память для массива из девяти ячеек, которые будут заполнены нулями (табл. 2).

Таблица 2. Вспомогательный массив, заполненный нулями

Теперь будем поочередно просматривать каждый элемент массива, который

необходимо отсортировать, и, если на /-ом шаге выделен элемент М, то во

вспомогательном массиве значение элемента, находящегося в позиции М, увеличиваем

на единицу.

Совершим вышеописанные действия с заданным массивом чисел. После

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

Таблица 3.

Теперь вспомогательный массив обработан, можно выводить результат

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

выводим номер его позиции Р раз, где Р равно значению данного элемента.

Итак, в нашем случае вывод будет следующим: 2, 4, 5, 5, 8, 9.

Теперь рассмотрим программу, которая сортирует массив натуральных чисел

вышеуказанным методом. Чтобы не вводить все элементы массива, сгенерируем их

случайным образом при помощи функции random(int). Ниже приведен код данной про-

граммы:

#include <iostream.h>

#include <conio.h>

tinclude <stdlib.h>

int i, j, N, K, array[1000], Help_array[1000];

main()

{

cin>>N>>K;

randomize();

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

array[i]=random(K);

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

Help_array[array[i]]+=1;

for (i=1; i<K; i++)

if (Help_array!=0)

for (j=0; j<Help_array[i]; j++)

cout<<i<<” “;

getch();

return 0;

}

Поиск заданного элемента в массиве

Последовательный поиск элемента

Необходимо запустить цикл повторений, который станет просматривать все

элементы один за другим до тех пор, пока нужный элемент не будет найден, либо пока не

будут пройдены все его элементы.

#include <iostream.h>

#include <conio.h>

int Search(int array[], int N, int Number)

{

int i = 0;

while (i!=N)

if (array[i]==Number) return i; else i++;

return -1; }

main()

{

int i, Size, Numerals[1000], Number, P;

соut<<"Введите размерность массива! "<<endl;

cin>>Size;

cout<<" Введите элементы массива! "<<endl;

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

cin>>Numerals[i];

cout<<"Введите число для поиска! "<<endl;

cin>>Number;

P=Search (Numerals, Size, Number);

if (P==-l)

cout<<"No"; else cout<<"Yes "<<P+l;

getch();

return 0;

}

Двоичный (бинарный) поиск

Если у нас есть массив, содержащий упорядоченную последовательность данных,

то очень эффективен двоичный поиск.

Переменные Left и Right содержат, соответственно, левую и правую границы

отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с

исследования среднего элемента отрезка. Если искомое значение меньше среднего

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

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

область поиска. Так, в нашем примере, после первой итерации область поиска – всего

лишь три элемента, после второй остается всего лишь один элемент. Таким образом,

если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Двоичный поиск - очень мощный метод. Если, например, длина массива равна

1023, после первого сравнения область сужается до 511 элементов, а после второй - до

255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10

сравнений.

#include <iostream.h>

#include <conio.h>

int Binary_Search(int array[], int N, int Number)

{

int Left, Right, Middle;

Left=0;

Right=N-1;

Middle=(Left+Right)/2;

while (Left<=Right)

{

if (array[Middle]==Number) return Middle;

if (array [Middle]>Number) Right=Middle-l;

else Left=Middle+l;

Middle=(Left+Right)/2; }

return -1; }

main()

{

int i, Size, Numerals[100000], Number, Pos;

cout<<"Введите размер массива! "<<endl;

cin>>Size;

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

Numerals[i]=i;

cout<<"Введите число для поиска! "<<endl;

cin>>Number;

Pos=Binary_Search(Numerals,Size,Number);