10.27 Память на куче

Форма для сдачи

Контрольная работа

Повторение:

Бывает по-разному, но обычно у запущенной программы в ОС:

• ↓ стек
• недоступная память
• ↑ куча
• статическая память

Почему так? Так пошла эволюцияПотому что!!! (+потому что виртуальная память, а так удобнее)

strlen, strlcpy и strlcat: ввести число n и строку, сформировать и вывести строку, повторенную n раз

NB! Вот здесь начали сильно тормозить из-за отсутствия нормальных падаванок

Тип void * и двойные ссылки; malloc() и calloc()

Был ли void * на лекциях? Для чего нужен?

• malloc и calloc (а также sizeof())

• Написать функцию char *strmul(char *str, int mul), которая заказывает память для результата и возвращает строку str, повторенную mul раз

Тип int ** и ему подобные — для чего нужны? многомерные массивы, но это не всё

•    1 #define ou() printf("pp=%p; *pp=%p; p=%p;\n*p=%d; **pp=%d, d=%d, e=%d\n\n", pp, *pp, p, *p, **pp, d, e);
     2 int main(void) {
     3         int d = 100500, e=123;
     4         int *p = &d;
     5         int **pp = &p;
     6         ou();
     7         *p = 42; ou();
     8         **pp = 1337; ou();
     9         *pp = &e; ou();
    10         *p = 0xfacade; ou();
    11         return 0;
    12 }
  

• Подсказка: все параметры передаются в функцию по значению а если мы хотим положить адрес в переменную?

• Преобразовать strmul() в функцию strmulinput(char **dst, int *size, int mul), которая вводит строку (не длиннее 100), формирует строку ввода, повторенную mul раз, и помещает указатель на строку и размер в dst и size. Вывести *dst и *size

  • Попробовать добавить наш любимый -fsanitize=address

  • А вот! free

• realloc: «увеличение» выделенного буфера

  •    1 int main(void) {
       2         int n=9;
       3         char *buf=malloc(n);
       4         for (int i=1; i<1024; i+=43) {
       5                 buf = realloc(buf, n*i);
       6                 printf("%p: %d\n", buf, n*i);
       7         }
       8         free(buf);
       9         return 0;
      10 }
    

  • это не увеличение!

  • (иногда!) выделяется новый (больший) буфер, в него копируется старый, старый уходит в free(), возвращается новый

    • Почему «иногда»? Так пошла эволюцияПредположительно, потому что ОС в действительности выделила больший буфер

• Написать функцию char *getlines(int n), которая вводит n строк в одну (\n удалять не надо), возвращая указатель на эту многострочную строку. Проверить, всё ли в порядке с -fsanitize=address

  • Подсказка: fgets() → realloc() → strcat() и так по кругу

NB! Это было только в режиме быстрой малопонятной падаванки

Ввод строки произвольного размера

Работа getline

1. Ввод строки произвольного размера (для этого надо инициализировать приёмник NULL-ом)

(требуется free()):

•    1         char *s=NULL;
     2         size_t buflen;
     3         ssize_t len;
     4         while ((len=getline(&s, &buflen, stdin)) > 0)
     5                 printf("%ld, %lu, %s", len, buflen, s);
     6         free(s);
     7         return 0;
  

  • ⇒ Если s != NULL, а вводимая строка больше bufsize, произойдёт realloc()

• Переписать getlines() с использованием getline(). Проверить, всё ли в порядке с -fsanitize=address

NB! Досюда не дошли, но это хотя бы несложно

Массив строк

• Инициализированный массив строк

• Ввести n, затем создать массив на n строк и ввести их; вывести только строки, в которых содержится первый символ последней строки (strchr)

  • Не забыть free() для них для всех!

Д/З

1. EJudge: SearchReplace 'Поиск с заменой'

   Ввести три cлова — s, a и b. Вывести строку s, в которой все вхождения a будут заменены на b. Повторную замену (в случае, когда после замены образуются новые вхождения) делать не надо.

   • Поиск и замену вести в один проход среди найденных вхождений a в s в порядке от начала к концу. Например, при s="11111", a="11", b="2" результатом замены должно быть "221".

   • Нет повторной замены: "aba" → "ca" в строке "ababa". Вхождение aba в ababa одно (за первым aba следует только ba) ⇒ результат поиска с заменой — "caba".

   Input:

   xqwedfqweasadsadfaqweqwesdf qwe RTYS

   Output:

   xRTYSdfRTYSasadsadfaRTYSRTYSsdf

2. EJudge: MaxSubstr 'Наибольшая общая подстрока'

   Ввести две строки длиной не более 2000 символов, вывести их наиболее длинную общую подстроку. Если таких подстрок несколько, вывести ту, что следует раньше в первой строке. Если общих подстрок нет, вывести "FAIL".

   Input:

   01uj12qawsed23tgyhej34
   uj-tgyhej-qawsed

   Output:

   qawsed

3. EJudge: PlusFrag 'Плюсфрагменты'

   Ввести последовательность «плюсфрагментов» — цепочек произвольных символов, разделённых символом '+'. Несколько символов-разделителей подряд в строке быть не может. Вывести только фрагменты, целиком состоящие из латинских гласных a, e, i, o, u. Внутри фрагмента могут встречаться пробелы и переводы строки.

   Input:

   qwe+aeuio+sd f+aeeug+ae

   Output:

   aeuio
   ae

4. EJudge: CommaSort 'Сортировка строк'

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

   • Алгоритм устойчивой сортировки сохраняет исходный порядок среди элементов, имеющих одинаковое значение критерия сортировки. Годится «пузырёк».
   Input:

       October 2026    
   Su Mo Tu We Th Fr Sa
                1  2  ,
    4  5  6  7  8  9 10
   11 12 1, 14 15 16 17
   18 19 20 21 22 2, 24
   25 26 27 28 29 ,0 ,1
   󠀠

   Output:

       October 2026    
   Su Mo Tu We Th Fr Sa
    4  5  6  7  8  9 10
   󠀠
                1  2  ,
   11 12 1, 14 15 16 17
   18 19 20 21 22 2, 24
   25 26 27 28 29 ,0 ,1