А.А. Белеванцев, С.С. Гайсарян, Л.С. Корухова, Е.А. Кузьменкова, В.С. Махнычев. Семинары по курсу Алгоритмы и алгоритмические языки (1108027), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Найти сумму всех элементов списка L.struct listnode *p;int sum = 0;p = L;while (p != NULL) {sum += p->elem;p = p->next; // движение по списку вправо}printf ("%d\n", sum);Для облегчения операций добавления и удаления звеньев в списки используютсписки с заглавным звеном. В таких списках всегда содержится хотя бы одно (первое)звено, которое и называют заглавным; в заглавном звене не хранят никаких данных. Длясписка с заглавным звеном указатель на его начало никогда не изменяется, посколькузаглавное звено списка не меняется. Это позволяет писать более компактный код.Пример 3. Описать функцию, которая добавляет в конец заданного списка звено сзаданным целым значением.а) для списка без заглавного звена:void insert (struct listnode **L, int x) {struct listnode *p, *q;p = (struct listnode*) malloc (sizeof (struct listnode));p->elem = x;p->next = NULL;if (*L == NULL) {// пустой список: меняется указатель на начало*L = p;} else {q = *L;// непустой список: находим последнее звеноwhile (q -> next != NULL)q = q->next;q->next = p;}}Пример вызова такой функции:insert (&L, 10);59Другой вариант решения этой задачи – возвращать указатель на новое началосписка, чтобы избежать работы с двойными указателями:struct listnode * insert (struct listnode *L, int x) {struct listnode *p, *q;p = (struct listnode*) malloc (sizeof (struct listnode));p->elem = x;p->next = NULL;if (L == NULL) {// список был пуст, новый список будетreturn p; // начинаться с указателя р} else {q = L; // находим последнее звеноwhile (q->next != NULL)q = q->next;q->next = p;return L; // указатель на начало списка не изменился}}Пример вызова такой функции:L = insert (L, 10);б) для списка с заглавным звеном:void insert (struct listnode *L, int x) {struct listnode *p, *q;p = (struct listnode*) malloc (sizeof (struct listnode));p->elem = x;p->next = NULL;q = L; // список точно не пуст: есть хотя бы заглавное звеноwhile (q -> next != NULL)q = q->next;q->next = p;}Пример вызова такой функции:insert (L, 10);В дальнейшем будут подразумеваться однонаправленные некольцевые списки беззаглавного звена, если иное не указано явно.Пример 4.

Описать функцию, удаляющую все звенья из заданного списка.struct listnode* erase (struct listnode *L) {struct listnode *p;while (L != NULL) {p = L;L = L->next;free (p);}return NULL;}Рекурсивное решение нередко оказывается короче нерекурсивногобыстродействие рекурсивных решений, как правило, ниже):60(хотяstruct listnode *erase (struct listnode *L) {if (L != NULL) {erase (L->next);free (L);}return NULL;}10.1.1.

Задачи для самостоятельного решенияСписки.Замечание. В задачах 10.1.1. – 10.1.11. считать, что под списком подразумеваетсяоднонаправленный некольцевой список без заглавного звена, в звеньях которого хранятсяцелые числа (int).10.1.1.

Описать функцию sum2(L), возвращающую сумму последнего ипредпоследнего чисел в списке L (если они есть).10.1.2. Описать функцию max(L), возвращающую максимальное значение внепустом списке L.10.1.3. Описать функцию has_duplicate(L), определяющую, есть ли в списке Lхотя бы два звена с одинаковыми числами.10.1.4. Описать функцию, которая получает в качестве параметра массив и строитпо нему список, содержащий те же элементы в том же порядке. В качестве результатафункция возвращает указатель на начало построенного списка. (Рекомендация: строитьсписок с конца.)10.1.5.

Описать функцию copy(L), которая строит копию списка L и возвращаетуказатель на начало нового списка.10.1.6. Описать функцию reverse(L), изменяющую порядок чисел в списке L напротивоположный. (Рекомендация: строить новый список, добавляя элементы в егоначало.)10.1.7. Описать функцию insert(L, X), которая вставляет в упорядоченный понеубыванию список L число X так, чтобы результирующий список был также упорядоченпо неубыванию.10.1.8. Описать функцию same(L1, L2), которая определяет, являются лисписки L1 и L2 одинаковыми (назовем списки одинаковыми, если они содержат одни и теже числа в одинаковом порядке).10.1.9.

Описать функцию filter(L1, L2), которая удаляет из списка L1 всечисла, которые содержатся в списке L2.10.1.10. Описать функцию sort(L), упорядочивающую список L по неубыванию.10.1.11. Описать функцию merge(L1, L2), которая из двух упорядоченных понеубыванию списков L1 и L2 строит новый список, содержащий все числа из этих двухсписков и также упорядоченный по неубыванию.а) новый список строится из звеньев L1 и L2; функция не должна создавать новыхзвеньев;61б) новый список строится из копий звеньев L1 и L2; списки L1 и L2 неизменяются.10.1.12. Считая, что L – однонаправленный кольцевой список без заглавного звена,описать функцию insert(L, X), которая вставляет число Х в начало списка L.10.1.13.

Считая, что L – двунаправленный некольцевой список без заглавногозвена, описать функцию delete(L, X), которая удаляет из списка L все звенья,хранящие число Х (если они есть).10.2. Стек. ОчередьНа практике нередко встречается необходимость откладывать обработкунекоторых данных на более позднее время. Для организации такой отложенной обработкииспользуют, в частности, стеки и очереди. И стек, и очередь определяют две основныеоперации: добавление элемента в структуру данных и извлечение первого элемента изструктуры данных.Стек (англ.

stack) – структура данных, предоставляющая доступ к элементам впорядке, обратном порядку добавления. То есть элемент, добавленный в стек последним,будет возвращен первой же операцией извлечения. Операцию добавления в стек принятоназывать push, а операцию извлечения из стека – pop.В случае очереди элементы извлекаются в том же порядке, в котором они былидобавлены. Функции, реализующие добавление и извлечение из очереди, рекомендуетсяназывать enqueue и dequeue соответственно.Стек и очередь могут быть реализованы, например, с помощью однонаправленныхсписков или с помощью динамических массивов; выбор зависит от конкретной задачи.Всю работу по поддержанию стека или очереди обычно выносят в отдельный модуль(достаточно описать пять функций: создание структуры данных, ее уничтожение,добавление нового элемента, извлечение элемента, проверка на пустоту).

Такой подходпозволяет отделить логику решения задачи от реализации структуры данных, благодарячему можно, например, легко заменить в программе одну реализацию стека на другую илииспользовать одну и ту же реализацию стека в разных задачах.Пример реализации стека с помощью динамического массива:typedef int datatype; // тип данных, хранимых в стекеtypedef struct { // структура - представление стекаdatatype *items;int size; // размер стекаint sp; // номер последнего занятого} stack;// функции для работы со стекомvoid init_stack (stack *st) {st->size = 16;st->sp = -1;st->items = malloc (16 * sizeof (datatype));}62void delete_stack (stack *st) {free (st->items);}void push (stack *st, datatype value) {if (st->sp == st->size - 1) {st->size = st->size * 2;st->items = realloc (st->items,st->size * sizeof (datatype));}st->items[++st->sp] = value;}void pop (stack *st, datatype *value) {if (st->sp < 0) {printf ("Стек пуст!");exit (1);}*value = st->items[st->sp--];}int empty_stack (stack *st) {return st->sp < 0;}Пример использования стека.Считая, что описан тип stack (datatype = char), а также функцииinit_stack, delete_stack, push, pop, empty_stack для работы со стеком,описать нерекурсивную функцию reverse, которая вводит с клавиатуры текст —последовательностьсимволов,оканчивающуюсяточкой,ивыводитэтупоследовательность в обратном порядке.void reverse (void) {stack st;char c;init_stack (&st);while ((c = getchar ()) != '.')push (&st, c);while (!empty_stack (&st)) {pop (&st, &c);putchar (c);}delete_stack (&st);}Пример реализации очереди с помощью массива:typedef int datatype; // тип данных, хранимых в очередиenum { max_queue_size = 256 };typedef struct { // структура - представление очередиdatatype items[max_queue_size];int head; // индекс первого элемента в очередиint size; // количество элементов в очереди} queue;// функции для работы с очередью63void init_queue (queue *q) { q->head = 0; q->size = 0; }void delete_queue (queue *q) { }void enqueue (queue *q, datatype value) {if (q->size >= max_queue_size) {printf ("Очередь переполнена!\n");exit (1);}q->items[(q->head + q->size) % max_queue_size] = value;q->size++;}void dequeue (queue *q, datatype *value) {if (q->size == 0) {printf ("Очередь пуста!\n");exit(1);}*value = q->items[q->head];q->head = (q->head + 1) % max_queue_size;q->size–-;}int empty_queue (queue *q) { return q->size == 0; }10.2.1.

Характеристики

Список файлов семинаров