26. Строки, их структура. Основные операции над строками.

В языке C++ нет строкового типа данных: строка – это всего лишь массивы символов, заканчивающийся символом с кодом, равным нулю (нуль-символом)

Синтаксис объявления строковой переменной: char <имя строки> “[“<размер строки>”]” [=<строковый литерал>]

Размер строки задается константным выражением целого типа

Строковый литерал – это последовательность символов, заключенная в кавычки. может включать также и управляющие символы ‘\t’ и ‘\n’

Массив для хранения строки может быть объявлен без инициализации: char a[10], b[n];

Если строковая переменная инициализируется при объявлении, то ее размен можно не указывать – он устанавливается компилятором равным длине инициализирующего строкового литерала char a[] = «Строка комментария»;

Так как строки являются массивами, то для них неприменимы операции присваивания

Кроме инициализации при объявлении, значение строковой переменной может быть задано путем ввода его с клавиатуры: scanf(“%s”, str);

Обработку строк можно вести, используя возможности посимвольного доступа

Например, определение длины строки str реализуется циклом: for (ls=0; str[ls]; ls++) ;

Аналогичный цикл можно использовать для копирования строки str2 в строку str1: for (int i=0; str1[i] && str2[i] ; str1[i] = str2[i++] );

# include <string.h>

Функция strcpy (dest, src) Копирует содержимое строки src в строку dest, заменяя старое содержимое этой строки

Функция strncpy (dest, src, n) Заменяет первые n символов строки dest первыми n символами строки src. Обе функции возвращают обновленную

строку dest

Функция strcat (dest, src)

Добавляет содержимое строки src к строке dest, заменяя старое содержимое этой строки

Функция strncat (dest, src, n)

Добавляет первые n символов строки src к строке dest

Обе функции возвращают обновленную строку dest

Функция strcmp (str1, str2)

Сравнивает содержимое строки str1 с содержимым строки str2

Функция strncmp (str1, str2, n)

Сравнивает первые n символов строк str1 и str2

Сравнение выполняется по лексикографическому принципу

Определение длины строки Функция strlen (str1)

Возвращает длину строки (без нулевого символа конца строки)

Поиск подстроки

Функция strstr (str, sub)

Ищет первое вхождение подстроки sub в строку str

Если подстрока обнаружена, то функция возвращает указатель на то место в строке str, с которого начинается подстрока

Если подстрока не обнаружена, то возвращается специальное значение, обозначаемое как NULL

Указатель на подстраку

Значение, возвращаемое функцией strstr может быть сохранено в отдельной переменной (указателе)

Такая переменная объявляется следующим образом:

char* <имя переменной>;

Например:

char* w; w = strstr (s, substr);

В дальнейшем с этой переменной можно работать как с обычной строкой

Поиск символа strchr (str, ch) – ищет первое вхождение символа ch в строке str;

strrchr(str, ch) - поиск символа ch, начиная с конца строки str;

strcspn (sr1, str2) – возвращает индекс первого символа в строке string1, который не принадлежит множеству символов string2, т.е. длину начальной подстроки в строке string1, которая полностью состоит из символов строки string2;

разбор строки Функция strtok(str, list) - возвращает следующий токен (элемент разбора), определяемый списком разделителей

Списки

Cвязь элементов Динамических структур

• Переменные, входящие в состав динамических структур, необходимо каким-либо образом связывать друг с другом

• Поэтому каждый элемент динамической структуры должен содержать один или несколько адресов связанных с ним элементов, т.е. ссылок на эти элементы

Линейные списки

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

• В результате получается динамическая структура, называемая линейным списком

• Между элементами линейного списка существует отношение предыдущий-последующий

Тип данных элемента списка

• Для элемента линейного списка можно определить следующий тип данных:

struct Element

{ Tdata info;

Element *next;

};

• Здесь Tdata – встроенный или определенный программистом тип данных информационного поля

Линейный список

Cоздание списка

• Для создания списка необходимо выполнить следующие действия:

1. определить указатель на начало списка

2. определить рабочую переменную-указатель

3. создать первый элемент списка с помощью указателя на начало

4. создать новый элемент с помощью рабочего указателя

5. связать новый элемент с первым элементом списка

1. переместить указатель на начало на новый элемент

2. если список не завершен, то перейти к пункту 4

• При таком алгоритме создания списка его элементы располагаются в порядке, обратном порядку ввода, что не всегда бывает удобным

• Предпочтительным был бы следующий способ создания списка

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

1. определить указатель на начало списка

2. определить рабочую переменную-указатель

3. создать первый элемент списка с помощью указателя на начало

4. присвоить рабочему указателю значение указателя на начало списка

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

6. присвоить рабочему указателю значение поля ссылки, адресуемого им элемента

7. если список не завершен, то перейти к пункту 5

Операции над списками

• добавление элемента в указанное место списка

• удаление элемента из списка

• поиск в списке элемента с заданным значением

Добавление элемента в список

• Новый элемент может быть добавлен в список до или после указанного

• Начнем рассмотрение со второго случая

• Пусть задан указатель p на начало списка и указатель q на некоторый элемент списка

• Требуется вставить новый элемент после элемента, адресуемого указателем q

Добавление после указанного элемента

• Алгоритм добавления нового элемента после указанного:

1. определить рабочий указатель r

2. создать с его помощью новый элемент и записать в него требуемое значение

3. связать новый элемент с элементом, следующим за указанным

4. связать указанный элемент с новым элементом

Добавление до указанного элемента

• Эта задача фактически сводится к предыдущей:

1. добавить новый элемент после указанного

2. скопировать в него значение , хранящееся в указанном элементе

3. записать в указанный элемент требуемое значение

Удаление элемента из списка

• Для удаления элемента необходимо иметь ссылку на предшествующий ему элемент

• Пусть задан указатель p на начало списка и указатель q на элемент списка, предшествующий удаляемому

• Требуется удалить элемент, следующий за указанным

Поиск в списке

• Алгоритм сводится к последовательному перемещению вдоль списка с помощью рабочего указателя q

Типы

typedef тип новое_имя_типа;

typedef тип новое_имя_типа [размер];

typedef unsigned int UNIT;

typedef char Msg[100];

UNIT i, j;

Msg err, str[10]; //строка, массив из 10 строк

Структуры

typedef struct

{ тип_1 поле_1;

тип_2 поле_2;

. . .

тип_n поле_n;

}; имя_типа

struct Worker // без typedef, сразу пилим имя

{ char fio [30];

int age, code;

double salary;

} ;

Worker fitter, turner;

fitter = {“”, 31, 215, 12500.00};

а можно и без имени, сразу запиливая переменные:

struct

{ char fio [30];

int age, code;

double salary;

} staff [100], smith;

Доступ: <имя структуры>.<имя_поля>

Объединения:

union имя_типа

{ тип_1 поле_1;

тип_2 поле_2;

. . .

тип_n поле_n;

};

То же самое, только другое расположение в памяти

Ввод-вывод в файлах

Файлы

FILE *file; //имя файловой переменной

file=fopen(“<адрес файла>”, “r”/*режим потока*/)

//откр. файл. потока в заданном реж.

/* r – чтение

w – запись поверх существующих символов

а – запись в конец файла

(Если файлов не существует, они будут созданы)

r+ - чтение и запись, файл должен существовать

w+ - чтение и запись, ранее созданные данные уничтожатся,

файл должен существовать

а+ - чтение и добавл., открыть файл для чтения и добавл.,

может создавать файл при его отсутствии */

char c,s[100];

rewind(file);

fgets (s, 100, file); //счит. из файла заданн. число симв. в массив

FILE *file2=fopen(“<адрес второго файла>”, “a”);

fputs (s, 100, file2); //запись в файл заданн. число симв. из массива

fgetc (c, file); //считывание из файла одиночн. символа

fputc (c, file2); //запись в файл одиночн. символа

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

Определение стека

• Стек — это структура, работа с которой происходит по принципу LIFO: последним пришел — первым ушел (от англ. Last - In - First - Out)

• Включение элемента в стек и удаление элемента из стека выполняются только с одной стороны, которая называется вершиной стека

Основные операции над стеком

• Инициализация стека, то есть подготовка структуры;

• Включение нового элемента в стек (англ. push – заталкивать);

• Проверка стека на пустоту;

• Исключение элемента из стека (англ. pop – выталкивать).

Структура стека

• Структуру стека и действия со стеком определим следующим образом:

struct Element

{

Tdata info;

Element *next;

};

typedef Element * Tstack;

Tstack top;

Инициализация и проверка на пустоту

void InitStack(Tstack &s)

{ // инициализация стека

s = NULL;

}

 

bool StackIsEmpty(Tstack s)

{ // проверка на пустоту

return s = = NULL;

}

Выборка из стека

Tdata PopStack(Tstack &s)

{ // взять из стека

Tdata x = s->info;

Tstack q = s;

s = s->next;

delete q;

return x;

}

Добавление в стек

void PushStack(Tstack &s, Tdata x)

{ // поместить в стек

Tstack q = new Tstack;

q->info = x;

q->next = s;

s = q;

}

51. Понятие алгоритма. Свойства алгоритмов. Язык программирования как способ записи алгоритмов. Синтаксис, семантика языков программирования. Этапы обработки программы. Препроцессорная обработка, директивы препроцессора. 

Алгоритм – описание последовательности действий над некоторыми объектами (данными), направленное на получение полностью определяемого этими данными результата Свойства алгоритма дискретность: состоит из отдельных шагов (команд) понятность: должен включать только команды, известные исполнителю (входящие в СКИ) определенность: при одинаковых исходных данных всегда выдает один и тот же результат конечность: заканчивается за конечное число шагов массовость: может применяться многократно при различных исходных данных корректность: дает верное решение при любых допустимых исходных данных

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

Семантические правила вскрывают смысловое содержание текста

Постановка задачи Поиск алгоритма решения Разработка программы Выполнение программы Анализ результатов

текстовый редактор для создания и редактирования текстов программ транслятор для перевода текстов программ на Си и Си++ в команды процессора компоновщик для создания исполняемого файла (EXE-файла), подключаются стандартные функции отладчик для поиска ошибок в программах

Список ключевых слов С++
asm	else	new	this
auto	enum	operator	throw
bool	explicit	private	true
break	export	protected	try
case	extern	public	typedef
catch	false	register	typeid
char	float	reinterpret_cast	typename
class	for	return	union
const	friend	short	unsigned
const_cast	goto	signed	using
continue	if	sizeof	virtual
default	inline	static	void
delete	int	static_cast	volatile
do	long	struct	wchar_t
double	mutable	switch	while
dynamic_cast	namespace	template

52. Алфавит языка программирования C++ – основные символы, специальные символы, зарезервированные слова.

Имена, правила записи имен. 

Алфавит языка C++ состоит из:

• "

  { }

  ,

  |

  [ ]

  ( )

  +

  -

  /

  %

  *

  .

  \

  '

  :

  ?

  <

  =

  >

  !

  &

  #

  ~

  ;

  ^

  букв латинского алфавита A..Z, a..z

• цифр 0..9

• специальных символов

• зарезервированных слов

В тексте программы делается различие между прописными и строчными буквами: язык C++ является регистро-зависимым (case-sensitive)

Алфавит языка, или его символы — это основные неделимые знаки, с помощью которых пишутся все тексты на языке.

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

• В составных именах в качестве разделителя можно использовать символ подчеркивания (_)

53. Блочная структура программы на языке C++. Описание меток, констант, переменных. Области видимости объектов. 

54. Типы данных. Простые типы данных в языке C++, их краткая характеристика. 

• Основные типы данных называют также стандартными, поскольку они присутствуют во всех реализациях языка, и арифметическими, т.к. данные этих типов можно использовать в арифметических выражениях.

• Основные типы в свою очередь делятся на целые и вещественные:

Для задания целых типов используются ключевые слова: int – целый тип char – символьный тип wchar_t – расширенный символьный тип bool – логический тип Для задания вещественных типов используются ключевые слова: float – одинарная точность double – двойная точность

При задании типов данных можно использовать спецификаторы типов: short – короткий long – длинный signed – знаковый unsigned – беззнаковый Спецификаторы уточняют внутреннее представление и диапазон значений стандартных типов

55. Целые типы данных в языке C++. Литералы целого типа. 

• Тип	Диапазон	Длина
  bool	0, 1	1 байт
  signed char	-128 … 127	1 байт
  unsigned char	0 … 255	1 байт
  signed wchar_t	–32768 ... 32767	2 байта
  unsigned wchar_t	0 … 65535	2 байта
  signed short int	–32768 ... 32767	2 байта
  unsigned short int	0 … 65535	2 байта
  signed long int	–2147483648..2147483647	4 байта
  unsigned long int	0 … 4294967295	4 байта

  Содержат одну или более цифр и, возможно, предшествующие цифрам знаки + или -..

• При определении значения литерала нули в его левой части игнорируются

• Литералы целого типа могут записываться с использованием шестнадцатеричной системы счисления. В этом случае им должен предшествовать символ $

• Например: $2A3 $-FFF4 -$134

При задании типов можно использовать отдельные слова: int, char, short, long, unsigned

• Это эквивалентно: long signed int, signed char, signed short int, signed long int, unsigned int, соответственно

• В памяти компьютера целые числа представляются в двоичной системе счисления

• Для знаковых типов (int, signed short int и signed long int) старший разряд является знаковым: s=0 для положительных чисел ; s=1 для отрицательных чисел

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

• Например значение переменной типа char, равное 25 представляется кодом 00011001,а значение -25 представляется кодом: 11100111