Решение задач на обработку строк

Цель лекции: изучить принципы работы со строками и указателями на строки, алгоритмы решения задач на обработку строковых данных, научиться приемам решения задач на обработку строк, используя, функции для работы со строками и указателями на строки в языке С++.

Строки и указатели

Строки в языке С++ представляют собой массив символов. Поскольку имя массива без индексов является указателем на первый элемент этого массива, то при использовании функций обработки строк им будут передаваться не сами строки, а указатели на них.

Так как все строки в языке С++ заканчиваются нулевым символом, который имеет значение <ложь>, то условие в операторе while(*str) будет истинным до тех пор, пока программа не достигнет конца строки.

При разработке функций для работы со строками в большинстве случаев целесообразно применять указатели. Приведем примеры фрагментов программ:

/*Пример пользовательской функции копирования строки s2 в s1*/
char * strcpy_my (char *s1, char *s2){
  char *ptrs1 = s1;
  //указатель инициализирован на начало строки
  while ((*s1++ = *s2++) != 0);
  return ptrs1; //возвращается указатель на строку s1
}

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

/*Пример пользовательской функции конкатенации*/
char * strcat_my (char *s1, char *s2) {
char *p1, *p2;
p1 = s1; p2 = s2;
while ( *p1 != '\0') p1++; //найти конец 1-ой строки.
                           //или while ( *p1) p1++;
  while ((*p1 = *p2) != 0) {
  /*копировать строку р2, пока не будет скопирован нулевой 
    Ограничитель*/
    p1++;  
    p2++; //Передвинуть указатели к следующему байту
  }       //или while (( *p1++ = *p2++) != 0);/*.
return s1;
}

Пример 1.

/*Демонстрация работы с указателями и с функциями для обработки строк*/
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[]){
  char string[100], temp[100], *result, simvol;
  int numresult, res;
  /*создает строку "computer program" посредством 
    использования strcpy и strcat*/
  strcpy(string, "computer");
  result = strcat(string," program"); 
  printf("1) создали строку\n%s\n",result);
  /*находит строку, в которой первый раз обнаружено 'a'*/
  simvol='a';
  result = strchr(string,simvol);    
  printf("2) находим в строке первое вхождение символа \'%c\'\n
          %s\n",simvol,result);
  /* создает копию строки */
  result = strcpy(temp,string);
  printf("3) создали копию строку\n%s\n",result);
  /* находит "a","b","c" в строке */
  strcpy(string,"xyzabbc"); 
  res = strcspn(string,"abc");   
  printf("4) определяем длину заданного сегмента \n%d\n",res);
  /*создает новый указатель на строку для дублирования 
    строки*/
  result = strdup(string);   
  printf("5) создали новый указатель на строку \n%s\n",result);
  system("pause");
  return 0;
}

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

Пример 2.

/*Вывести на экран часть строки после первого пробела*/
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[]){
  char s[80], *p;
  int i;
  printf("ввести строку: ");
  gets(s);
  /*найти первый пробел или конец строки*/
  for(i=0; s[i]  s[i]!=' '; i++);
  p = s[i];
  printf(p);
  system("pause");
  return 0;
}

В этой программе p будет указывать либо на пробел, если он есть, либо на ноль, если в строке нет пробелов. Если p указывает на пробел, то программа выведет на экран его и затем остаток строки. Например, если ввести фразу <язык программирования С++>, функция printf() напечатает сначала пробел и затем <программирования С++>. Если p укажет на ноль, то на экран ничего не выводится.

Пример 3:

//Выводит каждое отдельное слово и подсчитывает его длину
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[]){
  char text[100],*p, *razd=" .,";
  int dlina;
  puts ("Введите текст ");
  gets(text);
  p=strtok(text,razd); // Выделение первого слова текста
  while (p) {  // Пока можно выделить слово
    dlina=strlen(p); // Определение длины слова
    cout << "\n слово "<< p << " длина = " << dlina <<"\n";
    p=strtok(NULL,razd); 
    //Выделение второго, третьего, и т.д. слов
  } 
  system("pause");
  return 0;
}

При использовании строк или указателей на строки в качестве параметров функций следует учитывать некоторые особенности.

При передаче строки как параметра функции не указывается длина, так как ограничителем является символ конца строки.

Строки передаются в функции в качестве параметров как массивы символов или как указатели типа char.

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

Обращение к строкам через указатели позволяет вносить и сохранять изменения, записанные в адресуемой области памяти. Для недопущения изменений в строке указатель на константу можно объявить с лексемой const следующим образом: const char *p;.

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

При копировании строки или подстроки с использованием указателя не создается физической копии значений элементов. Объявленный новый указатель адресует то место в памяти, с которого начинается копируемая строка или подстрока. Например:

char text[50]="Язык программирования";
char *p=text, *pp;
//объявление и инициализация указателя р адресом строки text
pp=p;
//указатель рр адресует ту же строку text

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

Ключевые термины

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

Строки как параметры функций – это описание передачи значений строк в функции как массив символов или указатель типа char.

Указатель на строку – адрес начала расположения строки в памяти.

Краткие итоги

Лабораторная работа 9. Решение задач на обработку строк

Цель работы: изучить принципы работы со строками и указателями на строки, алгоритмы решения задач на обработку строковых данных, научиться приемам решения задач на обработку строк, используя, функции для работы со строками и указателями на строки в языке С++.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 9.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Введите строку символов латинского алфавита:
AtTimesYouMayWantToReadDataFromTheKeyBoard
Полученная строка: At Times You May Want To Read Data 
From The Key Board

Введите арифметическое выражение,
например, 45+5-3-125+2 (пробелы и другие знаки недопустимы)
354-457+74+2-37
Значение выражения 354-457+74+2-37 = -64

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученными методами обработки строковых и символьных данных в языке С++. При разработке программного кода требуется использовать метод процедурной абстракции и комментировать фрагменты кода.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы