Int *ptr_a; char *ptr_ch, *ptr_var;
Для того чтобы с помощью указателя ptr_a работать с переменной a он должен указывать на адрес этой переменной. Это значит, что значение указателя ptr_a должно быть равно адресу переменной a. Здесь возникает две задачи: во-первых, необходимо определить адрес переменной, и, во-вторых, присвоить этот адрес указателю. Для определения адреса в языке С++ используется символ ‘&’ как показано ниже:
unsigned long ptr = &a;
В результате переменной ptr будет присвоен адрес переменной a. Аналогичным образом можно выполнить инициализацию указателя ptr_a:
ptr_a = &a; //инициализация указателя
По существу получается, что указатель это переменная, которая хранит адрес на заданную область памяти. Но в отличие от обычной переменной позволяет еще, и работать с данной областью, т.е. записывать в нее значения и считывать их. Допустим, что переменная a содержит число 10, а указатель ptr_a указывает на эту переменную. Тогда для того чтобы считывать и записывать значения переменной a с помощью указателя ptr_a используется следующая конструкция языка С:
int b = *ptr_a; //считывание значения переменной а *ptr_a = 20; //запись числа 20 в переменную а
Здесь переменной b присваивается значение переменной a через указатель ptr_a, а, затем, переменной a присваивается значение 20. Таким образом, для записи и считывания значений с помощью указателя необходимо перед его именем ставить символ ‘*’ и использовать оператор присваивания.
24. Какие алгоритмы сортировок массивов существует? Продемонстрируйте алгоритм сортировки массива методом выбора и приведите пример его реализации.
Быстрая и распределяющая сортировки, Сортировка списков путем слияния, Слияние списков, Сортировка посредством выбора, Пузырьковая сортировка, СОРТИРОВКА МЕТОДОМ ШЕЛЛА, Сортировка методом простого выбора (простой перебор), Сортировка методом простого включения
(сдвиг-вставка, вставками, вставка и сдвиг).
Сортировка выбором
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.
Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.
На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
#include<stdio.h>
#define N 10
void main()
{
long i,n, j, k;
int x,a[N];
scanf("%d", &n); // n -di engizemiz
for(i = 0 ; i < n; i++)
{ scanf("%d", &a[i]); // a[n] massivin engizemiz
}
for( i=0; i < n; i++) {
k=i; x=a[i];
for( j=i+1; j < n; j++) // minimaldik elementtin izdeu cikli
if ( a[j] < x ) {
k=j; x=a[j]; // k -shamalangan en kishi elementtin indeksi
}
a[k] = a[i]; a[i] = x; // kishi elementpen a[i]-din orndarin austramiz
printf("%d ",a[i]) ;}
}
25 Какие алгоритмы сортировок массивов существует? Продемонстрируйте алгоритм сортировки массива методом быстрой сортировки и приведите пример его реализации..
1.Пузырьковая сортировка Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
/* сортировка пузырьковым методом */
float * bubble(float * a, int m, int n)
{ char is=1;
int i;
float c;
while(is)
{ is=0;
for (i=m+1; i<=n; i++)
if ( a[i] < a[i-1] )
{ c=a[i];
a[i]=a[i-1];
a[i-1]=c;
is=1; } }
return(a); }
2. Сортировка вставкой Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i. Функция insert реализует сортировку вставкой.
/* сортировка методом вставки */
float *insert(float *s, int m, int n)
{int i,j,k;
float aux;
for (i=m+1; i<=n; i++)
{ aux=s[i];
for (k=m; k<=i && s[k]=k; j--) s[j+1]=s[j];
s[k]=aux; }
return(a);}
3. Сортировка посредством выбора Упорядоченный список В' получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В', который первоначально должен быть пустым.
Функция select упорядочивает массив s сортировкой посредством выбора.
/* сортировка методом выбора */
double *select( double *s, int m, int n)
{int i,j;
double c;
for (i=m; is[j])
{ c=s[i];
s[i]=s[j];
s[j]=c:}
return(s);}
4. Слияние списков
/* слияние списков */
double *merge(double *s, int low, int up, int l)
{double *b,*c,v;
int i,j,k;
b=calloc(l,sizeof(double));
c=calloc(up+1-l,sizeof(double));
for(i=low;i<low+l;i++)
b[i-low]=s[i];
for(i=0;i<up-l;i++)
c[i]=s[i+l+low];
v=(b[l]=(c[up-l]=(s[low+l-1]>s[up-1]) ?
(s[low+l-1]+1) : (s[up-1]+1)));
i=(j=0);
k=low;
while(b[i]<v||c[j]<v)
{ if(b[i]<c[j]) s[k]=b[i++];
else s[k]=c[j++]; k++; }
return (s); }
6. Быстрая сортировка Быстрая сортировка состоит в том, что список В=< K1,K2,...,Kn> реорганизуется в список B',< K1 >,B", где В' - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B',< K1 >,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B' и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками < и >.
Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.
/* быстрая сортировка */
double * quick(double *s,int low,int hi)
{ double cnt,aux;
int i,j;
if (hi>low)
{ i=low;
j=hi;
cnt=s[i];
while(i < j)
{ if (s[i+1]<=cnt)
{ s[i]=s[i+1];
s[i+1]=cnt; i++; }
else { if (s[j]<=cnt)
{ aux=s[j];
s[j]=s[i+1];
s[i+1]=aux; } j--; } }
quick(s,low,i-1);
quick(s,i+1,hi); }
return(s);}
26) Текстовый файл в языке Си. Библиотечные функции для работы с текстовыми файлами Пример использования
Включение файла Если функция задана как макроопределение, то можно директивой #include включить файл, содержащий ее определение. Часто подобные функции могут быть собраны в соответствующим образом названный заголовочный файл. Например, некоторые системы имеют файл ctype.h, содержащий макроопределения, задающие тип символа (прописная буква, цифра и т.д.) Включение библиотеки На некотором этапе компиляции или загрузки программы вы можете выбрать библиотеку. Даже система, которая автоматически контролирует свою стандартную библиотеку, может иметь другие библиотеки редко применяемых функций, и эти библиотеки следует запрашивать явно, указывая соответствующий признак во время компиляции. Очевидно, мы не сможем рассмотреть все особенности всех систем, но эти три примера показывают, что вас ожидает! Связь с файлами Один способ организации связи программы с файлом заключается в использовании операций переключения < и >. Этот метод прост, но ограничен. Язык Си предоставляет и более мощные методы связи с файлами. Рассмотрим использование функции fopen( ), которая открывает файл, затем применяются специальные функции ввода-вывода для чтения файла или записи в этот файл и далее используется функция fclose( ) для закрытия файла. Прежде чем исследовать эти функции, кратко познакомимся с сущностью файла. Файл является частью памяти, обычно на диске, со своим именем. Мы считаем, что он содержит некоторую полезную информацию. Для операционной системы файл более сложен, но это системные проблемы, а не наши. Но мы должны знать, что означает файл для программы на языке Си. В предлагаемых для обсуждения функциях, работающих с файлами, язык Си рассматривает файл как структуру. Вот типичный пример, взятый из IBM-версии компилятора Lattice C: struct_iobuf { char*_ptr; /* текущий указатель буфера*/ int_cnt; /* текущий счетчик байтов*/ char*_base; /* базовый адрес буфера ввода-вывода*/ char_flag; /* управляющий признак*/ char_file; /* номер файла*/ } #define FILE struct_iobuf /* краткая запись*/ Здесь мы не собираемся разбираться детально в этом определении. Главное состоит в том, что файл является структурой, и что краткое наименование шаблона - FILE. Многие системы используют директиву typedef для установления этого соответствия. Таким образом, программа, имеющая дело с файлами, будет использовать тип структуры FILE, чтобы делать так. Рассмотрим пример чтения содержимого файла, названного File, и вывода его на экран: #include <stdio.h> main( ) { FILE *in; /* описываем указатель на файл */ int ch; if ((in = fopen("File", "r") ) != NULL) { /*открываем File для чтения, проверяя существует ли он */ /* указатель FILE ссылается теперь на File */ while ((ch = getc(in) != EOF)) /* получаем символ из in*/ putc(ch, stdout); /* посылаем ch на стандартный вывод*/ fclose(in); /* закрываем фаил*. } else printf (" Файл не открывается\"File\".\n); } Объясним работу: fopen( ), fclose и использование функций ввода-вывода файла. Открытие файла: fopen( ) Функцией fopen( ) управляют три основных параметра. Первый - имя файла, который следует открыть. Он является и первым аргументом fopen( ). В нашем примере это "File". Второй параметр описывает, как должен использоваться файл: "r" - файл нужно считать, "w" - файл нужно записать, "a" - файл нужно дополнить. "w+" - новый текстовый файл открывается для записи и последующих многократных исправлений. Если файл уже существует, то предыдущее содержимое стирается. Последующие после открытия файла запись и чтение из него допустимы в любом месте файла, в том числе запись разрешена и в конце файла, т.е. файл может увеличиваться. "r+" - существующий текстовый файл открывается как для чтения, так и для записи в любом месте файла; однако в этом режиме невозможна запись в конец файла, то есть недопустимо увеличение размеров файла. "a+" - текстовый файл открывается или создается, если файла нет, и становится доступным для изменений, т.е. для записи и для чтения в любом месте; при этом в отличие от режима "w+"можно открыть существующий файл и не уничтожать его содержимое; в отличие от режима "r+" в режиме "a+" можно вести запись в конец файла, то есть увеличивать его размеры. Используемые коды являются строками, а не символьными константами. Некоторые системы предоставляют еще дополнительные возможности, которые мы здесь не будем рассматривать. Используемые коды являются строками, а не символьными константами. При применении "r" открывается существующий файл. При двух других применениях тоже будет открываться существующий файл, но если такого файла нет, он будет создан. Если вы используете "w" для существующего файла, то старая версия его стирается, и ваша программа начинает записывать на чистое место. Третий параметр является указателем на файл. Это значение возвращается самой функцией: FILE *in; in=fopen("File","r"); Теперь in является указателем на файл "File". С этого момента программа ссылается на файл при помощи указателя in, а не по имени File. (Файл stdio.h содержит строку FILE *fopen( ) Если fopen( ) не способна открыть требуемый файл, она возвращает значение NULL, определенное в stdio.h как 0.
Закрытие файла: fclose( ) В нашем примере показано, как нужно закрывать файл: fclose(in); Аргумент функции является указателем на файл. Для более серьезной программы нужно смотреть, успешно ли закрыт файл. Функция fclose( ) возвращает значение 0, если файл закрыт успешно, и -1 в противном случае. Текстовые файлы с буферизацией Функции fopen( ) и fclose( ) работают с текстовыми файлами с "буферизацией". Под буферизацией мы понимаем, что вводимые и выводимые данные запоминаются во временной области памяти, называемой буфером. Если буфер заполнился, содержимое его передается в блок, и процесс буферизации начинается снова. Одна из основных задач fclose( ) заключается в том, чтобы освободить любые частично заполненные буферы, если файл закрыт. Текстовым считается файл, в котором информация запоминается в виде символов в коде ASCII или аналогичном. Текстовый файл отличается от двоичного файла, который обычно используется для запоминания кодов машинного языка. Ввод-вывод текстового файла: getc( ), putc( ) Две функции getc( ) и putc( ) работают аналогично функциям getchar( ) и putchar( ) (описанным в предыдущих лекциях). Разница заключается в том, что вы должны сообщить, какой файл следует использовать. char ch; ch=getchar( ); предназначена для получения символа от стандартного ввода, а ch=getc(in); - для получения символа от файла, на который указывает in. putchar(ch); выводит символ на стандартный файл вывода. putc(ch,t); предназначена для записи символа ch в файл, на который ссылается указатель t типа FILE. Ввод-вывод файла: fprintf( ), fscanf( ), fgets( ), fputs( ) Все функции ввода-вывода, которые мы использовали в предыдущих лекциях, имеют аналоги для ввода-вывода файла. Основное отличие состоит в том, что нам нужно использовать указатель типа FILE , чтобы сообщить функциям с каким файлом им следует работать. Подобно getc( ) и putc( ) эти функции используются после функции fopen( ), открывающей файл, и перед fclose( ), закрывающей его. Функции fprintf( ) и fscanf( ) Эти функции ввода-вывода работают почти как printf( ) и scanf( ) (см. лекцию 4), но им нужен дополнительный аргумент для ссылки на сам файл. Он является первым в списке аргументов. Пример, иллюстрирующий обращение к этим функциям: #include<stdio.h> main( ) { FILE *fi; int age; fi=fopen("File","r"); /* считывание*/ fscanf(fi,"%d",&age); /* fi указывает на File */ fclose(fi); fi=fopen("Data", "a"); /*дополнение*/ fprintf(fi,"Data is %d.\n",age); /*fi указывает на Data*/ fclose(fi); } В отличие от getc( ) и putc( ) эти функции получают указатель типа FILE в качестве первого аргумента. Функция fgets( ) Эта функция имеет три аргумента, в то время как gets( ) имеет лишь один. Пример ее использования: /* Программа считывает файл строка за строкой */ #include<stdio.h> #define MAX 80 main( ) { FILE *f1; char *string[MAX] f1=fopen("File","r"); while (fgets(string,MAX,f1) != NULL) puts(string); }
27. Прототип функции. Библиотечные файлы. Директива препроцессора #include.
Прототипом функции в языке Си или C++ называется объявление функции, которое не содержит тело функции, но указывает имя функции, арность, типы аргументов и возвращаемый тип данных. В то время как определение функции описывает, что именно делает функция, прототип функции может восприниматься как описание её интерфейса.
В прототипе имена аргументов являются необязательными, тем не менее, необходимо указывать тип вместе со всеми модификаторами (например, указатель ли это или константный аргумент).
Пример
В качестве примера, рассмотрим следующий прототип функции:
int myFunction(int n);
Этот прототип объявляет функцию с именем «myFunction», которая принимает один аргумент «n» целого типа и возвращает целое число. Определение функции может располагаться где угодно в программе, но определение требуется только в случае её использования.
Библиотечные файлы. В командном языке предусмотрены некоторые дополнительные
возможности и удобства при работе с файлами. В частности, в нем
определен такой объект, как библиотечный файл. Внешне этот файл
подобен обычному файлу МС ДОС и с ним можно выполнять все обычные
действия, не затрагивающие (не изменяющие) внутреннее содержимое
файла (например, копирование, переименование, удаление). Однако
внутреннее его устройство более сложное, чем у обычного файла. Он
заключает в себе целый набор обычных файлов, которые записываются в
него последовательно друг за другом с некоторым "зазором". Кроме
того, в самом начале библиотечного файла отводится место под
каталог, в котором помимо имен составляющих его простых файлов
содержатся указания на их положение внутри библиотечного файла. Эти
простые файлы, являющиеся элементарными составляющими библиотечного
файла, называются объектами библиотечного файла.
Библиотечный файл может быть удобен при необходимости заведения
множества достаточно мелких файлов, имена которых будут слишком
загромождать каталог. Кроме того, библиотечный файл удобен при
необходимости выполнения каких-либо групповых операций над
множеством файлов. Например, поиск определенного контекста сразу во
многих файлах.
При каждом запуске компилятора сначала запускается препроцессор, который выполняет директивы начинающиеся с символа #. При выполнении этих команд создается временный файл исходного кода, с которым уже работает компилятор.
Директива #include
Строка #include "имя. файла " заменяет эту строку полным содержимым файла имя. файла. Если не указан путь то файл сначала ищется в директории исходного файла , затем в директории заданной в опциях компилятора(обычно директория Include). Строка #include <имя. файла> ищет файл только в директории заданной в опциях компилятора.
28 |
Описание массивов. Работа с массивами и их элементами. Связь массивов и указателей. Адресная арифметика; |
В языке C понятие массива тесно связано с понятием указателя. Действительно, как было описано выше, имя массива представляет собой адрес области памяти, распределенной под этот массив, или иными словами адрес первого элемента массива. Пусть описаны следующие данные:
int a[100], *pa;
и осуществлено присваивание:
pa = a;
Оно является корректным, поскольку имя a обозначает адрес первого элемента массива a и поэтому имеет тип указателя на int. После этого присваивания
pa[0] или *pa будет обозначать a[0];
pa[1] или *(pa+1) будет обозначать a[1];
pa[2] или *(pa+2) будет обозначать a[2] и т. д. И вообще обозначения вида *(pa+n) и pa[n] являются полностью эквивалентными. Точно также эквивалентны выражения *(a+i) и a[i].
На первый взгляд кажется, что массив и указатель полностью эквивалентны. Однако имеется два существенных отличия массива от указателя:
массиву при описании выделяется память для хранения всех его элементов, а указателю только для хранения адреса;
адрес массива навсегда закреплен за именем, то есть имя массива является адресной константой и выражение вида a = pa недопустимо.
Результат прибавления к указателю или вычитания из него целочисленной величины является указателем того же типа, значение которого отличается от значения исходного указателя на число байт, определяемое произведением целочисленной величины на размер данного, которое адресует указатель. Например, если имеются описания
int A[20], *pA = A;
double B[20], *pB = B;
то указатель (pA+3) будет иметь значение на 6 байт больше, чем pA, и будет адресовать элемент A[3] массива A. Указатель (pB+3) будет иметь значение на 24 байта больше, чем pB, и будет адресовать элемент B[3] массива B. С указателями типа void подобные операции выполнены быть не могут, поскольку компилятор не знает размера адресуемого данного.
Для указателей определены операции увеличения и уменьшения на целочисленную величину, как альтернативная форма записи выражений
pA = pA + i; эквивалентно pA += i;
pA = pA - i; эквивалентно pA -= i;
pA = pA + 1; эквивалентно pA++; или ++pA;
pA = pA - 1; эквивалентно pA--; или --pA; При этом, работа префиксных и постфиксных операций ++ и -- совпадает с их работой для арифметических данных.
Указатели допускается использовать в операциях сравнения. При этом всегда возможно сравнение указателя с нулем и сравнение двух однотипных указателей. Однако правильность результата последнего сравнения для 16-ти разрядного режима работы IBM PC гарантируется только в том случае, если сравниваемые указатели являются указателями на элементы одного и того же массива данных или если они предварительно подвергаются нормализации
Язык Си имеет средства работы непосредственно с областями оперативной памяти ЭВМ, задаваемыми их адресами (указателями). В языке C указатели строго типизированы, т. е. различают указатели (адреса) символьных, целых, вещественных величин, а также типов данных, создаваемых программистом.
Для описания указателя на какой-либо тип данных перед именем переменной ставится *. Например в строке
int *a, *b, c, d;
описываются два адреса и две переменные целого типа. В строке
double *bc;
описан адрес переменной вещественного типа. Никогда не следует писать знак * слитно с типом данных, например как в следующей строке:
int* a, b;
В этой строке создается ложное впечатление о том, что описаны два указателя на тип int, в то время как на самом деле описан один указатель на int, а именно a, и одна переменная типа int.
Описание переменных заставляет компилятор выделять память для хранения этих переменных. Описание указателя выделяет память лишь для хранения адреса. В этом смысле указатель на целое данное и на тип double будут занимать в ЭВМ одинаковое количество байт памяти, зависящее от модели памяти, на которую настроен компилятор. Например, в 16-ти разрядной Small модели длина указателя равна двум байтам, а в 16-ти разрядной Large модели - четырем.
При описании указателей в качестве имени типа данных можно использовать ключевое слово void, например
void *vd;
При таком описании с указателем не связывается никакой тип данных, то есть получаем указатель на данное произвольного типа.
Для указателей одного и того же типа допустимой является операция присваивания, кроме того указателю типа void может быть присвоено значение адреса данного любого типа, но не наоборот, например
int *a, *b;
double *d;
void *v;
...
a = b; /* Правильно */
v = a; /* Правильно */
v = d; /* Правильно */
b = v; /* Неправильно */
d = a; /* Неправильно */
В случае неправильного присваивания указателей компиляторы обычно выдают предупреждающие сообщения, которыми никогда не следует пренебрегать. Например, компилятор фирмы Borland выдает сообщение:
"Suspicious pointer conversion", которое переводится как "Подозрительное преобразование указателей".
Если по какой-либо причине необходимо выполнить операцию присваивания между указателями разного типа, то следует использовать явное преобразование типов, например для указателей из предыдущего примера
b = (int *) v;
d = (double *) a.