- •1) Базовые элементы языка с. Алфавит и словарь языка (в1б1, в3б3)
- •2) Основные типы данных. Классификация их типов. Модификация базовых типов. (в1б2, в3б17)
- •3) Константы (в1б3, в3б2)
- •4) Переменные (в1б4, в3б16)
- •5) Структура с-программы. Понятие локальных и глобальных переменных. Функция main(). Директивы препроцессора (# include и #define). Комментарии. (в1б5, в3б1)
- •6) Операции языка с. Арифметические, логические операции. Поразрядные операции. (в1б6, в3б15)
- •7. Операции языка с. Операция присваивания и отношения. Операция определения размера. Оператор последовательного вычисления. (в1б7, в2б30)
- •8. Операции языка с. Условная операция. Операция (), операция []. (в1б8, в3б14)
- •9) Приоритет операций и порядок вычислений (в1б9, в2б29)
- •10) Основные сведения о вводе-выводе. (в1б10, в3б13)
- •11) Ввод-вывод символов (в1б11, в2б28)
- •12) Форматированный ввод-вывод. Модификаторы формата. Спецификаторы преобразования. Подавление ввода. (в3б12, в1б12)
- •13) Операторы языка с. Условные операторы (if, switch). (в1б13, в2б27)
- •14) Операторы цикла (while, for, do while )(в1б14, в3б11)
- •15) Операторы безусловного перехода ( break, continue, go to, return) (в1б15, в2б26)
- •16) Одномерные массивы. (в1б16, в3б10)
- •17) Строковый литерал. Чтение и запись строк. (в1б17, в2б25)
- •18)Двухмерные массивы. Массивы строк (в1б18, в3б9)
- •19) Инициализация массива. (в1б19, в2б24)
- •20) Способы доступа к элементом массива. (в1б20, в3б8)
- •22) Указательные переменные. Операции получения адреса (&) и раскрытие ссылка (*) (в1б22, в3б7)
- •23) Указательные выражения. Адресная арифметика. (в1б23, в2б22)
- •24) Связь массивов и указателей (в1б24,в3б6)
- •25) Функции динамического распределения памяти (в1б25, в2б21)
- •26) Динамическое выделение памяти для массивов. (в1б26, в3б5)
- •27) Функции. Определения функций. Оператор return.( в1б27, в3б20)
- •28) Функции. Прототипы функции. (в1б28, в3б4)
- •29) Функции. Вызов функций: вызов по значению и по ссылке. (в1б29, в2б19)
- •30) Передача массива в функцию. (в1б30, в3б27)
- •31) Классы памяти. Область видимости. (в2б1, в3б28)
- •32) Аргумент функции main(): argv и argc (в2б2, в3б26)
- •33) Рекурсия. (в2б3, в3б29)
- •34) Вызов библиотечных функций(в2б4, в3б25)
- •35) Директива препроцессора #define: создание макрофункций с помощью директивы #define (в2б5, в3б30)
- •36) Директивы условной компиляции #if, #else, #elif, #endif, #ifdef, #ifndef (в2б6, в3б24)
- •37) Понятие структуры. Доступ к членом структуры (в2б7)
- •38) Присваивание структур (в2б8, в3б23)
- •39) Массивы структуры(в2б9)
- •40) Передача членов структур функциям. Передача целых структур функциям. (в2б10, в3б22)
- •41) Указатели на структуры. Средство typedef (в2б11)
- •42) Понятие объединение и перечисления. Битовые поля. (в2б12,в3б21)
- •44) Методы поиска: последовательный и двоичный поиск. (в2б14, в3б20)
- •45) Основы файловой системы. Стандартные потоки. Указатель файла. Открытые файлы. Закрытые файлы. (в2б15)
- •46) Форматированный ввод-вывод в файл (в2б16, в2б17, в3б19)
- •48) Понятие очереди, стеков, связанных списков и деревьев. (в2б12, в3б18)
42) Понятие объединение и перечисления. Битовые поля. (в2б12,в3б21)
Понятия объединения и перечисления
Объединение подобно структуре, однако в каждый момент времени может использоваться (или другими словами быть ответным) только один из элементов объединения. Тип объединения может задаваться в следующем виде:
union { описание элемента 1;
...
описание элемента n; };
Главной особенностью объединения является то, что для каждого из объявленных элементов выделяется одна и та же область памяти, т.е. они перекрываются. Хотя доступ к этой области памяти возможен с использованием любого из элементов, элемент для этой цели должен выбираться так, чтобы полученный результат не был бессмысленным.
Доступ к элементам объединения осуществляется тем же способом, что и к структурам. Тег объединения может быть формализован точно так же, как и тег структуры.
Объединение применяется для следующих целей:
- инициализации используемого объекта памяти, если в каждый момент времени только один объект из многих является активным;
- интерпретации основного представления объекта одного типа, как если бы этому объекту был присвоен другой тип.
Память, которая соответствует переменной типа объединения, определяется величиной, необходимой для размещения наиболее длинного элемента объединения. Когда используется элемент меньшей длины, то
переменная типа объединения может содержать неиспользуемую память. Все элементы объединения хранятся в одной и той же области памяти, начиная с одного адреса.
Пример:
union {
char fio[30];
char adres[80];
int vozrast;
int telefon; } inform;
union {
int ax;
char al[2]; } ua;
При использовании объекта infor типа union можно обрабатывать только тот элемент который получил значение, т.е. после присвоения значения элементу inform.fio, не имеет смысла обращаться к другим элементам. Объединение ua позволяет получить отдельный доступ к младшему ua.al[0] и к старшему ua.al[1] байтам двухбайтного числа ua.ax .
Битовые поля
Элементом структуры может быть битовое поле, обеспечивающее доступ к отдельным битам памяти. Вне структур битовые поля объявлять нельзя. Нельзя также организовывать массивы битовых полей и нельзя применять к полям операцию определения адреса. В общем случае тип структуры с битовым полем задается в следующем виде:
struct { unsigned идентификатор 1 : длина-поля 1;
unsigned идентификатор 2 : длина-поля 2; }
Длинна - поля задается целым выражением или константой. Эта константа определяет число битов, отведенное соответствующему полю. Поле нулевой длинны обозначает выравнивание на границу следующего слова.
Пример:
struct { unsigned a1 : 1;
unsigned a2 : 2;
unsigned a3 : 5;
unsigned a4 : 2; } prim;
Структуры битовых полей могут содержать и знаковые компоненты. Такие компоненты автоматически размещаются на соответствующих границах слов, при этом некоторые биты слов могут оставаться неиспользованными.
Ссылки на поле битов выполняются точно так же, как и компоненты общих структур. Само же битовое поле рассматривается как целое число, максимальное значение которого определяется длиной поля.
43) Методы сортировки данных. Пузырьковая структура. Сортировка по средствам выбора. Сортировка вставками. Улучшенный алгоритм сортировки: сортировка Шелла, быстрая сортировка. Сортировка строк и структур. (В2Б13)
1.Пузырьковая сортировка
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=< K’1, K’2,...,K’n >, в котором для любого 1<=i<=n элемент K’ (i) <= K’(i+1). При обменной сортировке упорядоченный список В’ получается из В систематическим обменом пары рядомстоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
Пример:
B=<20,-5,10,8,7>, исходный список;
B1=<-5,10,8,7,20>, первый просмотр;
B2=<-5,8,7,10,20>, второй просмотр;
B3=<-5,7,8,10,20>, третий просмотр.
В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.
Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.
/* сортировка пузырьковым методом */
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);}
Пузырьковая сортировка выполняется при количестве действий Q=(n-m)*(n-m) и не требует дополнительной памяти.
2.Сортировка посредством выбора
Упорядоченный список В’ получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В’, который первоначально должен быть пустым.
Функция select упорядочивает массив s сортировкой посредством выбора.
/* сортировка методом выбора */
double *select( double *s, int m, int n)
{
int i,j;
int imin,c;
for(i=m;i< n;i++){ //для каждого элемента
//ищем минимальный элемент в оставшейся части массива
imin=s[i];
for (j=i; j< n;j++) if(s[j]< s[imin]) imin=j;
//меняем текущий элемент с минимальным
c=s[i];
s[i]=s[imin];
s[imin]=c; }
return(s); }
Здесь, как и в предыдущем примере оба списка В и В’ размещаются в разных частях массива s. При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.
Сортировка вставками
Упорядоченный массив B’ получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B’ так, что B’ остается упорядоченным списком длины i.
Функция insert реализует сортировку вставкой.
/* сортировка методом вставки */
int *insert(int *s, int m, int n){
int i,j,k;
int aux;
for (i=m+1; i< n; i++){ //для каждого элемента массива
aux=s[i]; //берем текущий элемент
//ищем место вставки и одновременно освобождаем его сдвигая элементы массива назад
for (k=i-1; k>=0 && s[k]>aux; k--) s[k+1]=s[k];
//вставляем элемент на найденное место
s[k+1]=aux; } return(a); }
Здесь оба списка В и В’ размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B’ - часть s c индексами от m до i-1.
При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.
4. Улучшенный алгоритм сортировки: быстрая сортировка, сортировка Шелла
Быстрая сортировка состоит в том, что список В=< K1,K2,...,Kn> реорганизуется в список B’,< K1 >, B", где В’ - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B’,< K1 >,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B’ и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками < и >.
Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B’ и В" приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов.
Рекурсивная функция quick упорядочивает участок массива s быстрой сортировкой.
Быстрая сортировка требует дополнительной памяти порядка log2(N) для выполнения рекурсивной функции quick (неявный стек).
Оценка среднего количества действий, необходимых для выполнения быстрой сортировки списка из N различных чисел, получена как оценка отношения числа различных возможных последовательностей из N различных чисел, равного N!, и общего количества действий C(N), необходимых для выполнения быстрой сортировки всех различных последовательностей. Доказано, что C(N)/N! < 2*N*ln(N).
Существенными в сортировках вставками являются затраты на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить погружение с большим шагом, сразу определяя элемент по мест. Этим отличается СОРТИРОВКА ШЕЛЛА: исходный массив разбивается на n частей, в каждую из которых попадают элементы с шагом m, начиная от 0,1,...,m-1 соответственно, то есть
0, m, 2m, 3m,...
1, m+1, 2m+1, 3m+1,...
2, m+2, 2m+2, 3m+2,...
Каждая часть сортируется отдельно с использованием алгоритма вставок. Затем выбирается меньший шаг, и алгоритм повторяется. Шаг может быть выбран равным степеням 2, например 64, 32, 16, 8, 4, 2, 1. Последняя сортировка выполняется с шагом 1.
3. Сортировка строк
#include
#include
#define MAXLINES 5000 // максимальное число строк
char *lineptr[MAXLINES]; // указатели на строки
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);
/* сортировка строк */
main() {
int nlines; /* количество прочитанных строк */
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort(lineptr, 0, nlines-1);
writelines(lineptr, nlines);
return 0; }
else {
printf("ошибка: слишком много строк\n");
return 1;} }