Учебное пособие 80053

//високосный год

if(d.month<l | | d.month>12) return -1;

if(d.day<l | | d.day>tab days[k][d.month]) return -1;

for(i=1; i<d.month; i++)

d.day+=tab_days[k][i];

return d.day;

}

#include<stdio.h>

void main()

{

DATE d;int N;

puts("Введите число, номер месяца и год.");

scanf("%d%d%d", &d.day, &d.month, &d.year);

N=day_of_year (d) ;

if(N<0) puts("Неверно введена дата!");

else

printf("B %d году этот день с номером %d\n", d.year, N);

}

Задание

1. Изучить:

а) терминологию, которая связана со структурой; б) формат определения структуры; в) формат доступа к полям структуры; г) способ задания массива структур;

10

д) способы доступа к элементам массива структур; е) способы ввода и вывода элементов структур.

2. Используя пример, разработайте алгоритм и составьте программу решения следующей задачи.

Ввести структуру (с полями число, месяц, год) для описания понятия дата. Составить и протестировать функцию, которая:

а) вычисляет интервал (в днях), прошедший между двумя датами;

б) по порядковому номеру дня в году определяет число и месяц года, соответствующие этому дню;

в) по введенной дате распечатывает дату на N дней впе-

ред.

3. Подготовить тестовый вариант программы и исходных данных.

Контрольные вопросы

1.Как определить структуру?

2.Как обратиться к полям структуры?

3.Как обратится к элементу массива структур?

4.Какое ключевое слово начинает определение структуры?

5.Как обратиться к полям структуры через указатель на нее?

6.При помощи какой операции формируется доступ к полям структуры?

7.Опишите объект, для которого надо определить структуру и определите ее.

11

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №4 РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММ СО СПИСКАМИ

Цель практического занятия Цель работы – овладеть практическими навыками рабо-

ты с односвязными списками.

Задание

1. Изучить:

а) способы формирования списка; б) операции над списками: удалить элемент из списка;

добавить элемент в список, найти элемент в списке, способы вывода списка;

в) связный список стек, операции на стеке; г) связный список очередь, операции на очереди.

2. Разработайте алгоритм решения, составьте и отладьте программу решения задачи.

Задача 1

Разработайте рекурсивную функцию для суммирования всех элементов множества целых чисел, хранящихся в связном списке.

Задача 2

Разработайте рекурсивную функцию для перестановки всех элементов указанного списка в обратном порядке.

Контрольные вопросы

1. Как определить объект для списка, элементами которого являются числа.

12

2.Как определить объект для списка, элементами которого являются слова.

3.Как определить объект для списка, элементами которого являются указатели.

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

6.Написать фрагмент программы, который удаляет требуемый элемент из списка.

7.Перечислите информацию, которая необходима, для того чтобы в список добавить элемент со значением равным некоторому числу k.

8.Перечислите информацию, которая необходима для того, чтобы удалить из списка головной (первый) элемент списка.

9.Перечислите информацию, которая необходима для того, чтобы новый элемент стал головным (первым) элементом списка.

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 5 РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММ,

ИСПОЛЬЗУЮЩИХ ОЧЕРЕДИ И СТЕКИ

Цель практического занятия Овладеть навыками алгоритмизации и программирова-

ния задач, в которых используются очереди и стеки.

Теоретические сведения

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

13

цу, в каждой строке которой будут находиться координаты соответствующих пар скобок, т.е. для текста

(. . . .(. . . . . . . . .). . .( . . . . . . . . . . ) . . . . .)

таблица должна быть такой

17 42

61 84

0 95

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

Рассмотрим программу, в которой реализована работа со стеком. В ней использованы функции:

Push() - положить элемент на вершину стека,

рор() - вытолкнуть верхний элемент из стека,

peek() - прочитать значение верхнего элемента, не уда-

ляя сам элемент из стека.

#include <stdio.h>

#include <alloc.h>

#define STACK struct stack

STACK

STACK *next; // поле ссылки на следующий элемент стека

14

};

void push ( STACK **s, int item)

{

STACK *new_n;

new_n = (STACK*)malloc(sizeof(STACK));

// запросили память под новый элемент new_n->info=item; // заносим значение в новый элемент new_n->next=*s; // новый элемент стал головой стека

*s=new_n; // указателю *s присвоили адрес головы стека

}

int pop (STACK **s, int *error)

{

STACK *old=*s; int info=0;

if(*s) // стек не пуст

{ info=old->info; *s=(*s)->next;

free(old); //освобождаем память из-под выбранного элем. *error=0; // элемент удален успешно

}

else *error=l; return(info);

}

int peek (STACK **e, int *error)

{

if (*s) { *error=0; return(*s)->info; }

15

else { *error=l; return 0;}

}

Задание 1

В файле находится текст, в котором используются скобки трех типов: ( ), | |, { }. Используя стек, проверить, соблюден ли баланс скобок в тексте.

Задание 2

Создайте стек с положительными и отрицательными числами.

Создайте новый стек, содержащий только положительные числа из первого стека.

Задание 3

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

a+(45-f(x)*(b-c)) надо напечатать 8 10; 12 16; 3 17);

б) открывающих скобок (например, для текста a+(45-f(x)*(b-c)) надо напечатать 3 17; 8 10; 12 16).

16

Контрольные вопросы

1.Что такое стек?

2.Какие Вы знаете способы организации стека?

3.Какие операции могут быть реализованы для стеков?

4.Что такое очередь?

5.Какие Вы знаете способы организации очереди?

6.Какие операции могут быть реализованы с очередью?

7.В какой из этих структур данных могут применяться приоритеты?

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 6 ПРОГРАММИРОВАНИЕ ЗАДАЧ С ДЕРЕВЬЯМИ

Цель практического занятия Овладеть навыками алгоритмизации и программирова-

ния задач, в которых используются деревья.

Теоретические сведения

Дерево состоит из элементов, называемых узлами (вершинами). Узлы соединены между собой направленными дугами. В случае X->Y вершина X называется предшественником (родителем), a Y - преемником (сыном). Дерево имеет единственный узел - корень, у которого нет предшественников. Любой другой узел имеет ровно одного, предшественника. Узел, не имеющий преемника, называется листом.

Рассмотрим работу с бинарным деревом (в котором у каждого узла может быть только два преемника - левый и правый сын). В некотором смысле двоичное дерево является особым видом связанного списка. Необходимо уметь:

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

узле;

17

удалить заданный элемент; обойти все элементы дерева (например, чтобы над каж-

дым из них провести некоторую операцию).

Для того чтобы вставить новый элемент в дерево, надо найти для него место. Для этого, начиная с корня, будем сравнивать значения узлов (Y) со значением нового элемента (NEW). Если NEW < Y , то пойдем по левой ветви; в противном случае - по правой. Когда дойдем до узла, из которого выходит нужная ветвь для дальнейшего поиска, это означает что место под новый элемент найдено.

При удалении узла из дерева возможны три ситуации:

а) исключаемый узел – лист (в этом случае надо просто удалить ссылку на данный узел);

б) из исключаемого узла выходит только одна ветвь; в) из исключаемого узла выходят две ветви (в таком слу-

чае на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева).

Задание

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

struct NОDE

{

char *word;

int k;

struct NODE *left;

struct NODE *right;

}

18