Электронный конспект по программированию часть 1. Программа на языке Си, так же как и на большинстве современных языков программирования, создается в два этапа
 Скачать 32.35 Mb.
|
|
Снег на экране Приведенная ниже программа генерирует случайное значение x в интервале [0,399], случайное значение y в интервале [0,299] и проверяет цвет точки с координатами (x,y). Если эта точка черная, то ее цвет устанавливается случайный, а если нет — черный. Случайный цвет строится с помощью стандартной функции COLOR из красной (R), зеленой (G) и синей (B) составляющих, которые выбираются случайно в интервале [0,255].  • для определения того, была ли нажата какая-нибудь клавиша, используется функция kbhit, которая возвращает 0, если клавиша не была нажата, и ненулевое значение, если нажата любая клавиша. Для того, чтобы определить код этой клавиши, надо вызвать функцию getch. Таким образом, цикл «пока не нажата клавиша» может выглядеть так: while ( ! kbhit() ) { ... } • для того, чтобы получить текущий цвет точки, используется функция getpixel. 1. Массивы Основные понятия Определение массива Основное предназначение компьютеров не вычисления, как считают многие, а обработка больших объемов данных. При размещении большого количества данных в памяти возникает такая проблема: надо научиться обращаться к каждой ячейке с данными отдельно. При этом очень сложно дать каждой ячейке собственное имя и при этом не запутаться. Выкручиваются из этой ситуации так: дают имя не ячейке, а группе ячеек, в которой каждая ячейка имеет номер.Такая область памяти называется массивом. Массив – это группа ячеек памяти одинакового типа, расположенных рядом и имеющих общее имя. Каждая ячейка в группе имеет уникальный номер. При работе с массивами надо научиться решать три задачи: • выделять память нужного размера под массив • записывать данные в нужную ячейку • читать данные из ячейки Объявление массива Чтобы использовать массив, надо его объявить – выделить место в памяти. Типом массива называется тип массива это тип входящих в него элементов. Массивы могут быть разных типов— int, float, char, и т.д. Массив объявляют так же, как и обычные переменные, но после имени массива в квадратных скобках записывается его размер. int A[10], B[20]; // 2 массива на 10 и 20 целых чисел float C[12]; // массив из 12 вещественных чисел При объявлении массива можно сразу заполнить его начальными значениями, перечисляя их внутри фигурных скобок: int A[4] = { 2, 3, 12, 76 }; Если в списке в фигурных скобках записано меньше чисел, чем элементов в массиве, то оставшиеся элементы заполняются нулями. Если чисел больше, чем надо, транслятор сообщает об ошибке. Например, int A[4] = { 2 }; // последние три элементы равны 0 Для повышения универсальности программы размер массива лучше определять через константу. В этом случае для переделки программы для массива другого размера надо только поменять значение этой константы:  В таблице показаны примеры правильного и неправильного объявления массива.  Обращение к элементу массива Каждый элемент массива имеет свой порядковый номер. Чтобы обратиться к элементу массива, надо написать имя массива и затем в квадратных скобках номер нужного элемента.Важно запомнить одно важное правило:Элементы массивов в языке Си нумеруются с нуля. Таким образом, если в массиве 10 элементов, он содержит элементы: A[0], A[1], A[2], ..., A[9] Номер элемента массива также называется его индексом. Вот примеры обращения к массиву A: x = (A[3] + 5)*A[1]; // прочитать значения A[3] и A[1] A[0] = x + 6; // записать новое значение в A[0] В языке Си не контролируется выход за границы массива, то есть формально вы можете записать что-то в элемент с несуществующим индексом, например в A[345] или в A[-12]. Однако при этом вы стираете какую-то ячейку в памяти, не относящуюся к массиву, поэтому последствия такого шага непредсказуемы и во многих случаях программа «зависает». Ввод с клавиатуры и вывод на экран Как же ввести данные в массив? Существует много способов в зависимости от вашей задачи: • элементы массива вводятся с клавиатуры вручную; • массив заполняется случайными числами (например, для моделирования случайных процессов); • элементы массива читаются из файла; • элементы массива поступают через порт с внешнего устройства (например, сканера, модема и т.п.); • массив заполняется в процессе вычислений. Задача. Ввести с клавиатуры массив из 10 элементов, умножить все элементы на 2 и вывести полученный массив на экран.К сожалению, невозможно просто сказать компьютеру: «введи массив A». Мы должны каждый элемент прочитать отдельно. Чтобы ввести массив в память, надо каждый его элемент обработать отдельно (например, вызвав для него функцию ввода scanf).Ввод с клавиатуры применяется в простейших программах, когда объем вводимой информации невелик. Для ввода массива будем использовать цикл for. Напомним, что массив надо предварительно объявить, то есть выделить под него память.Вводить можно столько элементов массива, сколько ячеек памяти выделено. Помните, что элементы массива нумеруются с нуля, поэтому если массив имеет всего 10 элементов, то последний элемент имеет номер 9. Если пытаться записывать в 10-ый элемент, произойдет выход за границы массива, и программа может работать неверно (а, возможно, и «зависнет»). При вводе массива желательно выдать на экран общую подсказку для ввода всего массива и подсказки для каждого элемента. Для умножения элементов массива на 2 надо снова использовать цикл, в котором за один раз обрабатывается 1 элемент массива.Вывод массива на экран выполняется также в цикле for. Элементы выводятся по одному.Если в конце строки-формата в операторе printf поставить пробел, то элементы массива будут напечатаны в строчку, а если символ \n – то в столбик.  Заполнение случайными числами Этот прием используется для моделирования случайных процессов, например, броуновского движения частиц. Пусть требуется заполнить массив равномерно распределенными случайными числами в интервале [a,b]. Поскольку для целых и вещественных чисел способы вычисления случайного числа в заданном интервале отличаются, рассмотрим оба варианта.Здесь и далее предполагается, что в начале программы есть строчка const int N = 10; Описание функции-датчика случайных чисел находится в заголовочном файле stdlib.h. Удобно также добавить в свою программу функцию random: int random (int N) { return rand() % N; } которая выдает случайные числа с равномерным распределением в интервале [0,N-1]. Как вы уже знаете из первой части курса, для получения случайных чисел с равномерным распределением в интервале [a,b] надо использовать формулу k = random ( b – a + 1 ) + a; Для вещественных чисел формула несколько другая: x = rand()*(b - a)/RAND_MAX + a; Здесь константа RAND_MAX – это максимальное случайное число, которое выдает стандартная функция rand. В приведенном ниже примере массив A заполняется случайными целыми числами в интервале [-5,10], а массив X – случайными вещественными числами в том же интервале.  Возможно, в этом примере не вполне ясно, зачем перед вызовом функции rand поставлено слово (float). Это связано с тем, что у нас a и b – целые числа. Результат функции rand –тоже целое число. Здесь возможны две проблемы: • При умножении результата функции rand на b-a может получиться очень большое число,которое не поместится в переменную типа int. • В языке Си при делении целого числа на целое остаток отбрасывается, поэтому при делении результат будет неверным. Когда массив заполняется случайными числами, обязательно вывести на экран исходный массив. Пример. Заполнить массив случайными целыми числами в интервале [-10,15], умножить все элементы на 2 и вывести на экран исходный массив и результат.  Работа с текстовыми файлами Наверняка при работе с предыдущими программами вы ощутили, что вводить с клавиату- ры большое количество данных очень утомительно, особенно если это надо делать много раз. В таких случаях создают файл на диске, в который записывают нужные данные, а программа сама читает данные из файла.Файлы бывают текстовые (в которых можно записывать только буквы, цифры, скобки и т.п.) и двоичные (в которых могут храниться любые символы из таблицы). В этом разделе мы рассмотрим только текстовые файлы. Как работать с файлами из программы Работа с файлами строит по принципу сэндвича:  Понятие «открыть файл» означает «начать с ним работу», сделать его активным и забло- кировать обращение других программ к этому файлу. При закрытии файла он освобождается(теперь с ним могут работать другие программы) и все ваши изменения вносятся на диск.Для работы с файлом используется специальная переменная, которая называется указателем на файл. Это адрес блока данных в памяти, в котором хранится вся информация об открытом файле. Объявляется указатель на файл так: FILE *fp; Чтобы открыть файл, надо вызвать функцию fopen, которая попытается открыть файл и записать его адрес в переменную fp. После этого все обращения к файлу выполняются не по имени файла, а через указатель fp. fp = fopen ( "qq.dat", "r" ); Здесь файл qq.dat из текущего каталога открывается для чтения (режим "r" во втором параметре функции fopen). Если надо, можно указать полный (или относительный) путь к файлу,например так: fp = fopen ( "c:\\data\\qq.dat", "r" ); Знак «наклонные черта» (слэш) в символьных строках всегда удваивается, потому что одиночный слэш – это специальный символ, например в сочетании \n. Кроме режима "r" (чтение из файла) есть еще несколько режимов: "r" Запись в новый файл. Если на диске уже есть файл с таким именем, он будет предварительно удален. "a" Добавление в конец файла. Если на диске уже есть файл с таким именем, новые данные дописываются в конец файла. Если такого файла нет, то он будет создан. "r+" Открыть существующий файл для изменения с возможностью записи и чтения "w+" Создание нового файла для записи и чтения (если файл с таким именем уже есть, он заменяется новым). Иногда программа не может открыть файл. Если файл открывается на чтение, это возможно в следующих случаях: • неверно задано имя файла или файла нет на диске; • файл используется другой программой и заблокирован. Если файл открывается на запись, операция может закончиться неудачно, если • на диске нет места; • файл защищен от записи; • неверно задано имя файла (например, оно содержит две точки, знак вопроса и т.п.). Если файл не удалось открыть, функция fopen возвращает специальное нулевое значение (нулевой указатель), который обозначается NULL. Поэтому надо всегда проверять правильностьоткрытия файла, особенно в режиме чтения. Если файл не был открыт, надо вывести сообщениеоб ошибке и выйти из программы. if ( fp == NULL ) { printf("Нет файла с данными"); return 1; // выход по ошибке, код ошибки 1 } Если файл открыт, можно читать из него данные. Для того используем функцию fscanf. Она полностью аналогична scanf, но служит для ввода из файла, а не с клавиатуры. Кроме того, ее первый параметр – указатель на файл, из которого читаются данные. n = fscanf ( fp, "%d", &A[i] ); Функция fscanf возвращает результат – количество чисел, которые ей удалось прочитать. Если мы запрашивали одно число, то значение переменой n может быть равно единице (если все нормально) или нулю (если данные закончились или ошибочные, например, вместо чисел введено слово). Для успешного чтения данные в файле должны отделяться пробелом или символом перехода на новую строчку (он вставляется в файл при нажатии на клавишу Enter). Если файл открыт на запись, можно записать в него данные с помощью.функции fprintf, которая полностью аналогична printf.Когда работа с файлом закончена, надо закрыть его, вызвав функцию fclose: fclose ( fp ); После этого указатель fp свободен и его можно использовать для работы с другим файлом. Массивизвестного размера Пример. Ввести массив из 10 целых чисел из файла input.dat, умножить каждый элемент на 2 и вывести в столбик в файл output.dat. Эта задача решается с помощью функций fopen, fscanf, fprintf и fclose, описанных выше. В программе обрабатываются две ошибки: • файла нет (его не удалось открыть); • в файле мало данных или данные неверные (например, слова вместо целых чисел).  В отличие от предыдущих, эта программа выдает результаты не на экран, а в файл output.dat в текущем каталоге. Массив неизвестного размера Прмер. В файле input.dat записаны в два столбика пары чисел (x,y). Записать в файл output.dat в столбик суммы x+y для каждой пары.Сложность этой задачи состоит в том, что мы не можем прочитать все данные сразу в память,обработать их и записать в выходной файл. Не можем потому, что не знаем, сколько пар чисел в массиве. Конечно, если известно, что в файле, скажем, не более 200 чисел, можно выделить массив «с запасом», прочитать столько данных, сколько нужно, и работать только с ними. Однако в файле могут быть миллионы чисел и такие массивы не поместятся в памяти. Однако, если подумать, становится понятно, что для вычисления суммы каждой пары нужны только два числа, а остальные мы можем не хранить в памяти. Когда вычислили их сумму, ее также не надо хранить в памяти, а можно сразу записать в выходной файл. Поэтому будем использовать такой алгоритм: 1) открыть два файла, один на чтение (с исходными данными), второй – на запись; 2) попытаться прочитать два числа в переменные x и y; если это не получилось (нет больше данных или неверные данные), закончить работу; 3) сложить x и y и записать результат в выходной файл; 4) перейти к шагу 2. Для того, чтобы определить, удачно ли закончилось чтение, мы будем использовать тот факт,что функция fscanf (как и scanf) возвращает количество удачно считанных чисел. За один раз будем читать сразу два числа, x и y. Если все закончилось удачно, функция fscanf возвращает значение 2 (обе переменных прочитаны). Если результат этой функции меньше двух,данные закончились или неверные. Заметим, что надо работать одновременно с двумя открытыми файлами, поэтому в памяти надо использовать два указателя на файлы, они обозначены именами fin и fout. Для сокращения записи ошибки при открытии файлов не обрабатываются.  Работа с двоичными файлами Двоичные файлы отличаются от текстовых тем, что в них записана информация во внут- реннем машинном представлении. Двоичный файл нельзя просмотреть на экране (вернее, можно просмотреть, но очень сложно понять). Но есть и преимущества – из двоичных файлов можно читать сразу весь массив в виде единого блока. Также можно записать весь массив или его любой непрерывный кусок за одну команду. При открытии двоичного файла вместо режимов "r", "w" и "a" используют соответст- венно "rb", "wb" и "ab". Дополнительная буква "b" указывает на то, что файл двоичный(от английского слова binary – двоичный). Приведем решение одной задачи, которую мы уже разбирали ранее. Пример. Ввести массив из 10 целых чисел из двоичного файла input.dat, умножить каждый элемент на 2 и вывести в двоичный файл output.dat.э   Для чтения из двоичного файла используется функция fread, которая принимает 4 пара- метра: • адрес области в памяти, куда записать прочитанные данные (в данном случае это адрес первого элемента массива A, который обозначается как &A[0] или просто A); • размер одного элемента данных (лучше сделать так, чтобы машина сама определила его, например, в нашем случае – sizeof(int) – размер целого числа. Хотя в Dev- C++ целое число занимает 4 байта, в в других системах программирования это может быть не так; наша программа будет работать и в этом случае, то есть станет переносимой на другую платформу; • количество элементов данных в массиве (N); • указатель на открытый файл, откуда читать данные (fp). Функция fread возвращает количество успешно прочитанных элементов массива – ее возвращаемое значение можно использовать для обработки ошибок. Если функция fread вернула значение, меньшее, чем N, в файле не хватает данных. Для записи массива в двоичный файл используется функция fwrite с такими же параметрами; она возвращает количество успешно записанных элементов. Преимущество этого способа состоит в том, что массив читается и записывается сразу единым блоком. Это значительно увеличивает скорость записи на диск (в сравнении с выводом в текстовый файл отдельно каждого элемента). Простой поиск в массиве Во многих задачах требуется последовательно перебрать все элементы массива и найти нужные нам. Мы рассмотрим четыре таких задачи: • поиск одного заданного элемента; • вывод всех элементов, которые удовлетворяют заданному условию; • формирование нового массива из всех отобранных элементов; • поиск минимального (максимального) элемента. Все эти задачи решаются с помощью цикла, в котором перебираются все элементы массива от начального (0-ого) до конечного (N-1-ого) элемента. Такой поиск называется линейным, поскольку все элементы просматриваются последовательно один за другим. Поиск одного элемента Пример. Определить, есть ли в массиве элемент с заданным значением x, и, если он есть, найти его номер. Если нет никакой информации о расположении элементов массива, то применяется линейный поиск, основная идея которого – последовательно просматривать массив, пока не будет обнаружено совпадение или не будет достигнут конец массива. Это реализует следующая простая программа:  Чтобы определить ситуацию, когда элемент не найден, нам надо ввести специальную переменную success, которая устанавливается в 1, если элемент найден, и остается равной нулю, если в массиве нет нужного элемента. Такая переменная называется флагом, флаг может быть установлен (равен 1) или сброшен (равен нулю). Для линейного поиска в худшем случае мы имеем N сравнений. Понятно, что для ускорения поиска надо сначала как-то упорядочить данные, в этом случае можно сделать поиск эффективным. Поиск всех элементов, соответствующих условию Пример. Определить, сколько в массиве положительных элементов и вывести их на экран.Для решения этой задачи вводим счетчик – специальную переменную, значение которой будет увеличиваться на единицу, когда мы нашли очередной положительный элемент.   Для чтения из двоичного файла используется функция fread, которая принимает 4 пара- метра: • адрес области в памяти, куда записать прочитанные данные (в данном случае это адрес первого элемента массива A, который обозначается как &A[0] или просто A); • размер одного элемента данных (лучше сделать так, чтобы машина сама определила его, например, в нашем случае – sizeof(int) – размер целого числа. Хотя в Dev- C++ целое число занимает 4 байта, в в других системах программирования это может быть не так; наша программа будет работать и в этом случае, то есть станет переносимой на другую платформу; • количество элементов данных в массиве (N); • указатель на открытый файл, откуда читать данные (fp). Функция fread возвращает количество успешно прочитанных элементов массива – ее возвращаемое значение можно использовать для обработки ошибок. Если функция fread вернула значение, меньшее, чем N, в файле не хватает данных. Для записи массива в двоичный файл используется функция fwrite с такими же параметрами; она возвращает количество успешно записанных элементов. Преимущество этого способа состоит в том, что массив читается и записывается сразу единым блоком. Это значительно увеличивает скорость записи на диск (в сравнении с выводом в текстовый файл отдельно каждого элемента). Простой поиск в массиве Во многих задачах требуется последовательно перебрать все элементы массива и найти нужные нам. Мы рассмотрим четыре таких задачи: • поиск одного заданного элемента; • вывод всех элементов, которые удовлетворяют заданному условию; • формирование нового массива из всех отобранных элементов; • поиск минимального (максимального) элемента. Все эти задачи решаются с помощью цикла, в котором перебираются все элементы массива от начального (0-ого) до конечного (N-1-ого) элемента. Такой поиск называется линейным, поскольку все элементы просматриваются последовательно один за другим. Поиск одного элемента Пример. Определить, есть ли в массиве элемент с заданным значением x, и, если он есть, найти его номер.Если нет никакой информации о расположении элементов массива, то применяется линейный поиск, основная идея которого – последовательно просматривать массив, пока не будет обнаружено совпадение или не будет достигнут конец массива. Это реализует следующая простая программа:  Чтобы определить ситуацию, когда элемент не найден, нам надо ввести специальную переменную success, которая устанавливается в 1, если элемент найден, и остается равной нулю, если в массиве нет нужного элемента. Такая переменная называется флагом, флаг может быть установлен (равен 1) или сброшен (равен нулю). Для линейного поиска в худшем случае мы имеем N сравнений. Понятно, что для ускорения поиска надо сначала как-то упорядочить данные, в этом случае можно сделать поиск эффективным. Поиск всех элементов, соответствующих условию Пример. Определить, сколько в массиве положительных элементов и вывести их на экран. Для решения этой задачи вводим счетчик – специальную переменную, значение которой будет увеличиваться на единицу, когда мы нашли очередной положительный элемент.  Формирование массива по заданному условию Пример. Сформировать новый массив B, включив в него все положительные элементы исходного массива A, и вывести его на экран. Пусть есть массив A[N]. Надо выбрать из него все положительные элементы и записать их в новый массив, который и будет дальше использоваться.Сначала надо определить, сколько места в памяти надо выделить для массива B. В «худшем» случае все элементы в массиве A будут положительными и войдут в массив B, поэтому массив B должен иметь такой же размер, что и массив A.Можно предложить такой способ: просматривать весь массив A, и если для очередного элемента A[i]>0, его значение копируется в B[i].  Однако в этом случае использовать такой массив B очень сложно, потому что нужные элементы стоят не подряд.Есть более красивый способ. Объявляем временную переменную-счетчик count, в которой будем хранить количество найденных положительных элементов. Сначала она равна нулю.Если нашли очередной положительный элемент, то ставим его в ячейку B[count] и увеличиваем счетчик. Таким образом, все нужные элементы стоят в начале массива B.  Минимальный элемент Пример. Найти и вывести на экран минимальный элемент в массиве A. Для решения задачи надо выделить в памяти ячейку (переменную) для хранения найденного минимального значения. Сначала мы записываем в эту ячейку первый элемент (A[0]). Затем берем следующий элемент и сравниваем его с минимальным. Если он меньше минимального, записываем его значение в ячейку минимального элемента. И так далее. Когда мы рассмотрим последний элемент в массиве, в дополнительной ячейке памяти будет минимальное значение из всех элементов массива. Заметим, что перебор в цикле начинается с элемента с номером 1 (а не 0), поскольку начальный элемент мы рассмотрели отдельно.  Чтобы найти максимальный элемент, достаточно изменить условие в заголовке условного оператора на обратное (A[i] > min). Конечно, вспомогательную переменную в этом случае лучше(но не обязательно!) назвать max. Теперь можно усложнить задачу и найти еще и номер минимального элемента. Пример. Найти и вывести на экран минимальный элемент в массиве A и его номер. Напрашивается такое решение: завести еще одну переменную, в которой хранить номер минимального элемента. Если мы нашли новый минимальный элемент, то в одну переменную записали его значение, а во вторую – его номер.Тем не менее, можно обойтись одной дополнительной переменной. Дело в том, что по номеру элемента можно легко найти его значение в массиве. На этом основана приведенная ниже программа. Теперь мы запоминаем (в переменной nMin) не значение минимального элемента, а только его номер.  Перестановка элементов массива О кувшине и вазе Представьте, что в вазе для цветов налито молоко, а в кувшине – вода с удобрениями. Как привести все в порядок? Надо использовать третью емкость такого же (или большего) объема.Сначала переливаем в нее воду из кувшина (или молоко из вазы, все равно), затем в пустой кувшин переливаем молоко (или в вазу – воду), а затем из третьей емкости переливаем воду в вазу (или, соответственно, молоко в кувшин).Так же и в программировании: чтобы поменять местами значения двух ячеек в памяти, надо использовать временную переменную1. Пусть даны ячейки a и b, содержащие некоторые значения. После выполнения следующих команд их значения поменяются:  Эта цепочка операторов присваивания особая: • она начинается и заканчивается временной переменной c; • следующий оператор начинается с той переменной, на которую закончился предыдущий Перестановка наоборот (инверсия) Инверсия (от английского inverse – обратный) – это такая перестановка, когда первый элемент становится последним, второй – предпоследним и т.д.  Эта простая задача имеет один подводный камень. Пусть размер массива N. Тогда элемент A[0] надо переставить с A[N-1], A[1] с A[N-2] и т.д. Заметим, что в любом случае сумма индексов переставляемых элементов равнаN-1, поэтому хочется сделать цикл от 0 до N-1, в котором переставить элементы A[i] с A[N-1-i]. Однако при этом вы обнаружите, что массив не изменился. Обратим внимание, что перестановка затрагивает одновременно и первую, и вторую половину массива. Поэтому сначала все элементы будут переставлены правильно, а затем (когдаi> N/2) будут возвращены на свои места. Правильное решение – делать перебор, при котором переменная цикла доходит только до середины массива.  Циклический сдвиг При циклическом сдвиге (вправо) первый элемент переходит на место второго, второй на место третьего и т.д., а последний элемент – на место первого.  Для выполнения циклического сдвига нам будет нужна одна временная переменная – в ней мы сохраним значение последнего элемента, пока будем переставлять остальные. Обратите внимание, что мы начинаем с конца массива, иначе массив просто заполнится первым элементом. Первый элемент ставится отдельно – копированием из временной переменной.  Сортировка массивов Сортировка – это расстановка элементов некоторого списка в заданном порядке. Существуют разные виды сортировки (по алфавиту, по датам и т.д.), они отличаются лишь процедурой сравнения элементов. Мы рассмотрим простейший вариант сортировки – расстановку элементов массива в порядке возрастания.Программисты придумали множество методов сортировки. Они делятся на две группы: • понятные, но не эффективные • эффективные, но непонятные (быстрая сортировка и т.п.). Пока мы будем изучать только методы из первой группы, которых хватает для простых задач(когда размер массива не более 1000). Метод пузырька Название этого метода произошло от известного физического явления – пузырек воздуха в воде поднимается вверх. В этом методе сначала поднимается «наверх» (к началу массива) самый «легкий» элемент (минимальный), затем следующий и т.д. Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно, то меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать  При следующем проходе наша задача – поставить на место элемент A[1]. Делаем это так же,но уже не рассматриваем A[0], который стоит на своем месте. Сделав N-1 проходов, мы установим на место элементы с A[0] по A[N-2]. Это значит, что последний элемент, A[N-1], уже тоже стоит на своем месте (другого у него нет).  Метод пузырька работает медленно, особенно на больших массивах. Можно показать, что при увеличении размера массива в 10 раз время выполнения программы увеличивается в 100 раз(метод имеет порядок N2). К сожалению, все простые алгоритмы сортировки имеют такой(квадратичный) порядок. Метод выбора минимального элемента Еще один недостаток метода пузырька состоит в том, что приходится слишком часто переставлять местами соседние элементы. Этого можно избежать, если использовать метод выбора минимального элемента. Он заключается в следующем. Ищем в массиве минимальный элемент и ставим его на первое место. Затем из оставшихся элементов также ищем минимальный и ставим на следующее место и т.д.В сравнении с методом пузырька, этот метод требует значительно меньше перестановок элементов (в худшем случае N-1). Он дает значительный выигрыш, если перестановки сложны и занимают много времени.-  Двоичный поиск в массиве Пусть элементы массива A уже расставлены по возрастанию и требуется найти элемент, равный x, среди элементов с номерами от L до R.. Для этого использую следующую идею: выбираем средний элемент между L и R , он имеет номер m=(L+R)/2, где деление выполняется нацело. Сравним его с искомым x. Если он равен x, мы нашли то, что искали. Если x меньше A[m], надо искать дальше между A[L] и A[m], если x больше A[m], дальше ищем между A[m] и A[R].  Переменная flag служит для того, чтобы определить, нашли мы нужный элемент или нет. Если нашли элемент, равный x, надо присвоить этой переменной значение 1 и выйти из цикла.При этом в переменной m остается номер найденного элемента. Если массив маленький, то скорость двоичного поиска незначительно отличается от ли- нейного. Представим себе, что размер массива — 1000000 элементов и нужный нам элемент стоит в конце массива (это самый худший вариант для линейного поиска).  поскольку число операций возрастает как логарифм N, то есть медленнее, чем увеличивается размер массива. Его недостатком является то, что элементы должны быть заранее отсортированы. Двоичный поиск используется при поиске информации в больших базах данных. Массивы в процедурах и функциях Массивы, так же как и простые переменные, можно передавать в процедуры и функции в качестве параметров. Рассмотрим, например, функцию, вычисляющую сумму элементов массива. Желательно сделать ее так, чтобы в нее можно было передавать массивы любого размера, и она всегда правильно вычисляла результат. Для этого функция должна знать (или определить)размер массива. В языке Си функции не могут самостоятельно определять размер массива, поэтому он должен быть обязательно одним из параметров.  Обратите внимание, что в заголовке функции размер массива указан отдельно, нельзя объявлять массив-параметр как A[N], а только как A[]. С другой стороны такая запись возможна только в заголовках функций, поскольку при этом не надо выделять новую память под массив.Объявлять локальный или глобальный массив, не указав явно его размер, нельзя.Для вызова приведенной функции в параметрах надо указать название массива (без скобок) и его размер.  2. Символьные строки ��Что такое символьная строка? Понятно, что символьная строка – это последовательность символов. Мы будем рассмат- ривать строки, в которых на каждый символ отводится 1 байт. В этом случае можно использовать 28=256 различных символов. Каждый символ имеет свой код (от 0 до 255), эти коды определяются по специальной таблице. Строка, как и другие переменные, записывается в память, причем компьютеру все равно, какие данные записаны – для него это набор байтов. Как же определить, где заканчивается строка? Есть два решения: 1) хранить длину строки в отдельной ячейке (как в языке Паскаль); 2) выбрать один особый символ, который будет обозначать конец строки, причем в середине строки этот символ не может встречаться. В языке Си принят второй подход. Символьная строка – это последовательность символом, которая заканчивается символом с кодом 0. Символ с кодом ноль не имеет никакого изображения, в программе его записывают как '\0'. Символ с кодом ноль (обозначается как '\0') и цифра ноль (обозначается '0', имеет код 48) – это два разных символа. Объявление и инициализация Строка представляет собой массив символов, поэтому и объявляется она именно как массив: char s[80]; Однако строка отличается от массива тем, что она заканчивается символом с кодом 0 – признаком окончания строки, поэтому Если массив символов будет использоваться как строка, надо выделять на 1 байт больше памяти.При выделении памяти глобальные переменные заполняются нулями, а локальные содержат«мусор». Начальное значение строки можно задать при объявлении в двойных кавычках после знака равенства: char s[80] = "Привет, Вася!"; Символы в кавычках будут записаны в начало массива s, а затем – признак окончания строки '\0'. Оставшиеся символы не меняются, и в локальных строках там будет «мусор». Можно написать и так char s[] = "Привет, Вася!"; В этом случае компилятор подсчитает символы в кавычках, выделит памяти на 1 байт больше и занесет в эту область саму строку и завершающий ноль. Аналогично можно выделить память на указатель: char *s = "Привет, Вася!";__ Результат – тот же самый, что и в предыдущем случае, но теперь s – это указатель (переменная, в которой хранится адрес ячейки в памяти), и с ним можно работать так же, как с обычным указателем (присваивать, изменять и т.п.). Если строка не будет изменяться во время работы программы, то можно объявить константу (постоянную строку) так: const char PRIVET[] = "Привет, Вася!"; Стандартный ввод и вывод Для ввода и вывода строк с помощью функций scanf и printf используется специальный формат"%s": #include main() { char Name[50]; printf("Кактебязовут? "); scanf("%s", Name); printf("Привет, %s!", Name); } Заметьте, что в функцию scanf надо передать просто имя строки (без знака &), ведь имя массива является одновременно адресом его начального элемента. Однако у функции scanf есть одна особенность: она заканчивает ввод, встретив первый пробел. Если вы на вопрос в предыдущем примере ввели "Вася Пупкин", то увидите надпись "Привет, Вася!" вместо ожидаемого"Привет, Вася Пупкин!". Если надо ввести всю строку целиком, включая пробелы (то есть до нажатия на клавишу Enter), придется делать иначе, заменив вызов scanf на более простой: gets ( s ); Название этой функции происходит от английских слов get string – получить строку. Для вывода строки на экран можно (кроме printf) использовать и функцию puts, которая после вывода строки еще и дает команду перехода на новую строку. В примере значение строки Name будет напечатано на следующей строчке экрана. #include main() { char Name[50] = "Вася!"; puts( "Привет," ); puts ( Name ); } Пример. Ввести символьную строку и заменить в ней все буквы 'A' на буквы 'Б'. Будем рассматривать строку как массив символов. Надо перебрать все элементы массива, пока мы не встретим символ '\0' (признак окончания строки) и, если очередной символ – это буква 'A', заменить его на 'Б'. Для этого используем цикл while, потому что мы заранее не знаем длину строки. Условие цикла можно сформулировать так: «пока не конец строки».  Заметьте, что Одиночный символ записывается в апострофах, а символьная строка – в кавычках. При выводе строк с помощью функции printf часто применяется форматирование. После знака % в формате указывается размер поля для вывода строки. Перед этим числом можно также поставить знак минус, что означает «прижать к левому краю поля».  Работа с файлами В реальной ситуации требуется обрабатывать очень много строк, которые чаще всего на- ходятся в файле, причем их количество заранее неизвестно. Однако, если для обработки одной строки нам не требуется знать остальные, можно использовать способ, который мы применяли при работе с массивами данных неизвестного размера. В данном случае мы будем читать очередную строку из файла, обрабатывать ее и сразу записывать в выходной файл (если это требуется). Работа с файлами имеет несколько особенностей. Во-первых, для чтения строки можно использовать функцию fscanf. Однако эта функция читает только одно слово и останавливается на первом пробеле. Поэтому функция fscanf применяется тогда, когда надо читать файл по словам.Вот пример чтения слова из открытого файла с указателем fp:  Если надо читать всю строку с пробелами, используют функцию fgets. Она принимает три параметра: • имя символьной строки, в которую записать данные; • максимальную длину этой строки; функция не допускает выхода за границы строки; если строка в файле длиннее, чем можно записать в память, читается только начальная |