Podstawy Programowania
Wykład ósmy:
Typy łańcuchowe
1.Budowa zmiennych typu  string
Dotychczas traktowaliśmy typ string (łańcuch znaków) jako typ prosty. Mając
wiedzę na temat tablic jednowymiarowych możemy poznać jego budowę we-
wnętrzną. Typ ten jest tablicą domyślnie zawierającą 256 elementów. Indeksy
tej tablicy są typu byte, natomiast wartości elementów mają typ char. Możemy
stworzyć typ łańcuchowy o mniejszej liczbie elementów definiując go w części
type programu lub podprogramu, według następującego wzoru:
nazwa_typu = string[rozmiar];
gdzie rozmiar jest wartością1 typu byte:
type
lancuch = string[50];
Zmienne2 tego typu deklarujemy według tego samego wzorca, co zmienne in-
nych typów definiowanych przez programistę. Istnieje również możliwość za-
deklarowania zmiennej o anonimowym typie łańcuchowym np.:
l:string[40];
Ta deklaracja posiada ograniczenie znane z innych typów anonimowych: nie
możemy zadeklarować parametrów formalnych o takim typie. Nie stanowi to
jednak problemu, jeżeli będziemy przekazywać parametry wywołania przez sta-
łą lub wartość3. W takich przypadkach możemy parametr formalny zadekla-
rować jako parametr typu string. Niezależnie od tego jaką podstawimy za ten
parametr zmienną łańcuchową będzie ona traktowana, jako zmienna typu
string. Ta sama sytuacja zachodzi, jeśli parametrem wywołania będzie wartość,
czyli tekst ujęty w apostrofy. Niestety, to rozwiązanie nie może być użyte
w przypadku kiedy przekazujemy parametr przez zmienną. W takiej sytuacji
kompilator zgłosi błąd, jeśli parametr wywołania będzie innego typu niż string.
Stosowanie parametrów formalnych, których typ jest nazwanym typem ła-
ńcuchowym też może prowadzić do błędów. Jeśli za parametr formalny, który
ma typ łańcuchowy pozwalający przechowywać np. 30 znaków, podstawimy,
stosując przekazanie przez wartość, zmienną typu string, lub innego typu ła-
ńcuchowego, który pozwala na przechowanie większej liczby znaków niż 30, to
 nadmiarowe znaki z parametru wywołania zostaną w parametrze formalnym
pominięte. Podobnie zachowuje się instrukcja przypisania  pozwala na przypi-
1 Ta wartość może być również wartością stałej lub wyrażenia stałego.
2 Mogą to być również zmienne zainicjalizowane.
3 Ponieważ typ string jest tablicą, to przekazywanie przez wartość nie jest zalecane.
2
sanie zmiennej  krótszego typu łańcuchowego wartości zmiennej  dłuższego
typu łańcuchowego. Inaczej działa przekazanie przez stałą. W tym wypadku
parametr formalny  przyjmuje typ parametru wywołania, co zapobiega utracie
znaków z przekazywanego łańcucha. Znaki w zmiennych typów łańcuchowych
są przechowywane w pewien charakterystyczny sposób. Otóż zmienna typu
string ma rozmiar 256 bajtów, ale można w niej przechować maksymalnie 255
znaków. Podobnie zmienne zdefiniowanego przez nas wyżej typu lancuch mogą
przechowywać 50 znaków, ale ich rozmiar wynosi 51 bajtów. Program, którego
kod z
ródłowy jest zamieszczony poniżej pozwoli nam zbadać budowę we-
wnętrzną typów łańcuchowych:
program lancuchy_znakow;
uses
crt;
type
lancuch_1 = string[20];
lancuch_2 = string[40];
var
x:lancuch_1;
y:lancuch_2;
z:string;
procedure wypisz(const a:string);
var
i:byte;
begin
writeln('Paramet ''a'' ma rozmiar ',sizeof(a),' bajtów.');
writeln('Indeks pierwszego elementu w zmiennej typu string ma wartość: ',low(a));
writeln('Indeks ostatniego elementu w zmiennej typu string ma wartość: ',high(a));
for i:=low(a) to high(a) do write(a[i]);
writeln;
writeln('Kod ASCII zerowego elementu łańcucha: ',ord(a[0]));
end;
begin
clrscr;
writeln('Rozmiar zmiennej ''x'' wynosi: ',sizeof(x),' bajtów.');
3
 writeln('Rozmiar zmiennej ''y'' wynosi: ',sizeof(y),' bajtów.');
writeln('Rozmiar zmiennej ''z'' wynosi: ',sizeof(z),' bajtów.');
readln;
x:='Ala ma kota.';
z:=x;
wypisz(z);
readln;
end.
W bloku głównym programu wpisywana jest wielkość każdej ze zadeklarowa-
nych zmiennych typów łańcuchowych. Następnie przypisujemy zmiennej x typu
lancuch_1 pewien ciąg znaków. W kolejnej instrukcji wartość tej zmiennej
przypisujemy zmiennej z typu string. Następnie wywołujemy procedurę wypisz,
której parametrem wywołania jest zmienna z. Procedura ta traktuje zmienną
typu string jak tablicę. Wypisuje jej wielkość, wartości indeksów pierwszego
i ostatniego elementu oraz wartości poszczególnych elementów tej tablicy.
Z informacji umieszczonych przez tę procedurę na ekranie możemy się
dowiedzieć, że pierwszy element zmiennej typu łańcuchowego ma indeks o war-
tości zero i zawiera on znak nie należący do napisu. Wartość kodu ASCII tego
znaku odpowiada liczbie liter w napisie. Ustaliliśmy więc, że definiując nowy
typ łańcuchowy podajemy maksymalną liczbę znaków, jaka może być
przechowywana w zmiennych tego typu. Faktyczna długość ciągu znaków4,
który jest w zmiennej tego typu przechowywany jest zapisana w elemencie
łańcucha o indeksie zero. Jeśli użyjemy typu łańcuchowego string, to będziemy
mogli zapisać w nim maksymalnie 255 znaków.
2.Operatory i typ łańcuchowy
Operator  + działa ze zmiennymi typów łańcuchowych. Służy on do łączenia
dwóch lub większej liczby łańcuchów znaków w jeden łańcuch. Jeśli wynikowy
ciąg znaków ma więcej elementów niż może pomieścić zmienna w której zapi-
sywany jest wynik, to nadmiarowe znaki są  ucinane . Operator  + dla ła-
ńcuchów znaków nazywa się operatorem łączenia lub konkatenacji. Do ła-
ńcuchów znaków można stosować również operatory relacyjne  = ,  < ,  > ,
 <> ,  <= ,  >= . Operator  = zwraca wartość true, jeśli oba porównywane ła-
ńcuchy zawierają takie same znaki. Operator  <> zwraca wartość true jeśli ła-
ńcuchy różnią się choć jednym znakiem, lub jeśli jeden ciąg znaków jest podci-
ągiem drugiego. Operator  < porównuje kody ASCII znaków znajdujących się
4 Nazywana także długością dynamiczną.
4
w łańcuchach5. Najpierw porównywana jest pierwsza para znaków. Jeśli oba
znaki są takie same, to porównywana jest następna para, aż zostaną znalezione
dwa różne znaki i będzie można ustalić, który ciąg jest mniejszy, lub gdy nie
będzie w obu ciągach więcej par znaków.
W przypadku ciągów, które są po-
kazane na ilustracji, ciąg  krew
jest ciągiem mniejszym, bo znak
k r o w a
 o ma kod ASCII o większej war-
tości niż znak  e 6. Jeżeli jeden
z porównywanych ciągów znaków
byłby podciągiem innego, to on
k r e w
jest uznawany za mniejszy (bo za-
wiera mniejszą liczbę znaków). Na
podobnej zasadzie działają pozo-
stałe z wymienionych operatorów
relacyjnych. Operatory te można
np.: zastosować do sortowania tablic elementów typu string:
program sortowanie_lancuchow;
uses
crt;
type
tablica_lancuchow = array [1..6] of string;
const
bazowa:tablica_lancuchow=
('Bruksela','Amsterdam','Antwerpia','Kraków','Wiedeń','Warszawa');
procedure wypisz(const t:tablica_lancuchow);
var
i:byte;
begin
for i:=low(t) to high(t) do write(t[i],' ');
writeln;
end;
5 Jeśli tymi znakami są litery, to duże litery są uznawane za mniejsze, bo np.: litera  A ma kod
ASCII równy 65, natomiast litera  a ma kod ASCII równy 97.
6 Oczywiście znak  e występuje również w alfabecie wcześniej niż znak  o . Takie uzasadnienie
przestaje jednak wystarczać jeśli porównujemy ciągi zawierające inne znaki niż litery.
5
procedure sortuj(var t:tablica_lancuchow);
var
i,j,k:byte;
tmp:string;
begin
for i:=low(t) to high(t)-1 do
begin
k:=i;
for j:=i+1 to high(t) do
if t[k]>t[j] then k:=j;
if k<>i then
begin
tmp:=t[i];
t[i]:=t[k];
t[k]:=tmp;
end;
end;
end;
begin
clrscr;
wypisz(bazowa);
readln;
sortuj(bazowa);
wypisz(bazowa);
readln;
end.
Proszę zauważyć, że procedura sortuj jest niewielką  przeróbką procedury
selection_sort z poprzedniego wykładu. Poza zmianą typu zmiennej, w której za-
pamiętywana jest tymczasowo wartość modyfikowanego elementu oraz zmianą
typu parametru nie są konieczne inne modyfikacje.
3.Operacje na zmiennych łańcuchowych
Twórcy środowisk Turbo Pascal i Fee Pascal dostarczają szereg gotowych funk-
cji i procedur pozwalających wykonać podstawowe operacje na łańcuchach,
6
takie, jak wstawienie ciągu znaków wewnątrz innego lub jego usunięcie.
Wszystkie te podprogramy zostały zebrane w tablę, która oprócz ich nazw
zawiera również opis sposobu ich wywołania, oraz opis ich działania:
Funkcja Upcase(znak), jako parametr wywo- Zmienia małą literę na dużą. Środowisko
FreePascal ma jej wersję przeciążoną, która
łania przyjmuje wartość lub zmienną typu
zamienia litery na duże w ciągu znaków.
char, zwraca wartość również typu char.
Funkcja Length(ciąg) przyjmuje jeden argu- Zwraca liczbę znaków, które zostały zapisane do
ment wywołania będący zmienną typu ła- zmiennej typu łańcuchowego, która została
przekazana jej przez parametr.
ńcuchowego. Zwraca wartość typu integer.
Funkcja Pos(cszuk, ciag), jako parametry wy- Zwraca miejsce pierwszego wystąpienia szu-
kanego ciągu w ciągu przeszukiwanymi. Jeśli
wołania przyjmuje ciąg, którego wystąpienie
zwróci zero, to szukany ciąg nie występuje
ma zostać znalezione (cszuk), oraz ciąg, który
w ciągu przeszukiwanym.
należy przeszukać (ciag). Zwraca wartość
typu byte.
Procedura Insert(z
ródło,cel,pozycja) przyj- Wstawia ciąg z
ródłowy do ciągu docelowego
w określonym miejscu. Jeśli ciąg wynikowy ma
muje trzy parametry wywołania. y
ródło to
więcej znaków niż można zmieścić w zmiennej
ciąg, który należy wstawić, cel to ciąg do
cel, to niemieszczące się znaki zostają po-
którego należy wstawić z
ródło, natomiast po-
minięte.
zycja określa gdzie ciąg z
ródłowy ma być
wstawiony w ciągu docelowym.
Usuwa określoną liczbę znaków z ciągu począw-
Procedura Delete(ciąg,pozycja,ile) przyjmuje
szy od znaku na zadanej pozycji. Jeśli w ciągu
trzy parametry wywołania. Pierwszy to ciąg,
jest mniej znaków niż chcemy usunąć, to zosta-
z którego mają zostać usunięte znaki, drugi
ną usunięte tylko te istniejące znaki.
określa pozycję pierwszego znaku, który ma
zostać usunięty, natomiast ostatni określa
liczbę znaków do usunięcia.
Zwraca łańcuch zawierający określoną liczbę
Funkcja Copy(ciąg, pozycja, ile) przyjmuje
znaków z łańcucha, który został jej przekazany
trzy parametry wywołania: ciąg, z którego
jako pierwszy parametr.
znaki będą kopiowane, pozycja znaku od
którego należy zacząć kopiowanie i liczbę
znaków do skopiowania. Zwraca wartość
typu string.
Funkcja, ta działa tak samo jak operator  + .
Funkcja Concat(c1,c2) przyjmuje dwa lub
Zwraca łańcuch będący połączeniem wszystkich
większą liczbę parametrów wywołania typu
łańcuchów, które zostały przekazane jej jako
łańcuchowego. Zwraca wartość typu string.
parametry wywołania.
Zanim zostanie pokazany przykład zastosowania tych podprogramów spróbuje-
my napisać własne funkcje i procedury o działaniu podobnym do tych, które
zostały przedstawione wyżej. Rozpocznijmy od funkcji Length i napiszmy funk-
cję dlugosc, która będzie działała w ten sam sposób. Aby uzyskać liczbę znaków
zapisaną w zmiennej typu łańcuchowego wystarczy odczytać znak z elementu
łańcucha o indeksie zero i poznać jego kod ASCII. Oto funkcja, która działa
w ten sposób:
7
function dlugosc(const a:string):byte;
W przeciwieństwie do funkcji Length zwra-
begin
ca wartość typu byte, a nie typu integer.
dlugosc:=ord(a[0]);
end;
Kolejną funkcją, której działanie spróbujemy poznać będzie funkcja UpCase,
jednakże nie będziemy starali się napisać jej odpowiedniczki. Zauważmy, że nie
mamy funkcji, która byłaby do niej komplementarna, tzn. takiej, która
zamieniałaby duże litery na małe litery. Napiszmy więc funkcję DownCase,
która realizowałaby tę operację. Zauważmy, że litera  A ma kod ASCII równy
65, a litera  a - 97. Jeśli więc chcielibyśmy zamienić literę  A na  a , to do jej
kodu ASCII musielibyśmy dodać 32 (wynik operacji 97-65). Tą samą metodę
możemy zastosować dla pozostałych liter. Oto funkcja realizująca ten algorytm:
function downcase(a:char):char;
Zanim przystąpimy do konwersji
begin
znaku musimy się upewnić, że ten
downcase:=a;
znak jest dużą literą, stąd w funkcji
if (a>='A') and (a<='Z') then
pojawia się odpowiednia instrukcja
warunkowa. Jeśli przekazany przez
begin
parametr znak nie jest dużą literą, to
downcase:=chr(ord(a)+(ord('a')-ord('A')));
jest po prostu przez funkcję
end;
zwracany.
end;
Bardziej skomplikowany algorytm wykonuje procedura delete. Aby usunąć
znaki z ciągu musimy przesunąć na ich miejsce znaki znajdujące się za nimi:
A l a m a k o t a .
Po wykonaniu tej operacji należy zmodyfikować pierwszy element łańcucha, tak
aby zawierał nową liczbę znaków. Opisany algorytm zrealizujemy nie w postaci
procedury lecz w postaci funkcji. Zauważmy, że w przypadku tego algorytmu
8
możemy podać błędne dane wejściowe, takie jak zbyt duża liczba znaków do
usunięcia, lub błędna pozycja pierwszego ze znaków, który będziemy chcieć
usunąć. W takich wypadkach nasza funkcja zwróci odpowiednio wartości -1
i -2. Jeśli operacja usuwania przebiegnie pomyślnie funkcja zwróci wartość 0.
Opisane tu sytuacje wyjątkowe nie są wszystkimi wyjątkami jakie mogą się
pojawić, ale skupimy się tylko na nich. Oto kod naszego odpowiednika proce-
dury delete:
function usun(var skad:string; odkad,ile:byte):shortint;
var
i:byte;
begin
if ile>length(skad) then
begin
usun:=-1; {Próba usunięcia większej liczby znaków niż jest w łańcuchu.}
exit;
end;
if odkad>length(skad) then
begin
usun:=-2; {Próba usunięcia znaków spoza łańcucha.}
exit;
end;
for i:=odkad to length(skad) do {Usunięcie znaków.}
skad[i]:=skad[i+ile];
skad[0]:=chr(length(skad)-ile); {Zapisanie nowej długości.}
usun:=0; {Operacja usuwania zakończona pomyślnie.}
end;
Operacja przesunięcia znaków, o zadaną odległość (ile) jest realizowana w pętli
for. Po jej zakończeniu należy jeszcze w elemencie łańcucha o indeksie zero za-
pisać nową liczbę znaków w łańcuchu. Jeszcze bardziej skomplikowany al-
gorytm jest realizowany przez procedurę Insert. W jej wypadku należy najpierw
 rozsunąć znaki w oryginalnym ciągu, aby zrobić miejsce na nowe i dopiero po
wykonaniu tej czynności je wstawić. Ostatni krok polega oczywiście na zapisa-
niu do elementu o indeksie zero, nowej liczby znaków w łańcuchu. Pisząc naszą
wersję procedury Insert zrealizujemy ją jako funkcję, która będzie zwracała
wartość -1 jeśli będziemy próbować wstawić nowe znaki poza oryginalnym
ciągiem, -2 jeśli wynikowy ciąg będzie miał więcej niż 255 znaków i zero, jeśli
operacja wstawiania przebiegnie bezproblemowo. Oto kod tej funkcji:
9
function wstaw(const co:string; var gdzie:string; odkad:byte):shortint;
var
i:byte;
begin
if odkad > length(gdzie)+1 then
begin
wstaw:=-1; {Wstawienie znaków poza łańcuchem.}
exit;
end;
if length(co)+length(gdzie)>255 then
begin
wstaw:=-2; {Ciąg wynikowy miałby więcej niż 255 znaków.}
exit;
end;
for i:=length(gdzie) downto odkad do {"Przesunięcie" końca napisu.}
gdzie[i+length(co)]:=gdzie[i];
for i:=1 to length(co) do {Wpisanie nowego łańcucha.}
gdzie[odkad+i-1]:=co[i];
gdzie[0]:=chr(length(gdzie)+length(co)); {Zapisanie nowej długości.}
wstaw:=0; {Operacja wstawiania wykonana prawidłowo.}
end;
 Rozsunięcie znaków w oryginalnym ciągu jest dokonywane w pierwszej pętli
for. Proszę zwrócić uwagę, że przesuwanie znaków rozpoczynamy od ostatniego.
W drugiej pętli for kopiujemy znaki z ciągu wstawianego do ciągu oryginalnego,
umieszczając je w przygotowanym wcześniej miejscu. Ostatnią czynnością
związaną z manipulacją elementami ciągu jest wstawienie do elementu
zerowego ciągu nowej liczby znaków. Poniżej znajduje się ilustracja
wyjaśniająca, działanie funkcji wstawiania ciągu w inny ciąg.
10
A l a k o t a .
m a
A l a k o t a .
m a
A l a k o t k o t a .
m a
A l a m a k o t a .
Ostatnią funkcją, której działanie spróbujemy  powielić będzie funkcja pos.
Istnieje szereg algorytmów, które służą do wyszukiwania wzorca w tekście.
Tutaj zaimplementujemy najprostszy z nich, tak zwany algorytm wyszukiwania
naiwnego. Aby stwierdzić, czy jakiś ciąg występuje w innym ciągu będziemy
najpierw sprawdzać, czy występuje w przeszukiwanym ciągu jego pierwszy
znak. Jeśli tak, to sprawdzamy, czy za tym znakiem znajdują się wszystkie
pozostałe znaki z tego ciągu. Jeżeli tak, zwracamy pozycję wystąpienia
pierwszego znaku w przeszukiwanym ciągu. Poniżej zamieszczony jest kod
z
ródłowy funkcji, która realizuje naiwne wyszukiwanie:
11
function naiwne_wyszukiwanie(const co,gdzie:string):byte;
var
i,j:byte;
begin
naiwne_wyszukiwanie:=0;
for i:=1 to length(gdzie) do
if gdzie[i]=co[1] then
begin
j:=2;
while (j<=length(co)) and (j+i-1<=length(gdzie)) do if co[j]=gdzie[i+j-1] then inc(j) else break;
if j-1=length(co) then
begin
naiwne_wyszukiwanie:=i;
exit;
end;
end;
end;
W pętli for szukamy wystąpienia pierwszego znaku ciągu którego poszukujemy
w przeszukiwanym ciągu. Jeśli znajdziemy taki znak, to w pętli while
sprawdzamy, czy pozostałe też są takie same jak we wzorcu. Pętla ta kończy
się, kiedy znaki w ciągach przestaną się zgadzać, lub gdy wartości wyrażeń
indeksujących (i, j+i-1) przekroczą rozmiar któregoś z łańcuchów. Po
zakończeniu tej pętli badamy, czy liczba znaków, które się zgodziły (j-1) jest
równa liczbie znaków we wzorcu, jeśli tak, to znalez
liśmy wystąpienie wzorca
w ciągu przeszukiwanym. Proszę zauważyć, że pętla while rozpoczyna badanie
wzorca od drugiego elementu. Pierwszy element możemy pominąć, gdyż jego
znalezienie jest warunkiem, aby wykonanie pętli while mogło się rozpocząć.
Na zakończenie opisu operacji na łańcuchach przedstawmy prosty program,
który za pomocą predefiniowanych procedur i funkcji znajduje wszystkie
wystąpienia danego ciągu znaków w innym ciągu i zastępuje go nowymi
znakami:
program znajdz_i_zastap;
uses
crt;
type
12
 lancuch_1 = string[10];
lancuch_2 = string[20];
var
zrodlo:string;
wzorzec:lancuch_1;
zastapienie:lancuch_2;
procedure sar(var zr:string; const w:lancuch_1; const za:lancuch_2);
var
i:byte;
begin
repeat
i:=pos(w,zr);
if i<>0 then
begin
delete(zr,i,length(w));
insert(za,zr,i);
end;
until i=0;
end;
begin
clrscr;
write('Podaj napis: ');
readln(zrodlo);
write('Podaj wzorzec: ');
readln(wzorzec);
writeln('Podaj czym zastąpić: ');
readln(zastapienie);
writeln(zrodlo);
sar(zrodlo,wzorzec,zastapienie);
writeln(zrodlo);
readln;
end.
13
Opisana operacja jest realizowana w całości w procedurze sar. Przez parametr
formalny zr jest przekazywany ciąg z
ródłowy, przez w wzorzec, a przez za ciąg,
którym zostanie zastąpiony wzorzec. Ciąg wzorcowy jest wyszukiwany w pętli
repeat. Jeśli funkcja pos zwróci wartość różną od zera, to wzorzec występujący
na tej pozycji jest usuwany z ciągu z
ródłowego za pomocą procedury delete
i zastępowany ciągiem przekazanym przez za, za pomocą procedury insert.
Pętla repeat kończy się, kiedy funkcja pos zwróci wartość zero.
4.Znaki specjalne
Oprócz znaków drukowalnych, w kodzie ASCII występują również znaki
sterujące. Znak o kodzie 13 to znak  powrotu karetki (ang. carriage return),
który powoduje przejście kursora do początku wiersza7. Można go wstawić do
ciągu znaków w następujący sposób:
x:='Bardzo '#13'długi napis';
lub w ten sposób:
x := 'Bardzo '^M'długi napis';
Znak o kodzie ASCII równym 10, który możemy zapisać jako ^J, to znak nowej
linii (ang. line feed), który powoduje przejście kursora do nowego wiersza na
ekranie. Na końcu każdego wiersza tekstu wyświetlonego na monitorze
znajdują się więc dwa znaki: #13#10. Znak o kodzie ASCII równym 8 (^H), to
znak, który po angielsku nazywa się backspace. Powoduje on skasowanie
znaku, który znajduje się po lewej stronie kursora. Jeśli chcemy w ciągu
znaków umieścić apostrof, to musimy poprzedzić go innym apostrofem, czyli
napisać: ''.
7 Jest to również znak klawisza  Enter .
14