Podstawowe operacje na łańcuchach znakowych


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Podstawowe operacje na tablicach
  Deklaracja zmiennych znakowych
Kod znaku
Konkatencja – łączenie łańcuchów
Wstawianie znaku do łańcucha
Usuwanie znaku z łańcucha
Zastępowanie fragmentu łańcucha innym
Porównywanie łańcuchów
Pozostałe operacje tekstowe

 

Deklaracja zmiennych znakowych i dostęp do przechowywanych znaków

We współczesnych językach programowania znaki są podstawowym typem danych. W pamięci komputera znak jest przechowywany w postaci liczby, którą nazywamy kodem znaku (ang. character code). Każdy znak posiada swój własny kod. Aby różne urządzenia systemu komputerowego mogły w ten sam sposób interpretować kody znaków, opracowano kilka standardów kodowania liter. Poniżej przedstawiamy wybrane dwa:

 

ASCII – American Standard Code for Information Interchange – Amerykański Standardowy Kod do Wymiany Informacji.

 

Znaki są zapamiętywane w postaci 8 bitowych kodów (pierwotnie było to 7 bitów, lecz później standard ASCII został poszerzony na 8 bitów, w których znalazły się różne znaki narodowe). Taki sposób reprezentacji znaków jest dzisiaj bardzo wygodny, ponieważ podstawowa komórka pamięci komputera IBM przechowuje właśnie 8 bitów. Dzięki temu znaki dobrze mieszczą się w pamięci.

8-bitowy kod pozwala przedstawić 256 różnych wartości i tylko tyle może być zdefiniowane znaków w kodzie ASCII. Pierwsza połówka zbioru kodów – od 0 do 127 – jest zdefiniowana na stałe i raczej nigdy nie jest modyfikowana. Jest to tzw. podstawowy zestaw znaków ASCII. Druga połówka – od 128 do 255 – zawiera znaki narodowe, które w różny sposób mogą być przydzielane rozszerzonym kodom ASCII. Z tego właśnie powodu powstały różne strony kodowe. Na przykład konsola znakowa stosuje kodowanie LATIN II. Natomiast system Windows stosuje Windows 1250. Niestety, w obu systemach polskie literki posiadają różne kody. Dlatego wyświetlenie przygotowanego w Windows polskiego tekstu w konsoli znakowej powoduje, iż polskie znaki Windows 1250 zostają źle zinterpretowane w konsoli LATIN II.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Poniższy program demonstruje niekompatybilność kodowania znaków w Windows ze znakami wyświetlanymi w oknie konsoli znakowej.

 

Lazarus Code::Blocks Free Basic
program prg;

begin
  writeln('ĄąĆćĘꣳŃńÓ󌜏źŻż');
end.
#include <iostream>

using namespace std;

int main()
{
  cout << "ĄąĆćĘꣳŃńÓ󌜏źŻż\n";
  return 0;
}
Print "ĄąĆćĘꣳŃńÓ󌜏źŻż"
End
ĄąĆćĘꣳŃńÓ󌜏źŻż ą╣ĂŠ╩ŕú│нˡîťĆč»┐ ą╣ĂŠ╩ŕú│нˡîťĆč»┐

 

Unicode

Znaki są zapamiętywane w postaci kodów 16-bitowych. Dzięki temu rozwiązaniu liczba możliwych do przedstawienia znaków rośnie do 65536. Pierwsze 256 kodów jest zwykle kompatybilne z kodami ASCII. Kody powyżej 256 tworzą banki znaków, w których znajdują się wszystkie znaki narodowe, arabskie, hebrajskie, matematyczne itp.

 

Poniższa tabelka prezentuje nazwy typów znakowych w wybranych przez nas językach programowania:

 

  Lazarus Code::Blocks Free Basic
ASCII
char
unsigned char
String * 1
Unicode
widechar
wchar
wchar_t
Wstring * 1

 

W języku Free Basic nie ma prostego typu znakowego. W tym charakterze używamy łańcucha znakowego o stałej długości 1, o czym piszemy dalej.

 

Zmienne znakowe deklarujemy w identyczny sposób jak zmienne innych typów:

 

  Lazarus Code::Blocks Free Basic

Deklaracja
zmiennej
znakowej

...
var
  c  : char;
  wc : wchar;
...
...
char c;
wchar_t wc;
...
...
Dim c  As String * 1
Dim wc As Wstring * 1
...
 

 

Tak zadeklarowana zmienna c może przechowywać jeden znak ASCII, a zmienna wc jeden znak Unicode.

Zmienne znakowe mogą również być zadeklarowane jako tablice znaków.

 

  Lazarus Code::Blocks Free Basic

Deklaracja
tablicy
znakowej

...
var
  c  : array[0..99] of char;
  wc : array[0..99] of wchar;
...
...
char     c[100];
wchar_t wc[100];
...
...
Dim  c As String  * 100
Dim wc As Wstring * 100
...

 

W przypadku tablicy znakowej mamy dostęp do poszczególnych znaków za pomocą indeksu w klamerkach kwadratowych. Wyjątkiem jest język Basic, gdzie zmienna znakowa jest traktowana jako spójna całość i dostęp do poszczególnych znaków uzyskujemy poprzez polecenie Mid (przy zapisie do zmiennej) oraz funkcję Mid (przy odczycie ze zmiennej). Pierwszy znak posiada zawsze indeks równy 1.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tworzy trzyznakową tablicę i wpisuje do niej wyraz ALO. Następnie literki są wypisywane w kierunku odwrotnym:

 

Lazarus Code::Blocks Free Basic
program prg;

var
  s : array[0..2] of char;

begin
  s[0] := 'A';
  s[1] := 'L';
  s[2] := 'O';
  writeln(s[2],s[1],s[0]);
end.
#include <iostream>

using namespace std;

int main()
{
  unsigned char s[3];
  
  s[0] = 'A';
  s[1] = 'L';
  s[2] = 'O';
  cout << s[2] << s[1] << s[0]
       << endl << endl;
  return 0;
}
Dim s As String * 3

Mid(s,1) = "A"
Mid(s,2) = "L"
Mid(s,3) = "O"
Print Mid(s,3,1);
Print Mid(s,2,1);
Print Mid(s,1,1)
End
Wynik
  OLA  

 

Oprócz zwykłych tablic znakowych (ang. character tables), języki Pascal, C++ oraz Basic udostępniają tzw. łańcuchy znakowe (ang. character strings). Są to tablice dynamiczne, które mogą przechowywać ciągi znaków o różnych długościach (łańcuchy automatycznie dopasowują się do rozmiaru przechowywanego tekstu – tablice znakowe natomiast nie posiadają takich cech, programista musi o to zadbać sam):

 

  Lazarus Code::Blocks Free Basic
łańcuch ASCII
ansistring
string
String
łańcuch Unicode
widestring
wstring
Wstring Ptr
 

 

Koniec łańcucha znakowego znaczony jest kodem 0. Znak o tym kodzie nie jest wliczany do łańcucha. Również nie powinieneś tego znaku umieszczać wewnątrz łańcucha, gdyż może to spowodować nieprawidłowe działanie wielu funkcji i procedur tekstowych.

W języku Pascal i Basic indeksy znaków w łańcuchu rozpoczynają się od 1, a w języku C++ od 0. W algorytmach tekstowych musimy wziąć na to poprawkę.

W języku Basic łańcuchy Wstring są wskaźnikami do obszaru pamięci przechowującego właściwe znaki. Dlatego do wskaźnika musi być przypisywany adres zarezerwowanego obszaru, w którym będą umieszczane znaki Unicode. Dostęp do danych następuje poprzez operator *, podobnie jak w języku C++.

Liczbę znaków przechowywanych w łańcuchu tekstowym otrzymamy przy pomocy następujących funkcji:

 

  Lazarus Code::Blocks Free Basic
Długość łańcucha
length(s)
s.length()
s.size()
Len(s)

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Programy demonstrują sposoby deklarowania zmiennej łańcuchowej oraz dostępu do znaków zawartych w łańcuchu.

 

Lazarus Code::Blocks Free Basic
program prg;

var
  s : ansistring;
  i : integer;

begin
  s := 'Hello there!!!';
  for i := length(s) downto 1 do
    write(s[i]);
  writeln; writeln;
end.
#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  s = "Hello there!!!";
  for(int i = s.length()-1; i >= 0; i--)
    cout << s[i];
  cout << endl << endl;
  return 0;
}
Dim s As String
Dim i As Integer

s = "Hello there!!!"
For i = Len(s) To 1 Step - 1
  Print Mid(s,i,1);
Next
Print: Print
End
program prg;

var
  s : widestring;
  i : integer;

begin
  s := 'Hello there!!!';
  for i := length(s) downto 1 do
    write(s[i]);
  writeln; writeln;
end.
#include <iostream>
#include <string>

using namespace std;

int main()
{
  wstring s;
  s = L"Hello there!!!";
  for(int i = s.length()-1; i >= 0; i--)
    cout << (char)s[i];
  cout << endl << endl;
  return 0;
}
Dim s As Wstring Ptr
Dim i As Integer

s = Allocate(20 * Len(Wstring))
*s = "Hello there!!!"
For i = Len(*s) To 1 Step - 1
  Print Mid(*s,i,1);
Next
Print: Print
End
Wynik
  !!!ereht olleH  
 

Kod znaku

Przy przetwarzaniu tekstu często musimy odczytywać kody znaków zawartych w zmiennej znakowej lub zamieniać kody na odpowiadające im znaki – na przykład w celu umieszczenia ich w tekście. W każdym z wybranych przez nas języków programowania istnieją odpowiednie do tego zadania narzędzia.

 

  Lazarus Code::Blocks Free Basic
dostęp do kodu znaku
ord(znak)
(int)znak
Asc(znak)
zamiana kodu na znak
chr(kod)
(char) kod
Chr(kod)

 

Język C++ traktuje znaki jak liczby całkowite (unsigned char – bez znaku, char – ze znakiem). Nie ma zatem zwykle potrzeby dokonywać konwersji znakowych. Wyjątek stanowi przesyłanie znaków do strumieni – musimy dokonać konwersji kodu, aby w strumieniu został zapisany znak, a nie jego kod jako liczba całkowita.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje z klawiatury łańcuch znaków do zmiennej łańcuchowej, a następnie wypisuje kolejne literki wraz z ich kodami ASCII.

 

Lazarus
program prg;

var
  s : ansistring;
  i : integer;
begin
  readln(s);
  writeln;
  for i := 1 to length(s) do
    writeln(s[i],' : ',ord(s[i]):3);
  writeln;
end.
Code::Blocks
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

int main()
{
  string s;

  getline(cin,s);
  cout << endl;
  for(unsigned i = 0; i < s.length(); i++)
    cout << s[i] << " : " << setw(3) << (int)s[i] << endl;
  cout << endl;
  return 0;
}
Free Basic
Dim s As String, i As Integer

Input s
Print
For i = 1 To Len(s)
  Print Using "! : ###"; Mid(s,i,1); Asc(Mid(s,i,1))
Next
Print
End
Wynik
Aligator Arek

A :  65
l : 108
i : 105
g : 103
a :  97
t : 116
o : 111
r : 114
  :  32
A :  65
r : 114
e : 101
k : 107

 

Konkatencja – łączenie łańcuchów

Często zdarza się, iż chcemy połączyć dwa lub więcej tekstów w jeden tekst. Operacja łączenia tekstu nosi nazwę konkatencji (ang. concatenation). W przypadku łańcuchów jest to bardzo proste:

 

  Lazarus Code::Blocks Free Basic
Łączymy łańcuch s1 z s2
i wynik połączenia
umieszczamy w s3
s3 := s1 + s2;
s3 = s1 + s2;
s3 = s1 + s2

 

Wstawianie znaku/ciągu znaków do łańcucha

Podmiana znaku w łańcuchu jest operacją prostą. Po prostu odwołujemy się do wybranego elementu w zmiennej łańcuchowej – może nią być również tablica znaków – i zapisujemy go nową zawartością:

 

  Lazarus Code::Blocks Free Basic
Zamiana znaku
na pozycji i-tej
w łańcuchu s
s[i] := 'znak';
s[i] := char(kod);
s[i] = 'znak';
s[i] = kod
Mid(s,i,1) = "znak"
Mid(s,i,1) = Chr(kod)

 

Wstawienie znaku wymaga przesunięcia części znaków w zmiennej łańcuchowej, aby udostępnić miejsce na wstawiany znak. Operacja wstawiania znaku lub łańcucha znaków jest obsługiwana przez funkcje biblioteczne:

 

  Lazarus Code::Blocks Free Basic
Wstawiamy łańcuch s1
na pozycję i-tą
w łańcuchu s2
insert(s1,s2,i);
s2.insert(i,s1);
s2 = Left(s2,i-1) + s1 + Right(s2,Len(s2)-i+1)

 

Język FreeBasic nie posiada bezpośredniej funkcji wstawiania znaku lub łańcucha do innego łańcucha. Dlatego posiłkujemy się dwoma funkcjami pomocniczymi:

 

Left(s,i)  – zwraca i pierwszych znaków łańcucha s. Jeśli i = 0, to zwraca łańcuch pusty.
Right(s,i)  – zwraca i ostatnich znaków łańcucha s. Jeśli i = 0, to zwraca łańcuch pusty.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program umieszcza w łańcuchu tekstowym zdanie "Rudy lisek", a następnie wstawia łańcuch ", szybki" po słowie "Rudy".

 

Lazarus
program prg;

var
  s : ansistring;
begin
  s := 'Rudy lisek';
  writeln(s);
  insert(', szybki',s,5);
  writeln(s);
  writeln;
end.
Code::Blocks
#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;

  s = "Rudy lisek";
  cout << s << endl;
  s.insert(4,", szybki");
  cout << s << endl << endl;
  return 0;
}
Free Basic
Dim s As String

s = "Rudy lisek"
Print s
s = Left(s,4) + ", szybki" + Right(s,6)
Print s
Print
End
Wynik
Rudy lisek
Rudy, szybki lisek

 

Usuwanie znaku z łańcucha

Usunięcie znaku z łańcucha/tablicy polega na przesunięciu wszystkich znaków następujących za znakiem usuwanym o jedną pozycję w lewo. W ten sposób znak zostaje nadpisany znakiem sąsiadującym z prawej strony – w efekcie zniknie on z łańcucha. Dla łańcuchów znakowych mamy w każdym z wybranych języków programowania gotowe funkcje usuwania znaku lub fragmentu łańcucha.

 

  Lazarus Code::Blocks Free Basic
Usuwamy z łańcucha s
n znaków począwszy
od pozycji i-tej
delete(s,i,n);
s.erase(i,n);
s = Left(s,i-1) + Right(s,Len(s)-i-n+1)

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program umieszcza w łańcuchu tekstowym zdanie "Rakieta kosmiczna", a następnie usuwa z wyrazu "kosmiczna" literkę 's'.

 

Lazarus Code::Blocks Free Basic
program prg;

var
  s : ansistring;
begin
  s := 'Rakieta kosmiczna';
  writeln(s);
  delete(s,11,1);
  writeln(s);
  writeln;
end.
#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;

  s = "Rakieta kosmiczna";
  cout << s << endl;
  s.erase(10,1);
  cout << s << endl << endl;
  return 0;
}
Dim s As String

s = "Rakieta kosmiczna"
Print s
s = Left(s,10) + Right(s,6)
Print s
End
Wynik
  Rakieta kosmiczna
Rakieta komiczna
 

 

Zastępowanie fragmentu łańcucha innym łańcuchem tekstowym

Zastępując fragment łańcucha innym łańcuchem możemy wykorzystać funkcje usuwania i wstawiania tekstu – najpierw usuwamy zastępowany fragment z łańcucha, a następnie wstawiamy na jego miejsce nowy fragment. W języku C++ możemy wykorzystać funkcję składową replace() klasy string, która wykonuje dokładnie to samo zadanie. W języku FreeBasic wykorzystujemy funkcje Left() i Right().

 

  Lazarus Code::Blocks Free Basic
n znaków od pozycji i-tej
w łańcuchu s2 zastępujemy
łańcuchem s1
delete(s2,i,n);
insert(s1,s2,i);
s2.replace(i,n,s1);
s2 = Left(s2,i-1) + s1 + Right(s2,Len(s2)-i-n+1)

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program umieszcza w łańcuchu tekstowym zdanie "Zielone, stare drzewko", a następnie wymienia wyraz "stare" na "wysokie".

 

Lazarus Code::Blocks Free Basic
program prg;

var
  s : ansistring;
begin
  s := 'Zielone, stare drzewko';
  writeln(s);
  delete(s,10,5);
  insert('wysokie',s,10);
  writeln(s);
  writeln;
end.
#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;

  s = "Zielone, stare drzewko";
  cout << s << endl;
  s.replace(9,5,"wysokie");
  cout << s << endl << endl;
  return 0;
}
Dim s As String

s = "Zielone, stare drzewko"
Print s
s = Left(s,9) + "wysokie" + Right(s,8)
Print s
End
Wynik
  Zielone, stare drzewko
Zielone, wysokie drzewko
 

 

Porównywanie łańcuchów

Łańcuchy tekstowe możemy porównywać przy pomocy typowych operatorów porównań. Jednakże obowiązuje tutaj kilka zasad.

Dwa łańcuchy są równe, jeśli składają się z takiej samej liczby znaków oraz zgadzają się ze sobą na każdej pozycji znakowej.

Jeśli dwa łańcuchy mają różną długość, lecz krótszy łańcuch zawiera te same początkowe znaki c łańcuch dłuższy, to krótszy jest mniejszy, a dłuższy jest większy.

W dwóch łańcuchach porównywane są znaki na odpowiadających sobie pozycjach znakowych aż do napotkania niezgodności kodów. Wtedy mniejszy łańcuch jest tym, który posiada na porównywanej pozycji znak o mniejszym kodzie. Na przykład:

"ALA" > "AKACJA" – kod literki L jest większy od kodu literki K.

Taki sposób porównywania nosi nazwę leksykograficznego. Zwróć uwagę, iż w ten sposób nie można porównywać łańcuchów zawierających polskie litery – poprawny będzie jedynie test na równość łańcuchów.

 

Pozostałe operacje tekstowe

W poniższej tabelce zebraliśmy często wykonywane, typowe operacje na tekstach. Z operacji tych będziemy intensywnie korzystać w przykładach programowych do omawianych algorytmów tekstowych.

 

  Lazarus Code::Blocks Free Basic
Odczyt wiersza znaków
ze standardowego wejścia
readln(s);
write('opis'); readln(s) 
getline(cin,s);
cout << "opis"; getline(cin,s)
Line Input s
Line Input "opis";s
Zapis łańcucha znaków
na standardowe wyjście
writeln(s);
write(s);
cout << s << endl;
cout << s;
Print s
Print s;
Sprawdzenie,
czy łańcuch jest pusty
if s = '' then ...
if length(s) = 0 then ...
if(s == "") ...
if(!s.length())...
if(!s.size())...
If s2 = "" Then ...
If Len(s2) = 0 Then ...
Kopiowanie n znaków
łańcucha s1 od pozycji i-tej
do łańcucha s2
s2 = copy(s1,i,n);
s2 = s1.substr(i,n);
s2 = Mid(s1,i,n)
Kopiowanie n początkowych
znaków łańcucha s1
do łańcucha s2
s2 = copy(s1,1,n);
s2 = s1.substr(0,n);
s2 = Left(s1,n)
Kopiowanie n końcowych
znaków łańcucha s1
do łańcucha s2
s2 = copy(s1,length(s1)-n+1,n);
s2 = s1.substr(s1.length()-n);
s2 = Right(s1,n)

 



List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.