Типы данных: целый, вещественный, символьный. Размеры данных.

Исходные и объектные модули, процессы компиляции и связывания.

Исходный модуль (source code) – это текст программы на языке программирования.Объектный модуль (object code) – результат обработки компилятором исходного модуля. Объектный модуль не может быть выполнен. Это незавершенный вариант машинной программы. Исполняемый модуль создает компоновщик, объединяя в один общий модуль объектные модули, реализующие отдельные части алгоритма. На этом этапе к машинной программе подсоединяются необходимые функции стандартной библиотеки. Стандартная библиотека – набор программных модулей, выполняющих наиболее часто встречающиеся в программировании задачи: ввод, вывод данных, вычисление математических функций, сортировки и т.д. Есть два способа выполнения программы компилятором: она может быть подвергнута компиляции или интерпретации. Программа, написанная на любом языке программирования, может как компилироваться, так и интерпретироваться, однако многие языки изначально созданы для выполнения преимущественно одним из этих способов. И хотя интерпретаторы С существуют и доступны для программистов, С разрабатывался преимущественно для компиляции. В простейшем случае интепретатор читает исходный текст программы по одной строке за раз, выполняет эту строку и только после этого переходит к следующей. Компилятор читает сразу всю программу и конвертирует ее в объектный код, то есть транслирует исходный текст программы в форму, более пригодную для непосредственного выполнения компьютером. Объектный код также называют двоичным или машинным кодом. Когда программа скомпилирована, в ее коде уже нет отдельных строк исходного кода.В общем случае интерпретируемая программа выполняется медленнее, чем скомпилированная. Необходимо помнить, что компилятор преобразует исходный текст программы в объектный код, который выполняется компьютером непосредственно. Значит, потеря времени на компиляцию происходит лишь единожды, а в случае интерпретации – каждый раз при очередной интерпретации фрагмента программы в процессе ее выполнения. При вызове библиотечной фукнции компилятор “запоминает» ее имя. Потом компоновщик связывает код исходной программы с объектным кодом, уже найденным в стандартной библиотеке. Этот процесс называется компоновкой.

Алфавит языка Си.

Алфавит языка Си включает:

- прописные и строчные буквы латинского алфавита, а также знак подчеркивания (код ASCII 95);

- арабские цифры от 0 до 9;

- специальные символы:

+(плюс) –(минус) *(звездочка) /(дробная черта) =(равно) > (больше) < (меньше); (точка с запятой) & (амперсант) [ ](квадратные скобки) { }(фигурные скобки) ()(круглые скобки) _(знак подчеркивания). (точка), (запятая): (двоеточие) #(" решетка" ) %(процент) ~(поразрядное отрицание)? (знак вопроса)! (восклицательный знак) \(обратный слеш).

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

Ключевые слова языка Си.

auto	break	case	char
const	continue	default	do
double	else	enum	extern
float	for	goto	if
int	long	register	return
short	signed	sizeof	static
struct	switch	typedef	union
unsigned	void	volatile	while

Основные ключевые слова Си:

Идентификаторы в языке Си.

Идентификатор (в дальнейшем, для краткости - ID ) – это имя программного объекта (константы, переменной, метки, типа, функции, модуля, поля в структуре). В идентификаторе могут использоваться латинские буквы, цифры и знак подчеркивания; первым символом ID может быть буква или знак подчеркивания, но не цифра; пробелы внутри ID не допускаются. Длина идентификатора определяется реализацией (версией) транслятора Cи и редактора связей (компоновщика). Современная тенденция - снятие ограничений длины идентификатора.

При именовании объектов следует придерживаться общепринятых соглашений:

- ID переменной обычно пишется строчными буквами, например index (для сравнения: Index – это ID типа или функции, а INDEX – константа);

- идентификатор должен нести какой-либо смысл, поясняя назначение объекта в программе, например birth_date (день рождения) или sum (сумма);

- если ID состоит из нескольких слов, как, например birth_date, то принято либо разделять слова символом подчеркивания (birth_date), либо писать каждое следующее слово с большой буквы (birthDate).

Разделители идентификаторов объектов:

- пробелы;

- символы табуляции, перевода строки и страницы;

- комментарии (играют роль пробелов).

Наличие разделителей не влияет на работу программы.

Виды констант в языке Си.

Константы - объекты, не подлежащие использованию в левой части оператора присваивания, т.к. константа - является неадресуемой величиной и, хотя она хранится в памяти ЭВМ, обычно нет никакого способа узнать ее адрес. В языке Си константами являются:

- самоопределенные арифметические, символьные и строковые данные;

- идентификаторы массивов и функций;

- элементы перечислений.

Арифметические константы могут быть целого или вещественного типов.

Целочисленные константы:

Общий формат: ±n (+ обычно не ставится).

Десятичные константы - последовательность цифр 0...9, первая из которых не должна быть 0. Например, 22 и 273 - обычные целые константы, если нужно ввести длинную целую константу, то указывается признак L(l) - 273L (273l). Для такой константы будет отведено – 4 байта. Обычная целая константа, которая слишком длинна для типа int, рассматривается как более длинный тип ( long или long long).

Существует система обозначений для восьмеричных и шестнадцатеричных констант.

Восьмеричные константы - последовательность цифр от 0 до 7, первая из которых должна быть 0, например: 020 = 16-десятичное.

Шестнадцатеричные константы - последовательность цифр от 0 до 9 и букв от A до F (a...f), начинающаяся символами 0Х (0х), например: 0X1F (0х1f) = 31-десятичное.

Восьмеричные и шестнадцатеричные константы могут также заканчиваться буквой L(l) - long, например, 020L или 0X20L.

Примеры целочисленных констант:

1992 13 1000L - десятичные;

0777 00033 01l - восьмеричные;

0x123 0X00ff 0xb8000l - шестнадцатеричные.

Вещественные константы:

Данные константы размещаются в памяти по формату double, а во внешнем представлении могут иметь две формы:

1) с фиксированной десятичной точкой, формат записи: ±n.m, где n, m - целая и дробная части числа;

2) с плавающей десятичной точкой (экспоненциальная форма): ±n.mE±p, где n, m - целая и дробная части числа, р - порядок, например, 1, 25× 10^-8 записывается как 1.25E-8.

Примеры констант с фиксированной и плавающей точками:

1.0 -3.125100е-10 0.12537е+13.

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

Символьная константа - это символ, заключенный в одинарные кавычки: 'A', 'х' (занимает 1 байт).

В языке Си используются и. специальные (управляющие ) символы, не отображаемые на экране; их назначение - влиять на порядок изображения других символов.. Поскольку они не отображаются на экране, для их обозначения в тексте программы используется пара символов, первый из которых всегда - обратная косая черта (обратный слеш) (" \" ). Основные их них:

\n	- новая строка;
\t	- горизонтальная табуляция;
\0	- нулевой символ (нуль-терминатор).

С помощью обратного слеша в символьных и строковых (см. ниже) константах представляются и некоторые обычные символы, чье написание там могло бы привести к двусмысленности:

\\	- сам обратный слеш;
\'	- апостроф;
\"	- кавычки.

При присваивании символьной переменной эти последовательности должны быть заключены в апострофы. Символьная константа '\0' (не путать с символом - цифрой '0'! ) часто записывается вместо целой константы 0, чтобы подчеркнуть символьную природу некоторого выражения (см. тему " Строки" ).

Примеры символьных констант: 'А', '9', '$', '\n', '\" '.

Строковые константы:

Строковая константа представляет собой последовательность символов кода ASCII, заключенная в кавычки (”). Во внутреннем представлении к строковым константам добавляется нулевой символ '\0', еще называемый нуль-терминатор, отмечающий конец строки. Кавычки не являются частью строки, а служат только для ее ограничения. Строка - это массив, состоящий из символов. Внутреннее представление константы " 01234\0ABCDEF":

'0', '1', '2', '3', '4', '\0', 'A', 'B', 'C', 'D', 'E', 'F', '\0'

Примеры строковых констант:

" Система", " \n\t Аргумент \n", " Состояние \" WAIT\" "

В конец строковой константы компилятор автоматически помещает нуль-символ (нуль-терминатор). Нуль-символ - это не цифра 0, он на печать не выводится и в таблице кода ASCII имеет код 0.

Например, строка " " - пустая строка, содержащая лишь нуль-терминатор.

Именованные константы:

Рассмотренные выше константы не имеют имен. Но иногда одну и ту же постоянную (т.е. не меняющуюся в ходе работы программы) величину приходится использовать в тексте программы многократно. Тогда может быть удобно назвать ее именем, чтобы в дальнейшем обращаться к ней по этому имени. Значение же ее будет указываться лишь в одном месте - при ее объявлении, и для его изменения необходимо лишь единственное исправление в тексте программы.

Объявление такой именованной константы пишется так же, как и объявление переменной, но перед ее типом указывается слово const:

const double pi=3.14159

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

double x=2*pi;

Таким образом, именованная константа выглядит, как переменная, но ее значение нельзя менять в процессе работы программы. Зато ее можно использовать там, где разрешается использовать только константы. В языке С++ в сложных программах, разбитых на модули, употребление именованных констант часто считается предпочтительнее, чем директива #define.

Операции сдвига.

Операции сдвига осуществляют смещение операнда влево (< < ) или вправо (> > ) на число битов, задаваемое вторым операндом. Оба операнда должны быть целыми величинами. Выполняются обычные арифметические преобразования. При сдвиге влево правые освобождающиеся биты устанавливаются в нуль. При сдвиге вправо метод заполнения освобождающихся левых битов зависит от типа первого операнда. Если тип unsigned, то свободные левые биты устанавливаются в нуль. В противном случае они заполняются копией знакового бита. Результат операции сдвига не определен, если второй операнд отрицательный. Преобразования, выполненные операциями сдвига, не обеспечивают обработку ситуаций переполнения и потери значимости. Информация теряется, если результат операции сдвига не может быть представлен типом первого операнда, после преобразования. Отметим, что сдвиг влево соответствует умножению первого операнда на степень числа 2, равную второму операнду, а сдвиг вправо соответствует делению первого операнда на 2 в степени, равной второму операнду.

Примеры:

int i=0x1234, j, k; k = i< < 4; /* k=" 0x0234" */ j=" i< < 8" ; /* j=" 0x3400" */ i=" j" > > 8; /* i = 0x0034 */

Void main ()

{ void cd (char); // прототип функции

cd ( ‘ *’); // оператор - выражение

…

}

2. Оператор – присваивания является оператором –выражением.

Оператор простого присваивания:

L-значение = выражение;

Оператор составного присваивания:

L-значение op= выражение;

Примеры:

x*= i; … i=x-4*i;

3. Оператор – выражение – инкремент или декремент L-значения:

Пример:

i++;

4. Операторы ввода - вывода данных также являются операторами –выражениями.

Оператор return

Оператор return; производит досрочный выход из текущей функции. Он, так же возвращает значение результата функции: return < выражение>; В функциях, не возвращающих результат, он неявно присутствует после последнего оператора. Значение выражения при необходимости преобразуется к типу возвращаемого функцией значения.

Пример 1:

float estim(float *x, int n) {

int i;

float y;

if ((! x)||(! n) {

error(x, n);

return 0;

}

for (y=i=0; i< n; i++) y+=x[i];

return y/n;

}

Пример 2:

void error(void *x, int n)

{

if (! x) printf(" \nМассив не создан" );

if (! n) printf(" \nМассив пустой" );

}

Рекурсивные программы.

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

int factorial (int n)

{if (n< =0) return 1; // рекурсия закончилась

else return n*factorial(n-1); //рекурсивный вызов

}

Функция factorial вызывает сама себя, если n> 0.

Обычно, в программировании под рекурсией понимают такую реализацию, в которой подпрограмма использует в своем теле вызов самой себя. Такие вызовы называют рекурсивными. Когда функция А в своем теле вызывает только одну рекурсивную функцию (саму себя), то говорят о простой рекурсии. Под косвенной рекурсией понимают явление, когда рекурсивные функции вызывают друг друга (например, функция А вызывает В, а функция В вызывает А).

Прямая рекурсия:

void A() {операторы;

A();

oператоры; }

Косвенная рекурсия:

void A() {операторы;

В();

oператоры; }

void В() {операторы;

A();

oператоры; }

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

Декларация структур.

Структура – тип данных, созданный пользователем, построенный с использованием других типов. Ключевое слово struct начинает определение структуры.

struct имя_структуры

{

тип1 имя_переменной;

тип2 имя_переменной;

тип3 имя_переменной; и т.д.

};

Например: struct Man {

char fam[20];

char name[15];

int year, day, month;

};

Среди типов данных структуры могут также присутствовать, кроме стандартных типов данных (int, float, char и т.д.) ранее определенные типы, но структура не может включать в себя переменные своего типа.

При непосредственной работе со структурой, доступ к компонентам структуры осуществляется с помощью оператора «точка», а при использовании указателя на структуру «-> ». Синтаксис для доступа к компонентам структуры следующий:

имя_переменной_структуры.член_данных

имя_переменной_структуры.-> член_данных

Указатели на структуры.

В случае, если мы имеем указатель на объект структуры, обращение к элементам осуществляется за счет разыменования указателя:

person *man=(person*)malloc(sizeof(person)); /*malloc – функция выделения динамической памяти*/

(*man).birthYear=1978;

(*man).birthMonth=;

В записи (*man) – скобки обязательны, а их отсутствие вызовет синтаксическую ошибку.

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

person *man = ( person* )malloc( sizeof( person ) );

man-> birthYear = 1978;

man-> birthMonth = 9;

man-> birthDay = 28;

man-> phone = 3222741;

man-> firstName = " Name";

man-> secondName = " Surname";

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

Двусвязный линейный список

Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два компонента указателя (ссылки на предыдущий и последующий элементы линейного списка). В программе двусвязный список можно реализовать с помощью описаний:

typedef struct ndd

{ float val; // значение элемента

struct ndd * n; // указатель на следующий элемент

struct ndd * m; // указатель на предыдующий элемент

} NDD;

NDD *dl, *p, *r;

Графическая интерпретация списка с двумя связями приведена на рис. 12.

Вставка нового узла со значением new за элементом, определяемым

указателем p, осуществляется при помощи операторов:

r=malloc(NDD);

r-> val=new;

r-> n=p-> n;

(p-> n)-> m=r;

p-> =r;

Удаление элемента, следующего за узлом, на который указывает p

p-> n=r;

p-> n=(p-> n)-> n;

( (p-> n)-> n )-> m=p;

free(r);

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

двунаправленным списком.

#include < stdio.h>

#include < alloc.h>

#include < conio.h>

#include < string.h>

struct zap

{ char inf[50];

zap *pr;

zap *nx; };

void add(zap **, zap **);

void ins(zap **, char *);

void del_any(zap **, zap **, char *);

void see(zap *, int);

void sort(zap **, zap **);

void main(void)

{ zap *h, *g; // указатели на хвост и голову очереди

char l, *st;

st=(char *)malloc(10);

h=g=NULL;

clrscr();

while(1)

{ puts(" вид операции: 1-создать очередь" );

puts(" 2-вывод содержимого очереди" );

puts(" 3-вставка нового элемента в очередь" );

puts(" 4-удаление любого элемента из очереди" );

puts(" 5-сортировка очереди" );

puts(" 0-окончить" );

fflush(stdin);

switch(getch())

{ case '1': add(& h, & g); break;

case '2': clrscr();

puts(" 0-просмотр с хвоста\n1- просмотр с головы" );

l=getch();

if( l=='0')se e(h, 0);

else see(g, 1);

break;

case '3': if(h)

{ gets(st);

ins(& h, st);

}br eak;

case '4': if(h)

{ge ts(st);

del_any(& h, & g, st);

}br eak;

case '5': if (h) sort(& h, & g); break;

case '0': return;

default: printf(" Ошибка, повторите \n" ); } } }

// функция создания очереди и добавления (только) в хвост очереди

void add(zap **ph, zap **pg)

{ zap *n;

puts(" Создание очереди \n" );

{ if(! (n=(zap *) calloc(1, sizeof(zap))))

{ puts(" Нет свободной памяти" );

return; }

puts(" Введите информацию в inf" );

scanf(" %s", n-> inf);

if (! *ph ||! *pg) // очередь еще не создана

{ *ph=n; // указатель на хвост очереди

*pg=n; } // указатель на голову очереди

else

{ n-> nx=*ph; // указатель на элемент (хвост) очереди

(*ph)-> pr=n; // хвост указывает на новый элемент

*ph=n; // передвигаем указатель хвоста на новый элемент

}

puts(" Продолжить (y/n): " );

fflush(stdin);

} while(getch()=='y'); }

// функция вывода содержимого очереди

// вывод начинать с хвоста (i==0) или головы (i==1)

void see(zap *p, int i)

{ puts(" Вывод содержимого очереди \n" );

if (! p)

{ puts(" Очередь пуста" );

return; }

{ printf(" %s\n", p-> inf);

if(! i) p=p-> nx;

else p=p-> pr;

} while(p);

return; }

// функция добавления элемента в очередь (до головы очереди)

// добавление работает правильно только если очередь упорядочена

// с хвоста по возрастанию [ (хвост) 1 2 5 7 9 (голова) вставить 4 ]

void ins(zap **ph, char *s)

{ zap *p=*ph, *n;

while(p & & strcmp(p-> inf, s)< 0) p=p-> nx;

if(! (n=(zap *) calloc(1, sizeof(zap))))

{ puts(" Нет свободной памяти" );

return; }

strcpy(n-> inf, s); // копирует s n-> inf

p-> pr-> nx=n; // предыдущий элемент очереди указывает

// на вводимый элементт (n)

n-> nx=p; // новый элемент указывает на следующий

// элемент очереди p

n-> pr=p-> pr; // новый элемент указывает на предыдующий

// элемент очереди p

p-> pr=n; // последующий элемент очереди указывает на

// вводимый элемент

}

// функция удаления любого одного элемента очереди

// p1- указатель на хвост p2- на голову очереди

void del_any(zap **p1, zap **p2, char *st)

{ zap *ph=*p1;

if (! *p1 ||! p2)

{ puts(" Очередь пуста" );

return; }

if (ph-> nx==NULL & & // в очереди только один элемент

(! strcmp(ph-> inf, st) || *st=='\0'))

{ free(ph);

*p1=*p2=NULL; // очередь пуста

return; }

while(ph & & strcmp(ph-> inf, st)) ph=ph-> nx;

if (! strcmp(ph-> inf, st)) // найден элемент со строкой st

{ if(ph==*p1) // удаляемая вершина - хвост очереди

{ *p1=(*p1)-> nx; // новый указатель на хвост очереди

(*p1)-> pr=NULL; }

else if(ph==*p2) // удаляемая вершина - голова очереди

{ *p2=(*p2)-> pr; // новый указатель на голову очереди

(*p2)-> nx=NULL; }

else

{ ph-> pr-> nx=ph-> nx; // обходим элемент pr

ph-> nx-> pr=ph-> pr; }

free(ph); }} // удаляем элемент pr очереди

// функция сортировки содержимого очереди

void sort(zap **ph, zap **pg)

{ zap *s1, *s2, *s3;

for(s2=*pg; s2; s2=s2-> pr)

for(s1=*ph; s1-> nx; s1=s1-> nx)

{ if(strcmp(s1-> nx-> inf, s1-> inf)> 0)

{ s3=s1-> nx; // s3- вершина следующая за s1

if(! s1-> pr) *ph=s1-> nx; // модификация хвоста очереди

s1-> nx=s1-> nx-> nx; // s1-nx указывает через вершину

if(s1-> nx) s1-> nx-> pr=s1; // s1-> nx выше был модифицирован

else s2=*pg=s1; // s1-> nx==NULL -коррекция головы

s3-> pr=s1-> pr;

s3-> nx=s1;

if (s3-> pr) s3-> pr-> nx=s3;

s1-> pr=s3;

s1=s1-> pr; }} // откат для s1=s1-> nx в цикле for

puts(" Сортировка выполнена" ); }

Методом выбора.

Алгоритм:

1 шаг – находится наименьший элемент в массиве;

2 шаг – найденный элемент меняется с первым элементом;

3 шаг – процесс повторяется с оставшимися n-1 элементами, n-2 элементами и так далее, пока в конце не останется самый большой элемент, который не нуждается в перестановке.

Пример 15.3

void MinSort(int a[], int n)

{ int i, j, k;

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

{ for (k=i; j=i+1; j< n; j++) // находим в цикле

if (a[j] < a[k]) // минимальный элемент

{ k = j; // запоминаем его номер в к

swap(& a[k], & a[i]); // меняем местами минимальный и

} // элемент, с которого начинался цикл}}

Методом вставки.

Сортировка вставками — очень простой метод сортировки, при котором элементы данных используются как ключи для сравнения. Этот алгоритм сначала упорядочивает А[0] и А[1], вставляя А[1] перед А[0], если А[0] > А[1]. Затем оставшиеся элементы данных по очереди вставляются в этот упорядоченный список. После k-й итерации элемент A[k] оказывается в своей правильной позиции и элементы от А[0] до A[k] уже отсортированы.

Пример 15.4

Функция InsertSort() реализует алгоритм сортировки методом вставки:

void InsertSort (int a[], int n)

{ int i, j

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

{ j=i;

while (a[j]< a[j-1] & & j> =1)

{ Swap(& a[j], & a[j-1]);

j--; } }}

Анализ сортировки вставками

Сортировка вставками обладает следующими характеристиками:

• после каждой итерации только один элемент помещается в свою правильную позицию;

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

• наихудший случай - когда все элементы данных отсортированы в обратном порядке;

• наилучший случай - когда элементы почти отсортированы в правильном порядке;

• легкость реализации.

Методом Шелла.

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

Основная идея алгоритма состоит в том, что на начальном этапе реализуется сравнение и, если требуется, перемещение далеко отстоящих друг от друга элементов. Интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних стадиях сортировки (если это необходимо).

Реализуем метод Шелла следующим образом. Начальный шаг сортировки примем равным n/2, т.е. ½ от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на gap элементов. Проход с тем же шагом повторяется, если элементы переставлялись. Заметим, что после каждого этапа отстоящие на gap элементы отсортированы. Рассмотрим пример.

Пример 15.5

Рассортировать массив чисел: 41, 53, 11, 37, 79, 19, 7, 61. В строке после массива в круглых скобках указаны индексы сравниваемых элементов и указан номер внешнего цикла.

41 53 11 37 79 19 7 61 – исходный массив

42 19 11 37 79 19 7 61 – (0, 4), (1, 5)

1-й цикл

41 19 7 37 79 19 11 61 – (2, 6), (3, 7)

7 19 41 37 11 53 79 61 – (0, 2), (1, 3), (2, 4), (3, 5), (4, 6), (5, 7)

2-й цикл

7 19 11 37 41 53 79 61 –

7 11 19 37 41 53 61 79 – (сравнивались соседние элементы) 3-й цикл

void sort_shell(int *x, int n)

{ int i, j; //две переменные цикла

int gap; //шаг сортировки

int sorted; //флаг окончания этапа сортировки

for(gap=n/2; gap> 0; gap/=2)//начало сортировки

{ sorted = 0;

for(i=0, j=gap; j< n; i++, j++)

if(*(x+i)> *(x+j))

{ swap((x+i), (x+j);

sorted = 1; } }

while(sorted); }

Анализ сортировки методом Шелла

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

57.Метод быстрой сортировки(Хоара).

Сортировка методом Хоора (или быстрая сортировка) — это наиболее эффективный алгоритм внутренней сортировки. Его производительность зависит от выбора точки разбиения. При быстрой сортировке используется следующая стратегия:

1. Массив разбивается на меньшие подмассивы.

2. Подмассивы сортируются.

3. Отсортированные подмассивы объединяются.

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

Рассмотрим один из вариантов реализации сортировки Хоора.

Пример 15.6

В самой процедуре сортировки сначала выберем средний элемент. Потом, используя переменные i и j, пройдемся по массиву, отыскивая в левой части элементы больше среднего, а в правой – меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше j. Тогда получаем два подмножества, ограниченные с краев индексами l и r, а в середине – j и i. Если эти подмножества существуют (то есть i< r и j> l), то выполним их сортировку.

void Quicksort(int a[], int n, int left, int right)

{ int i=left, j=right; /*Инициализируем переменные левой и

правой границами подмассива*/

int test=a[(left+right)/2]; /*Выбираем в качестве

элемента разбиения средний элемент массива*/

do { while (a[i] < test)

i++;

/*находим элемент, больший элемента разбиения */

while (a[j] > test)

j--;

/*находим элемент, меньший элемента разбиения */

if (i< =j)

{ Swap(& a[i], & a[j);

i++; j--; }

}

while(i < = j); /*рекурсивно вызываем алгоритм для

правого и левого подмассива*/

if (i< right)

QuickSort(a, n, i, right);

if (j> left)

QuickSort(a, n, left, j);

}

Анализ быстрой сортировки

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

Исходные и объектные модули, процессы компиляции и связывания.

Алфавит языка Си.

Алфавит языка Си включает:

- прописные и строчные буквы латинского алфавита, а также знак подчеркивания (код ASCII 95);

- арабские цифры от 0 до 9;

- специальные символы:

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

Ключевые слова языка Си.

auto	break	case	char
const	continue	default	do
double	else	enum	extern
float	for	goto	if
int	long	register	return
short	signed	sizeof	static
struct	switch	typedef	union
unsigned	void	volatile	while

Основные ключевые слова Си:

Идентификаторы в языке Си.

При именовании объектов следует придерживаться общепринятых соглашений:

Разделители идентификаторов объектов:

- пробелы;

- символы табуляции, перевода строки и страницы;

- комментарии (играют роль пробелов).

Наличие разделителей не влияет на работу программы.

Виды констант в языке Си.

- самоопределенные арифметические, символьные и строковые данные;

- идентификаторы массивов и функций;

- элементы перечислений.

Арифметические константы могут быть целого или вещественного типов.

Целочисленные константы:

Общий формат: ±n (+ обычно не ставится).

Существует система обозначений для восьмеричных и шестнадцатеричных констант.

Восьмеричные и шестнадцатеричные константы могут также заканчиваться буквой L(l) - long, например, 020L или 0X20L.

Примеры целочисленных констант:

1992 13 1000L - десятичные;

0777 00033 01l - восьмеричные;

0x123 0X00ff 0xb8000l - шестнадцатеричные.

Вещественные константы:

Данные константы размещаются в памяти по формату double, а во внешнем представлении могут иметь две формы:

1) с фиксированной десятичной точкой, формат записи: ±n.m, где n, m - целая и дробная части числа;

Примеры констант с фиксированной и плавающей точками:

1.0 -3.125100е-10 0.12537е+13.

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

Символьная константа - это символ, заключенный в одинарные кавычки: 'A', 'х' (занимает 1 байт).

\n	- новая строка;
\t	- горизонтальная табуляция;
\0	- нулевой символ (нуль-терминатор).

\\	- сам обратный слеш;
\'	- апостроф;
\"	- кавычки.

Примеры символьных констант: 'А', '9', '$', '\n', '\" '.

Строковые константы:

12 3 4 5 6 Следующая ⇒

Последнее изменение этой страницы: 2017-03-14; Просмотров: 606; Нарушение авторского права страницы