1. Count upper-case and lower-case letters

Описание задания (RU)

Реализуйте функцию count_upper_lower, которая получает C-строку (нулём-terminiert) и считает: количество заглавных букв (A–Z) и количество строчных букв (a–z). Результаты записываются в переменные, на которые указывают параметры upper и lower.

1. Инициализируйте *upper и *lower значением 0.
2. Проходите по строке с помощью указателя (не используйте индексирование text[i]).
3. Используйте функции isupper и islower из заголовка <ctype.h>.
4. Все прочие символы (цифры, пробелы, пунктуация) игнорируются.

Task description (EN)

Implement void count_upper_lower(const char *text, int *upper, int *lower);. The function initializes both counters to 0, iterates over the 0-terminated string using a pointer, and uses isupper / islower to count upper-case and lower-case letters. The results are stored in *upper and *lower.

// Solution for Task 1
#include <ctype.h>

void count_upper_lower(const char *text, int *upper, int *lower)
{
 // 1) initialize counters
 *upper = 0;
 *lower = 0;

 // 2) use a pointer to traverse the string
 const unsigned char *p = (const unsigned char *)text;

 while (*p != '\0') {
 if (isupper(*p)) {
 (*upper)++; // upper-case letter found
 } else if (islower(*p)) {
 (*lower)++; // lower-case letter found
 }
 p++; // move to next character
 }
}

2. Implement dequeue for a queue of tree nodes

Описание задания (RU)

В файле заданы структуры очереди:

typedef struct QueueElement {
 TreeNode *value; // или другое имя поля с TreeNode*
 struct QueueElement *next;
} QueueElement;

typedef struct {
 QueueElement *first_element;
 QueueElement *last_element;
} Queue;

И уже реализованы функции initializeQueue, isEmpty, enqueue. Нужно дописать функцию:

int dequeue(Queue *q, TreeNode **value);

1. Если очередь пуста (first_element == NULL), вернуть -1.
2. Иначе:
   • взять первый элемент очереди,
   • записать TreeNode* из него в *value,
   • переместить q->first_element на следующий элемент,
   • если после этого очередь стала пустой — обнулить также q->last_element,
   • освободить память удалённого QueueElement через free,
   • вернуть 0 при успешном удалении.

Task description (EN)

Implement dequeue for a linked queue of TreeNode*. If the queue is empty, return -1. Otherwise remove the first element, store its TreeNode* in *value, update first_element (and last_element if the queue becomes empty), free the removed queue element, and return 0.

// Solution for Task 2
#include <stdlib.h>

int dequeue(Queue *q, TreeNode **value)
{
 // empty queue?
 if (q->first_element == NULL) {
 return -1;
 }

 // 1) take first element
 QueueElement *first = q->first_element;

 // 2) pass the stored TreeNode* back to caller
 *value = first->value;

 // 3) advance head pointer
 q->first_element = first->next;

 // 4) if queue is now empty, clear last_element as well
 if (q->first_element == NULL) {
 q->last_element = NULL;
 }

 // 5) free removed element
 free(first);

 return 0; // success
}

3. Breadth-First Search on a binary tree (using the queue)

Описание задания (RU)

Реализуйте функцию обхода бинарного дерева в ширину:

void breadth_first_search(TreeNode *root);

Дерево задано структурой:

typedef struct TreeNode {
 int value;
 struct TreeNode *left;
 struct TreeNode *right;
} TreeNode;

Требуется пройти по дереву в порядке BFS / level-order, используя очередь (функции initializeQueue, enqueue, dequeue из предыдущего задания) и печатать значения узлов в том порядке, в котором они посещаются. Рекурсию использовать не рекомендуется.

Task description (EN)

Implement void breadth_first_search(TreeNode *root); that traverses the binary tree in breadth-first order (level-order) starting at root. Use the queue data structure (enqueue/dequeue) instead of recursion and print each node’s value when it is visited.

// Solution for Task 3
void breadth_first_search(TreeNode *root)
{
 // empty tree?
 if (root == NULL) {
 return;
 }

 Queue q;
 initializeQueue(&q);

 // start with root node
 enqueue(&q, root);

 TreeNode *node;

 // process nodes level by level
 while (!isEmpty(&q)) {
 // get next node from queue
 if (dequeue(&q, &node) != 0) {
 break; // should not really happen if isEmpty() works correctly
 }

 // visit / print node
 printf("%d ", node->value);

 // enqueue children (if present)
 if (node->left != NULL) {
 enqueue(&q, node->left);
 }
 if (node->right != NULL) {
 enqueue(&q, node->right);
 }
 }

 // optional: print newline
 printf("\n");
}