11.Основные методы сортировки: метод вставки

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

• сортируем первые два элемента

• смотрим третий элемент и вставляем его в нужную позицию по отношению к первым двум

Продолжаем процесс до конца сортируемого множества.

const int n=10;

int a[n], i, j;

...

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

{

x=a[i];

j=i-1;

while (j>=0 && a[j]>x)

{

a[j+1]=a[j];

j--;

}

a[j+1]=x;

}

12.Основные методы сортировки: метод выбора

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

const int n=10;

int a[n], i, j, imin;

...

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

{

imin=i;

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

if (a[j]<a[imin])

imin=j;

int t=a[i];

a[i]=a[imin];

a[imin]=t;

}

13.Поиск минимального и максимального элементов

const int n; // n - количество элементов в массиве

int a[100]; // a - массив целых чисел, максимальный размер 100 элементов

cin >> n;

for (int i = 0; i < n; i++) // ввод массива

cin >> a[i];

int m = a[0];

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

if (a[i] < m)

m = a[i];

cout << m; // вывод минимального значения

const int n; // n - количество элементов в массиве

int a[100]; // a - массив целых чисел, максимальный размер 100 элементов

cin >> n;

for (int i = 0; i < n; i++) // ввод массива

cin >> a[i];

int m = a[0];

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

if (a[i] > m)

m = a[i];

cout << m; // вывод максимального значения

14. Вставка и удаление элементов

Вставка:

const int maxn=10;

int a[maxn], n, x, k, i;

...

cin>>k;

//k – номер элемента, после которого будет производиться вставка нового элемента

cin>>x;

//x – значение нового элемента

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

a[i]=a[i-1];

a[k+1]=x;

Удаление:

const int maxn=10;

int a[maxn], n, k, i;

...

cin>>k; //номер элемента, который будет удален

for (i=k; i<n; i++)

{

a[i-1]=a[i];

}

15. Файлы произвольного и последовательного доступа. Работа с файлами в с

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

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

Примером последовательных файлов являются текстовые файлы (*.txt)

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

Файлы с последовательным доступом читаются от начала к концу, поэтому невозможно одновременно и считывать из них данные, и записывать таковые. Обычно информация из текстового файла считывается вся в память и сохраняется вся в файле после окончания работы с ней. Чтобы изменить одну запись файла последовательного доступа, его нужно весь записать заново. Если же приложению требуется частый доступ к данным, хранящимся в некотором файле, следует использовать файлы с произвольным доступом.

Работа с файлами в С:

Библиотека работы с файлами - <stdio.h>

FILE *f; - задание переменной файлового типа

fopen(“C:\\input.txt”,”wt”) – функция открытия файла, у неё два параметра:  первый -- это путь к файлу (строка), второй -- параметры открытия файла.

Параметры открытия файла состоят из двух частей: тип операции w – запись, r – чтение, a – дозапись, если к этим символам добавить знак «+», то тогда можно выполнять и противоположное действие (н-р r+ обозначает не только чтение, но и запись); тип файла t – текстовый файл, b – бинарный (двоичный) файл.

Закрывается файл с помощью функции fclose();

Запись текстовой строки в файл выполняет функция fprintf(): fprintf( имя-файловой-переменной, формат, список-переменных-для-вывода );

Для ввода данных (текстовой строки) используют функцию fscanf():

fscanf( файловая-переменная, формат-ввода, список-адресов-переменных );

функция feof(файловая-переменная) возвращает 1 (истинное значение), если файл, открытый для считывания, закончился. Она возвращает 0, если из файла еще можно продолжать ввод.