Сцепление двух строк.

Строка-список

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

Представление строки списком может усложнить или, наоборот, упростить отдельные алгоритмы обработки строк (например, сравнение строк)

Рассмотрим реализацию тех же функций обработки строк:

- сцепление двух строк,

- поэлементное сравнение двух строк,

- разбиение строки на несколько частей

- нахождение подстроки.

Сцепление двух строк.

Исходные строки заданы списками; в результате сцепления получаем объединенный список, в котором вторая строка подцеплена к концу первой строки (рис. II-17). Если первая строка задана пустым списком, результатом будет вторая строка. Функция возвращает указатель на результирующую строку-список.

Рис. II‑ 17.

Алгоритм функции приведен на рис. II-18.

Рис. II‑ 18.

Текст функции приводится ниже и в файле Programs/stringl.cpp.

struct Item{

char s;

Item *next;

};

Item *concat(Item *ptr1, Item *ptr2)

{

Item *cur;

/* сначала проверим, что первый список не пуст */

if(! *ptr1)

return ptr2;

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

for(cur = ptr1; cur-> next; cur = cur-> next)

;

/* включаем второй список в конец первого */

cur-> next = ptr2;

return ptr1;

}

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

Item *concat1(Item *ptr1, Item *ptr2)

{

Item **pcur;

/* формируем указатель на поле указателя в последнем элементе списка */

for(pcur = & ptr1; *pcur; pcur = & (*pcur)-> next)

;

/* включаем второй список в конец или вместо первого */

*pcur = ptr2;

return ptr1;

}

Текст данной функции также приводится в файле Programs/stringl.cpp.