~simple_grep
Рекурсивно обойти поддерево файловой системы, заданное пользователем,
выполнить для каждого найденного файла поиск в нем подстроки, заданной пользователем.
Если подстрока найдена в файле, вывести имя файла на стандартный вывод.
Пример вызова:
./my_grep.exe c:/temp/ abc
Вывод:
c:/temp/1.txt
c:/temp/222/readme
Похожим образом работает стандартная утилита grep.
Для получения списка файлов использовать набор функций
opendir, readdir, closedir.
Они упомянуты в заголовочном файле dirent.h
Дополнительные условия:
компилятор языка C, стандартная библиотека языка C (использовать
заголовочные файлы stdio.h, stdlib.h, string.h).
Программа должна запускаться из командной строки,
анализировать аргументы командной строки,
выводить результат на стандартный вывод.
~reverse_stdin_search_substr
Есть текстовый файл неопределенной длины - стандартный ввод (stdin),
пользователь задает искомую подстроку.
Нужно выбрать все строки из файла, содержащие искомую подстроку,
и вывести их на стандартный вывод (stdout) в обратном порядке, причем
строки перевернуть задом на перед. Пример:
искомая подстрока: ab
входной поток:
kdk ldlfu abd d
gdt kjyh gefd
cab ks dghy loo
df fi
выходной поток:
d dba ufldl kdk
ool yhgd sk bac
Программа должна запускаться из командной строки и считывать
строки текста пока пользователь не сигнализирует о конце
файла (стандартного ввода) комбинацией Ctrl+D (unix) или
Ctrl+Z (windows). Искомую подстроку задавать как аргумент
командной строки (см. argc, argv).
Необходимо использовать динамическую память для хранения
считываемых строк, так как заранее не известно их количество.
~reverse_stdin_search_numbers
Есть текстовый файл неопределенной длины - стандартный ввод (stdin),
пользователь задает натуральное число.
Нужно выбрать все строки из файла, длина которых делится на заданное число
без остатка, и вывести их на стандартный вывод (stdout) в обратном порядке,
причем в каждой строке изменить регистр символов на противоположный. Пример:
заданное число: 4
входной поток:
Abc CDE 1278
123 yit
baCD
iopt uUI
выходной поток:
IOPT Uui
BAcd
aBC cde 1278
Программа должна запускаться из командной строки и считывать
строки текста пока пользователь не сигнализирует о конце
файла (стандартного ввода) комбинацией Ctrl+D (unix) или
Ctrl+Z (windows). Искомое натуральное число задавать как аргумент
командной строки (см. argc, argv).
Необходимо использовать динамическую память для хранения
считываемых строк, так как заранее не известно их количество.
~sort_stdin
Есть текстовый файл неопределенной длины - стандартный ввод (stdin),
нужно отсортировать его строки в лексикографическом порядке
по возрастанию и вывести их на стандартный вывод (stdout).
Программа должна запускаться из командной строки и считывать
строки текста пока пользователь не сигнализирует о конце
файла (стандартного ввода) комбинацией Ctrl+D (unix) или
Ctrl+Z (windows).
Необходимо использовать динамическую память для хранения
считываемых строк, так как заранее не известно их количество.
Программа сортирует считанные строки любым алгоритмом сортировки
и выводит их на stdout.
Лексикографическое сравнение строк:
"ABC" < "ABCD", "ABC" = "ABC", "ABC" < "ABD"
Для его выполнения можно воспользоваться функцией strcmp().
Дополнительные условия:
компилятор языка C, стандартная библиотека языка C (использовать
только заголовочные файлы stdio.h, stdlib.h, string.h).
Пользователь может перенаправить стандартные ввод и вывод
программы средствами операционной системы.
~sort_phonebook_hoare
Сортировка массива записей (телефонной книги) методом быстрой
сортировки Хоара.
Записи считываются из текстового файла, каждая запись состоит
из двух строк: имя (строка) и телефон (целое число).
Записи отделяются друг от друга пустой строкой.
Сортировать записи по полю "имя" в лексикографическом
порядке (man 3 strcmp) по возрастанию.
Количество записей в файле может быть любым,
нужно сохранять данные в динамически выделенной памяти.
Пример вызова:
quick_sort_phone_book.exe input.txt output.txt
Пример входного файла:
Vasya
Petya
Misha
Пример выходного файла:
Misha
Petya
Vasya
~sort_phonebook_tree
Сортировка массива записей (телефонной книги) с помощью
двоичного дерева.
Записи считываются из текстового файла, каждая запись состоит
из двух строк: имя (строка) и телефон (целое число).
Записи отделяются друг от друга пустой строкой.
Сортировать записи по полю "телефон" по убыванию.
Количество записей в файле может быть любым,
нужно сохранять данные в динамически выделенной памяти.
Сортировка с помощью двоичного дерева состоит из двух
фаз: 1) построение дерева, когда очередной элемент помещается
на свое место в дереве, если он меньше значения в текущем узле,
то поместить в правое поддерево (поскольку сортируем по убыванию),
если больше - в левое поддерево. Если поддерево пустое, то оно
будет создано из нового элемента.
2) обхода дерева "слева направо",
когда рекурсивно выписывается левое поддерево, потом
значение в текущем узле и рекурсивно - правое поддерево.
Пример вызова:
tree_sort_phone_book.exe input.txt output.txt
Пример входного файла:
Vasya
Petya
Misha
Пример выходного файла:
Petya
Misha
Vasya
~sort_phonebook_funcptr
Сортировка массива записей (телефонной книги) методом Пузырька.
Записи считываются из текстового файла, каждая запись состоит
из двух строк: имя (строка) и телефон (целое число).
Записи отделяются друг от друга пустой строкой.
По какому полю сортировать и в каком порядке - задается
пользователем из командной строки, через первый параметр
(возможные значения: NAME - по имени, PHONE - по телефону)
и через второй параметр
(возможные значения: ASC - по возрастанию, DESC - по убыванию).
Третий и четвертый параметры- имена входного и выходного файлов.
Количество записей в файле может быть любым,
нужно сохранять данные в динамически выделенной памяти
(связный список).
Использовать тип "указатель на функцию" для параметризации
функции сортировки.
Пример вызова:
bubble_sort_phone_book.exe NAME DESC input.txt output.txt
Пример входного файла:
Petya
Vasya
Misha
Пример выходного файла:
Vasya
Petya
Misha
~ext_sort_2way
Выполнить сортировку строк в текстовом файле используя метод
внешней сортировки слиянием.
На основе алгоритма двухпутевого слияния можно прийти к рекурсивному
определению сортировки слиянием: исходный массив следует разделить на две половины
(то есть два временных файла), применить к каждой половине алгоритм
сортировки слиянием, а затем с помощью алгоритма
двухпутевого слияния объединить подсписки в один отсортированный массив.
Рекурсивные вызовы завершаются, когда подсписок n-ого уровня,
переданный алгоритму сортировки, будет содержать всего один элемент,
поскольку он, очевидно, уже отсортирован.
Пример вызова:
./ext_sort.exe file.txt
Дополнительные условия:
компилятор языка C, стандартная библиотека языка C (использовать
только заголовочные файлы stdio.h, stdlib.h, string.h).
Программа должна запускаться из командной строки и получать
параметры (имя файла) из командной
строки (см. параметры функции main(): argc, argv).
~phonebook_editor
Интерактивный редактор телефонной книги. Операции добавления просмотра, удаления, загрузки и сохранения.
~hashmap_crc32_chains
Реализовать структуру данных хеш-массив на основе хеш-функции CRC32.
Метод разрешения коллизий: связный список.
Размер хеш-таблицы: 4096 элементов.
Вычисление CRC32:
http://ru.wikipedia.org/wiki/Циклический_избыточный_код
Протестировать хэш путем заполнения его строками текста из произвольного
текстового файла (словарь). Вывести содержимое хеш-массива на стандартный
вывод в читаемом виде (текст) и статистику возникновения коллизий
при заполнении структуры.
Программа должна запускаться из командной строки и считывать имя
файла для тестирования со стандартного ввода,
выводить результат на стандартный вывод.
~infix_to_postfix
Алгоритм преобразования выражения из инфиксной (привычной) записи
в постфиксную (обратную польскую).
Для перевода выражения из инфиксной формы в постфиксную с учетом приоритетов операций и скобок
существует простой алгоритм (Дейкстры). Алгоритм работает со стеком, в котором хранятся знаки операций.
Сначала стек пуст. На вход алгоритму подается последовательность лексем (числа, скобки или знаки операций),
представляющая некоторое арифметическое выражение, записанное в инфиксной форме.
Результатом работы алгоритма является эквивалентное выражение в постфиксной форме.
Вводятся приоритеты операций: открывающая скобка имеет приоритет 0, знаки '+' и '–'
— приоритет 1 и знаки '*' и '/' — приоритет 2.
1. Пока не достигнут конец входной последовательности, читать очередную лексему и выполнять с ней следующие операции:
1. если прочитан операнд (число), записать его в выходную последовательность;
2. если прочитана открывающая скобка, положить её в стек;
3. если прочитана закрывающая скобка, вытолкнуть из стека в выходную последовательность
всё до открывающей скобки, при этом сами скобки уничтожаются (удаляются из стека и в ответ не идут);
4. если прочитан знак операции, вытолкнуть из стека в выходную последовательность все операции
с большим либо равным приоритетом, а прочитанную операцию положить в стек.
2. Если достигнут конец входной последовательности, вытолкнуть всё из стека в выходную последовательность и завершить работу.
Заметим, что порядок операндов в выходной последовательности не отличается от порядка операндов
в исходной последовательности. В выходной последовательности отсутствуют скобки.
Пример:
ввод:
(1 + 23 * 4)*(5 - 1)
вывод:
1 23 4 * + 5 1 - *
~stack_calc
Стековый калькулятор.
На входе - строка, содержащая выражение в постфиксной записи.
На выходе - строка, результат вычислений.
Пример:
ввод:
1 23 + 4 -
5 1 - *.
вывод:
Числа: целые неотрицательные.
Должны поддерживаться следующие двухместные
арифметические операции:
+ - * /
Каждая из них берет аргументы со стека, сначала
первый, потом - второй, выполняет над ними действие
и результат помещает на вершину стека.
Кроме того, должна поддерживаться операция '.'
- она берет один аргумент со стека и печатает его на вывод.
~stack_calc_module
Стековый калькулятор.
На входе - строка, содержащая выражение в постфиксной записи. На выходе - результат вычислений.
Пример: вход:
1 23 + 4 - 5 1 - *
выход: 80
Должны поддерживаться следующие двухместные арифметические операции:
+ - * /
Каждая из них берет аргументы со стека, сначала первый, потом - второй, выполняет над ними действие
и результат помещает на вершину стека.
В качестве операндов допустимы как целочисленные константы, так и имена переменных.
Имя переменной может содержать символы A-Z,a-z,0-9,_, но начинаться с цифры не может.
Решение оформить в виде отдельного.c модуля,.h файл приведен ниже.
Снабдить модульными тестами (unit-tests).
#ifndef EXEC_POSTFIX_H
#define EXEC_POSTFIX_H
/* типы лексем: константы, операции, имена переменных */
typedef enum { tt_CONST, tt_OPER, tt_ID } TokenType;
/* виды операций: сложение, вычитание, умножение, деление */
typedef enum { op_ADD, op_SUB, op_MUL, op_DIV } OperType;
/* максимальная длина имени переменной */
#define MAX_ID_LEN 40
typedef struct {
TokenType ttype;
union Value {
/* с лексемой связано одно из следующих значений */
int inum;
OperType otype;
char id[MAX_ID_LEN + 1];
} tvalue;
} Token;
typedef struct {
char id[MAX_ID_LEN + 1];
int value;
} Variable;
/* перевести текстовую строку (s) в массив лексем (*tokens).
получается массив длиной (*len).
память под выходной массив выделяется внутри функции,
а освобождается вызывающей стороной.
в случае успеха вернуть 0, иначе какой-либо код ошибки. */
int tokenize(const char *s, Token **tokens, int *len);
/* вычислить переданное постфиксное выражение (postfix, длина - len),
с использованем массива именованных переменных (vlist, длина vlen),
результат записать в *result.
в случае успеха вернуть 0, иначе какой-либо код ошибки. */
int execute_postfix(const Token *postfix, int len,
const Variable *vlist, int vlen, int *result);
#endif
~infix_to_postfix_module
Алгоритм преобразования выражения из инфиксной (привычной) записи
в постфиксную (обратную польскую).
Для перевода выражения из инфиксной формы в постфиксную с учетом приоритетов операций и скобок
существует простой алгоритм (Дейкстры). Алгоритм работает со стеком, в котором хранятся знаки операций.
Сначала стек пуст. На вход алгоритму подается последовательность лексем (числа, скобки или знаки операций),
представляющая некоторое арифметическое выражение, записанное в инфиксной форме.
Результатом работы алгоритма является эквивалентное выражение в постфиксной форме.
Вводятся приоритеты операций: открывающая скобка имеет приоритет 0, знаки '+' и '–'
— приоритет 1 и знаки '*' и '/' — приоритет 2.
1. Пока не достигнут конец входной последовательности, читать очередную лексему и выполнять с ней следующие операции:
1. если прочитан операнд (число), записать его в выходную последовательность;
2. если прочитана открывающая скобка, положить её в стек;
3. если прочитана закрывающая скобка, вытолкнуть из стека в выходную последовательность
всё до открывающей скобки, при этом сами скобки уничтожаются (удаляются из стека и в ответ не идут);
4. если прочитан знак операции, вытолкнуть из стека в выходную последовательность все операции
с большим либо равным приоритетом, а прочитанную операцию положить в стек.
2. Если достигнут конец входной последовательности, вытолкнуть всё из стека в выходную последовательность и завершить работу.
Заметим, что порядок операндов в выходной последовательности не отличается от порядка операндов
в исходной последовательности. В выходной последовательности отсутствуют скобки.
Пример: ввод:
(1 + 23 * 4)*(5 - 1)
вывод:
1 23 4 * + 5 1 - *
В качестве операндов допустимы как целочисленные константы, так и имена переменных.
Имя переменной может содержать символы A-Z,a-z,0-9,_, но начинаться с цифры не может.
Решение оформить в виде отдельного.c модуля,.h файл приведен ниже.
Снабдить модульными тестами (unit-tests).
#ifndef INFIX2POSTFIX_H
#define INFIX2POSTFIX_H
/* типы лексем: константы, операции, имена переменных */
typedef enum { tt_CONST, tt_OPER, tt_ID } TokenType;
/* виды операций: сложение, вычитание, умножение, деление,
левая и правая скобки */
typedef enum { op_ADD, op_SUB, op_MUL, op_DIV, op_LBR, op_RBR } OperType;
/* максимальная длина имени переменной */
#define MAX_ID_LEN 40
/* тип - лексема */
typedef struct {
TokenType ttype;
union Value {
/* с лексемой связано одно из следующих значений */
int inum;
OperType otype;
char id[MAX_ID_LEN + 1];
} tvalue;
} Token;
/* перевести текстовую строку (s) в массив лексем (*tokens).
получается массив длиной (*len).
память под выходной массив выделяется внутри функции,
а освобождается вызывающей стороной.
в случае успеха вернуть 0, иначе какой-либо код ошибки. */
int tokenize(const char *s, Token **tokens, int *len);
/* перевести набор лексем из инфиксного порядка в постфиксный.
память выделяется внутри функции, освобождается вызывающей стороной.
в случае успеха вернуть 0, иначе какой-либо код ошибки. */
int infix2postfix(const Token *infix, int in_len,
Token **postfix, int *out_len);
#endif
~graph_cycles
Определить содержит ли заданный граф циклы.
Граф - это множество вершин, и множество ребер, соединяющих их.
Граф можно задавать так:
1) Списком ребер, пример: AB, BC, AD.
2) Матрицей смежности, размера NxN, где N - количество вершин в графе.
Если на пересечении строки A и столбца B единица, то существует ребро AB.
Если ребра не имеют выделенного направления, то граф называется
неориентированным и матрица смежности будет симметрична относительно
главной диагонали.
Пример:
. | A B C D
-----------
A | 0 1 0 1
B | 1 0 1 0
C | 0 1 0 0
D | 1 0 0 0
Оба эти примера описывают один и тот же граф.
Существует простой алгоритм для определения того,
есть ли циклы в неориентированном графе:
Взять все вершины, каждая из которых связана лишь с одной другой,
вычеркнуть все соответствующие ребра и вершины. Повторять пока граф не станет
пустым или перестанет изменяться.
Ответить на вопрос, является ли граф циклическим.
Использовать представление графа в виде матрицы смежности.
Граф считывать со стандартного ввода:
сначала считать N - количество вершин, затем выделить массив размера NxN в куче
и заполнить его значениями 0 или 1 со стандартного ввода.
Выводить на стандартный вывод "yes" или "no".
~graph_labirynth
Есть лабиринт, заданный прямоугольной матрицей клеток, в которой 0 — пустая клетка, 1 — заполненная. Известны начальные координаты человечка, он может двигаться за один ход на одну клетку по вертикали или горизонтали, если новая клетка пустая. Если пустая клетка находится на краю матрицы — она выход из лабиринта. Нужно написать алгоритм достижения выхода или определения, что выхода нет.
Подсказка: использовать алгоритм поиска с откатом в глубину в графе.
Входные данные — текстовый файл с целыми числами, первые два числа — размеры матрицы, далее следует сама матрица построчно, затем — два числа — начальные координаты человечка.
Выходные данные — исходная матрица с отмеченным путем, отметить цифрой 2, или надпись «no route».
Пример входных данных:
5 6
0 0 1 1 1 1
1 0 0 0 0 1
1 1 1 0 1 1
1 0 0 0 0 1
0 1 1 1 1 0
4 3
Пример выходных
0 2 1 1 1 1
1 2 2 2 0 1
1 1 1 2 1 1
1 0 2 2 0 1
0 1 1 1 1 0
~graph_search_width
Поиск в ширину в графе.
Этот алгоритм позволяет найти кратчайший по количеству ребер путь между данной вершиной и всеми остальными.
Граф - это множество вершин, и множество ребер, соединяющих их.
Граф можно задавать так:
1) Списком ребер, пример: AB, BC, AD.
2) Матрицей смежности, размера NxN, где N - количество вершин в графе.
Если на пересечении строки A и столбца B единица, то существует ребро AB.
Если ребра не имеют выделенного направления, то граф называется
неориентированным и матрица смежности будет симметрична относительно
главной диагонали.
Пример:
. | A B C D
-----------
A | 0 1 0 1
B | 1 0 1 0
C | 0 1 0 0
D | 1 0 0 0
Оба эти примера описывают один и тот же граф.
Для поиска в ширину используются вспомогательные структуры:
1) очередь просмотра вершин.
2) массив размера N, в котором отмечаются все пройденные вершины.
3) для каждой вершины — пометка, какая вершина ей предшествует, чтобы можно было восстановить кратчайший путь — последовательность вершин.
Матрица, а также начальная и конечная вершины задаются пользователем.
Язык: С
~graph_search_depth
Поиск в глубину в графе или поиск с возвратами.
Этот алгоритм позволяет найти путь между данной вершиной и всеми остальными, если такой путь существует.
Граф - это множество вершин, и множество ребер, соединяющих их.
Граф можно задавать так:
1) Списком ребер, пример: AB, BC, AD.
2) Матрицей смежности, размера NxN, где N - количество вершин в графе.
Если на пересечении строки A и столбца B единица, то существует ребро AB.
Если ребра не имеют выделенного направления, то граф называется
неориентированным и матрица смежности будет симметрична относительно
главной диагонали.
Пример:
. | A B C D
-----------
A | 0 1 0 1
B | 1 0 1 0
C | 0 1 0 0
D | 1 0 0 0
Оба эти примера описывают один и тот же граф.
Для поиска в ширину используются вспомогательные структуры:
1) стек возвратов.
2) массив размера N, в котором отмечаются все пройденные вершины.
Матрица, а также начальная и конечная вершины задаются пользователем.
Язык: С
~bit_plane
Реализовать компактное хранилище для двумерного битового массива.
Каждое значение матрицы занимает в памяти один бит.
С помощью разработанной битовой матрицы реализовать рисование
линии по алгоритму Брезенхема:
http://www.codenet.ru/progr/video/alg/alg3.php
Интерфейс модуля (bitmap.h):
#ifndef BITMAP_H__INCLUDED
#define BITMAP_H__INCLUDED
typedef struct { /* допишите сами */ } BitMap;
/* инициализация массива нужной размерности,
возврат 1 - все хорошо, 0 - не хватило памяти */
int bmp_new(BitMap *bmp, int width, int height);
/* освободить память, занимаемую массивом */
void bmp_free(BitMap *bmp);
/* извлечь значение из строки y, столбца x,
если координаты выходят за пределы - всегда возвращать 0 */
int bmp_get(const BitMap *bmp, int x, int y);
/* установить значение бита = value в матрице, в строке y, столбце x.
предыдущее значение вернуть в качестве результата функции,
если координаты выходят за пределы - всегда возвращать 0 */
int bmp_set(BitMap *bmp, int x, int y, int value);
/* нарисовать линию по алгоритму Брезенхема,
точки рисовать значением value */
void bmp_line(BitMap *bmp, int x1, int y1, int x2, int y2, int value);
#endif
Для отладки нужно матрицу выводить на стандартный вывод.
~pas_filter_comments
Задание:
Программа - текстовый фильтр, отбрасывающий комментарии в стиле языка Object Pascal,
но сохраняющая все остальное без изменений.
В Object Pascal предусмотрено 3 типа комментариев: скобочные { }, (* *)
и строчный //, который комментирует текст до конца строки.
Скобочные комментарии одного типа не могут быть вложенными, например нельзя так:
{ { } }, разных типов — могут быть вложенными, например: (* { } *).
Программа считывает символы со стандартного ввода, выводит на стандартный вывод.
Внутри нее нужно устроить конечный автомат, устройство которого - состояния и переходы
между ними - отразить в пояснительной записке.
Язык программирования: ANSI C
~int_stack_module
Дата добавления: 2015-11-04; просмотров: 35 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| | | Мiнiстерство освіти і науки України |