14. Функции для ввода и вывода строк. Функции, реализующие операции со строками.

Основные функции ввода/вывода
Функция	Ее действия
getchar()	Читает символ с клавиатуры; обычно ожидает возврат каретки
getche()	Читает символ, при этом он отображается на экране; не ожидает возврата каретки; в стандарте С не определена, но распространена достаточно широко
getch()	Читает символ, но не отображает его на экране; не ожидает возврата каретки; в стандарте С не определена, но распространена достаточно широко
putchar()	Отображает символ на экране
gets()	Читает строку с клавиатуры
puts()	Отображает строку на экране

Функция gets() читает строку символов, введенную с клавиатуры, и записывает ее в память по адресу, на который указывает ее аргумент. Символы можно вводить с клавиатуры до тех пор, пока не будет введен символ возврата каретки. Он не станет частью строки, а вместо него в ее конец будет помещен символ конца строки ('0'), после чего произойдет возврат из функции gets(). На самом деле вернуть символ возврата каретки с помощью этой функции нельзя (а с помощью getchar() — как раз можно). Перед тем как нажимать <ENTER>, можно исправлять неправильно введенные символы, пользуясь для этого клавишей возврата каретки на одну позицию (клавишей backspace). Вот прототип для gets():

char *gets(char *cmp);

Функция puts() отображает на экране свой строковый аргумент, после чего курсор переходит на новую строку. Вот прототип этой функции:

int puts(const char *cmp);

puts() признает те же самые управляющие последовательности^[1], что и printf(), например, \t в качестве символа табуляции. Вызов функции puts() требует намного меньше ресурсов, чем вызов printf(). Это объясняется тем, что puts() может только выводить строку символов, но не может выводить числа или делать преобразования формата. В результате эта функция занимает меньше места и выполняется быстрее, чем printf(). Поэтому тогда, когда не нужны преобразования формата, часто используется функция puts().

15 Что такое массив? Почему массив является структурированным типом данных? Ввод/вывод элементов массива. Функция заполнения массивов случайными числами.

Массив — это пронумерованная последовательность величин одинакового типа, обозначаемая одним именем. Элементы массива располагаются в последовательных ячейках памяти, обозначаются именем массива и индексом. Каждое из значений, составляющих массив, называется его компонентой (или элементом массива). Массивы бывают одномерные и многомерные. Массив данных в программе рассматривается как переменная структурированного типа. Массиву присваивается имя, посредством которого можно ссылаться как на массив данных в целом, так и на любую из его компонент. Переменные, представляющие компоненты массивов, называются переменными с индексами в отличие от простых переменных, представляющих в программе элементарные данные. Индекс в обозначении компонент массивов может быть константой, переменной или выражением порядкового типа. Если за каждым элементом массива закреплен только один его порядковый номер, то такой массив называется линейным. Вообще количество индексов элементов массива определяет размерность массива. По этому признаку массивы делятся на одномерные (линейные), двумерные, трёхмерные и т.д.

Пример: числовая последовательность четных натуральных чисел 2, 4, 6, ..., N представляет собой линейный массив, элементы которого можно обозначить А[1]=2, А[2]=4, А[3]=6, ..., А[К]=2*(К+1), где К — номер элемента, а 2, 4, 6, ..., N — значения. Индекс (порядковый номер элемента) записывается в квадратных скобках после имени массива.

Заполнить массив можно следующим образом:1) с помощью оператора присваивания. Этот способ заполнения элементов массива особенно удобен, когда между элементами существует какая-либо зависимость, например, арифметическая или геометрическая прогрессии, или элементы связаны между собой рекуррентным соотношением.

Другой вариант присваивания значений элементам массива — заполнение значениями, полученными с помощью датчика случайных чисел. Над элементами массивами чаще всего выполняются такие действия, как а) поиск значений; б) сортировка элементов в порядке возрастания или убывания; в) подсчет элементов в массиве, удовлетворяющих заданному условию.

Сумму элементов массива можно подсчитать по формуле S=S+A[I] первоначально задав S=0. Количество элементов массива можно подсчитать по формуле К=К+1, первоначально задав К=0. Произведение элементов массива можно подсчитать по формуле P = P * A[I], первоначально задав P = 1.

Язык Си не имеет встроенных средств для ввода-вывода массива целиком, поэтому массив вводят и выводят поэлементно с помощью циклов, как, например, в следующей программе:

1. #include<stdio.h>

2.

3. voidmain(void)

4. {

5. double a[100]; int n, i;

6. printf("Введите количество чисел n = ");

7. scanf("%d", &n);

8. if( n>(sizeof a)/sizeof(double) )

9. { printf("Слишком много элементов\n"); return; }

10. for(i=0; i<n; i++)

11. {

12. printf("a[%d] = ", i); scanf("%lf", &a[i]);

13. }

14.

15. /* Операторы, обрабатывающие массив */

16.

17. }

Следующий фрагмент программы выводит массив строками по 5 элементов. После вывода 120 элементов программа останавливается для просмотра выдачи. Очередные 120 элементов выводятся после нажатия на любую клавишу.

1. for (i=0; i<n; i++)

2. {

3. printf("%10.3lf ", a[i]);

4. if( (i+6) % 5 == 0 ) printf("\n");

5. if( (i+121) % 120 == 0 ) { getch(); clrscr(); }

6. }

Здесь стандартная функция clrscr() очищает экран.Функции и процедуры, используемые для заполнения массива случайными числами:

Random - функция, возвращает случайное вещественное в диапазоне [0..1).

Random(x) -функция, возвращает случайное целое в диапазоне от 0 до x-1.

Randomize - процедура языка Pascal, которая инициализирует встроенный генератор случайных чисел с произвольным значением.

Заполнение массива оператором случайных чисел Random на интервале [0;1):

randomize;

for i:=1 to n do

a[i]:=random;

Пример 1 (.pas) Заполните массив, состоящий из 10 вещественных чисел в диапазоне [0..1):

randomize;

for i:=1 to 10 do

a[i]:=random;

Заполнение массива оператором случайных чисел Random на интервале [ a ; b ]:

randomize;

for i:=1 to n do

a[ i ] := random (b-a+1)+a;

16) Разновидности линейных списков. Дать определение стеку, очереди и двусторонней очереди. Привести примеры.

Понятие линейного списка

Стеки и очереди

Сжатое и индексное хранение линейных списков

Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. Линейный список F, состоящий из элементов D1, D2, ..., Dn, записывают в виде последовательности значений заключенной в угловые скобки F=<D1,D2,...,Dn>. Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d[0]=7; d[1]=10; l=2;

При связанном хранении в качестве элементов хранения используются структуры, связанные по одной из компонент в цепочку, на начало которой (первую структуру) указывает указатель dl. Структура образующая элемент хранения, должна кроме соответствующего элемента списка содержать и указатель на соседний элемент хранения. Описание структуры и указателя в этом случае может иметь вид:

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n ; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

Стеки и очереди В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков называемые стеком, очередью и двусторонней очередью. Стек - это конечная последовательность некоторых однотипных элементов - скалярных переменных, массивов, структур или объединений, среди которых могут быть и одинаковые. Стек обозначается в виде: S=<S1,S2,...,Sn> и представляет динамическую структуру данных; ее количество элементов заранее не указывается и в процессе работы, как правило изменяется. Если в стеке элементов нет, то он называется пустым и обозначается S=< >. Допустимыми операциями над стеком являются: - проверка стека на пустоту S=< >, - добавление нового элемента Sn+1 в конец стека - преобразование <S1,...,Sn> в <S1,...,Sn+1>; - изъятие последнего элемента из стека - преобразование <S1,...,Sn-1,Sn> в <S1,...,Sn-1>; - доступ к его последнему элементу Sn, если стек не пуст. Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху. Очередь - это линейный список, где элементы удаляются из начала списка, а добавляются в конце списка (как обыкновенная очередь в магазине). Двусторонняя очередь - это линейный список, у которого операции добавления и удаления элементов и доступа к элементам возможны как вначале так и в конце списка. Такую очередь можно представить как последовательность книг стоящих на полке, так что доступ к ним возможен с обоих концов. Реализация стеков и очередей в программе может быть выполнена в виде последовательного или связанного хранения. Рассмотрим примеры организации стека этими способами.

Рассмотрим другую задачу. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке (т.е. если на входе будет "ABcEr-1." то на выходе должно быть "1-rEcBA"). Представленная ниже программа сначала вводит все символы последовательности, записывая их в стек, а затем содержимое стека печатается в обратном порядке. Это основная особенность стека - чем позже элемент занесен в стек, тем раньше он будет извлечен из стека. Реализация стека выполнена в связанном хранении при помощи указателей p и q на тип, именованный именем STACK.

#include<stdio.h>

typedef struct st /* объявление типа STACK */

{ char ch;

struct st *ps; } STACK;

main()

{ STACK *p,*q;

char a;

p=NULL;

do /* заполнение стека */

{ a=getch();

q=malloc(sizeof(STR1));

q->ps=p; p=q;

q->ch=a;

} while(a!='.');

do /* печать стека */

{ p=q->ps;free(q);q=p;

printf("%c",p->ch);

} while(p->ps!=NULL);