Задания к лабораторным работам
1. Найти в массиве и вывести значение наиболее часто встречающегося элемента.
2. Найти в массиве элемент, наиболее близкий к среднему арифметическому суммы его элементов.
3. Разделить массив на две части, поместив в первую элементы, большие среднего арифметического их суммы, а во вторую - меньшие (части не сортировать).
4. Сформировать массив простых чисел, не больших заданного.
5. Сформировать массив простых множителей заданного числа.
6. Найти наименьшее общее кратное всех элементов массива (то есть числа, которое делится на все элементы).
7. Найти наибольший общий делитель всех элементов массива (на который они все делятся без остатка).
8. Интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разбить массив на две части (части не сортировать).
9. Задан массив, определить значение k, при котором сумма |A(1)+A(2)+…A(k)-A(k+1)+…+A(N)| минимальна (то есть минимален модуль разности сумм элементов в правой и левой части, на которые массив делится этим k).
10. Заданы два упорядоченных по возрастанию массива. Составить из их значений третий, также упорядоченный по возрастанию (слияние).
11. Известно, что 1 января 1999 г. пятница. Для любой заданной даты программа должна выводить день недели.
12. Известно, что 1 января 1999 г. пятница. Программа должна найти все " черные вторники" и " черные пятницы" 1999 года (то есть 13 числа).
13. Найти в массиве наибольшее число подряд идущих одинаковых элементов (например {1,5,3,l 6,6,6,6,6,3,4,4,5,5,5} = 5).
14. Составить алгоритм решения ребуса РАДАР=(Р+А+Д)^4 (различные буквы означают различные цифры, старшая - не 0 ).
15. Составить алгоритм решения ребуса МУХА+МУХА+МУХА=СЛОН (различные буквы означают различные цифры, старшая - не 0 ).
16. Составить алгоритм решения ребуса ДРУГ-ГУРД=2727 (различные буквы означают различные цифры, старшая - не 0 ).
17. Составить алгоритм решения ребуса КОТ+КОТ=ТОК (различные буквы означают различные цифры, старшая - не 0 ).
Для заданного варианта написать функцию вычисления суммы ряда. для диапазона значений 0.1 .. 0.9 и шага 0.1 изменения аргумента вычислить значения суммы ряда и контрольной функции, к которой он сходится, с точностью до 4 знаков после запятой.
Для вариантов 6-8 использовать значение sin и cos на предыдущем шаге для вычисления значений на текущем шаге по формулам:
sin(nx) = sin((n-1)x) cos(x) + cos((n-1)x) sin(x)
cos(nx) = cos((n-1)x) cos)x) - sin((n-1)x) sin(x)
В вариантах 3, Bn - числа Бернулли, использовать в виде следующего массива значений для n = 1..11 .
1 1 1 1 5 691 7 3617 43867 174611 854513
-, --, --, --, --, ----, -, ----, -----, -------, ------
6 30 42 30 66 2730 6 510 798 330 138]
__________________________________________________________________________
Вариант Ряд Функция
__________________________________________________________________________
2 n 2n
1 1 - x / 2! + ... + (-1) x / (2n)! cos(x)
__________________________________________________________________________
3 2n-1
2 z=((x-1)/(x+1)) (2/1)z + (2/3)z +...+ (2/2n-1)z ln(x)
__________________________________________________________________________
1 3 2 5 2n 2n 2n-1
3 x + -- x + --- x +...+2 (2 -1) Bn x / (2n)! tg(x)
3 15 ( ряд с n=1 )
__________________________________________________________________________
1 3 1 3 5...(2n-1) 2n+1
4 x + ---x +...+ ----------------- x arcsin(x)
2 3 2 4 6...2n(2n+1)
__________________________________________________________________________
2 n x
5 1+ x ln3 + (x ln3)/2! +...+(x ln 3)/n! 3
__________________________________________________________________________
1 1 1 2 n 1 1 3...(2n-3) n 0.5
6 1+ - x + --- x -...+ (-1) ------------- x (1 + x)
2 2 4 2 4 6...2n
__________________________________________________________________________
n
7 sin(x) - sin(2x) / 2+..+(-1)sin(nx) / n x / 2
__________________________________________________________________________
2 n 2 2 2
8 -cos(x) + cos(2x)/2 +..+(-1) cos(nx)/n 0.25(x - PI /3)
__________________________________________________________________________
1. Выполнить сортировку символов в строке. Порядок возрастания "весов" символов задать таблицей вида c h ar ORD[] = "АаБбВвГгДдЕе1234567890"; Символы, не попавшие в таблицу, размещаются в конце отсортированной строки.
2. В строке, содержащей последовательность слов, найти конец предложения, обозначенный символом "точка". В следующем слове первую строчную бувку заменить на прописную.
3. В строке найти все числа в десятичной системе счисления, сформировать новую строку, в которой заменить их соответствующим представлением в шестнадцатеричной системе.
4. Заменить в строке принятое в Си обозначение символа с заданным кодом (например, \101) на сам символ (в данном случае - A).
5. Переписать в выходную строку слова из входной строки в порядке возрастания их длины.
6. Преобразовать строку, содержащую выражение на Си с операциями (=,==,!=,a+=,a-=), в строку, содержащую эти же операции с синтаксисом языка Паскаль (:=,=,#,a=a+,a=a-).
7. Удалить из строки комментарии вида "/* ... */". Игнорировать вложенные комментарии.
8. Заменить в строке символьные константы вида 'А' на соответствующие шестнадцатеричные (т.е. 'А' на 0x41).
9. Заменить в строке последовательности одинаковых символов (не пробелов) на десятичное число, состоящее из двух десятичных цифр и соответствующее их количеству (т.е. " abcdaaaaa xyznnnnnnn " на " abcd5a xyz7n " ).
10. Найти в строке два одинаковых фрагмента (не включающих в себя пробелы) длиной более 5 символов и возвратить индекс начала первого из них (т.е. для " aaaaaabcdefgxxxxxxbcdefgwwwww" вернуть n=6 - индекс начала " bcdefg" ) .
11. Оставить в строке фрагменты, симметричные центрального символа, длиной более 5 символов (например, " dcbabcd" ), остальные символы заменить на пробелы.
12. Найти во входной строке самую внутреннюю пару скобок {...} и переписать в выходную строку содержащиеся между ними символы. Во входной строке фрагмент удаляется.
13. Заменить в строке все целые числа соответствующим повторением следующего за ними символа (например " abc5xacb15y" - " abcxxxxxacbyyyyyyyyyyyyyyy ") .
14. "Перевернуть" в строке все слова. (Например : "Жили были дед и баба" - "илиЖ илиб дед и абаб").
15. Функция переписывает строку. Если она находит в строке число, то вместо него она переписывает в выходную строку соответствующее по счету слово из входной строки. (например, " aaa bb1bb cc2cc" - " aaa bbaaabb ccbb1bbcc") .
Алгоритм сортировки реализовать в виде функции, возвращающей в качестве результата характеристику трудоемкости алгоритма (например, количество сравнений ). Если имеется базовый алгоритм сортировки (для Шелла - " пузырек" , для Шейкер - " пузырек" , для вставки с двоичным поиском - погружение), то аналогично оформить базовый алгоритм и произвести сравнение эффективности.
1. Сортировка вставками, место помещения очередного элемента в отсортированную часть производить с помощью двоичного поиска. Двоичный поиск оформить в виде отдельной функции.
2. Сортировка Шелла. Частичную сортировку с заданным шагом, начиная с заданного элемента оформить в виде функции. Алгоритм частичной сортировки - вставка погружением.
3. Сортировка разделением. Способ разделения : вычислить среднее арифметическое всех элементов массива и относительно этого значения разбить массив на две части (с использованием вспомогательных массивов).
4. Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр - направление движения (+1/-1) и меняя местами нижнюю и верхнюю границы просмотра.
5. "Быстрая" сортировка с итерационным циклом вычисления медианы. Для заданного интервала массива, в котором производится разделение, ищется медиана обычным способом. Затем выбирается та часть интервала между границей и медианой, в которой находится середина исходного интервала, и процесс повторяется.
6. Сортировка циклическим слиянием с использованием одного выходного и двух входных массивов. Для упрощения алгоритма и разграничения сливаемых групп в последовательности в качестве разделителя добавить " очень большое значение" ( MAXINT) .
7. Сортировка разделением. Способ разделения : интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разбить массив на две части (с использованием вспомогательных массивов).
8. Простое однократное слияние. Разделить массив на n частей и отсортировать их произвольным методом.
Вариант задания реализовать в виде функции, использующей для работы со строкой только указатели и операции вида *p++, p++ и т.д.. Если функция возвращает строку или ее фрагмент, то это также необходимо сделать через указатель.
1. Функция находит в строке заданную подстроку и возвращает указатель на нее. С использованием функции найти все вхождения подстроки в строке.
2. Функция находит минимальный элемент массива и возвращает указатель на него. С использованием этой функции реализовать сортировку выбором.
3. Шейкер-сортировка с использованием указателей на правую и левую границы отсортированного массива и сравнения указателей (см.3.7).
4. Функция находит в строке пары одинаковых фрагментов и возвращает указатель на первый. С помощью функции найти все пары одинаковых фрагментов.
5. Функция находит в строке пары инвертированных фрагментов (например "123apr" и "rpa321") и возвращает указатель на первый. С помощью функции найти все пары.
6. Функция производит двоичный поиск места размещения нового элемента в упорядоченном массиве и возвращает указатель на место включения нового элемента. С помощью функции реализовать сортировку вставками.
7. Функция находит в строке десятичные константы и заменяет их на шестнадцатеричные с тем же значением, например "aaaaa258xxx" на "aaaaa0x102xxx".
8. Функция находит в строке символьные константы и заменяет их на десятичные коды, например "aaa'6'xxx" на "aaa54xxx".
9. Функция находит в строке самое длинное слово и возвращает указатель на него. С ее помощью реализовать размещение слов в выходной строке в порядке убывания их длины.
10. Функция находит в строке самое первое (по алфавиту) слово. С ее помощью реализовать размещение слов в выходной строке в алфавитном порядке.
11. Функция находит в строке симметричный фрагмент вида " abcdcba" длиной 7 и более символов (не содержащий пробелов) и возвращает указатель на его начало и длину. С использованием функции " вычеркнуть" все симметричные фрагменты из строки.
Определить структурированный тип, определить набор функций для работы с массивом структур. В структурированной переменной предусмотреть способ отметки ее как не содержащей данных (т.е. "пустой"). Функции должны работать с массивом структур или с отдельной структурой через указатели, а также при необходимости возвращать указатель на структуру. В перечень функций входят:
- " очистка" структурированных переменных ;
- поиск свободной структурированной переменной ;
- ввод элементов (полей) структуры с клавиатуры;
- вывод элементов (полей) структуры с клавиатуры;
- поиск в массиве структуры и минимальным значением заданного поля;
- сортировка массива структур в порядке возрастания заданного поля (при сортировке можно использовать тот факт, что в Си++ разрешается присваивание структурированных переменных);
- поиск в массиве структур элемента с заданным значением поля или с наиболее близким к нему по значению.
- удаление заданного элемента;
- изменение (редактирование) заданного элемента.
- вычисление с проверкой и использованием всех элементов массива по заданному условию и формуле (например, общая сумма на всех счетах) - дается индивидуально.
Перечень полей структурированной переменной:
1. Фамилия И.О., дата рождения, адрес.
2. Фамилия И.О., номер счета, сумма на счете, дата последнего изменения.
3. Номер страницы, номер строки, текст изменения строки, дата изменения.
4. Название экзамена, дата экзамена, фамилия преподавателя, количество оценок, оценки.
5. Фамилия И.О., номер зачетной книжки, факультет, группа,
6. Фамилия И.О., номер читательского билета, название книги, срок возврата.
7. Наименование товара, цена, количество, процент торговой надбавки.
8. Номер рейса, пункт назначения, время вылета, дата вылета, стоимость билета.
9. Фамилия И.О., количество оценок, оценки, средний балл.
10. Фамилия И.О., дата поступления, дата отчисления.
11. Регистрационный номер автомобиля, марка, пробег.
12. Фамилия И.О., количество переговоров (для каждого - дата и продолжительность).
13. Номер телефона, дата разговора, продолжительность, код города.
14. Номер поезда, пункт назначения, дни следования, время прибытия, время стоянки.
15. Название кинофильма, сеанс, стоимость билета, количество зрителей.
Разработать две функции, одна из которых вводит с клавиатуры набор данных в произвольной последовательности и размещает в памяти в переменном формате. Другая функция читает эти данные и выводит на экран. Программа запрашивает и размещает в памяти несколько наборов данных при помощи первой функции, а затем читает их и выводит на экран при помощи второй. Размещение данных производить в статическом массиве байтов фиксированной размерности с контролем его переполнения.
1. Прямоугольная матрица вещественных чисел, предваренная двумя целыми переменными - размерностью матрицы.
2. Последовательность тестовых строк. Каждая строка ограничена символом \0, последовательность - двумя символами \0.
3. Последовательность строк символов. Каждая строка предваряется байтом - счетчиком символов. Ограничение последовательности - счетчик со значением 0.
4. Упакованный массив целых переменных. Байт-счетчик, имеющий положительное значение n, предваряет последовательность из n различных целых переменных, байт-счетчик, имеющий отрицательное значение -n, обозначает n подряд идущих одинаковых значений целой переменной. Пример:
-исходная последовательность: 2 3 3 3 5 2 4 4 4 4 4 8 -6 8
-упакованная последовательность: (1) 2 (-3) 3 (2) 5 2 (-5) 4 (3) 8 -6 8
5. Упакованная строка, содержащая символьное представление целых чисел. Все символы строки, кроме цифр, помещаются в последовательность в исходном виде. Последовательность цифр преобразуется в целую переменную, которая записывается в упакованную строку, предваренная символом \0. Конец строки - два подряд идущих символа \0. Пример:
-исходная строка: "aa2456bbbb6665"
-упакованная строка: 'a' 'a' '\0' 2456 'b' 'b' 'b' 'b' '\0' 6665 '\0' '\0'
6. Произвольная последовательность переменных типа char, int и long. Перед каждой переменной размещается байт, определяющий ее тип (0-char, 1-int, 2-long). Последовательность вводится в виде целых переменных типа long, которые затем " укорачиваются" до минимальной размерности без потери значащих цифр.
Разработать функцию с переменным количеством параметров. Для извлечения параметров из списка использовать технологию программирования областей памяти переменного формата, описанную в 4.4.
1. Целая переменная - счетчик, затем последовательность вещественных переменных. Функция возвращает сумму переменных.
2. Последовательность целых положительных переменных, ограниченная переменной со значением -1. Функция возвращает максимальную из них.
3. Последовательность переменных различных типов. Перед каждой переменной находится целая переменная - идентификатор типа : 1-целое, 2-длинное целое, 3-вещественнное, 0-конец последовательности. Функция возвращает сумму значений параметров.
4. Первый параметр - строка, в которой каждый символ " *" обозначает место включения строки, являющейся очередным параметром. Функция выводит на экран полученный текст.
5. Первый параметр - форматная строка, в которой каждая цифра обозначает тип очередного параметра : 1-целое, 2-длинное целое, 3-вещественнное. Функция возвращает сумму значений параметров.
6. Каждый параметр - строка, последний параметр - NULL. Функция возвращает строку в динамической памяти, содержащую объединение строк-параметров.
7. Последовательность вещественных положительных переменных, ограниченная переменной со значением -1. Функция возвращает динамический массив, содержащий значения этих переменных.
8. Последовательность указателей на вещественные переменные, ограниченная NULL.. Функция возвращает динамический массив указателей на эти переменные.
9. Последовательность вещественных массивов. Сначала идет целый параметр - размерность массива (int), затем непосредственно последовательность значений типа double. Значение целого параметра - 0 обозначает конец последовательности. Функция возвращает сумму всех элементов.
10. Последовательность вещественных массивов. Сначала идет целый параметр - размерность массива (int), затем указатель на массив значений типа double (имя массива ). . Значение целого параметра - 0 обозначает конец последовательности.
1. Программа умножения целых переменных произвольной длины с использованием операций сложения и сдвига (проверить на переменных типа long).
2. Программа деления целых чисел произвольной длины с использованием операций вычитания и проверки на знак результата (проверить на переменных типа long).
3. Программа умножения чисел произвольной длины, представленных непосредственно строками цифр:
char a1[]="364543453";
char s[20];
add (a1,"345353",s);
4. Программа сложения и вычитания чисел произвольной длины, представленных непосредственно строками цифр:
char a1[]="364543453";
char s[20];
add (a1,"345353",s);
5. Кодирование и декодирование строки символов, содержащих цифры, в последовательность битов. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает, что за ней следует байт (2 цифры) с кодом символа, отличного от цифры. Разработать функции кодирования и декодирования с определением процента уплотнения.
6. Число произвольной длины представлено в двоично-десятичной системе. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает конец последовательности цифр. Разработать функции сложения и вычитания чисел в такой форме представления.
7. Число произвольной длины представлено в двоично-десятичной системе. Десятичная цифра кодируется 4 битами - одной шестнадцатеричной цифрой. Цифра F обозначает конец последовательности цифр. Разработать функцию умножения чисел в такой форме представления.
8. Последовательность целых переменных различной размерности типов char, int, long кодируется следующим образом : перед каждым числом размещаются 2 бита, определяющие размерность числа - 00 - конец последовательности, 01 - char, 10 - int, 11 - long. Разработать функции упаковки и распаковки массива переменных типа long с учетом количества значащих битов и с определением коэффициента уплотнения. Пример : 01 xxxxxxxx 10 xxxxxxxxxxxxxxxx 01xxxxxxxx 00
9. Последовательность целых переменных различной размерности кодируется следующим образом : перед каждым числом размещаются 5 битов, определяющие количество битов в следующем за ним целом числе. 00000 - конец последовательности.
Задание рассчитано на выполнение в течение 2-3 лабораторных занятий и предполагает разработку функций поддержки индексного файла с заданной структурой, заполнение файла данных, построение индекса и выполнение операций поиска, добавления, удаления и обновления записи.
1. Построение двухуровнего индекса. Выполнение операций над записями файла с коррекцией таблиц верхнего и нижнего уровней. Сохранение индекса нижнего уровня в файле. Построение индекса верхнего уровня при открытии индекса.
2. Индексный файл с областью переполнения. Выполнение операций с коррекцией области переполнения и основной области. При превышении размера области переполнения 10% от размера основной области производится операция повторного построения основной области.
3. Индексный файл с индексируемым полем переменной длины. Значение поля хранится в отдельном файле записей переменной длины, а запись файла данных содержит ссылку на него.
4. Файл содержит записи переменной длины текстовые строки, организованные в виде дерева: каждая запись содержит ссылки (адреса в файле) двух других записей. Реализовать операции двоичного поиска и включения записи в файл без чтения в память всего файла. Обеспечить сохранение сбалансированности дерева.
5. Индексный файл представляет собой индексное дерево, которое сохраняется в файле записей фиксированной длины "естественным" образом. Записи индексного файла содержат номера записей файла данных. Индекс считывается в память полностью, для записей первых m уровней (задается при загрузке) обеспечивается считывание и связывание записей файла данных для ускорения поиска по индексу. Обеспечить сохранение сбалансированности дерева.
6. Ключом в файле записей фиксированной длины является поле name[30], содержащее строку ограниченного размера. Реализовать функции добавления, удаления и поиска записей по ключу с использованием метода расстановки ключей (хеширования). Для исключения коллизий использовать область переполнения с организацией списков записей. Предложить функцию расстановки и проверить ее эффективность.
7. Ключом в файле записей является целая переменная. Используется хеширование на основе функции середины квадрата. Размер таблицы изменяется: 16,32,64 и так далее записей. При отсутствии в области переполнения свободного места создается новый файл вдвое большего размера и в него переписываются записи из старого файла с использованием новой функции размещения (количество разрядов в "середине квадрата" увеличивается на 1).
8. Предложить и реализовать способ организации индекса для файла данных, содержащих координаты точек на плоскости.
Варианты 1-6. Используя программу - заготовку
int MENU(int x0, int y0 , char *s , char *m [])
// Возвращает номер выбранной строки меню
// x0,y0 - координаты окна меню
// s0 - надпись на рамке меню
// m - массив указателей на строки меню
реализовать функции редактирования файла. Для вывода на экран редактируемого текста использовать функцию MENU с массивом указателей на строки редактируемого текста. Строки редактируемого текста разместить в динамической памяти. В программе предусмотреть меню основных операции, в которое включить - просмотр текста, добавление строки к тексту и действие над текстом из варианта задания :
1. Удаление, вставка, перемещение строки.
2. Отметка начала и конца блока, удаление, перемещение блока строк.
3. Редактирование выбранной строки: стирание и вставка символов.
4. Поиск по образцу в выделенном блоке и замена на другой образец.
5. Отметка начала и конца блока, копирование блока строк, запись блока в отдельный файл.
6. Чтение файла и включение текста после текущей строки.
7. Функция получает строку текста и возвращает динамический массив указателей на слова. Каждое слово копируется в отдельный массив в динамической памяти.
8. Функция получает массив указателей на строки и возвращает строку в динамической памяти, содержащую объединенный текст из входных строк.
9. Функция получает массив вещественных чисел. Размерность массива - формальный параметр. Функция создает динамический массив указателей на переменные в этом массиве и выполняет сортировку указателей (без перемещения указуемых переменных).
10. Функция получает на вход и возвращает в качестве результата динамический массив указателей на упорядоченные по алфавиту строки и включает в нее копию заданной строки с сохранением упорядоченности. Если после включения размерность массива становится кратной N (k=N,2N,4N....), то создается новый массив указателей, размерность которого в два раза больше, В него переписываются указатели из старого, а старый разрушается.
1. Включение элементов в двусвязный циклический список с сохранением упорядоченности.
2. Включение элементов в односвязный список с сохранением упорядоченности.
3. Включение элементов в двусвязный список с сохранением упорядоченности.
4. Сортировка односвязного циклического списка путем исключения первого элемента и включения в новый список с сохранением его упорядоченности.
5. Сортировка односвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка.
6. Сортировка двусвязного циклического списка путем перестановки соседних элементов.
7. Элемент односвязного списка содержит указатель на строку в динамической памяти. Написать функции просмотра списка и включения очередной строки с сохранением упорядоченности по длине строки и по алфавиту.
8. Элемент односвязного списка содержит массив из 4 целых переменных. Массив может быть заполнен частично. Все значения целых переменных хранятся в порядке возрастания. Написать функцию включения значения в элемент списка с сохранением упорядоченности. При переполнении массива создается новый элемент списка и в него включается половина значений из переполненного.
9. Элемент двусвязного циклического списка содержит указатель на строку в динамической памяти. Написать функции просмотра списка и включения очередной строки с сохранением упорядоченности по длине строки и по алфавиту.
10. Элемент двусвязного циклического списка содержит массив из 4 целых переменных. Массив может быть заполнен частично. Все значения целых переменных хранятся в порядке возрастания. Написать функцию включения значения в элемент списка с сохранением упорядоченности. При переполнении массива создается новый элемент списка и в него включается половина значений из переполненного.
11. Элемент односвязного списка содержит указатель на строку. Вставить строку в конец списка. В список помещается копия входной строки в динамической памяти.
12. Элемент односвязного списка содержит указатель на строку. Строки упорядочены по возрастанию. Вставить строку в список с сохранением упорядоченности. В список помещается копия входной строки в динамической памяти.
13. Элемент односвязного списка содержит указатель на строку. Отсортировать список путем исключения максимального элемента и включения в начало нового списка.
14. Элемент двусвязного циклического списка содержит указатель на строку. Строки упорядочены по возрастанию. Вставить строку в список с сохранением упорядоченности. В список помещается копия входной строки в динамической памяти.
15. Элемент односвязного списка содержит массив указателей на строки. Строки читаются из текстового файла функцией fgets и указатели на них помещаются в структуру данных. Элементы списка и сами строки должны создаваться в динамической памяти в процессе чтения файла. В исходном состоянии структура данных - пуста.
1. Используя фрагмент программы просмотра каталога, приведенный ниже, написать рекурсивную функцию поиска файлов с одинаковыми именами во всех подкаталогах диска. (Структуру данных, содержащую имена найденных файлов можно реализовать в виде глобального односвязного списка).
#include <stdio.h>
#include <dir.h>
#define FA_DIREC 0x10
void showdir(char *dir)
{ struct ffblk DIR; int done; char irname[40];
strcpy(dirname,dir);
strcat(dirname,"*.*");
done=findfirst(dirname,&DIR,FA_DIREC);
while(! done)
{ if (DIR.ff_attrib & FA_DIREC)
{
if (DIR.ff_name[0] != '.')
printf("Подкаталог %s\n",DIR.ff_name);
}
else
printf("Файл %s%s\n",dir,DIR.ff_name);
done=findnext(&DIR);
} }
void main() showdir("E:\\a\\b\\"); }
2. Реализовать рекурсивный алгоритм построения цепочки из имеющегося набора костей домино.
3. Рекурсивная программа обхода дерева и изображения его вершин на экране. Для равномерного размещения вершин н экране программа должна "знать" для каждой вершины интервал позиций экрана, который выделен для данного поддерева и количество вершин в нем. Само дерево можно задать статически (инициализация).
4. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0 ). Написать программу поиска минимального пути для произвольной пары городов.
5. Расстояния между городами заданы матрицей (Если между городами i,j есть прямой путь с расстоянием N, то элементы матрицы A(i,j) и A(j,i) содержат значение N, иначе 0 ). Написать программу поиска минимального пути обхода всех городов без посещения дважды одного и того же города (задача коммивояжера).
6. Задача о восьми ферзях. Разместить на шахматной доске восемь ферзей так, чтобы они не находились " под боем" .
7. Разместить на шахматной доске максимальное количество коней так, чтобы они не находились друг у друга " под боем" .
Программа должна содержать функцию обхода дерева с выводом его содержимого, функцию добавления вершины дерева (ввод), а также указанную в варианте функцию.
1. Вершина дерева содержит указатель на строку. Строки в дереве не упорядочены. Функция включает вершину в дерево с новой строкой в ближайшее свободное к корню дерева место. (То есть дерево должно иметь ветви, отличающиеся не более чем на 1).
2. Вершина двоичного дерева содержит массив целых и два указателя на правое и левое поддерево. Массив целых в каждом элементе упорядочен, дерево в целом также упорядочено. Функция включает в дерево целую переменную с сохранением упорядоченности.
3. Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддерево. Строки в дереве упорядочены по возрастанию. Написать функций включения строки и получения указателя на строку по заданному номеру, который она имеет в упорядоченной последовательности обхода дерева.
4. Элемент дерева содержит либо данные (строка ограниченной длины), либо указатели на правое и левое поддеревья. Строки в дереве упорядочены. Написать функцию включения новой строки. (Обратить внимание на то, что элемент с указателями не содержит данных, и при включении новой вершины вершину с данными следует заменить на вершину с указателями).
5. Вершина дерева содержит целое число и массив указателей на поддеревья. Целые в дереве не упорядочены. Функция включает вершину в дерево с новой целой переменной в ближайшее свободное к корню дерева место. (То есть дерево должно иметь ветви, отличающиеся не более чем на 1).
6. Вершина дерева содержит два целых числа и три указателя на поддеревья. Данные в дереве упорядочены. Написать функцию включения нового значения в дерево с сохранением упорядоченности.
7. Вершина дерева содержит указатель на строку и N указателей на потомков. Функция помещает строки в дерево так, что строки с меньшей длиной располагаются ближе к корню. Если новая строка " проходит" через вершину, в которой находится более длинная строка, то новая занимает место старой, а алгоритм включения продолжается для старой строки.
Для заданной в варианте структуры данных, каждый элемент которой содержит указатели на элементы произвольного типа void*, написать итератор. Проверить его работу на примере вызова итератора для структуры данных с соответствующими элементами и конкретной функцией.
1. Односвязный список, элемент которого содержит указатель типа void* на элемент данных. Функция включения последним и итератор сортировки методом вставок: исключается первый и включается в новый список с порядке возрастания. Проверить на примере элементов данных - строк и функции сравнения strcmp.
2. Дерево, каждая вершина которого содержит указатель на элемент данных void* и не более 4 указателей на поддеревья. Итератор поиска первого подходящего firstthat и функция включения в поддерево с минимальной длиной ветви. Проверить на примере элементов данных - строк и функции проверки на длину строки - не менее 10 символов.
3. Динамический массив указателей типа void*, содержащий указатели на упорядоченные элементы данных. Итераторы включения с сохранением упорядоченности и foreach. Предусмотреть увеличение размерности динамического массива при включении данных. Проверить на примерах элементов данных типов int и float (2 проверки).
4. Двусвязный циклический список, элемент которого содержит указатель типа void* на элемент данных. Итераторы foreach и включения с сохранением упорядоченности. Проверить на примере элементов данных структурированного типа, содержащих фамилию, год рождения и номер группы и функций сравнения по году рождения и по фамилии.
5. Двоичное дерево, каждая вершина которого содержит указатель типа void*. Итераторы foreach , двоичного поиска и включения с сохранением упорядоченности. Проверить на примере элементов данных структурированного типа, содержащих фамилию, год рождения и номер группы и функций сравнения по году рождения и по фамилии.
6. Динамический массив указателей типа void* на неупорядоченные элементы данных. Итератор поиска минимального элемента. Проверить на примере элементов данных структурированного типа, содержащих фамилию, год рождения и номер группы и функций сравнения по году рождения и по фамилии.
Разработать заданные функции для иерархической (двухуровневой) структуры данных.
1. Список - элемент содержит статический массив указателей на упорядоченные строки. Включение с сохранением упорядоченности. Если после включения строки массив заполняется полностью, то создается еще один элемент списка с массивом указателей, в который переписывается половина указателей из старого.
2. Список, каждый элемент которого содержит динамический массив указателей на строки, упорядоченные по длине. Размерность массива в каждом следующем элементе в 2 раза больше, чем в предыдущем. Строка включается в структуру данных с сохранением упорядоченности. Если строка включается в заполненный массив, то последний указатель перемещается в следующий элемент и так далее).
3. Двухуровневый массив указателей на упорядоченные строки. Массив верхнего уровня - статический, массивы нижнего уровня - динамические. Включение строки с сохранением упорядоченности. Если после включения строки массив заполняется полностью, то создается еще один массив указателей, в который переписывается половина указателей из старого.
4. Двухуровневый массив указателей на строки, упорядоченные по длине. Размерность каждого следующего массива нижнего уровня в 2 раза больше предыдущего. Строка включается в структуру данных с сохранением упорядоченности. Если строка включается в заполненный массив, то последний указатель перемещается в следующий элемент и так далее).
5. Список - элемент содержит статический массив указателей на строки. Включение новой строки - последней. Сортировка выбором - в старой структуре данных выбирается минимальная строка и включается последней в новую структуру данных.
6. Двухуровневый массив указателей на строки. Массив верхнего уровня - статический, массивы нижнего уровня - динамические. Включение новой строки - последней. Сортировка выбором - в старой структуре данных выбирается минимальная строка и включается последней в новую структуру данных.
7. Дерево, вершина которого содержит статический массив указателей на строки и N указателей на потомков.
Указанные варианты заданий реализовать с использованием позиционирования указателя в текстовом файле и массива указателей, без загрузки самого текстового файла в память.
1. Сортировка строк файла по длине и по алфавиту и вывод результата в отдельный файл.
2. Программа-интерпретатор текста. Текстовый файл разбит на именованные модули. Каждый модуль может иметь вызовы других текстовых модулей. Требуется вывести текст модуля main с включением текстов других модулей в порядке вызова:
.
#aaa
{
Произвольные строки модуля текста ааа
}
#ппп
{
Произвольные строки текста
#aaa // Вызов модуля текста с именем aaa
Произвольные строки текста
}
#main
Основной текст с вызовами других модулей
3. Программа - редактор текста с командами удаления, копирования, и перестановки строк, с прокруткой текста в обоих направлениях (исходный файл при редактировании не меняется).
4. Программа - интерпретатор текста, включающего фрагменты следующего вида :
.
#repeat 5
Произвольный текст
#end
При просмотре файла программа выводит его текст, текст фрагментов "#repeat - #end" выводится указанное количество раз. Фрагменты могут быть вложенными.
5. Программа просмотра блочной структуры Си-программы с командами вывода текущего блока, входа в n-ый по счету вложенный блок и выхода в блок верхнего уровня.
6. Программа построчного сравнения двух файлов с выводом групп строк, вставленных или удаленных из второго файла относительно первого.
7. Программа просмотра текстового файла по предложениям. Предложением считается любая последовательность слов, ограниченная точкой, после которой идет большая буква или конец строки. Программа выводит на экран любой блок с n-го по m-ое предложение.
8.Программа просмотра текстового файла по абзацам. Абзацем считается любая последовательность строк, ограниченная пустой строкой. Программа выводит на экран любой абзац по номеру.
9. Программа составляет словарь терминов. Каждый термин - слово, записанное большими (строчными) буквами.
1. Файл записей переменной длины перед каждой записью содержит целое, определяющее длину этой записи. Написать функции ввода и вывода записи в такой файл. Функция ввода (чтения) должна возвращать размер очередной прочитанной записи. Использовать функции для работы с двумя файлами - строк и динамических массивов целых чисел.
2. Программа создает в файле массив указателей фиксированной размерности на строки текста. Размерность массива находится в начале файла, сами строки также хранятся в файле в виде записей переменной длины. Написать функции чтения/записи строки из файла по заданному номеру.
3. Программа переписывает дерево с ограниченным количеством потомков из памяти в файл записей фиксированной длины, заменяя указатели на вершины номерами записей в файле. Затем выполняет обратную операцию.
4. Дерево представлено в файле записей фиксированной длины естественным образом: если вершина дерева в файле находится в записи под номером N, то ее потомки - под номерами 2N и 2N+1. Корень дерева - запись с номером 1. Написать функции включения в дерево с сохранением упорядоченности и обхода дерева (вывод упорядоченных записей). (Необходимо учесть, что несуществующие потомки должны быть записями специального вида (например, пустой строкой)).
5. Упорядоченные по возрастанию строки хранятся в файле в виде массива указателей (см.вар.2). Написать функции включения строки в файл и вывода упорядоченной последовательности строк (просмотр файла).
6. Для произвольного текстового файла программа составляет файл записей фиксированной длины, содержащий файловые указатели на строки (см. л/р 6, вар.3). Используя массив указателей на строки из этого файла программа производит логическое удаление, перестановку и сортировку строк, не меняя самого текстового файла.
7. Выполнить задание 3 применительно к графу, представленному списковой структурой.
8. Составить файл записей фиксированной длины, в котором группы записей связаны в односвязные списки (например, списочный состав студентов различных групп).
Разработать резидентную программу в DOS. Программа должна обеспечивать включение и отключение (если необходимо, с восстановлением содержимого экрана) заданного процесса по комбинации " горячих клавиш" ALT/?. Процесс, связанный с изменением содержимого экрана, должен начинаться при отсутствии ввода с клавиатуры в течение заданного интервала и прекращаться при начале ввода. Изменение следующего слова или буквы должно производиться только после завершения аналогичного процесса над предыдущим словом или буквой.
1. Подсчет интенсивности работы с клавиатурой и вывод сообщения "не торопись" при превышении интенсивности ввода выше заданной. Строка отображается 2 секунды и исчезает.
2. Осыпание букв и цифр на экране (последовательное перемещение каждой буквы и цифры по всем строкам сверху вниз).
3. Вывод окна с сохранением содержимого, перемещение окна по всем направлениям, (с использованием " горячих клавиш" ) и уничтожение окна с восстановлением содержимого экрана.
4. Программа запоминает последние n (100-200) интервалов нажатия клавиш и по " горячей клавише" выводит строку с математическим ожиданием и дисперсией времени нажания. Через 3 секунды строка стирается.
5. Поиск в видеопамяти идентификаторов (цепочка букв) и перестановка первых и последних букв. Измененные слова запоминаются и в дальнейшем уже не меняются.
6. Бегающий по экрану символ, отражающийся от границ экрана и от всех символов - не пробелов.
7. Поиск в видеопамяти идентификаторов (цепочка букв) и замена строчных букв на прописные и наоборот.
8. " Буквоед" - символ, бегающий по экрану по диагонали. При попадании на букву или цифру " выедает" все слово, заменяя его на пробелы.
9. " Анти-комментатор" . При обнаружении комментариев ( //..... или /*.....*/) удаляет их. При удалении комментария вида /*...*/ сдвигает текст вверх-влево (либо заливает определенным цветом).
10. Автоматическая подсветка блока. Программа обнаруживает на экране последователь-ности, заключенные в фигурные скобки ( {...} ) и меняет цвет фона внутри каждого блока в зависимости от уровня вложенности.
