- •Отображает данные, вводимые в ручную, во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, полоски со штрих кодом и т.д.).
- •Символ отображает хранимые данные в виде, пригодном для обработки. Носитель данных не определен. В схемах алгоритмов он предназначен для обозначения ввода-вывода данных в случае использования запоминающего устройства, управляемого процесса.
- •Тема 1. Основные этапы решения задач на ЭВМ
- •Постановка задачи разработки программного обеспечения
- •Анализ формальной постановки задачи
- •Выбор или разработка математической модели и метода решения
- •Разработка алгоритма
- •Базовые структуры алгоритма
- •Тема 2. Жизненный цикл программы. Критерии качества программы.
- •Техническое задание и спецификация программы
- •Разработка проекта программной системы
- •Программирование (кодирование) или программная реализация алгоритмов
- •Тестирование и отладка
- •Эксплуатация и сопровождение
- •Критерии качества программного обеспечения
- •Тема 3. Схемы алгоритмов, данных, программ
- •Символы данных
- •Символы процесса
- •Символы линий
- •Специальные символы
- •Правила применения символов в схемах
- •Правила выполнения соединений
- •Специальные условные обозначения
- •Тема 4. Язык программирования высокого уровня Си
- •Общие сведения о языке Си
- •Алфавит языка Си
- •Грамматика для описания языка, синтаксические диаграммы
- •Структура программы на языке Си
- •Имена объектов в программе
- •Выражения, операции и приоритеты
- •Тема 5. Стандартные типы данных
- •Тема 6. Составные типы данных
- •Данные регулярного типа (массивы)
- •Строки
- •Данные комбинированного типа (структуры)
- •Перечисления
- •Объединения
- •Указатели
- •Тема 7. Представление основных управляющих структур программирования
- •Оператор присваивания
- •Составной оператор
- •Оператор перехода Goto
- •Условный оператор If
- •Оператор выбора switch
- •Операторы цикла while, do – while, for
- •Операторы прерывания циклов
- •Форматированный ввод данных
- •Форматированный вывод данных
- •Преобразование типов
- •Инициализация данных
- •Тема 8. Функции
- •Определение функций в языке Си
- •Вызов функций в языке Си
- •Рекурсивные функции
- •Тема 9. Файлы
- •Тема 10. Приемы программирования. Примеры алгоритмов
- •Алгоритмы сортировки
- •Алгоритмы поиска
- •Динамические структуры данных
- •Линейные списки
- •Стек, очередь, дек
- •Деревья
- •Приложение 1. Стандартные библиотеки языка Си
- •Приложение 2. Примеры реализации алгоритмов
- •Не рекурсивный алгоритм решения задачи Ханойская башня.
- •Рекурсивный алгоритм решения задачи Ханойская башня.
- •Приложение 3. Лабораторные работы
- •Лабораторная работа №1
- •Лабораторная работа №2
- •Лабораторная работа №3
- •Лабораторная работа №4
- •Лабораторная работа №5
- •Лабораторная работа №6
- •Лабораторная работа №7
- •Лабораторная работа №8
- •Лабораторная работа №9
- •Лабораторная работа №10
- •Лабораторная работа №11
- •Лабораторная работа №12
- •Список литературы
Пример 34. Напишем процедуру обохода списока с целью вывода его содержимого на экран и поиска совпадающей строки, а также функцию перехода к узлу списка по номеру.
void PrintSearchList (list head, int val)
//Head – указатель на голову списка, str – искомая строка
{
bool lfound = false; // признак того, что строка найдена
tail = &head; //начинаем с головы списка
while (tail != NULL)// если указатель на текущий элемент списка не пуст
{printf("%d\n", tail->value); //выводим информационное поле списка if (tail->value = val) lfound = true; //совпадает с искомой строкой? tail = tail->next; //переходим к следующему узлу списка
}
}
if (lfound) printf("Элемент в списке найден!"); else printf("Элемент в списке не найден!");
list GotoNode (list head, int cnt)
//Cnt – номер узла, начиная с 1, к которому нужно перейти
{
int i = 1; tail = &head;
while ((tail->next != NULL) && (i < cnt))
{ i++;
} tail = tail->next;
return(*tail);
}
Стек, очередь, дек
Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Говорят, что стек реализует дисциплину обслуживания LIFO (Last In
– First Out, последним пришел – первым ушел). Физически стек может быть реализован на основе массива или на основе односвязанного линейного списка, в котором все операции осуществляются только с головой списка. Этот элемент в стеке называется верхушкой стека и на него указывает указатель стека ptrStack (рис.43). Если указатель стека – пустой, то стек считается пустым.
Стек должен поддерживать следующие операции:
push – добавить (положить) в верхушку стека новый элемент; pop – извлечь из верхушки стека элемент;
isEmpty – проверка, пуст ли стек;
top – узнать (прочитать) значение верхушки стека (не удаляя ее);
156
size – узнать количество элементов в стеке;
clear – очистить стек (удалить из него все элементы).
ptrStack |
|
|
|
Верхушка стека |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.43. Графическое изображение стека
Поскольку стек с точки зрения программной реализации является частным случаем односвязного линейного списка, то на языке Паскаль стек можно описать с помощью следующих структур:
struct st // объявление типа stack
{
char info; информационная часть
struct st *ps; // указатель на предыдущий (более нижний) элемент стека } stack;
Стек имеет очень широкое применение в программировании. Особенно часто он используется при решении системных задач, задач компиляции и анализа выражений. Рассмотрим наиболее характерный пример использования стека при переводе выражений в обратную польскую запись.
Обратная польская запись (ОПЗ) – это способ записи выражений (как правило алгебраических) в так называемом постфиксном (или суффиксном) виде, т.е. в таком виде, когда сначала записываются все операнды, а потом выполняемые над ними операции, т.е. для обычных бинарных операций сложения, вычитания, умножения и деления знак операции располагается после операндов, а не между ними как в привычном «инфиксном» виде. Одна из особенностей ОПЗ – отсутствие скобок, что позволяет вычислять ОПЗ за один проход слева направо. ОПЗ как правило используется в трансляторах и компиляторах для преобразования выражений в машинный код, их последующего вычисления, а также для анализа и трансляции синтаксических конструкций языка к виду, удобному для генерации машинного кода.
157
Пример 35. Представим выражение (a+b)/(c/a*c – e*d) в постфиксном
виде:
ОПЗ: ab+ca/c*ed*–/. Вычислим ОПЗ слева на право, при вычислении пользуемся правилом: «в операции участвуют два операнда, расположенные слева от знака операции».
1.Первое вычисление: R1 = ab+ = a+b, подставляем в исходную строку вместо ab+ вычисленный результат R1 получается ОПЗ: R1ca/c*ed*–/.
2.Второе действие: R2 = ca/ = c/a
ОПЗ: R1R2c*ed*–/
3. Третье действие: R3 = R2c* = R2*c = c/a*c
ОПЗ: R1R3ed*–/
4.Четвертое действие: R4 = ed* = e*d
ОПЗ: R1R3R4–/
5.Пятое действие: R5 = R3R4– = R3–R4 = c/a*c–e*d
ОПЗ: R1R5/
6.Шестое действие: R6 = R1R5/ = R1/R5=(a+b)/(c/a*c–e*d)
ОПЗ: R6
ОПЗ вычислено и его значением стало значение выражения R6.
Наиболе известным алгоритмом перевода простого алгебраического выражения в ОПЗ является алгоритм Дейкстры (Э́дсгер Ви́бе Де́йкстра,1930– 2002, – выдающийся нидерландский ученый, идеи которого оказали огромное влияние на развитие компьютерной индустрии). Идея алгоритма основывается на использовании стека и анализе приоритета операций и заключается в следующем:
1.Исходная строка просматривается посимвольно, слева направо до достижения конца строки.
2.Если встречается символ операция, то эта операция при определенных условиях помещается в стек (затем при определенных условиях операции выталкиваются в выходную строку).
158
3.Если встречаются символы операндов, то они из входной строки поступают сразу в выходную строку.
4.Если встречается открывающаяся скобка, то она всегда помещается в стек.
5.Закрывающаяся скобка ни в стек, ни в выходную строку не помещается. Когда она встречается во входной строке, то из стека выталкиваются все символы до первой встречной открывающейся скобки включительно. При этом знаки операций выталкиваются в выходную строку, а открывающаяся скобка просто удаляется из стека.
6.Необходимо использовать следующие приоритеты операций (табл. 17). Чем больше значение приоритета, тем сильнее операция связывает операнды:
Таблица 17. Приоритеты операций для вычисления ОПЗ
Операции |
( |
+ |
– |
* |
/ |
Приоритет |
0 |
1 |
1 |
2 |
2 |
7.Если во входной строке текущий символ – знак операции, то сравниваются приоритеты операций из строки и верхушки стека.
8.Если приоритет операции из входной строки больше приоритета операции из верхушки стека, то операция из входной строки стека перемещается в стек.
9.В противном случае из стека выталкиваются все операции с приоритетами большими либо равными приоритету операции из входной строки. После чего операция из входной строки помещается в стек.
10.При встрече конца входной строки содержимое стека выталкивается в
выходную строку.
Пример 36. Напишем программу перевода входной строки в ОПЗ.
/* Описание стpуктуpы(элемента стека) */ struct st
{
char c;
}; struct st *next;
struct st *push(struct st *, char);
/* Пpототипы функций */ char DEL(struct st **); int PRIOR(char);
void main(void)
{
// Стек опеpаций пуст struct st *OPERS = NULL;
char a[80], outstring[80];
159
int k, point; do
{ puts("Введите выражение (в конце поставте '=') : "); fflush(stdin);
// Ввод аpифметического выpажения gets(a);
k = point = 0;
// Повтоpяем , пока не дойдем до '=' while(a[k] != '\0' && a[k] != '=')
{ if(a[k] == ')') // Если очеpедной символ - ')', то выталкиваем из
// стека в выходную стpоку все знаки опеpаций до // ближайшей откpывающей скобки
{ while((OPERS->c) != '(') outstring[point++] = DEL(&OPERS);
}
DEL(&OPERS); // Удаляем из стека саму откpывающую скобку
if(a[k] >= 'a' && a[k] <= 'z') // Если очеpедной символ - буква , то
// пеpеписываем её в выходную стpоку outstring[point++] = a[k];
if(a[k] == '(') // Если очеpедной символ - '(' , то заталкиваем её //в стек
OPERS = push(OPERS, '(');
// Если следующий символ - знак опеpации , то:
if(a[k] == '+' || a[k] == '-' || a[k] == '/' || a[k] == '*')
{ if(OPERS == NULL) // если стек пуст записываем в него опеpацию
OPERS = push(OPERS, a[k]); else // если не пуст
// если пpиоpитет поступившей опеpации больше пpиоpитета опеpации на веpшине стека заталкиваем поступившую опеpацию на стек
if(PRIOR(OPERS->c) < PRIOR(a[k])) OPERS = push(OPERS, a[k]); //
else // если пpиоpитет меньше пеpеписываем в выходную стpоку все
// опеpации с большим или pавным пpиоpитетом
{ while((OPERS != NULL) && (PRIOR(OPERS->c) >= PRIOR(a[k]))) // outstring[point++] = DEL(&OPERS);
}
}
OPERS = push(OPERS, a[k]); // записываем в стек поступившую // опеpацию
} k++; // Пеpеход к следующему символу входной стpоки
// После pассмотpения всего выpажения пеpеписываем все опеpации из стека в выходную стpоку и печатаем её
while(OPERS != NULL) outstring[point++] = DEL(&OPERS);
outstring[point] = '\0'; printf("\n%s\n", outstring); fflush(stdin);
} puts("\Повторить (y/n)?");
}
while(getchar() != 'n');
/* Функция push записывает на стек (на веpшину котоpого указывает HEAD) символ a. Возвpащает указатель на новую веpшину стека */
struct st *push(struct st *HEAD, char a)
{
st* PTR = new st; // Выделение памяти
PTR->c = a; // Инициализация созданной веpшины
PTR->next = HEAD; // Подключение её к стеку
160
}
/* Функция DEL удаляет символ с веpшины стека.
Возвpащает удаляемый символ. Изменяет указатель на веpшину стека */ char DEL(struct st **HEAD)
{
struct st *PTR; char a;
if(*HEAD == NULL) return '\0'; // Если стек пуст, возвpащается '\0' PTR = *HEAD; // в PTR - адpес веpшины стека
a = PTR->c;
*HEAD = PTR->next; // Изменяем адpес веpшины стека free(PTR); // Освобождение памяти
}
return a; // Возвpат символа с веpшины стека
// Функция PRIOR возвpащает пpиоpитет аpифметической опеpации int PRIOR(char a)
{
switch(a)
{ case '*': case '/':
return 3; case '-': case '+':
return 2; case '(':
}
}
return 1;
|
|
Таблица 18. |
|
Приведем |
пример |
использования |
Алгоритма |
||||
|
Пример построения ОПЗ |
|
|||||||||
Вх. |
Стек |
Вых строка |
|
Дейкстры |
для |
входной |
строки |
(a+b*c)*(a–b)/(d– |
|||
cимвол |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
( |
( |
|
|
(a+b*d)). Для удобства отображения стека в таблице |
|||||||
a |
( |
A |
|
||||||||
+ |
(+ |
A |
|
«транспонируем» его, т.е. разместим стек в строке, |
|||||||
b |
(+ |
Ab |
|
||||||||
* |
(+* |
ab |
|
развернув по часовой стрелке на 90 градусов, так |
|||||||
c |
(+* |
abc |
|
||||||||
) |
Пусто |
abc*+ |
|
чтобы вершина стека располагалась в конце строки |
|||||||
* |
* |
abc*+ |
|
||||||||
( |
*( |
abc*+ |
|
справа (табл.18). |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||
a |
*( |
abc*+a |
|
|
|
|
|
|
|
|
|
- |
*(- |
abc*+a |
|
|
В программировании, кроме списков и стека |
||||||
|
|
|
|
|
|
|
|
|
|||
b |
*(- |
abc*+ab |
|
|
|
|
|
|
|
|
|
) |
* |
abc*+ab- |
|
часто |
используются подобные |
динамические |
|||||
|
|
|
|
|
|
|
|
|
|||
/ |
/ |
abc*+ab-* |
|
|
|
|
|
|
|
|
|
( |
/( |
abc*+ab-* |
|
структуры, программная |
реализация |
которых |
|||||
|
|
|
|
|
|
|
|
|
|||
d |
/( |
abc*+ab-*d |
|
похожа на списки и стек, но дисциплина доступа к |
|||||||
- |
/(- |
abc*+ab-*d |
|
||||||||
|
|
|
|
|
|
|
|
|
|||
( |
/(-( |
abc*+ab-*d |
|
ним |
и |
набор |
типовых |
операций |
несколько |
||
a |
/(-( |
abc*+ab-*da |
|
||||||||
+ |
/(-(+ |
abc*+ab-*da |
|
видоизменены, к ним относятся очередь и дек. |
|||||||
b |
/(-(+ |
abc*+ab-*dab |
|
||||||||
* |
/(-(+* |
abc*+ab-*dab |
|
|
Очередью (aнгл. queue) называется структура |
||||||
d |
/(-(+* |
abc*+ab-*dabd |
|
|
|||||||
) |
/(- |
abc*+ab-*dabd*+ |
|
данных, в |
которой элементы кладутся |
в конец, а |
|||||
) |
/ |
abc*+ab-*dabd*+- |
|
||||||||
Конец |
Пусто |
|
|
|
|
|
|
|
|
|
|
строки |
abc*+ab-*dabd*+-/ |
|
|
|
|
|
|
|
|
161 |
|
|
|
|
|
|
|
|
|
|
|
|