Финальная задача Жуковой

main.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<ctype.h>

int podstroki(char *st, char **pod_str, int k, int *massiv_nomerov, int m)
{
	char *pl, *pr, **q;
	int n = strlen(st);
	char *temp;
	int length = 0;
	char *dig;

	q = pod_str + k;

	pl = strstr(st, "**");
	if (pl == NULL)
		return q - pod_str;
	pl += 2;
	
	for (; pl < st + n; pl++)
	{
		pr = strstr(pl, "**");
		
		if (pr == NULL)
			return q - pod_str;
		else length = (int)(pr - pl);
		
		for (dig = pl; dig < pr; dig++)
			if (isdigit(*dig))
				break;

		if (length > 0 && dig == pr)
		{
			*q = (char*)malloc(length * sizeof(char));
			strncpy(*q, pl, length);
			*(*q + length) = '\0';
			q++;
			*(massiv_nomerov + k) = m;
			k++;
		}
		pl = pr + 2;
	}
	return q - pod_str;
}

int poisk_max_podstroki(char **a, int n)
{
	char **s; int d, max;
	d = 0;
	for (s = a; s<a + n; s++)
	{
		if (strlen(*s) > d)
		{
			max = (s - a);
			d = strlen(*s);
		}
	}
	return max;
}

void zamena_simvola(char *st, char sim1, char sim2)
{
	char *p;
	p = st;
	while ((p = strchr(p, sim1))) *p = sim2;
}

int main()
{
	char **st, buf[80], **a, **pod_str, sim1, sim2;
	int n = 0, k = 0, max, *i, m=0, *massiv_nomerov;
	st = (char**)malloc(10 * sizeof(char*));
	a = st;
	
	// выделение памяти под массив
	while (n<100 && *gets_s(buf) != '\0')
	{
		*a = (char*)malloc(strlen(buf) + 1);
		strcpy(*a, buf);
		a++;
		n++;
	}

	massiv_nomerov = (int*)malloc(20 * sizeof(int));
	pod_str = (char**)malloc(20 * sizeof(char*));
	
	for (a = st; a<st + n; a++)
	{
		k = podstroki(*a, pod_str, k, massiv_nomerov, m);
		m++;
	}

	if (k == 0)
	{
		printf("Podstroki ne naydeni! gtfo \n");
		return 0;
	}

	printf("Vivod vsex podctrok:\n");
	for (a = pod_str; a< pod_str + k; a++) 
		puts(*a);

	max = poisk_max_podstroki(pod_str, k);
	printf("Samaya dlinnaya podstroka:");
	puts(*(pod_str + max));
	
	printf("Prinadlejit stroke:");
	char *swap = *(st + *(massiv_nomerov + max));
	puts(swap);
	
	printf("\n Vvedite simvoli:\n");
	printf("1> ");  scanf("%c", &sim1);
	getchar();
	printf("2> ");  scanf("%c", &sim2);
	
	zamena_simvola(swap, sim1, sim2);
	
	printf("Vivod vsex podctrok:\n");
	for (a = st; a< st + n; a++)
		puts(*a);

	return 0;
}

Последняя задача Жуковой.

Последняя в семестре задача состоит из трёх подзадач. Последовательность решения всех трёх задач следующая:
0. Ввести массив подстрок (обозначим его как А)

1. Выделить из А новый массив подстрок Б
2. В массиве Б найти подстроку по данному в задании условию.
3. Найти из А строку, содержащую найденную строку из Б.
4. Выполнить модификацию найденной в А стррки.

Если рассматривать структуру решения, то , вам следует написать 4 функции:

• main()
• gen_podstr()
• find_str()
• modify_str()
  Важно: Для простоты изложения я буду называть функции адекватными и понятными обозначениями. Не забудьте переписать названия под себя.

---

Для решения всей задачи надо заранее ответить на один вопрос: как сопоставлять подстроке из массива Б строку из массива А?
Одним из самых простых вариантов: ввести некоторую таблицу, хранящую сколько строк вынули из массива А. Её устройство может быть различным.
Рассмотрим 3 варианта, основанных на массиве. Для простоты будем рассматривать разбиение массива строк на подстроки по пробелам.
Вариант 1:

Таблица представлена в виде массива, его размерность равна количеству выделенных подстрок. В каждую ячейку записан номер строки из массива А, из которой мы выделили подстроку.

Вариант 2:

В данном случае размерность массива равна количеству исходных строк. В каждую ячейку записано количество выделенных подстрок.

Пусть по обеим таблицам нам следует найти строку, содержавшую подстроку 2E. По варианту 1 мы сразу получаем ответ.
По варианту 2, нам необходимо проявить смекалку: зная порядковый номер подстроки 2E мы должны найти строку из массива А, содержащую i-ую подстроку. Нас интересует такая строка, что предыдущая строка массива А гарантированно не содержит искомую.

Можно выполнить некоторую оптимизацию и вывести вариант 3:

Вариант 1 является самым простым.

---

0. Ввести массив подстрок

Всё необходимое описано в подробном разборе ввода массива подстрок по ссылке/

---

1. Выделить массив подстрок

Будем работать с массивом А (введён с клавиатуры) и массивом Б (формируем сами).
Выделение подстрок из массива/. Для выделения массива подстрок вы проходите в цикле по всему массиву А
Анализ вариантов из задания показывает следующие варианты разбиения:

1. Выделить подстроки, заключенные в некоторые символы
2. Разбить строку на подстроки по неким литералам
3. Разбить строку на подстроки по неким литералам и выполнить для каждой подстроки проверку

Отдельно стоит вариант 10: для него лучше всего воспользоваться циклом for и

2. Выделить из А новый массив подстрок Б.

Условия разбиения можно разбить по следующим группам:

• Заключенные, без условия: 7
• Заключенные, с условием: 1, 8
• Разделенные, без условия: 2, 3, 4, 6, 11
• Разделенные, с условием: 8, 9, 5, 10

Заметка про задачи где встречаются "скобки": считайте, что все скобки стоят верно, каждой открывающей соответствует закрывающая и вложенных выражений вида ((АBC)D(EFG)) не встречается. Если ТВ предъявит вам что надо было проверять, то она во-первых этому не учит, во-вторых пусть научится техзадание адекватно формулировать.

Отметим условие задачи: пустые подстроки не следует выделять и нельзя печатать. Если вы выделяете подстроки, то убедитесь что разница

Для решения всех задач я рекомендую ввести два указателя: char *p_left и char *p_right, обозначающие левую и правую границу вашей подстроки (то есть, её первый и последний символы).

Также напоминаю полезные для работы функции:

• strstr(strA, strB) возвращает первое вхождение strB в strA.
• strchr(str, letter) вернёт позицию letter в str
• strncpy(dest, length, source) - копирует из source в dest первые n элементов

Есть нюанс между. Допустим вы идете с начала строки. "Найти заключенные подстроки" означает, что нужно выделить подстроки ограниченные слева и справа. Следовательно, перед циклом прохода по строке вы можете пропустить часть подстроки, пока не найдете последовательность символов с которой начинается ваше слово.
Если же следует найти "разделенные", то начало строки пропускать нельзя.

Рассмотрим вариант задания 9, где требуется разбить на подстроки, разделенные двумя звездочками .
"Более чем двумя звездочками" означает две вещи. Во-первых, мы можем пользоваться strstr(str, "***") для нахождения границ подстроки. Во-вторых, после выделения строки необходимо пролистать лишние звездочки: из 111***333******AA нужно выделить 111, 333,AA.
Функция gen_podst() принимает аргументы:

• char *st - строка которую следует разбить
• char **pod_str - указатель на массив подстрок. В него могут быть уже внесены некоторые подстроки.
• int k - смещение в массиве подстрок начиная с которого можно добавлять новые строки.
• int *massiv_nomerov - указатель на массив номеров, позволяющий сопоставлять А и Б. Заполняется по варианту 1
• int m - порядковый номер текущей строки.

Функция же возвращает модифицированное значение k, то есть общее кол-во всех выделенных подстрок

int gen_podstr(char *st, char **pod_str, int k, int *massiv_nomerov, int m)

Переменные необходимые для работы:

• char *p_left, *p_right - указатели на левую и правую часть
• char **q - указатель для работы с pod_str
• int n = strlen(st) - длина исходной строки. Считаем сразу для оптимизации
• int length = 0; - длина выделенной подстроки
• int *nomer_stroki; - указатель для работы с massiv_nomerov
• char *dig - переменная для проверки на цифру (см. условие варианта 3)

Инициализируем значения:

nomer_stroki = massiv_nomerov + k;
q = pod_str + k;

Общая логика алгоритма такая:
находим правую границу, вычисляем длину length выделяем строку от p_left до p_right, проверяем её на наличие цифры, если всё хорошо - копируем, затем ставим p_left = p_right + 1. Обязательно +1, так как p_left далее в цикле будет увеличено на 1, а всего мы ищем 2 звездочки. В противном случае, пропускали бы лишний 1 символ в последующих подстроках. Когда p_right равно NULL, копируем остаток строки.

for (p_left = st; p_left < st + n; p_left++)
{
	p_right = strstr(p_left, "**");  // находим ** 

        // нужно найти разделенные. Значит, последняя часть строки тоже может подходить под условие задачи
        // учтем это при расчете длины
	if (p_right == NULL)
		{
			p_right = st + n - 1; // p-right ставим на конец строки
			length = (int)(st - p_left + n); // находим скорректированную длину
		}
		else length = (int)(p_right - p_left); // обычная длина
	
        // теперь когда известны начало и конец строки нужно просмотреть её согласно условию
        // счётчик dig будет равен p_right только если не будут найдены цифры
	for (dig = pl; dig < pr; dig++)
		if (isdigit(*dig))
			break;
	
         // нам интересуют непустые строки и строки без цифр. 
        if (length > 0 && dig == pr)
	{
                // если всё хорошо, то копируем блок.
                // выделим память под новую подстроку
		*q = (char*)malloc(length * sizeof(char));
		strncpy(*q, pl, length); // скопируем
		*(*q + length) = '\0'; // не забудем поставить нуль терминант в конце
		q++; // переместим указатель для новой подстроки
		*nomer_stroki = m; // для выделенной строки 
		k++;
	}
        if (p_right == st + n - 1)
			break;
		else p_left = p_right + 1;
	}
	*nomer_stroki = m;
	return q - pod_str;
}

3. Поиск подстроки по условию.

Поиск подстроки осуществляется функцией find_str(). Функция возвращает порядковый номер строки из массива подстрок Б, удовлетворяющую условию.
Рассмотрим пример - найти подстроку наибольшей длины (вариант 1).

int find_str(char **a, int n)
{
	char **s; 
        int d, max;
	d = 0;
	for (s = a; s<a + n; s++)
	{
		if (strlen(*s) > d)
		{
			max = (int)(s - a); 
			d = strlen(*s);
		}
	}
	return max;
}

Для работы с исходным массивом подстрок char** a вводим указатель char **s. Для данной задачи помимо результата - переменной max - необходимо хранить и временное значение d, в котором хранится длина максимальной строки. Это позволяет не пересчитывать её каждый раз.
Сам по себе порядковый номер строки - это разница между указателем на неё и указателем на первую строку из списка подстрок.
Данный алгоритм превращается в вариант 2 с минимальными модификациями.

Для остальных вариантов (кроме 5 и 9) данный алгоритм поиска является костяком, на который следует навесить дополнительную логику. Однако следует учитывать один момент.
У алгоритмов поиска минимума и максимума в массивах всегда был недостаток - экстремумом считается первый элемент, подошедший под условия. То есть, если у вас две строки длиной 1 символ, то минимальной по длине будет считаться первая из них.
В то же время, у вас может не найтись например максимальной по длине строки содержащей двойки так как в исходном массиве Б не будет никаких подстрок, содержащих 2. Тогда ваша функция

Варианты 5 и 9 стоят особняком и требуют отдельного решения.
Для варианта 9 достаточно в цикле обхода массива подстрок вернуть первую подстроку, для который результат strchr не равен NULL. Если же ни одна строка не содержит символ, то следует продумать какое значение вернуть обратно в функцию main.

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

char min_char; // наш минимальный символ
...
if (min_char < *p) {...}

Где *p - указатель на символ рассматриваемой подстроки

---

4. Модификация строки

Если прочитать условия, то всё сходится к следующим вариантам:

1. Длина строки не изменится
2. Длина строки уменьшится
3. Длина строки увеличится

В рамках этих трёх строк происходят различные операции замены, удаления или вставки.

В группу 1 входит только вариант 6.
В группу 2: 1, 3, 7, 8.
В группу 3: 2, 4, 5

Группа 1
Вводите с клавиатуры два символа: старый и новый.
Затем следует простой цикл.

char *p;
for (p = str; p < str + n; p++)
	if (*p == char_old) *p = char_new;

Группа 2
При удалении символа ваша задача - сдвинуть весь остаток строки так, чтобы закрыть удаляемый символ. Вариантов сдвига два: либо "руками", то есть прописывая сдвиг каждого символа, либо через strcpy. Второй вариант лучше подходит под задачу удаления нескольких подряд идущих символов, но в задании у вас такого нигде не требуется.

Пример универсальной функции для удаления заданного символа из строки:

void remove_char_from_string(char* str, char c)
{
	char *src, *dest;

	src = dest = str;
	while (*src != '\0')
	{
		if (*src != c)
		{
			*dest = *src;
			dest++;
		}
		src++;
	}
	*dest = '\0';
}

В функции remove два указателя src и dest идут с начала строки до её конца. src перебирает все символы исходной строки, a dest указывает на ту позицию, куда следует перенести откопированный символ.

Группа 3