Поиск в упорядоченной таблице - раздел Программирование, КУРС ПРОГРАММИРОВАНИЯ НА ЯЗЫКЕ СИ Все Реально Применяемые Методы Поиска Относятся К Отсортированным Таблицам...
Все темы данного раздела:
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
&2k
Касюк, СТ.
К289 Курс программирования на языке Си: конспект лекций/
СТ. Касюк. — Челябинск: Издательский центр ЮУрГУ, 2010. — 175 с.
Учебное пособие по курсу программирования на языке Си нап
Результат работы программы
Здравствуй, язык Си!
В этой программе имя функции main. При выполнении программы, созданной на языке Си, операционная система компьютера всегда передаёт управление в програм
Объекты языка Си и их типы
Программа, написанная на языке Си, оперирует с объектами. Они могут быть простыми и сложными. К простым объектам относятся переменные и константы, к сложным — массивы, структуры, очереди, списки и
Простые объекты
К простым объектам языка Си относятся константы и переменные.
Константа — это ограниченная последовательность символов алфавита языка (лексема), представляющая собой изображение фик
Ввод и вывод информации
Основной задачей программирования является обработка информации, поэтому любой язык программирования должен иметь средства для ввода и вывода данных. В языке Си нет операторов ввода-вывода; ввод и
Общая форма записи функции printfQ
printf("строка форматов",объект 1,объект 2,...,объект п]
Строка форматов состоит из следующих элементов:
1) управляющих символов;
2) текста, котор
V — возврат на начало строки;
6) 'а' — звуковой сигнал.
Форматы нужны для того, чтобы указывать вид, в котором информация будет выведена на экран. Отличительной чертой формата является наличие символа процент «%»
Результат работы программы
Значение переменной у=3.0000000
В программе 10 — общее количество позиций под значение переменной; 7 — количество позиций после десятичной точки.
Функция форматированного ввода
Общая форма записи
switch( <целое выражение> )
{
case <константное выражение1>:
<оператор1>; break;
Общая форма записи
while(<выражение>; <оператор> ;
Если выражение истинно (т. е. не равно нулю), то выполняется оператор или группа операторов, входящих в цикл while; затем выражение прове
Функции
Функция — это самостоятельная единица программы, которая спроектирована для реализации конкретной задачи. Функция является подпрограммой, которая может содержаться в основной п
Старый стиль определения функции
тип функции имя функции (имена формальных
параметров через запятую)
объявление формальных параметров;
{
/* тело функции */
return (<выражение>); }
Результат работы программы
Введите целое число
7.0000001=5040.000000
Вызов функций Общий вид вызова функции
имя функции(<список фактических параметров>);
Прототипы функций
В практике программирования бывают случаи, когда тело функции располагается в программе ниже функции её вызывающей или функция вообще компилируетсятся отдельно. В этом случае до использования функц
F начало J
Формальные параметры функции
I
Р=2
| i<=index;H-i- |
Препроцессор
Препроцессор — это специальная программа, являющаяся частью компилятора языка Си и предназначенная для предварительной обработки текста программы. Препроцессор позволяет включать в текст про
Математические функции
Математические функции стандартной библиотеки хранятся в головном файле <math.h>. Аргументы функции имеют тип double — тип с плавающей точкой двойной точности. Все математические функц
Глобальные и локальные объекты
Глобальныминазываются объекты, объявление которых дано вне функции. Они доступны (видимы) во всём файле, в котором они объявлены, а также во всех внешних файлах (модулях).
Модификация объектов
Модификация или видоизменение объектов в языке Си применяется для того, чтобы расширить или, наоборот, сузить диапазон значений или область действия объекта. Инструкции, которые применяются для мод
Модификация расположения объектов в оперативной памяти
Модификатор static. При выполнении программы объекты могут быть расположены либо по фиксированным адресам оперативной памяти, либо по произвольным адресам по мере того, как
Результат работы программы
k=l k=2 k=3 k=4 k=5
Переменная к в функции stat зафиксирована в оперативной памяти. Инициализация к проводится только один раз — при первом вызове функции переменной
Указатели
Указатель — переменная, содержащая адрес объекта. Указатель не несет никакой информации о самом объекте, а содержит сведения о том, где размещен
объект. Указат
Результат работы программы
Значение переменной а равно 134.
Адрес
переменной
а
равен 0012FED4.
&n
Модели памяти
При разработке программ для персональных компьютеров, оснащенных микропроцессорами серии х8б, размер указателя (число байтов, требуемых для размещения адреса памяти) зависит от модели памяти
Массивы
Большинством объектов языка Си, с которыми мы имели дело, были переменные. Каждая переменная при объявлении получала тип и имя, с которым связывалась определенная ячейка памяти. Однако расположение
Sizeof(float)
-J------ L
sizeof(data)
■*i
Рис. 1.5
Форма обращения к элементам массива с помощью указателей следующая:
•
Передача массива в функцию
Обработку массивов удобно организовывать с помощью специальных функций. Если в функцию передается массив, то на самом деле внутрь функции попадает только адрес массива. Фактически в функцию передаю
Общая форма объявления многомерного массива
тип имя массива [индекс 1]
[индекс 2]
[индекс п];
Элементы многомерного массива располагаются в последовательных ячейках оперативной памяти по возрастанию адресов. Между
Динамическое распределение памяти
При программировании на языке Си может возникнуть ситуация, когда формально правильно написанная программа содержит некоторую серьёзную ошибку, которая может настолько повредить работе компьютера,
Динамическое распределение памяти под массивы
Динамическое распределение памяти под массивы необходимо использовать в том случае, когда размер массива заранее не известен. Это означает, что размер массива будет определяться в ходе выполнения п
Программа
#include <stdio.h> #include <alloc.h> main()
{
float *b;
int n, m, i, j ;
printf("n Введите количество строк: n= ";
scant("%u
Массивы указателей
Свободным называется двухмерный массив (матрица), размер строк которого может быть различным. Преимущество использования свободного массива заключается в том, что не требуется отводить памят
Общая форма объявления структуры
struct
тип структуры
{
Объединения
Объединениями называют сложный тип данных, позволяющий размещать в одном и том же месте оперативной памяти данные различных типов. Естественно, что в данный момент времени в данном месте пам
Общая форма объявления объединения
union имя объединения
{
тип имя объекта 1; тип имя объекта 2;
тип имя объекта п; } имя переменной;
Видно, что объединение подобно структуре, однако в определённы
Битовые поля
Используя структуры, можно упаковать целочисленные компоненты ещё более плотно, чем это было сделано с использованием массива. При упаковке целых объектов, как правило, допускается применять только
Программа
#include <stdio.h>
struct field t
{
unsigned i
:ype
Указатели и структуры
Выбор элементов структуры или объединения.Выражение выбора элемента позволяет получить доступ к элементу структуры или объединения. Выражение имеет значение и тип выбранного элемен
Инициализация структур без указателя
gets ( libry[i] .title );
/*
Ввод
названия книги.*/
gets ( libry[i].author);
/*
Инициализация массива структур при помощи указателя р
gets((*p).title);
/*
Ввод названия книги.*/
gets ( ( *р) .author);
/*
Ввод имени автора.*/
Функции ввода-вывода нижнего уровня.
Для функций ввода-вывода верхнего уровняхарактерным является то, что обмен информации производится через буфер. Буфер — это некоторая область оперативной памяти, в которую п
Программа
Рис. 1.13. Схема передачи информации функций ввода-вывода верхнего уровня
Поток — это абстрактное понятие, относящееся к любому переносу данных от источника данны
Функции ввода-вывода высокого уровня
В языке Си ввод и вывод информации возложен на функции ввода-вывода. Прототипы функций ввода-вывода высокого уровня содержатся в файле stdio.h.
До сих пор мы использовали только две функци
Функция scanfQ
#include <stdio.h>
int scant(format string
[,
argu
Работа программы
а
<Enter>
а
<Enter>
абв
<Enter>
абв
Работа с файлами данных
Для программиста открытый файл представляется как последовательность данных — считываемых данных или записываемых данных. При открытии файла с ним связывается поток. Выводимая информация записывает
Функции ввода-вывода, работающие с файлами
1. Функция чтения символа из файла fgetc. Функция fgetc читает один символ из вводного потока/
#inc
lude
Функции обработки строк
Функции, оперирующие со строками, определены в головном файле string.h. Аргументы функций условно имеют имена s, t, cs, ct, n, с, причем s и t должны быть описаны как char *
Работа со строками
В программе строки могут определяться следующим образом [14]:
1) как строковые константы;
2) как массивы символов;
3) через указатель на символьный тип;
4) как м
Результат работы
отдохнешь и ты.
Явное задание размера памяти.При объявлении массива можно указать: char ml[36] = "В полдневный жар в долине Дагестана"; вместо
Получился диалог
Привет, как
вас зовут?
Владимир
<Enter>
Владимир?
Программа
/* Использование main ( )
г
функции scanf(
) .*/
char namel[
Программма
#include <stdio.h>
#define
DEF "Я строка #d
e
Результат работы программы
Я аргумент функции puts.
Я строка #define.
Массив инициализирован мной.
Указатель инициализирован мной.
ив инициализирован мной,
атель инициализирован м
Результат работы программы
С т р о
к а си
м в
о л
о
в
С т р о
к а си
м
Результат работы программы
Назовите
ваш
любимый
цветок
Пион
<Enter>
&nb
Логический тип данных в языке Си
Логическая переменная — переменная, которая принимает только два значения:
1) истина — (1 или TRUE);
2) ложь — (0 или FALSE).
На первый взгляд логиче
Результат работы программы
!2 = 0
Логические операции «И», «ИЛИ» и «НЕ» позволяют создавать функции алгебры логики
Y=f(X,X2,...,Xn), в которой XI, XI, ...., Хп — логиче
Программная реализация стека
Стеком называют область памяти ЭВМ, предназначенную для сохранения данных и организованную по принципу «первым вошел — последним вышел» [11]. Графическое представление стека показано на рис.
Стек (структура, состоящая ш int info н указателя на саму себя)
Рис. 1.17.Графическое представление работы программы
Анализ работы функции push приведен ниже. Шаг1. С помощью строки
STACK*stl =
Адрес 2024 Адрес 2026
ММ........................................ мь!-*.............
new item=2024
info=1200nest=*s
В указатель stl помещается число new item
.............. п
stl=2024
Рис. 1.23
Для иллюстрации работы программы построим таблицу (табл. 2.6).
Таблица 2.6
Результат работы программы
Указатель стека
после ввода
числа
1200 2204
Указатель стека
после ввода
числа
Однонаправленные связанные списки
Связанный списокявляется простейшим типом данных динамической структуры. Компоненты связанного списка можно помещать и исключать произвольным образом [1,3,8,11]. Графическое предст
Однонаправленные циклические списки
Одним из недостатков линейных списков является то, что имея указатель р на элемент, мы не можем получить доступа к предшествующим элементам.
Циклический связанный список
Двунаправленные связанные списки
Каждый элемент двунаправленного связанного списка имеет два указателя
(рис. 2.3) [8, И]:
• один указатель установлен на предшествующий элемент;
• другой указатель установ
ЦИКЛИЧЕСКИЙ ДВУНАПРАВЛЕННЫЙ СПИСОК
ptrnl -NULL
1
■
ptrn2=N
Очереди
Очередьюназывается упорядоченный набор элементов, которые могут удаляться с начала очереди и помещаться в конец очереди (рис. 2.9). Очередь организована в отличие от
ТОРГОВЫЙ ЗАЛ
Рис. 2.9. Графическое представление очереди Объявление пустой очереди
#define Maxg 5
float git[Maxg];
frnt=l; rear=0;
Игнорируя возможность
Инициализация очереди
#define Maxg
float
git[Maxg];
f rnt =
= Maxg;
FIFO (FIRST INPUT — FIRST OUTPUT)
Рис. 2.12
1. Операция проверки пустоты очереди empty
if(frnt == NULL && rear == NULL; printf("Очередь пуста.");
2. Операция удаления элемента из
Бинарные деревья
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями. Ка
Узел дерева
struct tnode
{
char *word; /^указатель на поле info*/
struct tnode *left; /*левый потомок*/ struct tnode *right; /*правый потомок*/
Функция обхода дерева снизу вверх
void
{
i
{
inorder (struct node
*t)
f (t!=NULL)
&nbs
Алгоритм последовательного поиска
for ( search=-l, i=0;
i<n;
i + + )
if(key == k[i])
Алгоритм поиска
i = 0;
while ( (
i < ind size)
&a
Алгоритм поиска
low=0; high=n-l; search=-l; while(low<high)
{
mid=(int)(low+high)/2; if (key==k[mid])
{
search=mid;
break; }
if (key<k[m
Хеширование таблиц
Хеширование — один из способов увеличения эффективности поиска [9]. Основная идея хеширования — подобрать некий способ преобразования значения ключа сразу в адрес записи. Таким образо
Сортировка с помощью прямого включения
Элементы массива условно разделяются на готовую последовательность ах,а2, ..., а{. и входную последовательность аи а2, ..
Функция сортировки с помощью метода прямого включения
void insertionSort(int numbers[], int array_size)
{
int i, j , index;
for (i=l; i < array_size; i++)
{
index = numbers[i];
j = i;
Функция сортировки прямым выбором
void selectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;
for( i = 0; i < array_size-l; i++ )
{
min = i;
for( j
Сортировка с помощью прямого обмена
Алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будет отсортирован весь массив. Как и в методе прямого выбора совершаются проходы по массиву, сдвигая каж
Функция сортировки прямым обменом
void bubbleSort(int numbers[], int array_size
{
int i, j , temp;
for( i = 0; i < array size; i++
Сортировка включениями с убывающим приращением
В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сам метод сортировки объясняется и демонстрируется на стандартном примере (рис. 3.5). Сначала отдельно
Функция сортировки Шелла
void shellSort(int numbers[],
{
int i, j, increment, temp;
int array size)
inc
Сортировка
| 06 | 12 I 18 | 42 | 44 | 55 | 67 | эЦ
Рис. 3.5. Пример сортировки Шелла
Приводимая программа не ориентирована на некую определенную последовательность расстояний. Все
Сортировка с помощью дерева
Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди п элементов, затем среди п- элементов и так далее. Улучшить сортировку можно в том с
ВЫБОР НАИМЕНЬШЕГО КЛЮЧА
Пирамидальная сортировка
Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева [1, 3, 9, 10, 13]. Пирамидой называется двоичное дерево такое, что
Быстрая сортировка
Рассмотрим усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех трех алгоритмов прямой сортировки. Однако усовершенствова
Функция быстрой сортировки
void quicksort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
Сравнение методов сортировки массивов
Сравним эффективность методов сортировки массивов. Для всех прямых методов сортировки можно дать точные аналитические формулы [3]. Они представлены в табл. 3.5.
Для усовершенствова
Сортировка файлов методом прямого слияния
Алгоритмы сортировки, рассмотренные ранее, неприменимы, если сортируемые данные расположены в файле с последовательным доступом (на диске), который характеризуется тем, что в каждый момент имеется
Третье разбиение и слияние приводят к нужному результату
Об, 12, 18, 42, 44, 55, 67, 94
Операция, которая однократно обрабатывает множество данных, называется фазой, а наименьший подпроцесс, который, повторяясь, образует процесс сортировк
Первая версия программы сортировки с помощью простого слияния имеет следующий вид
int i,
j,
k, 1;
int up
, p;
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Ахо, А.В. Структуры данных и алгоритмы/А.В. Ахо, Д.Д. Ульман, Д.Э. Хопкрофт; пер. с англ. и ред. А.А. Минько. — М.:Вильямс, 2000. — 384 с.
2. Болски, М.И. Язык программирования Си: спра
Новости и инфо для студентов