Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Улучшенный алгоритм сортировки: быстрая сортировка, сортировка ШеллаСодержание книги
Поиск на нашем сайте Быстрая сортировка состоит в том, что список В=< K1,K2,...,Kn> реорганизуется в список B’,< K1 >,B", где В’ - подсписок В с элементами, не большими К1, а В" - подсписок В с элементами, большими К1. В списке B’,< K1 >,B" элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B’ и В" снова применяется упорядочивание быстрой сортировкой. Приведем в качестве примера сортировку списка, отделяя упорядоченные элементы косой чертой, а элементы Ki знаками < и >. Пример: 9, 7, 18, 3, 52, 4, 6, 8, 5, 13, 42, 30, 35, 26 7, 3, 4, 6, 8, 5/ <9>/ 18, 52, 13, 42, 30, 35, 26 3, 4, 6, 5/<7>/ 8/ 9/ 13/ <18>/ 52, 42, 30, 35, 26 <3>/ 4, 6, 5/ 7/ 8/ 9/ 13/ 18/ 42, 30, 35, 26/ <52> 3/ <4>/ 6, 5/ 7/ 8/ 9/ 13/ 18/ 30, 35, 26/ <42>/ 52 3/ 4/ 5/ <6>/ 7/ 8/ 9/ 13/ 18/ 26/ <30>/ 35/ 42/ 52 Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подсписки B’ и В" приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов. Рекурсивная функция 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); } Здесь используются два индекса i и j, проходящие части массива навстречу друг другу. При этом i всегда фиксирует разделяющий элемент cnt=s[low], слева от которого находятся числа, не большие cnt, а справа от i - числа, большие cnt. Возможны три случая: при s[i+1]<=cnt; при s[i+1]>cnt и s[j]<=cnt; при s[i+1]>cnt и s[j]>cnt. По окончании работы i=j, и cnt=s[i] устанавливается на своем месте. Быстрая сортировка требует дополнительной памяти порядка 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. Сортировка строк #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; } }
44. Методы поиска: последовательный и двоичный поиск. Последовательный поиск Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация, когда V содержит один элемент, а в В имеется не более одного такого элемента. Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В, а Si - количество сравнений, необходимое для его поиска, то n Max{А} = max{ Si, i=1,n }; Avg{А} = Pi Si. i=1 Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядкеих расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера. Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка. Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом: /* последовательный поиск без стоппера */ #include main() { int k[100],v,i; for (i=0;i<100;i++) scanf("%d",&k[i]); scanf("%d",&v); i=0; while(k[i]!=v && i<100) i++; if (k[i]==v) printf("%d %d",v,i); else printf("%d не найден",v); } С использованием стоппера программу можно записать в виде: /* последовательный поиск со стоппером */ #include main() { int k[101],v,i; for (i=0;i<100;i++) scanf("%d",&k[i]); //ввод данных scanf("%d",&v); k[100]=v; //стоппер i=0; while(k[i]!=v) i++; if (i<100) printf ("%d %d",v,i); else printf ("%d не найден",v); } Двоичный поиск Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для такихсписков применим последовательный поиск. Двоичный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, противном случае поиск продолжается в одной из половин списка. Нахождение элемента двоичным поиском осуществляется очень быстро. Max двоичного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg двоичного поиска равен log2(N). Недостаток двоичного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов. Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V – элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления двоичного поиска ключа V в списке К1,К2,...,К100. /* Двоичный поиск */ #include main() { int k[100],v,i,j,m; for (i=0;i<100;i++) scanf("%d",&k[i]); scanf("%d",&v); i=0; j=100; m=50; while (k[m]!=v) { if (k[m] < v) i+=m; else j=m-i; m=(i+j)/2; } printf("%d %d",v,m); }
Основы файловой системы. Стандартные потоки. Указатель файла. Открытие файла. Закрытие файла. Потоки Потоки представляют собой удобный переносимый способ чтении и записи данных. Они обеспечивают гибкие и эффективные средства для ввода/вывода. Поток - это байтовая последовательность, передаваемая в процессе ввода, которая управляется через указатель на поток. Потоковый ввод/вывод - буферизированный: это означает, что блок данных фиксированного размера читается/пишется в файл не посредственно, а через временную область хранения (буфер). Это повышает эффективность ввода/вывода, но будьте осторожны: данные, записанные в буфер, не появятся в файле или на устройстве, пока буфер не будет очищен. Всякое неуспешное завершение программы может вызвать проблемы. Потоковый ввод/вывод эффективен для символов и строк. Основы файловой системы Основным понятием, связанным с информацией на внешних устройствах ЭВМ, является понятие файла. Всякая операция ввода/вывода трактуется как операция обмена с файлами: Ввод- это чтение из файла в оперативную память; вывод - это запись из оперативной памяти в файл. Сначала нужно открыть поток перед выполнением каких-либо операций ввода/вывода, затем выполнить операции доступа (чтения/записи) и потом закрыть. В языке Си файл - это байтовая последовательность, заканчивающаяся EOF. В языке Си отсутствует понятие типа файла. Указатель файла Работа с файлами начинается с объявления указателя на поток: FILE *имя_указателя; FILE *fp; FILE внутренняя C-структура данных языка Си,которая используется для работы с потоками и определена в stdio.h. Стуктура FILE содержит следующую информацию: указатель на буфер, указатель текущей позиции в потоке. Открытие файла Открыти файла возможно при помощи функции fopen(), синтаксис которой следующий: FILE *fopen(char *name, char *mode) fopen возвращает указатель на структуру FILE. Строка name содержит имя файла. Строка mode определяет способ доступа. Если файл не может быть открыт по какой-либо причине, функция возвращает NULL. Способы доступа включают: "r" - чтение, "w" - запись, "a" - добавление в конец. Также способ доступа может включать: "t" - текстовый, "b" - бинарный. Для открытия файла myfile.dat на чтение необходимо: FILE *stream, *fopen(); /* описание потока и прототипа fopen */ stream = fopen("myfile.dat","r"); Необходимо проверять, что файл открылся: if ((stream = fopen("myfile.dat", "r")) == NULL) { printf("Нельзя открыть %s\n", "myfile.dat"); exit(1); } ...... Закрытие файла Для того, чтобы закрыть файл, используется функция fclose. Ее синтаксис: fclose(FILE *stream) Пример. Ввести матрицу из файла inputfile.dat.Файл входных данных имеет следующую структуру: n - количество строк m - количество столбцов a a... a ... a a... a, где n - количество строк m - количество стобцов a - элементы матрицы. И вывести ее в файл outputfile.dat.
#include <stdio.h> // открытие файла на чтение }
46. Форматированный ввод-вывод в файл.
47. Запись и чтение символов. Ввод/вывод строк. Стирание файлов. Запись и чтение символа Функции записи и чтения символа подобны fprintf и fscanf, только пишут и читают не в поток/из потока, а в строку/из строки: int sprintf(char *string, char *format, args..)
int sscanf(char *string, char *format, args..) Пример: float full_tank = 47.0; float miles = 300; char miles_per_litre[80]; sprintf(miles_per_litre,"Miles per litre = %2.3f", miles/full_tank); Ввод/вывод строк Стандартная библиотека содержит функцию fgets. В результате обращения fgets(line, maxline, fp) следующая строка ввода (включая символ новой строки) считывается из файла fp в символьный массив line; самое большое maxline_1 символ будет прочитан. Результирующая строка заканчивается символом \0. Нормально функция fgets возвращает line; в конце файла она возвращает null. Предназначенная для вывода функция fputs записывает строку (которая не обязана содержать символ новой строки) в файл: fputs(line, fp) Очистка буфера потока Функция fflush очищает буфер потока: fflush(FILE *stream)
48. Понятия очереди, стеков, связанных списков и деревьев. Понятия очереди, стеков, связанных списков и деревьев В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью. Стек – это конечная последовательность некоторых однотипных элементов – скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S= и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило, изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >. Допустимыми операциями над стеком являются: - проверка стека на пустоту S=< >, - добавление нового элемента Sn+1 в конец стека - преобразование < S1,...,Sn> в < S1,...,Sn+1>; - изъятие последнего элемента из стека - преобразование < S1,...,Sn-1,Sn> в < S1,...,Sn-1>; - доступ к его последнему элементу Sn, если стек не пуст. Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху. Очередь – это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине). Двусторонняя очередь – это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов. Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами. Одной из форм представления выражений является польская инверсная запись, задающая выражение так, что операции в нем записываются в порядке выполнения, а операнды находятся непосредственно перед операцией. Например, выражение (6+8)*5-6/2в польской инверсной записи имеет вид 6 8 + 5 * 6 2 / -Особенность такой записи состоит в том, что значение выражения можно вычислить за один просмотр записи слева направо, используя стек, который до этого должен быть пуст. Каждое новое число заносится в стек, а операции выполняются над верхними элементами стека, заменяя эти элементы результатом операции. Для приведенного выражения динамика изменения стека будет иметь вид S = < >; <6>; <6,8>; <14>; <14,5>; <70>; <70,6>; <70,6,2>; <70,3>; <67>. Ниже приведена функция eval, которая вычисляет значение выражения, заданного в массиве m в форме польской инверсной записи, причем m[i]>0 означает неотрицательное число, а значения m[i]<0 - операции. В качестве кодировки операций сложения, вычитания, умножения и деления выбраны отрицательные числа -1, -2, -3, -4. Для организации последовательного хранения стека используется внутренний массив stack. Параметрами функции являются входной массив a и его длина l. float eval (float *m, int l) { int p,n,i; float stack[50],c; for(i=0; i < l;i++) if ((n=m[i])<0) { c=st[p--]; switch(n) { case -1: stack[p]+=c; break; case -2: stack[p]-=c; break; case -3: stack[p]*=c; break; case -4: stack[p]/=c; } } else stack[++p]=n; return(stack[p]); }Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1.", то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK. #include typedef struct st /* объявление типа STACK */ { char ch; struct st *ps; } STACK; main() { STACK *p,*q; char a; p=NULL; do // заполнение стека { a=getch(); q=malloc(sizeof(STR1)); q->ps=p; p=q; q->ch=a; } while(a!= ’. ’); do // печать стека { p=q->ps;free(q);q=p; printf("%c",p->ch); } while(p->ps!=NULL); } Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17,19,23,25,38,39,47, 60> из 9 элементов. Для слияния списков А и В список С сначала полагается пустым, а затем к нему последовательно приписывается первый узел из А или В, оказавшийся меньшим и отсутствующий в С. Составим функцию для слияния двух упорядоченных, расположенных рядом частей массива s. Параметром этой функции будет исходный массив s с выделенными в нем двумя расположенными рядом упорядоченными подмассивами: первый с индекса low до индекса low+l, второй с индекса low+l+1 до индекса up, где переменные low, l, up указывают месторасположения подмассивов. Функция merge осуществляет слияние этих подмассивов, образуя на их месте упорядоченный массив с индексами от low до up. /* слияние списков */ 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);}
|
||
|
|
Последнее изменение этой страницы: 2021-08-16; просмотров: 92; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.216.236 (0.012 с.) |
