С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 41
Текст из файла (страница 41)
Если этот параметр не задан, поискначинается с первого элемента. (Поскольку мы добавляем второй параметр, имеющийзначение по умолчанию, открытый интерфейс данной функции не меняется. Программы,class ilist {public:// ...ilist_item* find( int value, ilist_item *start_at = 0 );// ...использующие предыдущую версию find(), будут работать без модификации.)};Упражнение 5.19Используя новую версию find(), напишите функцию count(), которая подсчитываетколичество вхождений элементов с заданным значением.
Подготовьте тестовуюпрограмму.Упражнение 5.20Модифицируйте insert(int value) так, чтобы она возвращала указатель навставленный объект ilist_item.Упражнение 5.21void ilist::insert( ilist_item *begin,int *array_of_value,Используя модифицированную версию insert(), напишите функцию:int elem_cnt );где array_of_value указывает на массив значений, который нужно вставить в ilist,elem_cnt – на размер этого массива, а begin – на элемент, после которого производитсявставка. Например, если есть ilist:(3)( 0 1 21 )и массив:int ia[] = { 1, 2, 3, 5, 8, 13 };вызов этой новой функции242С++ для начинающихilist_item *it = mylist.find( 1 );mylist.insert( it, ia, 6 );изменит список таким образом:(9) ( 0 1 1 2 3 5 8 13 21 )Упражнение 5.22Функции concat() и reverse() модифицируют оригинальный список.
Это не всегдажелательно. Напишите аналогичную пару функций, которые создают новый объектilist ilist::reverse_copy();ilist:ilist ilist::concat_copy( const ilist &rhs );243С++ для начинающих6. Абстрактные контейнерные типыВ этой главе мы продолжим рассмотрение типов данных, начатое в главе 3,представим дополнительную информацию о классах vector и string ипознакомимся с другими контейнерными типами, входящими в состав стандартнойбиблиотеки С++. Мы также расскажем об операторах и выражениях, упомянутых вглаве 4, сосредоточив внимание на тех операциях, которые поддерживаютсяобъектами контейнерных типов.Последовательный контейнер содержит упорядоченный набор элементов одного типа.Можно выделить два основных типа контейнеров – вектор (vector) и список (list).(Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает туже функциональность, что и vector, но особенно эффективно реализует операциивставки и удаления первого элемента.
deque следует применять, например, приреализации очереди, из которой извлекается только первый элемент. Все сказанное нижеотносительно вектора применимо также и к deque.)Ассоциативный контейнер эффективно реализует операции проверки существования иизвлечения элемента. Два основных ассоциативных контейнера – это отображение(map) и множество (set). map состоит из пар ключ/значение, причем ключиспользуется для поиска элемента, а значение содержит хранимую информацию.Телефонный справочник хорошо иллюстрирует понятие отображения: ключом являетсяфамилия и имя абонента, а значением – его телефонный номер.Элемент контейнера set содержит только ключ, поэтому set эффективно реализуетоперацию проверки его существования.
Этот контейнер можно применить, например, приреализации системы текстового поиска для хранения списка так называемых стоп-слов –слов, не используемых при поиске, таких, как и, или, не, так и тому подобных.Программа обработки текста считывает каждое слово и проверяет, есть ли оно вуказанном списке. Если нет, то слово добавляется в базу данных.В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Дляподдержки дубликатов существуют контейнеры multimap и multiset.
Например,multimap можно использовать при реализации такого телефонного справочника, вкотором содержится несколько номеров одного абонента.В последующих разделах мы детально рассмотрим контейнерные типы и разработаемнебольшую программу текстового поиска.6.1. Система текстового поискаВ систему текстового поиска входят текстовый файл, указанный пользователем, исредство для задания запроса, состоящего из слов и, возможно, логических операторов.Если одно или несколько слов запроса найдены, печатается количество их вхождений.
Пожеланию пользователя печатаются предложения, содержащие найденные слова.244С++ для начинающихНапример, если нужно найти все вхождения словосочетаний Civil War и CivilRights, запрос может выглядеть таким образом9:Civil && ( War || Rights )Результат запроса:Civil: 12 вхожденийWar: 48 вхожденийRights: 1 вхождениеCivil && War: 1 вхождениеCivil && Rights: 1 вхождение(8) Civility, of course, is not to be confused withCivil Rights, nor should it lead to Civil WarЗдесь (8) представляет собой номер предложения в тексте. Наша система должна печататьфразы, содержащие найденные слова, в порядке возрастания их номеров (т.е.предложение номер 7 будет напечатано раньше предложения номер 9), не повторяя однуи ту же несколько раз.Наша программа должна уметь:•запросить имя текстового файла, а затем открыть и прочитать этот файл;•организовать внутреннее представление этого файла так, чтобы впоследствиисоотнести найденное слово с предложением, в котором оно встретилось, иопределить порядковый номер этого слова ;•понимать определенный язык запросов.
В нашем случае он включаетследующие операторы:&& два слова непосредственно следуют одно за другим в строке|| одно или оба слова встречаются в строке! слово не встречается в строке() группировка слов в запросеИспользуя этот язык, можно написать:Lincolnчтобы найти все предложения, включающие слово Lincoln, или9 Замечание. Для упрощения программы мы требуем, чтобы каждое слово было отделенопробелом от скобок и логических операторов. Таким образом, запросы вида(War || Rights)Civil&&(War||Rights)не будут поняты нашей системой. Хотя удобство пользователей не должноприноситься в жертву простоте реализации, мы считаем, что в данном случаеможно смириться с таким ограничением.245С++ для начинающих246! Lincolnдля поиска фраз, не содержащих такого слова, или же( Abe || Abraham ) && Lincolnдля поиска тех предложений, где есть словосочетания Abe Lincoln или Abraham Lincoln.Представим две версии нашей системы.
В этой главе мы решим проблему чтения ихранения текстового файла в отображении, где ключом является слово, а значением –номер строки и позиции в строке. Мы обеспечим поиск по одному слову. (В главе 17 мыреализуем полную систему поиска, поддерживающую все указанные выше операторыязыка запросов с помощью класса Query.) .Возьмем шесть строчек из неопубликованного детского рассказа Стена Липпмана (StanLippman)10:Рис. 2.Alice Emma has long flowing red hair.
Her Daddy says when thewind blows through her hair, it looks almost alive, like afiery bird in flight. A beautiful fiery bird, he tells her,magical but untamed. "Daddy, shush, there is no such thing,"she tells him, at the same time wanting him to tell her more.Shyly, she asks, "I mean. Daddy, is there?"После считывания текста его внутреннее представление выглядит так (процесссчитывания включает ввод очередной строки, разбиение ее на слова, исключение знаковпрепинания, замену прописных букв строчными, минимальная поддержка работы ссуффиксами и исключение таких слов, как and, a, the):alice ((0,0))alive ((1,10))almost ((1,9))ask ((5,2))beautiful ((2,7))bird ((2,3),(2,9))blow ((1,3))daddy ((0,8),(3,3),(5,5))emma ((0,1))fiery ((2,2),(2,8))flight ((2,5))flowing ((0,4))hair ((0,6),(1,6))has ((0,2))like ((2,0))long ((0,3))look ((1,8))magical ((3,0))mean ((5,4))more ((4,12))red ((0,5))same ((4,5))say ((0,9))she ((4,0),(5,1))shush ((3,4))shyly ((5,0))such ((3,8))tell ((2,11),(4,1),(4,10))10 Иллюстрация Елены Дрискилл (Elena Driskill).С++ для начинающихthere ((3,5),(5,7))thing ((3,9))through ((1,4))time ((4,6))untamed ((3,2))wanting ((4,7))wind ((1,2))Ниже приводится пример работы программы, которая будет реализована в данномразделе (то, что задает пользователь, выделено курсивом):please enter file name: alice_emmaenter a word against which to search the text.to quit, enter a single character ==> alicealice occurs 1 time:( line 1 ) Alice Emma has long flowing red hair.
Her Daddy saysenter a word against which to search the text.to quit, enter a single character ==> daddydaddy occurs 3 times:( line 1 ) Alice Emma has long flow-ing red hair. Her Daddy says( line 4 ) magical but untamed. "Daddy, shush, there is no such thing,"( line 6 ) Shyly, she asks, "I mean, Daddy, is there?"enter a word against which to search the text.to quit, enter a single character ==> phoenixSorry.
There are no entries for phoenix.enter a word against which to search the text.to quit, enter a single character ==> .Ok, bye!Для того чтобы реализация была достаточно простой, необходимо детально рассмотретьстандартные контейнерные типы и тип string, представленный в главе 3.6.2. Вектор или список?Первая задача, которую должна решить наша программа, – это считывание из файлазаранее неизвестного количества слов. Слова хранятся в объектах типа string.Возникает вопрос: в каком контейнере мы будем хранить слова – в последовательном илиассоциативном?С одной стороны, мы должны обеспечить возможность поиска слова и, в случае успеха,извлечь относящуюся к нему информацию.
Отображение map является самым удобнымдля этого классом.Но сначала нам нужно просто сохранить слова для предварительной обработки –исключения знаков препинания, суффиксов и т.п. Для этой цели последовательныйконтейнер подходит гораздо больше. Что же нам использовать: вектор или список?Если вы уже писали программы на С или на С++ прежних версий, для вас, скорее всего,решающим фактором является возможность заранее узнать количество элементов.
Еслиэто количество известно на этапе компиляции, вы используете массив, в противномслучае – список, выделяя память под очередной его элемент.Однако это правило неприменимо к стандартным контейнерам: и vector, и dequeдопускают динамическое изменение размера. Выбор одного из этих трех классов должен247С++ для начинающихзависеть от способов, с помощью которых элементы добавляются в контейнер иизвлекаются из него.Вектор представляет собой область памяти, где элементы хранятся друг за другом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
