Шпаргалка по языку СИ. Конспект Лекций «программирование На Языке Высокого Уровня Си» П. Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления
 Скачать 1.25 Mb.
|
|
Исходный массив 12 16 10 9 10 9 9 11 10 11 2: 12 16 10 9 10 9 9 11 10 11 3: 10 12 16 9 10 9 9 11 10 11 4: 9 10 12 16 10 9 9 11 10 11 5: 9 10 10 12 16 9 9 11 10 11 6: 9 9 10 10 12 16 9 11 10 11 7: 9 9 9 10 10 12 16 11 10 11 8: 9 9 9 10 10 11 12 16 10 11 9: 9 9 9 10 10 10 11 12 16 11 10: 9 9 9 10 10 10 11 11 12 16 Результат 9 9 9 10 10 10 11 11 12 16 Рис. 39. Сортировка массива простыми вставками //процедура сортировки простыми вставками void SortInsert (int count, int* pArr) { int temp, j; for (int i = 1; i < n; i++) // цикл проходов, i - номер прохода { temp = pArr[i]; j = i-1; // поиск места элемента в готовой последовательности while (j >= 0 && pArr[j] > temp) { pArr[j+1] = pArr[j]; // сдвигаем элемент направо, пока не дошли --j; } // место найдено, вставить элемент pArr[j+1] = temp; } } 141 № шага Сортировка простыми вставками является наиболее быстрой из рассмотренных. На практике очень часто используются оптимизированные (улучшенные) алгоритмы сортировки на основе алгоритма простых вставок, например, алгоритм простых вставок со «сторожевым» элементом или алгоритм Шелла. Алгоритмы поиска Поиск является одной из основных задач в программировании. Несмотря на кажущуюся простоту задачи, существует множество алгоритмов для ее решения. В общем виде задача поиска ставится следующим образом: найти элемент и его координаты с указанным значением в массиве. Это тривиальная задача решается алгоритмом линейного поиска, когда последовательно проходится весь массив и текущий элемент массива сравнивается с искомым элементом. В случае совпадения запоминается индекс(ы) найденного элемента. Однако в задаче поиска может быть множество дополнительных условий. Например, поиск минимального и максимального элемента, поиск подстроки в строке, поиск в массиве, который уже отсортирован, поиск с целью узнать есть или нет нужного элемента без указания индекса и т.д. Рассмотрим некоторые типовые задачи поиска. Поиск подстроки в тексте (строке). Алгоритм грубой силы Поиск подстроки в строке осуществляется по заданному образцу, т.е. некоторой последовательности символов, длина которой не превышает длину исходной строки. Задача поиска заключается в том, чтобы определить, содержит ли строка заданный образец и указать место (индекс) в строке, если совпадение найдено. Алгоритм грубой силы является самым простым и самым медленным и заключается в проверке всех позиций текста на предмет совпадения с началом образца. Если начало образца совпадает, то сравнивается следующая буква в образце и в тексте и так далее до полного совпадения образца или отличия в очередной букве. 142 int BFSearch(char *s, char *p) { for (int i = 1; strlen(s) - strlen(p); i++) { for (int j = 1; strlen(p); j++) { if (p[j] != s[i+j-1]) { break; } else { if (j = strlen(p)) { return(i); exit; } } } } } Функция BFSearch ищет подстроку p в строке s и возвращает индекс первого символа подстроки или 0, если подстрока не найдена. Хотя в общем случае этот метод, как и большинство методов грубой силы, малоэффективен, в некоторых ситуациях он вполне приемлем. Наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке, считается алгоритм Бойера- Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), суть которого в следующем. Алгоритм Бойера-Мура Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге строится таблица смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т.д. Если все символы образца совпали с наложенными символами строки, значит найдена подстрока и поиск 143 окончен. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, мы сдвигаем образец на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки. Величина сдвига в случае несовпадения последнего символа вычисляется по правилу: сдвиг образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, то смещается образец таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если же образец вообще не содержит этого символа, то образец сдвигается на величину, равную его длине, так что первый символ образца накладывается на следующий за проверявшимся символом строки. Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть есть набор из пяти символов: a, b, c, d, e и нужно найти вхождение образца “abbad” в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма: Таблица смещений для образца “abbad”. Начало поиска. Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций: 144 Три символа образца совпали, а четвертый – нет. Сдвигаем образец вправо на одну позицию: Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции: Еще раз сдвигаем образец на 2 позиции: Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца: Реализуем указанный алгоритм. Прежде всего, следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение структуры будет выглядеть так: struct BMTable { int bmtarr[255]; } *bmt; Далее приводится процедура, вычисляющая таблицу смещений для образца p. BMTable MakeBMTable(char *p) { int i; for (i = 0; i <= 255; i++) bmt->bmtarr[i] = strlen(p); for (i = strlen(p); i <= 1; i--) { if (bmt->bmtarr[p[i]] == strlen(p)) { bmt->bmtarr[p[i]] = strlen(p)-i; } } return(*bmt); } Теперь напишем функцию, осуществляющую поиск. int BMSearch(int startpos, char *s, char *p) { int pos, lp, i; 145 lp = strlen(p); pos = startpos + lp - 1; while (pos < strlen(s)) { if (p[lp] != s[pos]) pos = pos + bmt->bmtarr[s[pos]]; else { for (i = lp - 1; i <= 1; i--) { if (p[i] != s[pos - lp + i]) { pos++; break; } else if (i = 1) { return(pos - lp + 1); exit; } } } } return(0); } Функция BMSearch возвращает позицию первого символа первого вхождения образца p в строке s. Если последовательность p в s не найдена, функция возвращает 0. Параметр startpos позволяет указать позицию в строке s, с которой следует начинать поиск. Это может быть полезно в том случае, если вы захотите найти все вхождения p в s. Для поиска с самого начала строки следует задать startpos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение p в s, нужно задать startpos равным значению «предыдущий результат плюс длина образца». Бинарный (двоичный) поиск Бинарный поиск используется в том случае, если массив, в котором осуществляется поиск, уже упорядочен. Переменные lb и ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный элемент. Поиск начинается всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, то нужно перейти к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением ub становится (m – 1) и на следующей итерации проверяется половина исходного 146 массива. Таким образом, в результате каждой проверки вдвое сужается область поиска. Например, если в массиве 100 чисел, то после первой итерации область поиска уменьшается до 50 чисел, после второй – до 25, после третьей до 13, после четвертой до 7 и т.д. Если длина массива равна n, то для поиска в массиве элементов достаточно около log 2 n сравнений. int BinarySearch (int lb, int ub, int key, int* pArr) /* a – исходный массив, lb – левая граница поиска, ub – правая граница поиска, key – значение искомого элемента. Функция возвращает индекс совпадающего элемента в массиве, и -1 – если элемент не найден */ { int m; return(-1); // функция возвращает -1 , если элемент не найден do { m = (lb + ub)/2; //находим индекс «половинки» массива if (key < pArr[m]) ub = m-1; else if (key > pArr[m]) lb = m+1; else { // найдено совпадение return(m); break; } } while (lb > ub); } Динамические структуры данных Динамические структуры данных основаны на использовании указателей и применении стандартных процедур и функций выделения/освобождения памяти в процессе работы программы. Они отличаются от статических структур данных, которые описываются в разделах описания типов и данных. Когда описывается статическая переменная в программе, то при компиляции программы выделяется оперативная память, в зависимости от типа переменной. При этом изменить размер выделенной памяти невозможно. Например, если указан массив char S[10]; то под него один раз в начале выполнения программ выделяется 10 байт оперативной памяти. 147 Динамические структуры характеризуются непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки. Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей: 1) информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой – записью, вектором, массивом, другой динамической структурой и т.п.; 2) поля связок, в которых содержатся один или несколько указателей, связывающих данный элемент с другими элементами структуры. Когда связное представление данных используется для решения прикладной задачи, для конечного пользователя "видимым" делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком. Достоинства связного представления данных: • в возможности обеспечения значительной изменчивости структур; • размер структуры ограничивается только доступным объемом машинной памяти; • при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей; • большая гибкость структуры. Вместе с тем связное представление не лишено и недостатков, основные из которых: • на поля связок расходуется дополнительная память; 148 • доступ к элементам связной структуры может быть менее эффективным по времени. Последний недостаток является наиболее серьезным и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных (массивы) для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента и информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, списки, деревья и т.д.). К динамическим структурам, используемым в программировании, относятся: • динамические массивы (были рассмотрены в теме 6); • линейные списки; • стек; • очередь, дек; • деревья. Линейные списки Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Линейные связные списки являются простейшими динамическими структурами данных. 149 Графически связи в списках удобно изображать с помощью стрелок, как было показано в разделе описания указателей. Если элемент списка не связан с любым другим, то в поле указателя записывают значение, не указывающее ни на какой элемент (пустой указатель). Такая ссылка в Паскале обозначается nil, а на схеме обозначается перечеркнутым прямоугольником. Ниже приведена структура односвязного списка (рис.40), т.е. связь идет от одного элемента списка к другому в одном направлении. Здесь поле D – это информационное поле, в котором находятся данные (любой допустимый в языке Паскаль тип), поле N (NEXT) – указатель на следующий элемент списка. Каждый список должен иметь следующие указатели: Head – голова списка, Cur – текущий элемент списка, иногда в односвязных списках также используется указатель Tail – хвост списка (в двухсвяхных списках он используется всегда). Поле указателя последнего элемента списка является пустым, в нем находится специальный признак nil, свидетельствующий о конце списка и обозначается перечеркнутым квадратом. Двухсвязный линейный список отличается от односвязного наличием в каждом узле списка ещё одного указателя B (Back), ссылающегося на предыдущий элемент списка (рис.41). D D Head Cur Tail D N N D N Рис.40. Пример односвязного линейного списка D D D H T C Рис.41. Пример двухсвязного линейного списка N N B B 150 Структура данных, соответствующая двухсвязному линейному списку описывается на языке Си следующим образом: struct list { int value; // значение элемента struct list *next; // указатель на следующий элемент struct list *back; // указатель на предыдующий элемент } При работе с линейными списками используются следующие основные операции: • создание списка; • добавление нового элемента в список: в голову списка, в хвост списка, после текущего элемента списка, перед текущим элементом списка; • удаление элемента из списка; • обход списка с целью его обработки; • поиск узла в списке; • переход на узел в списке по номеру от начала и другие операции. Создание списка При создании списка нужно выполнить следующие действия (рис. 42): • выделить память; • «обнулить» указатели на предыдущий и последующий элементы; • определить указатели на голову, хвост и текущий элемент списка; • внести в информационную часть списка данные. Добавление нового узла в список Для добавления нового узла в голову списка нужно выполнить последоватеьность действий, указанных в табл.15. head tail cur int val; list head,tail,cur; list* ptr = new list; ptr -> next = NULL; ptr -> back = NULL; tail = ptr; head = ptr; cur = ptr; ptr -> value = val; p Рис.42. Процедура создания списка 151 Таблица 15. Добавление нового узла в голову списка № Действие Иллюстрация 1. Выделить память под новый узел списка: list* ptr = new list. 2. Заполнить информационную часть узла и обнулить указатели в нем 3. Если список пуст, то этот узел сделать головой списка: head = ptr. 4. Если список не пуст, то 4.1. Для нового узла следующий указатель установить на голову текущего списка: ptr -> next = head. 4.2. Для головы списка предыдущий указатель установить на новый узел: head -> back = ptr. 4.3. Установить на новый узел указатель на голову списка: head = ptr. int val; list head; list* ptr = new list; ptr->value = val; ptr->next = NULL; ptr->back = NULL; if (head == Nil) head = ptr //список пустой? 152 данные ptr head ptr head ptr данные head head ptr ptr |