Структуры со сылками на себя

Замечание: в задачах 6.27 – 6.40 речь идет об однонаправленных списках без заглавного звена (если не сказано особо в постановке задачи);

struct lnode { type data; /* поле данных */

struct lnode *next; /*указатель на следующее звено списка */

}

Здесь struct lnode определяет структуру звена списка. Термин “элемент” будем использовать и для звена, и для поля данных в звене, если это не приводит к неоднозначности. Тип данных type уточняется в каждой задаче.

6.27. Описать функцию, которая

a) находит сумму всех элементов списка;

b) находит максимальный элемент в заданном непустом списке;

c) проверяет, упорядочены ли по возрастанию элементы списка.

d) находит сумму минимального и максимального элементов в
списке;

Тип данных – int.

6.28. Описать функцию, которая

a) меняет местами первый и последний элементы списка;

b) удаляет из списка первое вхождение элемента с заданным значением (если оно есть);

1) список с заглавным звеном;

2) список без заглавного звена;

c) удаляет из списка все вхождения элемента с заданным значением (если они есть);

1) список с заглавным звеном;

2) список без заглавного звена;

d) после каждого звена с заданным значением вставляет еще одно звено с таким же значением.

Тип данных - double*, анализируются вещественные числа.

6.29. Описать функцию, которая определяет, есть ли в заданном списке хотя бы два одинаковых элемента. Тип данных – int.

6.30. Описать функцию, которая печатает в обратном порядке значения элементов списка. Тип данных - double.

6.31. Описать функцию, которая заменяет в списке все вхождения данного слова на удвоенное. Тип данных - char*.

6.32. Описать функцию, которая строит список L2 - копию списка L1.

struct lnode { struct data *p;

struct lnode *next; };

struct data { double f; char *s[2]; };

6.33. Описать функцию, которая переворачивает список, изменяя ссылки. struct lnode { struct data *p;

struct lnode *next; };

struct data { double f; char *s[2]; };

6.34. Описать функцию, которая проверяет, входит ли список L1 в список L2. Тип данных - char*, анализируются строки, указатели на которые хранятся в звеньях списка.

6.35. Описать функцию, которая выполняет слияние двух упорядоченных по возрастанию списков L1 и L2, строя третий список L3:

a) список L3 состоит из звеньев списков L1и L2;

b) список L3 строится из копий звеньев списков L1 и L2; списки L1 и L2 не изменяются.

Тип данных - int*.

6.36. Описать функцию, которая после последнего вхождения элемента E (структуры типа data) в список L1 вставляет список L2, изменяя ссылки.

struct lnode { struct data * dtpr; struct lnode *next; };

struct data { int i; char *s; };

6.37. Описать функцию, которая в упорядоченный по возрастанию список вставляет элемент, сохраняя упорядоченность. Тип данных - char*.

6.38. Описать функцию, которая формирует список L3, включая в него элементы списка L1, которые не входят в список L2.

a) список L3 состоит из звеньев списка L1;

b) список L3 строится из копий звеньев списка L1; список L1 не изменяется.

Тип данных - int*.

6.39. Описать функцию, которая формирует список L3, включая в него в одном экземпляре элементы, входящие в список L1 и в список L2. Список L3 формируется из копий звеньев списков L1 и L2; списки L1 и L2 не изменяются.

Тип данных - char*.

6.40. Описать функцию, которая формирует список L3, включая в него элементы, которые входят в один из списков (L1 или L2), но при этом не входят в другой. Список L3 формируется из копий звеньев списков L1 и L2; списки L1 и L2 не изменяются.

Тип данных - char*.

Замечание: в задачах 6.41 – 6.44 требуется разработать и реализовать несколько абстрактных типов данных (АТД). Абстрактный тип данных – это тип, определяемый программистом, для которого он описывает структуру значений этого типа и множество операций с такими данными. Детали реализации АТД по возможности максимально скрыты от пользователя, и оперировать с такими данными можно только с помощью предоставленных операций (аналогично тому, как пользователь работает с предопределенными в языке типами данных). Поэтому, создавая АТД, надо тщательно продумать, какие операции предоставить пользователю, чтобы их было достаточно для выполнения традиционных действий с этими типами данных.

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

6.42. Описать эффективный способ представления АТД «очередь»: описать структуру этого типа данных, разработать и реализовать набор операций для данных этого типа (в частности, позаботиться о действиях при переполнении очереди).

6.43. Описать способ представления АТД «стек»: описать структуру этого типа данных, разработать и реализовать набор операций для данных этого типа.

6.44. Описать способ представления АТД «набор» Набор – это аналог множества, но в наборе (в отличие от множества) может содержаться несколько экземпляров одного элемента. Разработать и реализовать набор операций для данных этого типа.

Замечание: в задачах 6.45 – 6.47 речь идет о двоичных деревьях;

struct tnode { type data; /* поле данных */

struct tnode *left; /*указатель на левый узел */

struct tnode *right; /*указатель на правый узел */

}

Здесь struct tnode определяет структуру узла дерева. Термин “элемент” будем использовать и для узла, и для поля данных в узле, если это не приводит к неоднозначности. Тип данных type уточняется в каждой задаче.

6.45. Используя определенные в задачах 6.42 и 6.43 АТД «очередь» и «стек», описать нерекурсивную функцию, которая

a) определяет число вхождений данного элемента в двоичное дерево;

b) вычисляет сумму элементов двоичного дерева;

c) находит длину (количество узлов) на пути от корня дерева до ближайшего узла, содержащего данный элемент (если такого узла в дереве нет, то считать результат равным -1);

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

e) подсчитывает количество узлов на N-ом уровне непустого двоичного дерева (корень считать узлом нулевого уровня);

f) печатает все элементы двоичного дерева по уровням, начиная с корня, на каждом уровне – слева направо.

Тип данных – int.

6.46. Описать рекурсивную функцию, которая

a) определяет число вхождений данного элемента в двоичное дерево;

b) вычисляет сумму элементов двоичного дерева;

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

d) печатает значения данных из всех узлов дерева, не являющихся листьями;

e) проверяет, идентичны ли два двоичных дерева;

Тип данных – int.

6.47. Описать функцию, которая в дерево двоичного поиска вставляет новый элемент (определение дерева двоичного поиска см. задачу 6.45(d)).

6.48. Программа. Упорядочить по алфавиту и распечатать все слова входного текста.