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

 

Замечание: в задачах 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. Программа. Упорядочить по алфавиту и распечатать все слова входного текста.

 

 

ВВОД-ВЫВОД

 

Стандартный ввод-вывод

 

7.1. Программа. Даны натуральные числа i, n (i £ n), вещественные числа a₁, a₂, …,a_n. Найти среднее арифметическое всех чисел, кроме a_i.

 

7.2. Программа. Даны вещественные числа a₁, a₂, …,a₅₀. Распечатать “сглаженные” значения a₁, a₂, …,a₅₀, заменив в исходной последовательности все члены, кроме первого и последнего, по формуле

a_i = (a_i-1 + a_i + a_i+1)/3 i = 2, 3, …,49;

считая, что

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

b) при “сглаживании” используются лишь старые члены последовательности.

 

7.3. Программа. Даны вещественные числа a₁, a₂, … Известно, что a₁ > 0 и что среди a₂, a₃, … есть хотя бы одно отрицательное число. Пусть a₁, a₂, …,a_n - члены данной последовательности, предшествующие первому отрицательному члену (n заранее неизвестно). Распечатать

a) a₁ + a₂ + … +a_n

b) a₁ * a₂ * …* a_n

c) среднее арифметическое a₁, a₂, …,a_n

d) a₁, a₁ * a₂, a₁ * a₂ * a₃,…, a₁ * a₂ * …* a_n

e) a₁ + 2*a₂ + 3*a₃ + … + (n-1)*a_n-1 + …n*a_n

f) | a₁ - a₂ |, | a₂ - a₃ |, …, | a_n-1 - a_n |, | a_n - a₁ |

 

7.4. Программа. Даны целые положительные числа n, a₁, a₂, …, a_n
(n ³ 4). Считать, что a₁, a₂, …, a_n - это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 метров. По этим результатам составить команду из четырех лучших бегунов для участия в эстафете 4´100, т.е. распечатать номера спортсменов, имеющих четыре лучших результата.

 

7.5. Верно ли решена следующая задача: «читать символы из стандартного входного потока, пока код каждого следующего символа больше кода предыдущего; определить, сколько символов было прочитано»

a)... i = 0;

while (getchar() < getchar()) i = i + 2;

b) … i = 0; c = getchar();

while (c < (c = getchar())) i++;

c) … i = 0; c = getchar();

while (c < (d = getchar())) { i++; c = d;}

d) … i = 0; c = getchar();

while (d = getchar(), c<d)) { i++; c = d; }

e) … i = 0; c = getchar();

while (c!= EOF && (d = getchar())!= EOF && c<d) { i++; c=d; }

 

7.6. Сравнить следующие фрагменты программы:

a) while (c = getchar() = EOF)

b) while (c = getchar() == EOF)

c) while ((c = getchar()) == EOF)

d) while ((c = getchar()) = -1)

 

7.7. Допустимо ли в Си? Если "да" - опишите семантику этих действий; если "нет" - объясните почему.

int i,k,sum;

for (i=1; scanf("%d",&k) == 1; i++)

printf("i = %d, k = %d, sum = %d\n", i, k, sum+=k);

 

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

 

7.9. Программа. Дана непустая последовательность слов из прописных (больших) латинских букв. Слова разделены пробелом; признак конца текста – точка.

a) подсчитать количество слов в этом тексте;

b) подсчитать количество слов, у которых совпадают первая и последняя буквы;

c) подсчитать количество слов, являющихся некоторым фрагментом латинского алфавита;

d) подсчитать количество слов, содержащих все буквы, которые входят в состав слова UNIX.

 

7.10. Программа. Дана непустая последовательность слов, разделенных пробелом; признак конца текста – точка. Длина каждого слова – не более 20 литер.

a) распечатать все слова, у которых не совпадают первая и последняя буквы;

b) распечатать все слова, являющиеся «перевертышами», т.е. словами, одинаково читающимися слева направо и справа налево;

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

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

 

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

 

7.12. Программа. Дана непустая последовательность слов из строчных (малых) латинских букв. Слова разделены пробелом; признак конца текста – точка. Напечатать все буквы, которые

a) чаще других встречаются в данном тексте;

b) входят в каждое слово данного текста;

c) входят в наибольшее количество слов данного текста;

 

Работа с файлами

 

Замечание: в задачах 7.13 – 7.21 содержимое файлов только анализируется; в остальных задачах этого раздела создается новый файл(ы) либо изменяется содержимое данного.

 

7.13. Программа. Определить, сколько раз в данном файле f встречается символ ‘A’.

7.14. Программа. Определить, сколько раз в данном файле g встречается строка UNIX.

7.15. Программа. Распечатать все строки данного файла, содержащие заданную строку в качестве подстроки. Имя файла и строка задаются в командной строке.

7.16. Написать программу, определяющую какой символ чаще других встречается в данном файле. Имя файла задается в командной строке.

 

7.17. Написать программу, определяющую сколько строк, состоящих из одного, двух, трех и т.д. символов, содержится в данном файле. Считать, что длина каждой строки - не более 80 символов. Имя файла задается в командной строке.

7.18. Программа. Определить, какая строка является самой длинной в заданном файле. Если таких строк несколько, то в качестве результата выдать первую из них. Имя файла задается в командной строке.

 

7.19. Программа. Даны два непустых файла. Определить номер строки и номер символа в этой строке, где встречается первый символ, отличающий содержимое одного файла от другого. Если содержимое файлов полностью совпадает, то результат – 0, 0 и соответствующее сообщение; если один из файлов является началом другого, то результат - n+1, 1, где n - количество строк в коротком файле, и соответствующее сообщение. Имена файлов задаются в командной строке.

 

7.20. Программа. В файле записана непустая последовательность целых чисел (целое число – это непустая последовательность десятичных цифр, возможно начинающаяся знаком + или -). Имя файла задается в командной строке.

a) найти наибольшее из этих чисел;

b) определить, сколько четных чисел содержится в файле;

c) определить, составляют ли эти числа арифметическую прогрессию;

d) определить, образуют ли эти числа возрастающую последовательность;

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

 

7.21. Написать программу, определяющую, какая из строк чаще других встречается в данном файле.

 

7.22. Написать программу, создающую файл - копию заданного файла. Имена файлов задаются в командной строке.

 

7.23. Программа. Создать файл, являющийся конкатенацией других файлов. Имена файлов задаются в командной строке: fres f1 f2 …, где fres - имя файла-результата, f1, f2, … - файлы, содержимое которых должно быть записано в файл-результат.

 

7.24. Программа. Дан файл f. Создать файл g, полученный из файла f заменой всех его прописных латинских букв соответствующими строчными.

 

7.25. Программа. Дан файл f. Создать два файла f1 и f2 следующим образом: в файл f1 записать в том же порядке все строки из файла f, состоящие только из латинских букв (прописных и строчных);в файл f2 – строки файла f, состоящие только из цифр; все остальные строки файла f не записываются ни в один из этих файлов.

7.26. Программа. В конец файла f приписать строку FINISH.

 

7.27. Программа. В конец файла f приписать содержимое файла g.

 

7.28. Программа. Даны два файла, строки в которых упорядочены по алфавиту. Написать программу, осуществляющую слияние этих двух файлов в третий, строки которого тоже упорядочены по алфавиту. Имена всех трех файлов задаются в командной строке.

 

7.29. Программа. Дан файл и две строки. Все вхождения первой строки в файл заменить второй строкой (вхождения первой строки в качестве подстроки не рассматривать). Имя файла и строки задаются в командной строке.

 

7.30. Программа. Дан файл и две строки. Все вхождения первой строки в файл (в том числе и в качестве подстроки) заменить второй строкой. Имя файла и строки задаются в командной строке.

 

7.31. Программа. В данном файле символы каждой строки упорядочить по алфавиту. Имя файла задается в командной строке.

 

7.32. Программа. Строки данного файла упорядочить по алфавиту. Имя файла задается в командной строке.

 

7.33. Программа. В данном файле упорядочить все строки по возрастанию их длин. Имя файла и максимальная длина строки задаются в командной строке.

7.34. Программа. В файле записана непустая последовательность целых чисел, являющихся числами Фибоначчи (см. задачу 3.34). Приписать еще одно, очередное число Фибоначчи.

 

7.35..Программа. В файле записана непустая последовательность целых чисел (целое число – это непустая последовательность десятичных цифр, возможно начинающаяся знаком + или -). Создать новый файл, где

a) все отрицательные числа заменены нулем;

b) минимальный элемент последовательности поставлен в ее начало, а максимальный – в конец;

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

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

Имена файлов задаются в командной строке.

 

ИНТЕРФЕЙС С СИСТЕМОЙ UNIX

Низкоуровневый ввод-вывод

 

Замечание: во всех задачах этого раздела при вводе-выводе использовать низкоуровневые средства системы UNIX.

 

8.1. Верно ли решена задача: «написать версию функции
int getchar(void), которая осуществляет небуферизованный ввод, читая по одной литере из входного потока»

a) int getchar (void)

{ char c;

return (read (0, &c, 1) == 1)? c: EOF);

}

b) int getchar (void)

{ int c;

return (read (0, &c, 1) == 1)? c: EOF);

}

c) int getchar (void)

{ char c;

return (read (0, &c, 1) == 1)? (unsigned char)c: EOF);

}

d) int getchar (void)

{ char c;

return (read (0, &c, 1) == 1)? (int)c: EOF);

}

 

8.2. Написать буферизованный вариант функции int getchar(void), когда функция осуществляет ввод большими порциями, но при каждом обращении к ней выдает только одну литеру.

 

8.3. Используя низкоуровневый ввод-вывод, реализовать следующие функции:

a) int putchar (int c)

b) char *gets (char *s)

c) int puts (const char *s)

 

8.4. Написать программу, копирующую свой стандартный ввод в стандартный вывод.

 

8.5. Написать программу, создающую файл - копию заданного файла. Имена файлов задаются в командной строке.

a) копирование по одной литере;

b) копирование блоками;

 

8.6. Программа. Создать файл, являющийся конкатенацией других файлов. Имена файлов задаются в командной строке (см. задачу 7.23).

 

8.7. Описать функцию, удваивающую в заданном файле каждую очередную четверку байт.

 

8.8. Программа. В каждом из данных файлов удалить те N–ки байт, в которых первый байт равен коду символа s. Имена файлов, символ s и величина N задаются в командной строке.

 

8.9. Описать функцию, определяющую количество символов s в тексте, состоящем из нечетных N-ок байт заданного файла. Имя файла, символ s и величина N – параметры функции.

 

8.10. Программа. Создать файл, содержащий значения функции sin(x)*cos(x)*exp(x) на отрезке [a,b] в точках x_i = a+i*h, h = (b-a)/n, i = 0,1,…,n; имя файла и значения a, b, n задаются в командной строке.

 

8.11. Программа. В файле записана последовательность целых чисел. Создать файл, состоящий из чисел данного файла, значения которых меньше N. Имена файлов и величина N задаются в командной строке.

 

8.12. Программа. В конец файла f приписать

a) число 1234;

b) строку “end”;

 

8.13. Программа. В конец файла f приписать содержимое файла g.

 

8.14. Написать программу, приписывающую в конец файла f его содержимое.

8.15. Описать функцию char *get (char *f, int n, int pos), читающую n байт из файла f, начиная с позиции pos.

 

8.16. Программа. Содержимое файлов, длина которых меньше N байт, переписать в новый файл-результат и удалить такие файлы. Файлы, длина которых больше либо равна N байт, не изменяются и не удаляются. Имена файлов и величина N задаются в командной строке: fres f1 f2 …, где fres - имя файла-результата, f1, f2, … - файлы, содержимое которых должно быть проанализировано.

8.17. Написать программу слияния двух файлов в третий. Файл -результат формируется чередованием N-ок символов первого и второго файлов (если один из файлов длиннее другого, то его оставшаяся часть приписывается в конец файла-результата). Имена файлов и величина N задаются в командной строке.

 

Процессы, сигналы