05-arrays.tex

\documentclass[alsotrans]{beamerswitch}
\usepackage{iprog}

\title{Масиви и низове}

\date{15--29 ноември 2021 г.}

\newcommand{\s}{<низ>\xspace}
\renewcommand{\ss}[1]{<низ$_{#1}$>\xspace}
% do not add space before syntactic element marked by \tta
\xspaceaddexceptions{\tta}
\renewcommand{\b}{<буфер>\xspace}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Масиви}

\begin{frame}
  \frametitle{Логическо описание}

  Масивът
  \begin{itemize}
  \item е съставен тип данни
  \item представя крайни редици от елементи
  \item всички елементи са от един и същи тип
  \item позволява произволен достъп до всеки негов елемент по номер (индекс)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Дефиниция на масив}

  <тип> <идентификатор> \tta[ [<константа] \tta]\\
  \hspace{3em} [ \tta= \tta\{ <израз> \{\tta, <израз> \} \tta\} ] \tta;\\[2ex]
  \pause
  \textbf{Примери:}
  \begin{itemize}[<+->]
  \item \lst{bool b[10];}
  \item \lst{double x[3] = \{ 0.5, 1.5, 2.5 \}, y = 3.8;}
  \item \lst{int a[] = \{ 3 + 2, 2 * 4 \};} \eqv\ \lst{int a[2] = \{ 5, 8 \};}
  \item \lst{float f[4] = \{ 2.3, 4.5 \};} \eqv\ \lst{float f[4] = \{ 2.3, 4.5, 0, 0 \};}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Физическо представяне}

  \scriptsize
  \begin{tabular}{*{11}{|c}|}
    \multicolumn{11}{l}{\tt a}\\
    \hline
    \rowcolor{diagramblue}
    \tt{a[0]}&\tt{a[1]}&\tt{a[2]}&\tt{a[3]}&\tt{a[4]}&\tt{a[5]}&\tt{a[6]}&\tt{a[7]}&\tt{a[8]}&\tt{a[9]}&\tt{a[10]}\\
    \hline
  \end{tabular}
\end{frame}

\begin{frame}
  \frametitle{Операции за работа с масиви}

  \begin{itemize}[<+->]
  \item Достъп до елемент по индекс: <масив>\tta[<цяло\_число>\tta]
  \item \textbf{Примери}:
    \begin{itemize}
    \item \lst{x = a[2];} (\alert{rvalue})
    \item \lst{a[i] = 7;} (\alert{lvalue!})
    \item \alert{Внимание: няма проверка за коректност на индекса!}
    \end{itemize}
  \item Няма присвояване
    \begin{itemize}
    \item \sta{a = b}
    \end{itemize}
  \item Няма поелементно сравнение
    \begin{itemize}
    \item \lst{a == b} винаги връща \lst{false} ако \tta a и \tta b са различни масиви, дори и да имат еднакви елементи
    \end{itemize}
  \item Няма операции за вход и изход
    \begin{itemize}
    \item \sta{cin >{}> a;}
    \item \lst{cout << a;} извежда адреса на \tt{a}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Задачи за масиви}

  \begin{itemize}[<+->]
    \item Да се въведе масив от числа
    \item Да се изведе масив от числа
    \item Да се намери сумата на числата в даден масив
    \item Да се провери дали дадено число се среща в масив
    \item Да се провери дали числата в масив нарастват монотонно
    \item Да се провери дали всички числа в даден масив са различни
    \item Да се подредят числата в даден масив в нарастващ ред
    \item Да се слеят два масива подредени в нарастващ ред
  \end{itemize}
\end{frame}

\section{Низове}

\begin{frame}
  \frametitle{Низове: описание и представяне}

  \begin{itemize}[<+->]
  \item \textbf{Описание:} \alert{Низ} наричаме последователност от символи
    \begin{itemize}
    \item последователност от 0 символи наричаме \alert{празен низ}
    \end{itemize}
  \item \textbf{Представяне в C++:} Масив от символи (\lst{char}), в който след последния символ в низа е записан \alert{терминиращият символ} \term
    \begin{itemize}
    \item \term\ е първият символ в ASCII таблицата, с код 0
    \end{itemize}
  \item \textbf{Примери:}
    \begin{itemize}
    \item \lst{char word[] = \{ 'H', 'e', 'l', 'l', 'o', '\\0' \};}
    \item \lst{char word[6] = \{ 'H', 'e', 'l', 'l', 'o' \};}
    \item \lst{char word[100] = \"Hello\";}
    \item \sta{char word[5] = \quot Hello\quot;}
    \item \lst{char word[6] = \"Hello\";}
    \item \sta{char word[5] = \{ 'H', 'e', 'l', 'l', 'o' \};}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Операции за работа с низове}

  \begin{itemize}[<+->]
  \item Вход (\tta{>{}>}, \tta{cin.getline(}\s, <число>\tta))
    \begin{itemize}
    \item \tta{>{}>} въвежда до разделител (интервал, табулация, нов ред)
    \item \tta{cin.getline(}\s, <число>\tta) въвежда до нов ред, но не повече от <число>$-1$ символа
    \end{itemize}

  \item Изход (\tta{<{}<})
  \item Индексиране (\tta{[]})
  \item Няма присвояване! (\sta{a = b})
  \item Няма поелементно сравнение! (\sta{a == b})
  \item но...
  \item ...има вградени функции!
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Вградени функции за низове}

  \lst{\#include <cstring>}

  \begin{itemize}[<+->]
  \item \tta{strlen(}\s\tta)
    \begin{itemize}
    \item връща дължината на \s, т.е. броя символи без \term
    \end{itemize}
  \item \tta{strcpy(}\b, \s\tta)
    \begin{itemize}
    \item прехвърля всички символи от \s в \b
    \item връща \b
    \item \alert{отговорност на програмиста е да осигури, че в \b да има достатъчно място да поеме всички символи на \s}
    \end{itemize}
  \item \tta{strcmp(}\ss1, \ss2\tta)
    \begin{itemize}
    \item сравнява два низа \alert{лексикографски} (речникова наредба)
    \item връща число $<0$, ако \ss1 е преди \ss2
    \item връща 0, ако \ss1 съвпада с \ss2
    \item връща число $>0$, ако \ss1 е след \ss2
    \item \textbf{Интуиция:} ``знакът'' на ``разликата'' \ss1 $-$ \ss2
    \item \textbf{Свойство:} \lst{strcmp(s1, s2) == -strcmp(s2, s1)}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Вградени функции за низове}

  \begin{itemize}[<+->]
  \item \tta{strcat(}\ss1, \ss2\tta)
    \begin{itemize}
    \item \alert{конкатенация} (слепване) на низове
    \item записва символите на \ss2 в края на \ss1
    \item старият терминиращ символ се изтрива и се записва нов
    \item връща \ss1
    \item \alert{отговорност на програмиста е да осигури, че в \ss1 да има достатъчно място да поеме всички символи на \ss2}
    \end{itemize}
  \item \tta{strchr(}\s, <символ>\tta)
    \begin{itemize}
    \item търсене на <символ> в \s
    \item връща \alert{суфикса} на \s от първото срещане на <символ>
    \item връща 0, ако <символ> не се среща в \s
    \end{itemize}
  \item \tta{strstr(}\s, <подниз>\tta)
    \begin{itemize}
    \item търсене на <подниз> в \s
    \item т.е. символите на <подниз> да се срещат последователно в \s
    \item връща \alert{суфикса} на \s от първото срещане на <подниз>
    \item връща 0, ако <символ> не се среща в \s
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Задачи за низове}

  \begin{itemize}[<+->]
  \item Да се провери дали даден низ е \alert{палиндром}
    \begin{itemize}
    \item чете се еднакво в двете посоки
    \item \lst{\"abba\"}, \lst{\"racecar\"}, \lst{\"risetovotesir\"}, \lst{\"wasitacaroracatisaw\"}
    \end{itemize}
  \item Да се преброят думите в даден низ
    \begin{itemize}
    \item Считаме, че за разделители служат всички символи, които не са букви.
    \end{itemize}
  \item Да се пресметне аритметичен израз, записан в низ
    \begin{itemize}
    \item{} <израз> ::= <число>\{<операция><число>\} \tta=
    \item{} <число> ::= <цифра>\{<цифра>\}
    \item{} <операция> ::= \tta+ | \tta- | \tta* | \tta/ | \tta\%
    \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Ограничени операции}

\begin{frame}
  \frametitle{Проблеми при работа с низове}

  \begin{itemize}[<+->]
  \item Излизане извън буфера (buffer overflow)
    \begin{itemize}
    \item \sta{char a[10] = \quot Hello, world!\quot}
    \item \lst{char b[] = \"Hello,\", c[] = \" world!\";}
    \item \sta{strcat(b, c);}
    \item \sta{strcpy(b, c);}
    \end{itemize}
  \item Нетерминирани низове (non-terminated strings)
    \begin{itemize}
    \item \lst{char word[5] = \{ 'H', 'e', 'l', 'l', 'o' \};}
    \item \sta{cout <{}< strlen(word);}
    \item \lst{char word2[10];}
    \item \sta{strcpy(word2, word);}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Ограничени операции}

  \begin{itemize}[<+->]
  \item \tta{strncpy(}\b, \s, $n$\tta)
    \begin{itemize}
    \item копира първите $n$ символа на \s в \b
    \item винаги записва точно $n$ символа в \b, допълвайки с \term\ при нужда
    \item \alert{ако \s има повече от $n$ символа, не записва \term!}
    \item връща \b
    \end{itemize}
  \item \tta{strncat(}\ss1, \ss2, n\tta)
    \begin{itemize}
    \item конкатенира първите $n$ символа на \ss2 след \ss1
    \item винаги поставя \term на края
    \item \alert{все още е отговорност на програмиста да осигури достатъчно място в \ss1!}
    \item връща \ss1
    \end{itemize}
  \item \tta{strncmp(}\ss1, \ss2, n\tta)
    \begin{itemize}
    \item сравнява първите $n$ символа на \ss1 и \ss2
    \item връща $<0$, $0$ или $>0$, също като \tt{strcmp}
    \end{itemize}
  \end{itemize}
\end{frame}

\section{Многомерни масиви}

\begin{frame}
  \frametitle{Многомерни масиви}

  \begin{tabular}{c|c}
    Масив, чиито елементи...&наричаме\\
    \hline
    ...са масиви,&\alert{многомерен} масив\\
    \tpause
    ...\alert{не са} масиви,&\alert{едномерен} масив\\
    \tpause
    ...са $n$-мерни масиви,&\alert{$n+1$-мерен} масив
  \end{tabular}
  \pause
  \begin{itemize}[<+->]
  \item{} <тип> <идентификатор> \tta[[<константа>]\tta]\{\tta[<константа>\tta]\}\\
  \hspace{3em} [ \tta= \tta\{ <израз> \{\tta, <израз> \} \tta\} ] \tta;
  \item първата размерност може да бъде изпусната, ако е даден инициализиращ списък
  \item \textbf{Примери:}
    \begin{itemize}
    \item \lst{int a[2][3] = \{\{1, 2, 3\}, \{4, 5, 6\}\};}
    \item \lst{double b[5][6] = \{0.1, 0.2, 0.3, 0.4\};}
    \item \lst{int c[4][5] = \{\{1, 2\}, \{3, 4, 5, 6\}, \{7, 8, 9\}, \{10\}\};}
    \item \lst{float f[][2][3] = \{\{\{1.2, 2.3, 3.4\}, \{4.5, 5.6, 6.7\}\},}\\
        \hspace{10em}\lst{\{\{7.8, 8.9, 9.1\}, \{1.2, 3.4, 3.4\}\},}\\
        \hspace{10em}\lst{\{\{5.6\},\{6.7, 7.8\}\}\};}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Физическо представяне на многомерни масиви}

  \begin{center}
    \scalebox{.95}{
      \begin{tabular}{|*{12}{@{\hspace{0.1em}}c@{\hspace{0.1em}}|}}
        \hline
        \multicolumn{12}{|c|}{\tt{a}}\\
        \hline
        \multicolumn{6}{|c|}{\tt{a[0]}}&\multicolumn{6}{|c|}{\tt{a[1]}}\\
        \hline
        \multicolumn{3}{|c|}{\tt{a[0][0]}}&\multicolumn{3}{|c|}{\tt{a[0][1]}}&\multicolumn{3}{|c|}{\tt{a[1][0]}}&\multicolumn{3}{|c|}{\tt{a[1][1]}}\\
        \hline
        \tiny a[0][0][0]&\tiny a[0][0][1]&\tiny a[0][0][2]&\tiny a[0][1][0]&\tiny a[0][1][1]&\tiny a[0][1][2]&\tiny a[1][0][0]&\tiny a[1][0][1]&\tiny a[1][0][2]&\tiny a[1][1][0]&\tiny a[1][1][1]&\tiny a[1][1][2]\\
        \hline
      \end{tabular}}    
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Задачи за многомерни масиви}

  \begin{itemize}[<+->]
  \item Да се въведе от клавиатурата матрица от числа
  \item Да се изведе на екрана матрица от числа
  \item Да се транспонира правоъгълна матрица от числа
  \item Да се намерят сумите на всяка колона в матрица от числа
  \item Да се намерят редовете в матрица от числа, в които се среща $x$
  \item Да се провери дали в матрица от цели числа има колона, чиито най-малък елемент е четно число
  \item Да се изведат елементите на дадена матрица от числа по диагонали
  \item Да се слеят ``шахматно'' две матрици от числа с еднакви размерности
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Обхождане на матрици}

  \tikzset{
    l/.style={thick,red,->,>=stealth},
    m/.style={
      matrix of nodes,
      ampersand replacement=\&,
      nodes={
        rectangle,
        minimum width=1.8em,
        minimum height=2ex,
        text height=1ex,
        text depth=0.25ex,
        draw},
      nodes in empty cells
    }
  }
  \begin{tikzpicture}
    \matrix (a) [m] {
         \&    \&    \&    \& 11 \\
         \&    \&    \& 7  \& 12 \\
         \&    \& 4  \& 8  \& 13 \\
         \& 2  \& 5  \& 9  \& 14 \\
      1  \& 3  \& 6  \& 10 \& 15 \\
    };
   \fill[red] (a-5-1.center) circle [radius=0.3ex];
   \draw[l] (a-4-2.center) -> (a-5-2.center);
   \draw[l] (a-3-3.center) -> (a-5-3.center);
   \draw[l] (a-2-4.center) -> (a-5-4.center);
   \draw[l] (a-1-5.center) -> (a-5-5.center);
   \draw[l] (a-5-1.center) -> (a-1-5.center);
  \end{tikzpicture}
  \begin{tikzpicture}
    \matrix (a) [m] {
      1  \& 3  \& 6  \& 10 \& 15 \\
      2  \& 5  \& 9  \& 14 \&    \\
      4  \& 8  \& 13 \&    \&    \\
      7  \& 12 \&    \&    \&    \\
      11 \&    \&    \&    \&    \\
    };
   \fill[red] (a-1-1.center) circle [radius=0.3ex];
   \draw[l] (a-2-1.center) -> (a-1-2.center);
   \draw[l] (a-3-1.center) -> (a-1-3.center);
   \draw[l] (a-4-1.center) -> (a-1-4.center);
   \draw[l] (a-5-1.center) -> (a-1-5.center);
   \draw[l] (a-1-1.center) -> (a-5-1.center);
  \end{tikzpicture}
  \begin{tikzpicture}
    \matrix (a) [m] {
      1  \& 3  \& 6  \& 10 \& 15 \\
      2  \& 5  \& 9  \& 14 \& 19 \\
      4  \& 8  \& 13 \& 18 \& 22 \\
      7  \& 12 \& 17 \& 21 \& 24 \\
      11 \& 16 \& 20 \& 23 \& 25 \\
    };
   \fill[red] (a-1-1.center) circle [radius=0.3ex];
   \draw[l] (a-2-1.center) -> (a-1-2.center);
   \draw[l] (a-3-1.center) -> (a-1-3.center);
   \draw[l] (a-4-1.center) -> (a-1-4.center);
   \draw[l] (a-5-1.center) -> (a-1-5.center);
   \draw[l] (a-5-2.center) -> (a-2-5.center);
   \draw[l] (a-5-3.center) -> (a-3-5.center);
   \draw[l] (a-5-4.center) -> (a-4-5.center);
   \fill[red] (a-5-5.center) circle [radius=0.3ex];
   \draw[l] (a-1-1.center) |- (a-5-5.center);
  \end{tikzpicture}
  \begin{tikzpicture}
    \matrix (a) [m] {
      1  \&    \&    \&    \&    \\
      2  \& 4  \&    \&    \&    \\
      3  \& 6  \& 9  \&    \&    \\
      5  \& 8  \& 11 \& 13 \&    \\
      7  \& 10 \& 12 \& 14 \& 15 \\
    };
   \fill[red] (a-1-1.center) circle [radius=0.3ex];
   \fill[red] (a-2-1.center) circle [radius=0.3ex];
   \draw[l] (a-3-1.center) -> (a-2-2.center);
   \draw[l] (a-4-1.center) -> (a-3-2.center);
   \draw[l] (a-5-1.center) -> (a-3-3.center);
   \draw[l] (a-5-2.center) -> (a-4-3.center);
   \draw[l] (a-5-3.center) -> (a-4-4.center);
   \fill[red] (a-5-4.center) circle [radius=0.3ex];
   \fill[red] (a-5-5.center) circle [radius=0.3ex];
   \draw[l] (a-1-1.center) |- (a-5-5.center);
  \end{tikzpicture}
  \begin{tikzpicture}
    \matrix (a) [m] {
      1  \& 4  \& 9  \& 16 \& 25 \\
      2  \& 3  \& 8  \& 15 \& 24 \\
      5  \& 6  \& 7  \& 14 \& 23 \\
      10 \& 11 \& 12 \& 13 \& 22 \\
      17 \& 18 \& 19 \& 20 \& 21 \\
    };
   \fill[red] (a-1-1.center) circle [radius=0.3ex];
   \draw[l] (a-2-1.center) -| (a-1-2.center);
   \draw[l] (a-3-1.center) -| (a-1-3.center);
   \draw[l] (a-4-1.center) -| (a-1-4.center);
   \draw[l] (a-5-1.center) -| (a-1-5.center);
   \draw[l] (a-1-1.center) -| (a-5-1.center);
  \end{tikzpicture}
  \begin{tikzpicture}
    \matrix (a) [m] {
      25 \& 10 \& 11 \& 12 \& 13 \\
      24 \& 9  \& 2  \&  3 \& 14 \\
      23 \& 8  \& 1  \&  4 \& 15 \\
      22 \& 7  \& 6  \&  5 \& 16 \\
      21 \& 20 \& 19 \& 18 \& 17 \\
    };
   \draw[l] (a-3-3.center) -- (a-2-3.center) -| (a-4-4.center) -|
   (a-1-2.center) -| (a-5-5.center) -| (a-1-1.center);
  \end{tikzpicture}

\end{frame}

\end{document}